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

poly Class Template Reference

4-point polynomial interpolation wavelet. More...

#include <poly.h>

Inheritance diagram for poly::

liftbase List of all members.

Public Methods

 poly ()
 poly class constructor. More...

 ~poly ()
 poly (const poly &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 stage calculates the forward and inverse Haar scaling functions. More...

void predict (T &vec, int N, transDirection direction)
 Predict an odd point from the even points, using 4-point polynomial interpolation. 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 poly

4-point polynomial interpolation wavelet.

This wavelet transform uses a polynomial interpolation wavelet (e.g., the function used to calculate the differences). A Haar scaling function (the calculation of the average for the even points) is used.

This wavelet transform uses a two stage version of the lifting scheme. In the "classic" two stage Lifting Scheme wavelet the predict stage preceeds the update stage. Also, the algorithm is absolutely symetric, with only the operators (usually addition and subtraction) interchanged.

The problem with the classic Lifting Scheme transform is that it can be difficult to determine how to calculate the smoothing (scaling) function in the update phase once the predict stage has altered the odd values. This version of the wavelet transform calculates the update stage first and then calculates the predict stage from the modified update values. In this case the predict stage uses 4-point polynomial interpolation using even values that result from the update stage.

In this version of the wavelet transform the update stage is no longer perfectly symetric, since the forward and inverse transform equations differ by more than an addition or subtraction operator. However, this version of the transform produces a better result than the Haar transform extended with a polynomial interpolation stage.

This algorithm was suggested to me from my reading of Wim Sweldens' tutorial Building Your Own Wavelets at Home.

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

This code was originally implemented in Java and then ported to C++.

Definition at line 85 of file poly.h.


Member Enumeration Documentation

template<class T>
enum poly<T>::bogus [private]
 

Enumeration values:
numPts  

Definition at line 97 of file poly.h.

00097 { numPts = 4 } bogus;


Constructor & Destructor Documentation

template<class T>
poly<T>::poly<T> ( ) [inline]
 

poly class constructor.

Definition at line 91 of file poly.h.

00091 {}

template<class T>
poly<T>::~poly<T> ( ) [inline]
 

Definition at line 92 of file poly.h.

00092 {}

template<class T>
poly<T>::poly<T> ( const poly<T> & rhs )
 


Member Function Documentation

template<class T>
void poly<T>::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 111 of file poly.h.

Referenced by predict().

00112   {
00113     int n = numPts;
00114     if (n > N)
00115       n = N;
00116     int end = start + n;
00117     int j = 0;
00118 
00119     for (int i = start; i < end; i++) {
00120       d[j] = vec[i];
00121       j++;
00122     }
00123   } // fill

template<class T>
void poly<T>::forwardStep ( T & vec,
const int n ) [inline, virtual]
 

One step in the forward wavelet transform.

Reimplemented from liftbase.

Definition at line 248 of file poly.h.

00249   {
00250     split( vec, n );
00251     update( vec, n, forward );
00252     predict( vec, n, forward );
00253   } // forwardStep

template<class T>
void poly<T>::inverseStep ( T & vec,
const int n ) [inline, virtual]
 

One inverse wavelet transform step.

Reimplemented from liftbase.

Definition at line 255 of file poly.h.

00256   {
00257     predict( vec, n, inverse );
00258     update( vec, n, inverse );
00259     merge( vec, n );
00260   }

template<class T>
void poly<T>::predict ( T & vec,
int N,
transDirection direction ) [inline, protected, virtual]
 

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

Reimplemented from liftbase.

Definition at line 200 of file poly.h.

00201   {
00202     int half = N >> 1;
00203     double d[4];
00204 
00205     for (int i = 0; i < half; i++) {
00206       double predictVal;
00207 
00208       if (i == 0) {
00209         if (half == 1) {
00210           // e.g., N == 2, and we use Haar interpolation
00211           predictVal = vec[0];
00212         }
00213         else {
00214           fill( vec, d, N, 0 );
00215           predictVal = fourPtInterp.interpPoint( 0.5, half, d );
00216         }
00217       }
00218       else if (i == 1) {
00219         predictVal = fourPtInterp.interpPoint( 1.5, half, d );
00220       }
00221       else if (i == half-2) {
00222         predictVal = fourPtInterp.interpPoint( 2.5, half, d );
00223       }
00224       else if (i == half-1) {
00225         predictVal = fourPtInterp.interpPoint( 3.5, half, d );
00226       }
00227       else {
00228         fill( vec, d, N, i-1);
00229         predictVal = fourPtInterp.interpPoint( 1.5, half, d );
00230       }
00231 
00232       int j = i + half;
00233       if (direction == forward) {
00234         vec[j] = vec[j] - predictVal;
00235       }
00236       else if (direction == inverse) {
00237         vec[j] = vec[j] + predictVal;
00238       }
00239       else {
00240         printf("interp: bad direction value\n");
00241         break;
00242       }
00243     } // for
00244   } // predict

template<class T>
void poly<T>::update ( T & vec,
int N,
transDirection direction ) [inline, protected, virtual]
 

The update stage calculates the forward and inverse Haar scaling functions.

The forward Haar scaling function is simply the average of the even and odd elements. The inverse function is found by simple algebraic manipulation, solving for the even element given the average and the odd element.

In this version of the wavelet transform the update stage preceeds the predict stage in the forward transform. In the inverse transform the predict stage preceeds the update stage, reversing the calculation on the odd elements.

Reimplemented from liftbase.

Definition at line 144 of file poly.h.

00145   {
00146     int half = N >> 1;
00147 
00148     for (int i = 0; i < half; i++) {
00149       int j = i + half;
00150       double updateVal = vec[j] / 2.0;
00151 
00152       if (direction == forward) {
00153         vec[i] = (vec[i] + vec[j])/2;
00154       }
00155       else if (direction == inverse) {
00156         vec[i] = (2 * vec[i]) - vec[j];
00157       }
00158       else {
00159         printf("update: bad direction value\n");
00160       }
00161     }
00162   } // update


Member Data Documentation

template<class T>
polyinterp poly<T>::fourPtInterp [private]
 

Definition at line 98 of file poly.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 doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001