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

invpacktree Class Reference

Inverse wavelet packet transform. More...

#include <invpacktree.h>

List of all members.

Public Methods

 invpacktree (packdata_list< double > &list, liftbase< packcontainer, double > *w)
 This constructor calculates the inverse wavelet packet transform. More...

 ~invpacktree ()
 The destructor does nothing. More...

const double* getData ()
 Get the result of the inverse packet transform. More...

void pr ()
 print the result of the inverse wavelet packet transform. More...


Private Methods

 invpacktree (const invpacktree &rhs)
 disallow the copy constructor. More...

void new_level (packdata< double > *elem)
 Allocate a new level in the wavelet packet tree that is being constructed. More...

void add_elem (packdata< double > *elem)
 Add a packdata element to the inverse wavelet packet transform calculation. More...

void reduce ()
 At this point the Top Of Stack (TOS) packcontainer object should have both a right and a left array. More...


Private Attributes

liftbase<packcontainer, double>* waveObj
 wavelet transform object. More...

LIST<packcontainer *> stack
 inverse wavelet packet transform calculation stack. More...

const double* data
 pointer to the inverse transform result. More...

size_t N
 length of data. More...


Detailed Description

Inverse wavelet packet transform.

The invpacktree constructor is passed a packdata_list object and a wavelet transform object. It calculates the inverse wavelet packet transform, using the data in the packdata_list object and the inverse wavelet transform step function of the wavelet transform object. The best basis data is destroyed in calculating the inverse transform.

The packdata_list object contains the "best basis" result from a wavelet packet transform. The wavelet packet transform should have been calculated with the same wavelet transform as the object passed to this constructor.

After the constructor completes, the data result can be obtained by calling the getData() function.

The wavelet transforms used by this object are all derived from the liftbase class and are "lifting scheme" wavelet transforms.

I have found the wavelet literature difficult, in general. When it comes to the wavelet packet transform I have found most of it impossible to understand. Impossible, that it until I got the book Ripples in Mathematics by Jensen and la Cour-Harbo, Springer Verlag, 2001. The wavelet packet transform, for which this class is the inverse, is heavily based on Chapter 8 of Ripples in Mathematics.

I have found very little material on the actual implementation of the inverse wavelet packet transform. This algorithm is my own design.

Author:
Ian Kaplan

Definition at line 83 of file invpacktree.h.


Constructor & Destructor Documentation

invpacktree::invpacktree ( const invpacktree & rhs ) [inline, private]
 

disallow the copy constructor.

Definition at line 88 of file invpacktree.h.

00088 {}

invpacktree::invpacktree ( packdata_list< double > & list,
liftbase< packcontainer, double > * w )
 

This constructor calculates the inverse wavelet packet transform.

The constructor is passed a packdata_list object, which contains the "best basis" result of the wavelet packet transform. The liftbase template argument is a pointer to a wavelet transform function. This wavelet transform must be the same function that was used to calculate the packet transform.

Definition at line 203 of file invpacktree.cpp.

00205 {
00206   data = 0;
00207   N = 0;
00208   waveObj = w;
00209 
00210   // Traverse the "best basis" list and calculate the inverse
00211   // wavelet packet transform.
00212   packdata_list<double>::handle h;
00213   for (h = list.first(); h != 0; h = list.next( h )) {
00214     packdata<double> *elem = list.get_item( h );
00215     add_elem( elem );
00216   } // for
00217 
00218   LIST<packcontainer *>::handle tosHandle;
00219   tosHandle = stack.first();
00220   packcontainer *tos = stack.get_item( tosHandle );
00221 
00222   if (tos != 0) {
00223     size_t len = tos->length();
00224     N = len/2;
00225 
00226     data = tos->lhsData();
00227     stack.remove();
00228   }
00229 } // invpacktree

invpacktree::~invpacktree ( ) [inline]
 

The destructor does nothing.

Definition at line 107 of file invpacktree.h.

00107 {}


Member Function Documentation

void invpacktree::add_elem ( packdata< double > * elem ) [private]
 

Add a packdata element to the inverse wavelet packet transform calculation.

A packdata element contains the wavelet packet data items from one level of the wavelet packet transform tree.

The inverse wavelet packet transform calculation uses a stack. Each level in the stack consists of a packcontainer object. This object consists of left and right hand size arrays. When both these arrays are present, they can be treated as one contiguous array (courtesy of C++ operator overloading). The size of the packcontainer object is twice the size of its left and right hand size arrays.

If the stack is empty, a new level is created. A packetcontainer object can be viewed as a binary tree element. The left hand size is filled in first.

If the stack is not empty and the packcontainer object on the top of stack (TOS) is twice the size of the elem argument, then the array contained in the elem argument is added to the TOS element and reduce is called to calculate a step of the inverse wavelet transform.

