next up previous contents
Next: The à trous algorithm Up: The discrete wavelet transform Previous: Introduction

   
Multiresolution Analysis

Multiresolution analysis [25] results from the embedded subsets generated by the interpolations at different scales.

A function f(x) is projected at each step j onto the subset Vj. This projection is defined by the scalar product cj(k) of f(x) with the scaling function $\phi(x)$ which is dilated and translated:

$\displaystyle c_j(k)=<f(x),2^{-j}\phi( 2^{-j}x-k)>$     (14.9)

As $\phi(x)$ is a scaling function which has the property:
 
$\displaystyle {1 \over 2} \phi({x \over 2}) = \sum_n h(n) \phi(x-n)$     (14.10)

or
$\displaystyle \hat{\phi}(2\nu)=\hat h(\nu)\hat{\phi}(\nu)$     (14.11)

where $\hat h(\nu)$ is the Fourier transform of the function $\sum_n
h(n)\delta(x-n)$. We get:
$\displaystyle \hat h(\nu)=\sum_n h(n)e^{-2\pi n \nu}$     (14.12)

Equation 14.10 permits to compute directly the set cj+1(k) from cj(k). If we start from the set c0(k) we compute all the sets cj(k), with j>0, without directly computing any other scalar product:
$\displaystyle c_{j+1}(k)=\sum_n h(n-2 k)c_{j}(n)$     (14.13)

At each step, the number of scalar products is divided by 2. Step by step the signal is smoothed and information is lost. The remaining information can be restored using the complementary subspace Wj+1 of Vj+1 in Vj. This subspace can be generated by a suitable wavelet function $\psi(x)$ with translation and dilation.

$\displaystyle {1 \over 2}\psi({x\over 2})=\sum_n g(n)\phi(x-n)$     (14.14)

or
$\displaystyle \hat{\psi}(2\nu)=\hat{g}(\nu)\hat{\phi}(\nu)$     (14.15)

We compute the scalar products $<f(x),2^{-(j+1)}\psi(2^{-(j+1)} x-k)>$ with:

$\displaystyle w_{j+1}(k)=\sum_n g(n-2k)c_{j}(n)$     (14.16)

With this analysis, we have built the first part of a filter bank [34]. In order to restore the original data, Mallat uses the properties of orthogonal wavelets, but the theory has been generalized to a large class of filters [8] by introducing two other filters $\tilde h$ and $\tilde g$ named conjugated to h and g. The restoration is performed with:

$\displaystyle c_{j}(k)=2\sum_l [c_{j+1}(l)\tilde h(k+2l)+w_{j+1}(l)\tilde g(k+2l)]$     (14.17)

In order to get an exact restoration, two conditions are required for the conjugate filters:


  
Figure 14.3: The filter bank associated with the multiresolution analysis
\begin{figure}
\centerline{
\hbox{
\psfig{figure=fig_paper_3.ps,bbllx=3.5cm,bblly=9cm,bburx=18cm,bbury=22.5cm,height=10
cm,width=14cm,clip=}
}}
\end{figure}

In the decomposition, the function is successively convolved with the two filters H (low frequencies) and G (high frequencies). Each resulting function is decimated by suppression of one sample out of two. The high frequency signal is left, and we iterate with the low frequency signal (upper part of figure 14.3). In the reconstruction, we restore the sampling by inserting a 0 between each sample, then we convolve with the conjugate filters $\tilde H$ and $\tilde G$, we add the resulting functions and we multiply the result by 2. We iterate up to the smallest scale (lower part of figure 14.3).

Orthogonal wavelets correspond to the restricted case where:

$\displaystyle \hat g(\nu)$ = $\displaystyle e^{-2\pi\nu}\hat h^*(\nu+{1\over 2})$ (14.20)
$\displaystyle \hat{\tilde h}(\nu)$ = $\displaystyle \hat h^*(\nu)$ (14.21)
$\displaystyle \hat{\tilde g}(\nu)$ = $\displaystyle \hat g^*(\nu)$ (14.22)

and
$\displaystyle \mid \hat h(\nu) \mid^2+ \mid \hat h(\nu+{1\over 2} \mid^2=1$     (14.23)

We can easily see that this set satisfies the two basic relations 14.18 and 14.19. Daubechies wavelets are the only compact solutions. For biorthogonal wavelets [8] we have the relations:
$\displaystyle \hat g(\nu)$ = $\displaystyle e^{-2\pi\nu}\hat{\tilde h}^*(\nu+{1\over 2})$ (14.24)
$\displaystyle \hat{\tilde g}(\nu)$ = $\displaystyle e^{2\pi\nu}\hat h^*(\nu+{1\over 2})$ (14.25)

and
$\displaystyle \hat h(\nu)\hat{\tilde h}(\nu)+\hat h^*(\nu+{1\over 2})
\hat{\tilde h}^*(\nu+{1\over 2})=1$     (14.26)

We also satisfy relations 14.18 and 14.19. A large class of compact wavelet functions can be derived. Many sets of filters were proposed, especially for coding. It was shown [9] that the choice of these filters must be guided by the regularity of the scaling and the wavelet functions. The complexity is proportional to N. The algorithm provides a pyramid of N elements.

The 2D algorithm is based on separate variables leading to prioritizing of x and y directions. The scaling function is defined by:

$\displaystyle \phi(x,y) = \phi(x)\phi(y)$     (14.27)

The passage from a resolution to the next one is done by:
$\displaystyle f_{j+1}(k_x,k_y) = \sum_{l_x=-\infty}^{+\infty} \sum_{l_y=-\infty}^{+\infty}
h(l_x- 2k_x) h(l_y -2k_y) f_{j}(l_x,l_y)$     (14.28)

The detail signal is obtained from three wavelets: which leads to three sub-images:

\begin{displaymath}C_{j+1}^1 (k_x, k_y) = \sum_{l_x=-\infty}^{+\infty} \sum_{l_y=-\infty}^{+\infty}
g(l_x- 2k_x) h(l_y -2k_y) f_{j}(l_x,l_y)\end{displaymath}


\begin{displaymath}C_{j+1}^2 (k_x, k_y) = \sum_{l_x=-\infty}^{+\infty} \sum_{l_y=-\infty}^{+\infty}
h(l_x- 2k_x) g(l_y -2k_y) f_{j}(l_x,l_y)\end{displaymath}


\begin{displaymath}C_{j+1}^3 (k_x, k_y) = \sum_{l_x=-\infty}^{+\infty} \sum_{l_y=-\infty}^{+\infty}
g(l_x- 2k_x) g(l_y -2k_y) f_{j}(l_x,l_y)\end{displaymath}


  
Figure 14.4: Wavelet transform representation of an image
\begin{figure}
\centerline{
\hbox{
\psfig{figure=fig_mallat3.ps,bbllx=5.5cm,bblly=9.5cm,bburx=16cm,bbury=20cm,height=8cm,width=8cm,clip=}
}}
\end{figure}

The wavelet transform can be interpreted as the decomposition on frequency sets with a spatial orientation.


next up previous contents
Next: The à trous algorithm Up: The discrete wavelet transform Previous: Introduction
Petra Nass
1999-06-15