Wavelet & FFT Resources

1. Fourier Transform

2. Applications of the Fourier transform

3. Exercise: JPEG Encoding with MATLAB

4. Short term Fourier transform

5. Wavelets

6. Applications of wavelets

7. Exercise:JPEG-2000 Encoding with MATLAB

Fourier Transform

The Fourier transform transforms functions (or signals in the discrete case) from the time domain to the frequency domain. The drawbacks of Fourier transform are

• Only frequency information is available, there is no time information.
• Because of the non-locality of the basisfunctions it is bad for non-periodic functions. (worst case example: the dirac delta function needs all Fourier coefficients)

The transform is popular because of a fast implementiation, the fast Fourier transform (FFT).

Applications of the Fourier Transform

• The Fourier transform works well for audio signals, for examplecompression or noise reduction.
• The JPEG image format (offical site) uses the discrete cosine transform (DCT).
• Differential equations http://www.sosmath.com/fourier/fourier6/fourier6.html
• MPEG video compression uses the DCT (http://www.mpeg.org/MPEG/index.html)

Exercise: JPEG Encoding with MATLAB

There is an introduction to JPEG compression using MATLAB (ps.gz, pdf)
and matlab source files (tar.gz  *,  zip) as well as example images (tar.gz  *, zip).
You can use the LaTeX source (tar.gz,  *,  zip) if you want to use a matrix or a figure from the `introduction paper'.

Short term Fourier Transform

To overcome the lack of compactness in the Fourier basisfunctions one can use windows in the time domain. A window has a certain width and is shifted over the domain, usually the windows overlap and a convolution is used with a function that falls off at the ends of the window. The short-term Fourier transform however faces the Heisenberg Uncertainty Principle:
Wide window <-> Good frequency representation <-> bad time localisation.
Narrow window <-> Bad frequency representation <-> good time locatisation.

Wavelets

The resolution problems in the Fourier analysis techniques can be overcome by a multiresolution analysis. Essentially this means considering the function/signal at various levels in the time domain. At the smallest scale one obtains the slowly varying features while at higher scales more detail is incorporated. The wavelet transform makes this possible. The wavelet transform uses basisfunctions that are generated from a compactly supported mother wavelet by means of dilations and translations.

Links

• http://www.amara.com/current/wavelet.html is a good starting point.
• as is www.wavlets.org.
• A wavelet tutorial by S. Mallat
• http://perso.wanadoo.fr/polyvalens/clemens/wavelets/wavelets.htm
• Wim Sweldens
• Gilbert Strang

Applications of the wavelet transform

• Image compression(FBI fingerprint compression (http://www.amara.com/IEEEwave/IW_fbi.html, http://www.gvsu.edu/math/wavelets/links.htm)
• Denoising
• Detecting Self-similarity in a Time Series (http://www.amara.com/IEEEwave/IW_selfsim.html)
• Detecting discontinuities in signals
• Seismology (http://www.ima.umn.edu/short_course_material/Felix_Herrmann/, http://www.cwp.mines.edu/~zmeng/waveletlab/waveletlab.html )
• Sound Sythesis (http://www.amara.com/IEEEwave/IW_musicaltones.html)
• Estimation of the global fractal dimension (http://www.swin.edu.au/chem/complex/vp/vp07/vp07.html)
• Differential equations
• JPEG 2000 (http://ltswww.epfl.ch/~dsanta/teaching/, http://css.engineering.uiowa.edu/%7Eaip/papers/lossy_wavelet_compress01.pdf, http://www.jpeg.org/JPEG2000.html)
• Pattern recognition
• Diverse applications and sample student assignments at http://faculty.gvsu.edu/aboufade/web/dw.htm.
• Content-based Image Retrieval Project, image search engine (http://www-db.stanford.edu/IMAGE/)

Exercise: JPEG-2000 Encoding with MATLAB

There is an introduction to JPEG-2000-like compression using MATLAB (ps.gz, pdf)
and matlab source files (requires matlab6, crashes under matlab7!) (tar.gz  *) as well as example images (same as for JPEG encoding with MATLAB).
You can use the LaTeX source (tar.gz,  *, zip) if you want to use a matrix or a figure from the `JPEG-2000 introduction paper'.

Additional links

• Huffman coding: Here (Course on Data Structures and Algorithms by John Morris) is a very instructive applet (by Woi Ang) that explains how the huffman coding works: just run the applet. If that is not instructive enough, there is a writen explanation as well.