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

haar Class Template Reference

Haar (flat line) wavelet. More...

#include <haar.h>

Inheritance diagram for haar::

liftbase List of all members.

Protected Methods

void predict (T &vec, int N, transDirection direction)
 Haar predict step. More...

void update (T &vec, int N, transDirection direction)
 Update step of the Haar wavelet transform. More...

void normalize (T &vec, int N, transDirection direction)
 The normalization step assures that each step of the wavelet transform has the constant "energy" where energy is defined as. More...

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

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

Detailed Description

template<class T> class haar

Haar (flat line) wavelet.

As with all Lifting scheme wavelet transform functions, the first stage of a transform step is the split stage. The split step moves the even element to the first half of an N element region and the odd elements to the second half of the N element region.

The Lifting Scheme version of the Haar transform uses a wavelet function (predict stage) that "predicts" that an odd element will have the same value as it preceeding even element. Stated another way, the odd element is "predicted" to be on a flat (zero slope line) shared with the even point. The difference between this "prediction" and the actual odd value replaces the odd element.

The wavelet scaling function (a.k.a. smoothing function) used in the update stage calculates the average between an even and an odd element.

The merge stage at the end of the inverse transform interleaves odd and even elements from the two halves of the array (e.g., ordering them even0, odd0, even1, odd1, ...)

This is a template version of the Haar wavelet. The template must be instantiated with an array or an object that acts like an array. Objects that act like arrays define the left hand side and right hand side index operators: [].

See www.bearcave.com for more information on wavelets and the wavelet lifting scheme.

Author:
Ian Kaplan

Definition at line 79 of file haar.h.

Member Function Documentation

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

One step in the forward wavelet transform, with normalization.

Reimplemented from liftbase.

Definition at line 218 of file haar.h.

00219   {
00220     split( vec, n );
00221     predict( vec, n, forward );
00222     update( vec, n, forward );
00223     normalize( vec, n, forward );
00224   } // forwardStep

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

One inverse wavelet transform step, with normalization.

Reimplemented from liftbase.

Definition at line 207 of file haar.h.

00208   {
00209     normalize( vec, n, inverse );
00210     update( vec, n, inverse );
00211     predict( vec, n, inverse );
00212     merge( vec, n );
00213   }  // inverseStep

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

The normalization step assures that each step of the wavelet transform has the constant "energy" where energy is defined as. 

    double energy = 0.0;
    for (int n = 0; n < N; n++) {
       energy = energy + (a[i] * a[i]);
    }

See 5.2.1 of Ripples in Mathematics by Jensen and la Cour-Harbo

The most common implementation of the Haar transform leaves out the normalization step, since it does not make much of a difference in many cases. However, in the case of the wavelet packet transform, many of the cost functions are squares, so normalization produces smaller wavelet values (although the scaling function values are larger). This may lead to a better wavelet packet result (e.g., a few large values and lots of small values).

Normalization does have the disadvantage of destroying the averaging property of the Haar wavelet algorithm. That is, the final scaling factor is no longer the mean of the time series.

Definition at line 182 of file haar.h.

Referenced by forwardStep(), and inverseStep(). 

00183   {
00184     const double sqrt2 = sqrt( 2.0 );
00185     int half = N >> 1;
00186 
00187     for (int i = 0; i < half; i++) {
00188       int j = i + half;
00189 
00190       if (direction == forward) {
00191         vec[i] = sqrt2 * vec[i];
00192         vec[j] = vec[j]/sqrt2;
00193       }
00194       else if (direction == inverse) {
00195         vec[i] = vec[i]/sqrt2;
00196         vec[j] = sqrt2 * vec[j];
00197       }
00198       else {
00199         printf("normalize: bad direction value\n");
00200       }
00201     } // for
00202   } // normalize

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

Haar predict step.

Reimplemented from liftbase.

Definition at line 85 of file haar.h.

00086   {
00087     int half = N >> 1;
00088 
00089     for (int i = 0; i < half; i++) {
00090       double predictVal = vec[i];
00091       int j = i + half;
00092 
00093       if (direction == forward) {
00094         vec[j] = vec[j] - predictVal;
00095       }
00096       else if (direction == inverse) {
00097         vec[j] = vec[j] + predictVal;
00098       }
00099       else {
00100         printf("haar::predict: bad direction value\n");
00101       }
00102     }
00103   }

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

Update step of the Haar wavelet transform.

The wavelet transform calculates a set of detail or difference coefficients in the predict step. These are stored in the upper half of the array. The update step calculates an average from the even-odd element pairs. The averages will replace the even elements in the lower half of the array.

The Haar wavelet calculation used in the Lifting Scheme is 

       dj+1, i = oddj+1, i = oddj, i - evenj, i
       aj+1, i = evenj, i = (evenj, i + oddj, i)/2

Note that the Lifting Scheme uses an in-place algorithm. The odd elements have been replaced by the detail coefficients in the predict step. With a little algebra we can substitute the coefficient calculation into the average calculation, which gives us 

       aj+1, i = evenj, i = evenj, i + (oddj, i/2)

Reimplemented from liftbase.

Definition at line 134 of file haar.h.

00135   {
00136     int half = N >> 1;
00137 
00138     for (int i = 0; i < half; i++) {
00139       int j = i + half;
00140       double updateVal = vec[j] / 2.0;
00141 
00142       if (direction == forward) {
00143         vec[i] = vec[i] + updateVal;
00144       }
00145       else if (direction == inverse) {
00146         vec[i] = vec[i] - updateVal;
00147       }
00148       else {
00149         printf("update: bad direction value\n");
00150       }
00151     }
00152   }

The documentation for this class was generated from the following file:
Generated at Sat Aug 10 13:23:36 2002 for Wavelet Packet Transform and Lossless Compression by doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001