正交變換第二組

正交變換第二組第1頁，共60頁，2023年，2月20日，星期六主要內(nèi)容

第一章沃爾什變換第二章小波變換第2頁，共60頁，2023年，2月20日，星期六第一章沃爾什變換1.1沃爾什函數(shù)1.2沃爾什變換1.3算法1.4應(yīng)用第3頁，共60頁，2023年，2月20日，星期六1.1沃爾什函數(shù)※※※函數(shù)值僅取“+1”、“-1”兩值的非正弦型的標(biāo)準(zhǔn)正交完備函數(shù)系。任何一個時間函數(shù)完全可以用多個沃爾什函數(shù)來表示。只定義在有限時間T內(nèi)，具有兩個自變量，時間變量t和序數(shù)n。函數(shù)通常表示為Wal(n,t)。第4頁，共60頁，2023年，2月20日，星期六

三種定義方法：按照沃爾什排列來定義（按列率排序）；按照佩利排列來定義（按自然排序）；按照哈達(dá)瑪排列來定義。第5頁，共60頁，2023年，2月20日，星期六拉德梅克函數(shù)集是一個不完備的正交函數(shù)集，由它可以構(gòu)成完備的沃爾什函數(shù)。把一個正弦函數(shù)進(jìn)行無限限幅就可以得到拉得梅克函數(shù)。拉得梅克函數(shù)包括n和t兩個自變量,用R(n,t)表示。它可以用下式來表示：

當(dāng)x=0時，sgn（x）無定義。拉德梅克函數(shù)第6頁，共60頁，2023年，2月20日，星期六按沃爾什排列定義的沃爾什函數(shù)是按列率排列的。通常把正交區(qū)間內(nèi)波形變號次數(shù)的二分之一稱為列率（按照函數(shù)的序數(shù)由正交區(qū)間內(nèi)過零點(diǎn)平均數(shù)來定義的）。函數(shù)的列率由下式?jīng)Q定：按沃爾什排列的沃爾什函數(shù)可由拉德梅克函數(shù)構(gòu)成，表達(dá)式如下：g(i)是i的格雷碼，g(i)k是此格雷碼的第K位數(shù)字，m為正整數(shù)。（1）按沃爾什排列的沃爾什函數(shù)第7頁，共60頁，2023年，2月20日，星期六按佩利排列的沃爾什函數(shù)也可由拉德梅克函數(shù)構(gòu)成，定義是如下：ik是將函數(shù)序號寫成自然二進(jìn)制碼的第K位數(shù)字，即

。（2）按佩利排列的沃爾什函數(shù)第8頁，共60頁，2023年，2月20日，星期六按哈達(dá)瑪排列的沃爾什函數(shù)也可由拉德梅克函數(shù)構(gòu)成，解析式如下：式中是把i的自然二進(jìn)碼反寫后的第k位數(shù)字,并且 也就是反寫后：（3）按哈達(dá)瑪排列的沃爾什函數(shù)第9頁，共60頁，2023年，2月20日，星期六由于哈達(dá)瑪排序的沃爾什函數(shù)是由2n（n=0,1,…）階哈達(dá)瑪矩陣(HadamardMatrix)得到的，而哈達(dá)瑪矩陣的最大優(yōu)點(diǎn)在于它具有簡單的遞推關(guān)系，即高階矩陣可用兩個低階矩陣的克羅內(nèi)克積求得，因此我們重點(diǎn)介紹哈達(dá)瑪排列定義的沃爾什變換。2n階哈達(dá)瑪矩陣：遞推關(guān)系：第10頁，共60頁，2023年，2月20日，星期六三種定義下的沃爾什函數(shù)，盡管它們的排列順序各不相同，但三種排序方法得到的沃爾什函數(shù)有一定的關(guān)系。沃爾什函數(shù)三種定義之間的關(guān)系：WALp(i，t)WALw(i，t)WALH(i，t)比特倒置二進(jìn)碼寫，格雷碼讀格雷碼寫，二進(jìn)碼讀比特倒置格雷碼寫，倒置，二進(jìn)碼讀二進(jìn)碼寫，倒置，格雷碼讀圖1-1沃爾什函數(shù)關(guān)系圖第11頁，共60頁，2023年，2月20日，星期六以沃爾什函數(shù)為基礎(chǔ)，將一個函數(shù)變換為取值為+1或-1為基向量構(gòu)成的級數(shù)。與傅里葉變換相比，沃爾什變換的主要優(yōu)點(diǎn)在于存儲空間少和運(yùn)算速度快，這一點(diǎn)對于圖像處理來說是至關(guān)重要的。

