Open access peer-reviewed chapter

Shift Invariant Discrete Wavelet Transforms

Written By

Hannu Olkkonen and Juuso T. Olkkonen

Submitted: November 30th, 2010 Reviewed: March 16th, 2011 Published: August 29th, 2011

DOI: 10.5772/23828

Chapter metrics overview

3,148 Chapter Downloads

View Full Metrics

1. Introduction

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 x[n]and the corresponding time shifted signalx[nτ], whereτ[0,1], 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: h0[n]andh0[n0.5], the corresponding wavelets are a Hilbert transform pair. In z-transform domain we should be able to construct the scaling filters H0(z)andz0.5H0(z). 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 changeN=1to2.

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.

Figure 1.

The analysis and synthesis parts of the real-valued CQF DWT bank.


2. Design of the shift invariant CQF

The CQF DWT bank consists of the H0(z)and H1(z)analysis filters and G0(z)and G1(z)synthesis filters for N odd (Fig. 1)


where P(z)is a polynomial inz1. The scaling filter H0(z)has the Kth order zero atω=π. The wavelet filter H1(z)has the Kth order zero atω=0, 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


Figure 2.

The tree structured implementation of the real-valued CQF DWT, which yields the wavelet sequencesw1[n],w2[n]...wM[n]and one scaling sequencesM[n].

Next we construct a phase shifted parallel CQF filter bank consisting of the scaling filter H¯0(z)and the wavelet filterH¯1(z). Let us suppose that the scaling filters in parallel CQF trees are related as


where ϕ(ω)is a 2πperiodic phase function. Then the corresponding CQF wavelet filters are related as




We may easily verify that the phase shifted CQF bank (6,8) obeys the PR condition (2). Correspondingly, the frequency response of the M-stage CQF wavelet sequence is


where the phase function


If we select the phase function ϕ(ω)in (6) as


the scaling filters (6) are half-sample delayed versions of each other. By inserting (11) in (10) we have


The wavelet sequences (5,9) yielded by the CQF bank (1) and the phase shifted CQF bank (6,8) can be interpreted as real and imaginary parts of the complex wavelet sequence


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ω/2M+1, 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ω/2. The elimination of the error term can be made by prefiltering the analyzed signal by the half-sample delay operatorD(z)=z1/2, which has the frequency responseD(ω)=ejω/2. 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.

Figure 3.

The two equivalents for transferring the phase function in front of the phase shifted CQF tree.


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 H0(z)has the Lth order zero atω=π. The wavelet filter H1(z)has the Kth order zero atω=0, correspondingly. Q(z)andR(z)are polynomials inz1. The low-pass and high-pass reconstruction filters G0(z)and G1(z)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 state2K=L+M. 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 Q(z)andR(z)can be found by factoringP(z)P(z1), which is a symmetrical polynomial. The roots of the product filter P(z)P(z1)should be optimally divided so that both Q(z)and R(z)are low-pass. Then R(z)is high-pass. If the BF bank is known it is easy to factor Q(z)R(z)into P(z)andP(z1)using some spectral factorization method. An important result is related to the modification of the BF bank (Olkkonen & Olkkonen, 2007a).

Lemma 1:If the scaling filterH0(z), the wavelet filter H1(z)and the reconstruction filters G0(z)and G1(z)in FB bank (19) have a perfect reconstruction property (20), the following modified FB bank obeys also the PR relation


where F(z)is any polynomial inz1. Proof is yielded by direct insertion (26) to PR condition (20).


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(z), which has the frequency response


where sgn(ω)=1for ω0and sgn(ω)=1forω<0. We describe a novel method for constructing the Hilbert transform filter based on the half-sample delay filterD(z)=z0.5. The classical approach for design of the half-sample delay filter D(z)is based on the Thiran all-pass interpolator


where the ckcoefficients are optimized so that the frequency response follows approximately


In this work we define the half-sample delay filter more generally as


The quadrature mirror filter D(z)has the frequency response


The frequency response of the filter D(z)D1(z)is, correspondingly


Comparing (27) and using the IIR filter notation (30) we obtain the Hilbert transform filter as


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 BF bank (34) can be highly simplified by noting the following equivalents concerning on (33)


By inserting (35) in (34) we obtain a highly simplified FB bank


