Wavelet Filter Banks Using Allpass Filters

1. Introduction

The discrete wavelet transform (DWT), which is implemented by a two band perfect reconstruction (PR) filter bank, has been applied extensively to digital signal processing, image processing, medical and health care, economy and so on [1, 2, 3, 4]. In many applications such as image processing, wavelets are required to be real since the signal is real-valued in general. We restrict ourselves to real-valued wavelet filter banks in this chapter.

In addition to orthogonality, one desirable property for wavelets is symmetry, which requires all filters in the filter bank to possess exactly linear phase, because the symmetric extension method is generally used to treat the boundaries of images [5, 6]. It is known in [1, 2, 3, 4] that finite impulse response (FIR) filters (corresponding to the compactly supported wavelets) can easily realize exactly linear phase. However, it is widely appreciated that the only FIR solution that produces a real orthogonal symmetric wavelet basis is the Haar wavelet, which is not continuous and the corresponding filter is of order 1 only that is not enough for many practical applications. To obtain wavelet filter banks with higher degrees of freedom, infinite impulse response (IIR) filters have been used to construct wavelet filter banks with some of the desired properties [7, 8, 9, 10, 11, 12]. Among the existing IIR wavelet filter banks, wavelet filter banks composed of allpass filters are attractive [7, 9, 10, 12], which can realize both of orthogonality and symmetry.

Allpass filter is a computationally efficient versatile signal processing building block and quite useful in many applications [13]. Allpass filter possesses unit magnitude at all frequencies (see Appendix) and is a basic scalar lossless building block. The interconnection of allpass filters has found numerous applications in practical filtering problems, such as low sensitivity filter structures, multirate filtering, filter banks and so on [7, 10, 12, 13]. The phase approximation of allpass filters has been also discussed in [13, 14, 15].

The lifting scheme proposed by W. Sweldens in [16, 17] is an efficient tool for constructing second generation wavelets, and has advantages such as faster implementation, fully in-place calculation, reversible integer-to-integer transforms, and so on. It has been proved in [18, 19] that every FIR wavelet filter bank can be decomposed into a finite number of lifting steps, thus this allows the construction of an integer version of the wavelet transform. Such integer wavelet transforms are invertible, and then are attractive in lossless coding applications. Due to these properties, the lifting implemantation has been adopted in the international standard JPEG2000 [5]. Conventionally, the lifting scheme is often used to construct a class of biorthogonal wavelet filter banks. It has been shown in [18] that orthogonal wavelet filter banks can also be realized by the lifting scheme. However, it is not always possible for IIR wavelet filter banks to be decomposed into a finite number of lifting steps.

In this chapter, we discuss several classes of wavelet filter banks by using allpass filters. Firstly, we describe two classes of orthogonal wavelet filter banks composed of two real allpass filters or a single complex allpass filter. We consider design of the proposed orthogonal wavelet filter banks without or with symmetry, respectively, and give the maximally flat solutions, where the orthogonal symmetric wavelet filter banks using real or complex allpass filter are corresponding to half sample symmetric (HSS) and whole sample symmetric (WSS) wavelets, respectively. Next, we present two classes of wavelet filter banks based on the lifting scheme with two lifting steps only. By using real allpass filters in the lifting steps, we can obtain one class of causal stable biorthogonal wavelet filter bank and another class of orthogonal wavelet filter bank, all with approximately linear phase response. In addition, we show some design examples to demonstrate the effectiveness of the proposed method.

2. Two band wavelet filter bank

It is well-known [1, 2, 3, 4] that wavelet basis can be generated by two band filter bank shown in Figure 1. In Figure 1, H0zand H1zare analysis filters, and G0zand G1zare synthesis filters. The relationship of input Xzand output Yzof the filter bank is given by

Therefore the PR condition is

where cis constant and Iis integer.

One desirable property for wavelets is orthogonality, which requires the filter bank is orthogonal, i.e., ∣H0ejω∣=∣G0ejω∣=∣H1ejπ−ω∣=∣G1ejπ−ω∣. Another desirable property is symmetry, i.e., the wavelet basis is symmetric or antisymmetric. It requires all filters in the filter bank to possess exactly linear phase, whose impulse responses are symmetric or antisymmetric.

3. The proposed orthogonal wavelet filter banks using allpass filters

In this section, we describe several classes of orthogonal wavelet filter banks without or with symmetry. The proposed classes of orthogonal wavelet filter banks are composed of two real allpass filters or a complex allpass filter.