If the TOS element is greater than twice the size of elem then a new level is added.

Definition at line 165 of file invpacktree.cpp.

Referenced by invpacktree().

00166 {
00167   assert( elem != 0 );
00168 
00169   if (stack.first() == 0) {
00170     new_level( elem );
00171   }
00172   else {
00173     size_t half = elem->length();
00174     size_t n = half * 2;
00175     LIST<packcontainer *>::handle h;
00176     h = stack.first();
00177     packcontainer *tos = stack.get_item( h );
00178 
00179     if (tos->length() == n) {
00180       assert( tos->rhsData() == 0);
00181       tos->rhsData( (double *)elem->getData() );
00182       reduce();
00183     }
00184     else if (tos->length() > n) {
00185       new_level( elem );
00186     }
00187     else {
00188       printf("add_elem: the size of the TOS elem is wrong\n");
00189     }
00190   } // else
00191 } // add_elem

const double * invpacktree::getData ( ) [inline]
 

Get the result of the inverse packet transform.

Definition at line 110 of file invpacktree.h.

00110 { return data; }

void invpacktree::new_level ( packdata< double > * elem ) [private]
 

Allocate a new level in the wavelet packet tree that is being constructed.

The new "level" is built from a packcontainer object. The left child will be the elem argument. The length of the data in the new level will be twice that of lower level (of which elem is half).

Definition at line 55 of file invpacktree.cpp.

Referenced by add_elem().

00056 {
00057   size_t half = elem->length();
00058   size_t n = half * 2;
00059 
00060   packcontainer *container = new packcontainer( n );
00061   container->lhsData( (double *)elem->getData() );
00062   stack.add( container );
00063 } // new_level

void invpacktree::pr ( )
 

print the result of the inverse wavelet packet transform.

Definition at line 235 of file invpacktree.cpp.

Referenced by main().

00236 {
00237   if (data != 0) {
00238     for (int i = 0; i < N; i++) {
00239       printf("%7.4f ", data[i] );
00240     }
00241     printf("\n");
00242   }
00243 } // pr

void invpacktree::reduce ( ) [private]
 

At this point the Top Of Stack (TOS) packcontainer object should have both a right and a left array.

Calculate an inverse wavelet transform step on the packcontainer object. The packcontainer object allows the right and left hand side arrays to be treated as one array

If the current top of stack is twice the size of the inverse wavelet transform step result, the result becomes the right hand size of top of stack packcontainer and reduce is called recursively.

If the TOS is empty or it is not twice the size of the inverse transform result, a new packcontainer will be pushed on the stack. The left hand size will be the transform result.

Definition at line 84 of file invpacktree.cpp.

Referenced by add_elem().

00085 {
00086   LIST<packcontainer *>::handle h;
00087   h = stack.first();
00088   packcontainer *tos = stack.get_item( h );
00089 
00090   assert( tos->lhsData() != 0 && tos->rhsData() != 0 );
00091 
00097   stack.remove();
00098 
00099   size_t n = tos->length();
00100   // calculate the inverse wavelet transform step
00101   waveObj->inverseStep( (*tos), n );
00102 
00103   // copy the result of the inverse wavelet transform
00104   // into a new data array.
00105   block_pool mem_pool;
00106 
00107   double *vec = (double *)mem_pool.pool_alloc( n * sizeof( double ) );
00108   for (int i = 0; i < n; i++) {
00109     vec[i] = (*tos)[i];
00110   }
00111 
00112   if (stack.first() != 0) {
00113     h = stack.first();
00114     packcontainer *tos = stack.get_item( h );
00115 
00116     if (tos->length() == n*2) {
00117       tos->rhsData( vec );
00118       reduce();
00119     }
00120     else {
00121       assert( tos->length() > n*2 );
00122       packcontainer *container = new packcontainer( n*2 );
00123       container->lhsData( vec );
00124       stack.add( container );
00125     }  // else
00126   }
00127   else {
00128     // the stack is empty
00129     packcontainer *container = new packcontainer( n*2 );
00130     container->lhsData( vec );
00131     stack.add( container );  
00132   }
00133 } // reduce


Member Data Documentation

size_t invpacktree::N [private]
 

length of data.

Definition at line 96 of file invpacktree.h.

const double * invpacktree::data [private]
 

pointer to the inverse transform result.

Definition at line 94 of file invpacktree.h.

LIST< packcontainer *> invpacktree::stack [private]
 

inverse wavelet packet transform calculation stack.

Definition at line 91 of file invpacktree.h.

liftbase< packcontainer, double > * invpacktree::waveObj [private]
 

wavelet transform object.

Definition at line 86 of file invpacktree.h.


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