Ten Dropbox Engineers Build BSD-licensed, Lossless 'Pied Piper' Compression Algorithm

An anonymous reader writes: In Dropbox's "Hack Week" this year, a team of ten engineers built the fantasy Pied Piper algorithm from HBO's Silicon Valley, achieving 13% lossless compression on Mobile-recorded H.264 videos and 22% on arbitrary JPEG files. Their algorithm can return the compressed files to their bit-exact values. According to FastCompany, "Its ability to compress file sizes could actually have tangible, real-world benefits for Dropbox, whose core business is storing files in the cloud."The code is available on GitHub under a BSD license for people interested in advancing the compression or archiving their movie files.

Comments

From TFA: bit-exact or not?

[QuietLagoon]

...Horn and his team have managed to achieve a 22% reduction in file size for JPEG images without any notable loss in image quality....

Without any notable loss in image quality.

.
Hmmm... that does not sound like "bit-exact" to me.

Re:From TFA: bit-exact or not?

[JoeMerchant]

If you are viewing images on an LCD monitor, the first thing you can do is strip them down from 24bit color to 18bit color, because your sub-$1000 monitors don't display more than 6 bits per color channel.

Re:From TFA: bit-exact or not?

[danielreiterhorn]

Very insightful comments... let me go into detail
I would say we have several advantages over H.264
a) Pied Piper has more memory to work with than an embedded device (bigger model)
b) Pied Piper does not need to seek within a 4 Megabyte block (though it must be able to stream through that block on decode) whereas H.264 requires second-by-second seekability (more samples in model).
c) Pied Piper does not need to reset the decoder state on every few macroblocks (known as a slice), whereas H.264 requires this for hardware encoders (again, more samples per model).
d) As opposed to a committee that designed H.264, Pied Piper had a team of 10 creative Dropboxers and guests, spending a whole week identifying correlations between the decoder state and the future stream. That is a big source of creativity! (design by commit, not committee)
Our algorithm is, however streaming---and it's happiest to work with 4 MB videos or bigger
Our decode window is a single previous frame--so we can pull in past information about the same macroblock-- but we only work in frequency space right now (there are some pixel space branches just to play with, but none has yielded any fruit so far) so the memory requirements are quite small.
We are doing this streaming with just the previous frame as our state--- and it may matter--but we have a lot of work to do to get very big wins on CABAC... but given that we're not limited by the very small window and encoding parallelization requirements that CABAC is tied to, Pied Piper could well be useful soon!

Re:From TFA: bit-exact or not?

[danielreiterhorn]

No one has tried to undo and redo compression of video files before. There are still doom9 forum posts asking for this feature from 12 years ago. I would say that saving lossless percentage points off of real world files is novel and important. And, since it's open source, if someone else gets more %age improvement than what we have, it could become as transformative as you describe.
But the point is that we have something that's currently useful. It's out there and ready to be improved. It's lossless. And it has never before been tried.
Also we did the entire algorithm in a week and aren't out of ideas!
Besides we never claimed it was a revolution--leave that sort of spin to the marketeers...
we're engineers trying to make things more efficient, a few percentage points at a time :-)

Re:From TFA: bit-exact or not?

[Cassini2]

The grandparent poster is talking about compressing videos. If something is known about the data being encoded, then it is trivial to show that you can exceed the performance of arithmetic coding, because arithmetic coding makes no assumptions about the underlying message.

For instance, suppose I was encoding short sequences of positions that are random integer multiples of pi. Expressed as decimal or binary numbers, the message will seem highly random, because of the multiplication by an irrational number (pi). However, if I can back out the randomness introduced by pi, then the compression of the resulting algorithm can be huge.

The same applies to video. If it is possible to bring more knowledge of the problem domain to the application, then it is possible to do better on encoding. Especially with real-life video, there are endless cheats to optimize compression. Also, Dropbox may not be limited by real-time encoding. Drop-box might not even need intermediate frames to deal with fast-forward and out-of-order viewing. Dropbox may be solely interested in creating an exact image of the original file. Knowing the application affects compression dramatically.

Lastly, application specific cheats can save real-world companies and individuals money and time. Practical improvements count as advancements too.

Re:From TFA: bit-exact or not?

[pla]

Interpolation is WORSE than nothing. you're discarding signal then adding noise in the hopes that it matches up with what should've been there kinda okay.

1, 2, 3, X, 5, 6. Guess the value of X... Congratulations, you just interpolated the right answer.

In the case of what the GP described, though, it works out even better than that, because the panel actually "knows" the right answer, so it hasn't "thrown away" information; it just lacks the luminance resolution to display it. It can, however, interpolate in the temporal domain way, way faster than the human eye can tell, to create a color we perceive as the correct value.

/ Go ahead, twitch gamers, tell us all about your ability to resolve sub-millisecond 1.5% color changes. XD

Re:Hard to believe

[Kjella]

H.264 and JPEG are supposed to output random-looking bytes, by definitions. If you can compress those, something is very wrong.

Well, it seems to be applied per codec not a general compression algorithm like zip. And they probably say mobile-encoded for a reason, simple encoders have to work on low power and in real time, random JPGs from the Internet is probably the same. From what I can gather the algorithm basically take a global scan of the whole media and applies an optimized variable-length transformation making commonly used values shorter at the expense of making less commonly used values longer. Nothing you couldn't do with a proper two-pass encoding in the codec itself, the neat trick is doing it to someone else's already compressed media afterwards in a bit-reversible way. Very nice when you're a third party host, assuming the increase in CPU time is worth it but not so useful for everyone else.

Re: No description

[danielreiterhorn]

It depends if the goal is to a) market a hip algorithm or b) store movies more efficiently.

Open source makes it easy for anyone to contribute to the algorithm.
The more people contribute, the better the code will be at compressing movies.

The better it is at compressing movies, the fewer resources it will take to store them.
This isn't a zero-sum game we're talking about: it's about making the world a more efficient place, one bit at a time.

But the bottom line is that, it's a lot easier for many organizations to contribute to a code base if there are no strings attached.

Interest from an article like this can get people playing around with compression.
Maybe another 10% gain is right around the corner.