1、小波變換與應(yīng)用小波變換與應(yīng)用一、小波變換1.小波2.小波變換3. 離散小波變換 二、Haar小波變換1.哈爾函數(shù)2.求均值和差值3. 哈爾變換的特性4.一維哈爾小波變換5. 二維哈爾小波變換三、閱讀和練習作業(yè)一、一、Wavelet Transform 小波分析是近十幾年才發(fā)展起來并迅速應(yīng)用到圖像處理和語音分析等眾多領(lǐng)域的一種數(shù)學工具。它是繼110多年前的傅里葉(Joseph Fourier)分析之后的一個重大突破，無論是對古老的自然學科還是對新興的高新技術(shù)應(yīng)用學科都產(chǎn)生了強烈沖擊。 小波理論是應(yīng)用數(shù)學的一個新領(lǐng)域。要深入理解小波理論需要用到比較多的數(shù)學知識。本教學提綱企圖從工程應(yīng)用角度出發(fā)，用

2、比較直觀的方法來介紹小波變換和它的應(yīng)用，為讀者深入研究小波理論和應(yīng)用提供一些背景材料1. What is wavelet一種函數(shù)一種函數(shù)具有有限的持續(xù)時間、突變的頻率和振幅具有有限的持續(xù)時間、突變的頻率和振幅波形可以是不規(guī)則的，也可以是不對稱的波形可以是不規(guī)則的，也可以是不對稱的在整個時間范圍里的幅度平均值為零在整個時間范圍里的幅度平均值為零比較正弦波比較正弦波部分小波波形部分小波波形小波的定義小波的定義 Wavelets are a class of a functions used to localize a given function in both space and scaling

3、. A family of wavelets can be constructed from a function , sometimes known as a mother wavelet, which is confined in a finite interval. Daughter wavelets are then formed by translation (b) and contraction (a). Wavelets are especially useful for compressing image data, since a wavelet transform has

4、properties which are in some ways superior to a conventional Fourier transform. ( ) x( , )( )a bxAn individual wavelet can be defined by and Calderns formula givesThenA common type of wavelet is defined using Haar functions. 2. Wavelet Transform老課題函數(shù)的表示方法 新方法Fourier Haar wavelet transform (1) 1807:

5、Joseph Fourier傅里葉理論指出，一個信號可表示成一系列正弦和余弦函數(shù)之和，叫做傅里葉展開式。用傅里葉表示一個信號時，只有頻率分辨率而沒有時間分辨率，這就意味我們可以確定信號中包含的所有頻率，但不能確定具有這些頻率的信號出現(xiàn)在什么時候。 為了繼承傅里葉分析的優(yōu)點，同時又克服它的缺點，人們一直在尋找新的方法。傅里葉變換的定義：A mathematical description of the relationship between functions of time and corresponding functions of frequency; a map for convert

6、ing from one domain to the other. For example, if we have a signal that is a function of time-an impulse response- then the Fourier Transform will convert that time domain data into frequency data, for example, a frequency response. (keithyates/glossary.htm)(2) 1910: Alfred Haar發(fā)現(xiàn)發(fā)現(xiàn)Haar小波小波哈爾(Alfred

7、 Haar)對在函數(shù)空間中尋找一個與傅里葉類似的基非常感興趣。1909年他發(fā)現(xiàn)了小波，1910年被命名為Haar wavelets他最早發(fā)現(xiàn)和使用了小波。 (3) 1945: Gabor提出提出STFT 20世紀40年代Gabor開發(fā)了STFT (short time Fourier transform)STFT的時間-頻率關(guān)系圖(4) 1980: Morlet提出了提出了CWTCWT (continuous wavelet transform) 20世紀70年代，當時在法國石油公司工作的年輕的地球物理學家Jean Morlet提出了小波變換WT(wavelet transform)的概念。

