University:
Massachusetts Institute of Technology
Course:
18.327 | Wavelets, Filter Banks and Applications
Academic year:

2019
Views:

483

Pages:

11
Author:

Diego Kennedy

Course 18.327 and 1.130 Wavelets and Filter Banks Multiresolution Analysis (MRA): Requirements for MRA; Nested Spaces and Complementary Spaces; Scaling Functions and Wavelets Scaling Functions and Wavelets φ(t) Box function Continuous time: 1 0 1 0 1 φ(2t) Scaling 1/2 t t φ(2t - 1) Scaling + Shifting 1 0 1/2 1 t 2 1 For this example: φ(t) = φ(2t) + φ(2t φ φ φ – 1) More generally: N φ(t) = 2∑ φ ∑ h0[k]φ(2t φ – k) k=0 Refinement equation or Two-scale difference equation φ(t) φ is called a scaling function The refinement equation couples the representations of a continuous-time function at two time scales. The continuous-time function is determined by a discretetime filter, h0[n]! For the above (Haar) example: h0[0] = h0[1] = ½ (a lowpass filter) 3 Note: (i) Solution to refinement equation may not always exist. If it does… (ii) φ(t) φ has compact support i.e. φ(t) = 0 outside 0 ≤ t < N φ (comes from the FIR filter, h0[n]) (iii) φ φ(t) often has no closed form solution. (iv) φ φ(t) is unlikely to be smooth. Constraint on h0[n]: N φ(2t – k)dt ∫ φ(t)dt = 2 ∑ h0[k] ∫ φ φ k=0 N = 2 ∑ h0[k] • ½ ∫ φ φ(τ)dτ τ τ k=0 So N ∑ h0[k] = 1 k=0 Assumes ∫ φ φ(t)dt ≠ 0 4 2 1 Square wave of finite length Haar wavelet w(t) Now consider: 1 0 1 t 1/2 φ(2t) Scaled 1/2 0 t 1/2 0 -φ φ(2t – 1) Scaled + shifted + sign flipped 1 t w(t) = φ(2t) - φ(2t – 1) 5 More generally: N w(t) = 2∑ φ(2t – k) ∑ h1[k] φ Wavelet equation k=0 For the Haar wavelet example: h1[0] = ½ h1[1] = -½ (a highpass filter) 6 3 Some observations for Haar scaling function and wavelet 1. Orthogonality of integer shifts (translates): 1 0 φ(t - 1) 1 φ(t) 1 0 t ∫ φ(t) φ(t – k)dt = = 2 1 t  1 if k = 0  0 otherwise  δ[k] Similarly ∫ w(t) w(t – k)dt = δ[k] Reason: no overlap 7 2. Scaling function is orthogonal to wavelet: 1 φ(t) 1 w(t) + + 1 0 1 t 0 t 1/2 - ∫φ φ(t) w(t)dt = 0 Reason: +ve and –ve areas cancel each other. 8 4 3. Wavelet is orthogonal across scales: w(2t) w(t) 1 w(2t - 1) + + + 1/2 1 0 1/2 t - 0 ∫ w(t) w(2t)dt = 0 , t - - t ∫ w(t) w(2t – 1)dt = 0 Reason: finer scale versions change sign while coarse scale version remains constant. 9 Wavelet Bases Our goal is to use w(t), its scaled versions (dilations) and their shifts (translates) as building blocks for continuous-time functions, f(t). Specifically, we are interested in the class of functions for which we can define the inner product: ∞ = ∫ f(t) g*(t)dt < ∞ -∞ ∞ Such functions f(t) must have finite energy: ∞ 2 2 ||f(t)|| = ∫f(t) ∫  dt -∞ ∞ < ∞ and they are said to belong to the Hilbert space, L2(ℜ). ℜ 10 5 Consider all dilations and translates of the Haar wavelet: wj,k(t) = 2j/2 w(2jt – k) ; -∞ ∞≤j≤∞ -∞ ∞≤k≤∞ Normalization factor so that ||wj,k(t)|| = 1 ∫ wj,k(t) wJ,K(t) dt = ∫ 2j/2 w(2jt – k) . 2J/2 w(2Jt – K)dt  1 if j = J and k = K =  0 otherwise  = δδ[ j – J ] δ[ δ k–K] 11 M 1 √2 L L w-1,k(t) 4 2 1 3 t 1 L 1 L 4 3 2 w0,k(t) t √2 L 1 2 3 4 L w1,k(t) t 12 6 wjk(t) form an orthonormal basis for L2(ℜ). ℜ f(t) = ∑ bjk wjk(t) ; j,k ∞ wjk(t) = 2j/2 w(2jt – k) bjk = -∞∞∫ f(t) wjk(t) dt 13 Multiresolution Analysis Key ingredients: 1. A sequence of embedded subspaces: {0} ⊂ … ⊂ V-1 ⊂ V0 ⊂ V1 ⊂ … ⊂ Vj ⊂ Vj+1 ⊂ … ⊂ L2(ℜ) ℜ L2(ℜ) ℜ = all functions with finite energy ∞ = {ƒ(t): ∫  ƒ(t) 2 dt < ∞} Hilbert ∞ -∞ ∞ space Requirements: • Completeness as j → ∞ . If ƒ(t) belongs to L2(ℜ) ℜ and ƒj(t) is the portion of ƒ(t) that lies in Vj, then lim j→ → ∞ ƒj(t) = ƒ(t) 14 7 Restated as a condition on the subspaces: ∞ ∪ j=-∞ • Vj = L2 (ℜ) ℜ Emptiness as j → - ∞ lim j → - ∞ || fj(t) || = 0 Restated as a condition on the subspaces: ∞ ∩ Vj = {0} j=-∞ 15 2. A sequence of complementary subspaces, Wj, such that Vj + Wj = Vj+1 and Vj ∩ Wj = {0} (no overlap) This is written as Vj ⊕ Wj = Vj+1 (Direct sum) Note: An orthogonal multiresolution will have Wj orthogonal to Vj : Wj � Vj . So orthogonality will ensure that Vj ∩ Wj = {0} 16 8 We thus have V1 = V0 ⊕ W 0 V2 = V 1 ⊕ W 1 = V0 ⊕ W 0 ⊕ W 1 V3 = V2 ⊕ W 2 = V0 ⊕ W 0 ⊕ W 1 ⊕ W 2 M J-1 VJ = VJ-1 ⊕ WJ-1 = V0 ⊕ ∑ Wj j=0 M ∞ L2(ℜ) ℜ = V0 ⊕ ∑ Wj j=0 We can also write the recursion for j < 0 V0 = V-1 ⊕ W-1 = V-2 ⊕ W-2 ⊕ W-1 M -1 = V-k ⊕ ∑ Wj j=-k M ∞ -1 ⇒ L2(ℜ) = ∑ Wj ℜ = ∑ Wj j = -∞ ∞ j = -∞ ∞ 17 3. A scaling (dilation) law: If ƒ(t) ∈ Vj then ƒ(2t) ∈ Vj+1 4. A shift (translation) law: k integer If ƒ(t) ∈ Vj then ƒ(t-k) ∈ Vj : - ∞ ≤ k ≤ ∞} 5. V0 has a shift-invariant basis, {φ(t-k) φ ∞ W0 has a shift-invariant basis, {w(t-k) : - ∞ ≤ k ≤ ∞} ∞ We expect that V1 = V0 + W0 will have twice as many basis functions as V0 alone. First possibility: {φ(t-k) , w(t-k) : - ∞ ≤ k ≤ ∞} φ ∞ Second possibility: use the scaling law i.e. if φ(tk) ∈ V1 φ k) ∈ V0 , then φ(2tφ 18 9 So V1 has a shift-invariant basis, {√2 φ(2t-k): - ∞ ≤ k ≤ ∞} ∞ Can we relate this basis for V1 to the basis for V0? We know that V0 ⊂ V1 So any function in V0 can be written as a combination of the basic functions for V1. In particular, since φ(t) ∈ V0, we can write φ(t) = 2∑ ∑ h0[k] φ(2t – k) k This is the Refinement Equation (a.k.a. the TwoScale Difference Equation or the Dilation Equation). 19 We also know that W0 = V1 – V0 So W0 ⊂ V1 This means that any function in W0 can also be written as a combination of the basic functions for V1. Since w(t) ∈ W0, we can write w(t) = 2∑ ∑ h1[k] φ(2t φ – k) k Wavelet Equation 20 10 Multiresolution Representations Functions: L2 (ℜ) = V0 ⊕ W0 ⊕ W1 ⊕ W2 ⊕ ... Level 2 detail Level 1 detail Level 0 detail Finite energy functions Coarse approximation Images: V0 W0 + V1 W1 V2 + 21 Multiresolution Representations Geometry: Mesh courtesy of Igor Guskov (Caltech) 22 11

18.327 Handout 9

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock