Wavelet Toolbox

Why Does Such an Algorithm Exist?

The previous paragraph describes algorithms designed for finite-length signals or images. To understand the rationale, we must consider infinite-length signals. The methods for the extension of a given finite-length signal are described in the section Dealing with Border Distortion.

Let us denote h = Lo_R and g = Hi_R and focus on the one-dimensional case.

We first justify how to go from level j to level j+1, for the approximation vector. This is the main step of the decomposition algorithm for the computation of the approximations. The details are calculated in the same way using the filter g instead of filter h.

Let be the coordinates of the vector A_j:

and the coordinates of the vector A_j+1:

is calculated using the formula

This formula resembles a convolution formula.

The computation is very simple.

Let us define

The sequence is the filtered output of the sequence by the filter .

We obtain

We have to take the even index values of F. This is downsampling.

The sequence is the downsampled version of the sequence .

The initialization is carried out using , where s(k) is the signal value at time k.

There are several reasons for this surprising result, all of which are linked to the multiresolution situation and to a few of the properties of the functions _j,k and _j,k.

Let us now describe some of them.

1. The family is formed of orthonormal functions. As a consequence for any j, the family is orthonormal.
2. The double indexed family is orthonormal.
3. For any j, the are orthogonal to .
4. Between two successive scales, we have a fundamental relation, called the twin-scale relation.
   
   

   Twin-Scale Relation for

This relation introduces the algorithm's h filter (). For more information, see the section Filters Used to Calculate the DWT and IDWT.

5. We check that
1. The coordinate of on _j,k is and does not depend on j.
2. The coordinate of on _j,k is equal to .
6. These relations supply the ingredients for the algorithm.
7. Up to now we used the filter h. The high-pass filter g is used in the twin scales relation linking the and functions. Between two successive scales, we have the following twin-scale fundamental relation.
   
   

   Twin-Scale Relation Between and

8. After the decomposition step, we justify now the reconstruction algorithm by building it. Let us simplify the notation. Starting from A₁ and D₁, let us study A₀ = A₁ + D₁. The procedure is the same to calculate A_j = A_j+1 + D_j+1.

1. Let us define _n, _n, by

1. Let us assess the coordinates as

We will focus our study on the first sum

; the second sum

is handled in a similar manner.

The calculations are easily organized if we note that (taking k = 0 in the previous formulas, makes things simpler)

If we transform the (_n) sequence into a new sequence defined by

      ..., _-1, 0, ₀, 0, ₁, 0, ₂, 0, ... that is precisely

Then

and by extension

Since

the reconstruction steps are

1. Replace the and sequences by upsampled versions and inserting zeros.
2. Filter by h and g respectively.
3. Sum the obtained sequences.

Algorithms

One-Dimensional Wavelet Capabilities

© 1994-2005 The MathWorks, Inc.