Hacker News Reader

Comment by personjerry | Hacker News Reader

Could someone explain to me how compression algorithms work? Shouldn't they not work very consistently, by pigeonhole principle?

View on HN

They work because while most possible data is unstructured, most real-world data is highly structured. On average over all possible inputs, any compression scheme must have 1x compression.

Consider images of slides for a presentation that are text on a flat background. If you know the value of the pixel just to the left of the current pixel, then if you guess that the current pixel will be the same, you will be right most of the time. This is obviously not true for random noise. Consider a really simple compression scheme where a pixel is stored as a single bit of a 1 if it is the same color as the previous pixel, and the color is stored as usual, but with an additional 0 bit prepended to the color. When you guess wrong, you pay a tax of 1 bit, but when you guess right you save N-1 bits where N is the number of bits per pixel.

For random noise, this will grow the input quite a bit, but for simple flat-shaded graphics it will shrink the input quite a bit.

On average, any lossless compression scheme must have >= 1x compression. Lossy compression schemes can have less (since they're discarding information), and lossless compression schemes certainly can average out to > 1x (this is trivially observable by taking any 1x-average scheme and adding a fixed-length header to the output).

It's very easy to make a JPEG file that will not compress at all. Luckily it might look like snow from a television set rather than a typical image produced by a camera.

We live in a world where it is common for blue sky to occupy a portion of the frame and green grass to occupy another portion of the frame. Since images captured of our world exhibit repetition and patterns, there are opportunities for lossless compression that focuses on serializing deviations from the patterns.

Impressive work, Daniel! Do I understand correctly that any image prediction for which the deltas are smaller in absolute value than the full JPEG/DCT coefficients would offer continued compression benefits? As in, if you could "name that tune" to predict the rest of the entire image from the first few pixels, the rest of the image would be stored for close to free (and if not, it essentially falls back to regular JPEG encoding).

If that's the case, then not only could we rely on the results of everything we've decompressed so far to use for prediction (which is like one-sided image in-painting), but we also could store a few bits of semantic information (e.g. from an image-net-based CNN, from face detection) about the content of the original image before re-compression, and use that semantic information for prediction as well via some generative model. All of this would obviously be trading computation for storage/bandwidth, but it this seems like an exciting direction to me. Again, nice work.

Hi GrantS: That's pretty close to how it works. We always use the new prediction, even where it's worse than JPEG though (very rarely), to stay consistent.

As for having the mega-model that predicts all images better: well it turns out with the lepton model out you only lose a few tenths of a percent by training the model from scratch on each images individually. We have a test case for training a global model in the archive (it's https://github.com/dropbox/lepton/blob/master/src/lepton/tes... ) That trains the "perfect" lepton model on the current image then uses that same model to compress the image (It's not meant to be a fair test, but it gives us a best-case scenario for potential gains from a model that has been trained from a lot of images) and in this case it doesn't gain much, even in a controlled situation like the test suite.

However the idea you mention here may still be a good idea for a hypothetical model--but we haven't identified that model yet.

I think you are explaining how both lossy and lossless compression work without explaining how this does it differently.

I can't read the article due to technical constraints, but understand that e.g. JPEG has a lossy quantisation pass followed by a lossless encoding/compression pass of the result of the first stage. If they're reproducing bit-identical result to the input JPEG, it must be a (very good) optimisation of the latter stage. [How'd I do?]

JPEG has a very poor lossless encoding stage; this is well known. Several archiving tools (most notably winRAR) already do some lossless reencoding of JPEG.

> Luckily it might look like snow from a television set rather than a typical image produced by a camera.

That would actually compress rather well. A hard to compress random image would not look like TV snow (white dots, with space between them), but rather randomly colored dots that are continuous in the image.

Random link: "I am trying to design a cloth that, from the point of view of a camera, is very difficult to compress with JPG, resulting in big-size files (or leading to low image quality if file size is fixed)."

https://dsp.stackexchange.com/questions/2010/what-is-the-lea...

No compression algorithm works on completely random data. Fortunately (for compressors) there is in practice almost no completely random data sets people care about in the world. Almost all data is corrolated in some way. In pictures you can do a good job of predicting the colours of neighbouring pixels (they will, most of the time, be a similar colour).

In this case they are making use of the fact that JPEGs store a certain mathematical formulation of a picture. It turns out JPEG doesn't store that mathematical formulation very well, so you can squash it loselessly into a better formulation, then later turn it back into the original JPEG.

Reply on news.ycombinator.com