# 15-859E Programming Assignment 3: Wavelet Image Compression

Due Date: 11:59pm Mon. 2 Nov. 1998

Revision 3: 30 Oct. 98.

In this assignment, you'll implement simple Haar wavelet image compression. Image and signal compression is one of the most important applications of wavelets. The primary reference is the Stollnitz book, chapters 2 and 3.

Earlier, I said that the assignment would be variational surface modeling, but that appeared too involved for the short time we have, so I settled on this simpler assignment.

### Tips

• I bet float will give sufficient precision, and that doubles won't be necessary.
• 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.
• A very simple picture file format I recommend is PGM. I have code for reading/writing PGM files that you can see in pic.c, pic.h, and pnm.c. Or more interesting, inout.cc is a main program that uses it to read a picture into an array of doubles. To convert a picture from TIFF format to PGM, try "tifftopnm". The "convert" program is another good picture file format conversion program. There's also a library called libpgm for reading/writing this format. Try "rtfm libpgm" on Andrew. The PGM file format is documented in "rtfm pgm". For more info on PGM, see the software page.
• You could use "xv", "photoshop", or "pnmtops" to print your pictures. Photoshop doesn't understand PGM file format, however.
• I suggest you put picture file names, frac, and b on the command line, to avoid recompiling for each run. The argument parser discussed in the multigrid assignment would be handy for that.
• There won't be any starter code, per se, beyond that mentioned above.
• Here's a simple quantization formula for converting coefficient c[i,j] into quantized coeff qc[i,j] and then back to recovered coefficient rc[i,j]. It simply maps the interval [-cmax,cmax] to b bits, temporarily stores it into an integer variable, and then converts back.
```double c[i,j]
#define TINY .001
// cmax is max of |c[i,j]| for all i,j
//   (probably the coeff of the level 0 scaling fn, I'm guessing)
double scalefactor = (pow(2,b-1)-.5-TINY)/cmax
int qc[i,j] = floor(scalefactor*c[i,j] + .5)
// qc is an integer in [-2^(b-1)+1,2^(b-1)-1]
double rc[i,j] = qc[i,j]/scalefactor
// rc is approximately equal to c
// the more bits you use (large b) the closer it is
```
• Note that even if you set frac=1, quantization will probably cause some of the smaller coefficients to be zeroed.
• You could also calculate the RMS error in the "wavelet domain", as Stollnitz did. That might work out to be faster.
• Please put some effort into optimization. In your inner loops, instead of dividing by "sqrt(2)", multiply by a constant equal to sqrt(1/2). The header file /usr/include/math.h has one. I hope I don't see any code that looks like:
```    c2[pow(2,j)/2+i] = (c[2*i-1]-c[2*i])/sqrt(2);
```
Use "1<<(j-1)" instead of "pow(2,j)/2", or better yet precompute that outside the loop! The fastest implementation would use pointers.
• For the ambitious, after you get the above done, some extra credit options:
• Color images
• Interactive program: put frac, b on sliders and display the output picture, instead of writing it to a file. Optimize the heck out of it.
• Do compression for real. Write out a compressed image file and try to make it as small as possible without sacrificing image quality. You might want to use Huffman coding or arithmetic coding on the quantized values.
• Try other wavelet bases. Haar is a primitive wavelet, and human vision is very sensitive to its step discontinuities. Stollnitz page 197 talks about some options.

15-859, Hierarchical Methods for Simulation
Paul Heckbert