XII. Wavelet Transform Main References

Presentation on theme: "XII. Wavelet Transform Main References"— Presentation transcript:

1 XII. Wavelet Transform Main References
[1] R. C. Gonzalez and R. E. Woods, Digital Image Processing, Chap. 7, 2nd edition, Prentice Hall, New Jersey, (適合初學者閱讀) [2] S. Mallat, A Wavelet Tour of Signal Processing, Academic Press, 3rd edition, (適合想深入研究的人閱讀) (若對時頻分析已經有足夠的概念，可以由這本書 Chapter 4 開始閱讀)

2 Other References [3] I. Daubechies, “Orthonormal bases of compactly supported wavelets,” Comm. Pure Appl. Math., vol. 4, pp , Nov [4] S. Mallat, “Multiresolution approximations and wavelet orthonormal bases of L2(R),” Trans. Amer. Math. Soc., vol. 315, pp , Sept [5] C. Heil and D. Walnut, “Continuous and discrete wavelet transforms,” SIAM Rev., vol. 31, pp , 1989. [6] I. Daubechies, “The wavelet transform, time-frequency localization and signal analysis,” IEEE Trans. Information Theory, pp , Sept [7] R. K. Young, Wavelet Theory and Its Applications, Kluwer Academic Pub., Boston, 1995. [8] S. Qian and D. Chen, Joint Time-Frequency Analysis: Methods and Applications, Chapter 4, Prentice-Hall, New Jersey, 1996. [9] L. Debnath, Wavelet Transforms and Time-Frequency Signal Analysis, Birkhäuser, Boston, 2001. [10] B. E. Usevitch, “A Tutorial on Modern Lossy Wavelet Image Compression: Foundations of JPEG 2000,” IEEE Signal Processing Magazine, vol. 18, pp , Sept

3 (1) Conventional method for signal analysis
Fourier transform : Cosine and Sine transforms: if x(t) is even and odd Orthogonal Polynomial Expansion 傳統方法共通的問題： (2) Time frequency analysis 例如， STFT Time frequency analysis 共通的問題：

4 12-A Haar Transform 一種最簡單又可以反應 time-variant spectrum 的 signal representation 8-point Haar transform

5 N = 4 N = 2 N = 8

6 General way to generate the Haar transform:
where  means the Kronecker product

7 N = 2k 時 H 除了第 0 個row 為 以外 第 2p + q 個row 為 hp,q[n] N 個 1 p = 0, 1, …, k−1, q = 0, 1, …, 2p−1 k = log2N hp,q[n] = when q2k−p  n < (q+1/2)2k−p hp,q[n] = −1 when (q+1/2)2k−p  n < (q+1)2k−p

8  Inverse 2k-point Haar Transform
D[m, n] = 0 if m  n D[0, 0] = 2−k, D[1, 1] = 2−k, D[n, n] = 2−k+p if 2p  n < 2p+1 When k = 3,

9 12-B Characteristics of Haar Transform
(1) No multiplications (2) Input 和 Output 點數相同 (3) 頻率只分兩種：低頻 (全為 1) 和高頻 (一半為 1，一半為 −1) (4) 可以分析一個信號的 localized feature (5) Very fast, but not accurate Example:

10 terms required for NRMSE < 105
Transforms Running Time terms required for NRMSE < 105 DFT 9.5 sec 43 Haar Transform 0.3 sec 128 References A. Haar, “Zur theorie der orthogonalen funktionensysteme ,” Math. Annal., vol. 69, pp , 1910. H. F. Harmuth, Transmission of Information by Orthogonal Functions, Springer-Verlag, New York, 1972. The Haar Transform is closely related to the Wavelet transform (especially the discrete wavelet transform).

11 12-C History of the Wavelet Transform
 1910, Haar families.  1981, Morlet, wavelet concept.  1984, Morlet and Grossman, ''wavelet''.  1985, Meyer, ''orthogonal wavelet''.  1987, International conference in France.  1988, Mallat and Meyer, multiresolution.  1988, Daubechies, compact support orthogonal wavelet.  1989, Mallat, fast wavelet transform. 1990s, Discrete wavelet transforms 1999, Directional wavelet transform  2000, JPEG 2000

12 12-D Three Types of Wavelets
Wavelet 以 continuous / discrete 來分，有 3 種 Input Output Name Type 1 Continuous Continuous Continuous Wavelet Transform 有時被稱為 discrete wavelet transform，但其實是continuous wavelet transform with discrete coefficients Type 2 Continuous Discrete Type 3 Discrete Discrete Discrete Wavelet Transform 比較：Fourier transform 有四種

13 12-E Continuous Wavelet Transform (WT)
Definition: x(t): input, (t): mother wavelet a: location, b: scaling a is any real number, b is any positive real number Compare with time-frequency analysis: location + modulation b Gabor Transform

14 Gabor Wavelet transform
f-axis b-axis frequency t-axis t-axis a-axis

15 a: location, b: scaling The resolution of the wavelet transform is invariant along a (location- axis) but variant along b (scaling axis). If x(t) = (t t1) + (t  t2) + exp(j2 f1t) + exp(j2 f2t), f b2 f b1 t t t t2 STFT WT b-axis 的方相反

