15-859B: Assignment 4: Wavelet Image Compression

Summary

Reading

Details

• Implement (a) wavelet decomposition of images (a.k.a. the wavelet transform), (b) compression of the wavelet coefficients by quantization and (c) reconstruction (inverse wavelet transform) of images from the compressed wavelet representation.
• You can implement in any computer language, but Matlab is probably easiest.
• Your program should read and write picture files. At minimum, your program should read pictures with 8 bits of grayscale per pixel. In Matlab, see 'help imread' and 'help imwrite' for picture I/O.
• Stollnitz' compression scheme is a little complicated because it involves sorting or binary search.

  We'll do even simpler compression: After computing the wavelet transform of the image, quantize its coefficients to b bits per coefficient. Reasonable values of b will be between 8 and 16.

  To do this, first find the largest coefficient in the wavelet transform -- that will be the coefficient of the broadest scaling function, phiphi(x,y). Call this value cmax. Scale all coefficients so that the range [-cmax,cmax] is mapped to a signed, b-bit integer, i.e. a number between -2^(b-1) and 2^(b-1), quantize these values to integers using floor() to create a new coefficient array.

• Now reconstruct an image from the quantized wavelet transform. First you'll probably want to undo the scaling that you did just prior to floor-ing, so that your coefficients are back in their natural range. Then do reconstruction via the inverse wavelet transform. If any of the reconstructed pixel values come out <0 then set them to 0 or if >255 then set them to 255. Now we've got an 8-bit image again.
• For testing, write out your wavelet transform to a picture file (scaled to 8 bits per pixel) and also write out the reconstructed picture (after compression) to a separate picture file. The former should look like the bottom right image of Stollnitz's figure 6. If you write JPEG from Matlab, use "'Quality',100" in your options to imwrite() to minimize additional compression effects.
• I don't expect you to implement it, but real compression could be achieved using an entropy coding scheme that exploits the large number of zero coefficients in the wavelet transform. Huffman coding is such an approach.

  I do ask you to estimate the compression achievable using a very simple sparse matrix compression scheme: we could use one bit per coefficient to record whether its value is zero or not, and then use b additional bits per coefficient for the nonzero values. Call this number of bits the "compressed image size". Now calculate (compression factor) = (original image size)/(compressed image size) where original image size is pessimistically taken to be 8*npixels bits (note that JPEG and other picture file formats do much better than 8 bits per pixel, typically).

• Measure the error of the reconstructed image. Compute the relative L2 error of the output image "out" relative to the input image "in": sqrt(sum over x,y of (in[x,y]-out[x,y])^2) / sqrt(sum over x,y of in[x,y]^2)). This is the reciprocal of the "signal to noise ratio" that is popular in signal processing.
• Run your program on a picture provided by me, such as src/asst4/roar512.jpg (512x512 pixels). You can use the smaller versions (e.g. roar8.jpg is 8x8 pixels) for testing. Also run your program on a picture of your own choosing.
• Make a table listing

  picture-name   npixels   b  cf    rel.err
      

  where "cf" means compression factor. Run each picture at least two times with results including one run where the errors of compression are invisible, and another where they're barely visible.
• Turn in:
  • Discussion of what you did.
  • The statistics described above.
  • Pictures described above.
  • Code listing.

Tips

• It will be simplest to implement all of this using floating point arithmetic, but it's possible to do most of it in integer arithmetic, if you're careful.
• For Matlabbers, try to implement the wavelet transforms and compression at the matrix or vector level, not at the scalar level. Otherwise it will be quite slow. It's also good brain exercise to learn to think "in parallel".
• Make your pictures square and powers of two in width & height. 512x512 pixels is a good size. You can use the "xv" program or "Photoshop" to resample an image to any size, or to convert it to grayscale.
• Hopefully you won't have to write your own picture file I/O routines, but if you do, I suggest the PGM file format.
• You could use Matlab, xv, or Photoshop to print your pictures.
• I'll give extra credit worth up to 40% of the entire assignment to anyone who implements a non-Haar wavelet, e.g. the Cohen-Daubechies-Feauveau biorthogonal wavelet given in Burrus' table 7.2, or see their paper, A. Cohen, I. Daubechies, J. Feauveau, "Biorthogonal bases of compactly supported wavelets", Commun. on Pure and Applied Math., vol. 45, 1992. That is a wavelet that the "big boys" of image compression might use. By comparison, Haar is child's play. I recommend you implement Haar first, for practice, however.