One-dimensional

Next: Two-dimensional Up: Fast wavelet transforms Previous: Fast wavelet transforms

One-dimensional

The (periodic) one-dimensional fast wavelet transform is implemented by the functions fwt1 and ifwt1. ³ Let H be the low-pass filter corresponding to the scaling function followed by down-sampling, G the high-pass filter corresponding to the wavelet (followed by down-sampling). Schematically the wavelet transform is shown in figure 2. The inverse transform essentially amounts to reversing the arrows and replacing H and G with their adjoints.

**Figure 2:** Wavelet transform

The output vector of fwt1 is partitioned as follows: let (h and g contain the filter coefficients of H and G. Then

        w = fwt1(f,h,g)

yields

$\begin{displaymath}w = [\; s_n \;\vert\; d_n \;\vert\; d_{n-1} \;\vert\; \cdots \;\vert\; d_2 \;\vert\; d_1 \;], \end{displaymath}$

where d₁ = Gf, d₂=GHf, d₂=GHHf, ..., $d_n=GH\cdots Hf$ , and $s_n=HH\cdots Hf$ . Here |d_i| = 2^-i |w|.

        FWT1 -- fast wavelet transform, one dimensional standard version
        
        w = fwt1(f,h,g)
        
        Input:
            f     Vector to transform
            h     Filter coefficients for the scaling function
            g     Filter coefficients for the wavelet
        
        Output:
            w     contains standard multiscale analysis (column vector)
        
        The wavelet coefficients are stored in the following order:
        
            w = [sn | dn | d(n-1) | d(n-2) | ... | d2 | d1 ]
        
        where length(sn) = 1, length(di) = 2^(-i)*length(w) and 
        n = log2(length(w)).
        
        See also IFWT1, FWT1NS, FWT2, FWT2TNS.

Inverse transform is computed by ifwt1:

        IFWT1 -- inverse fast wavelet transform, standard version
        
        result = ifwt1(msa, h, g)
        
        h  and  g  are the filter coefficients for the scaling function 
        and wavelet,  msa  is a standard multiscale analysis, e.g.,
        produced by fwt1.
        
        result  is the inverse transform.
        
        fwt1  followed by  ifwt1  is the identity.
        
        See also FWT1, IFWT1NS, FWT2TNS, IFWT2TNS.

Terminology:

The output of fwt1 is also called a multi-resolution analysis (msa).
The functions fwt1 and ifwt1 and the msa they produce are called ``standard'', to distinguish them from the functions and data-structures described in the section on the fast multiplication algorithm.

The following example computes the wavelet coefficients of the function 1/|x-0.5| on the interval [0,1] and displays the resulting multi-resolution analysis using showmsa. Finally the inverse transform is computed and compared to the original vector.

        [h,g] = wavecoef('dau',6);
        x = (0:1/511:1)';
        f = sqrt(1./abs(x-.5));
        w = fwt1(f,h,g);
        showmsa(w)
        g = ifwt1(w,h,g);
        norm(f-g)

The error was 1.40739e-13 . Here is the figure produced by showmsa:

The rows, from bottom to top, are bar plots of s_n, d_n, ..., d₁. Note how in finer levels the only significant coefficients are those near the singularity at 0.5 (but not exactly, since the wavelet is not centered at zero⁴).

Footnotes

...ifwt1. ³: The input vector must have length 2ⁿ.
... zero ⁴: This is really a bug in showmsa, it should take into account the location of the center of the filter. The function phasepln for wavelet packets is much better in this respect, see the section on wavelet packets and figure 7.

Next: Two-dimensional Up: Fast wavelet transforms Previous: Fast wavelet transforms

Harri Ojanen
1998-05-02