Math 382 Topics in Wavelets Final Projects Spring 2013

Instructor: Caroline Haddad

Possible Projects

Chuck Close Style Portraits

Chuck Close is an American artist who paints large ‘block portraits,’ which are a type of mosaic where the tiles are small rotated squares which contain abstract shapes. Despite the drastic change in fine details compared to a photograph, all of the abstract marks work together to create a realistic looking portrait. There is a certain duality: viewed up close, the paintings are flat and obscured, but from afar they seem to pop out into three dimensions. This article presents a new method to digitally create portraits in the block style of Chuck Close.

This is part of the abstract from a paper entitled: Digital creation of Chuck Close block-style portraits using wavelet filters. You will be expected to follow through the paper and reproduce what was done, and time permitting, carry through on some of their suggested expansions, or some of your own. Note that they perform Haar Wavelet transforms a bit differently than we do. Coding should be done in Matlab. I expect you will use your own digital images.

Wavelet Packets and Compressing Audio Files

Wavelet Packets is a variation on the wavelet decomposition method.

When we apply a wavelet transform to a vector, we produce a low-pass portion and a high-pass portion. We can iterate this process by applying the wavelet transform to the low-pass portion.

Wavelet packets simply allow you to apply the wavelet transform on the high-pass 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 chooses the best decomposition of the signal. The final part of the project involves using your modules to perform compression on digital audio files.

The Mathematica website is a good place to start.

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.

FBI Fingerprint Compression and Wavelet Packets

The FBI uses Wavelet Packets to compress fingerprints for storage in its AFIS data-base. The Wavelet Packet is a variation on the wavelet decomposition methods studied in class.

When we apply a wavelet transform to a vector, we produce a low-pass portion and a high-pass portion. We can iterate this process by applying the wavelet transform to the low-pass portion.

Wavelet packets simply allow you to apply the wavelet transform on the high-pass portion (at any iterative level) you so desire. Thus you have several options for decomposing a signal. An application-specific cost function is used to determine the best

The FBI uses a CDF97 wavelet. In the first part of this project, you will write a module that will compute the wavelet packet transform of an image The second portion of the project involves writing a module that chooses the best decomposition of the image. The final part of the project involves using your modules to perform compression on fingerprints, and finally to recover them.

The Mathematica website is a good place to start.

Biorthogonal 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 low-pass filters, two high-pass 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.

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

SUREShrink Denoising

Stanford statisticians David Donoho and Iain Johnstone developed a wavelet-based method for signal/image denoising called Wavelet Shrinkage that is covered in chapter 9.

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.

A good place to start might be

http://faculty.gvsu.edu/aboufade/web/wavelets/student_work/Ms/Welcome_Home.html

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 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 Matlab code to do bootstrapping and use it to edge detect 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 Matlab code to break a CAPTCHA. Perhaps look into using Daubechies wavelets and compare results, if time permits.

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 Matlab module to perform the D4 integer-to-integer 1-D wavelet transformation.

Partial Inverse Problem

Given an image transformed by the k iterations of the HWT write an algorithm that finds the inverse of a sub-matrix in the blur portion without inverting the entire matrix. This is known in the medical field as "region of interest" ( it’s a piece of the blur portion of the transformed image).

You should write a code that will identify which pieces of the transformed matrix will be needed to reconstruct that portion of the image. This should be something that works automatically once you enter the coordinates of the region (i.e. you should not have to calculate this by hand for each given image). Then your code should find the inverse of this. (You should be doing a partial inverse and NOT finding the inverse wavelet transform of the entire image.) You should do this for k=1, 3, 5 with the HWT. Then repeat for D4 or D6. Weird things happen with the wrap-around that depend directly on the value of k. You should determine what they are for each filter in terms of k. Discuss how you might fix them.

Steganography/Steganalysis

Steganography is the ancient art of embedding a secret message into a seemingly harmless one. For example embedding a secret message in seemingly harmless spam, hiding them in sound files, or perhaps embedding an entire image into another image.

The simplest replace the least significant bits of the image with the most significant of the secret information. Discrete wavelet transforms can also be used (such as integer transforms). I believe that trying to do a project with image embedding might be too difficult with so little time (can anyone say Directed Study?).

I would approach the simpler task of trying to embed a message in a sound file or an image. You will learn how wavelets can be used to hide information and compare the results to those of the simplest technique.

Your code should be able to encode the message and then decode it.

I would start with the following article and try to follow the results in the paper by Lisa Driskell on Wavelet Based Steganography in the April 2004 issue of Cyrptologia.

Steganalysis is the art of detecting a steganographic image. This is too difficult to tackle at this time, but you might include something in your write-up that would allow a steganalyst to detect that an image or sound file has been altered.

Comparing the naive image compression

In Chapter 6 using cumulative energy is used as the quantization method In chapter 9 the shrinkage function from Chapter 9. Figure out a "good" threshold for the function and use that to quantize – (you should also talk a bit about dequantizing) - in as much as you can only somewhat invert the shrinkage function. That'd be a good doable project with some room to experiment.

Using Wavelets to Identify Handwriting/Painting Forgeries

This is a fairly weighty project. However, if you stick to the Handwriting and not the Painting at this time, this could be do-able. This does involve some statistics.

Painters have a certain style of painting. The brushstrokes are fairly unique to a particular artist. Typically when an artist attempts a forgery, they use far too many brush strokes and strokes that are not characteristic of the artist. When an image of the painting is decomposed using a discrete wavelet transform, these differences show up in the Difference Portions of the transform. People have found a way to quantify this with a messy formula of many variables. Some have found a way to “boil down” this information so that a statistical analysis can be done. A topological metric is used to look at the “distance” between paintings and early results show that those that are within a certain distance of a painting known to be painted by a famous artist are likely to also have been painted by that artist. Those that are “far away” are more likely to be reproductions or forgeries.

A PBS special was done where several groups used different techniques to prove which one group featured our hero, Ingrid Daubechies, and used wavelets.

A similar technique could be used to detect handwriting forgeries. What you would have to do is gather writing samples of friends, scan them into an image, have someone try to forge another’s handwriting, and write a code to use wavelets to detect the forgery. There is a paper that I can give you to start off the process. Start here:

http://faculty.gvsu.edu/aboufade/web/wavelets/students.htm

(Note: This was done in Fall 2009. Instead of starting from scratch, it might be possible to pick up where the last group left. Please see me if you are really interested. This was a difficult project to work on, in part, because of the background statistics knowledge required.)

You may propose your own projects. Detailed descriptions, along with references, must be provided to me by April 19, along with your project preferences.