XIII. Continuous WT with Discrete Coefficients

Presentation on theme: "XIII. Continuous WT with Discrete Coefficients"— Presentation transcript:

1 XIII. Continuous WT with Discrete Coefficients
13-A Definition The parameters a and b are not chosen arbitrarily. For example, a = n2m and b = 2m. 註：某些文獻把這個式子稱作是 discrete wavelet transform，實際上仍然是 continuous wavelet transform 的特例  Main reason for constrain a and b to be n2m and 2m : Easy to implementation Xw(n, m) can be computed from Xw(n, m−1) by digital convolution.

2 13-B Inverse Wavelet Transform
1(t) is the dual function of (t). i.e., should be satisfied.

3 We often desire that 1(t) = (t).
The mother wavelet should satisfies

4 13-C Haar Wavelet (t) mother wavelet (wavelet function)
(t) scaling function 1 t=0 t= 0.5 t=1 t = 1 t = 0 (2t) (2t) (2t) = (t) + (t) 0 0.5 (t) = (2t) + (2t–1) (t) = (2t) – (2t–1)

5 (2mt − n) (2mt − n) t=n2-m t=(n+.5)2-m t=(n+1)2-m t=n2-m t=(n+1)2-m  Advantages of Haar wavelet (1) Simple (2) Fast algorithm (3) Orthogonal →reversible (4) Compact, real, odd (5) Vanish moment

6 Properties (1) 任何 function 都可以由 (t), (2t), (4t), (8t), (16t), ……….. 以及它們的位移所組成 (2) 任何平均為 0 的function 都可以由 (t), (2t), (4t), (8t), (16t), ……….. 所組成 換句話說……. 任何 function 都可以由 constant, (t), (2t), (4t), (8t), (16t), ……….. 所組成

7 (3) Orthogonal The dual function of (t) is (t) itself.

8 (4) 不同寬度 (也就是不同 m) 的 wavelet / scaling functions 之間會有一個關係
(t) = (2t) + (2t − 1) (t − n) = (2t − 2n) + (2t − 2n − 1) (2mt − n) = (2m+1t − 2n) + (2m+1t − 2n − 1) (t) = (2t) − (2t − 1) (t − n) = (2t − 2n) − (2t − 2n − 1) (2mt − n) = (2m+1t − 2n) − (2m+1t − 2n − 1)

9 (5) 可以用 m+1 的 coefficients 來算 m 的 coefficients
若

10 layer: w[n, m] w[2n, m +1] w[4n, m +2] w[4n+1, m +2] Xw[2n, m +1] −1 w[2n+1, m+1] Xw[n, m] w[4n+2, m +2] −1 Xw[2n+1, m +1] w[4n+3, m +2] −1 structure of multiresolution analysis (MRA)

11 13-D General Methods to Define the Mother Wavelet and the Scaling Function
Constraints: (a) nearly compact support (b) fast algorithm (c) real (d) vanish moment (e) orthogonal 和 continuous wavelet transform 比較： (1) compact support 放寬為 “near compact support” (2) 沒有 even, odd symmetric 的限制 (3) 由於只要是 complete and orthogonal, 必定可以 reconstruction 所以不需要 admissibility criterion 的限制 (4) 多了對 fast algorithm 的要求

12 13-E Fast Algorithm Constraints
Higher and lower resolutions 的 recursive relation 的一般化 稱作 dilation equation (t): mother wavelet, (t): scaling function 這些關係式成立，才有fast algorithms

13 If then If then

14 (Step 1) convolution (Step 2) down sampling

15  2  2 m 越大，越屬於細節

16  To satisfy , FT FT where (f) 是 (t) 的 continuous Fourier transform G(f) 是 {gk} 的 discrete time Fourier transform

17 連乘 (可以藉由 normalization, 讓 (0) = 1) 若G(f) 決定了，則 (f) 可以被算出來 G(f): 被稱作 generating function constraint 1

18  同理 constraint 2  另外，由於 (f = 0 代入) 必需滿足 constraint 3

19 13-F Real Coefficient Constraints
Since If are satisfied, constraint 4 constraint 5 then (f) = *(− f), (f) = *(−f), and (t), (t) are real. Note: If these constraints are satisfied, gk, hk on page 383 are also real.

20 13-G Vanish Moment Constraint
If (t) has p vanishing moments, for k = 0, 1, 2, …, p−1 Since from the Parseval’s Theorem, (Here, we use the fact that general form of the sifting property )

21 for k = 0, 1, 2, …, p−1 Therefore, Taking the conjugation on both sides, for k = 0, 1, 2, …, p−1 Since if for k = 0, 1, 2, …, p−1 is satisfied, constraint 6 then for k = 0, 1, 2, …, p−1 are satisfied and the wavelet function has p vanishing moments.

22 13-H Orthogonality Constraints
(t): wavelet function If the above equality is satisfied, forward wavelet transform: inverse wavelet transform: (much easier for inverse) C = mean of x(t) (證明於後頁)

23 If and then due to

24 Therefore, is the inverse operation of #

25 ※ 要滿足 之前，需要滿足以下三個條件 (1) for mother wavelet 這個條件若滿足， 對所有的 m 皆成立 (2) for scaling function 嚴格來說，這並不是必要條件，但是可以簡化 第 (3) 個條件的計算

