Wavelets

Back to . . .

Data Analysis:
Data Analysis categories

Here is the histogram for one iteration . . .

and after two iterations . . .
Histogram two iterations

The Haar Wavelet Transform
and
Digital Images

Begin with a random image -
let's call him Jesse,
Ilustrative image of a person

and then apply a "HWT" transformation to the image.
HWT appied to the image
The upper left quadrant is the approximate of the original image, while the upper right, and lower quadrants represent only the vertical, horizontal and diagonal details of the original.

.....and then apply a second "HWT" transformation to the previous iteration.

Clearly, there is much freedom in choosing data for the lossy compression.

The 'correct choice' depends upon the selection, and belongs to the 'art' of mathematics.

For Huffman Coding in
Part I . . .

NCB Deposit # 65

Patrick Van Fleet, University of St. Thomas, St. Paul, MN
NSF DUE-0442684

Continuing with the basic ideas of Wavelet transformation, we now examine . . . . .

Building Our Wavelet Transform - Examples

Suppose we have the following list of numbers we wish to send to a friend over the internet and we wish to accelerate the transfer:

{ 200, 220, 150 140, 96, 100, 100, 100}

We average the numbers two at a time.
We give the directional difference between each of the pairs we averaged.
Finally, we have to make sure we can invert the process. We might verify the inversion as follows:

Inverted expression

If you are familiar with matrices, you can write this transformation as follows:
The left side becomes . . . . .............. and the matrix is called the Haar Wavelet Transformation
And what about the inverse ??????
Here is the Inverse Haar Wavelet Transformation

Making the transformation using MATHEMATICA® notebook.

One loop is needed.
This algorithm is very slow when the length of x is large. You can write a much more efficient module in MATHEMATICA® using N = 8 and the top portion of the Haar Transform.
The same result can also be obtained by computing . .........................


Finally, it is quite simple to apply the Haar Wavelet Transform (HWT) to a digital image. Think of a digital grayscale image as a matrix of dimensions N X M whose entries are integers ranging from 0 (black) to 255 (white). Look at Jesse's digital photo in the left column for an example.

Quantizing the Output

Now it is desirable to have a method for determining which values are more or less unimportant and may be converted to 0 in a transformed data set.

If we do such a conversion, we are performing lossy compression. Cumulative Energy is used for the task.
Computing the cumulative energy is quite easy. We use the data as a running example.
First take the absolute value of each entry and then sort the data from largest to smallest.
Now sum the squares of the entries.
The squares of the sorted vector are and the sum of these squares is 78.
Recall the list of squares is . We form the cumulative energy vector y as follows:

Putting it All Together - Image Compression

We begin by taking two iterations of Jesse using HWT.

We will retain 99.9% of the energy of the signal. That means we will retain the 9883 largest elements (in absolute value) in the transform and convert the remaining 64517 elements to 0. This means that 86.72% of the transform consists of 0's!

Now we want to retrieve Jesse from his compressed data image.

We need to multiply all the elements of the quantized transform by 2 to create integers (this is easily inverted) and then we can compute the Huffman codes for the quantized transform.

The image has dimensions 300 x 248 so we need a total of 300 x 248 x 8 = 595200 bits to encode it.

The quantized wavelet transform can be reduced to 181902 bits using Huffman codes! This is coding at 2.445 bpp!

Jesse has been retrieved using the inverse HWT of the quantized wavelet transform.

References

[1 ] R. C. Gonzalez and R. E. Woods, "Digital Image Processing", 2nd ed., Prentice Hall, 2002.

[2 ] C. K. Chui, “An introduction to wavelets ”, Academic Press, San Diego, 1992.

[3 ] W. Dahmen, Multiscale problems and methods in numerical simulations, CIME Summer Course, 2001
< http://www.igpm.rwth-aachen.de/dahmen/cime/ >.

[4 ] I. Daubeschies, “Ten lectures on wavelets ”, SIAM, Philadelphia, 1992.

[5] Mark W. Drew and Ze-Nian Li, "Fundamentals of Multimedia", Prentice Hall, 2003.

[6 ] A. Gelb and E. Tadmor, Detection of edges in spectral data, To appear in Applied and Computational Harmonic Analysis.

[7 ] S. Mallat, “A wavelet tour of signal processing ”, Academic Press, 1998.

[8] E. J. Candes, Harmonic analysis of neural networks, Appl.Comput.Harm.Anal., 6 (1999), 197-218.

Links University of St. Thomas Center for Applied Mathematics
          < http://cam.mathlab.stthomas.edu/wavelets/ >

Osmar R. Zaïane, University of Alberta, Canada
          < http://www.cs.sfu.ca/CC/365/li/material/cgi-bin/wavelet.cgi >

Fourier Series: Oscillating Harmonic Vibrations
          < http://www.tfh-berlin.de/%7Eschwenk/hobby/fourier/einzelbilder.html >

Center for Wavelets, Approximation and Information Processing, National University of Singapore
          < http://www.cwaip.nus.edu.sg/demo/wdic.htm >

The Engineer's Ultimate Guide to Wavelets
<http://engineering.rowan.edu/%7epolikar/WAVELETS/WTtutorial.html > .

Another Introduction to Wavelets
< http://www.amara.com/IEEEwave/IEEEwavelet.html >

Dr. Van Fleet's project on Wavelets and Applications: A Multidisciplinary Undergraduate Course on Scientific Computing was an MAA Professional Enhancement Program in Summer 2006 and an MAA Minicourse at the Joint MAA-AMS New Orleans Meeting, January, 2007.