0.2 Computational harmonic analysis  (Page 3/3)

The multiresolution theory of Mallat (Mallat:89b) and Meyer(Meyer:92c) proves that any conjugate mirror filter characterizes a wavelet ψ that generates an orthonormal basis of ${\mathbf{L}}^{\mathbf{2}}\left(\mathbb{R}\right)$ , and that a fast discrete wavelet transform is implemented by cascading these conjugate mirror filters(Mallat:89). The equivalence between this continuous time wavelet theory and discrete filter banks led to a new fruitfulinterface between digital signal processing and harmonic analysis, first creating a culture shock that is now well resolved.

Continuous versus discrete and finite

Originally, many signal processing engineers were wondering what is the point of considering wavelets and signals as functions,since all computations are performed over discrete signals with conjugate mirror filters.Why bother with the convergence of infinite convolution cascades if in practicewe only compute a finite number of convolutions? Answering these important questions is necessary in orderto understand why this book alternates between theorems on continuous time functions and discrete algorithms applied tofinite sequences.

A short answer would be “simplicity.” In ${\mathbf{L}}^{\mathbf{2}}\left(\mathbb{R}\right)$ , a wavelet basis is constructedby dilating and translating a singlefunction ψ . Several important theorems relatethe amplitude of wavelet coefficients to the local regularity of the signal $f$ . Dilations are not defined over discrete sequences, anddiscrete wavelet bases are therefore more complex to describe. The regularity of a discrete sequence is not well defined either, whichmakes it more difficult to interpret the amplitude of wavelet coefficients. A theory ofcontinuous-time functions gives asymptotic results for discrete sequences with samplingintervals decreasing to zero. This theory is useful because these asymptotic results are precise enough to understand thebehavior of discrete algorithms.

But continuous time or space models are not sufficient for elaborating discrete signal-processing algorithms.The transition between continuous and discrete signals must be done with great care to maintain important properties such as orthogonality.Restricting the constructions to finite discrete signals adds another layer of complexity because of border problems.How these border issues affect numerical implementations is carefully addressed once the properties of the bases are thoroughlyunderstood.

Wavelets for images

Wavelet orthonormal bases of images can be constructed from wavelet orthonormal bases of one-dimensional signals.Three mother wavelets ${\psi }^1\left(x\right)$ , ${\psi }^2\left(x\right)$ , and ${\psi }^3\left(x\right)$ , with $x=(x_1,x_2)\in {\mathbb{R}}^2$ , are dilated by $2^j$ and translated by $2^{j}n$ with $n=(n_1,n_2)\in {\mathbb{Z}}^2$ . This yields an orthonormal basisof the space ${\mathbf{L}}^{\mathbf{2}}\left({\mathbb{R}}^2\right)$ of finite energy functions $f\left(x\right)=f(x_1,x_2)$ :

The support of a wavelet ${\psi }_{j,n}^k$ is a square of width proportional to the scale $2^j$ .Two-dimensional wavelet bases are discretized to define orthonormal bases of images including N pixels. Wavelet coefficients are calculated with the fast $O\left(N\right)$ algorithm described in Chapter 7.

Like in one dimension, a wavelet coefficient $⟨f,{\psi }_{j,n}^k⟩$ has a small amplitude if $f\left(x\right)$ is regular over the support of ${\psi }_{j,n}^k$ . It has a large amplitude near sharp transi-tions such as edges.Figure (b) is the array of N wavelet coefficients. Each direction k and scale $2^j$ corresponds to a subimage, which shows in black the position of the largest coefficientsabove a threshold: $|⟨f,{\psi }_{j,n}^k⟩|\ge T$ .