8、20世紀80年代,從STFT開發(fā)了CWT： Definition - Basis Functions: a set of linearly independent functions that can be used (e.g., as a weighted sum) to construct any given signal.nwhere:na = scale variable 縮放因子nk = time shift 時間平移nh* = wavelet function 小波函數(shù) n用y = scaled (dilated) and shifted (translated) Mother w

9、avelet function,n在CWT中，scale和position是連續(xù)變化的縮放縮放(scaled)的概念的概念例1：正弦波的算法縮放縮放(scaled)的概念的概念(續(xù)續(xù))例2：小波的縮放平移平移(translation)的概念的概念(5) CWT的變換過程的變換過程可分成如下可分成如下5個步驟個步驟步驟步驟1: 把小波把小波 和原始信號和原始信號 的開始部分進行比較的開始部分進行比較步驟步驟2: 計算系數(shù)計算系數(shù)c 。該系數(shù)表示該部分信號與小。該系數(shù)表示該部分信號與小波的近似程度。系數(shù)波的近似程度。系數(shù) c 的值越高表示信號與小的值越高表示信號與小波越相似，因此系數(shù)波越相似，因此

10、系數(shù)c 可以反映這種波形的相可以反映這種波形的相關(guān)程度關(guān)程度步驟步驟3: 把小波向右移，距離為把小波向右移，距離為 ，得到的小波函，得到的小波函數(shù)為數(shù)為 ，然后重復步驟，然后重復步驟1和和2。再把小波向右移，。再把小波向右移，得到小波得到小波 ，重復步驟，重復步驟1和和2。按上述步驟一直。按上述步驟一直進行下去，直到信號進行下去，直到信號 終了終了步驟步驟4: 擴展小波擴展小波 ，例如擴展一倍，得到的小波，例如擴展一倍，得到的小波函數(shù)為函數(shù)為 步驟步驟5: 重復步驟重復步驟14(a) 二維圖(b) 三維圖連續(xù)小波變換分析圖(6) 三種變換的比較三種變換的比較(7) 1984: subband

11、coding (Burt and Adelson) SBC (subband coding)的基本概念：把信號的頻率分成幾個子帶，然后對每個子帶分別進行編碼，并根據(jù)每個子帶的重要性分配不同的位數(shù)來表示數(shù)據(jù) 20世紀70年代，子帶編碼開始用在語音編碼上20世紀80年代中期開始在圖像編碼中使用1986年Woods, J. W.等人曾經(jīng)使用一維正交鏡像濾波器組(quadrature mirror filterbanks，QMF)把信號的頻帶分解成4個相等的子帶 圖(a) 正交鏡像濾波器(QMF) 圖中的符號 表示頻帶降低1/2，HH表示頻率最高的子帶，LL表示頻率最低的子帶。這個過程可以重復，直到符

12、合應(yīng)用要求為止。這樣的濾波器組稱為分解濾波器樹(decomposition filter trees)圖(b) 表示其相應(yīng)的頻譜(8) 20世紀世紀80年代年代Mallat, Meyer等人提出multiresolution theory法國科學家Y.Meyer創(chuàng)造性地構(gòu)造出具有一定衰減性的光滑函數(shù)，他用縮放(dilations)與平移(translations)均為 2的j次冪的倍數(shù)構(gòu)造了平方可積的實空間L2(R)的規(guī)范正交基，使小波得到真正的發(fā)展小波變換的主要算法由法國的科學家Stephane Mallat提出 S.Mallat于1988年在構(gòu)造正交小波基時提出了多分辨率分析(multir

13、esolution analysis)的概念, 從空間上形象地說明了小波的多分辨率的特性 提出了正交小波的構(gòu)造方法和快速算法，叫做Mallat算法。該算法統(tǒng)一了在此之前構(gòu)造正交小波基的所有方法，它的地位相當于快速傅里葉變換在經(jīng)典傅里葉分析中的地位。 小波分解得到的圖像小波分解得到的圖像 (9)著名科學家著名科學家 Inrid Daubechies，Ronald Coifman和 Victor Wickerhauser等著名科學家把這個小波理論引入到工程應(yīng)用方面做出了極其重要的貢獻Inrid Daubechies于1988年最先揭示了小波變換和濾波器組(filter banks)之間的內(nèi)在關(guān)系，

