Dealing with Border Distortion

Classically, the DWT is defined for sequences with length of some power of 2, and different ways of extending samples of other sizes are needed. Methods for extending the signal include zero-padding, smooth padding, periodic extension, and boundary value replication (symmetrization).

The basic algorithm for the DWT is not limited to dyadic length and is based on a simple scheme: convolution and downsampling. As usual, when a convolution is performed on finite-length signals, border distortions arise.

Signal Extensions: Zero-Padding, Symmetrization,
and Smooth Padding

To deal with border distortions, the border should be treated differently from the other parts of the signal.

Various methods are available to deal with this problem, referred to as "wavelets on the interval" (see [CohDJV93] in References). These interesting constructions are effective in theory but are not entirely satisfactory from a practical viewpoint.

Often it is preferable to use simple schemes based on signal extension on the boundaries. This involves the computation of a few extra coefficients at each stage of the decomposition process to get a perfect reconstruction. It should be noted that extension is needed at each stage of the decomposition process.

Details on the rationale of these schemes are in Chapter 8 of the book Wavelets and Filter Banks, by Strang and Nguyen (see [StrN96] in References).

The available signal extension modes are as follows (see dwtmode):

• Zero-padding ('zpd'): This method is used in the version of the DWT given in the previous sections and assumes that the signal is zero outside the original support.

• The disadvantage of zero-padding is that discontinuities are artificially created at the border.

• Symmetrization ('sym'): This method assumes that signals or images can be recovered outside their original support by symmetric boundary value replication.

• It is the default mode of the wavelet transform in the toolbox.

  Symmetrization has the disadvantage of artificially creating discontinuities of the first derivative at the border, but this method works well in general for images.

• Smooth padding of order 1 ('spd' or 'sp1'): This method assumes that signals or images can be recovered outside their original support by a simple first-order derivative extrapolation: padding using a linear extension fit to the first two and last two values.

• Smooth padding works well in general for smooth signals.

• Smooth padding of order 0 ('sp0'): This method assumes that signals or images can be recovered outside their original support by a simple constant extrapolation. For a signal extension this is the repetition of the first value on the left and last value on the right.
• Periodic-padding (1) ('ppd'): This method assumes that signals or images can be recovered outside their original support by periodic extension.

• The disadvantage of periodic padding is that discontinuities are artificially created at the border.

The DWT associated with these five modes is slightly redundant. But IDWT ensures a perfect reconstruction for any of the five previous modes whatever the extension mode used for DWT.

• Periodic-padding (2) ('per'): If the signal length is odd, the signal is first extended by adding an extra-sample equal to the last value on the right. Then a minimal periodic extension is performed on each side. The same kind of rule exists for images. This extension mode is used for SWT (1-D & 2-D).

This last mode produces the smallest length wavelet decomposition. But the extension mode used for IDWT must be the same to ensure a perfect reconstruction.

Before looking at an illustrative example, let us compare some properties of the theoretical Discrete Wavelet Transform versus the actual DWT.

The theoretical DWT is applied to signals that are defined on an infinite length time interval (Z). For an orthogonal wavelet, this transform has the following desirable properties:

1. Norm preservation

1. Let cA and cD be the approximation and detail of the DWT coefficients of an infinite length signal X. Then the l²-norm is preserved:

• 

2. Orthogonality

1. Let A and D be the reconstructed approximation and detail. Then, A and D are orthogonal and

• 

3. Perfect reconstruction

1. X = A + D

Since the DWT is applied to signals that are defined on a finite-length time interval, extension is needed for the decomposition, and truncation is necessary for reconstruction.

To ensure the crucial property 3 (perfect reconstruction) for arbitrary choices of

• The signal length
• The wavelet
• The extension mode

the properties 1 and 2 can be lost. These properties hold true for an extended signal of length usually larger than the length of the original signal. So only the perfect reconstruction property is always preserved. Nevertheless if the DWT is performed using the periodic extension mode ('per') and if the length of the signal is divisible by 2^J, where J is the maximum level decomposition, the properties 1, 2, and 3 remain true.

It is interesting to notice that if arbitrary extension is used, and decomposition performed using the convolution-downsampling scheme, perfect reconstruction is recovered using idwt or idwt2. This point is illustrated below.