3.1 Orthogonal wavelet filter banks without symmetry

In some applications of signal processing, for example, speech and acoustic signal processing, wavelet filters are required to have minimal phase response rather than exactly linear phase. Therefore, wavelet basis is not necessarily symmetric or antisymmetric. In the following, we discuss two classes of orthogonal wavelet filter banks without symmetry [20].

3.1.1 Filter bank using real allpass filters

We firstly consider a pair of IIR filters H0zand H1zthat are based on a parallel connection of two real allpass filters as shown in Figure 2, i.e.,

H0z=12AN1z2+z−2K−1AN2z2H1z=12AN1z2−z−2K−1AN2z2,E3

where Kis integer, AN1zand AN2zare real allpass filters of order N1and N2respectively. Let the synthesis filters G0z=H0z−1and G1z=H1z−1, then the PR condition in Eq.(2) is satisfied.

From Eq.(3), we have

H0z=12AN2z2ANz2+z−2K−1,E4

where ANzis a real allpass filter of order N=N1+N2, and defined as

ANz=AN1zAN2z=z−N∑n=0Nanzn∑n=0Nanz−n,E5

where anis real coefficient, and a0=1.

Let θωbe the phase response of ANz, the magnitude responses of H0zand H1zare given by

∣H0ejω∣=∣cosθ2ω2+K+12ω∣∣H1ejω∣=∣sinθ2ω2+K+12ω∣.E6

It is clear that the magnitude responses satisfy ∣H0ejω∣=∣H1ejπ−ω∣and the following power-complementary relation;

H0ejω2+H1ejω2=1,E7

which means that the filter bank is orthogonal.

For H0zand H1zto be a pair of lowpass and highpass filters, the desired phase response of ANzis given by

θdω=−K+12ω=−τω,E8

where τ=K+12. From the regularity of wavelets, it is known that an additional flatness condition is required to impose on H0z, i.e.,

∂k∣H0ejω∣∂ωkω=π=0k=01⋯L−1,E9

where Lis integer. Hence, the resulting wavelet function will have Lconsecutive vanishing moments. This flatness condition can be obtained if H0zcontains Lzeros located at z=−1.

For the maximally flat filters, the closed-form formula is given by

an=Nn∏i=1nN−τ−i+1τ+i.E10

Once a set of filter coefficients anare obtained, we compute poles of ANzand then assign the poles inside the unit circle to AN1zas its poles and the poles outside the unit circle to AN2zas its zeros. Therefore, we can obtain causal stable analysis filters H0zand H1z, then the synthesis filters G0zand G1zare anti-causal stable.

In many applications of signal processing, frequency selectivity is also thought of as a useful property from the viewpoint of signal band-splitting. However, regularity and frequency selectivity somewhat contradict each other. For this reason, design of H0zthat has the best possible frequency selectivity for the given flatness condition has been also discussed in [20].

Example 1: We consider design of filter banks using two real allpass filters with N1=N2=2and K=0. By setting L=9,5,1, we have designed H0zby using the design method proposed in [20]. The magnitude responses are shown in Figure 3, and the scaling and wavelet functions are shown in Figure 4, respectively. When L=9, it is seen that H0zis the maximally flat filter, and it is the elliptic filter if L=1. It is clear in Figure 3 that the magnitude error increases with an increasing L, and in Figure 4 that the scaling and wavelet functions decline more rapidly.

3.1.2 Filter bank using complex allpass filter

We consider a pair of H0zand H1zusing a single complex allpass filter as shown in Figure 5, i.e.,

H0z=12ANz+ÂNzH1z=z−12jANz−ÂNz,E11

where ANzand ÂNzare complex allpass filters of order N, and their coefficients are mutually complex conjugate. Let G0z=H0z−1and G1z=H1z−1similarly. From the orthogonality, ANzand ÂNzmust satisfy [7]

ANz=±jÂN−z,E12

which means that if αis a pole of ANz, then −α∗is a pole of ANzalso. Consequently, ANzhas a pair of poles α−α∗or a single pole jβ, where βis real, αis complex and α∗denotes the complex conjugate of α.

From Eq.(11),

H0z=12ÂNzA2Nz+1,E13

where A2Nzis a complex allpass filter of order 2N, and defined by

