Course: CIS451/651  Data Compression in Multimedia
Professor: Paul D. Amer
Semester: Next usage after Spring 2009
Title:  Homework - Chapter 14 - Subband Encoding
Due Date:

Tasks

Read Chapter 14. Focus on Section 14.1, 14.2, 14.9-14.13. Omit Sections 14.5-14.8.

1. (5 pts)  Perform a 3-level 2-dimensional Haar subband transform as presented in class on the following 8X8 "image". (Submit work showing all intermediate transforms.)
• The method used in the book's Example 14.12.1, while similar, is NOT identical to Haar's method as presented in class.
• HINT: Consider using MATLAB or programming the Haar transform in an Excel spreadsheet

24  12  12   0  12   0   0 -12
 8   4   4   0   4   0   0  -4
12   6   6   0   6   0   0  -6
 4   2   2   0   2   0   0  -2
-4  -2  -2   0  -2   0   0   2
-4  -2  -2   0  -2   0   0   2
 0   0   0   0   0   0   0   0
-8  -4  -4   0  -4   0   0   4

2. (5 pt) Quantize the transformed image from Problem 1 in the following two ways to form two quantized images:
• (1/2 pt) Quantize all values in the HH component to 0. (The HH component is the lower right quadrant.)
• (1/2 pt) Quantize all values in the HH, HL, and LH components to 0.
• (4 pts) Perform the inverse 3-level 2-dimensional Haar transform in both cases above, and compute the PSNR in decibels for both reconstructed images.
• HINT: Consider using MATLAB or programming the inversed Haar transform in an Excel spreadsheet. Or do the inverses by hand to better understand how to work “backwards,” i.e., in the inverse direction.
3. (5 pts) Perform an inverse 3-level 2-dimensional Haar subband transfrom as presented in class on the following 8X8 matrix. You may use Matlab or the Excel spreadsheet developed for Problem 2. Show your work for all intermediate steps. Assume the forward transform transformed each row in all three levels, and then transformed each column in all three levels. Hence your inverse should invert each column in all three levels (first invert level 3, then invert level 2, then invert level 1), and then invert each resulting row in all three levels (first invert level3, then 2, then 1).

8  6  4  3  6  0  7 -1
1 -2  0  4  3  8  5 -3
0 -3  9  4  2  5  7  0
4  1 -3  4  3  0  0  0
1  1 -1 -1 -1  1  1  1
2  2  2  2  2  2  2  2
0  1  0  1  0  1  1  0
3  2  0  1  7  2  2 -4

4. (5 pts) Derive the 3-level 1-dimensional inverse Haar Transform basis set for N=8. Show all work. (The answer consists of 8 - 1X8 vectors.) (In class, we showed the forward 3-level 1-D Haar Transform). Draw an analogous picture to that shown in Figure 13.3 for your basis set. Using Matlab, apply your inverse to the matrix in the previous problem (twice; once in each dimension) to verify the your answer to Problem 3.

5. (4 pts) Does the order of performing transforms matter? Consider the 4X4 image used in the class presentation, and repeated here:

   18  8  9  1
   20  6 11 15
   16  8  6  6
    6  6 -2  2

   • In the class exercise, we first transformed level 1 and 2 on the rows, and then transformed level 1 and 2 on the columns. For this example, transform levels 1 and 2 on the columns and then levels 1 and 2 on the rows. Do we get the same result as in class?
   • For the original example, now transform level 1 on the rows, then level 1 on the columns, then level 2 on the rows, and finally level 2 on the columns. Do we get the same result as in class?
6. (Extra Credit: 3 pts) Derive the 3-level 2-dimensional Haar Transform basis matrices for N=8. (The answer consists of 64 - 8X8 matrices.) In addition to submitting the answer, please email this answer to the Professor.
7. (Extra Credit: 3 pts) Derive the 3-level 2-dimensional inverse Haar Transform basis matrices for N=8. (The answer consists of 64 - 8X8 matrices.) In addition to submitting the answer, please email this answer to the Professor.
8. (Extra Credit: 2 pts) Derive the 3-level 1-dimensional normalized Haar Transform basis set for N=8. (The normalized transform uses (a+b)/(2^.5) and (a-b)/(2^.5) rather than (a+b)/2 and (a-b)/2). Draw an analogous picture to that shown in Figure 13.3 for your basis set. In addition to submitting the answer, please email this answer to the Professor.
9. (Extra Credit: 2 pts) Derive the 3-level 1-dimensional inverse normalized Haar Transform basis set for N=8. Draw an analogous picture to that shown in Figure 13.3 for your basis set. How does your answer relate to the previous question's answer? In addition to submitting the answer, please email this answer to the Professor.
10. (Extra Credit: 2 pts) Derive the 3-level 2-dimensional normalized Haar Transform basis matrices for N=8. (The answer consists of 64 - 8X8 matrices.) In addition to submitting the answer, please email this answer to the Professor.
11. (Extra Credit: 2 pts) Derive the 3-level 2-dimensional inverse normalized Haar Transform basis matrices for N=8. (The answer consists of 64 - 8X8 matrices.) In addition to submitting the answer, please email this answer to the Professor.

Notes

1. Show all work for full credit.  Students may work individually or in groups of 2.   Students in different groups may NOT compare answers prior to submitting their work.  See the syllabus for the full statement on the lateness and academic honesty policies.