• % Set initial signal and get filters.
  x = sin(0.3*[1:451]); w = 'db9';
  [Lo_D,Hi_D,Lo_R,Hi_R] = wfilters(w);
  % In fact using a slightly redundant scheme, any signal
  % extension strategy works well. 
  % For example use random padding.
  
  
  lx = length(x); lf = length(Lo_D);
  randn('seed',654);
  ex = [randn(1,lf) x randn(1,lf)];
  axis([1 lx+2*lf -2 3])
  subplot(211), plot(lf+1:lf+lx,x), title('Original signal')
  axis([1 lx+2*lf -2 3])
  subplot(212), plot(ex), title('Extended signal')
  axis([1 lx+2*lf -2 3])
  
  % Decomposition.
  la = floor((lx+lf-1)/2);
  ar = wkeep(dyaddown(conv(ex,Lo_D)),la);
  dr = wkeep(dyaddown(conv(ex,Hi_D)),la);
  % Reconstruction.
  xr = idwt(ar,dr,w,lx);
  
  % Check perfect reconstruction.
  err0 = max(abs(x-xr))
  
  err0 = 
      3.0464e-11
  

Now let us illustrate the differences between the first three methods both for 1-D and 2-D signals.

Zero-Padding.   

Using the GUI we will examine the effects of zero-padding.

1. From the MATLAB^® prompt, type

• dwtmode('zpd')
  

2. From the MATLAB prompt, type wavemenu.

1. The Wavelet Toolbox Main Menu appears.

3. Click the Wavelet 1-D menu item.The discrete wavelet analysis tool for one-dimensional signal data appears.
4. From the File menu, choose the Example Analysis option and select Basic Signals > with db2 at level 5 > Two nearby discontinuities.
5. Select Display Mode: Show and Scroll.

• The detail coefficients clearly show the signal end effects.

  

Symmetric Extension.   

6. From the MATLAB prompt, type

• dwtmode('sym')
  

7. Click the Wavelet 1-D menu item.

1. The discrete wavelet analysis tool for one-dimensional signal data appears.

8. From the File menu, choose the Example Analysis option and select Basic Signals >\9 with db2 at level 5 > Two nearby discontinuities.
9. Select Display Mode: Show and Scroll.

1. The detail coefficients show the signal end effects are present, but the discontinuities are well detected.

   

Smooth Padding.   

10. From the MATLAB prompt, type

• dwtmode('spd')
  

11. Click the Wavelet 1-D menu item.

1. The discrete wavelet analysis tool for one-dimensional signal data appears.

12. From the File menu, choose the Example Analysis option and select Basic Signals >\9 with db2 at level 5 --> Two nearby discontinuities.
13. Select Display Mode: Show and Scroll.

1. The detail coefficients show the signal end effects are not present, and the discontinuities are well detected.

   

Let us now consider an image example.

Original Image.   

1. From the MATLAB prompt, type

• load geometry;
  % X contains the loaded image and 
  % map contains the loaded colormap. 
  nbcol = size(map,1);
  colormap(pink(nbcol));
  image(wcodemat(X,nbcol));
  
   
  

Zero-Padding.   

Now we set the extension mode to zero-padding and perform a decomposition of the image to level 3 using the sym4 wavelet. Then we reconstruct the approximation of level 3.

2. From the MATLAB prompt, type

• lev = 3; wname = 'sym4';
  dwtmode('zpd')
  [c,s] = wavedec2(X,lev,wname);
  a = wrcoef2('a',c,s,wname,lev);
  image(wcodemat(a,nbcol));
  
  
  

Symmetric Extension.   

Now we set the extension mode to symmetric extension and perform a decomposition of the image again to level 3 using the sym4 wavelet. Then we reconstruct the approximation of level 3.

3. From the MATLAB prompt, type

• dwtmode('sym')
  [c,s] = wavedec2(X,lev,wname);
  a = wrcoef2('a',c,s,wname,lev);
  image(wcodemat(a,nbcol));
  
  
  

Smooth Padding.   

Now set the extension mode to smooth padding and perform a decomposition of the image again to level 3 using the sym4 wavelet. Then reconstruct the approximation of level 3.

4. From the MATLAB prompt, type

• dwtmode('spd')
  [c,s] = wavedec2(X,lev,wname);
  a = wrcoef2('a',c,s,wname,lev);
  image(wcodemat(a,nbcol));
  

Provide feedback about this page

Fast Wavelet Transform (FWT) Algorithm

Discrete Stationary Wavelet Transform (SWT)

© 1984-2009- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS