Course: CIS451/651 Data Compression in Multimedia
Professor: Paul D. Amer
Semester: next time taught after Spring 2013
Title: Homework - Chapters 8 and 9 - Lossy mathematical preliminaries and Scalar Quantization

Tasks

Read Chapter 8 with emphasis on Sections 8.3 and 8.6.1. Omit Section 8.5.
Read Chapter 9 with emphasis on Sections 9.1-9.4, 9.6. Omit Section 9.7.

1. (15 pts) Midrise vs. Midtread Quantizers
• Recall two scalar quantizers evaluated in class for encoding an analog source generating values over the domain [-4.0, +4.0]. The midrise quantizer defined 8 equal sized intervals; the midtread quantizer defined 7 equal intervals. For this question, only consider the versions from class that used the interval midpoints as the reconstructed values. In class, design and evaluation of these two quantizers assumed the source input was uniform.
• Now suppose the source is non-uniform as follows. Assume 1/2 of the generated values are expected to be exactly 0, and the other 1/2 are uniform over the full domain [-4.0, +4.0]. Hence for the midrise quantizer, the interval [0,1) is expected to contain 9/16 of the values (8/16 are expected to be 0, 1/16 are expected to be uniform over [0,1)); and for the midtread quantizer, the interval [-4/7, +4/7) is expected to contain 8/14 of the values (7/14 are expected to be 0; 1/14 are expected to be uniform over [-4/7, +4/7)). Compare/contrast the midrise and midtread quantizers for this nonuniform input. That is (submit),
  1. (1pt each) compute the entropy of the system for each quantizer
  2. (2pts each) derive a Huffman code for each quantizer, and compute the average number of bits per input each coder will use
  3. (2pts each) graph each quantizer's squared error for the full domain
  4. (2pts each) compute each quantizer’s expected mean squared error
  5. (1 pt) argue which, if either, quantizer is better?
2. (10 pts) Chapter 8: Projects and Problems: 1(a) [1(b) is not required]
• The author uses the word "reconstruction." I believe a better word would be "modification".
• Instead of modifying images by +10 or +/-10, modify the images by +20 or +/-20, respectively.
• Perform modifications to two images: sena.img and earth.img. You will need to write a simple program in the language of your choice. For both modifications for both images, compute the new pixel values "without wraparound". That is, when adding 10 to any pixel in the domain [246-255], the resultant pixel would be 255. When subtracting 10 from any pixel in the domain [0-9], the resultant pixel would be 0. (Suggestion: use the od command to make sure your modified images are correct.)
• (submit) a copy of your well-commented program.
• (submit) Using Sayood's program distimg.c, calculate the SNR and other metrics for each of the four modified images. What do you observe about the metrics for each pair of modifications of the same starting image?
• (submit) For both sena and earth, print and label the original and both modified images. Note: to view a .img file, use Sayood's program convpgm.c to convert from .img to .pgm, and then use the unix program xv (or other available image software such as IrfanView or GIMP) to view and print the .pgm image file. All printed images should be at least 3" X 3".
• (submit) In your opinion, does one modified image more closely match the original? What does your opinion say about SNR and the other metrics?
3. (6 pts) Image Scalar Quantization
• (submit) Use Sayood's programs uqimg_enc.c and uqimg_dec.c to reproduce the scalar-quantized 1bpp, 2bpp and 3bpp images of sena.img as shown in Figure 9.7 and earth.img. For both sena and earth, print 4 figures as done in Figure 9.7.
• (submit) Use Sayood's program distimg.c, and make a table comparing the SNR and PSNR of the 1, 2, and 3 bit images you produced.
4. (Extra Credit 3 pts) Specify a scalar quantizer that inputs values over the domain [0,127.5) and outputs the value rounded to the nearest integer represented as a 7-bit unsigned integer. For example, an input of 65.83 results in an output of 1000010 and a reconstructed value of 66; an input of 65.306 results in an output of 1000001 and a reconstructed value of 65. Assuming the input is uniformly distributed, compute the mean squared error. Provide a figure to help clarify your mean squared error computation.
5. (Extra Credit 3 pts) Specify a scalar quantizer that resides inside a digital scale capable of weighing objects over the domain [0-300) pounds in 1/2 pound increments. Assume the scale truncates not rounds (a feature that customers like!) Assuming the input is uniformly distributed, (note: for humans, this assumption is invalid.) compute the expected mean squared error. Provide a figure to help clarify your mean squared error computation.

Notes

1. For all tasks where you write a program, submit well-commented source listings of your code.
2. Graduate students must do all assignments individually. Undergraduate students may collaborate in groups of 2 for assignments. Only one submission with both names should be turned in from a group.
3. Clearly label your answers, and please submit answers in the order assigned.
4. (repeated from course syllabus) Academic Honesty: Unless explicitly stated otherwise, students are not permitted to access or compare any homework, or program-project answers with those of any other student or group past or present, alive or dead, or any Internet web site prior to submitting the assignment. Comparing answers, or getting answers off the Internet before submitting one's work is considered cheating. If you do not have time to complete an assignment, it is better to submit partial solutions than to get answers from someone else. While it is obviously difficult to enforce this policy, students who do not follow this policy should be keenly aware that in this class, they a re cheating, and if caught, will be prosecuted according to University guidelines. This applies both to the student (or group) who gets answers and the student (or group) who gives answers.
5. (repeated from course syllabus)  Lateness Policy: Assignments are due at the beginning of class. Unexcused late assignments will be penalized up to 10% per school day (weekends do not count) up to a 2-day maximum penalty of 20%. Without prior discussion with the professor, assignments will not be accepted more than two school days late without a university approved excuse.