Back to . . .

Curve Bank Home

Wavelets Part I

Wavelet Applications

Historical background slideshow

Wavelet compression vs jpeg images

             Data Analysis:
Data Analysis categories

Here is the histogram for one iteration . . .

Histogram one iteration

and after two iterations . . .
Histogram two iterations

The Haar Wavelet Transform
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 . . .
Other information button 

NCB logo

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.

    Data analysis: directional differences

  • 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: Matrix expression

The left side becomes . . . . ..............

and the matrix is called the

Haar Wavelet Transformation

Haar Wavelet Transformation
And what about the inverse ?????? Inverse of matrix

Here is the

Inverse Haar Wavelet Transformation

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.
Code modification
The same result can also be obtained by computing . .........................
Another calculation
More code
HWT applied to the image
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.
    Equation 1
  • First take the absolute value of each entry and then sort the data from largest to smallest.
    Equation 2
  • Now sum the squares of the entries.
    Equation 3
  • The squares of the sorted vector are and the sum of these squares is 78.
    Equation 3 cont.
  • Recall the list of squares is Equation 4.  We form the cumulative energy vector  y  as follows:
    Equation 5

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!

"Before" image

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.

"After" image


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

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

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

University of St. Thomas Center for Applied Mathematics
          <  >

Osmar R. Zaïane, University of Alberta, Canada
          <  >

Fourier Series:  Oscillating Harmonic Vibrations
          <  >

Center for Wavelets, Approximation and Information Processing, National University of Singapore

          < >

The Engineer's Ultimate Guide to Wavelets
          < > .

Another Introduction to Wavelets
          < >

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.
MAA workshop logo
Home button
MAA logo