besttree
Best tree wavelet packet analysis
Syntax
T = besttree(T)
[T,E] = besttree(T)
[T,E,N] = besttree(T)
Description
besttree is a one- or two-dimensional wavelet packet analysis function
that computes the optimal subtree of an initial tree with respect to an entropy type
criterion. The resulting tree may be much smaller than the initial one.
Following the organization of the wavelet packets library, it is natural to count the decompositions issued from a given orthogonal wavelet.
A signal of length N = 2L can be expanded in α different ways, where α is the number of binary subtrees of a complete binary tree of depth L.
As a result, we can conclude that α ≥ 2N/2 (for more information, see the Mallat's book given in References at page 323).
This number may be very large, and since explicit enumeration is generally intractable, it is interesting to find an optimal decomposition with respect to a convenient criterion, computable by an efficient algorithm. We are looking for a minimum of the criterion.
T = besttree( computes
the best tree T)T corresponding to the best
entropy value.
[T,E] = besttree( computes
the best tree T)T and, in addition, the best
entropy value E.
The optimal entropy of the node, whose index is j-1,
is E(j).
[T,E,N] = besttree( computes
the best tree T)T, the best entropy value E and,
in addition, the vector N containing the
indices of the merged nodes.
Examples
Best Wavelet Packet Tree
This example shows to obtain the optimal wavelet packet tree based on an entropy criterion.
Load the noisy Doppler signal. Obtain the wavelet packet tree down to level 4 with the 'sym4' wavelet. Use the periodic extension mode.
dwtmode('per');
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! WARNING: Change DWT Extension Mode !
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
*****************************************
** DWT Extension Mode: Periodization **
*****************************************
load noisdopp; T = wpdec(noisdopp,4,'sym4');
Obtain the best wavelet packet tree and plot the result.
BstTree = besttree(T); plot(BstTree)
Return the DWT extension mode to the default value.
dwtmode('sym');
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! WARNING: Change DWT Extension Mode !
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
*******************************************************
** DWT Extension Mode: Symmetrization (half-point) **
*******************************************************
Algorithms
Consider the one-dimensional case. Starting with the root node, the best tree is calculated using the following scheme. A node N is split into two nodes N1 and N2 if and only if the sum of the entropy of N1 and N2 is lower than the entropy of N. This is a local criterion based only on the information available at the node N.
Several entropy type criteria can be used (see wenergy for more information). If the
entropy function is an additive function along the wavelet packet
coefficients, this algorithm leads to the best tree.
Starting from an initial tree T and using the merging side of this algorithm, we obtain the best tree among all the binary subtrees of T.
References
Coifman, R.R.; M.V. Wickerhauser (1992), “Entropy-based algorithms for best basis selection,” IEEE Trans. on Inf. Theory, vol. 38, 2, pp. 713–718.
Mallat, S. (1998), A wavelet tour of signal processing, Academic Press.