Open access

Shift Invariant Discrete Wavelet Transforms

Written By

Hannu Olkkonen and Juuso T. Olkkonen

Submitted: 30 November 2010 Published: 29 August 2011

DOI: 10.5772/23828

From the Edited Volume

Discrete Wavelet Transforms - Algorithms and Applications

Edited by Hannu Olkkonen

Chapter metrics overview

3,297 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.

Advertisement

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)

H0(z)=(1+z1)KP(z)H1(z)=zNH0(z1)G0(z)=H1(z)G1(z)=H0(z)E1

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

H0(z)G0(z)+H1(z)G1(z)=2zNH0(z)G0(z)+H1(z)G1(z)=0E2

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

H(z)=nhnznH(ω)=nhnejωnE3

Correspondingly, we have the relations

H(z)H(ωπ)H(z1)H(ωπ)E4

where * denotes complex conjugation. In M-stage CQF tree the frequency response of the

wavelet sequence is

WM(ω)=H1(ω/2)k=2MH0(ω/2k)E5

Figure 2.

The tree structured implementation of the real-valued CQF DWT, which yields the wavelet sequences w1[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

H¯0(ω)=ejϕ(ω)H0(ω)E6

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

H1(ω)=ejωNH0*(ωπ)E7

and

H¯1(ω)=ejωNH¯0*(ωπ)=ejωNejϕ(ωπ)H0*(ωπ)=ejϕ(ωπ)H1(ω)E8

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

W¯M(ω)=H¯1(ω/2)k=2MH¯0(ω/2k)=ejϕ(ω/2π)H1(ω/2)k=2Mejϕ(ω/2k)H0(ω/2k)=ejϕ(ω/2π)ejk=2Mϕ(ω/2k)H1(ω/2)k=2MH0(ω/2k)=ejθWM(ω)E9

where the phase function

θ=ϕ(ω/2π)k=2Mϕ(ω/2k)E10

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

ϕ(ω)=ω/2E11

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

θ=ω/2π2ωk=2M12k+1=π2+ω2M+1E12

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

WMC(ω)=WM(ω)+jW¯M(ω)E13

The requirement for the shift-invariance comes from

W¯M(ω)={ψM(ω)}E14

where denotes the Hilbert transform. The frequency response of the Hilbert transform operator is defined as

(ω)=jsgn(ω)E15

where the sign function is defined as

sgn(ω)={1forω01forω<0E16

In this work we apply the Hilbert transform operator in the form

(ω)=ejπ/2sgn(ω)E17

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 πωπ

θ(ω)=D(ω)π/2+ω/2=π/2E18

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.

Advertisement

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

H0(z)=(1+z1)LQ(z)H1(z)=(1z1)MR(z)G0(z)=H1(z)G1(z)=H0(z)E19

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

H0(z)G0(z)+H1(z)G1(z)=2zDH0(z)G0(z)+H1(z)G1(z)=0E20
Advertisement

4. Relationships between CQF and BF wavelet transforms

In the following treatment we use a short notation for the binomial term

BK(z)=(1+z1)KE21

which appears both in the CQF and BF banks. Using the binomial term the CQF bank can be written as

H0(z)=BK(z)P(z)H1(z)=zN(z)KBK(z)P(z1)G0(z)=zNzKBK(z)P(z1)G1(z)=BK(z)P(z)E22

For the PR condition of the CQF bank ( ) the following is valid for K odd

B2K(z)P(z)P(z1)B2K(z)P(z)P(z1)=2zNE23

On the other hand, the PR condition of the BF bank gives

BL+M(z)Q(z)R(z)BL+M(z)Q(z)R(z)=2zDE24

Both PR conditions are identical if we state2K=L+M. Then we have

P(z)P(z1)zN+D=Q(z)R(z)E25

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

H¯0(z)=F(z)H0(z)H¯1(z)=F1(z)H1(z)G¯0(z)=F1(z)G0(z)G¯1(z)=F(z)G1(z)E26

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

Advertisement

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

(ω)=ejπ/2sgn(ω)E27

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

D(z)=z0.5=k=1pck+z11+ckz1=zNA(z1)A(z)=cN+cN1++zN1+c1z1++cNzNE28

where the ck coefficients are optimized so that the frequency response follows approximately

D(ω)=ejω/2E29

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

D(z)=A(z)B(z)E30

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

D(ωπ)=ej(ωπ)/2E31

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

D(ω)D(ωπ)=ejω/2ej(ωπ)/2=ejπ/2E32

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

(z)=A(z)B(z)A(z)B(z)E33

The Hilbert transform filter is inserted in the BF bank using the result of Lemma 1 (26). The modified prototype BF filter bank is

H¯0(z)=(z)H0(z)H¯1(z)=1(z)H1(z)G¯0(z)=1(z)G0(z)G¯1(z)=(z)G1(z)E34

The BF bank (34) can be highly simplified by noting the following equivalents concerning on (33)

1(z)=(z)1(z)=(z)E35

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

H¯0(z)=(z)H0(z)H¯1(z)=(z)H1(z)G¯0(z)=(z)G0(z)G¯1(z)=(z)G1(z)E36

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

a(z)=1+j(z)E37

By filtering the real-valued signal x[n] by the Hilbert transform operator results in an analytic signal

xa[n]=x[n]+j{x[n]}E38

whose magnitude response is zero at negative side of the frequency spectrum

Xa(ω)={2X(ω)0ω<π0πω<0E39

The wavelet sequence is obtained by decimation of the high-pass filtered analytic signal

W(ω)=[Xa(ω)H1(ω)]2=Wa(ω)2=12Xa(ω/2)H1(ω/2)E40

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.

Advertisement

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 1 and the equivalence (35) of the Hilbert transform filter (33). In many respects the BF bank (36) outperforms the previous nearly shift invariant DWT approaches.

References

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