The modified BF bank (36) can be realized by the Hilbert transform filter(z), which works as a prefilter for the analysed signal. The Hilbert transform filter (z)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 x[n]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 Wa(ω)contains frequency components only in the range0ω<π, but the frequency spectrum of the decimated analytic signal has the frequency band0ω<2π. 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 x[nτ]is 12ejωτ/2Wa(ω/2)and the corresponding wavelet sequence isw[nτ/2]. The energy (absolute value) of the decimated wavelet coefficients is12|W(ω/2)|, 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 D(z)=A(z)/B(z)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).

Table I.

The half-delay filter polynomials for the B-spline transform order K=4, 5 and 6.

Figure 4.

Magnitude and phase spectra of the Hilbert transform filter yielded by the fourth order B-spline transform.


6. Conclusion

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 ω/2M+1(12) compared with the ideal phase responseθ(ω)=π/2. 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 D(z)=A(z)/B(z)(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 Lemma 1and the equivalence (35) of the Hilbert transform filter (33). In many respects the BF bank (36) outperforms the previous nearly shift invariant DWT approaches.


  1. 1. DaubechiesI.1988Orthonormal bases of compactly supported wavelets.Commmun. Pure Appl. Math.,41909 EOF996 EOF
  2. 2. ITU-T2000Recommend. T.800-ISO DCD15444-1: JPEG2000 Image Coding System. International Organization for Standardization, ISO/IEC JTC! SC29/WG1.
  3. 3. JohanssonH.LowenborgP.2002Reconstruction of nonuniformy sampled bandlimited signals by means of digital fractional delay filters,IEEE Trans. Signal Process.,501127572767
  4. 4. KingsburyN. G.2001Complex wavelets for shift invariant analysis and filtering of signals.J. Appl. Comput. Harmonic Analysis.10234 EOF253 EOF
  5. 5. LaaksoT.ValimakiV.KarjalainenM.LaineU. K.1996Splitting the unit delay. Tools for fractional delay filter design,IEEE Signal Processing Magazine,3080
  6. 6. OlkkonenH.PesolaP.OlkkonenJ. T.2005Efficient lifting wavelet transform for microprocessor and VLSI applications.IEEE Signal Process. Lett.122120 EOF122 EOF
  7. 7. OlkkonenH.PesolaP.OlkkonenJ. T.ZhouH.2006Hilbert transform assisted complex wavelet transform for neuroelectric signal analysis.J. Neuroscience Meth.151106 EOF113 EOF
  8. 8. OlkkonenH.OlkkonenJ. T.2007aHalf-delay B-spline filter for construction of shift-invariant wavelet transform.IEEE Trans. Circuits and Systems II.547611 EOF615 EOF
  9. 9. OlkkonenH.OlkkonenJ. T.PesolaP.2007bFFT-based computation of shift invariant analytic wavelet transform.IEEE Signal Process. Lett.143177 EOF180 EOF
  10. 10. OlkkonenH.OlkkonenJ. T.2008Simplified biorthogonal discrete wavelet transform for VLSI architecture design.Signal, Image and Video Process.2101 EOF105 EOF
  11. 11. PeiT. S. C.TsengC. C.2003An efficient design of a variable fractional delay filter using a first-order differentiator,IEEE Signal Processing Letters,1010307310
  12. 12. PeiS. C.WangP. H.2004Closed-form design of all-pass fractional delay,IEEE Signal Processing Letters,1110788791
  13. 13. SelesnickI. W.2002The design of approximate Hilbert transform pairs of wavelet bases.IEEE Trans. Signal Process.5051144 EOF1152 EOF
  14. 14. SmithM. J. T.BarnwellT. P.1986Exaxt reconstruction for tree-structured subband coders.IEEE Trans. Acoust. Speech Signal Process.34
  15. 15. SweldensW.1988The lifting scheme: A construction of second generation wavelets.SIAM J. Math. Anal.29511 EOF546 EOF
  16. 16. TsengC. C. .2006Digital integrator design using Simpson rule and fractional delay filter,IEEE Proc. Vision, Image and Signal Process.,15317985

Written By

Hannu Olkkonen and Juuso T. Olkkonen

Submitted: November 30th, 2010 Reviewed: March 16th, 2011 Published: August 29th, 2011