16 12-F Mother Wavelet There are many ways to choose the mother wavelet. For example,  Haar basis  Mexican hat function In fact, the Mexican hat function is the 2nd order derivation of the Gaussian function.

17 Constraints for the mother wavelet:
(1) Compact Support support: the region where a function is not equal to zero compact support: the width of the support is not infinite a b (2) Real (3) Even Symmetric or Odd Symmetric

18 (4) Vanishing Moments kth moment: If m0 = m1 = m2 = ….. = mp−1 = 0, we say (t) has p vanishing moments. Vanish moment 越高，經過內積後被濾掉的低頻成分越多 Question：為什麼要求 ? 註：感謝 2006年修課的張育思同學

19 the 1st order derivation of the Gaussian function
Vanish moment = 1 b 方向相反 a [Ref] S. Mallat, A Wavelet Tour of Signal Processing, 2nd Ed., Academic Press, San Diego, 1999.

20 the 2nd order derivation of the Gaussian function
Vanish moment = 2 b 方向相反 a

21 Similarly, when the vanish moment is p

22 (5) Admissibility Criterion
[Ref] A. Grossman and J. Morlet, “Decomposition of hardy functions into square integrable wavelets of constant shape,” SIAM J. Appl. Math., vol. 15, pp , 1984.

23 12-G Inverse Wavelet Transform
where (Proof): Since if then

24 where If (t) is real, (−f) = *(f), (−bf) (bf) = *(bf) (bf) = |(bf)|2 (f1 = bf, df1 = fdb) Therefore, y(t) = x(t).

25 12-H Scaling Function 定義 scaling function 為 where
for f > 0, (−f) = *(f) (t) is usually a lowpass filter (Why?)

26 修正型的 Wavelet transform
(1) a is any real number, 0 < b < b0 (2) reconstruction: 由 b0 至 ∞ 的積分被第二項取代

27 (Proof): If (from the similar process on pages 360 and 361) 關鍵

28 Therefore, if y(t) = y1(t) + y2(t),
y(t) = x(t)

29 12-I Property (1) real input real output
(2) If x(t) Xw(a, b), then x(t − ) Xw(a −, b), (3) If x(t) Xw(a, b), then x(t /) (4) Parseval’s Theory: When (t) = C−1(t),

30 12-J Scalogram Scalogram 即 Wavelet transform 的絕對值平方

31 12-K Problems Problems of the continuous WT (1) hard to implement
(2) hard to find (t) Continuous WT is good in mathematics. In practical, the discrete WT and the continuous WT with discrete coefficients are more useful.

32 附錄十二 電機 +資訊領域的中研院院士 王兆振 (電子物理學家，1968年當選院士) 葛守仁 (電子電路理論奠基者之一，1976年當選院士)
附錄十二 電機 +資訊領域的中研院院士 王兆振 (電子物理學家，1968年當選院士) 葛守仁 (電子電路理論奠基者之一，1976年當選院士) 朱經武 (超導體，1987年當選院士) 田炳耕 (微波放大器，1987年當選院士) 崔琦 (量子霍爾效應，1992年當選院士，1998年諾貝爾物理獎) 王佑曾 (資料庫管理理論先驅，1992年當選院士) 高錕 (光纖通訊，1992年當選院士，2009年諾貝爾物理獎) 方復 (半導體，1992年當選院士) 厲鼎毅 (光電科技，1994年當選院士) 湯仲良 (光電科技，1994年當選院士) 施敏 (Non-volatile semiconductor memory 發明者，手機四大發明者 之一，1994年當選院士) 張俊彥 (半導體，1996年當選院士) 薩支唐 (MOS and CMOS，1998年當選院士) 林耕華 (光電科技，1998年當選院士) 劉兆漢 (跨領域，電機與地球科學，1998年當選院士) 虞華年 (微電子科技，2000年當選院士) 蔡振水 (光電與磁微波，2000年當選院士)

33 王文一 (奈米與應用物理，2002年當選院士) 胡正明 (微電子科技，2004年當選院士) 黃鍔 (Hilbert Huang Transform，2004年當選院士) 胡玲 (奈米科技，2004年當選院士) 李德財 (演算法設計，2004年當選院士) 劉必治 (多媒體信號處理，2006年當選院士) 莊炳湟 (語音信號處理，2006年當選院士) 黃煦濤 (圖形辨識，2006年當選院士) 舒維都 (信號處理與人工智慧，2006年當選院士) 李雄武 (電磁學，2006年當選院士) 孟懷縈 (無線通信與信號處理，2010年當選院士) 李澤元 (電力電子，2012年當選院士) 馬佐平 (微電子，2012年當選院士) 張懋中 (電子元件，2012年當選院士) 林本堅 (積體電路與傅氏光學，2014年當選院士) 陳陽闓 (高速半導體，2016年當選院士) 王康隆 (自旋電子學，2016年當選院士) 李琳山 (語音訊號處理，2016年當選院士) 戴聿昌 (微積電系統與醫工，2016年當選院士)

34 註：歷年中研院院士當中，屬於電機+資訊相關領域的有36人，佔了全部的 7.7 %
其中和通信及信號處理相關的有8位，大多是2004年以後當選院士