The discrete wavelet transform (DWT) has an established position in processing of signals and images in research and industry. The first DWT structures were based on the compactly supported conjugate quadrature filters (CQFs) (Smith & Barnwell, 1986; Daubechies, 1988). However, a drawback in CQFs is related to the nonlinear phase effects such as image blurring and spatial dislocations in multi-scale analyses. On the contrary, in biorthogonal discrete wavelet transform (BDWT) the scaling and wavelet filters are symmetric and linear phase. The biorthogonal filters (BFs) are usually constructed by a ladder-type network called lifting scheme (Sweldens, 1988). The procedure consists of sequential down and uplifting steps and the reconstruction of the signal is made by running the lifting network in reverse order. Efficient lifting BF structures have been developed for VLSI and microprocessor environment (Olkkonen et al. 2005; Olkkonen & Olkkonen, 2008). The analysis and synthesis filters can be implemented by integer arithmetics using only register shifts and summations. Many BDWT-based data and image processing tools have outperformed the conventional discrete cosine transform (DCT) -based approaches. For example, in JPEG2000 Standard (ITU-T, 2000), the DCT has been replaced by the lifting BFs.
One of the main difficulties in DWT analysis is the dependence of the total energy of the wavelet coefficients in different scales on the fractional shifts of the analysed signal. If we have a discrete signal and the corresponding time shifted signal, where, there may exist a significant difference in the energy of the wavelet coefficients as a function of the time shift. Kingsbury (2001) proposed a nearly shift invariant method, where the real and imaginary parts of the complex wavelet coefficients are approximately a Hilbert transform pair. The energy (absolute value) of the wavelet coefficients equals the envelope, which provides smoothness and approximate shift-invariance. Selesnick (2002) observed that using two parallel CQF banks, which are constructed so that the impulse responses of the scaling filters have half-sample delayed versions of each other: and, the corresponding wavelets are a Hilbert transform pair. In z-transform domain we should be able to construct the scaling filters and. For design of the scaling filters Selesnick (2002) proposed a spectral factorization method based on the half delay all-pass Thiran filters. As a disadvantage the scaling filters do not have coefficient symmetry and the nonlinearity interferes with the spatial timing in different scales and prevents accurate statistical correlations. Gopinath (2003) generalized the idea for N parallel filter banks, which are phase shifted versions of each other. Gopinath showed that increasing N the shift invariance of the wavelet transform improves. However, the greatest advantage comes from the change.
In this book chapter we review the methods for constructing the shift invariant CQF and BF wavelet sequences. We describe a dual-tree wavelet transform, where two parallel CQF wavelet sequences form a Hilbert pair, which warrants the shift invariance. Next we review the construction of the BF wavelets and show the close relationship between the CQF and BF wavelets. Then we introduce a novel Hilbert transform filter for constructing shift invariant dual-tree BF banks.
2. Design of the shift invariant CQF
The CQF DWT bank consists of the and analysis filters and and synthesis filters for N odd (Fig. 1)
where is a polynomial in. The scaling filter has the Kth order zero at. The wavelet filter has the Kth order zero at, correspondingly. The filters are related via the perfect reconstruction (PR) condition
The tree structured implementation of the real-valued CQF filter bank is described in Fig. 2. Let us denote the frequency response of the z-transform filter as
Correspondingly, we have the relations
where * denotes complex conjugation. In M-stage CQF tree the frequency response of the
wavelet sequence is
Next we construct a phase shifted parallel CQF filter bank consisting of the scaling filter and the wavelet filter. Let us suppose that the scaling filters in parallel CQF trees are related as
where is a periodic phase function. Then the corresponding CQF wavelet filters are related as
where the phase function
If we select the phase function in (6) as
The requirement for the shift-invariance comes from
where denotes the Hilbert transform. The frequency response of the Hilbert transform operator is defined as
where the sign function is defined as
In this work we apply the Hilbert transform operator in the form
Our result (12) reveals that if the scaling filters are the half-sample delayed versions of each other, the resulting wavelet sequences are not precisely Hilbert transform pairs. There occurs a phase error term, which depends both in frequency and the stage M of the wavelet sequence. In sequel we describe a novel procedure for elimination this error. We move the phase error in front of the phase shifted CQF tree using the equivalence described in Fig. 3. Then the error term reduces to. The elimination of the error term can be made by prefiltering the analyzed signal by the half-sample delay operator, which has the frequency response. The total phase function is then for
which warrants that the M-stage CQF wavelet sequence and the phase error corrected sequence are a Hilbert transform pair.
3. Biorthogonal discrete wavelet transform
The first DWT structures were based on the compactly supported conjugate quadrature filters (CQFs) (Smith & Barnwell, 1986), which have unavoided nonlinear phase effects in multi-resolution analyses. On the contrary, in biorthogonal discrete wavelet transform (BDWT) the scaling and wavelet filters are symmetric and linear phase. The two-channel biorthogonal filter (BF) bank is of the general form
where the scaling filter has the Lth order zero at. The wavelet filter has the Kth order zero at, correspondingly. andare polynomials in. The low-pass and high-pass reconstruction filters and are defined as in the CQF bank. For two-channel biorthogonal filter bank the PR relation is
4. Relationships between CQF and BF wavelet transforms
In the following treatment we use a short notation for the binomial term
which appears both in the CQF and BF banks. Using the binomial term the CQF bank can be written as
For the PR condition of the CQF bank ( ) the following is valid for K odd
On the other hand, the PR condition of the BF bank gives
Both PR conditions are identical if we state. Then we have
The above relation (25) gives a novel way to design of the biorthogonal wavelet filter bank based on the CQF bank and vice versa. The polynomials can be found by factoring, which is a symmetrical polynomial. The roots of the product filter should be optimally divided so that both and are low-pass. Then is high-pass. If the BF bank is known it is easy to factor into using some spectral factorization method. An important result is related to the modification of the BF bank (Olkkonen & Olkkonen, 2007a).
5. Hilbert transform filter for construction of shift invariant BF bank
In BF bank the shift invariance is not an inbuilt property as in CQF bank. In the following we define the Hilbert transform filter, which has the frequency response
where for and for. We describe a novel method for constructing the Hilbert transform filter based on the half-sample delay filter. The classical approach for design of the half-sample delay filter is based on the Thiran all-pass interpolator
In this work we define the half-sample delay filter more generally as
The quadrature mirror filter has the frequency response
The frequency response of the filter is, correspondingly
The Hilbert transform filter is inserted in the BF bank using the result of Lemma 1 (26). The modified prototype BF filter bank is
The modified BF bank (36) can be realized by the Hilbert transform filter, which works as a prefilter for the analysed signal. The Hilbert transform filter works as a postfilter in the reconstruction stage, respectively. The wavelet sequences yielded by the two parallel BF trees can be considered to form a complex wavelet sequence by defining the Hilbert transform operator
By filtering the real-valued signal by the Hilbert transform operator results in an analytic signal
whose magnitude response is zero at negative side of the frequency spectrum
The wavelet sequence is obtained by decimation of the high-pass filtered analytic signal
The result (40) means that the decimation does not produce aliasing but the frequency spectrum is dilated by two. The frequency spectrum of the undecimated wavelet sequence contains frequency components only in the range, but the frequency spectrum of the decimated analytic signal has the frequency band. Hence, the decimation does not produce overlapping and leakage (aliasing) to the negative frequency range. A key feature of the dual-tree wavelet transform is the shift invariance of the decimated analytic wavelet coefficients. The Fourier transform of the decimated wavelet sequence of the fractionally delayed signal is and the corresponding wavelet sequence is. The energy (absolute value) of the decimated wavelet coefficients is, which does not depend on the fractional delay. If the wavelet filter has linear phase the wavelet coefficients are shift invariant in respect to their energy content.
An integer-valued half-delay filter is obtained by the B-spline transform (see details Olkkonen & Olkkonen, 2007b). Table I gives the polynomial coefficients for the B-spline orders K=4, 5 and 6. The frequency response of the Hilbert transform filter constructed by the fourth order B-spline (Fig. 4) shows a maximally flat magnitude spectrum. The phase spectrum corresponds to an ideal Hilbert transformer (15).
It is well documented that the real-valued DWTs are not shift invariant, but small fractional time-shifts may introduce significant differences in the energy of the wavelet coefficients. Kingsbury (2001) showed that the shift invariance is improved by using two parallel filter banks, which are designed so that the wavelet sequences constitute real and imaginary parts of the complex analytic wavelet transform. The dual-tree discrete wavelet transform has been shown to outperform the real-valued DWT in a variety of applications such as denoising, texture analysis, speech recognition, processing of seismic signals and neuroelectric signal analysis (Olkkonen et al. 2006; Olkkonen et al. 2007b).
Selesnick (2002) made an observation that a half-sample time-shift between the scaling filters in parallel CQF banks is enough to produce the shift invariant wavelet transform. In this work we reanalysed the condition and observed a phase-error term (12) compared with the ideal phase response. The phase error attains s highest value at high frequency range and small stage M of the wavelet sequence. Fortunately, we showed in this book chapter that the phase error term can be cancelled by adding a half-delay prefilter in front of the CQF chain. For this purpose the half-delay filter (30, Table I) constructed by the B-spline transform (Olkkonen & Olkkonen, 2007a) is well suited. In addition, there exists many other design methods for half-delay filters (see e.g. Laakso et al. 1996; Johansson & Lowenborg, 2002; Pei & Tseng, 2003; Pei & Wang, 2004; Tseng, 2006).
In multi-scale DWT analysis the complex wavelet sequences should be shift invariant. This requirement is satisfied in the Hilbert transform-based approach (Olkkonen et al. 2006, Olkkonen et al. 2007b), where the signal in every scale is Hilbert transformed yielding strictly analytic and shift invariant transform coefficients. The procedure needs FFT-based computation which may be an obstacle in many digital signal processor realizations. To avoid this we conducted the novel shift invariant dual-tree BF bank (36) based on the Hilbert transform filter (33). This highly simplified BF bank is yielded by
Daubechies I. 1988Orthonormal bases of compactly supported wavelets.
ITU-T 2000Recommend. T.800-ISO DCD15444-1: JPEG2000 Image Coding System. International Organization for Standardization, ISO/IEC JTC! SC29/WG1.
Johansson H. Lowenborg P. 2002Reconstruction of nonuniformy sampled bandlimited signals by means of digital fractional delay filters,
Kingsbury N. G. 2001Complex wavelets for shift invariant analysis and filtering of signals.
Laakso T. Valimaki V. Karjalainen M. Laine U. K. 1996Splitting the unit delay. Tools for fractional delay filter design,
Olkkonen H. Pesola P. Olkkonen J. T. 2005Efficient lifting wavelet transform for microprocessor and VLSI applications.
Olkkonen H. Pesola P. Olkkonen J. T. Zhou H. 2006Hilbert transform assisted complex wavelet transform for neuroelectric signal analysis.
Olkkonen H. Olkkonen J. T. 2007aHalf-delay B-spline filter for construction of shift-invariant wavelet transform.
Olkkonen H. Olkkonen J. T. Pesola P. 2007bFFT-based computation of shift invariant analytic wavelet transform.
Olkkonen H. Olkkonen J. T. 2008Simplified biorthogonal discrete wavelet transform for VLSI architecture design.
Pei T. S. C. Tseng C. C. 2003An efficient design of a variable fractional delay filter using a first-order differentiator,
Pei S. C. Wang P. H. 2004Closed-form design of all-pass fractional delay,
Selesnick I. W. 2002The design of approximate Hilbert transform pairs of wavelet bases.
Smith M. J. T. Barnwell T. P. 1986Exaxt reconstruction for tree-structured subband coders.
Sweldens W. 1988The lifting scheme: A construction of second generation wavelets.
Tseng C. C. . 2006Digital integrator design using Simpson rule and fractional delay filter,