Huffman Coding

Summary

Huffman coding is a method that can be used to compress data. The goal of Huffman encoding is to represent your most common pieces of data with the least number of bits. This can be applied to images, since each pixel has 255 possible outcomes. If we calculate the probability distribution for the possible pixel values, we can create a lookup tree or dictionary that can encode and decode the images. This type of compression is lossless, but requires a lot of computation.

Approach and Results

So far, we have been working with the code to compress and decompress images. We have been working with some different types of images to see where this method is useful, and where it is less useful. Below are some sample of images we have tried, as well as their probability distributions.

 

There are several things we can learn from the above pictures. We have learned that the probability distribution can tell a lot about how well the image can be compressed. High values in the probability distribution make the Huffman code more efficient at compression. This is apparent in the night sky photo. There is a peak at around .32 for black pixels. Huffman encoding could compress this by 1.3218X. On the other hand, having all low values in the probability distribution is not good for this type of compression. This is the case in the gradient picture. The gradient yields a perfectly uniform distribution, which cannot be compressed at all by Huffman Coding.

Huffman Coding Combined with Other Algorithms

Typically, Huffman coding is used as a back end with other types of compression. Since it is lossless, it can be applied in series with other image compression without giving up any extra information. We tried this with our other methods of image compression to see which one Huffman coding would complement best.

 

As you can see from the above images, Huffman coding complements Haar wavelets the best. The Huffman algorithm was applied on some images that were compressed by Haar Wavelets, Singular Value Decomposition, and Discrete Cosine Transform. This worked very well on the Haar compressed image for the same reasons we stated above. The majority of the image is black, which is easily compressible for Huffman coding.