Entropy, Compression, and Huffman Variable Length Encoding

stough 202-

1. Computing Entropy

2. Huffman Trees

3. Variable-length encoding and decoding

   • 🔨 Your Turn: Decoding

   • 🔨 Your Turn: Reconstructing

   • 🔨 Your Turn: In Color

Images and videos can be quite large. At 60 frames per second, a 4K Ultra HD movie of 2 hours could require

or about 163 blu-ray discs to store without compression. So clearly compression is a thing.

Compression takes advantage of different kinds of redundancy in the signal. Images in particular have a lot of redundancy. Spatial and Temporal redundancy are characterized by the fact that most pixels are closely related their neighbors. This is due to the fact that any images of human interest are likely to have objects comprised of regions of similar color. Temporal redundancy is the video case, where a pixel over time changes little usually.

Coding redundancy is the one we’re dealing with here. Most images we consider are 3-channel images with 8 bits per pixel per channel. We need 8 bits to represent a value in $[0, 255]$. Variable-length encoding can take advantage of the differential frequency of certain pixel values over others, encoding more common pixels with fewer bits, and paying for that by using more bits to represent less common pixels.

• Compressibility: The degree to which the information in an image or video can be represented using fewer bits. In the example above of the highly compressible 4K Ultra HD, we might say the compression ratio is ~160 (display size over storage size).

• Entropy: a measure of the information content in a signal.

  • signal: here, think of this as seeing each individual pixel in the image in order.

  • Think of entropy as the surprise, or “unpredictability” of the signal. Each new pixel value $k$ in the signal gives you some information,

  $$I(k) = -\log_2(p(k)),$$

  where $p(k)$ is the probability of observing $k$ in the signal. For example, if the probability of observing $k$ is 1, as in 100% of all the pixels have the value $k$, then there is no information/surpise, or 0 bits, associated with observing it. If $p(k) = \frac{1}{2}$, then that’s 1 bit of information. (We won’t consider the symbols $\kappa$ that never show up, since observing such a symbol would be infinitely surprising :-).

  • For our images in the range $[0, 255]$, we can measure the entropy or information content of the image as

  $$\tilde{H} = -\sum_{k=0}^{255} p(k)\log_{2}p(k)$$

  This is just an average of how many bits of information each newly observed pixel gives us, weighted by how likely that pixel value is. $p(k)$ is just the normalized histogram values.

In this notebook we’ll explore Huffman variable-length encoding and its effectiveness in some images.

Imports¶

Notice I’ve added our own custom Huffman utilities huff_utils and scipy.stats.entropy. Study build_huff_tree in particular.

Computing Entropy¶

We store this image with 8 bits per pixel, but on average each pixel carries only about 3.75 bits of information. The histogram shows why: a handful of gray levels account for almost all the pixels. So, at least in principle, we should be able to store this image in less than half the space. Entropy is the lower bound on the average bits per pixel that any code can achieve, as long as it treats each pixel independently. Let’s see how close Huffman coding gets.

Huffman Trees¶

A Huffman tree is a binary tree structure whose leaf nodes represent the symbols in a signal (the pixel values in an image). The path from the root of the tree to a leaf node represents the bit encoding of the associated symbol (0 for left child, 1 for right child, for example). Let’s see an example

In the example above we start with pixel values in [‘A’, ‘B’, ‘C’, ‘D’]. The Huffman Tree construction algorithm basically sorts these symbols (image intensities for example) from least to most frequent as a collection of leaf nodes (a minheap is useful for this).

• We then take the two least frequent nodes and combine them into one Huffman tree with the two symbols as leaf nodes and the frequency associated with this tree as the sum of the two individual frequencies.

• Then insert this tree back into the collection. This is where a heap comes in useful, as a self-maintaining structure always providing access to the least frequent node.

• Repeat. Each iteration we end up with one tree fewer in the collection/heap, until there is only one tree left.

The structure of that final tree represents an optimal encoding given the relative frequencies provided.

Variable-length encoding and decoding¶

See the code in huff_utils. One thing you’ll notice about the encoder is that a lot of pixel values require many more than even 8 bits!!! How could that possibly save space?

Huffman coding uses about 3.77 bits per pixel, within a few hundredths of a bit of the entropy, for a compression ratio of better than 2. This is no accident. Huffman codes are optimal among all codes that assign each symbol its own whole number of bits, and they always come within 1 bit per symbol of the entropy. Notice also that the rare pixel values that got codes much longer than 8 bits barely matter: they’re so rare that they hardly contribute to the total.

The next three sections are yours. Together they complete the round trip: an image goes in, bits come out, and the same image comes back.

🔨 Your Turn: Decoding¶

So in the above we see how we can take an image--an array of pixel values--and encode it using the Huffman variable-length encoding. In short:

I = load_huffable_image('../dip_pics/happy128.png')
encoder, decoder = build_huff_pair(I)
enI = ''.join(encoder[pix] for pix in I.ravel())

After the above section executes, enI is the encoded image (a sequence of bits), which can be stored or transmitted more efficiently. However, when display of the image is needed again, we’re going to need to decode the bit sequence back into an array of pixel values. We can use the decoder dictionary to do this.

Task: Write a decode_image function that accepts such an encoded string (like enI) and the decoder dictionary, and outputs a list of intensities equal to the uncompressed image I.ravel(). Show a validation test of this function: is the reconstructed array of intensities equal to the original? See array_equal.

Guidance:

• Look at decoder above: its keys are bit strings and its values are pixel intensities.

• The encoded string has no separators between codewords, so the hard part is knowing where one codeword ends and the next begins. Huffman codes are prefix-free: no codeword is the beginning of any other codeword. Think about why that property makes the decoding unambiguous, and use it to decide when you’ve read a complete codeword.

• Test on a tiny example you can check by hand first, such as encoding just Ih.ravel()[:5], before decoding the whole image.

• Decoding the whole $128 \times 128$ image in plain Python should take at most a few seconds. If yours takes much longer, look for work you repeat for every bit.

🔨 Your Turn: Reconstructing¶

Task: Now take the output of decode_image to reconstruct the original image I. Show your reconstruction code and a figure supporting its success.

Guidance:

• Even though our encoded stream does not include the image shape, you may cheat there and use the original image shape “out of band” so to speak. In practice we could send along the image shape with the encoded stream without too much trouble. See numpy.reshape.

• Your decoded list holds Python integers; give the reconstructed array the same datatype as the original (arr_info on both).

• A figure from vis_pair shows they look the same; np.array_equal shows they are the same. Show both, since lossless compression promises the second.

🔨 Your Turn: In Color¶

Task: Do this with a color image (that is not happyFace). Perform Huffman compression separately on each of the three channels and show that you can encode, and then decode and reconstruct such a color image. Report the compression ratio for each channel and for the whole image.

Guidance:

• Don’t load the image with load_huffable_image: it converts color images to grayscale (read it in huff_utils). Use plt.imread, and note that .png files load as floats in $[0,1]$ while .jpg files load as uint8 in $[0,255]$. Huffman coding needs the integer values.

• Each channel gets its own encoder/decoder pair, built from that channel alone. Your decode_image from above should work unchanged on each channel.

• Pick a modest image size, or crop one, so encoding and decoding stay quick: every pixel becomes several characters of a Python string.

• Which channel compresses best? Compare each channel’s bits per pixel with its entropy, as we did for the gray image.