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

packtree_int Class Reference

The packtree_int object constructs a wavelet packet tree. More...

#include <packtree_int.h>

Inheritance diagram for packtree_int::

packtree_base_int List of all members.

Public Methods

 packtree_int (const int *vec, const size_t n, liftbase< packcontainer_int, int > *w)
 Construct a wavelet packet tree from a vector of integer values. More...

 ~packtree_int ()
 destructor does nothing. More...

void prCost ()
 Print the wavelet packet tree cost values in breadth first order. More...

void prBestBasis ()
 Print the wavelet packet tree, showing the nodes that have been selected by the "best basis" algorithm. More...

void bestBasis ()
 Calculate the wavelet packet "best basis". More...

bool bestBasisOK ()
 Return true is be best basis has been calculated properly, return false if the best basis has not been calculated or it was not calculated properly. More...

packdata_list<int> getBestBasisList ()
 Return a list consisting of the best basis packdata values. More...


Private Methods

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

 packtree_int ()
 disallow the default constructor. More...

int bestBasisWalk (packnode< int > *root)
 Walk the wavelet packet tree and apply the "best basis" algorithm described in Chapter 8 of Ripples in Mathematics. More...

void buildBestBasisList (packnode< int > *root, packdata_list< int > &list)
 Traverse the tree from the top down and add the best basis nodes to the best basis list. More...

void checkBestBasis (packnode< int > *root)
 Recursively traverse the wavelet packet tree and check that the best basis result is correct. More...

void cleanTree (packnode< int > *root, bool removeMark)
 The best basis algorithm selects the nodes nearest the tree root for the best basis set. More...


Private Attributes

bool foundOriginalData
 Found original data marked as part of the best basis. More...

bool foundBestBasisVal
 found a best basis value in the wavelet packet tree. More...


Detailed Description

The packtree_int object constructs a wavelet packet tree.

The constructor is passed a vector of integers, the length of the vector (which must be a power of two) and a pointer to a wavelet lifting scheme class that will be used in calculating the wavelet transform step. If the vector passed to the constructor contains N int vaues, the result of the constructor will be a wavelet packet tree with log2(N) levels.

Definition at line 57 of file packtree_int.h.


Constructor & Destructor Documentation

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

disallow the copy constructor.

Definition at line 70 of file packtree_int.h.

00070 {};

packtree_int::packtree_int ( ) [inline, private]
 

disallow the default constructor.

Definition at line 72 of file packtree_int.h.

00072 {};

packtree_int::packtree_int ( const int * vec,
const size_t n,
liftbase< packcontainer_int, int > * w )
 

Construct a wavelet packet tree from a vector of integer values.

The size of the vector, which must be a power of two, is passed in N. A wavelet Lifting Scheme object is passed in w. This object is used to calculate the wavelet transform step which is applied at each level (where level > 0) of the wavelet packet tree.

The first level (level 0) of the wavelet packet tree contains the original data set.

  • vec An array of integer values on which the wavelet packet transform is calculated.
  • N The number of elements in the input array
  • w A pointer to the the wavelet transform object to use in calculating the wavelet packet transform.

Definition at line 58 of file packtree_int.cpp.

00061 {
00062   waveObj = w;
00063 
00064   block_pool mem_pool;
00065   int *vecCopy = (int *)mem_pool.pool_alloc( N * sizeof( int ) );
00066 
00067   for (int i = 0; i < N; i++) {
00068     vecCopy[i] = vec[i];
00069   }
00070 
00071   root = new packnode<int>( vecCopy, N, packnode<int>::OriginalData );
00072   root->mark( true );
00073   newLevel( root, false, false ); 
00074 } // packtree_int

packtree_int::~packtree_int ( ) [inline]
 

destructor does nothing.

Definition at line 90 of file packtree_int.h.

00090 {}


Member Function Documentation

void packtree_int::bestBasis ( )
 

Calculate the wavelet packet "best basis".

Definition at line 196 of file packtree_int.cpp.

Referenced by packet_calc().

00197 {
00198   bestBasisWalk( root );
00199 } // bestBasis

bool packtree_int::bestBasisOK ( )
 

Return true is be best basis has been calculated properly, return false if the best basis has not been calculated or it was not calculated properly.

The best basis is calculated in reference to a particular cost function. A particular cost function will not always result in a data set which differs from the original data set. If this is the case, the "best basis" result will include the original data.

Definition at line 249 of file packtree_int.cpp.

Referenced by packet_calc().

00250 {
00251   foundOriginalData = false;
00252   foundBestBasisVal = false;
00253   checkBestBasis( root );
00254 
00255   bool rslt = (foundBestBasisVal && (!foundOriginalData));
00256 
00257   return rslt;
00258 } // bestBasicOK

int packtree_int::bestBasisWalk ( packnode< int > * root ) [private]
 

Walk the wavelet packet tree and apply the "best basis" algorithm described in Chapter 8 of Ripples in Mathematics.

Nodes that are "marked" become part of the best basis, which is a minimal representation of the data in terms of the cost function.

Definition at line 152 of file packtree_int.cpp.

Referenced by bestBasis().

