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<#7313,#shensa<#7314]. One assumes that the sampled data are the scalar products at pixels k of the function f(x) with a scaling function which corresponds to a low pass filter.

The first filtering is then performed by a twice magnified scale leading to the set. The signal difference contains the information between these two scales and is the discrete set associated with the wavelet transform corresponding to . The associated wavelet is therefore .

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:

and the discrete wavelet transform w_i(k) by:

The coefficients derive from the scaling function :

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.

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

  

Figure 14.5: linear interpolation

we have:

c₁ is obtained by:

and c_j+1 is obtained from c_j by:

The figure 14.6 shows the wavelet associated to the scaling function.

  

Figure 14.6: Wavelet

The wavelet coefficients at the scale j are:

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

At each scale j, we obtain a set (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 (), and in two dimensions: