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

invpacktree_int Class Reference

Inverse wavelet packet transform. More...

#include <invpacktree_int.h>

List of all members.

Public Methods

 invpacktree_int (packdata_list< int > &list, liftbase< packcontainer_int, int > *w)
 This constructor calculates the inverse wavelet packet transform. More...

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

const int* 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_int (const invpacktree_int &rhs)
 disallow the copy constructor. More...

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

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

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


Private Attributes

liftbase<packcontainer_int,
int>* 
waveObj
 wavelet transform object. More...

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

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

size_t N
 length of data. More...


Detailed Description

Inverse wavelet packet transform.

The invpacktree_int 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.

Definition at line 81 of file invpacktree_int.h.


Constructor & Destructor Documentation

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

disallow the copy constructor.

Definition at line 86 of file invpacktree_int.h.

00086 {}

invpacktree_int::invpacktree_int ( packdata_list< int > & list,
liftbase< packcontainer_int, int > * 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_int.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<int>::handle h;
00213   for (h = list.first(); h != 0; h = list.next( h )) {
00214     packdata<int> *elem = list.get_item( h );
00215     add_elem( elem );
00216   } // for
00217 
00218   LIST<packcontainer_int *>::handle tosHandle;
00219   tosHandle = stack.first();
00220   packcontainer_int *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_int

invpacktree_int::~invpacktree_int ( ) [inline]
 

The destructor does nothing.

Definition at line 105 of file invpacktree_int.h.

00105 {}


Member Function Documentation

void invpacktree_int::add_elem ( packdata< int > * 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_int 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_int 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_int 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_int.cpp.

Referenced by invpacktree_int().

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_int *>::handle h;
00176     h = stack.first();
00177     packcontainer_int *tos = stack.get_item( h );
00178 
00179     if (tos->length() == n) {
00180       assert( tos->rhsData() == 0);
00181       tos->rhsData( (int *)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 int * invpacktree_int::getData ( ) [inline]
 

Get the result of the inverse packet transform.

Definition at line 108 of file invpacktree_int.h.

Referenced by packet_calc().

00108 { return data; }

void invpacktree_int::new_level ( packdata< int > * elem ) [private]
 

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

The new "level" is built from a packcontainer_int 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_int.cpp.

Referenced by add_elem().

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

void invpacktree_int::pr ( )
 

print the result of the inverse wavelet packet transform.

Definition at line 235 of file invpacktree_int.cpp.

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_int::reduce ( ) [private]
 

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

Calculate an inverse wavelet transform step on the packcontainer_int object. The packcontainer_int 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_int 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_int will be pushed on the stack. The left hand size will be the transform result.

Definition at line 84 of file invpacktree_int.cpp.

Referenced by add_elem().

00085 {
00086   LIST<packcontainer_int *>::handle h;
00087   h = stack.first();
00088   packcontainer_int *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   int *vec = (int *)mem_pool.pool_alloc( n * sizeof( int ) );
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_int *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_int *container = new packcontainer_int( n*2 );
00123       container->lhsData( vec );
00124       stack.add( container );
00125     }  // else
00126   }
00127   else {
00128     // the stack is empty
00129     packcontainer_int *container = new packcontainer_int( n*2 );
00130     container->lhsData( vec );
00131     stack.add( container );  
00132   }
00133 } // reduce


Member Data Documentation

size_t invpacktree_int::N [private]
 

length of data.

Definition at line 94 of file invpacktree_int.h.

const int * invpacktree_int::data [private]
 

pointer to the inverse transform result.

Definition at line 92 of file invpacktree_int.h.

LIST< packcontainer_int *> invpacktree_int::stack [private]
 

inverse wavelet packet transform calculation stack.

Definition at line 89 of file invpacktree_int.h.

liftbase< packcontainer_int, int > * invpacktree_int::waveObj [private]
 

wavelet transform object.

Definition at line 84 of file invpacktree_int.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