Problem Set: Compression
Before starting on the real exploration, let’s do some ”warmup” exercises to become familiar with these tools. Please go through the first 3 pages of the Compression Lab. If you are not quite sure what you should compute for the Averaging and Differencing, try first the fill-in example at the bottom of the lab-page on 2-dimensional Averaging and Differencing, or go over the lecture notes.
Problem 0: Compressing a 4x4 image
224 216 212 104 222 214 108 100 220 214 112 96 108 104 92 94
Could you describe what this image would look like? (Draw a picture.)
Compute the entries you obtain after averaging and differencing, first horizontally, then vertically:
Now set to zero all the entries that are smaller than 8 in absolute value, and round off every number that is not an integer:
You can now use these rounded numbers for the “reconstruction procedure”; follow the procedure we saw in class. Please write here what you obtain:
Subtract each of these entries from the corresponding entry in the original array. What do you get?
After this warm-up, let’s play with some real images. Go to the last webpage within the Compression Lab, also called Compression. You can use the default images provided there (parrot, house or boat), or load any image you have on your computer.
Choose small images – images larger than 100K will take much longer to load. Color images will be converted to gray-scale. The display will also squeeze any image into a postcard-like aspect ratio, so if you don’t want to see your uploaded image distorted too much, you may want to choose a landscape- oriented picture in the first place. Please print out a copy of your images if you use other than the default images, and attach them to this problem set when you hand it in – it will also help if you “name” them, so you can refer to them below.
(Note that you may need to push the Browse or Load a Default Image 2 or 3 times)
You will see the image you uploaded in two copies, left and right. Both sides have identical functions, but having two of them side by side allows you to compare the results of two different manipulations. To familiarize yourself with the settings, just stick to one side, at first.
You should explore what the different “buttons” will do for you:
• Filter–pickswhattypeofdifferencingandaveragingschemeyouwilluse.Haaristheschemeyou practiced above, and which we also saw in class: just simple sums (averages) and differences of two neighboring values. 4-tap is already a bit smarter; it uses not just 2 numbers to compute the sums and differences, but “coorects” somewhat by using some influence of their immediate neighbors as well. Finally, jpeg-2000 uses the averaging and differencing scheme of the JPEG2000 standard, which is the same as in digital movies or ESPN broadcasts.
• Levels – chooses how many times you repeat to do the Averaging and Differencing. In the Surfing with Wavelets slides we saw in class (which you can find under Lecture Notes), we did 5 levels in all.
• # Rounded bits – gives you a way of rounding off numbers. The higher you pick this number, the more severe the rounding off – but also the more space you will save. The “0” setting means you don’t touch the numbers.
• Options – here you choose whether you want to visualize the coefficients (i.e. the result of the “averaging” and “ differencing” operations: these are called the wavelet coefficients) – including the effect of the rounding-off you set in the previous button, the reconstruction from the rounded- off coefficients, or the amount of memory-space saved.
If at any point, you want to compare a reconstructed image (after compression, that is, after rounding off bits) with the original, then you leave on one side the settings to 0 Levels, 0 Rounded bits, and choose the “reconstructed” display – that will just display the untouched image, with which you can compare what you have on the other side.
Try out the different settings, making sure you understand what they do. Then you can start on the problems.
Problem 1. Wavelet Coefficients.
In the ”coefficients” display (with the Filter set to Haar and Levels set to 1), the three different ”difference” rectangles correspond to a special kind of information. (It is perhaps easiest to see the differences in the “house” image.) By comparing with the original image, you can see that the difference coefficients that are non zero come from particular regions in the image. What regions? Can you explain why the difference coefficients would be especially large there? What is the difference among the three types of difference coefficients (corresponding to the three different rectangles)?
Problem 2. Rounding.
Set the number of Levels to 4, and let us look closely at the reconstruction as we change the number of rounded bits. Compare with the original at all times. What are the features that deteriorate as the number of rounded bits increases? Describe, in some detail, for different images.
Is there are relationship between more rounding bits and compression? Use the space_saved display option.
Problem 3. Comparison.
With Levels set to 4, what is the largest number of rounded bits for which the reconstructed image is of comparable quality to the original? What is the percentage of saved space?
What is the number of rounded bits, and the percentage of space saved, for which the reconstructed image is of unacceptably low quality?
Problem 4. Filter Comparison.
Finally, we compare the Haar, 4-tap and jpeg-2000 filters. With Levels set to 4, look at the quality of the reconstructions after rounding off varying numbers of bits.
artifacts (changes introduced by the compression scheme), at special details, and the compression
Look at the overall quality, at the type of
ratios. Which of the filters do you prefer and why? (Provide at least three reasons.)
Problem 5. Huffman Coding
Use this tree:
Encode the word “AWESOME”
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.