Christopher Smemoe ,
Computer Science 450
Table of Contents 1. Size of original compressed file
2. Predictive coding source code
3. Histograms of original and residual images
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.
Figure 1: Picture of the original file
Size of original file: 49415 bytes
Size of original compacted file: 43278 bytes (12.42% Compression)
Return to the Table of Contents
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].
Source code for predictive encoding of the image: encode.c
Source code for predictive decoding of the image: decode.c
Return to the Table of Contents
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?
See the two histograms below. The range of values is the images varies quite a bit. The histogram of the encoded (residual) image shows that it is better suited for entropy encoding since there is a smaller range of values that form a gaussian-type distribution.
Figure 2: Histogram of the original image
Figure 3: Histogram of encoded image
Return to the Table of Contents
Apply the compact command to the predictively-encoded image. Record the size of your newly compressed file.
Size of predictively-encoded, compressed file: 32242 bytes (34.75% Compression)
Return to the Table of Contents
Display the image to make sure your compression/decompression code works.
Figure 4: Image after encoding, compacting, uncompacting, and decoding (looks the same as original)
Return to the Table of Contents
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).
|
File |
Size of the original image (Bytes) |
Size of the compacted file (Bytes) |
Size of the predictively-encoded/compacted file (Bytes) |
Original compression ratio (Percent) |
Predictively-encoded compression ratio (Percent) |
|
65551 |
56319 |
19878 |
14.08% |
69.69% |
|
|
9229 |
1302 |
1253 |
85.89% |
86.42% |
|
|
9229 |
1838 |
1686 |
80.08% |
81.73% |
|
|
65551 |
46778 |
45511 |
28.64% |
30.57% |
|
|
98319 |
90399 |
53723 |
8.06% |
45.36% |
|
|
262159 |
158072 |
199603 |
39.70% |
23.86% |
Return to the Table of Contents
smemoe@byu.edu
Date last modified: 12/9/1999