besttree (Wavelet Toolbox)

Best tree (wavelet packet).

[T,D] = besttree(T,D)
[T,D,E] = besttree(T,D)
[T,D,E,N] = besttree(T,D)

Description

besttree is a one- or two-dimensional wavelet packet analysis function that computes the optimal sub-tree 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. As a result, a signal of length N = 2^L can be expanded in at most 2^N different ways, the number of binary sub-trees of a complete binary sub-tree of depth L. As 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,D] = besttree(T,D) computes the modified tree structure T and data structure D (see maketree), corresponding to the best entropy value.

[T,D,E] = besttree(T,D) returns the best tree T, the data structure D, and in addition, the best entropy value E.

[T,D,E,N] = besttree(T,D) returns the best tree T, the data structure D, the best entropy value E, and in addition, the vector N containing the indices of the merged nodes.

Examples

% Load signal.
    load noisdopp; x = noisdopp;
% Decompose x at depth 3 with db1 wavelet packets, using 
% default entropy (shannon) and decompose the packet [3 0]. 
    [wpt,wpd] = wpdec(x,3,'db1'); 
    [wpt,wpd] = wpsplt(wpt,wpd,[3 0]);

% Plot wavelet packet tree structure wpt. 
    plottree(wpt)




% Compute best tree.
    [bt,bd] = besttree(wpt,wpd)
% Plot best tree structure bt. 
    plottree(bt)

Algorithm

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 wentropy). 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 sub-trees of T.