Wavelet Packets and Signal-Adapted Filterbanks

Designing signal-adapted bases via principal component filter banks, compaction filters, and wavelet packets

Wavelet Packets and Signal-Adapted Filterbanks

These notes investigate methods for designing signal-adapted bases from filter banks, in particular principal component filter banks (PCFBs), FIR compaction filters, and wavelet packets (WPs), and the interplay among them. Signal-adapted filter banks, when viewed as a way of designing a best basis, find many applications in communication, source coding, and feature detection. There exist many ways of designing such filter banks, arising mainly from the various properties one may demand of them: finite length, number of channels, smoothness, regularity, compactness, and existence in all practical cases. Quite naturally, choosing a design mechanism is not a simple task. PCFBs are optimal in the sense of coding gain but may not always exist. FIR compaction filters, on the other hand, are particularly suitable for implementation but are sub-optimal. As an alternative for optimal energy compaction, one can consider wavelet packets: a fully-grown wavelet tree is nothing but a uniform filter bank, the bandwidth of each band proportional to the depth of the tree. Pruning this fully-grown tree can lead to a non-uniform filter bank, or to any structure driven by the design criteria, so WPs can be considered an alternative to PCFBs and FIR compaction filters.

Introduction

Signal Adapted Filter-Banks find numerous applications in signal representation, data compression, noise suppression, progressive transmission. These filters are designed based on the input power spectral density subject to certain constraints on the number of channels, order of the filter lengths, bandwidth of the filters etc.. There exist numerous procedures to derive and design filters. Some of them include Principal Component filter banks, Compaction filters [1-3].

Based on the design criteria and input spectral density, the nature these filters vary. For example, it turns that, an optimal transform coder is an optimal subband coder with constant polyphase matrix.

Due to the presence of many constraints in the design stage, one should be very careful in designing appropriate filters. For example, if the number of channels is more than two and filter length is constrained, then PCFBs may not exist. These difficulties pose significant challenge to the designer.

These notes consider an alternative to these signal-adapted filter banks: a class of filter banks derived from wavelet packets.

Filter-bank

A filterbank, essentially decomposes the input spectrum into certain number of sub-bands where the subbands may or may not overlap. The advantage of dividing the spectrum into smaller bands is that most of the energy might be present in only few of the subbands while the remaining bands may not have any energy in them. This helps us in processing only the subband corresponding to the maximum energy. Applications of such principle can be found in data compression, progressive transmission.

A subband coder is optimal if it follows the following two properties ( a necessary and sufficient condition for optimality)

The coding gain is maximized if:

1. Total decorrelation (the subbands are decorrelated one from the other)
2. The subbands majorize the spectrum

Where the coding gain is defined as:

\[ G_{SBC}(M) = \frac{\sum_{i=0}^{M-1} \sigma_i^2 / M}{\left( \prod_{i=0}^{M-1} \sigma_i^2 \right)^{1/M}} = \frac{\sigma_x^2}{\left( \prod_{i=0}^{M-1} \sigma_i^2 \right)^{1/M}}. \]

\(\sigma_i^2\), is the variance of the \(i^{th}\) subband. \(\sigma_x^2\) is the variance of the input.

Principal component filter-banks (PCFBS)

Definition: Let C be a class of FBs (like transform coder class, class of filter of infinite order etc..), then for a given input spectral density, PCFB is the FB that if its the variance vector majorizes all vectors in the subbands belonging to the class C.

PCFBs are optimal in the sense that, they maximize the coding gain (\(G_{SBC}\)). PCFBs have strong connection with transforms coders (in the case of FBs belonging to the class C), to Wiener filters (when the objective is to estimate the signal in the presence of noise) and are also the filters which minimize the transmit power in the discrete multi-tone modulation. In particular, when the filter order is less than the number of channels, KLT maximizes the coding gain which in this case is the PCFB.

Despite their many desirable properties, their existence is not always guaranteed. At least in the case of DFT filterbanks and cosine-modulated filter banks PCFBs cease to exist. However, in the two-channel case, FBs with unconstrained order and in the transform coder case, they always exist. In other situations, one has to analyze case-by-case. This makes them less interesting despite their many desirable attributes.

In the case when we don’t have PCFBS, we design compaction filters. An FIR compaction filter is said to be the one that compacts most of the energy into only one band. Then, remaining N-1 filters are completed by considering the complement of the power spectral density. or . A compaction filter is necessarily a Nyquist(M) filter, i.e.,

\[ |H_i(e^{j\omega})|^2 \Big|_{\downarrow M} = 1 \]

Let \(G(e^{j\omega}) = |H(e^{j\omega})|^2\), and compaction gain is defined as:

