decomposition and representation
Israel Cohen, Shalom Raz, David Malah
Signal Processing 57(1997) 251-270
Theoretical background
Wavelet packets (WP) were firstly introduced by Coifman and Meyer as a library of orthonormal bases for L2(R). The proposed library, generated via a generalized version of the multiresolution decomposition, is cast into a binary tree configuration, in which the nodes represent subspaces with different time-frequency localization characteristics. A major deficiency of this approach is the lack of shift invariance. Both the wavelet packet decomposition (WPD) and local cosine decomposition (LCD) of Coifman and Wickerhauser, as well as the extended algorithms proposed by Herley et al. , are sensitive to the signal location with respect to the chosen time origin.
Shift-invariant multiresolution representations exist. However, some methods either entail high oversampling rates or immense computational complexity. In some other methods, the resulting representations are non-unique and involve approximate signal reconstructions, as is the case for zero crossing or local maxima methods. Another approach has given up obtaining shift invariance and settled for a less restrictive property named shiftability, which is accomplished by imposing limiting conditions on the scaling function.
Recently, several authors proposed independently to extend the library of bases, in which the best representations are searched for, by introducing additional degrees of freedom that adjust the time-localization of the basis functions. It was proved that the proposed modifications of the wavelet transform and wavelet packet decomposition lead to orthonormal best-basis representations which are shift invariant and are characterized by lower information costs. The principal idea is to adapt the down sampling when expanding each parent node. That is, following the low-pass and high pass filtering, when expanding a parent node, retain either all the odd samples or all the even samples, according to the choice which minimizes the cost function.
In this work we generate a shifted wavelet packet (SWP) library and introduce a shift-invariant wavelet packet decomposition (SIWPD) algorithm for a "best basis" selection with respect to an additive cost function (e.g., entropy). We prove that the proposed algorithm leads to a best-basis representation that is both shift-invariant and orthogonal.
Method employed
Pursuing the SIWPD algorithm, shift invariance is achieved by the introduction
of an additional degree of freedom. The added dimension is a relative shift
between a given parent node and its respective children nodes. Specifically,
upon expanding a prescribed node, with minimization of the information
cost in mind, we test as to whether or not the information cost indeed
decreases. We prove that for any given parent node it is sufficient to
examine and select one of two alternative decompositions. These decompositions
correspond to a zero shift and a 2-l shift where l (-L<l<0)
denotes the resolution level. The special case where, at any resolution
level, only low frequency nodes are further expanded corresponds to a shift-invariant
wavelet transform (SIWT). Accordingly, each parent node is expanded by
high-pass and low-pass filters, followed by a 2:1 down sampling which is
achieved adaptively for the prescribed signal. Owing to the orthogonality
of the representation and the presumed additive nature of the cost function,
the decision at any given node is strictly local, i.e., independent of
other notes at the same resolution level. In contrast to WPD, SIWPD wxpansion
leads to tree configurations that are independent of the time origin.
The best-basis expansion under SIWPD is also characterized by the invariance
of the information cost. This feature is significant as it facilitates
a meaningful quantitative comparison between alternative SWP libraries.
Usually such acomparison between alternative libraries lacks meaning for
WP.
Practical application results
An experiment on 50 acoustic transients, generated by explosive charges at various distances (these signals are detected by an array of receivers and used to evaluate the location of explosive devices). We applied the WPD algorithm, the suboptimal SIWPD with d=1 or d=2, and the optimal SIWPD to the compression of this data set. The decomposition was carried out to maximum level L=5 using 8-tap Daubechies minimum phase wavelet filters. The results show that the average entropy is lower when using the SIWPD. It decreases when d is larger, and a minimum value is reached using the optimal SIWPD (d=L). Moreover, the variations in the information cost, which indicate performance robustness across the data set, are also lower when using the SIWPD. To illustrate the improvement in information cost of the SIWPD with carious d values, over the conventional WPD, the reduction in entropy relative to the entropy obtained using the WPD. The results show that for some signals the entropy is reduced by more than 30%. The average reduction is 10.8% by the suboptimal SIWPD (d=1), 16.4% by the suboptimal SIWPD (d=2) and 18.1% by the optimal SIWPD.
When compared with the WPD algorithm, SIWPD has three advantageous. (1) it leads to a best basis expansion that is shift invariant. (2) the resulting representation is characterized by a lower information cost. (3) the complexity is controlled at the expense of the information cost. These advantages may prove crucial to signal compression, identification or classification applications.