7 ms·

Lossless video compression using Bloom filters

346 points by rh3939 1y ago

deleted 1y ago
[deleted]
chungy 1y ago
I'm confused by the README. It makes references to YouTube video, but also "lossless video". Is this about recompressing existing H.264[1] videos (like downloaded from YouTube) losslessly, or is it about making new videos from a source losslessly? The former reminds me of JPEG XL's ability to re-compress the DCT on old JPEGs, but even as you get better compression, you still don't have a lossless image. [1] To be fair, H.264 can be lossless in the first place, but YouTube does not serve up such files.
- perching_aix 1y ago
  I think it's safe to assume that the author is reencoding those YouTube samples there, so vp9/avc/av1 -> uncompressed -> compressed with this, and that the compression ratio is with respect to the uncompressed stream. Otherwise I think the README would sound quite a bit more enthusiastic :)
- runeblaze 1y ago
  Yeah probably if they were writing a paper, encoding `.raw` files would have served them better (for being more convincing)
- magicalhippo 1y ago
  The introduction seems quite clear on it being an alternative to H.264 and friends: Traditional video codecs like H.264 and H.265 achieve impressive compression by discarding "imperceptible" visual information. But what if we could guarantee perfect reconstruction while still achieving meaningful compression? This project explores an unconventional approach: repurposing Bloom filters—typically used for membership testing—as a lossless video compression mechanism. Further down comes the explanation for why this scheme might possibly work: Rather than compressing whole video frames, this system applies Bloom filter compression to frame differences. This capitalizes on temporal coherence—most pixels change little (or not at all) between consecutive frames, creating a sparse difference matrix ideal for this approach. Of course, using delta-frame compression has been a common theme of many video codecs for ages now, and many like H.264 and H.265 use additional techniques like motion estimation[1] to reduce the information in the delta frame further before final entropy coding step[2][3]. As such, the best is probably to view this as an alternative to the entropy encoding in H.264 or similar. [1]: https://en.wikipedia.org/wiki/Motion_estimation#Video_coding https://en.wikipedia.org/wiki/Motion_estimation#Video_coding [2]: https://en.wikipedia.org/wiki/Context-adaptive_variable-length_coding https://en.wikipedia.org/wiki/Context-adaptive_variable-leng... [3]: https://en.wikipedia.org/wiki/High_Efficiency_Video_Coding#Entropy_coding https://en.wikipedia.org/wiki/High_Efficiency_Video_Coding#E...