\[ G_{comp}(M,N) = \frac{\sigma_y^2}{\sigma_x^2} = \frac{\int_{-\pi}^{\pi} G(e^{j\omega}) S_{xx}(e^{j\omega}) \frac{d\omega}{2\pi}}{\int_{-\pi}^{\pi} S_{xx}(e^{j\omega}) \frac{d\omega}{2\pi}} \]

The method of designing compaction filters is in designing a filter which maximizes the compaction gain subject to the constraints,

\[ g(Mn) = \delta(n) \text{ (Nyquist}(M) \text{ condition)} \quad \text{and} \quad G(e^{j\omega}) \geq 0 \text{ (nonnegativity)} \]

Several methods were proposed to designing such filters in [4]. In the present context, we motivate ourselves to consider the following :

We want to design filters that are easily computable and share the elegance of PCFBs. That is we want to retain the existence of FIR compaction filters and retain and yet try to maximize the coding gain. We try to solve this by resorting to wavelet packets.

Wavelet Packets

A Wavelet packet is a complete grown wavelet tree. That is in dyadic wavelet transform, we only further filter the approximation coefficients and leave the detailed coefficients unattended. If think of the first analysis filter in as an approximate low-pass filter, then we repeatedly filter this low-pass filtered signal. Thus, after M levels of decomposition, we would have one approximate coefficient band and M-1 detailed coefficient band. We keep splitting the low-pass band repeatedly. In wavelet packets, we can process any of these low-pass or high-pass bands. If we selectively perform this operation of splitting, we can obtain a non-uniform filter-bank. A fully-grown wavelet packet upto M levels, would have M bands each of width 2Pi/M. This is the central idea behind using WPs as signal-adapted FBs.

Wavelet Packets as signal-adapted FBs

We achieve this by pruning the WP tree based on a certain criteria. It is suggested that certain entropy based techniques can be used to prune the tree. This problem was considered in the context of best-basis selection. Indeed, WP offer a wide variety of bases over which the signal can be projected. Thus, it is very suitable for processing large class of signals. As we increase the number of bands or in other words if we increase the depth of the decomposition, we search for even larger number of bases that can best approximate the signal under consideration.

A wavelet packet has an equivalent subband (filter-bank) representation: the wavelet packet tree splits the spectrum hierarchically, and each leaf of the tree corresponds to a band of the input spectrum.

The definition of best tree (i.e., the best way to prune the tree) very much depends on the objective function being used. In the context of best basis selection, [5], have used entropy as the criteria. Those nodes are pruned which minimize the cost function specified in terms of entropy. For example, when “pruning” corresponds to merging, i.e., we first grow the wavelet tree to its fullest depth possible, then we try to merge those two nodes which result in minimum increase in the entropy. We repeat this process until a stopping criteria is met. This stopping criteria can be given computational complexity, number of bands needed. On the other hand it is also possible to prune the tree by merging. In this case, we start with a initial tree and try to that node which results in maximum reduction in entropy. Like the earlier case, here also the stopping criteria can be desired number of subbands or desired SNR. The entropy function used in this operation is:

\[ - \sum_x x^2 \ln(x^2) \]

And this function is an additive function. However, as mentioned earlier, we want to prune the WP tree such that coding gain is maximized. For simplicity in implementation, we start with just two bands in the tree and try to split the bands which result in maximum increase in coding gain!

Conclusions

The criteria for pruning the tree play an important role in determining the structure of the resulting filter bank.

Wavelet packets are practically feasible; one needs alternate criteria for speeding up the pruning.

The entropy used in this pruning is an additive function, but it is not directly related to information.

References

[1] Sony Akkarakaran, P.P. Vaidyanathan, “Principal component filter banks- Existence issues and applications to modulated filter banks”, IEEE ISCAS –May 2000, pp. I-523-526

[2] P.P. Vaidyanathan, “Theory of optimal subband coders”, IEEE Trans. on Sig. Proc., Vol. 46, No. 6, June, 1998

[3] P.P. Vaidyanathan, “The best basis problem, compaction filters and PCFB design problems”, IEEE ICAS, Orlando, Florida, June, 1999.

[4] A. Kirac, P.P. Vaidyanathan, “Efficient methods of optimal FIR compaction filters for M-channel FIR subband coders”, Proc. of 30th ASILMORE conf. on Signals, Systems and Computers, 1996

[5] Ronald R. Coifman, M. V. Wickerhauser, “Entropy-based Algorithms for best basis selection”, IEEE Trans. on. Info. Th., Vol. 38, No. 2, March, 1992, pp. 713-718