A2Nz=ANzÂNz=ejηe−jη∑n=0N1a2nz2n+z−2n+j∑n=0N2a2n+1z2n+1+z−2n−1∑n=0N1a2nz2n+z−2n−j∑n=0N2a2n+1z2n+1+z−2n−1,E14

where η=±π/4or ±3π/4, anis real and a0=1/2, N1=N/2and N2=N/2−1if Nis even, and N1=N2=N−1/2if Nis odd.

Therefore, the phase response θωof A2Nzis given by

θω=2η+2tan−1∑n=0N2a2n+1cos2n+1ω∑n=0N1a2ncos2nω,E15

and the magnitude responses of H0zand H1zare

∣H0ejω∣=∣cosθω2∣∣H1ejω∣=∣sinθω2∣,E16

which satisfies the power-complementary relation in Eq.(7).

The closed-form formula of the maximally flat filters can be given by

an=Cn∏i=1ni−N−1i+N,E17

where C2n=1and C2n+1=tanη. Therefore, we compute poles of A2Nzand assign the poles inside the unit circle to ANzas its poles to obtain causal stable analysis filters H0zand H1z. Thus, the synthesis filters G0zand G1zare anti-causal stable. Design of H0zhaving the best possible frequency selectivity for the given degrees of flatness has been also discussed in [20].

Example 2: We consider design of filter banks using a complex allpass filter with N=4and L=8,4,0. We have designed H0zby using the design method proposed in [20]. The magnitude responses are shown in Figure 6, and the scaling and wavelet functions are shown in Figure 7, respectively. It is seen in Figure 6 that H0zis the maximally flat filter if L=8, and the elliptic filter if L=0that does not have any zero located at z=−1and is different from that in Example 1.

3.2 Orthogonal symmetric wavelet filter banks

In many applications of image processing, digital filters are required to have exactly linear phase. Therefore, the impulse responses of wavelet filters need to be symmetric or antisymmetric, and the generated wavelet bases are symmetric or antisymmetric also. In the following, we discuss two classes of orthogonal symmetric wavelet filter banks composed of allpass filters: HSS [21] and WSS [22] wavelet filter banks.

3.2.1 Filter bank using real allpass filters

To obtain exactly linear phase, we constitute a pair of H0zand H1zin Figure 2 by using an allpass filter ANzas

H0z=12ANz2+z−2K−1ANz−2H1z=12ANz2−z−2K−1ANz−2.E18

Let θωbe the phase response of ANz, then the frequency responses of H0zand H1zare given by

H0ejω=e−jK+12ωcosθ2ω+K+12ωH1ejω=je−jK+12ωsinθ2ω+K+12ω.E19

It is clear in Eq.(19) that H0zand H1zhave exact linear phase response and satisfy the power-complementary relation in Eq.(7). The filter has a group delay of K+12, and its impulse response is HSS. Therefore, the design problem of the wavelet filter banks becomes the phase approximation of allpass filter ANz. For H0zand H1zto be a pair of lowpass and highpass filters, the desired phase response of ANzis

θdω=−K2+14ω=−τω,E20

where τ=K2+14. The filter coefficients anof the maximally flat filters can be computed by Eq.(10). Design of wavelet filters having the best possible frequency selectivity for the given degrees of flatness has been also discussed in [21]. It has been pointed out in [21] that we must choose K=⋯,−7,−6,−3,−2,1,2,5,6,⋯if Nis odd and K=⋯,−5,−4,−1,0,3,4,7,⋯if Nis even, in order to obtain a pair of reasonable lowpass and highpass filters to avoid the undesired zero and bump.

Example 3: We consider design of the maximally flat wavelet filter banks with N=4and L=9. We have designed ANzwith K=0and K=1. The magnitude responses of H0zare shown in Figure 8. It is seen in Figure 8 that H0zwith K=1has the undesired zero and bump nearby ω=π/2. The generated scaling and wavelet functions are shown in Figure 9 respectively. It is seen in Figure 9 that the scaling functions are symmetric, while the wavelet functions are antisymmetric. Although H0zwith K=0and K=1have the same degrees of flatness, it is seen that the scaling and wavelet functions of K=1decline more slowly than that of K=0, because of the undesired zero and bump. Therefore, we should not choose K=1in this case.

3.2.2 Filter bank using complex allpass filter

We consider again H0zand H1zusing a complex allpass filter in Figure 5,

H0z=12ANz+ÂNzH1z=z−12jANz−ÂNz.E21

