Projects for Wavelets and Image Processing

This is a list of possible projects for MA 692B. Projects can be programmed in C, C++, Fortran, or Scheme. Projects should take pgm or ppm files as input and, where appropriate, as output. The pgm and ppm file formats are particularly easy to read and write; one can also use various libraries that are available on the Suns and the Alpha. Students can suggest their own project topic.

Everyone must get their project pre-approved by me. The following are very brief summaries of suggested projects; if any of them interest you, then you should ask me for more details.

• Write a program to calculate the two-dimensional Haar transform of an image, do scalar quantization to compress that image. You are allowed to reject any image that is not of size 2k square for some k. Your program must work as a filter, and take the Lp space that determines the scalar quantization scaling as a parameter.
• Write a program to take a description of a wavelet transform (a description in a form that you specify, i.e., width and coefficients) and apply it to an image. You must deal with boundary conditions in a reasonable way; reflecting the image across the boundary is reasonable, assuming the image is periodic is reasonable, assuming the image is zero outside the domain is not reasonable. For extra credit, allow a description of boundary wavelets to do high-order wavelet approximation even at the edges of the domain.
• Write a program to compress two-dimensional, uniformly-spaced data with a maximum (L-infinity) bound on the error. You must use (at least) piecewise-linear approximation; I suggest you use the (sub-optimal) algorithm given in "Surface Compression", by DeVore, Jawerth, and Lucier in Computer Aided Geometric Design in 1992. For extra credit, use smoother box-splines, or write a program using the algorithm given in a paper by DeVore and Yu.
• Write a program to remove Gaussian noise from images using Donoho and Johnstone's method of Wavelet Shrinkage. You can use Haar wavelets and reject all images that are not of size 2k square for some k. You should estimate the noise level sigma by sqrt(Pi/2) times the median of the absolute value of wavelet coefficients. You can use sqrt(log(N))sigma as the shrinkage parameter, where there are N pixels in the image. For extra credit, write an O(N) routine to calculate the median rather than just sorting the absolute values of the wavelet coefficients in O(N log(N)) time and then taking the middle one. For extra credit, use the SUREShrink algorithm to choose the shrinkage parameter.
• Write a program to compress the solution u(x,y,t) of a parabolic differential equation; the software to solve the equation is available on my CS 615 web page. Start with a coarse-grid triangulation of the domain and refine it several times; this will give you the multiresolution structure you will require for the compression. This program will require you to do three-dimensional compression using piecewise linear approximation. For extra credit, try Leisner's anisotropic wavelet compression method and see if that method results in better compression ratios.
• Write a program to interpolate missing data in a rectangular region of an image by applying a variational principle with a Besov space as smoother. If you get good results then write a paper about it (extra credit).
• Write libraries to do fast single-precision wavelet transforms using the AltiVec instruction set on the Macintosh under LinuxPPC. For extra credit, have these libraries work in more than one dimension. For extra credit, see if you can compress video using these routines in something approaching real time (> 10 frames/second).