4
$\begingroup$

I'm working on this lab where we need to apply a lossless predictive coding to an image before compressing it (with Huffman, or some other lossless compression algorithm).

From the example seen below, it's pretty clear that by pre-processing the image with predictive coding, we've modified its histogram and concentrated all of its grey levels around 0. But why exactly does this aid compression?

Is there maybe a formula to determine the compression rate of Huffman, knowing the standard deviation and entropy of the original image? Otherwise, why would the compression ratio be any different; it's not like the range of values has changed between the original image and pre-processed image.

Thank you in advance,

Liam.

$\endgroup$
7
$\begingroup$

Huffman coding, as usually applied, only considers the distribution of singletons. If $X$ is the distribution of a random singleton, then Huffman coding uses between $H(X)$ and $H(X)+1$ bits per singleton, where $H(\cdot)$ is the (log 2) entropy function.

In contrast, predictive coding can take into account correlations across data points. As a simple example, consider the following sequence: $$ 0,1,2,\ldots,255,0,1,2,\ldots,255,\ldots $$ Huffman coding would use 8 bits per unit of data, whereas with predictive coding we could get potentially to $O(\log n)$ bits for the entire sequence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.