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

packtree_base Class Reference

Base class for wavelet packet trees. More...

#include <packtree_base.h>

Inheritance diagram for packtree_base::

packfreq packtree List of all members.

Public Methods

void pr ()
 Print the wavelet packet tree data and wavelet transform result to standard out. More...

packnode<double>* getRoot ()
 get the root of the wavelet packet tree. More...


Protected Types

enum  printKind { BadPrintKind, printData, printCost, printBestBasis }

Protected Methods

void breadthFirstPrint (printKind kind)
 Print the wavelet packet tree, breadth first (this is also sometimes called a level traversal). More...

void newLevel (packnode< double > *top, bool freqCalc, bool reverse)
 Add a new level to the wavelet packet tree. More...


Protected Attributes

packnode<double>* root
 root of the wavelet packet tree. More...

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


Detailed Description

Base class for wavelet packet trees.

Subclasses for this class include classes to built wavelet packet trees for best basis calculation and wavelet packet trees for frequency analysis.

Author:
Ian Kaplan

Definition at line 52 of file packtree_base.h.


Member Enumeration Documentation

enum packtree_base::printKind [protected]
 

Enumeration values:
BadPrintKind  
printData  
printCost  
printBestBasis  

Definition at line 60 of file packtree_base.h.

00060                { BadPrintKind, 
00061                  printData, 
00062                  printCost, 
00063                  printBestBasis } printKind;


Member Function Documentation

void packtree_base::breadthFirstPrint ( printKind kind ) [protected]
 

Print the wavelet packet tree, breadth first (this is also sometimes called a level traversal).

The breadth first traversal uses a queue. The root of the tree is initially inserted into the queue. The function operates by deleting the node at teh front of the queue, printing the data associated with that node and adding the node's left and right children to the queue. Since a node's children are at the next lower level, and we add the left child before the right child, the function prints a tree level from left to right.

The above paragraph paraphrases Chapter 5, Level Order Traversal of Fundamentals of Data Structures in C by Horowitz, Sahni and Anderson-Freed, 1993.

Definition at line 129 of file packtree_base.cpp.

Referenced by pr(), packtree::prBestBasis(), and packtree::prCost().

00130 {
00131   queue<double> Q;
00132 
00133   Q.addQueue( root, 0 );
00134   while (! Q.queueEmpty() ) {
00135     packnode<double> *node = Q.queueStart()->node;
00136     size_t indent = Q.queueStart()->indent;
00137     Q.deleteStart();
00138     
00139     if (indent > 0) {
00140       // print 'indent' spaces
00141       printf("%*c", indent, ' ');
00142     }
00143 
00144     switch (kind) {
00145     case printData: node->pr();
00146       break;
00147     case printCost: node->prCost();
00148       break;
00149     case printBestBasis: node->prBestBasis();
00150       break;
00151     default:
00152       assert( false );
00153       break;
00154     } // switch
00155     
00156     packnode<double> *lhs = node->lhsChild();
00157     packnode<double> *rhs = node->rhsChild();
00158 
00159     if (lhs != 0) {
00160       Q.addQueue( lhs, indent + 2 );
00161     }
00162     if (rhs != 0) {
00163       Q.addQueue( rhs, indent + 2 );
00164     }
00165   }
00166 } // packtree_base::breadthFirstPrint

packnode< double > * packtree_base::getRoot ( ) [inline]
 

get the root of the wavelet packet tree.

Definition at line 72 of file packtree_base.h.

Referenced by main().

00072 { return root; }

void packtree_base::newLevel ( packnode< double > * top,
bool freqCalc,
bool reverse ) [protected]
 

Add a new level to the wavelet packet tree.

Wavelet packet trees are data structures that support a variety of applications.

If the reverse argument is true, the locations of the high pass and low pass filter results in the wavelet calculation will be reversed. This is used in building a wavelet packet tree for frequency analysis.

The top packnode object contains data from the previous level. If this is the first level in the tree, top will contain the input data set.

A packcontainer object is created with the top data. The packcontainer constructor will allocate new storage and copy the data into this storage. If the packcontainer object consists of N elements, then there will be N/2 elements on the left and N/2 or the right. The object allows the lhs and rhs data to be accessed as one array.

A wavelet transform step is calculated on the N element data set. This results in N/2 values from the wavelet scaling function (low pass function) and N/2 values from the wavelet function (high pass function). These values are used to create two new packnode objects which become children of top. Sub-trees for the new packnode objects are recursively calculated.

As the tree is constructed, the leaves of the tree are marked with a boolean flag in preparation for calculating the "best basis" representation for the data. See the algorithm outlined in section 8.2.2 of "Ripples in Mathematics" by Jensen and la Cour-Harbo

The wavelet packet tree form that is used for wavelet packet frequency analysis is described in section 9.3 (figure 9.14) ofg "Ripples in Mathematics".

Definition at line 47 of file packtree_base.cpp.

Referenced by packfreq::packfreq(), and packtree::packtree().

00050 {
00051   if (top != 0) {
00052     const size_t len = top->length();
00053     if (len > 1) {
00054       // Create a new wavelet packet container for use in
00055       // calculating the wavelet transform.  Note that the
00056       // container is only used locally.
00057       packcontainer container( top );
00058 
00059       if (reverse) {
00060         // Calculate the reverse foward wavelet transform step, 
00061         // where the high pass result is stored in the upper half
00062         // of the container and the low pass result is stored
00063         // in the lower half of the container.
00064         waveObj->forwardStepRev( container, len );
00065       }
00066       else {
00067         // Calculate the foward wavelet transform step, where
00068         // the high pass result is stored in the upper half
00069         // of the container and the low pass result is stored
00070         // in the lower half of the container.
00071         waveObj->forwardStep( container, len );
00072       }
00073 
00074       packnode<double> *lhs = new packnode<double>(container.lhsData(), 
00075                                                    len/2,
00076                                                    packnode<double>::LowPass );
00077       packnode<double> *rhs = new packnode<double>(container.rhsData(), 
00078                                                    len/2,
00079                                                    packnode<double>::HighPass );
00080 
00081       // set the "mark" in the top node to false and
00082       // mark the two children to true.
00083       top->mark( false );
00084       lhs->mark( true );
00085       rhs->mark( true );
00086 
00087       top->lhsChild( lhs );
00088       top->rhsChild( rhs );
00089 
00090       // The transform on the left hand side always uses
00091       // the standard order (e.g., low pass filter result
00092       // goes in the lower half, high pass goes in the
00093       // upper half of the container).
00094       newLevel( lhs, freqCalc, false );
00095 
00096       if (freqCalc) {
00097         // wavelet packet frequency analysis reverses the
00098         // storage locations for the filter results in the
00099         // right hand child
00100         newLevel( rhs, freqCalc, true );
00101       }
00102       else { // freq == false
00103         // use standard filter location
00104         newLevel( rhs, freqCalc, false );
00105       }
00106     }
00107   }
00108 } // newLevel

void packtree_base::pr ( )
 

Print the wavelet packet tree data and wavelet transform result to standard out.

Definition at line 175 of file packtree_base.cpp.

Referenced by main().

00176 {
00177   if (root != 0) {
00178     breadthFirstPrint(printData);
00179   }
00180 } // pr


Member Data Documentation

packnode< double > * packtree_base::root [protected]
 

root of the wavelet packet tree.

Definition at line 55 of file packtree_base.h.

liftbase< packcontainer, double > * packtree_base::waveObj [protected]
 

wavelet packet transform object.

Definition at line 58 of file packtree_base.h.


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