Homework #10: Human Vision, Color, and Compression

Due Date: Thursday, December 7 (Note: this is the last day of classes and is a hard deadline.)
 
 

From the textbook: Chapter 17: 1,3
 
 

Programming - Compression:
 
 

For this lab you will implement a simple compression algorithm. The Unix compact (compiled for linux x86 - like the open lab machines) program uses Huffman coding to compress a file. As we have discussed (or will discuss) in class, the effectiveness of entropy encoders can be improved by using a predictive encoder to decrease the entropy.

NOTE: I am unsure of the capability to compile this program on windows. But, the code is available. Once compiled, you just type compact to run the program on that file. A .jz extension is added. Additionally, you type compact -d to decompress the file.
 
 

1. Select one of the images that we've been using in class, copy it to your directory, and run the Unix compact command on it. Record the size of the compressed file.
 
 2. Write a program that uses predictive coding to reduce the entropy of an image.

The program should have a single image input and a single image output.

Use a variation of the lossless JPEG standard where each pixel is predicted as the weighted average of the adjacent 4 pixels already encountered in raster order (three above and one to the left). That is, try to predict the value of a pixel a based on preceding pixels, x, to the left as well as above a :

x x x
x a


 

Then calculate and encode the residual (difference between predicted and actual value).

Note: even though the residual may have both positive and negative values, [-256,256], it can still be encoded in one byte since the error for a prediction of P is in the range [-P,256-P].
 
 3. Display and compare histograms of the original and the residual image used in the predictive encoding. Specifically, how does the dynamic range compare? Which is a better candidate for entropy encoding - the orginal or the residual? Why?
 
 

4. Apply the compact command to the predictively-encoded image. Record the size of your newly compressed file.
 
 

5. Now use uncompact and your own predictive decoder to decompress the file.
 
 

6. Display the image to make sure your compression/decompression code works.

(Hint: you may want to do this step earlier in order to test your predictive encoder.)
 

7. Once you've verified that your code works, test it on at least five images. Record for each the size of the original image, the size of the compacted file, the size of your predictively-encoded/compacted file along with corresponding compression ratios (orginal/encoded).
 
 

8. For additional credit, experiment with different or even multiple predictive contexts. The better the compression rate, the more credit you'll earn.