Pyramidal algorithm

Fig. 40.43. Waveforms for the discrete wavelet transform using the Haar wavelet for an 8-points long signal with the scheme of Mallat s pyramid algorithm for calculating the wavelet transform coefficients.

This is the principle of the pyramidal algorithm developed by Mallat [20], which is computationally more efficient. Continuing the calculations according to this algorithm, the four a components are input to a 4x4 level transformation matrix, giving the level-3 components ... 

Having a closer look at the pyramid algorithm in Fig. 40.43, we observe that it sequentially analyses the approximation coefficients. When we do analyze the detail coefficients in the same way as the approximations, a second branch of decompositions is opened. This generalization of the discrete wavelet transform is called the wavelet packet transform (WPT). Further explanation of the wavelet packet transform and its comparison with the DWT can be found in [19] and [21]. The final results of the DWT applied on the 16 data points are presented in Fig. 40.44. The difference with the FT is very well demonstrated in Fig. 40.45 where we see that wavelet describes the locally fast fluctuations in the signal and wavelet a the slow fluctuations. An obvious application of WT is to denoise spectra. By replacing specific WT coefficients by zero, we can selectively remove... 

We will go through a numerical example of the pyramid algorithm for a signal of only 16 points. We will adopt the following code. The output of the LP filter, with impulse response (11) will be called a, for approximation, and that of the HP filter (1 -1) will be called d". for detail. The results are collected in Table 1. The first element of the column a" is the sum of the first two elements of the signal. The second element is the sum of the elements three and four etc. In the same way, the first element of the column "d" is the difference between the first two elements of the signal and so forth. 

Fig. 11 Power spectra of the different stages in the pyramid algorithm, (a) first application of a pair of filters to 16-point signal (h) the filters applied to the low-frequency part of (a) (c) and (d) further cut up of the lower frequencies analogous to (h).

Fig. 13 Illustration of the application of the pyramid algorithm for the numerical example.

For an impulse response that differs from zero on, let us say, four points, several aspects of the pyramid algorithm are less obvious. We need to be able to drop half the points and still represent the signal using the output of the LP and HP filters. In other words, we need to step the linear convolution of signal and impulse response by two points. The Haar wavelet basis is also special in the sense that, as the impulse responses are only two points wide, we do not lose points at the extremes when performing a linear convolution. For wider impulse responses, something has to be done about those extremes, e.g. a circular convolution, which puts an additional constraint on the shapes of those impulse responses. 

Fig. 14 (a) The pyramid algorithm a.s an upside-down pyramid of boxes (b) The wavelet packet decision tree as the full. set of boxes. 

We first consider redefining a multiresolution to cater for situations when functions are rescaled by a general factor m > 2 and then show how the fast wavelet transform (or pyramidal algorithm) is performed for higher multiplicity wavelets. 

Fig. 9.13. Mallat s pyramidal algorithm used to implement the DWT. Approximation and detail vectors are indicated by cA and cD respectively subindices denote decomposition level.

Figure 8 Overview of the DWT and multiresolution analysis scheme known as the pyramid algorithm/ The original signal is separated into low-frequency and high-frequency components, which comprise the signal approximation and detail information, respectively. Each level decomposes the approximation information further, making each level of detail (dj) a separate frequency band.

Figure 9 This series illustrates multiresolution analysis, separating out the high-frequency information at each level of transformation in the pyramid algorithm (illustrated in Figure 8). Note that the approximation (a,) signal in higher level iterations contain much less detailed information, because this has been removed and encoded into wavelet detail coefficients at each DWT deconstruction step. To reconstruct the original signal, the inverse DWT needs the wavelet coefficients of a given approximation level / (ai) and all detail information leading to that level (di i).

Figure 11 Illustrated here is the WPT. The pyramid algorithm enumerates a single branch (see Figure 8), whereas the WPT enumerates the complete tree of iterative decompositions. At each level, both the approximation and the detail information are separated into low-frequency and high-frequency components.

Figure 12 The signal representation or basis of the (a) pyramid algorithm and two examples (b, c) of selected representations from the entire hierarchy computed by the WPT are shown. The WPT allows for optimal signal basis selection by enumerating the complete decomposition tree, so that all signal representations can be evaluated.

Figure 16 WCDs are generated as illustrated for each electron density-derived property. The property distribution is deconstructed using the DWT (pyramid algorithm), allowing the isolation of the lowest frequency and coarsest approximation coefficients (ay and dy). These few coefficients are sufficient to reconstruct most of the original signal (via the inverse DWT) and contain the vital molecular property information needed for modeling. The WCDs replace the original TAE histogram descriptors and are orthogonal, consistent, and representative.

---