## Discrete Wavelet Transform and Filter Bank

Given a 1D signal of length N, {f (n), n = 0,..., N — 1}, the discrete orthogonal wavelet transform can be organized as a sequence of discrete functions according to the scale parameter s = 2j:

with

{Ljf, {Wjf}M,,j]}, where LJf = Lf(2Jn, 2J) and Wjf = Wf (2jn, 2j). I j 2 I downsampling by 2

Figure 6.2: Illustration of orthogonal wavelet transform of a discrete signal f (n) with CMF. A two-level expansion is shown.

I j 2 I downsampling by 2

Figure 6.2: Illustration of orthogonal wavelet transform of a discrete signal f (n) with CMF. A two-level expansion is shown.

Wavelet coefficients Wjf at scale s = 2j have a length of N/2j and the largest decomposition depth J is bounded by the signal length N as (sup( J) = log2 N).

For fast implementation (such as filter bank algorithms), a pair of conjugate mirror filters (CMF) h and g can be constructed from the scaling function \$ and wavelet function ^ as follows:

h[n] = |-1= ^2) 'M - «)) and g[n] = |-i= ^2) 'W - «)) • (6.12) A conjugate mirror filter k satisfies the following relation:

It can be proven that h is a low-pass filter and g is a high-pass filter. The discrete orthogonal wavelet decomposition in Eq. (6.11) can be computed by applying these two filters to the input signal and recursively decomposing the low-pass band, as illustrated in Fig. 6.2. A detailed proof can be found in .

For orthogonal basis, the input signal can be reconstructed from wavelet coefficients computed in Eq. (6.11) using the same pair of filters, as illustrated in Fig. 6.3.

 î 2 h î 2 HMQ- Figure 6.3: Illustration of inverse wavelet transform implemented with CMF. A two-level expansion is shown. It is easy to prove that the total amount of data after a discrete wavelet expansion as shown in Fig. 6.2 has the same length to the input signal. Therefore, such transform provides a compact representation of the signal suited to data compression as wavelet transform provides a better spatial-frequency localization. On the other hand, since the data was downsampled at each level of expansion, such transform performs poorly on localization or detection problems. Mathematically, the transform is variant under translation of the signal (i.e. is dependent on the downsampling scheme used during the decomposition), which makes it less attractive for analysis of nonstationary signals. In image analysis, translation invariance is critical to the preservation of all the information of the signal and a redundant representation needs to be applied. In the dyadic wavelet transform framework proposed by Mallat et al. , sampling of the translation parameter was performed with the same sampling period as that of the input signal in order to preserve translation invariance. A more general framework of wavelet transform can be designed with different reconstruction and decomposition filters that form a biorthogonal basis. Such generalization provides more flexibility in the design of the wavelet functions. In that case, similar to Eq. (6.11), the discrete dyadic wavelet transform of a signal s(n) is defined as a sequence of discrete functions: where SMs(n) = s*\$M(n) represents the DC component, or the coarsest information from the input signal. Given a pair of wavelet function ^ (x) and reconstruction function x (x), the discrete dyadic wavelet transform (decomposition and reconstruction) can be implemented with a fast filter bank scheme using a pair of decomposition filters H, G and a reconstruction filter K: 0(2«) = e-imsH(m)4>(m), f(2rn) = e-i«sG («)\$(«), x (2«) = eimsK («)£(«), where s is a ^ (x)-dependent sampling shift. The three filters satisfy: Defining Fs(w) = e iwsF(w), where F is H, G, or K, we can construct a filter bank implementation of the discrete dyadic wavelet transform as illustrated in Figure 6.4: Filter bank implementation of a one-dimensional discrete dyadic wavelet transform decomposition and reconstruction for three levels of analysis. H*(m) denotes the complex conjugate of Hs((o). Fig. 6.4. Filters F(2m a>) defined at level m + 1 (i.e., filters applied at wavelet scale 2m) are constructed by inserting 2m — 1 zeros between subsequent filter coefficients from level 1 (F(«)). Noninteger shifts at level 1 are rounded to the nearest integer. This implementation design is called "algorithme à trous" [17, 18] and has a complexity that increases linearly with the number of analysis levels. In image processing applications, we often deal with two, three, or even higher dimensional data. Extension of the framework to higher dimension is quite straightforward. Multidimensional wavelet bases can be constructed with tensor products of separable basis functions defined along each dimension. In that context, an N-dimensional discrete dyadic wavelet transform with M analysis levels is represented as a set of wavelet coefficients: where W^yS = {s, ^m) represents the detailed information along the kth coordinate at scale m. The wavelet basis is dilated and translated from a set of separable wavelet functions ^k, k = 1,..., N, for example in 3D: ^m,»1,n>,»3(X' y' Z) = 23m/2 * I 2m ' 2m ' 2m )' = Figure 6.5: Filter bank implementation of a multidimensional discrete dyadic wavelet transform decomposition (left) and reconstruction (right) for two levels of analysis. In this framework, reconstruction with an N-dimensional dyadic wavelet transform requires a nonseparable filter LN to compensate the interdimension correlations. This is formulated in a general context as: N N J^K (o )G(O )Ln (O,w-1, vi+1, • ••,( ) + n i H( )l2 = L (6.19) i=1 i=1 Figure 6.5 illustrates a filter bank implementation with a multidimensional discrete dyadic wavelet transform. For more details and discussions we refer to