一維離散沃爾什變換

離散沃爾什-哈達(dá)瑪變換

二維離散沃爾什變換

快速沃爾什變換（FWHT）1.2沃爾什變換第12頁，共60頁，2023年，2月20日，星期六

一維離散沃爾什變換定義：

一維離散沃爾什逆變換定義：1.2.1一維離散沃爾什變換第13頁，共60頁，2023年，2月20日，星期六

式中，代表N階沃爾什矩陣。是沃爾什變換系數(shù)序列；是時間序列。沃爾什變換矩陣式第14頁，共60頁，2023年，2月20日，星期六若將用哈達(dá)瑪矩陣表示，并將變換表達(dá)式寫成矩陣形式：

式中，為N階哈達(dá)瑪矩陣。1.2.2離散沃爾什-哈達(dá)瑪變換第15頁，共60頁，2023年，2月20日，星期六由哈達(dá)瑪矩陣的特點(diǎn)可知，沃爾什-哈達(dá)瑪變換的本質(zhì)上是將離散序列f(x)的各項(xiàng)值的符號按一定規(guī)律改變后，進(jìn)行加減運(yùn)算，因此，它比采用復(fù)數(shù)運(yùn)算的DFT和采用余弦運(yùn)算的DCT要簡單得多。第16頁，共60頁，2023年，2月20日，星期六將一維WHT的定義推廣到二維WHT。二維沃爾什-哈達(dá)瑪變換的指數(shù)式如下：二維沃爾什-哈達(dá)瑪變換的的逆變換式為：式中代表圖像的像素，是該像素在空間中的位置坐標(biāo)；代表變換系數(shù)；為正整數(shù)；是x，u的二進(jìn)制碼的第r位數(shù)字，

為正整數(shù)；是y，v的二進(jìn)制碼的第s位數(shù)字。1.2.3二維離散沃爾什變換第17頁，共60頁，2023年，2月20日，星期六二維沃爾什-哈達(dá)瑪變換的矩陣式定義如下：式中，和分別為和階哈達(dá)瑪矩陣第18頁，共60頁，2023年，2月20日，星期六類似于FFT，WHT也有快速算法FWHT。利用快速算法，完成一次變換只需

次加減法，預(yù)算速度可大大提高。快速沃爾什變換可由沃爾什-哈達(dá)瑪變換修改得到，所以下面著重討論一下沃爾什-哈達(dá)瑪快速變換。由離散沃爾什-哈達(dá)瑪變換的定義可知：

式中，，P為正整數(shù)。

1.2.4快速沃爾什變換（FWHT）第19頁，共60頁，2023年，2月20日，星期六以8階沃爾什-哈達(dá)瑪變換為例，討論分解過程及快速算法： 其中，均為酉陣。第20頁，共60頁，2023年，2月20日，星期六對于一般情況，則矩陣可以分解成P個矩陣之乘積，即第21頁，共60頁，2023年，2月20日，星期六由上面的分解有

令則

因?yàn)槎菍ΨQ矩陣，則

由此可得到兩種形式的蝶形運(yùn)算流程圖。所以任意2r階快速沃爾什-哈達(dá)瑪變換的碟式流程圖不難用上述方法引伸。第22頁，共60頁，2023年，2月20日，星期六法一：二維沃爾什-哈達(dá)瑪變換可以用一維沃爾什-哈達(dá)瑪變換來計(jì)算，其步驟如下：（1）以，對中個列中的每一列做變換，得到；（2）以，對中行中每一行做變換，即可得到二維變換系數(shù)。法二：將二維沃爾什-哈達(dá)瑪變換當(dāng)做一維來計(jì)算。這種方法是將數(shù)據(jù)矩陣的各列依次順序排列，這樣就形成由

個元素的列矩陣。然后再按一維沃爾什-哈達(dá)瑪變換方法來計(jì)算。

下面用事例說明一下兩種計(jì)算方法。1.3二維沃爾什-哈達(dá)瑪變換的計(jì)算第23頁，共60頁，2023年，2月20日，星期六

例：設(shè)數(shù)據(jù)矩陣如下，

求的二維沃爾什-哈達(dá)瑪變換。法一：首先對的每一列做變換：

第一列

第二列

第三列

第四列

所以

第24頁，共60頁，2023年，2月20日，星期六

對每一行做變換 第一行 第二行最后得到二維系數(shù)變換矩陣

第25頁，共60頁，2023年，2月20日，星期六法二： 將改寫成矩陣Y，即

對Y做以下變換

然后重排一下

