Scribd
Upload
45 views

Course 18.327 and 1.130 Wavelets and Filter Banks

This document discusses the lifting scheme for constructing wavelet filter banks and wavelet bases. It begins by explaining the basic lifting structure for filter banks and how the polyphase matrix can be factorized into lifting steps using the Euclidean algorithm. It then provides examples of how lifting can be used to modify existing filters to add properties like vanishing moments. The document also discusses efficient implementations of lifting schemes and provides examples of factorization for the Haar and 9/7 filter banks.

Uploaded by

djoseph_1
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
45 views

Course 18.327 and 1.130 Wavelets and Filter Banks

This document discusses the lifting scheme for constructing wavelet filter banks and wavelet bases. It begins by explaining the basic lifting structure for filter banks and how the polyphase matrix can be factorized into lifting steps using the Euclidean algorithm. It then provides examples of how lifting can be used to modify existing filters to add properties like vanishing moments. The document also discusses efficient implementations of lifting schemes and provides examples of factorization for the Haar and 9/7 filter banks.

Uploaded by

djoseph_1
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

Course 18.327 and 1.

130 Wavelets and Filter Banks


Lifting: ladder structure for filter banks; factorization of polyphase matrix into lifting steps; lifting form of refinement equation

Lifting
Basic idea: H0(z)
2
+

F0(z)
+

S(z)

S(z)
2
F1(z)

H1(z)

Filter bank is modified by a simple operation that preserves the perfect reconstruction property, regardless of the actual choice for S(z).
2

Advantages: Leads to faster implementation of DWT Provides a framework for constructing wavelets on non-uniform grids. What are the effective filters in the modified filter bank? 2 Synthesis bank 2 + S(z2) F1(z) F0(z) + 2
F1(z)+S(z2)F0(z)

F0(z) + F 1 (z)
3 new

use 2nd Noble identity

So the effective highpass filter is F1(z) + S(z2)F0(z). The lowpass filter is unchanged. To modify the lowpass filter, add a second lifting step, e.g. + T(z) + S(z) 2 F1(z) 2 F0(z) + 2
new F1 (z)

F0(z)+T(z2)F1 (z)

new

Consider F1new(z) = F1(z) [n] = f 1 [n] i.e. fnew 1 where r[k] = s[k/2] 0

+ S(z2) F0(z) + r[k] f0[n k]


k

; k even ; k odd
4

r[2k] = s[k] r[2k + 1] = 0 So [n] = f1 [n] + s[k] f0[n 2k] fnew 1


k

Then the corresponding wavelet is [n] (2t n) wnew(t) = fnew 1


n

= f1[n] (2t n) + s[k] f0[n 2k] (2t n)


n k n

= w(t) + s[k] f0[](2t - 2k - )


k

= w(t) + s[k] (t k)
k

since (t) = f0[](2t- )


5

Lifting for wavelet bases Lifting construction can be used to build a more complex set of scaling functions and wavelets from an initial biorthogonal set. e.g. lifting step S(z) gives (f0[n] unchanged) new(t) = (t) wnew(t) = w(t) - s[k] (t k)
k

~ ~ ~ new(t k) new(t) = h0 [n] new(2t-n) + s[k] w


n k

~ ~ new(t) = h [n] new(2t n) w 1


n

(h1[n] unchanged)

Example: H0(z) = 2 H1(z) = 2 {- + z - z 2} F0(z) = 2 {z + + z -1} F1(z) = 2 z-1

Scaling functions and wavelets are (t) -1 0 1 ~ ~ (t) = 2(2t) 1 -1 0 1 (t) = (2t + 1) + (2t) + (2t 1)
2

(2t 1) -1

0 1 -1 0 1 -(2t) -(2t 2) ~ ~ ~ ~ w(t) = -(2t) + (2t 1) -(2t 2) w(t) = 2(2t 1)

Biorthogonality/PR conditions are easy to verify, but what about zeros at ? F0(z) has double zero at H0(z) has no zeros at bad i.e. w(t) has no vanishing moments Lifting step to add vanishing moments to the synthesis wavelet: Suppose that the new wavelet has the form wnew(t) = w(t) - (t) - (t 1) Goal is to make the zeroth moment vanish
-

wnew(t)dt = 1 2 - 1 - 1 = 0 when =
8

So the new wavelet is


2

+ -1 0 w(t)
3 2

+ -1 0 1 - - (t) -1 0 1 2 - - (t 1)

= -1

1 2

- - new w (t)

Note: the wavelet will actually have two vanishing moments because of the symmetry constraint. i.e. zeros on unit circle appear in pairs when filter is symmetric.
9

What is F1 (z)? New wavelet equation is wnew(t) = w(t) - (t) - (t 1) = 2(2t 1) - {(2t + 1) + (2t) + (2t 1)} - { (2t - 1) + (2t - 2) + (2t - 3)} 3 = -(2t+1)- (2t)+ 2 (2t-1)- (2t - 2)-(2t-3) So new F1 (z) = 2 { z - + z -1 - z -2 - z-3} This can be rewritten as F1
new

