Adaptive Huffman Coding – Final Report
Adam Lanser
Consider a black and white image. This image is made up of many pixels that are all different shades of gray which have a number value corresponding to the brightness or darkness of the shade. Black is 0, white is 255, and all the numbers in between are shades of gray. So, each pixel is coded as some integer from 0 to 255. In order to encode these integers, we must use bits. A bit have a value of either 0 or 1, and the maximum number of bits needed to code any number between 0 and 255 is 8. Bits will appear in the following form using binary code:
_ _ _ _ _ _ _ _
Each dash represents one bit, and each bit will contain a value of 0 or 1. In this 8-bit series, each dash has a specific value when a 1 appears in that slot. When a 0 appears, it will have a value of 0. Let’s look at the following example for clarification…
The following 8-bit representation will code as a 0:
0 0 0 0 0 0 0 0
The next 8-bit representation will code as 255:
1 1 1 1 1 1 1 1
Why? Well, each bit placeholder has a certain value when a “1” appears in its place. So, when there is a one in every slot, this representation actually codes as…
128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255.
So, the first slot decodes as a value of 128 when a “1” appears in its place. The second decodes as 64, and so on down the line until the last slot decodes as a 1. So, the 8-bit representation of 153 would look like this…
153 = 1 0 0 1 1 0 0 1
128 + 0 + 0 + 16 + 8 + 0 + 0 + 1 = 153
So, now we are able to encode these images using 8-bit representations of each pixel to code for a specific shade of gray. Now, once we have coded this image up using this method, image compression is utilized in order to shrink the size of the image down so that fewer bits per pixel are used in the coding of the image. The goal of image compression is the use the fewest possible bits per pixel to code the image while still having a compressed image comparable to the original image.
Going back to our original image, with these number values 0 to 255 representing a different shade of gray, we construct a huge matrix. Each numerical entry in the matrix represents a pixel of a certain color in the original image. In order to compress this image, transforms exist that can arrange the elements of the matrix in a certain way to cut down on the number of bits per pixel. Some methods may simply round small values in the matrix down to 0 in order to cut down on the number of bits per pixel, but this can substantially change the original image which conflicts with one of the goals of image compression. One such transform that can be very effective is the discrete cosine transform (DCT).
The discrete cosine transform is a complex transformation that is too involved and complex to get into in this final report, but what the DCT leaves us with is what is important. The transform uses an algorithm in order to efficiently display the elements for use in Huffman coding. Huffman coding will take the results after the discrete cosine transform, and code the new matrix formed from those results in order to further compress the image. So, in order to encode an image in this way, you must apply the DCT to the original image. Then, using the resulting matrix, utilize Huffman coding to code these results. The Huffman coding algorithm can be reversed in order to decode the compressed result to arrive back at the original image. The focus of my summer research was to take the results of the DCT and create a Huffman coding algorithm in order to compress the original image.
The goal of my research this summer was to research the idea of Huffman coding to understand the algorithm, and then write Mathematica and Matlab code to create a module that will take the resulting matrix after applying the DCT and give you the compressed Huffman encoded matrix. Along with that, another goal was to write code in each Mathematica and Matlab to decode this Huffman encoded matrix and arrive back at our original image. In order to reach these goals, I needed to do extensive research on a topic that I knew very little about.
As it turns out, this Final Report has turned into more of a “progress report” because my preliminary research on Huffman coding has not yielded enough results to begin writing code in Mathematica or Matlab. I have the same goals for the end of the year, and I am hoping I am able to reach them with more research and hopefully further understanding.

download full report
http://cam.mathlab.stthomas.edu/pdf/fina...REPORT.pdf