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)$.

$$\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, c_i(k) is given by:

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

and the discrete wavelet transform w_i(k) by:

w_i(k) = c_i-1(k) - c_i(k) (14.31)

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

$$\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 c_np is added to all the differences w_i.

 

$$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{array}{ll} \phi(x) = 1 - \mid x \mid & \mbox{ if } x \... ...,1] \\ \phi(x) = 0 & \mbox{ if } x \not \in [-1,1] \end{array}$$

  

Figure 14.5: linear interpolation $\phi$

we have:

$$\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)

c₁ is obtained by:

$$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 c_j+1 is obtained from c_j by:

$$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$

The wavelet coefficients at the scale j are:

$$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:

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

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 B₃-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:

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