14、使離散小波分析變成為現(xiàn)實 在信號處理中，自從S.Mallat和Inrid Daubechies發(fā)現(xiàn)濾波器組與小波基函數(shù)有密切關(guān)系之后，小波在信號(如聲音信號，圖像信號等)處理中得到極其廣泛的應(yīng)用。 經(jīng)過十幾年的努力，這門學科的理論基礎(chǔ)已經(jīng)基本建立，并成為應(yīng)用數(shù)學的一個新領(lǐng)域。這門新興學科的出現(xiàn)引起了許多數(shù)學家和工程技術(shù)人員的極大關(guān)注，是國際科技界和眾多學術(shù)團體高度關(guān)注的前沿領(lǐng)域。 小波變換小波變換3. 離散小波變換離散小波變換在計算連續(xù)小波變換時，實際上也是用離散的數(shù)據(jù)進行計算的，只是所用的縮放因子和平移參數(shù)比較小而已。不難想象，連續(xù)小波變換的計算量是驚人的。為了解決計算量的問題，縮放因子和平

15、移參數(shù)都選擇 ( j.0的整數(shù))的倍數(shù)。使用這樣的縮放因子和平移參數(shù)的小波變換叫做雙尺度小波變換(dyadic wavelet transform)，它是離散小波變換(discrete wavelet transform，DWT)的一種形式。使用離散小波分析得到的小波系數(shù)、縮放因子和時間關(guān)系如圖所示。圖(a)是20世紀40年代使用Gabor開發(fā)的短時傅里葉變換(short time Fourier transform，STFT)得到的時間-頻率關(guān)系圖圖(b)是20世紀80年代使用Morlet開發(fā)的小波變換得到的時間-縮放因子(反映頻率)關(guān)系圖。3. 離散小波變換離散小波變換(續(xù)續(xù))離散小波變換

16、分析圖DWT變換方法變換方法執(zhí)行離散小波變換的有效方法是使用濾波器該方法是Mallat在1988年開發(fā)的，叫做Mallat算法這種方法實際上是一種信號的分解方法，在數(shù)字信號處理中稱為雙通道子帶編碼用濾波器執(zhí)行離散小波變換的概念如圖所示S表示原始的輸入信號，通過兩個互補的濾波器產(chǎn)生A和D兩個信號A表示信號的近似值(approximations)D表示信號的細節(jié)值(detail) 在許多應(yīng)用中，信號的低頻部分是最重要的，而高頻部分起一個“添加劑的作用。猶如聲音那樣，把高頻分量去掉之后，聽起來聲音確實是變了，但還能夠聽清楚說的是什么內(nèi)容。相反，如果把低頻部分去掉，聽起來就莫名其妙。在小波分析中，近似

17、值是大的縮放因子產(chǎn)生的系數(shù)，表示信號的低頻分量。而細節(jié)值是小的縮放因子產(chǎn)生的系數(shù)，表示信號的高頻分量。雙通道濾波過程離散小波變換可以被表示成由低通濾波器和高通濾波器組成的一棵樹原始信號通過這樣的一對濾波器進行的分解叫做一級分解信號的分解過程可以疊代，也就是說可進行多級分解。如果對信號的高頻分量不再分解，而對低頻分量連續(xù)進行分解，就得到許多分辨率較低的低頻分量，形成如圖所示的一棵比較大的樹。這種樹叫做小波分解樹(wavelet decomposition tree)分解級數(shù)的多少取決于要被分析的數(shù)據(jù)和用戶的需要小波分解樹小波分解樹(a)信號分解 (b)系數(shù)結(jié)構(gòu) (c)小波分解樹小波分解樹小波包分