To obtain exactly linear phase, ANzand ÂNzmust satisfy

ÂNz=1ANz,E22

which means that if αis a pole of ANz, then 1/αis a pole of ANztoo. In addition to orthogonality, ANzhas a quadruplet of poles α−α∗1/α−1/α∗or a pair of poles jβ1/jβ. Therefore, we have

ANz=ejηz−Na0+ja1z+a2z2+⋯+a2zN−2+ja1zN−1+a0zNa0−ja1z−1+a2z−2+⋯+a2z−N+2−ja1z−N+1+a0z−N,E23

where Nis even, anis real and a0=1. The phase response θωof ANzis given by

θω=η+2φω,E24

where if M=N/2is even,

φω=tan−1∑n=0M/2−1a2n+1cosM−2n−1ωaM2+∑n=0M/2−1a2ncosM−2nω,E25

and if M=N/2is odd,

φω=tan−1aM2+∑n=0M−3/2a2n+1cosM−2n−1ω∑n=0M−1/2a2ncosM−2nω.E26

Thus, we have

H0ejω=cosθωH1ejω=e−jωsinθω.E27

It is clear that H0zand H1zhave exactly linear phase responses and satisfy the power-complementary relation in Eq.(7). Its impulse response is WSS. Therefore, the design problem of wavelet filter banks becomes the phase approximation of ANzin Eq.(23).

For the maximally flat filters, the closed-form formula is given in [22] by

an=CnNn,E28

where C2n=1and C2n+1=−tanη2. Design of wavelet filters having the best possible frequency selectivity for the given degrees of flatness has been also discussed in [22]. It has been pointed out in [22] that we must choose η=±π/4if Mis even and η=±3π/4if Mis odd.

Example 4: We consider design of the filter banks with N=6and η=−3π/4. We have designed ANzwith L=0,2,4,6by using the design method proposed in [22]. The magnitude responses of H0zare shown in Figure 10, and the scaling and wavelet functions are shown in Figure 11, respectively. It is seen in Figure 10 that H0zwith L=6corresponds to the maximally flat filter, and H0zwith L=0is the minimax filter that has no zero located at z=−1. In Figure 11, the scaling and wavelet functions are not continuous because the regularity condition is not satisfied when L=0, and become more smooth with an increasing L. Both the scaling and wavelet functions are symmetric.

4. Lifting-based wavelet filter banks using allpass filters

The lifting scheme proposed in [16] and [17] is an efficient tool for constructing second generation wavelets, and has advantages such as faster implementation, fully in-place calculation, reversible integer-to-integer transforms, and so on. It has been proved in [18] and [19] that every FIR wavelet filter bank can be decomposed into a finite number of lifting steps, thus this allows the construction of an integer version of the wavelet transform. Such integer wavelet transforms are invertible, and then are attractive in lossless coding applications. Conventionally, the lifting scheme is often used to construct a class of biorthogonal wavelet filter banks. It has been shown in [18] that the orthogonal wavelet filter banks can also be realized by the lifting scheme. However, it is not always possible for IIR wavelet filter banks to be decomposed into a finite number of lifting steps. For example, it is difficult to realize the IIR orthogonal wavelet filter banks discussed in Section 3 by using a finite number of lifting steps.

Now, we restrict ourselves to the lifting scheme with two lifting steps [10] as shown in Figure 12. Let H0zand H1zbe a pair of lowpass and highpass filters,

then G0z=H1−zand G1z=−H0−z. It is clear in Figure 12 that the PR condition is structurally satisfied. Therefore, the design of H0zand H1zbecomes how to determine Pzand Qz. In the following, we describe two classes of near symmetric wavelet filter banks by using real allpass filters in the lifting scheme: causal stable biorthogonal wavelet filter bank [23] and orthogonal wavelet filter bank [24].

4.1 Causal stable wavelet filter banks

We use two real allpass filters in lifting steps, i.e., Pz=AN1zand Qz=AN2z, and thus,

H0z=12z−2K1−1+AN1z2H1z=z−2K2−AN2z2H0z.E30

Let θ1ωbe the phase response of AN1z, the frequency response of H0zis given by

H0ejω=ejθ12ω2−K1+12ωcosθ12ω2+K1+12ω.E31

For H0zto be lowpass filter, the desired phase response of AN1zis

θ1dω=−K1+12ω=−τ1ω,E32

