Open Access is an initiative that aims to make scientific research freely available to all. To date our community has made over 100 million downloads. It’s based on principles of collaboration, unobstructed discovery, and, most importantly, scientific progression. As PhD students, we found it difficult to access the research we needed, so we decided to create a new Open Access publisher that levels the playing field for scientists across the world. How? By making research easy to access, and puts the academic needs of the researchers before the business interests of publishers.
We are a community of more than 103,000 authors and editors from 3,291 institutions spanning 160 countries, including Nobel Prize winners and some of the world’s most-cited researchers. Publishing on IntechOpen allows authors to earn citations and find new collaborators, meaning more people see your work not only from your own field of study, but from other related fields too.
To purchase hard copies of this book, please contact the representative in India:
CBS Publishers & Distributors Pvt. Ltd.
www.cbspd.com
|
customercare@cbspd.com
Department of Applied Physics, University of Eastern Finland, Kuopio, VTT Technical Research Centre of Finland, VTT, Finland
Juuso T. Olkkonen
Department of Applied Physics, University of Eastern Finland, Kuopio, VTT Technical Research Centre of Finland, VTT, Finland
*Address all correspondence to:
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[n−0.5], the corresponding wavelets are a Hilbert transform pair. In z-transform domain we should be able to construct the scaling filters H0(z) andz−0.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.
where P(z)is a polynomial inz−1. 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
H(z)=∑nhnz−n⇒H(ω)=∑nhne−jωnE3
Correspondingly, we have the relations
H(−z)⇒H(ω−π)H(−z−1)⇒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(ω)=e−jϕ(ω)H0(ω)E6
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
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ω≥0−1forω<0E16
In this work we apply the Hilbert transform operator in the form
ℋ(ω)=e−jπ/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)=z−1/2, which has the frequency responseD(ω)=e−jω/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.
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 inz−1. 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
For the PR condition of the CQF bank ( ) the following is valid for K odd
B2K(z)P(z)P(z−1)−B2K(−z)P(−z)P(−z−1)=2z−NE23
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)=2z−DE24
Both PR conditions are identical if we state2K=L+M. Then we have
P(z)P(z−1)z−N+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(z−1), which is a symmetrical polynomial. The roots of the product filter P(z)P(z−1) 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(z−1) 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
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
ℋ(ω)=e−jπ/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)=z−0.5. The classical approach for design of the half-sample delay filter D(z)is based on the Thiran all-pass interpolator
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 12e−jωτ/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.
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.DaubechiesI.1988 Orthonormal bases of compactly supported wavelets. Commmun. Pure Appl. Math.,41909 EOF996 EOF
2.ITU-T2000 Recommend. T.800-ISO DCD15444-1: JPEG2000 Image Coding System. International Organization for Standardization, ISO/IEC JTC! SC29/WG1.
3.JohanssonH.LowenborgP.2002 Reconstruction of nonuniformy sampled bandlimited signals by means of digital fractional delay filters, IEEE Trans. Signal Process., 501127572767
4.KingsburyN. G.2001 Complex wavelets for shift invariant analysis and filtering of signals. J. Appl. Comput. Harmonic Analysis.10234 EOF253 EOF
5.LaaksoT.ValimakiV.KarjalainenM.LaineU. K.1996 Splitting the unit delay. Tools for fractional delay filter design, IEEE Signal Processing Magazine, 3080
6.OlkkonenH.PesolaP.OlkkonenJ. T.2005 Efficient lifting wavelet transform for microprocessor and VLSI applications. IEEE Signal Process. Lett.122120 EOF122 EOF
7.OlkkonenH.PesolaP.OlkkonenJ. T.ZhouH.2006 Hilbert transform assisted complex wavelet transform for neuroelectric signal analysis. J. Neuroscience Meth.151106 EOF113 EOF
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.OlkkonenH.OlkkonenJ. T.PesolaP.2007b FFT-based computation of shift invariant analytic wavelet transform. IEEE Signal Process. Lett.143177 EOF180 EOF
10.OlkkonenH.OlkkonenJ. T.2008 Simplified biorthogonal discrete wavelet transform for VLSI architecture design. Signal, Image and Video Process.2101 EOF105 EOF
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.PeiS. C.WangP. H.2004 Closed-form design of all-pass fractional delay, IEEE Signal Processing Letters, 1110788791
13.SelesnickI. W.2002 The design of approximate Hilbert transform pairs of wavelet bases. IEEE Trans. Signal Process.5051144 EOF1152 EOF
14.SmithM. J. T.BarnwellT. P.1986 Exaxt reconstruction for tree-structured subband coders. IEEE Trans. Acoust. Speech Signal Process.34
15.SweldensW.1988 The lifting scheme: A construction of second generation wavelets. SIAM J. Math. Anal.29511 EOF546 EOF
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 2010Published: 29 August 2011