顯然，與第一種算法的到的結(jié)果一致。第26頁，共60頁，2023年，2月20日，星期六下圖是一幅數(shù)字圖像及對其進(jìn)行二維WHT變換的結(jié)果。

圖1-2二維WHT結(jié)果（a）原圖像；（b）WHT結(jié)果

從以上例子可看出，二維WHT具有能量集中的特性，而且原始數(shù)據(jù)中數(shù)字越是均勻分布，經(jīng)變換后的數(shù)據(jù)越集中于矩陣的邊角上。因此，二維WHT可用于壓縮圖像信息。1.4應(yīng)用第27頁，共60頁，2023年，2月20日，星期六 綜上所述，WHT是將一個函數(shù)變換成取值為＋1或－1的基本函數(shù)構(gòu)成的級數(shù)，用它來逼近數(shù)字脈沖信號時要比FFT有利。同時，WHT只需要進(jìn)行實(shí)數(shù)運(yùn)算，存儲量比FFT要少得多，運(yùn)算速度也快得多。因此，WHT在圖像傳輸、通信技術(shù)和數(shù)據(jù)壓縮中被廣泛使用。第28頁，共60頁，2023年，2月20日，星期六第二章小波變換2.2離散小波變換2.4應(yīng)用2.3算法2.1連續(xù)小波變換第29頁，共60頁，2023年，2月20日，星期六背景知識傅立葉變換：提供了頻率域的信息，但丟失了時間域的局部化信息。小波變換:是對一個函數(shù)在時間和頻率上進(jìn)行局部化分析的一種數(shù)學(xué)變換。通過平移母小波(motherwavelet)獲得信號的時間信息。通過縮放母小波的寬度(或稱尺度)獲得信號的頻率特性。對母小波的平移和縮放操作是為計(jì)算小波的系數(shù)，這些系數(shù)代表局部信號和小波之間的相關(guān)程度。從而達(dá)到變換目的：獲得時間和頻率域之間的相互關(guān)系。第30頁，共60頁，2023年，2月20日，星期六2.1連續(xù)小波變換連續(xù)小波變換（ContinuousWaveletTransform，CWT）用下式表示：

上式表示小波變換是信號f(t)與被縮放和平移的小波函數(shù)ψ()之積在信號存在的整個期間里求和的結(jié)果。CWT的變換結(jié)果是許多小波系數(shù)C，這些系數(shù)是縮放因子（scale）和平移（positon）的函數(shù)。第31頁，共60頁，2023年，2月20日，星期六2.1.1小波小波的選擇既不是唯一的也不是任意的：這里是歸一化地具有單位能量的解析函數(shù)，他應(yīng)滿足以下條件：（1）具有有限的持續(xù)時間和突變的頻率和振幅。（2）在有限的時間范圍內(nèi)，它的平均值等于零，即（高階矩也為0）.

第32頁，共60頁，2023年，2月20日，星期六圖2-1（a）正弦波曲線（b）小波曲線

上圖表示了正弦波和小波的區(qū)別，由此可以看出，正弦波從負(fù)無窮一直延續(xù)到正無窮，正弦波是平滑而且是可預(yù)測的，而小波是一類在有限區(qū)間內(nèi)快速衰減到0的函數(shù)，其平均值為0，小波趨于不規(guī)則、不對稱。綜上，可以概括為：小波應(yīng)是具有震蕩性和迅速衰減的波。第33頁，共60頁，2023年，2月20日，星期六

基本小波函數(shù)ψ()的縮放和平移操作含義如下：(1)縮放。簡單地講，縮放就是壓縮或伸展基本小波，縮放系數(shù)越小，則小波越窄，如圖2-2所示。（2）平移。簡單地講，平移就是小波的延遲或超前。在數(shù)學(xué)上，函數(shù)f(t)延遲k的表達(dá)式為f(t-k)，如圖2-3所示。圖2-3小波的平移操作(a)小波函數(shù)ψ(t)；(b)位移后的小波函數(shù)ψ(t-k)

圖2-2小波的縮放操作第34頁，共60頁，2023年，2月20日，星期六例：設(shè)函數(shù)具有有限能量，即，則小波變換的定義如下：

積分核為。a為尺度參數(shù)，b為位置參數(shù)，為小波。若，函數(shù)具有伸展作用；，函數(shù)具有收縮作用。小波隨伸縮參數(shù)a，平移參數(shù)b而變化。隨參數(shù)a的減小，的支撐區(qū)也就變大（支撐區(qū)或支集就是函數(shù)定義域的閉子集），而

