What is the relationship between image entropy and LZMA compression?

Question

I've got some pictures which i want to compress by using LZMA algorithm in Python. I'm using this implementation.

I've tried to measure the entropy of an image by using skimage.measure.shannon_entropy

entropy = skimage.measure.shannon_entropy(entropy_input)

For a particular picture I obtain an entropy of 1.8675842990312255 bit/symbol. These images are represented by tensors of 128x128x3. If I use 1.86 bit for each symbol I should obtain an image with a size of 11.16KB, but the compressed file has a size of 2.66KB!

How is it possibile? Shouldn't entropy be a lower bound to the maximum lossless compression?

Answer 1

The Shannon Entropy (of a random variable) is computed from the histogram. This computation does not take spatial relationship into account, only how often each value occurs (since it assumes values are independent).

Compression algorithms do not just encode each input value with the fewest possible bits, they encode sequences of values too. An image with random values (or a random permutation of the pixels in your image) would compress to about 11KB. But images (and meaningful human messages too) have very strong spatial correlation that allows for much smaller compression.

Answer 2

The name and documentation of shannon_entropy are simply misleading.

It's not the Shannon entropy what this function computes.

Remember the definition of entropy $H(X)$ of a random source $X$: It's the expectation of information. Now, the formula used there is simply

$$H(X) = \mathbb E\left\{I(x\in X)\right\}$$

They simply equate that with the negated sum over all logarithms over the empirical frequency of a symbol, times that frequency (which they use as a proxy for probability).

That's only correct if the symbols are independent! That's almost never the case in imagery.

Example:

You have a source that gives you values out of {1,…,16} equiprobably, one after each other, totally unrelated. Of course, you'll find that the Shannon entropy of this source is $\log_2(16)=4\,\text{b}$. Fine!

Now, take a different source. Same alphabet, {1,…,16}, but every value is repeated four times. Clearly, every fourth symbol carries 4 bit of information – but all in between carry no information on their own, because you know their value if you know the value of the previous symbol.

So, within a streak of 4 of such symbols, there's one symbol that has 4 bit information, and 3 symbols that actually have 0 bit. The Shannon entropy is hence $H(X)= \frac14 \cdot 4\,\text{b} + \frac 34 \cdot 0\,\text{b}=1\,\text{b}$. Not surprising, I'd say - you could transport the same info with an image one fourth of the pixels! We call a source where we consider multiple symbols combined into one a "product source" (in this case, a sensible product source to construct from the original, correlated source is the product source made from 4 consecutive symbols).

The function shannon_entropy will tell you the Shannon entropy is 4 bit in both cases. It'd be wrong, plain as that - the thing it calculates only is the Shannon entropy of a source that gives independent samples of given statistics. It can be used as an upper bound, but typically becomes a very loose bound for images that aren't white noise.

Now, LZMA doesn't try to encode the image as independent pixels – it's designed to understand the data as output of a product source (i.e. one where you encode words that are made out of multiple symbols), and hence "sees" the correlations in your image, and compresses them.