[HN Gopher] Lossless video compression using Bloom filters
___________________________________________________________________
Lossless video compression using Bloom filters
Author : rh3939
Score : 137 points
Date : 2025-05-26 18:32 UTC (4 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| chungy wrote:
| 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 wrote:
| 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 wrote:
| Yeah probably if they were writing a paper, encoding `.raw`
| files would have served them better (for being more convincing)
| magicalhippo wrote:
| 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
|
| [2]: https://en.wikipedia.org/wiki/Context-adaptive_variable-
| leng...
|
| [3]:
| https://en.wikipedia.org/wiki/High_Efficiency_Video_Coding#E...
| rh3939 wrote:
| 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] 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 wrote:
| 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 wrote:
| 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.
| clayhacks wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| It's also possible to run codecs like H.264 in a true lossless
| mode, it's just almost never done.
| perching_aix wrote:
| Yup, even got it to work with hardware acceleration via NVENC.
| Playback was tough though, ffplay would work it, but nothing
| else.
| bob1029 wrote:
| > 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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/co...
| Retr0id wrote:
| 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 wrote:
| 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.
| mxfh wrote:
| 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
| perching_aix wrote:
| 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 wrote:
| 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.
| perching_aix wrote:
| Yes, they could do a lot of other things, but those other
| things would not be this. I think your expectations are a
| _bit_ misplaced. Maybe try giving all this a read again a
| day later?
| rowanG077 wrote:
| lossless isn't meaningless. Re-encoding introduces a lot of
| artifacts. Imagine your comment in 2001 when someone stored
| their movies in mjpeg or whatever. The moved to MP4, than the
| h264 than perhaps to HEVC. You realize how shit that movie
| would look after all those re-encode cycles?
| mxfh wrote:
| That's exactly what im talking about.
|
| Re-Containerizing MPEG-TS as-is to something like mkv, vs.
| Transcoding is exactly what I'm talking about here.
|
| There are currently not any meaningful ways known to me, to
| even make MPEG2 files significantly smaller in way more
| modern and advanced codecs without loosing perceived quality
| even at the same bitrate.
|
| Not even talking about interlacing issues here.
|
| So for anything MPEG2 and newer lossless reencoding seems
| quite a futile excersise to me from my personal experience.
|
| If there is a promising way I'm all here for it, but this
| sadly doesnt look like it.
| jitl wrote:
| Of course every round lossy of encoding further discards data.
| RemoveData(RemoveData(source)) is always going to look worse
| than just RemoveData(source). Newer encoders manage to remove
| less visual data per byte of storage used but there's no way
| re-encoding is going to ever look better.
| perching_aix wrote:
| If I understand it right, some lossy codecs can be
| implemented in an idempotent (and still standard-compliant)
| way, so there would be no generational loss (in select
| specific cases, e.g. matched settings). I'm also aware that
| e.g. JPEG-XL can reencode JPEGs without generational loss,
| while still improving compression efficiency a bit. But I
| never looked too deep into the math.
| vintermann wrote:
| This is a cute concept, but if you have a sparse binary string,
| you can probably do better with traditional methods!
| croemer wrote:
| Indeed, as this comparison with gzip shows:
| https://github.com/ross39/new_bloom_filter_repo/blob/main/co...
| antirez wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| antirez wrote:
| I have a theory, that I call "of the equivalence of
| modern software systems" that tells a lot about how
| unimportant Redis and other technologies are, that is:
| modern computing is so developed that pick any random
| language, kernel, and database, any of the top ones
| available, and I can create every project without too
| much troubles. PHP / Win32 / SQLite? Ok, I can make it
| work. Ruby / Linux / Redis? Well, fine as well.
| tehjoker wrote:
| redis is designed for scaling so if you don't have a
| large project you don't need it
| tie_ wrote:
| Ain't it cute 'splaining what redis is designed for to
| the person who designed it
| 90s_dev wrote:
| You win the "someone on HN made me laugh out loud" award.
| The last person to win it was like a month ago so good
| job.
| tehjoker wrote:
| I thought I was replying to a subcommenter... oopsie
| secondcoming wrote:
| Redis is absolutely not designed for scaling. Maybe
| valkey is but I've yet to use it
| 90s_dev wrote:
| I've noticed that too, LAMP stack vs MEAN stack etc.
|
| Part of it seems to be that software languages have
| "flavors" like natural spoken language does, so that one
| seems natural to one person and foreign to another, much
| like how DHH took TypeScript out of Rails, and I can't
| read Rails code or live without static types.
|
| Also college kids are always learning what the last
| generation already knew (like Lisp) and reinvent
| everything in it with the vigor of their youth and it
| gets popular, which I imagine is how Rails and Redis both
| started and caught on.
|
| But sometimes there are genuine innovations, and we can't
| build on them until someone comes up with them, much like
| how we couldn't invent machines until someone figured out
| that we could just use the lever to make gears to
| transport energy, which Archimedes didn't think of. And
| the more we learn collectively, the more these things
| spread.
|
| I wonder if this means it'll all stabilize into a
| JavaScript-like toolchain one day. Maybe Gary Bernhardt
| was right all along.
| braaaahp wrote:
| Yeh. Data driven model syncing machines will be what
| kills languages, software stacks.
|
| All the chip world talk of single function machines and
| how tech is now energy constrained industry, means
| pruning the state we store; most software is software to
| deliver software.
|
| Single function pipeline hardware platforms will act as
| little more than sync engines from models.
|
| I mean it's is 2025. Still write software like it's the
| 1970s. So high tech.
|
| Edit: https://arxiv.org/abs/2309.10668
|
| From LLMs to energy models that transform electromagnetic
| geometry. Saving what's needed to recreate cat pics and
| emails to mom. Pruning the tail as interest dips with
| generational churn.
| cryptonector wrote:
| A.k.a. all you need is PG and something to serve your app
| over HTTPS. :joy:
| messe wrote:
| I think PG might insist on using a lisp too.
| cozzyd wrote:
| dump1090 (but not Redis) user here! Hi! (We're about to
| publish a paper that depends on data taken with dump1090,
| funny enough...).
| antirez wrote:
| Awesome! Thanks! I had in mind of doing a V2 of dump1090
| soon (time permitting) I have a few ideas that may
| improve the performances very significantly.
| 90s_dev wrote:
| Also think about it this way:
|
| Redis will eventually become obsolete. It may take 10 or 50
| years, but it will happen.
|
| But kilo _taught_ many developers about C, editors,
| terminals, and how simple it is to do syntax highlighting.
| This epiphany inspired me and many others, and the things
| we make because of that will last _much_ longer than Redis.
| mattbis wrote:
| Redis does a lot of things most people don't know about
| and its all super optimised.. I am not so sure. I would
| not want that happen simple as I would be really bored
| using one way to do everything ( prb sql )
|
| Most people use it as a cache,.. you can build a lot of
| things with it that are far outside this narrow view... (
| say a bidding system or something like that )
|
| And for the other comment Scaling is possible via the
| commercial offering.. sofaik..
|
| I didn't get to persuade anyone to let me use it for
| that.. I really wanted to.
| hinkley wrote:
| A lot of video compression is about motion. How do you handle
| the same pixels sliding two pixels to the left due to a pan?
| 3cats-in-a-coat wrote:
| Thing is, if you store delta change from one frame to another,
| then pixels which aren't changed are just zeroes. Compressing
| zero sequences is the most trivial exercise for lossless
| compression and unlike the bloom filter, it has no false
| positives.
|
| I can see bloom filters as part of a complicated hybrid
| strategy compressor. The more tools on the belt of such a
| compressor, the better, but I don't think it'll improve things
| much on average.
| meatmanek wrote:
| 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 wrote:
| 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 wrote:
| So as it is, it would work great for animation.
| MBCook wrote:
| 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 wrote:
| 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.
| less_less wrote:
| 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.
___________________________________________________________________
(page generated 2025-05-26 23:00 UTC)