頻譜隨之向高頻端展寬，反之亦然。這就有可能實(shí)現(xiàn)窗口大小自適應(yīng)變化，當(dāng)信號頻率增高時，時窗寬度變窄，而頻窗寬度增大，有利于提高時頻分辨率，反之也一樣。第35頁，共60頁，2023年，2月20日，星期六 小波的縮放因子與信號頻率之間的關(guān)系是：縮放因子scale越小，表示小波越窄，度量的是信號的細(xì)節(jié)變化，表示信號頻率越高；縮放因子scale越大，表示小波越寬，度量的是信號的粗糙程度，表示信號頻率越低。第36頁，共60頁，2023年，2月20日，星期六2.1.2二維連續(xù)小波變換定義：逆變換為：第37頁，共60頁，2023年，2月20日，星期六2.1.3小波變換傅立葉分析用一系列不同頻率的正弦波表示一個信號。一系列不同頻率的正弦波是傅立葉變換的基函數(shù)。小波變換用母小波通過移位和縮放后得到的一系列小波表示一個信號。一系列小波可用作表示一些函數(shù)的基函數(shù)。凡能用傅立葉分析的函數(shù)都可用小波分析小波變換可理解為用經(jīng)過縮放和平移的一系列函數(shù)代替傅立葉變換用的正弦波。用不規(guī)則的小波分析變化激烈的信號比用平滑的正弦波更有效，或者說對信號的基本特性描述得更好。第38頁，共60頁，2023年，2月20日，星期六2.2離散小波變換（DWT）在連續(xù)小波變換中，伸縮參數(shù)a和平移參數(shù)b連續(xù)取值，在每個可能的縮放因子和平移參數(shù)下計(jì)算小波系數(shù)，其計(jì)算量相當(dāng)大，將產(chǎn)生驚人的數(shù)據(jù)量，而且有許多數(shù)據(jù)是無用的。實(shí)際應(yīng)用中離散小波變換更適合于計(jì)算機(jī)處理。離散小波：

離散小波變換（DiscreteWaveletTransform，DWT）：第39頁，共60頁，2023年，2月20日，星期六2.2.1雙尺度小波變換（DyadicWaveletTransform） 縮放因子和平移參數(shù)都選擇為2j（j>0且為整數(shù)）的倍數(shù)，使用這樣的縮放因子和平移參數(shù)的小波變換稱為雙尺度小波變換，它是離散小波變換的一種形式。通常離散小波變換就是指雙尺度小波變換。第40頁，共60頁，2023年，2月20日，星期六2.2.2快速小波變換（Mallat算法） 執(zhí)行離散小波變換的有效方法是使用濾波器，該方法是Mallat于1988年提出的，稱為Mallat算法。Mallat算法本質(zhì)上不需要知道尺度函數(shù)和小波函數(shù)的具體結(jié)構(gòu)，只由系數(shù)就可以實(shí)現(xiàn)的分解與重構(gòu)，因此稱為快速小波變換。第41頁，共60頁，2023年，2月20日，星期六

用濾波器執(zhí)行離散小波變換的概念如圖2-4所示。S表示原始的輸入信號，通過兩個互補(bǔ)的濾波器組，其中一個濾波器為低通濾波器，通過該濾波器可得到信號的近似值A(chǔ)（Approximations），另一個為高通濾波器，通過該濾波器可得到信號的細(xì)節(jié)值D（Detail）。圖2-4小波分解示意圖2.2.3小波分解第42頁，共60頁，2023年，2月20日，星期六對于一個信號，如采用圖2-4所示的方法，理論上產(chǎn)生的數(shù)據(jù)量將是原始數(shù)據(jù)的兩倍。于是，根據(jù)奈奎斯特（Nyquist）采樣定理，可用下采樣的方法來減少數(shù)據(jù)量，即在每個通道內(nèi)（高通和低通通道）每兩個樣本數(shù)據(jù)取一個，便可得到離散小波變換的系數(shù)（Coefficient），分別用cA和cD表示，如圖2-5所示。圖中表示下采樣。圖2-5小波分解下采樣示意圖第43頁，共60頁，2023年，2月20日，星期六2.2.4小波重構(gòu)定義：利用信號的小波分解的系數(shù)還原出原始信號，這一過程稱為小波重構(gòu)（WaveletReconstruction）或叫做小波合成（WaveletSynthesis）。這一合成過程的數(shù)學(xué)運(yùn)算叫做逆離散小波變換（InverseDiscreteWaveletTransform，IDWT）。圖2-6

