What is a Wavelet?
Sarah Constantin
October 20, 2011
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
1 / 17
Sparse Approximation
Goal: express a signal sparsely.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
2 / 17
Sparse Approximation
Goal: express a signal sparsely. Approximate functions as linear combinations of elements in a dictionary of elementary wave forms.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
2 / 17
Sparse Approximation
Goal: express a signal sparsely. Approximate functions as linear combinations of elements in a dictionary of elementary wave forms. Why?
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
2 / 17
Sparse Approximation
Goal: express a signal sparsely. Approximate functions as linear combinations of elements in a dictionary of elementary wave forms. Why? Image compression, ecient image processing.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
2 / 17
JPEG image compression
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
3 / 17
Fourier Transform
f (t) = 1/2 f () =
f ()e it d
f (t)e it dt
When discretized, the Fourier transform expresses a function as a linear combination of exponential functions e 2ikn/N .
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
4 / 17
Problems with the Fourier Transform
The problem is that the exponential functions are global. Theyre dened over all of CN . For a localized signal say, a corner in an image it takes too many Fourier coecients to approximate.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
5 / 17
The Haar Wavelet
(t) = 1 if 0 < t < 1/2, (t) = 1 if 1/2 < t < 1 (t) = 0 otherwise. Dilations and translations of form an orthonormal basis of L2 (R): 1 2j n 1 )} {j,n (t) = ( 2j 2j j denotes the neness of the scale, and n denotes the location of the wavelet; each wavelet is localized in space, unlike the Fourier modes.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
6 / 17
Haar transform
Express a signal as a linear combination of projections onto the wavelets.
f , j,n =
f (t)j, (t)dt
f =
j= n=
f , j,n j,n
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
7 / 17
Haar Wavelets
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
8 / 17
Wavelets in general
You dont have to use a Haar wavelet; there are many possible choices for wavelets. You just need 1 2j n 1 )} {j,n (t) = ( 2j 2j and a choice of that integrates to zero, and whose Fourier transform has the property |()|2 d < . ||
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
9 / 17
Daubechies Wavelet
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
10 / 17
Discrete Wavelet Transform
First, convolve the signal with a low-pass lter, for the low-frequency coecients:
ylow [n] =
k=
x[k]g [2n k]
Then convolve with a high-pass lter, for the high-frequency coecients:
yhigh [n] =
k=
x[k]h[2n k]
Downsampling (half the samples) is okay by Nyquists rule, since half the frequencies are gone. This process is repeated high-pass lter, low-pass lter, and downsampling, in a binary tree.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
11 / 17
Discrete Wavelet Transform Illustrated
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
12 / 17
Application: Denoising with Wavelets
A noisy signal is modeled as the sum of a clean signal and high-frequency noise. Solution: express the signal in the wavelet basis and threshold so that only the large coecients are preserved: f =
j k
jk jk (t)
is approximated by (f ) where (djk ) = 0 if |djk | and (djk ) = djk if |djk > .
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
13 / 17
Wavelets for Image Processing
High wavelet coecients pick out edges and sharp contrasts
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
14 / 17
Wavelets for Image Processing
High wavelet coecients pick out edges and sharp contrasts Wavelet coecients also pick out local features
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
14 / 17
Wavelets for Image Processing
High wavelet coecients pick out edges and sharp contrasts Wavelet coecients also pick out local features Wavelets form a good basis for image compression; the JPEG2000 standard is based on the wavelet transform.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
14 / 17
Wavelets in Vision
The visual systems contains analogues to wavelets.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
15 / 17
Wavelets in Vision
The visual systems contains analogues to wavelets. Not all of the retina is equally light-sensitive; visual acuity is highest at the fovea.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
15 / 17
Wavelets in Vision
The visual systems contains analogues to wavelets. Not all of the retina is equally light-sensitive; visual acuity is highest at the fovea. Active vision compensates with eye saccades at lower resolutions
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
15 / 17
Wavelets in Vision
The visual systems contains analogues to wavelets. Not all of the retina is equally light-sensitive; visual acuity is highest at the fovea. Active vision compensates with eye saccades at lower resolutions Multiresolution reconstruction sums information from dierent levels of acuity in an image pyramid analogous to the discrete wavelet transform.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
15 / 17
Marr-Hildreth Operator
Marr and Hildreths Laplacian of Gaussian function (the Marr Wavelet or Mexican Hat Wavelet) is a wavelet.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
16 / 17
Marr-Hildreth Edge Detection Algorithm
Convolve an image with the Laplacian of the Gaussian, at dierent scales and locations; the zero crossings represent edges.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
17 / 17
Marr-Hildreth Edge Detection Algorithm
Convolve an image with the Laplacian of the Gaussian, at dierent scales and locations; the zero crossings represent edges. Retinal ganglion X-cells have receptive elds accurately described by the dierence of two Gaussians.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
17 / 17
Marr-Hildreth Edge Detection Algorithm
Convolve an image with the Laplacian of the Gaussian, at dierent scales and locations; the zero crossings represent edges. Retinal ganglion X-cells have receptive elds accurately described by the dierence of two Gaussians. Detecting the zero-crossings of a wavelet transform is equivalent to the Marr-Hildreth edge detector.
Sarah Constantin ()
What is a Wavelet?
October 20, 2011
17 / 17