next up previous contents
Next: Pyramidal Algorithm Up: The discrete wavelet transform Previous: Multiresolution Analysis

   
The à trous algorithm

The discrete approach of the wavelet transform can be done with the special version of the so-called à trous algorithm (with holes) [#holschn1<#14462,#shensa<#14463]. One assumes that the sampled data $\{c_0(k)\}$ are the scalar products at pixels k of the function f(x) with a scaling function $\phi(x)$ which corresponds to a low pass filter.

The first filtering is then performed by a twice magnified scale leading to the $\{c_1(k)\}$ set. The signal difference $\{c_0(k)\} -
\{c_1(k)\}$ contains the information between these two scales and is the discrete set associated with the wavelet transform corresponding to $\phi(x)$. The associated wavelet is therefore $\psi(x)$.

$\displaystyle \frac{1}{2}\psi(\frac{x}{2}) = \phi(x) - \frac{1}{2}\phi(\frac{x}{2})$     (14.29)

The distance between samples increasing by a factor 2 from the scale (i-1) (i > 0) to the next one, ci(k) is given by:


$\displaystyle c_i(k) = \sum_l h(l) c_{i-1} (k+2^{i-1}l)$     (14.30)

and the discrete wavelet transform wi(k) by:

wi(k) = ci-1(k) - ci(k)     (14.31)

The coefficients $\{h(k)\}$ derive from the scaling function $\phi(x)$:

$\displaystyle \frac{1}{2}\phi(\frac{x}{2}) = \sum_l h(l) \phi(x-l)$     (14.32)

The algorithm allowing one to rebuild the data frame is evident: the last smoothed array cnp is added to all the differences wi.

 
$\displaystyle c_0(k) = c_{n_p}(k) \sum_{j=1}^{n_p} w_j(k)$     (14.33)

If we choose the linear interpolation for the scaling function $\phi$(see figure 14.5):

\begin{displaymath}\begin{array}{ll}
\phi(x) = 1 - \mid x \mid & \mbox{ if } x \...
...,1] \\
\phi(x) = 0 & \mbox{ if } x \not \in [-1,1]
\end{array}\end{displaymath}


  
Figure 14.5: linear interpolation $\phi$
\begin{figure}
\centerline{
\hbox{
\psfig{figure=fig_interp_linear.ps,bbllx=1cm,bblly=13.5cm,bburx=10.5cm,bbury=27cm,height=5cm,width=10cm,clip=}
}}
\end{figure}

we have:
$\displaystyle \frac{1}{2}\phi(\frac{x}{2}) = \frac{1}{4}\phi(x+1) + \frac{1}{2}\phi(x) + \frac{1}{4}\phi(x-1)$     (14.34)

c1 is obtained by:

$\displaystyle c_1(k) = \frac{1}{4} c_0(k-1) + \frac{1}{2} c_0(k) + \frac{1}{4} c_0(k+1)$     (14.35)

and cj+1 is obtained from cj by:
$\displaystyle c_{j+1}(k) = \frac{1}{4} c_j(k-2^j) + \frac{1}{2} c_j(k) + \frac{1}{4}
c_j(k+2^j)$     (14.36)

The figure 14.6 shows the wavelet associated to the scaling function.
  
Figure 14.6: Wavelet $\psi$
\begin{figure}
\centerline{
\hbox{
\psfig{figure=fig_wavelet_linear.ps,bbllx=1cm,bblly=13.5cm,bburx=10.5cm,bbury=27cm,height=5cm,width=10cm,clip=}
}}
\end{figure}

The wavelet coefficients at the scale j are:

$\displaystyle C_{j+1}(k) = -\frac{1}{4} c_j(k-2^j) + \frac{1}{2} c_j(k)
-\frac{1}{4} c_j(k+2^j)$     (14.37)

The above à trous algorithm is easily extensible to the two dimensional space. This leads to a convolution with a mask of $3 \times 3$ pixels for the wavelet connected to linear interpolation. The coefficents of the mask are:

\begin{displaymath}\left(\begin{array}{ccc}
\frac{1}{16} & \frac{1}{8} & \frac{...
...frac{1}{16} & \frac{1}{8} & \frac{1}{16}
\end{array}\right)
\end{displaymath}

At each scale j, we obtain a set $\{w_j(k,l)\}$ (we will call it wavelet plane in the following), which has the same number of pixels as the image.

If we choose a B3-spline for the scaling function, the coefficients of the convolution mask in one dimension are ( $\frac{1}{16},\frac{1}{4},\frac{3}{8},\frac{1}{4},\frac{1}{16}$), and in two dimensions:

\begin{displaymath}\left(\begin{array}{ccccc}
\frac{1}{256} & \frac{1}{64} & \fr...
...ac{3}{128} & \frac{1}{64} & \frac{1}{256}
\end{array}\right)
\end{displaymath}


next up previous contents
Next: Pyramidal Algorithm Up: The discrete wavelet transform Previous: Multiresolution Analysis
Petra Nass
1999-06-15