University of St. Thomas Center for Applied Mathematics
Final Projects
Daubechies Scaling Function and Wavelet
All final project presentations will be made on Wednesday, May 14, 2008.
The number of asterisks (*) next to the project title indicates the maximum number of people allowed to work as a group on the project. These will be group projects - only under special circumstances will I allow a single student to work on a project.-
**Wavelet Packets
- Wavelet Packets is a variation on the wavelet decomposition method. When we apply a wavelet transform to a vector, we produce a lowpass portion and a highpass portion. We can iterate this process by applying the wavelet transform to the lowpass portion. Wavelet packets simply allow you to apply the wavelet transform on the highpass portion (at any iterative level) you so desire. Thus you have several options for decomposing a signal. Coifman and Wickerhauser devised an entropy based method for determining the best decomposition. In the first part of this project, you will write a module that will compute the wavelet packet transform of a vector. The second portion of the project involves writing a module that choose the best decomposition of the signal. The final part of the project involves using your modules to perform compression on digital audio files.
- **Coiflets
- Yale mathematician Ronald Coifman suggested to Ingrid Daubechies that it should be possible to construct orthogonal filters whose Fourier series H(w) had vanishing derivatives at w=0. Daubechies worked out a method for constructing such filters and in honor of Coifman, named them Coiflets. Using Section 8.3 as a reference, you will learn how to construct Coiflet filters. You will then test the effectiveness of Coiflet filters by comparing them to the D4 and D6 filters used in the denoising Lab 9.2
- ***Birothogonal Wavelets - 1D and 2D Transforms
- This project needs the results from the Biorthogonal Wavelets - Filter Derivation project. For this project, you will write a module that computes i iterations of the biorthogonal wavelet transformation of either a vector or a matrix. That is, you will be given a number of iterations, two lowpass filters, two highpass filters, and the input, and your module will return the transform of the input signal/image. You will also write modules that will compute the inverse biorthogonal transform. The modules are very much like the Haar 1D and 2D modules but the difficulty lies with applying the transform to a column or row vector. Sections 11.1 and 11.2 will serve as references for this project.
- **The JPG2000 Compression Standard (Lossless)
- In this project, you will implement the so-called Le Gall filter used by the JPEG 2000 Image Compression Standard to perform lossless compression. The key to the algorithm is the ability to modify the transformation so that it maps integers to integers. The technique used is called lifting. You will write a module to compute i iterations of the 2-D Le Gall wavelet transformation and then use your module on several test images to determine the effectiveness of the transform when used to perform image compression. Sections 12.3 and 12.4 will serve as reference material for this project.
- ***Image Identification - Experimental!
- This project is totally experimental! Suppose you have a library of digital images and wish to match it with a new image. Can we use wavelets to do it? If so, how? In this project, you will create a library of images and then use wavelets to take a test image and determine if it matches any image in your library. You should report on the mathematics behind your method for determining the image match. You should also then create Mathematica code for image identification and then run your code on 3-4 test images.
- ***Analyzing CAPTCHAs
- In the March 2005 College Mathematics Journal (Volume 26, Number 2), Grand Valley State mathematics professor Edward Aboufadel and students Julia Olsen and Jesse Windle published an article entitled Breaking the Holiday Inn Priority Club CAPTCHA. You have probably seen a CAPTCHA if you have made a purchase on a secure internet site. It is a scrambled word that you must type into a form field in order to proceed with your purchase. This is a security device that, among other things, can be used to keep people from making mass purchases. For this project, you will reproduce the work done by the authors of the article. It turns out they use Haar wavelets to break the code! You should report on their methodology and produce mathematica code to break a CAPTCHA.
- **BootStrapping and Edge Detection
- A key application of wavelet transformations is boundary or edge detection. In this application, it is your task to use wavelets to find boundaries or edges in a digital images. You start by taking the wavelet transform of an image and then you consider only the details of the transform. Large values in the detail portion of the detail sections often indicate boundaries in the original image. After deciding which large detail values to keep, the remaining detail values are converted to zero and the detail portions of the transformation are combined to produce a picture of the edges in the original image. Bootstrapping is a statistical method that you will apply to determine which detail coefficients you will keep. You will learn the mathematics behind bootstrapping and then apply it to 3-4 test images. For comparison purposes, you will use the Daubechies 4-term transform on all of your test images. You will then reconstruct the image of edges and see how bootstrapping did. You will compare your results to those obtained by using elementary statistical methods for determining which detail coefficients to keep. You should report on the mathematics behind bootstrapping. You should also then create Mathematica code to do bootstrapping and use it to edge detect 3-4 test images.
- **Nonperiodic Wavelet Transforms
- When creating the wavelet transform matrix, we "wrapped" rows near the end of each lowpass/highpass part of the transform. This was done to make it easy to identify orthogonality conditions. The downside is that the process implicitly assumes the input is periodic. This assumption is not realistic in many cases. For this project, you will learn how to "complete" a wavelet transform matrix by appropriately truncating the last rows of the lowpass and highpass portions of the transform. You will illustrate your results on the D4, D6, and D8 filters and discuss the advantages and disadvantages of the process. Homework problem 7.19 will serve as a reference for this project.
- **Modifying the D4 Filter To Map Integers to Integers
- This problem is theoretical in nature. It builds off Problem 7.17 and requires some knowledge (or willingness to learn) of the singular value decomposition. The D4 filter is composed of irrational numbers and it is easy to show that the only four-vector of integers we can dot with the D4 filter and obtain an integer value is (0,0,0,0). Thus the D4 filter does not map integers to integers. Using the ideas of Problem 7.17 and results in a paper by Calderbank, Daubechies, Sweldens, and Yeo, the D4 wavelet transformation can be modified so that it maps integers to integers. In addition to working out the details of Problem 7.17, you will look at the paper mentioned above and learn how to modify the D4 transformation so that it maps integers to integers. Extra credit is available if you write a mathematica module to perform the D4 integer-to-integer 1-D wavelet transformation.
- **SUREShrink Denoising
- Stanford statisticians David Donoho and Iain Johnstone developed a wavelet-based method for signal/image denoising called Wavelet Shrinkage. We investigated this method in Lab 9.2. In this lab, you will learn about a more sophisticated method of denoising called SUREShrink. This method is outlined in Section 9.3 and some knowledge of statistics is required. You will learn how to perform SUREShrink and then illustrate the method on some test signals and images.