0.3 Fast wavelet transform

One-dimensional wavelet transform

Suppose we are given as signal the projection of a function onto the space $V_{j+1}$ :

Using the dual refinement equations, we have:

where the coefficients $s_{jk}$ are called scaling coefficients , since they are related to scaling functions. Similarly, the wavelet or detail coefficients $d_{jk}$ are obtained as

The coefficients $s_{jk}$ and $d_{jk}$ are obtained from $s_{j+1,l}$ by `moving average' schemes, using the filter coefficients $\left\{{\tilde{h}}_l\right\}$ and $\left\{{\tilde{g}}_l\right\}$ as `weights', with the exception that these moving averages are sampled only at the even integers, i.e. a downsampling is performed. Such transform allows, once we have computed $s_{J,k}$ $=〈f,,,,{\tilde{\varphi }}_{J,k}〉$ for a fine level $J\in \mathbb{N}$ , to compute $s_{jk}$ and $d_{jk}$ for all coarser levels $j<J$ without evaluating the integrals.

Suppose now we are given the values of $f$ at $n=2^J$ equispaced design points. The scaling functions ${\tilde{\varphi }}_{J,k},k=0,...,2^J-1$ , are compactly supported and localized around $2^{-J}k$ . Hence the coefficients $〈f,,,,{\tilde{\varphi }}_{J,k}〉$ are weighted and scaled average of $f$ on a neighborhood of $2^{-J}k$ which becomes smaller as $J$ tends to infinity. Consequently, it makes sense to replace the integral $〈f,,,,{\tilde{\varphi }}_{J,k}〉$ by the (scaled) value of $f$ at $2^{-J}k$ . More complicate quadrature formulae have been developedin [link] , [link] , [link] .

With $s_j:=\{s_{jk};k=0,...,2^j-1\}$ and $d_j:=\{d_{jk};k=0,...,2^j-1\}$ , the forward (or analyzing) wavelet transform given by [link] - [link] can be rewritten as

where ${\tilde{H}}_j^{*}$ denotes the Hermitian conjugate of ${\tilde{H}}_j$ .

The inverse (or synthesis) transform is found by using the primal refinement equations and the fact that $V_{j+1}=V_j\oplus W_j$ .

from which it follows that

In matrix form, we have

In the finite and classical setting, the matrices $H_j$ , $G_j$ , ${\tilde{H}}_j$ and ${\tilde{G}}_j$ are of size $2^{j+1}\times 2^j$ . Moreover, if the basis functions are compactly supported, the four filters ( $h_l$ , $g_l$ , ${\tilde{h}}_l$ , ${\tilde{g}}_l$ ) have only a finite number of nonzero elements, and hence all these matrices are banded.

Example: haar wavelet transform

In case of the orthogonal Haar transform, ${\tilde{H}}_j^{*}=H_j^{*}$ and is of the form

since only $h_0$ and $h_1$ are different from zero : $h_0=h_1=1/\sqrt{2}$ . The high-pass filter $\left\{g_l\right\}$ is such that $g_0=-1/\sqrt{2}$ and $g_1=1/\sqrt{2}$ . The forward transform [link] - [link] reduces to

and the reconstruction is given by

Two-dimensional wavelet transform

The wavelet transform has been successfully applied to compress images, which are modelled as functions defined on a regular two-dimensional grid.

The easiest way to build a two-dimensional MRA is probably to use tensor products of spaces, see [link] , [link] . In terms of wavelet transforms, this leads to applying two times a one-dimensional transform: first on the `row' of the signal matrix $S_J$ , and second on the `columns' of the resulting two matrices, see [link] . In this figure, we see that, at each level of the decomposition, three types of detail coefficients are produced: $D_j^h$ , $D_j^v$ and $D_j^d$ . These superscripts recall that, in an image, horizontal edges will lead to large values of $D_j^h$ , vertical edges will show up in $D_j^v$ and $D_j^d$ will be sensitive to diagonal lines.

However, such a transform is not able to compress efficiently an image that contains curves. More complex bidimensional bases are now proposed in the literature to better model discontinuities along curves, see forexample [link] , [link] , [link] , [link] .