Wavelet Toolbox    

How to Calculate the -Decimated DWT: SWT

It is possible to calculate all the -decimated DWT for a given signal of length N, by computing the approximation and detail coefficients for every possible sequence . Do this using iteratively, a slightly modified version of the basic step of the DWT of the form

The last two arguments specify the way to perform the decimation step. This is the classical one for e = 0, but for e = 1 the odd indexed elements are retained by the decimation.

Of course, this is not a good way to calculate all the -decimated DWT, because many computations are performed many times. We shall now describe another way, which is the stationary wavelet transform (SWT).

The SWT algorithm is very simple and is close to the DWT one. More precisely, for level 1, all the -decimated DWT (only two at this level) for a given signal can be obtained by convolving the signal with the appropriate filters as in the DWT case but without downsampling. Then the approximation and detail coefficients at level 1 are both of size N, which is the signal length. This can be visualized in the following figure.

The general step j convolves the approximation coefficients at level j-1, with upsampled versions of the appropriate original filters, to produce the approximation and detail coefficients at level j. This can be visualized in the following figure.

Next, we illustrate how to extract a given -decimated DWT from the approximation and detail coefficients structure of the SWT.

We decompose a sequence of height numbers with the SWT, at level J = 3, using an orthogonal wavelet.

The function swt calculates successively the following arrays, where A(j,1,...,j) or D(j,1,...,j) denotes an approximation or a detail coefficient at level j obtained for the -decimated DWT characterized by = [1,...,j].

Step 0 (Original Data).   
A(0)
A(0)
A(0)
A(0)
A(0)
A(0)
A(0)
A(0)

Step 1.   
D(1,0)
D(1,1)
D(1,0)
D(1,1)
D(1,0)
D(1,1)
D(1,0)
D(1,1)
A(1,0)
A(1,1)
A(1,0)
A(1,1)
A(1,0)
A(1,1)
A(1,0)
A(1,1)

Step 2.   
D(1,0)
D(1,1)
D(1,0)
D(1,1)
D(1,0)
D(1,1)
D(1,0)
D(1,1)
D(2,0,0)
D(2,1,0)
D(2,0,1)
D(2,1,1)
D(2,0,0)
D(2,1,0)
D(2,0,1)
D(2,1,1)
A(2,0,0)
A(2,1,0)
A(2,0,1)
A(2,1,1)
A(2,0,0)
A(2,1,0)
A(2,0,1)
A(2,1,1)

Step 3.   
D(1,0)
D(1,1)
D(1,0)
D(1,1)
D(1,0)
D(1,1)
D(1,0)
D(1,1)
D(2,0,0)
D(2,1,0)
D(2,0,1)
D(2,1,1)
D(2,0,0)
D(2,1,0)
D(2,0,1)
D(2,1,1)
D(3,0,0,0)
D(3,1,0,0)
D(3,0,1,0)
D(3,1,1,0)
D(3,0,0,1)
D(3,1,0,1)
D(3,0,1,1)
D(3,1,1,1)
A(3,0,0,0)
A(3,1,0,0)
A(3,0,1,0)
A(3,1,1,0)
A(3,0,0,1)
A(3,1,0,1)
A(3,0,1,1)
A(3,1,1,1)

Let j denote the current level, where j is also the current step of the algorithm. Then we have the following abstract relations with i = 0 or 1:

where wshift performs a -circular shift of the input vector. Therefore, if j+1 = 0, the wshift instruction is ineffective and can be suppressed.

Let = [1,...,J] with i = 0 or 1. We have 2J = 23 = eight different -decimated DWTs at level 3. Choosing , we can retrieve the corresponding -decimated DWT from the SWT array.

Now, consider the last step, J = 3, and let [C,L] denote the wavelet decomposition structure of an -decimated DWT for a given . Then, it can be retrieved from the SWT decomposition structure by selecting the appropriate coefficients as follows:

C =

A(3, 1, 2, 3)
D(3, 1, 2, 3)
D(2, 1, 2)
D(2, 1, 2)
D(1, 1)
D(1, 1)
D(1, 1)
D(1, 1)

L = [1,1,2,4,8]

For example, the -decimated DWT corresponding to = [1, 2, 3] = [1,0,1] is shown in bold in the sequence of arrays of the previous example.

This can be extended to the 2-D case. The algorithm for the stationary wavelet transform for images is visualized in the following figure.


  -Decimated DWT Inverse Discrete Stationary Wavelet Transform (ISWT)