Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members

# polyHaar Class Template Reference

This class implements the wavelet Lifting Scheme with polynomial interpolation. More...

`#include <polyHaar.h>`

Inheritance diagram for polyHaar::

List of all members.

## Public Methods

polyHaar ()
polyHaar class constructor. More...

~polyHaar ()
polyHaar (const polyHaar &rhs)
void forwardStep (T &vec, const int n)
One step in the forward wavelet transform. More...

virtual void inverseStep (T &vec, const int n)
One inverse wavelet transform step. More...

## Protected Methods

void update (T &vec, int N, transDirection direction)
The update step of the wavelet Lifting Scheme. More...

void interp (T &vec, int N, transDirection direction)
<. More...

void predict (T &vec, int N, transDirection direction)
Predict step of the wavelet Lifting Scheme. More...

## Private Types

enum  bogus { numPts = 4 }

## Private Methods

void fill (T &vec, double d[], int N, int start)
Copy four points or N (which ever is less) data points from vec into d These points are the "known" points used in the polynomial interpolation. More...

## Private Attributes

polyinterp fourPtInterp

## Detailed Description

### template<class T> class polyHaar

This class implements the wavelet Lifting Scheme with polynomial interpolation.

This version of wavelets is based on Wim Sweldens' tutorial paper Building Your Own Wavelets at Home. This tutorial was presented at SIGGraph. The tutorial is available on the Web.

One of the attractive features of Lifting Scheme wavelets is that the transform and the inverse transform are exact mirrors of each other. To arrive at the inverse transform the order of the operations is reversed and subtraction and addition operations are exchanged. This allows a generic Lifting Scheme base class to be constructed, where the ordering is defined by the sub-classes.

Definition at line 59 of file polyHaar.h.

## Member Enumeration Documentation

 template enum polyHaar::bogus` [private]`

Enumeration values:
 numPts

Definition at line 71 of file polyHaar.h.

```00071 { numPts = 4 } bogus;
```

## Constructor & Destructor Documentation

 template polyHaar::polyHaar ( )` [inline]`
 polyHaar class constructor. Definition at line 65 of file polyHaar.h.```00065 {} ```

 template polyHaar::~polyHaar ( )` [inline]`
 Definition at line 66 of file polyHaar.h.```00066 {} ```

 template polyHaar::polyHaar ( const polyHaar & rhs )

## Member Function Documentation

 template void polyHaar::fill ( T & vec, double d[], int N, int start )` [inline, private]`

Copy four points or N (which ever is less) data points from vec into d These points are the "known" points used in the polynomial interpolation.

Parameters:
 vec [] the input data set on which the wavelet is calculated d [] an array into which N data points, starting at start are copied. N the number of polynomial interpolation points start the index in vec from which copying starts

Definition at line 85 of file polyHaar.h.

Referenced by interp().

```00086   {
00087     int n = numPts;
00088     if (n > N)
00089       n = N;
00090     int end = start + n;
00091     int j = 0;
00092
00093     for (int i = start; i < end; i++) {
00094       d[j] = vec[i];
00095       j++;
00096     }
00097   } // fill
```

 template void polyHaar::forwardStep ( T & vec, const int n )` [inline, virtual]`
 One step in the forward wavelet transform. Reimplemented from liftbase. Definition at line 274 of file polyHaar.h.```00275 { 00276 split( vec, n ); 00277 predict( vec, n, forward ); 00278 update( vec, n, forward ); 00279 interp( vec, n, forward ); 00280 } // forwardStep ```

 template void polyHaar::interp ( T & vec, int N, transDirection direction )` [inline, protected]`

<.

p> Predict an odd point from the even points, using 4-point polynomial interpolation.

The four points used in the polynomial interpolation are the even points. We pretend that these four points are located at the x-coordinates 0,1,2,3. The first odd point interpolated will be located between the first and second even point, at 0.5. The next N-3 points are located at 1.5 (in the middle of the four points). The last two points are located at 2.5 and 3.5. For complete documentation see

```
http://www.bearcave.com/misl/misl_tech/wavelets/lifting/index.html
```

The difference between the predicted (interpolated) value and the actual odd value replaces the odd value in the forward transform.

As the recursive steps proceed, N will eventually be 4 and then 2. When N = 4, linear interpolation is used. When N = 2, Haar interpolation is used (the prediction for the odd value is that it is equal to the even value).

Parameters:
 vec the input data on which the forward or inverse transform is calculated. N the area of vec over which the transform is calculated direction forward or inverse transform