- rh3939 1y ago
  Author here. Totally agree that H.264 can be lossless. Generally its lossy. My idea(which I am still working out) is to compress the difference of frames using a rational bloom filter. I previously posted here about using conditional bloom filter that rely on rational k. The idea was to use different values of k based on whether the url was more likely to be malicious than not. This results in a lower fp rate for the same filter size when compared to integer k. I then saw this paper[https://arxiv.org/html/2502.02193v2 https://arxiv.org/html/2502.02193v2] was posted recently which describes an almost identical approach(theirs is much nicer). I will do much more rigorous testing as my current setup is a bit sloppy but I hope it illustrates the idea.
  - pipo234 1y ago
    I think you might be able to compress I and P frames somewhat descent, this way. But you only seem to address spatial domain, except for deltas(?) Or do you have some way to apply bloom filters to motion estimation as well?
  - wging 1y ago
    So it sounds like the use of rational Bloom filters here is just to get a better compression ratio, but the basic technique could be used with classic Bloom filters—is that right? Do you know how much you gain in space savings from using rational Bloom filters? It’s not obvious to me how much of a gain it would be.
deleted 1y ago
[deleted]
clayhacks 1y ago
I see you put how to calculate the compression ratio, but do you have some examples of worst case, average, and best case compression ratios? Edit: ok I see the photos in the repo. Putting them in the README would be helpful
- rh3939 1y ago
  Author here. The repo is a complete mess but I do have some some code in there to generate graphs and whatnot if you're willing to dig through the code. I will make this much more concrete with lots of proper testing. Its very much still a messy work in progress.
  - codetrotter 1y ago
    I applaud you for uploading even if it’s a bit disorganised still, and I do the same. It’s better to have something than nothing. Sometimes I see people talking about something but they don’t want to upload their code yet because they have to clean it up first. And then either they don’t get around to ever cleaning it up the way they wanted, or by they time they do it will have fallen off everyone’s radar and be forgotten. At least with a messy repo it’s possible to poke around, and not the least to star it and maybe check back later to see if they cleaned it up.
Dwedit 1y ago
It's also possible to run codecs like H.264 in a true lossless mode, it's just almost never done.
- perching_aix 1y ago
  Yup, even got it to work with hardware acceleration via NVENC. Playback was tough though, ffplay would work it, but nothing else.
bob1029 1y ago
> The key insight: when a binary string has a low density of 1s (specifically below p* ≈ 0.32453), we can encode just the positions of those 1s more efficiently than storing the raw string. Much of what JPEG/MPEG are doing is rearranging the problem such that it is possible to create long runs of zeroes. The way in which a DCT block is scanned relative to the location of its AC/DC components is potentially one of the most innovative aspects of many video & image compression techniques.
- cogman10 1y ago
  I don't believe this is correct. What the DCT does along with the color representation transformation is to turn fine details into higher frequencies and core details into low frequencies. From there, the quality of the image and thus compression ratio is as simple as dropping high frequency representations. And besides that, jpegs use a Huffman table to further reduce the size of the image. AFAIK, it doesn't do anything special to reduce runs. So lining up zeros really doesn't help much.
  - IshKebab 1y ago
    This is true, but OP was also correct. The DCT components are quantised and encoded in an order such that you get a long string of 0s at the end (the high frequencies).
  - Retr0id 1y ago
    Dropping (or rather, heavily quantizing) the high frequency components does create runs of zeroes with high probability. The order the components are stored (a diagonal zig-zag) pushes the likely-to-be-zero elements together. At higher quality settings you might not have actual runs of zeroes, but you'll at the least have runs of low-entropy values.
  - brigade 1y ago
    Dropping the high frequencies does create zero runs, and even JPEG encodes zero runs as a run-length (RRRR in the spec) But DCT isn't very useful for lossless since any lossless frequency domain representation requires more range than the source, and you can't quantize to counter it.
meindnoch 1y ago
So, according to your graph [1] this new compression is always strictly worse than just using GZIP? [1] https://github.com/ross39/new_bloom_filter_repo/blob/main/compression_comparison.png https://github.com/ross39/new_bloom_filter_repo/blob/main/co...
- Retr0id 1y ago
  It's absent from this graph, but I'd imagine the bloom filter approach could be at least be faster than gzip. But I don't see perf metrics anywhere else...
  - croemer 1y ago
    Why would it be faster? You have to do all that hashing and lookup of witness data etc. Also, if you want fast, good compression, use zstandard not gzip.
    - Retr0id 1y ago
      gzip (and zstandard) decompression is inherently serial, whereas many bloom filter lookups can be as parallel as you like.
      - alexjurkiewicz 1y ago
        You can de/compress multiple streams in parallel, at minimal cost of overall efficiency. For gzip, look at pigz. For video, look at how x264/x265 slice up the video frame.
      - croemer 1y ago
        Parallelism isn't speed. Zstandard decompression is insanely fast, no need for occupying multiple cores.
        Retr0id 1y ago
        Bloom filter lookups are embarrassingly parallel to the point that you could occupy 0 CPU cores and do it in a GPU fragment shader. There are probably other reasons why this is a bad idea but I'm curious to try it.
mxfh 1y ago
I have trouble following the motivation here. Isn't the idea of lossless pretty meaningless for all consumer grade purposes, especially if the input example was already mangled through YouTube's transcoders? Besides possibly going from some MPEG1 or older to .h264/like lossless transcoding, I see no benefit in lossless methods here. From my personal experience, I tried archiving some of my old DVDs where no better sources are available for purchase for the forseeable future by transcoding to even .265 at absurdly high bitrates, but they all looked worse at higher bitrates than simply re-containerized MPEG2 for media-server streaming. All you do is transcode the output of an existing compressing wasting information with conserving artifacts from a prior reductive step. 4:4:4 LOG or something would be a target to benchmark here. Even "lossy" Apple ProRes start out at 275 Mbit/s for ProRes 4444 at HD25p already. https://en.wikipedia.org/wiki/Apple_ProRes#Data_rates https://en.wikipedia.org/wiki/Apple_ProRes#Data_rates
- perching_aix 1y ago
  I think you're in a misunderstanding indeed. This is not about lossless being practical now with this, or about reeconding YouTube videos with this providing any practical utility, or anything. It's just about using bloom filters for compression. The motivation was just the technical interest in bloom filters. They say as much in the readme: > This project explores an unconventional approach: repurposing Bloom filters—typically used for membership testing—as a lossless video compression mechanism. The video source is practically irrelevant as long as it's an actual video.
  - mxfh 1y ago
    I just don't get why it's reinventing the whole wheel here – try using an off-the-shelf codec and tack on a sparse correction. For example, encode frames with a modern lossless/near-lossless codec (AV1 with QP=0) and then append a tiny bitmask+delta residual for perfect reconstruction. These codecs already exploit motion compensation, intra-prediction and DCT-like transforms to minimize frame-to-frame deltas. In practice you’d likely get better compression (and faster progress) by piggybacking on AV1 strengths – then use Bloom-filter trick just on the leftover sparse differences – rather than building a new codec from scratch. The residuals can be expected to be quite noisy and will likely not profit from any intra frame predictability anymore. JPEG XL’s lossless engine already improves on PNG by ~35%, that and other general purpose compression methods would then be the per frame benchmark here on the residuals to beat. In short: use the proven gear (motion-compensated blocks + modern transforms) to do the heavy lifitng, then let the bloom filter chase the hopefully comparably small residual. As a showcase of what bloom filters are this would be still worthwhile, but I don't see any practical benefit here yet. Not to forget, there is a reason visually lossless is the de facto the norm now, even in production grade environments, storage space is still not free while the average uncompressed display stream easily reaches way north of 5Gbps now easily, there is only so much lossless can resonably do here.
vintermann 1y ago
This is a cute concept, but if you have a sparse binary string, you can probably do better with traditional methods!
- croemer 1y ago
  Indeed, as this comparison with gzip shows: https://github.com/ross39/new_bloom_filter_repo/blob/main/compression_comparison.png https://github.com/ross39/new_bloom_filter_repo/blob/main/co...
antirez 1y ago
I don't believe the document does a great job in explaining what is otherwise a very simple idea (assuming I understood it well): 1. It creates a bitmap where each bit is a pixel in the image, if from frame 0 to frame 1 a given pixel changed, the corresponding bit is 1, otherwise it is 0. 2. All the 1s are added to the bloom filter, hashing their offsets. Now the bloom filter will be positive for all such indexes plus a percentage of false positive indexes. 3. We query the bloom filter to see all the indexes that are positive, and for all such pixels we store the raw pixel data of what changed. So we can reconstruct the next frame easily. You can think at this like as storing the delta between two frames as: x,y,r,g,b of all the pixels that changed, but compressing a lot the x,y part at the cost of storing a bit more r,g,b than needed. I have the feeling that since the pixels that changes from frame 0 to frame 1 are often similar (in their location) to what will change from frame 1 to frame 2, there is the possibility of further compressing that as well, by setting the right flags in the next frame and storing verbatim the only offsets that changed in addition to the previous or alike.
- 90s_dev 1y ago
  This comment is why I go to the comments first. Oh hey you're the guy who made kilo. Good job. [edit] lol he edited it... they always edit it
  - antirez 1y ago
    I always love when people recognize me for kilo or dump1090 or hping and not for Redis :D Side projects for the win. Thanks for your comment!
    - 90s_dev 1y ago
      I've literally never even used Redis, let alone know what it is or does. I dunno how I was able to make money in software since 2008 without figuring that out... or learning SQL, or C++. There's far more that I don't know than I do know. But anyway if you wrote Redis or something then congrats, I've definitely heard of it.
meatmanek 1y ago
I suspect this works better because the input videos (Youtube videos) have already been compressed and decompressed. With raw video input, I think the assumption "most pixels change little (or not at all) between consecutive frames, creating a sparse difference matrix ideal for this approach." would break down. For a very clean signal (low-noise sensor, brightly lit scene), maybe it'd work, but most real-world signals will have noise > 1 LSB, so I'd expect the lower bits to be changing at least half the time. Sending the video through a compression and decompression cycle first will tend to remove that noise, creating an artificially static video where that assumption holds up.
- jiggawatts 1y ago
  The lazy approach is to download an 8K video and downsample it to something like 720p. Or just buy a camera and run around capturing some raw 8K footage of everyday scenes.
- sionisrecur 1y ago
  So as it is, it would work great for animation.
- MBCook 1y ago
  Normal people never use raw, so that might not big a big issue. Phones and cameras store files in MP4 or AV1 or whatever anyway. Unless you know to turn it on and deal with the files sizes and processing people may not realize concept of raw/unprocessed exists anymore. I’d never thought about that before.
- nasso_dev 1y ago
  Just like you wouldn't use PNG for photography, I don't think you'd use a lossless video codec for real-world footage. Lossless video would make much more sense for digital content like screen recordings, where the assumption that few pixels change between consecutive frames makes much more sense.
  - einsteinx2 1y ago
    As far as video types go maybe it would work well for animation since that tends to compress well for the same reason a screen recording does.
less_less 1y ago
If you want to use Bloom filters for compression, you might want to consider binary fuse filters, ribbon filters or similar which avoid the 1/ln(2) leading factor in space usage.
ambicapter 1y ago
> The Innovation: Rational Bloom Filters Is this project about the video compression or about an innovation on Bloom filters?
- rh3939 1y ago
  without the rational bloom filter, no compression can take place. The new idea is rational bloom filters and this is just an example of how a rational bloom filter can be used to compress video. Its a novel approach to video compression. I posted an update on the top of the thread.
ggm 1y ago
Is it computationally less expensive? Is it amenable to stream processing e.g. in an FPGA? Is the compression ratio acceptable in a modern data stream? Is it actually a sub-class of compression already known, and therefore probably encumbered?
akoboldfrying 1y ago
I'm struggling to see how this could give decent compression performance. Compression works by exploiting patterns or tendencies in the input. One of the biggest and simplest patterns in video data is that pixel changes tend to be localised: E.g., a person waving their arm against a static background changes a clump of pixels in a small region only. By hashing positions, you immediately throw away this locality information -- under the proposed scheme, changing 400 pixels confined to a 20x20 rectangle requires ~exactly as much space as changing 400 pixels randomly scattered around the image, while a more efficient representation could record the top-left coords, width and height of the box, and save about 398 copies of pixel coordinates. And yes, this benefit remains even if we don't record the coords explicitly but rather discover them by querying a Bloom filter. And that's to say nothing of more advanced video compression techniques like motion detection (make the rectangle here look like the rectangle there from the previous frame), which is an absolute staple of every practical codec.
- joaohaas 1y ago
  I think you meant video decompression? Compression should theoretically be a lot more efficient, since the algorithm is a lot simpler and you can probably do a lot of SIMD to calculate the filters themselves.
  - akoboldfrying 1y ago
    In compression, "efficiency" usually means "compression level". If by "efficiency" you mean "speed", then yes, I think OP's approach can be much, much faster than usual video compression approaches -- but this is true of all compression algorithms that don't compress very well. The fastest such algorithm -- leaving the input unchanged -- is infinitely fast, but achieves no compression at all.
hxtk 1y ago
I'm confused by this line here: https://github.com/ross39/new_bloom_filter_repo/blob/4798d90b8d689a3a39cdd00b405917ef2d442f5c/video_delta_compress.py#L47 https://github.com/ross39/new_bloom_filter_repo/blob/4798d90... It seems like this would make the compression lossy and discard, e.g., transitions from #ffffff to #fffffa, and the line above it where the mean of pixel data is taken would discard, e.g., transitions from #ff0000 to #00ff00 regardless of the threshold used. Am I misunderstanding the role of that line of code? It doesn't seem like anything that is a 0 in the resulting mask would be encoded into the bloom filter.
oivey 1y ago
It’s difficult to trace through the repo, but it looks like the compression ratios are computed by seeing how many pixel diffs were able to dropped. That’s interesting, but the more interesting comparison would be to the average byte size of each frame in the compressed YouTube video. Without this, it’s hard to tell if the algorithm is an improvement relative to current methods. If the algorithm is lossy (small diffs are squeezed to zero) it probably should be compared to other lossy algorithms rather than lossless.
iqandjoke 1y ago
License type is needed. Something like GPLv3/ WTFPL Do What The Fuck You Want To Public License?
rh3939 1y ago
Hi HN, author here: I received some great feedback so I have decided to focus on raw video for now and more rigorous testing around noisy videos. I will continue to update the repo frequently. Its only very early days but the raw video testing has yielded some decent results(with some caveats). - Compression ratio of 4.8% (95.2% size reduction) - Compression speed: 8.29 frames per second - Decompression speed: 9.16 frames per second - Only 4% of frames needed as keyframes - Perceptually lossless output (PSNR: 31.10 dB) Comparison with standard codecs: - Rational Bloom Filter: 4.8% - JPEG2000 (Lossless): 3.7% - FFV1 (Lossless): 36.5% - H.265/HEVC: 9.2% (lossy) - H.264: 0.3% (lossy) ### Current Limitations and Future Work While the compression results are promising, the system is not yet truly lossless in its handling of color channels. The current implementation faces challenges with the YUV to BGR color space conversion process: 1. *Color Space Conversion Precision*: Small rounding errors occur during conversion between YUV and BGR color spaces, leading to minor differences in pixel values (average difference of ~4.7). 2. *Channel Processing*: The current implementation processes color channels in BGR format after conversion, which introduces additional precision loss. The plan moving forward is to: - Implement direct YUV processing without conversion to BGR - Develop a true bit-exact handling of color data - Refine the Bloom filter parameters specifically for chroma subsampling patterns - Create a dedicated verification system for each color channel independently I want to be able to prove its mathematically lossless but I am quite a ways from this. I plan to pursue this lossless compression idea and I have a few other ideas in different domains around using the rational bloom filter.

346 points by rh3939 1y ago

deleted 1y ago

[deleted]

I'm confused by the README. It makes references to YouTube video, but also "lossless video". Is this about recompressing existing H.264[1] videos (like downloaded from YouTube) losslessly, or is it about making new videos from a source losslessly? The former reminds me of JPEG XL's ability to re-compress the DCT on old JPEGs, but even as you get better compression, you still don't have a lossless image. [1] To be fair, H.264 can be lossless in the first place, but YouTube does not serve up such files.

perching_aix 1y ago
I think it's safe to assume that the author is reencoding those YouTube samples there, so vp9/avc/av1 -> uncompressed -> compressed with this, and that the compression ratio is with respect to the uncompressed stream. Otherwise I think the README would sound quite a bit more enthusiastic :)
runeblaze 1y ago
Yeah probably if they were writing a paper, encoding `.raw` files would have served them better (for being more convincing)
magicalhippo 1y ago
The introduction seems quite clear on it being an alternative to H.264 and friends: Traditional video codecs like H.264 and H.265 achieve impressive compression by discarding "imperceptible" visual information. But what if we could guarantee perfect reconstruction while still achieving meaningful compression? This project explores an unconventional approach: repurposing Bloom filters—typically used for membership testing—as a lossless video compression mechanism. Further down comes the explanation for why this scheme might possibly work: Rather than compressing whole video frames, this system applies Bloom filter compression to frame differences. This capitalizes on temporal coherence—most pixels change little (or not at all) between consecutive frames, creating a sparse difference matrix ideal for this approach. Of course, using delta-frame compression has been a common theme of many video codecs for ages now, and many like H.264 and H.265 use additional techniques like motion estimation[1] to reduce the information in the delta frame further before final entropy coding step[2][3]. As such, the best is probably to view this as an alternative to the entropy encoding in H.264 or similar. [1]: https://en.wikipedia.org/wiki/Motion_estimation#Video_coding https://en.wikipedia.org/wiki/Motion_estimation#Video_coding [2]: https://en.wikipedia.org/wiki/Context-adaptive_variable-length_coding https://en.wikipedia.org/wiki/Context-adaptive_variable-leng... [3]: https://en.wikipedia.org/wiki/High_Efficiency_Video_Coding#Entropy_coding https://en.wikipedia.org/wiki/High_Efficiency_Video_Coding#E...
rh3939 1y ago
Author here. Totally agree that H.264 can be lossless. Generally its lossy. My idea(which I am still working out) is to compress the difference of frames using a rational bloom filter. I previously posted here about using conditional bloom filter that rely on rational k. The idea was to use different values of k based on whether the url was more likely to be malicious than not. This results in a lower fp rate for the same filter size when compared to integer k. I then saw this paper[https://arxiv.org/html/2502.02193v2 https://arxiv.org/html/2502.02193v2] was posted recently which describes an almost identical approach(theirs is much nicer). I will do much more rigorous testing as my current setup is a bit sloppy but I hope it illustrates the idea.
- pipo234 1y ago
  I think you might be able to compress I and P frames somewhat descent, this way. But you only seem to address spatial domain, except for deltas(?) Or do you have some way to apply bloom filters to motion estimation as well?
- wging 1y ago
  So it sounds like the use of rational Bloom filters here is just to get a better compression ratio, but the basic technique could be used with classic Bloom filters—is that right? Do you know how much you gain in space savings from using rational Bloom filters? It’s not obvious to me how much of a gain it would be.

deleted 1y ago

[deleted]

clayhacks 1y ago

I see you put how to calculate the compression ratio, but do you have some examples of worst case, average, and best case compression ratios? Edit: ok I see the photos in the repo. Putting them in the README would be helpful

rh3939 1y ago
Author here. The repo is a complete mess but I do have some some code in there to generate graphs and whatnot if you're willing to dig through the code. I will make this much more concrete with lots of proper testing. Its very much still a messy work in progress.
- codetrotter 1y ago
  I applaud you for uploading even if it’s a bit disorganised still, and I do the same. It’s better to have something than nothing. Sometimes I see people talking about something but they don’t want to upload their code yet because they have to clean it up first. And then either they don’t get around to ever cleaning it up the way they wanted, or by they time they do it will have fallen off everyone’s radar and be forgotten. At least with a messy repo it’s possible to poke around, and not the least to star it and maybe check back later to see if they cleaned it up.

Dwedit 1y ago

It's also possible to run codecs like H.264 in a true lossless mode, it's just almost never done.

perching_aix 1y ago
Yup, even got it to work with hardware acceleration via NVENC. Playback was tough though, ffplay would work it, but nothing else.

bob1029 1y ago

> The key insight: when a binary string has a low density of 1s (specifically below p* ≈ 0.32453), we can encode just the positions of those 1s more efficiently than storing the raw string. Much of what JPEG/MPEG are doing is rearranging the problem such that it is possible to create long runs of zeroes. The way in which a DCT block is scanned relative to the location of its AC/DC components is potentially one of the most innovative aspects of many video & image compression techniques.

cogman10 1y ago
I don't believe this is correct. What the DCT does along with the color representation transformation is to turn fine details into higher frequencies and core details into low frequencies. From there, the quality of the image and thus compression ratio is as simple as dropping high frequency representations. And besides that, jpegs use a Huffman table to further reduce the size of the image. AFAIK, it doesn't do anything special to reduce runs. So lining up zeros really doesn't help much.
- IshKebab 1y ago
  This is true, but OP was also correct. The DCT components are quantised and encoded in an order such that you get a long string of 0s at the end (the high frequencies).
- Retr0id 1y ago
  Dropping (or rather, heavily quantizing) the high frequency components does create runs of zeroes with high probability. The order the components are stored (a diagonal zig-zag) pushes the likely-to-be-zero elements together. At higher quality settings you might not have actual runs of zeroes, but you'll at the least have runs of low-entropy values.
- brigade 1y ago
  Dropping the high frequencies does create zero runs, and even JPEG encodes zero runs as a run-length (RRRR in the spec) But DCT isn't very useful for lossless since any lossless frequency domain representation requires more range than the source, and you can't quantize to counter it.

meindnoch 1y ago

So, according to your graph [1] this new compression is always strictly worse than just using GZIP? [1] https://github.com/ross39/new_bloom_filter_repo/blob/main/compression_comparison.png https://github.com/ross39/new_bloom_filter_repo/blob/main/co...

Retr0id 1y ago
It's absent from this graph, but I'd imagine the bloom filter approach could be at least be faster than gzip. But I don't see perf metrics anywhere else...
- croemer 1y ago
  Why would it be faster? You have to do all that hashing and lookup of witness data etc. Also, if you want fast, good compression, use zstandard not gzip.
  - Retr0id 1y ago
    gzip (and zstandard) decompression is inherently serial, whereas many bloom filter lookups can be as parallel as you like.
    - alexjurkiewicz 1y ago
      You can de/compress multiple streams in parallel, at minimal cost of overall efficiency. For gzip, look at pigz. For video, look at how x264/x265 slice up the video frame.
    - croemer 1y ago
      Parallelism isn't speed. Zstandard decompression is insanely fast, no need for occupying multiple cores.
      - Retr0id 1y ago
        Bloom filter lookups are embarrassingly parallel to the point that you could occupy 0 CPU cores and do it in a GPU fragment shader. There are probably other reasons why this is a bad idea but I'm curious to try it.

mxfh 1y ago

I have trouble following the motivation here. Isn't the idea of lossless pretty meaningless for all consumer grade purposes, especially if the input example was already mangled through YouTube's transcoders? Besides possibly going from some MPEG1 or older to .h264/like lossless transcoding, I see no benefit in lossless methods here. From my personal experience, I tried archiving some of my old DVDs where no better sources are available for purchase for the forseeable future by transcoding to even .265 at absurdly high bitrates, but they all looked worse at higher bitrates than simply re-containerized MPEG2 for media-server streaming. All you do is transcode the output of an existing compressing wasting information with conserving artifacts from a prior reductive step. 4:4:4 LOG or something would be a target to benchmark here. Even "lossy" Apple ProRes start out at 275 Mbit/s for ProRes 4444 at HD25p already. https://en.wikipedia.org/wiki/Apple_ProRes#Data_rates https://en.wikipedia.org/wiki/Apple_ProRes#Data_rates

perching_aix 1y ago
I think you're in a misunderstanding indeed. This is not about lossless being practical now with this, or about reeconding YouTube videos with this providing any practical utility, or anything. It's just about using bloom filters for compression. The motivation was just the technical interest in bloom filters. They say as much in the readme: > This project explores an unconventional approach: repurposing Bloom filters—typically used for membership testing—as a lossless video compression mechanism. The video source is practically irrelevant as long as it's an actual video.
- mxfh 1y ago
  I just don't get why it's reinventing the whole wheel here – try using an off-the-shelf codec and tack on a sparse correction. For example, encode frames with a modern lossless/near-lossless codec (AV1 with QP=0) and then append a tiny bitmask+delta residual for perfect reconstruction. These codecs already exploit motion compensation, intra-prediction and DCT-like transforms to minimize frame-to-frame deltas. In practice you’d likely get better compression (and faster progress) by piggybacking on AV1 strengths – then use Bloom-filter trick just on the leftover sparse differences – rather than building a new codec from scratch. The residuals can be expected to be quite noisy and will likely not profit from any intra frame predictability anymore. JPEG XL’s lossless engine already improves on PNG by ~35%, that and other general purpose compression methods would then be the per frame benchmark here on the residuals to beat. In short: use the proven gear (motion-compensated blocks + modern transforms) to do the heavy lifitng, then let the bloom filter chase the hopefully comparably small residual. As a showcase of what bloom filters are this would be still worthwhile, but I don't see any practical benefit here yet. Not to forget, there is a reason visually lossless is the de facto the norm now, even in production grade environments, storage space is still not free while the average uncompressed display stream easily reaches way north of 5Gbps now easily, there is only so much lossless can resonably do here.

vintermann 1y ago

This is a cute concept, but if you have a sparse binary string, you can probably do better with traditional methods!

croemer 1y ago
Indeed, as this comparison with gzip shows: https://github.com/ross39/new_bloom_filter_repo/blob/main/compression_comparison.png https://github.com/ross39/new_bloom_filter_repo/blob/main/co...

antirez 1y ago

I don't believe the document does a great job in explaining what is otherwise a very simple idea (assuming I understood it well): 1. It creates a bitmap where each bit is a pixel in the image, if from frame 0 to frame 1 a given pixel changed, the corresponding bit is 1, otherwise it is 0. 2. All the 1s are added to the bloom filter, hashing their offsets. Now the bloom filter will be positive for all such indexes plus a percentage of false positive indexes. 3. We query the bloom filter to see all the indexes that are positive, and for all such pixels we store the raw pixel data of what changed. So we can reconstruct the next frame easily. You can think at this like as storing the delta between two frames as: x,y,r,g,b of all the pixels that changed, but compressing a lot the x,y part at the cost of storing a bit more r,g,b than needed. I have the feeling that since the pixels that changes from frame 0 to frame 1 are often similar (in their location) to what will change from frame 1 to frame 2, there is the possibility of further compressing that as well, by setting the right flags in the next frame and storing verbatim the only offsets that changed in addition to the previous or alike.

90s_dev 1y ago
This comment is why I go to the comments first. Oh hey you're the guy who made kilo. Good job. [edit] lol he edited it... they always edit it
- antirez 1y ago
  I always love when people recognize me for kilo or dump1090 or hping and not for Redis :D Side projects for the win. Thanks for your comment!
  - 90s_dev 1y ago
    I've literally never even used Redis, let alone know what it is or does. I dunno how I was able to make money in software since 2008 without figuring that out... or learning SQL, or C++. There's far more that I don't know than I do know. But anyway if you wrote Redis or something then congrats, I've definitely heard of it.

meatmanek 1y ago

I suspect this works better because the input videos (Youtube videos) have already been compressed and decompressed. With raw video input, I think the assumption "most pixels change little (or not at all) between consecutive frames, creating a sparse difference matrix ideal for this approach." would break down. For a very clean signal (low-noise sensor, brightly lit scene), maybe it'd work, but most real-world signals will have noise > 1 LSB, so I'd expect the lower bits to be changing at least half the time. Sending the video through a compression and decompression cycle first will tend to remove that noise, creating an artificially static video where that assumption holds up.

jiggawatts 1y ago
The lazy approach is to download an 8K video and downsample it to something like 720p. Or just buy a camera and run around capturing some raw 8K footage of everyday scenes.
sionisrecur 1y ago
So as it is, it would work great for animation.
MBCook 1y ago
Normal people never use raw, so that might not big a big issue. Phones and cameras store files in MP4 or AV1 or whatever anyway. Unless you know to turn it on and deal with the files sizes and processing people may not realize concept of raw/unprocessed exists anymore. I’d never thought about that before.
nasso_dev 1y ago
Just like you wouldn't use PNG for photography, I don't think you'd use a lossless video codec for real-world footage. Lossless video would make much more sense for digital content like screen recordings, where the assumption that few pixels change between consecutive frames makes much more sense.
- einsteinx2 1y ago
  As far as video types go maybe it would work well for animation since that tends to compress well for the same reason a screen recording does.

less_less 1y ago

If you want to use Bloom filters for compression, you might want to consider binary fuse filters, ribbon filters or similar which avoid the 1/ln(2) leading factor in space usage.

ambicapter 1y ago

> The Innovation: Rational Bloom Filters Is this project about the video compression or about an innovation on Bloom filters?

rh3939 1y ago
without the rational bloom filter, no compression can take place. The new idea is rational bloom filters and this is just an example of how a rational bloom filter can be used to compress video. Its a novel approach to video compression. I posted an update on the top of the thread.

ggm 1y ago

Is it computationally less expensive? Is it amenable to stream processing e.g. in an FPGA? Is the compression ratio acceptable in a modern data stream? Is it actually a sub-class of compression already known, and therefore probably encumbered?

akoboldfrying 1y ago

I'm struggling to see how this could give decent compression performance. Compression works by exploiting patterns or tendencies in the input. One of the biggest and simplest patterns in video data is that pixel changes tend to be localised: E.g., a person waving their arm against a static background changes a clump of pixels in a small region only. By hashing positions, you immediately throw away this locality information -- under the proposed scheme, changing 400 pixels confined to a 20x20 rectangle requires ~exactly as much space as changing 400 pixels randomly scattered around the image, while a more efficient representation could record the top-left coords, width and height of the box, and save about 398 copies of pixel coordinates. And yes, this benefit remains even if we don't record the coords explicitly but rather discover them by querying a Bloom filter. And that's to say nothing of more advanced video compression techniques like motion detection (make the rectangle here look like the rectangle there from the previous frame), which is an absolute staple of every practical codec.

joaohaas 1y ago
I think you meant video decompression? Compression should theoretically be a lot more efficient, since the algorithm is a lot simpler and you can probably do a lot of SIMD to calculate the filters themselves.
- akoboldfrying 1y ago
  In compression, "efficiency" usually means "compression level". If by "efficiency" you mean "speed", then yes, I think OP's approach can be much, much faster than usual video compression approaches -- but this is true of all compression algorithms that don't compress very well. The fastest such algorithm -- leaving the input unchanged -- is infinitely fast, but achieves no compression at all.

hxtk 1y ago

I'm confused by this line here: https://github.com/ross39/new_bloom_filter_repo/blob/4798d90b8d689a3a39cdd00b405917ef2d442f5c/video_delta_compress.py#L47 https://github.com/ross39/new_bloom_filter_repo/blob/4798d90... It seems like this would make the compression lossy and discard, e.g., transitions from #ffffff to #fffffa, and the line above it where the mean of pixel data is taken would discard, e.g., transitions from #ff0000 to #00ff00 regardless of the threshold used. Am I misunderstanding the role of that line of code? It doesn't seem like anything that is a 0 in the resulting mask would be encoded into the bloom filter.

oivey 1y ago

It’s difficult to trace through the repo, but it looks like the compression ratios are computed by seeing how many pixel diffs were able to dropped. That’s interesting, but the more interesting comparison would be to the average byte size of each frame in the compressed YouTube video. Without this, it’s hard to tell if the algorithm is an improvement relative to current methods. If the algorithm is lossy (small diffs are squeezed to zero) it probably should be compared to other lossy algorithms rather than lossless.

iqandjoke 1y ago

License type is needed. Something like GPLv3/ WTFPL Do What The Fuck You Want To Public License?

rh3939 1y ago

Hi HN, author here: I received some great feedback so I have decided to focus on raw video for now and more rigorous testing around noisy videos. I will continue to update the repo frequently. Its only very early days but the raw video testing has yielded some decent results(with some caveats). - Compression ratio of 4.8% (95.2% size reduction) - Compression speed: 8.29 frames per second - Decompression speed: 9.16 frames per second - Only 4% of frames needed as keyframes - Perceptually lossless output (PSNR: 31.10 dB) Comparison with standard codecs: - Rational Bloom Filter: 4.8% - JPEG2000 (Lossless): 3.7% - FFV1 (Lossless): 36.5% - H.265/HEVC: 9.2% (lossy) - H.264: 0.3% (lossy) ### Current Limitations and Future Work While the compression results are promising, the system is not yet truly lossless in its handling of color channels. The current implementation faces challenges with the YUV to BGR color space conversion process: 1. *Color Space Conversion Precision*: Small rounding errors occur during conversion between YUV and BGR color spaces, leading to minor differences in pixel values (average difference of ~4.7). 2. *Channel Processing*: The current implementation processes color channels in BGR format after conversion, which introduces additional precision loss. The plan moving forward is to: - Implement direct YUV processing without conversion to BGR - Develop a true bit-exact handling of color data - Refine the Bloom filter parameters specifically for chroma subsampling patterns - Create a dedicated verification system for each color channel independently I want to be able to prove its mathematically lossless but I am quite a ways from this. I plan to pursue this lossless compression idea and I have a few other ideas in different domains around using the rational bloom filter.