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).