18、解樹小波包分解樹 小波分解樹表示只對信號的低頻分量進行連續(xù)分解。如果不僅對信號的低頻分量連續(xù)進行分解，而且對高頻分量也進行連續(xù)分解，這樣不僅可得到許多分辨率較低的低頻分量，而且也可得到許多分辨率較低的高頻分量。這樣分解得到的樹叫做小波包分解樹(wavelet packet decomposition tree)，這種樹是一個完整的二進制樹。三級小波包分解樹圖表示的是一棵三級小波包分解樹。小波包分解方法是小波分解的一般化，可為信號分析提供更豐富和更詳細的信息。例如，小波包分解樹允許信號S表示為1 3 3 2SAAADDADDD降采樣過程降采樣過程n在使用濾波器對真實的數(shù)字信號進行變換時，得到的數(shù)

19、據(jù)將是原始數(shù)據(jù)的兩倍。例如，如果原始信號的數(shù)據(jù)樣本為1000個，通過濾波之后每一個通道的數(shù)據(jù)均為1000個，總共為2000個。n根據(jù)尼奎斯特(Nyquist)采樣定理就提出了降采樣(downsampling)的方法，即在每個通道中每兩個樣本數(shù)據(jù)取一個，得到的離散小波變換的系數(shù)(coefficient)分別用cD和cA表示降采樣過程如下圖。圖中的符號 表示降采樣。小波變換的定義小波變換的定義A transform which localizes a function both in space and scaling and has some desirable properties compa

20、red to the Fourier transform. The transform is based on a wavelet matrix, which can be computed more quickly than the analogous Fourier matrix.An alternative to the discrete cosine transform (DCT), the wavelet transform changes data, such as video data, into the sum of varying frequency wavelets. Wa

21、velets are sometimes used instead of the DCT because they are more versatile and dont slow down as much with larger images as the DCT does. Intels Indeo technology makes use of wavelets. geocities/emulationmaster/gloss.htmlHaar Transform A one-dimensional transform which makes use of the Haar functi

22、ons. H- Transform, Haar Function References Haar, A. 2019-2019 Wolfram Research, Inc. header.H-Transform A two-dimensional generalization of the Haar transform which is used for the compression of astronomical images. The algorithm consists of dividing the image into blocks of pixels, calling the pi

23、xels in the block , , , and . For each block, compute the four coefficients Construct.二、二、Haar小波變換小波變換1.哈爾函數(shù)哈爾函數(shù)哈爾基函數(shù)基函數(shù)是生成矢量空間V j 而定義的一組線性無關(guān)的函數(shù)，可以用來構(gòu)造任意給定的信號。也稱尺度函數(shù)(scaling function)，用符號V j 表示。 哈爾小波函數(shù)哈爾小波函數(shù)是生成矢量 的一組線性無關(guān)的函數(shù) ，用符號W j表示。矢量空間W j中的小波可用來表示一個函數(shù)在矢量空間 中不能表示的部分。見第2版，8.2 jV2. 哈爾變換原理哈爾變換原理假設(shè)兩個信

24、號的數(shù)值分別為a和b，計算它們的和與差，n從s和d重新獲得a和b，哈爾變換舉例哈爾變換舉例【例】假設(shè)有一幅分辨率只有4個像素 的一維圖像，對應(yīng)的像素值或者叫做圖像位置的系數(shù)分別為： 9 7 3 5計算它的哈爾小波變換系數(shù)步驟1：求均值(averaging)。計算相鄰像素對的平均值，得到一幅分辨率比較低的新圖像，它的像素數(shù)目變成了2個，即新的圖像的分辨率是原來的1/2，相應(yīng)的像素值為：8 4哈爾變換舉例哈爾變換舉例(續(xù)續(xù))步驟2：求差值(differencing)用2個像素表示這幅圖像時，圖像的信息已經(jīng)部分丟失。為了能夠從由2個像素組成的圖像重構(gòu)出由4個像素組成的原始圖像，就需要存儲一些圖像的細