new

(z) = 2 {z-1 + F1(z)

-(1 + z-2) 2

(z + + z -1)} F0(z)

S(z2)

10

The new analysis lowpass filter is H0 (z) = 2 {1 +


new (1 + z-2) 2 (-

+ z - z 2)}

This can be written as H 0 (z) = 2 (1 + z)(1 + z-1)(-z + 4 z-1) 5/3 filter bank F0(z) = 2 (1 + z)(1 + z -1)
new

11

Symmetric 5/3 Wavelets

12

Efficient Implementations
Ladder structure
2 x[n] P(s) U(d) z-1 2 U(d) P(s) s s

z-1

+
2

x[n-n0]

P and U may be nonlinear e.g. truncation to integer


13

Factorization of Filter Bank into Lifting Steps (Daubechies & Sweldens)


Goal is to perform a change of representation of the form:
H0(z)

H1(z)

P(z) z-1 2

S1(z) T1(z)

z-1 2

Sn(z) Tn(z)

1/c

14

P(z)

H0,even(z) H0,odd(z) = H1,even(z) H1,odd(z)

c 0 0
1 c

0 1 0

-Si(z) 1

i=n

-Ti(z) 1

Approach: use Euclidean algorithm for greatest common divisor 1) Start with A0(z) = H0,even(z) B0(z) = H0,odd(z) 2) Then iterate Ai(z) = Bi-1(z) Bi(z) = Ai-1(z) % B i-1(z) = Ai-1(z) Qi(z) Bi-1(z) remainder operator quotient
Ai-1(z) Bi-1(z)

(non-unique)

15

until i = n An(z) = c Bn(z) = 0

gcd (H0,even(z), H0,odd(z))

Matrix form of iteration: Ai(z) Bi(z) = Ai-1(z) Bi-1(z) 0 1 1 -Qi(z) 0 1 Invert this result to get 1 H0,even(z) H0,odd(z) = c 0 Qi(z) 1 1 -Qi(z) 1 0
16

After n iterations: n c 0 = H0,even(z) H0,odd(z)

i=1

i=n

Suppose that n is even (n = 2m). We can obtain a valid polyphase matrix of the form c 0 Qi(z) 1 1 Choice 1 c ensures ^ ^ =1 P(z) = that det P(z) 0
1 c i=2m

H0,even(z) H0,odd(z) = ^ ^ H1,even(z) H1,odd(z) ^ H1(z) gives P. R., but may not be the same as H1(z)

17

^ To recover the original highpass filter, H1(z), from H1(z), we introduce one more lifting step

H0(z)

H0(z)

H1(z) 2 ^ H1(z) 2

T(z) -

^ H1(z) = H1(z) T(z2) H0(z)


18

So the polyphase matrix is P(z) = 1 0 c 0


1

Qi(z) 1

-T(z) 1

1 0 0 1C
^ P(z)

i=2m

c 0

0
1 C

-c2T(z) 1 k=m 1

Q2k(z) 1 Q2k-1(z) 1 0 1 0

Rewrite each factor as a permutation of columns or rows Q2k(z) 1 Q2k-1 1 1 0 1 0 = = 1 Q2k(z) 0 1 0 1 1 0 1 0 1 1 0 0


19

Q2k-1(z) 1

1 Q2k(z) 0 1

Q2k-1(z) 1

So c P(z) = 0
1 C

1 -c2T(z)

0 1
k=m

1 Q2k(z) 0 1

Q2k-1(z) 1

+
Q1(z) Q2(z)

+
Q2m-1(z) Q2m(z) -c2T(z)

z-1

20

10

Example: Haar H0(z) =


1 2

(1 + z-1)
1 2 1 2

H1(z) =

1 2

(1 z-1)

A0(z) = H0,even(z) = B0(z) = H0,odd(z) = A1(z) = B0(z) =


1 2

= c

B1(z) = A0(z) % B0(z) = 0 Q1(z) = A0(z) / B0(z) = 1 ^ P(z) = 1/2 0 0 = 2


1

1 1

1 0

1 1 2 0
21

^ H1(z) =

2 2

^ H1(z) = H1(z) - T(z2) H0(z)


1 2

(1 z-1) =

2 2

- T(z2)

1 2

(1 + z-1)

i.e. T(z2) = 1 P(z) =


1 2

1 1 1 0
1 2

1 0 1 0 1 1
y0[n] =

0 2
1 2

- 1 1 0

1 0
1 2 (x[2n]

0 2

- 1

2 z-1 2

x[2n]

+
1

+ x[2n 1])

y1[n] = 2 (x[2n] - 2 y0[n])

x[2n-1]

1 2 (x[2n]

x[2n 1])

22

11

Factorization for 9/7 filter bank 2

Q1(z) Q2(z) Q3(z) Q4(z) z-1 2

1/c

Q1(z) = (1+z) Q2(z) = (1+z-1) Q3(z) = (1+z) Q4(z) = (1+z -1)

= -1.586134342 = -0.05298011854 = 0.8829110762 = 0.4435068522 c = 1.149604398


23

12

You might also like