where τ1=K1+12. According to Appendix, the order of AN1zis required to be N1=K1or N1=K1+1to obtain causal stable allpass filter.

Ideally, H0ejω=0in the stopband of H0z, then H1ejω=e−j2K2ω, having linear phase response from Eq.(30). In the passband of H0z, H0ejω=e−j2K1+1ωideally, thus,

H1ejω=e−j2K2ω−ejθ22ωe−j2K1+1ω=−2jejθ22ω2−K1+K2+12ωsinθ22ω2−K1−K2+12ω,E33

where θ2ωis the phase response of AN2z. Therefore, in the stopband of H1z, the desired phase response of AN2zis

θ2dω=K1−K2+12ω=−τ2ω,E34

where τ2=K2−K1−12. Similarly, the order of AN2zis required to be N2=K2−K1or N2=K2−K1−1to obtain causal stable allpass filter. Therefore, once N1and N2are given, we can obtain causal stable wavelet filter banks by appropriately choosing K1and K2. The maximally flat filters can be designed by using Eq.(10). H0zand H1zhave approximately linear phase response.

Example 5: We consider design of the maximally flat wavelet filter banks with N1=N2=6. We have designed AN1zwith K1=5, and the magnitude response of H0zis shown in Figure 13. We then designed AN2zwith K2=11and K2=12, and the magnitude responses of H1zare shown also in Figure 13. It is seen in Figure 13 that H1zwith K2=11has a large overshoot nearby ω=π/2. To avoid this overshoot, we should choose K2=N2+K1+1if K1=N1−1and K2=N2+K1if K1=N1. The scaling and wavelet functions generated by analysis and synthesis filters with K1=5and K2=12are shown in Figure 14 respectively.

4.2 Orthogonal wavelet filter banks

The above-mentioned causal stable wavelet filter banks are biorthogonal (not orthogonal). Here we discuss a class of orthogonal wavelet filter banks using the lefting scheme. We use Pz=ANzand Qz=ANz−1, then,

H0z=12z−2K1−1+ANz2H1z=z−2K2−ANz−2H0z.E35

Let θωbe the phase response of ANz, the frequency response of H0zis the same as in Eq.(31), thus the desired phase response of ANzis

θdω=−K1+12ω=−τω,E36

where τ=K1+12. To be orthogonal, we set K2=0and have

H1z=1−ANz−212z−2K1−1+ANz2=121−z−2K1−1ANz−2,E37

whose frequency response is

H1ejω=je−jθ2ω2+K1+12ωsinθ2ω2+K1+12ω.E38

It is clear that the magnitude responses satisfy ∣H0ejω∣=∣H1ejπ−ω∣and the power-complementary relation in Eq.(7). Therefore, this class of wavelet filter banks is orthogonal and both H0zand H1zhave approximately linear phase response. Design of this class of orthogonal wavelet filter banks has been discussed and applied to lossy to lossless image coding in [24].

Example 6: We consider design of the maximally flat orthogonal wavelet filter banks with N=2,4,6. We have designed ANzwith K1=N−1. The magnitude responses of H0zare shown in Figure 15. The generated scaling and wavelet functions are shown in Figure 16, respectively. It is seen in Figure 16 that the wavelet functions are near symmetric.

5. Conclusions

In this chapter, we have proposed several new classes of wavelet filter banks with some properties of orthogonality, symmetry and causal stablity by using allpass filters, which are potential options for readers to choose wavelet basis in practical applications. As shown in Table 1, first class of wavelet filter banks in Section 3.1 is orthogonal, but asymmetric, its analysis filters is causal stable. Second class of wavelet filter banks in Section 3.2 is orthogonal and symmetric, but not causal. Third and fourth classes of wavelet filter banks are based on the lifting scheme. Third class in Section 4.1 is biorthogonal, causal stable and near symmetric, while fourth class in Section 4.2 is orthogonal and near symmetric, but not causal. There is no solution to all of orthogonality, symmetry and causal stablity. The wavlet filter banks using allpass filters have been extended to Hilbert transform pair of wavelets [25], 2D wavelet filter banks [26], and applied to lossy to lossless image coding [27, 28, 29, 30] and scalable video compression [31]. It is possible also to extend them to higher dimension and irregural signal processing and to apply them to wavelet denoising, image fusion and so on.

Acknowledgments

This work was supported by JSPS KAKENHI Grant Number 18 K11260.

Abbreviations