26 (3) for any n, n if k > 0 若 (1) 和 (3) 的條件滿足，則 也將滿足 (Proof): Set If (3) is satisfied, when m  m1 In the case where m = m1, if (1) is satisfied, then #

27  由 Page 396 的條件 (1) Parseval’s theorem if p is an integer Therefore, for all f should be satisfied

28  同理，由 Page 396 的條件 (2) for scaling function 推導過程類似 page 398 for all f should be satisfied

29 衍生的條件：將 代入 (page 398) 因為 hk 是 discrete sequence, H(f) 是hk 的 discrete-time Fourier transform

30 因為 for all f (page 398 的條件) constraint 7

31 同理，將 代入 (page 398) 經過運算可得 constraint 8

32  Page 397 條件 (3) 的處理 由於 是 的 linear combination 是 的 linear combination 是 的 linear combination : 是 的 linear combination 所以 必定可以表示成 的 linear combination

33 所以，若 for any n1, nk 可以滿足 則 for any n1, nk 必定能夠成立 Page 397 條件 (3) 可改寫成 (將 t − n1 變成 t,  = nk − n1) (from Parseval’s theorem)

34 Since (since from page 404,  is an integer)

35 Since Since for all f (page 398) constraint 9

36 13-I Nine Constraints 整理： 設計 mother wavelet 和 scaling function 的九大條件 (皆由 page 382 的 constraints 衍生而來) (1) for fast algorithm , page 388 (2) for fast algorithm , page 389 (3) for fast algorithm , page 389 (4) for real , page 390 (5) for real , page 389 (6) for p vanish moments , page 392 for k = 0, 1, …, p-1

37 (7) for orthogonal , page 401 for orthogonal , page 402 (8) for orthogonal , page 406 (9)

38  條件的簡化 有時，令 此時，若 (條件 (5), (8) 滿足) 則 條件 (4), (7), (9) 也將滿足

39 整理： 設計 mother wavelet 和 scaling function 的幾個要求 (簡化版)
(1) for fast algorithm (2) for fast algorithm (3) for fast algorithm (4) for real for p vanish moments (5) for k = 0, 1, …, p-1 (6) for orthogonal (7)

40 13-J Design Process 設計時，只要 G(f) (0  f  1/4) 決定了，mother wavelet 和scaling function 皆可決定 G(f): 被稱作 generating function Design Process (設計流程): (Step 1): 給定 G(f) (0  f  1/4)，滿足以下的條件 (a) (b) for k = 0, 1, 2, …, p-1

41 (Step 2) 由 決定G(f) (3/4  f < 1) (Step 3) 由 決定G(f) (1/4 < f < 3/4) 再根據 G(f) = G(f+1)，決定所有的 G(f) 值 (Step 4) 由 決定H(f) (Step 5) 由 決定(f), (f)

42 註： (1) 當 Step 1 的兩個條件滿足，由於 for k = 0, 1, 2, …, p-1 又由於 for k = 0, 1, 2, …, p-1 (2) 所以當 G(f) (0  f  1/4) 給定，|G(f)| 有唯一解

43 13-K Several Continuous Wavelets with Discrete Coefficients
(1) Haar Wavelet g[0] = 1, g[1] = 1 h[0] = 1, h[1] = −1 或 g[0] = 1/2, g[1] = 1/2 h[0] = 1/2, h[1] = −1/2 vanish moment = ?

44 (2) Sinc Wavelet for |f | 1/4 otherwise vanish moment = ? (3) 4-point Daubechies Wavelet vanish moment = ? vanish moment VS the number of coefficients

45 From: S. Qian and D. Chen, Joint Time-Frequency Analysis: Methods and
Applications, Prentice Hall, N.J., 1996.

46 13-L Continuous Wavelet with Discrete Coefficients 優缺點
 Advantages: (1) Fast algorithm for MRA (2) Non-uniform frequency analysis FT (3) Orthogonal

47  Disadvantages: (a) 無限多項連乘 (b) problem of initial 皆由 算出 如何算 (c) 難以保證 compact support (d) 仍然太複雜

48 附錄十三 幾種常見的影像壓縮格式 (1) JPEG: 使用 discrete cosine transform (DCT) 和 88 blocks 是當前最常用的壓縮格式 (副檔名為 *.jpg 的圖檔都是用 JPEG 來壓縮) 可將圖檔資料量壓縮至原來的 1/8 (對灰階影像而言) 或 1/ (對彩色影像而言) (2) JPEG2000: 使用 discrete wavelet transform (DWT) 壓縮率是 JPEG 的 5 倍左右 (3) JPEG-LS: 是一種 lossless compression 壓縮率較低，但是可以完全重建原來的影像 (4) JPEG2000-LS: 是 JPEF2000 的 lossless compression 版本 (5) JBIG: 針對 bi-level image (非黑即白的影像) 設計的壓縮格式

49 (6) GIF: 使用 LZW (Lempel–Ziv–Welch) algorithm (類似字典的建構)
適合卡通圖案和動畫製作，lossless (7) PNG: 使用 LZ77 algorithm (類似字典的建構，並使用 sliding window) lossless (8) JPEG XR (又稱 HD Photo): 使用 Integer DCT，lossless 在 lossy compression 的情形下壓縮率可和 JPEG 2000 差不多 (9) TIFF: 使用標籤，最初是為圖形的印刷和掃描而設計的，lossless