25、節(jié)系數(shù)(detail coefficient)，以便在重構(gòu)時找回丟失的信息。原始圖像可用下面的兩個平均值和兩個細節(jié)系數(shù)表示，8 4 1 -1步驟3：重復步驟1和2把由第一步分解得到的圖像進一步分解成分辨率更低的圖像和細節(jié)系數(shù)。在這個例子中，分解到最后，就用一個像素的平均值6和三個細節(jié)系數(shù)2,1和1表示整幅圖像：6 2 1 -1哈爾變換過程哈爾變換過程分辨率 平均值 細節(jié)系數(shù)4 9 7 3 528 4 1 -11 6 2n把由4像素組成的一幅圖像用一個平均像素值和三個細節(jié)系數(shù)表示n這個過程就叫做哈爾小波變換(Haar wavelet transform)，也稱哈爾小波分解(Haar wavele

26、t decomposition)n這個概念可以推廣到使用其他小波基的變換3. 哈爾變換的特性哈爾變換的特性從這個例子中我們可以看到：變換過程中沒有丟失信息，因為能夠從所記錄的數(shù)據(jù)中重構(gòu)出原始圖像。對這個給定的變換，我們可以從所記錄的數(shù)據(jù)中重構(gòu)出各種分辨率的圖像。例如，在分辨率為1的圖像基礎(chǔ)上重構(gòu)出分辨率為2的圖像，在分辨率為2的圖像基礎(chǔ)上重構(gòu)出分辨率為4的圖像通過變換之后產(chǎn)生的細節(jié)系數(shù)的幅度值比較小，這就為圖像壓縮提供了一種途徑。例如，去掉一些微不足道的細節(jié)系數(shù)并不影響對重構(gòu)圖像的理解4. 一維哈爾小波變換一維哈爾小波變換求均值和差值的過程實際上就是一維小波變換的過程，現(xiàn)在用數(shù)學方法重新描述小

27、波變換的過程(1) 哈爾基函數(shù)哈爾基函數(shù)基函數(shù)是一組線性無關(guān)的函數(shù)，可以用來構(gòu)造任意給定的信號, 如用基函數(shù)的加權(quán)和表示。定義了基和矢量空間，就可以把由2j 個像素組成的一維圖像看成為矢量空間 中的一個矢量。最簡單的基函數(shù)是哈爾基函數(shù)(Haar basis function)。哈爾基函數(shù)在1909年提出，它是由一組分段常值函數(shù)(piecewise-constant function)組成的函數(shù)集。這個函數(shù)集定義在半開區(qū)間 上，每一個分段常值函數(shù)的數(shù)值在一個小范圍里是“1”，其他地方為“0”以圖像為例并使用線性代數(shù)中的矢量空間來說明哈爾基函數(shù)。這4個常值函數(shù)就是構(gòu)成矢量空間V 2的基 20( )

28、x21( ) x22( ) x23( )x20( )x21( ) x22( ) x23( )x012322221,01/41,1/41/2( )( )0,0,1,1/23/41,3/41( )( )0,0,xxxxxxxx其他其他其他其他20( )x21( )x22( )x23( )x哈爾基函數(shù)哈爾基函數(shù)(續(xù)續(xù)1)哈爾基函數(shù)哈爾基函數(shù)(續(xù)續(xù)2)為了表示矢量空間中的矢量，每一個矢量空間V j 都需要定義一個基(basis)為生成矢量空間 而定義的基函數(shù)也叫做尺度函數(shù)(scaling function)，這種函數(shù)通常用符號 表示。哈爾基函數(shù)定義為( )jix101( )0 xx其他哈爾基函數(shù)哈爾基

29、函數(shù)(續(xù)續(xù)3)哈爾基尺度函數(shù) 定義為 ( )jix( )(2),0,1,(21) jjjixxii其中，j 為尺度因子，改變j 使函數(shù)圖形縮小或者放大；i為平移參數(shù)，改變i使函數(shù)沿軸方向平移。 n空間矢量V j定義為( )0,21jjjiVspxi其中，表示線性生成(linear span) (2) 哈爾小波函數(shù)哈爾小波函數(shù)小波函數(shù)通常用 表示。與框函數(shù)相對應(yīng)的小波稱為基本哈爾小波函數(shù)(Haar wavelet functions)，并由下式定義，n哈爾小波尺度函數(shù) 定義為，( )ijx101/2( )11/210 xxx 當當其他( )ijx( )(2),0,(21) ijjjxxii哈爾小