Definition at line 175 of file polyHaar.h.

Referenced by forwardStep(), and inverseStep().

```00176   {
00177     int half = N >> 1;
00178     double d[4];
00179
00180     for (int i = 0; i < half; i++) {
00181       double predictVal;
00182
00183       if (i == 0) {
00184         if (half == 1) {
00185           // e.g., N == 2, and we use Haar interpolation
00186           predictVal = vec[0];
00187         }
00188         else {
00189           fill( vec, d, N, 0 );
00190           predictVal = fourPtInterp.interpPoint( 0.5, half, d );
00191         }
00192       }
00193       else if (i == 1) {
00194         predictVal = fourPtInterp.interpPoint( 1.5, half, d );
00195       }
00196       else if (i == half-2) {
00197         predictVal = fourPtInterp.interpPoint( 2.5, half, d );
00198       }
00199       else if (i == half-1) {
00200         predictVal = fourPtInterp.interpPoint( 3.5, half, d );
00201       }
00202       else {
00203         fill( vec, d, N, i-1);
00204         predictVal = fourPtInterp.interpPoint( 1.5, half, d );
00205       }
00206
00207       int j = i + half;
00208       if (direction == forward) {
00209         vec[j] = vec[j] - predictVal;
00210       }
00211       else if (direction == inverse) {
00212         vec[j] = vec[j] + predictVal;
00213       }
00214       else {
00216         break;
00217       }
00218     } // for
00219   } // interp
```

 template void polyHaar::inverseStep ( T & vec, const int n )` [inline, virtual]`
 One inverse wavelet transform step. Reimplemented from liftbase. Definition at line 282 of file polyHaar.h.```00283 { 00284 interp( vec, n, inverse ); 00285 update( vec, n, inverse ); 00286 predict( vec, n, inverse ); 00287 merge( vec, n ); 00288 } ```

 template void polyHaar::predict ( T & vec, int N, transDirection direction )` [inline, protected, virtual]`
 Predict step of the wavelet Lifting Scheme. The term "predict" comes from Building Your Own Wavelets at Home. transform In the wavelet transform, calculate the difference between even and odd element pairs. This is a slightly modified version of the classic haar difference. If the even elements are labeled as a and the odd elements are labeled as b (where we start counting at zero) the difference is simply ``` di = bi - ai ``` Since an "in-place" algorithm is used, where we update the odd elements with the difference, we get ``` bi = bi - ai ``` inverse transform Reverse the transform predict step by adding the average (even element) to the difference (odd element). Reimplemented from liftbase. Definition at line 251 of file polyHaar.h.```00252 { 00253 int i; 00254 int half = N >> 1; 00255 int j = 0; 00256 for (i = half; i < N; i++) { 00257 if (direction == forward) { // forward transform stage 00258 vec[i] = vec[i] - vec[j]; 00259 } 00260 else if (direction == inverse ) { // inverse transform stage 00261 vec[i] = vec[i] + vec[j]; 00262 } 00263 else { 00264 printf("predict: bad direction\n"); 00265 break; 00266 } 00267 j++; 00268 } 00269 } // predict ```

 template void polyHaar::update ( T & vec, int N, transDirection direction )` [inline, protected, virtual]`
 The update step of the wavelet Lifting Scheme. transform In the Lifting Scheme transform the update step follows the predict step. After the predict step, the differences have been calculated in-place writing over the even (b) values. The update step calculates the Haar average using an even/odd pair. The average is placed in the even member of the pair. Reimplemented from liftbase. Definition at line 115 of file polyHaar.h.```00116 { 00117 int i; 00118 int half = N >> 1; 00119 int j = half; 00120 for (i = 0; i < half; i++) { 00121 if (direction == forward) { // forward transform stage 00122 vec[i] = vec[i] + (vec[j]/2.0); 00123 } 00124 else if (direction == inverse) { // inverse transform step 00125 vec[i] = vec[i] - (vec[j]/2.0); 00126 } 00127 else { 00128 printf("update: bad direction value\n"); 00129 break; 00130 } 00131 j++; 00132 } // for 00133 } // update ```

## Member Data Documentation

 template polyinterp polyHaar::fourPtInterp` [private]`
 Definition at line 72 of file polyHaar.h.

The documentation for this class was generated from the following file:
Generated at Sun Aug 18 16:56:42 2002 for Wavelet Spectral Analysis by 1.2.8.1 written by Dimitri van Heesch, © 1997-2001