00153 {
00154   int cost = 0;
00155 
00156   if (top != 0) {
00157     packnode<int> *lhs = top->lhsChild();
00158     packnode<int> *rhs = top->rhsChild();
00159 
00160     if (lhs == 0 && rhs == 0) { // we've reached a leaf
00161       cost = top->cost();
00162     }
00163     else if (lhs != 0 && rhs != 0) {
00164 
00165       int lhsCost = bestBasisWalk( lhs );
00166       int rhsCost = bestBasisWalk( rhs );
00167 
00168       int v1 = top->cost();
00169       int v2 = lhsCost + rhsCost;
00170 
00171       if (v1 <= v2) {
00172         top->mark( true );
00173         lhs->mark( false );
00174         rhs->mark( false );
00175       }
00176       else { // v1 > v2
00177         top->cost( v2 );
00178       }
00179       cost = top->cost();
00180     }
00181     else {
00182       // The tree does not seem to be a full binary tree
00183       // Something has gone badly wrong.
00184       assert( false );
00185     }
00186   }
00187 
00188   return cost;
00189 } // bestBasicWalk

void packtree_int::buildBestBasisList ( packnode< int > * root,
packdata_list< int > & list ) [private]
 

Traverse the tree from the top down and add the best basis nodes to the best basis list.

Note that the list object is simply a package for a scalar value, the pointer to the head of the list. So it can be passed by value without incurring a cost greater than passing a pointer (e.g., pass by reference).

Definition at line 270 of file packtree_int.cpp.

Referenced by getBestBasisList().

00272 {
00273   if (top != 0) {
00274     if (top->mark()) {
00275       list.add( top );
00276     }
00277     else {
00278       buildBestBasisList( top->lhsChild(), list );
00279       buildBestBasisList( top->rhsChild(), list );
00280     }
00281   }
00282 } // buildBestBasisList

void packtree_int::checkBestBasis ( packnode< int > * root ) [private]
 

Recursively traverse the wavelet packet tree and check that the best basis result is correct.

That is, that the best basis has been calculated and that it does not include the orignal data set. The best basis includes the original data set with the packnode ofr the original data set is marked.

This algorithm makes use of two class global variables. There may be a purely recursive, way to do this without these global class variables, but these variables make the algorithm much easier. The variables are initialized by the calling function bestBasisOK().

Definition at line 217 of file packtree_int.cpp.

Referenced by bestBasisOK().

00218 {
00219   if (top != 0) {
00220     if (top->mark()) {
00221       foundBestBasisVal = true;
00222       if (top->getKind() == packdata<int>::OriginalData) {
00223         foundOriginalData = true;
00224       }
00225     }
00226     if (!foundOriginalData) {
00227       checkBestBasis( top->lhsChild() );
00228     }
00229     if (!foundOriginalData) {
00230       checkBestBasis( top->rhsChild() );
00231     }
00232   }
00233 }  // checkBestBasis

void packtree_int::cleanTree ( packnode< int > * root,
bool removeMark ) [private]
 

The best basis algorithm selects the nodes nearest the tree root for the best basis set.

These nodes are "marked" true with a boolean flag.

The best basis algorithm outlined in Ripples in Mathematics sets any marks in nodes that are below a marked node in the tree (nodes which are in a subtree of a marked node) to false. However, this is unnecessary when the best basis set is collected, since the algorithm uses top down tree traversal and stops at marked node.

A problem does arise when the entire tree is printed to show the nodes that are marked as part of the best basis set. In this case the result may appear wrong, since child nodes of a best basis node are marked. This function does a top down traversal setting the "marks" on these child nodes to false.

Definition at line 97 of file packtree_int.cpp.

Referenced by prBestBasis().

00098 {
00099   if (top != 0) {
00100     if (removeMark) {
00101       if (top->mark()) {
00102         top->mark( false );
00103       }
00104     }
00105     else {
00106       // if a mark is found, then set all the "marks" below that
00107       // point to false (e.g., remove the marks).
00108       if (top->mark()) {
00109         removeMark = true;
00110       }
00111     }
00112     cleanTree( top->lhsChild(), removeMark );
00113     cleanTree( top->rhsChild(), removeMark );
00114   }
00115 } // cleanTree

packdata_list< int > packtree_int::getBestBasisList<int> ( )
 

Return a list consisting of the best basis packdata values.

Definition at line 290 of file packtree_int.cpp.

Referenced by packet_calc().

00291 {
00292   packdata_list<int> list;
00293 
00294   buildBestBasisList( root, list );
00295   return list;
00296 } // getBestBasisList

void packtree_int::prBestBasis ( )
 

Print the wavelet packet tree, showing the nodes that have been selected by the "best basis" algorithm.

Definition at line 135 of file packtree_int.cpp.

00136 {
00137   if (root != 0) {
00138     cleanTree( root, false );
00139     breadthFirstPrint(printBestBasis);
00140   }
00141 } // prBestBasis

void packtree_int::prCost ( )
 

Print the wavelet packet tree cost values in breadth first order.

Definition at line 123 of file packtree_int.cpp.

00124 {
00125   if (root != 0) {
00126     breadthFirstPrint(printCost);
00127   }
00128 }


Member Data Documentation

bool packtree_int::foundBestBasisVal [private]
 

found a best basis value in the wavelet packet tree.

Definition at line 66 of file packtree_int.h.

bool packtree_int::foundOriginalData [private]
 

Found original data marked as part of the best basis.

This means that the best basis function failed (or that the original data is the most compact representation relative to the cost function used).

Definition at line 64 of file packtree_int.h.


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