小波重構(gòu)算法示意圖第44頁，共60頁，2023年，2月20日，星期六1）重構(gòu)近似信號與細(xì)節(jié)信號由上圖可知，由小波分解的近似系數(shù)和細(xì)節(jié)系數(shù)可以重構(gòu)出原始信號。同樣，可由近似系數(shù)和細(xì)節(jié)系數(shù)分別重構(gòu)出信號的近似值或細(xì)節(jié)值，這時只要近似系數(shù)或細(xì)節(jié)系數(shù)置為零即可。圖2-7是對第一層近似信號或細(xì)節(jié)信號進(jìn)行重構(gòu)的示意圖。圖2-7

重構(gòu)近似和細(xì)節(jié)信號示意（a）重構(gòu)近似信號；(b)重構(gòu)細(xì)節(jié)信號第45頁，共60頁，2023年，2月20日，星期六2）多層重構(gòu)在圖2-6中，重構(gòu)出信號的近似值A(chǔ)1與細(xì)節(jié)值D1之后，則原信號可用A1＋D1＝S重構(gòu)出來。對應(yīng)于信號的多層小波分解，小波的多層重構(gòu)如圖2-8，可見重構(gòu)過程為：A3＋D3＝A2；A2＋D2＝A1；A1+D1＝S。圖2-8

多層小波重構(gòu)示意圖第46頁，共60頁，2023年，2月20日，星期六2.2.5二維離散小波變換二維離散小波變換是一維離散小波變換的推廣，其實(shí)質(zhì)上是將二維信號在不同尺度上的分解，得到原始信號的近似值和細(xì)節(jié)值。由于信號是二維的，因此分解也是二維的。分解的結(jié)果為：近似分量cA、水平細(xì)節(jié)分量cH、垂直細(xì)節(jié)分量cV和對角細(xì)節(jié)分量cD。同樣也可以利用二維小波分解的結(jié)果在不同尺度上重構(gòu)信號。二維小波分解和重構(gòu)過程如圖2-9所示。第47頁，共60頁，2023年，2月20日，星期六圖2-9

二維小波分解和重構(gòu)過程示意圖（a）二維DWT；(b)二維IDWT第48頁，共60頁，2023年，2月20日，星期六2.3Mallat算法尺度函數(shù)由尺度函數(shù)構(gòu)造小波是小波變換的必經(jīng)之路。尺度函數(shù)應(yīng)滿足下列條件：它是一個平均函數(shù)。即尺度函數(shù)是范數(shù)為1的規(guī)范化函數(shù)。

即尺度函數(shù)對所有的小波是正交的。即尺度函數(shù)對于平移是正交的。

即某一尺度上的尺度函數(shù)可以由下一尺度的線性組合得到，hn是尺度系數(shù)。尺度函數(shù)與小波是有關(guān)聯(lián)的。式中，是歸一化因子，是有尺度系數(shù)導(dǎo)出的系數(shù)。這說明小波可以由尺度函數(shù)的伸縮和平移的線性組合獲得，這就是構(gòu)造小波正交基的途徑。第49頁，共60頁，2023年，2月20日，星期六（2）由離散小波的定義，如果把t也離散化，并選擇，則可得到二進(jìn)制小波：Mallat算法描述設(shè)V0是給定的多分辨率尺度空間，尺度因子m=0，相應(yīng)的尺度函數(shù)為:第50頁，共60頁，2023年，2月20日，星期六小波函數(shù)為：若，則正交小波分解為：當(dāng)m=1時，則令當(dāng)尺度因子m=1轉(zhuǎn)到m=2時，相應(yīng)于第51頁，共60頁，2023年，2月20日，星期六需補(bǔ)充細(xì)節(jié)信息d1，則類似的則。因此可得：

為建立和的系數(shù)之間的關(guān)系，代換角標(biāo)n用k代之，j用n代之則有：第52頁，共60頁，2023年，2月20日，星期六由此可得：由此推廣至系數(shù)表達(dá)的一般式：該式就是由小波系數(shù)和重構(gòu)函數(shù)f（t）的正交展開式系數(shù)的公式。函數(shù)f(t)的小波展開系數(shù)和

用雙尺度差分公式表示可按下式計(jì)算：第53頁，共60頁，2023年，2月20日，星期六同理：第54頁，共60頁，2023年，2月20日，星期六計(jì)算步驟可按下列方法進(jìn)行：由計(jì)算和，再由計(jì)算和，直至尺度到m為止。上述的分析從信息處理的觀點(diǎn)來看，可認(rèn)為是一種濾波運(yùn)算。Mallat算法本質(zhì)上不需要知道尺度函數(shù)和小波函數(shù)的具體結(jié)構(gòu)，只由系數(shù)就可以