30、波函數(shù)哈爾小波函數(shù)(續(xù)續(xù)1)用小波函數(shù)構(gòu)成的矢量空間用W j表示為，n根據(jù)哈爾小波函數(shù)的定義，可以寫出生成，W 0,W 1和W 2 等矢量空間的小波函數(shù) ( )0,1,21jjjiWspxi 其中，SP表示線性生成；j為尺度因子，改變j 使函數(shù)圖形縮小或者放大；i為平移參數(shù)，改變i 使函數(shù)沿軸方向平移哈爾小波函數(shù)哈爾小波函數(shù)(續(xù)續(xù)2)生成矢量空間W 2 的哈爾小波： 22012223101/812/83/8( )1 1/82/8( )13/84/80014/85/816/87/8( )15/86/8( )17/8100 xxxxxxxxxxxx 其他其他其他其他哈爾小波函數(shù)哈爾小波函數(shù)(續(xù)續(xù)3

31、)生成矢量空間W 2 的哈爾小波 (3) 哈爾小波變換過程哈爾小波變換過程用V2 中的哈爾基表示圖像9 7 3 5有2j =22=4個像素，因此可以用生成矢量空間中的框基函數(shù)的線性組合表示， 2222222200112233( )( )( )( )( )I xcxcxcxcx 其中的系數(shù) 是4個正交的像素值9 7 3 5，因此， 22220123,c c cc和22220123( )9( )7( )3( )5( ) I xxxxx哈爾小波變換過程哈爾小波變換過程(續(xù)續(xù)1)圖I(x)用V2中的哈爾基表示 用V 0, W 0和W1中的函數(shù)表示圖像生成矢量空間V 0的基函數(shù)為 ，生成矢量空間W 0的

32、小波函數(shù)為 ，生成矢量空間W1的小波函數(shù)為 和 ，根據(jù)哈爾小波變換過程哈爾小波變換過程(續(xù)續(xù)2)uI(x)可表示成00( ) x00( )x10( )x11( ) x2001VVWW0000111100000011( )( )( )( )( )I xcxdxdxdx其中，4個系數(shù) ， ， 和 就是原始圖像通過哈爾小波變換所得到的系數(shù)，用來表示整幅圖像的平均值和不同分辨率下的細節(jié)系數(shù)。4個函數(shù) , , 和 就是構(gòu)成空間V2的基。 哈爾小波變換過程哈爾小波變換過程(續(xù)續(xù)3)n用圖表示為00c00d10d11d00( )x00( )x10( ) x11( ) x一幅圖像是一個二維的數(shù)據(jù)陣列，進行小波

33、變換時可以對陣列的每一行進行變換，然后對行變換之后的陣列的每一列進行變換，最后對經(jīng)過變換之后的圖像數(shù)據(jù)陣列進行編碼1. 求均值與求差值使用求均值和求差值的方法，對矩陣的每一行進行計算3. 使用線性代數(shù)由于圖像可用矩陣表示，使用N個矩陣M1, M2，和MN 同樣可以對圖像矩陣進行求平均值和求差值。這N個矩陣分別是第一、第二和第N次分解圖像時所構(gòu)成的矩陣5. 二維哈爾小波變換二維哈爾小波變換二維哈爾小波變換二維哈爾小波變換(續(xù)續(xù)1)用小波對圖像進行變換有兩種方法，一種叫做標準分解(standard decomposition)，另一種叫做非標準分解(nonstandard decomposition)。標準分解方法是指首先使用一維小波對圖像每一行的像素值進行變換，產(chǎn)生每一行像素的平均值和細節(jié)系