小波分析及其應(yīng)用53579

1、 第八章 小波分析及應(yīng)用8.1 引言把函數(shù)分解成一系列簡(jiǎn)單基函數(shù)的表示，無(wú)論是在理論上，還是實(shí)際應(yīng)用中都有重要意義。1822年法國(guó)數(shù)學(xué)家傅里葉(J. Fourier 1768-1830)發(fā)表的研究熱傳導(dǎo)理論的“熱的力學(xué)分析”，提出并證明了將周期函數(shù)展開(kāi)為正弦級(jí)數(shù)的原理，奠定了傅里葉級(jí)數(shù)理論的基礎(chǔ)1。傅里葉級(jí)數(shù)理論研究的是把函數(shù)在三角函數(shù)系下的展開(kāi)，使得對(duì)信號(hào)和系統(tǒng)的研究歸結(jié)為對(duì)簡(jiǎn)單的三角函數(shù)的研究。傅里葉級(jí)數(shù)與傅里葉變換共同組成了平常所說(shuō)的傅里葉分析2。傅里葉級(jí)數(shù)用于分析周期性的函數(shù)或分布，理論分析時(shí)經(jīng)常假定周期是，定義如式(8.1-1)、(8.1-2)， (8.1-1)其中 (8.1-2)然

2、而，被分析函數(shù)的性質(zhì)并不能完整地由傅里葉系數(shù)來(lái)刻劃，這里有一個(gè)例子來(lái)說(shuō)明3：從任一個(gè)平方可和的函數(shù)出發(fā)，為了得到一個(gè)連續(xù)函數(shù)，只需或者增大f(x)的傅里葉系數(shù)的模，或者保持它不變并適當(dāng)?shù)馗淖兿禂?shù)的位相。因此，不可能僅根據(jù)傅里葉系數(shù)大小的階就預(yù)知函數(shù)的性質(zhì)（如大小、正則性）。傅里葉變換的定義如式(8.1-3)、(8.1-4) (8.1-3) (8.1-4)通過(guò)引入廣義函數(shù)或分布的概念，可獲得奇異函數(shù)（如沖擊函數(shù)）的傅里葉變換的存在。對(duì)于時(shí)域的常量函數(shù)，在頻域?qū)⒈憩F(xiàn)為沖擊函數(shù)，表明具有很好的頻域局部化性質(zhì)。由式(8.1-3)可知，為了得到，必須有關(guān)于f(x)的過(guò)去和未來(lái)的所有知識(shí)，而且f(x)在時(shí)

3、域局部值的變化會(huì)擴(kuò)散到整個(gè)頻域，也就是的任意有限區(qū)域的信息都不足以確定任意小區(qū)域的f(x)。在時(shí)域，哈爾(Haar)基是一組具有最好的時(shí)域分辨能力的正交基，它在時(shí)域上是完全局部化的，但在頻域的局部化卻很不好，這是由于哈爾系的兩個(gè)缺點(diǎn)：缺乏正則性與缺乏振動(dòng)性。研究者們希望尋找關(guān)于空間變量（或時(shí)間變量）與頻域變量都同時(shí)好的希爾伯特(Hilbert)基，R. Balian認(rèn)為：“在通訊理論中，人們對(duì)于在完全給定的時(shí)間內(nèi)，把一個(gè)振動(dòng)信號(hào)表示成由其中每一個(gè)都擁有足夠確定的位置與有一個(gè)頻率的小波的疊加這件事感興趣。事實(shí)上，有用的信息常常同時(shí)被發(fā)射信號(hào)的頻率與信號(hào)的時(shí)間結(jié)構(gòu)（如音樂(lè)）所傳遞。當(dāng)把一個(gè)信號(hào)表達(dá)

4、成時(shí)間的函數(shù)時(shí)，其中的頻譜表現(xiàn)并不好；相反地，信號(hào)的傅里分析卻顯示不了信號(hào)每一分量發(fā)射信號(hào)的瞬時(shí)與持續(xù)時(shí)間。一個(gè)適當(dāng)?shù)谋硎緫?yīng)結(jié)合這兩者互補(bǔ)描述的優(yōu)點(diǎn)，并用一個(gè)離散的刻劃來(lái)表示，以適應(yīng)通訊理論3?！睘榇?，人們提出了短時(shí)傅里葉變換（STFT）的概念：定義8.1-1 若選擇得使W與它的傅里葉變換滿(mǎn)足：那么使用W作為窗函數(shù)，在式(8.1-5)中引入的窗口傅里葉變換稱(chēng)為“短時(shí)傅里葉變換”(STFT)： (8.1-5)當(dāng)窗函數(shù)選擇為高斯(Gaussian)函數(shù)時(shí)，則為Gabor變換2。STFT的缺點(diǎn)是分析窗的大小和形狀是恒定的。因?yàn)轭l率與周期成反比，所以反映信號(hào)的高頻成份需要窄的時(shí)間窗，而反映信號(hào)的低頻成

5、份需要寬的時(shí)間窗，STFT無(wú)法滿(mǎn)足要求，此外，STFT的冗余很大，增加了不必要的計(jì)算量。小波變換作為能隨頻率的變化自動(dòng)調(diào)整分析窗大小的分析工具，自八十代中期以來(lái)得到了迅猛的發(fā)展，并在信號(hào)處理、計(jì)算機(jī)視覺(jué)、圖像處理、語(yǔ)音分析與合成等眾多的領(lǐng)域得到應(yīng)用。小波分析方法的出現(xiàn)可以追溯到1910年Haar提出Haar規(guī)范正交基，以及1938年Littlewood-Paley對(duì)傅里葉級(jí)數(shù)建立的L-P理論。為克服傳統(tǒng)傅里葉分析的不足，在八十年代初，便有科學(xué)家使用“小波”的概念來(lái)進(jìn)行數(shù)據(jù)處理，比較著名的是1984年法國(guó)地球物理學(xué)家Morlet引入小波的概念對(duì)石油勘探中的地震信號(hào)進(jìn)行存貯和表示。在數(shù)學(xué)方面所做的

6、探索主要是R. Coifman和G. Weiss創(chuàng)立的“原子”和“分子”學(xué)說(shuō)，這些“原子”和“分子”構(gòu)成了不同函數(shù)空間的基的組成部分。L. Carleron使用了非常象“小波”的函數(shù)構(gòu)造了Stein和Weiss的空間的無(wú)條件基。直到1986年，法國(guó)數(shù)學(xué)家Meyer成功地構(gòu)造出了具有一定衰減性的光滑函數(shù)，它的二進(jìn)伸縮與平移構(gòu)成的規(guī)范正交基。此前，人們普遍認(rèn)為這是不可能的，如Daubechies,Grossman和Meyer都退而研究函數(shù)系構(gòu)成的框架的條件去了。Lemarie和Battle繼Meyer之后也分別獨(dú)立地給出了具有指數(shù)衰減的小波函數(shù)。1987年，Mallat利用多分辨分析的概念，統(tǒng)一了

7、這之前的各種具體小波的構(gòu)造，并提出了現(xiàn)今廣泛應(yīng)用的Mallat快速小波分解和重構(gòu)算法。1988年Daubechies構(gòu)造了具有緊支集的正交小波基。Coifman, Meyer等人在1989年引入了小波包的概念。基于樣條函數(shù)的單正交小波基由崔錦泰和王建忠在1990年構(gòu)造出來(lái)。1992年A. Cohen, I. Daubechhies等人構(gòu)造出了緊支撐雙正交小波基。同一時(shí)期，有關(guān)小波變換與濾波器組之間的關(guān)系也得到了深入研究。小波分析的理論基礎(chǔ)基本建立起來(lái)。近年來(lái)，一種簡(jiǎn)明有效的構(gòu)造小波基的方法-提升方案(Lifting Scheme)得到很大的發(fā)展和重視4,5。利用提升方案可把現(xiàn)存的所有緊支撐小波

8、分解成更為基本的步驟6，另外，它還為構(gòu)造非線(xiàn)性小波提供了一種有力的手段，所以，利用提升方案構(gòu)造的小波被認(rèn)為是第二代小波5。小波理論及其應(yīng)用仍然處在發(fā)展中，其未來(lái)將在非線(xiàn)性多尺度方法、非規(guī)則集上的小波構(gòu)造以及非平穩(wěn)、非均勻、時(shí)變信號(hào)處理等方面等到更深入的研究。8.2 小波變換及其基本性質(zhì) 連續(xù)小波變換，的連續(xù)小波變換（有時(shí)也稱(chēng)為積分小波變換）定義為： (8.2-1)或用內(nèi)積形式： (8.2-2)式中要使逆變換存在，要滿(mǎn)足允許性條件： (8.2-3)式中是的傅里葉變換。這時(shí)，逆變換為 (8.2-4)這個(gè)常數(shù)限制了能作為“基小波（或母小波）”的屬于的函數(shù)的類(lèi)，尤其是若還要求是一個(gè)窗函數(shù)，那么還必須屬

9、于，即故是R中的一個(gè)連續(xù)函數(shù)。由式(8.2-3)可得在原點(diǎn)必定為零，即 (8.2-5)從式(8.2-5)可以發(fā)現(xiàn)小波函數(shù)必然具有振蕩性。連續(xù)小波變換具有如下性質(zhì)：性質(zhì)1（線(xiàn)性）：設(shè)，則性質(zhì)2（平移不變性）：若，則。平移不變性是一個(gè)很能好的性質(zhì)，在實(shí)際應(yīng)用中，盡管離散小波變換要用得廣泛一些，但在需要有平移不變性的情況下，離散小波變換是不能直接使用的。性質(zhì)3（伸縮共變性）：若，則，其中c>0。性質(zhì)4（冗余性）：連續(xù)小波變換中存在信息表述的冗余度。其表現(xiàn)是由連續(xù)小波變換恢復(fù)原信號(hào)的重構(gòu)公式不是唯一的，小波變換的核函數(shù)存在許多可能的選擇。盡管冗余的存在可以提高信號(hào)重建時(shí)計(jì)算的穩(wěn)定性，但增加了分析

10、和解釋小波變換的結(jié)果的困難。連續(xù)小波變換的離散化由于連續(xù)小波變換存在冗余，因而有必要搞清楚，為了重構(gòu)信號(hào)，需針對(duì)變換域的變量a ，b進(jìn)行何種離散化，以消除變換中的冗余，在實(shí)際中，常取，這時(shí)常簡(jiǎn)寫(xiě)為：。變換形式為：為了能重構(gòu)信號(hào)，要求是的Riesz基。定義8.2-1 一個(gè)函數(shù)稱(chēng)為一個(gè)R函數(shù)，如果在下述意義上是一個(gè)Risez基：的線(xiàn)性張成在中是稠密的，并且存在正常數(shù)A與B，使對(duì)所有二重雙無(wú)限平方可和序列成立，即對(duì)于的成立。假定是一個(gè)R函數(shù)，那么存在的一個(gè)唯一的Riesz基，它在意義上與對(duì)偶。這時(shí)，每個(gè)有如式(8.2-6)的唯一級(jí)數(shù)表示： (8.2-6)特別地，若構(gòu)成的規(guī)范正交基時(shí)，有重構(gòu)公式為：

11、(8.2-7)8.3 多分辨分析與Mallat算法8.3.1 多分辨分析Mallat使用多分辨分析的概念統(tǒng)一了各種具體小波基的構(gòu)造方法，并由此提出了現(xiàn)今廣泛使用的Mallat快速小波分解和重構(gòu)算法，它在小波分析中的地位與快速傅里葉變換在傅里葉分析中的地位相當(dāng)7。定義8.3-1 空間的多分辨分析是指構(gòu)造該空間內(nèi)一個(gè)子空間列，使其具有以下性質(zhì)：（1） 單調(diào)性（包容性）（2） 逼近性：（3） 伸縮性： （4） 平移不變性：（5）Riesz基存在性：存在，使得構(gòu)成的Riesz基。在定義8.3-1中，對(duì)應(yīng)于分辨率，在有些文獻(xiàn)中2,8，對(duì)應(yīng)于分辨率，這時(shí)，性質(zhì)（1）、（3）中子空間的下標(biāo)要做相應(yīng)的變化。定

12、理8.3-1 令是空間的一個(gè)多分辨分析，則存在一個(gè)唯一的函數(shù)使得 (8.3-1)必定是內(nèi)的一個(gè)標(biāo)準(zhǔn)正交基，其中稱(chēng)為尺度函數(shù)。式(8.3-1)中的系數(shù)是為了使的范數(shù)為1。引入尺度函數(shù)的目的是為了構(gòu)造正交小波基，圖8.3-1(a)為一指數(shù)衰減、連續(xù)可微分的尺度函數(shù)，圖(b)是其傅里葉變換。顯然，尺度函數(shù)與低通濾波器的形狀相同。(a)尺度函數(shù)的圖形 (b)尺度函數(shù)的傅里葉變換圖8.3-1 DB9尺度函數(shù)若生成一個(gè)多分辨分析，那么也屬于，并且因?yàn)槭堑囊粋€(gè)Riesz基，所以存在唯一的序列，它描述尺度函數(shù)的兩尺度關(guān)系： (8.3-2)由性質(zhì)（1）可知，所以 (8.3-3)反復(fù)應(yīng)用式(8.3-3)，得 (8

13、.3-4)同樣，象生成一樣，存在一個(gè)函數(shù)生成閉子空間，且有與式(8.3-2)類(lèi)似的雙尺度方程 (8.3-5)式(8.3-5)稱(chēng)為小波函數(shù)雙尺度方程。由式(8.3-2)、(8.3-5)可知，尺度函數(shù)與小波函數(shù)的構(gòu)造歸結(jié)為系數(shù)的設(shè)計(jì)，若令，則把尺度函數(shù)和小波函數(shù)的設(shè)計(jì)可以歸結(jié)為濾波器的設(shè)計(jì)。構(gòu)造正交小波時(shí)濾波器與必須滿(mǎn)足以下三個(gè)條件： (8.3-6) (8.3-7) (8.3-8)聯(lián)合求解式(8.3-7)和(8.3-8)可得 (8.3-9)由式(8.3-9)立刻可得 (8.3-10)所以，要設(shè)計(jì)正交小波，只需要設(shè)計(jì)濾波器。正交小波變換式(2.2-7)式說(shuō)明由一個(gè)函數(shù)的平移和伸縮所構(gòu)成的正交基在對(duì)信

14、號(hào)進(jìn)行分解和重構(gòu)方面是十分有用的。問(wèn)題是這樣的單個(gè)小波母函數(shù)是否存在呢？若存在是什么樣的呢？這樣的小波母函數(shù)是存在的，節(jié)的多分辨分析給出了具體的構(gòu)造方法，下面先給出幾個(gè)具有解析表達(dá)式的例子9。Haar小波母函數(shù)：Shannon小波母函數(shù)：Shannon小波母函數(shù)是無(wú)限次可導(dǎo)的，這比存在不連續(xù)點(diǎn)的Haar小波母函數(shù)要優(yōu)越，可是Haar系函數(shù)的支集是緊的，Shannon系的函數(shù)不僅不是緊支的，且當(dāng)時(shí)趨于零的速度僅為，故當(dāng)用Shannon系對(duì)函數(shù)進(jìn)行分解時(shí)，分解系數(shù)不能很好地反映信號(hào)的局部特征。Haar小波的缺點(diǎn)是不連續(xù)，利用卷積的方法可以將它變得光滑起來(lái)，通過(guò)正交化方法，這就構(gòu)成了由B樣條函數(shù)所生

15、成的正交小波函數(shù)。崔錦泰詳細(xì)研究了用基數(shù)-B樣條函數(shù)構(gòu)造小波的方法2。下面式(8.3-11)給出一個(gè)用B樣條構(gòu)造的正交小波母函數(shù)的例子，是用頻域表示的，理論上其時(shí)域表示可通過(guò)傅里葉反變換獲得，不過(guò)實(shí)際中只能通過(guò)數(shù)值運(yùn)算獲得其時(shí)域的函數(shù)圖形。 (8.3-11)Daubechies構(gòu)造了目前實(shí)際應(yīng)用中大量使用的具有有限支集的正交小波基，其對(duì)應(yīng)的濾波器是有限長(zhǎng)的10。不過(guò)無(wú)論是頻域還是時(shí)域，它們都沒(méi)有顯式的表達(dá)式，而且，除Haar基外所有其他正交緊支的小波函數(shù)、尺度函數(shù)關(guān)于實(shí)軸上的任何點(diǎn)都不具有對(duì)稱(chēng)或反對(duì)稱(chēng)性，因而所對(duì)應(yīng)的濾波器都不具有線(xiàn)性相位。下面是Daubechies小波濾波器的一個(gè)例子D4：。

16、更多的例子請(qǐng)參見(jiàn)附錄。8.3.3 雙正交小波變換在圖像處理中經(jīng)常希望所用濾波器具有線(xiàn)性相位，Cohen、Daubechies等人放棄了小波、尺度函數(shù)的正交性，給出了構(gòu)造具有對(duì)稱(chēng)性的雙正交基的方法，這時(shí)對(duì)應(yīng)的濾波器具有線(xiàn)性相位11。取代小波函數(shù)、尺度函數(shù)的正交性的是所謂的雙正交條件： (8.3-12) (8.3-13)此時(shí)相應(yīng)的多分辨分析子空間的嵌套序列分為兩種： (8.3-14)在雙正交的條件下，子空間與不是正交補(bǔ)空間，但是若令則有以下正交補(bǔ)的關(guān)系： (8.3-15)相應(yīng)的雙尺度方程為： (8.3-16)依據(jù)式(8.3-15)得 (8.3-17)所以，在設(shè)計(jì)雙正交小波濾波器時(shí)，實(shí)際上只要設(shè)計(jì)兩

17、個(gè)尺度濾波器。有關(guān)雙正交小波濾波器的例子請(qǐng)參見(jiàn)附錄。8.3.4 小波包變換短時(shí)傅里葉變換是一種等分析窗的分析方法，小波變換相當(dāng)于等Q濾波器組，語(yǔ)音、圖像比較適合用小波變換進(jìn)行分析，但并非所有信號(hào)的特性都與小波變換相適應(yīng)。以雷達(dá)為例，復(fù)雜目標(biāo)的回波，其包絡(luò)的起伏決定于目標(biāo)的姿態(tài)變化，而多譜勒頻率則取決于目標(biāo)的徑向速度，二者并無(wú)必然的聯(lián)系，所以在雷達(dá)里也經(jīng)常使用短時(shí)傅里葉變換。當(dāng)對(duì)某類(lèi)信號(hào)，等寬和等Q濾波器都不一定適用時(shí)，有必要按信號(hào)特性選用相應(yīng)組合的濾波器，這就引出了小波包的概念。Coifman及Wickerhauser在多分辨分析的基礎(chǔ)上提出了小波包的概念，可以實(shí)現(xiàn)對(duì)信號(hào)任意頻段的聚焦。小波包

18、的基本思想是對(duì)多分辨分析中的小波子空間也進(jìn)行分解，具體做法是：令 (8.3-18)定義子空間是函數(shù)的閉包空間，而是函數(shù)的閉包空間，并令滿(mǎn)足如下雙尺度方程： (8.3-19) (8.3-20)式中即兩系數(shù)也具有正交關(guān)系。其等價(jià)表示是： (8.3-21)定義8.3-2（小波包）：由式(8.3-19)、(8.3-20)構(gòu)造的序列稱(chēng)為由基函數(shù)確定的小波包?？臻g分解的子空間列可以寫(xiě)成，。若n是一個(gè)倍頻程細(xì)劃分的參數(shù)，即令，則有小波包的簡(jiǎn)略記號(hào)，其中。與小波相比較可知，小波包除了離散尺度和離散平移之外，還增加了一個(gè)頻率參數(shù)n，正是由于這個(gè)頻率參數(shù)的作用，使得小波包克服了小波時(shí)間分辨率高時(shí)頻率分辨率差的缺點(diǎn)

19、。n表示的零交叉?zhèn)€數(shù)，也就是其波形的振蕩次數(shù)。 8.3.5 一維Mallat算法Mallat在著名的用于圖像分解的金字塔算法(Pyramidal algorithm)的啟發(fā)下，結(jié)合多分辨分析，提出了信號(hào)的塔式多分辨分解與綜合算法，常簡(jiǎn)稱(chēng)為Mallat算法。設(shè)，并假定已得到在分辨率下的粗糙象，構(gòu)成的多分辨分析，從而有，即 (8.3-22)式中，于是 (8.3-23)由尺度函數(shù)的雙尺度方程可得利用尺度函數(shù)的正交性，有 (8.3-24)同理由小波函函數(shù)的雙尺度方程可得 (8.3-25)由式(8.3-23)、(8.3-24)和(8.3-25)立即可得： (8.3-26) (8.3-27) (8.3-2

20、8)引入無(wú)窮矩陣，其中則式(8.3-26)、(8.3-27)和(8.3-28)可分別表示為： (8.3-29)和 (8.3-30)其中分別是H和G的共軛轉(zhuǎn)置矩陣。式(8.3-29)為Mallat一維分解算法，式(8.3-30)為Mallat一維重構(gòu)算法，如圖8.3-2所示： H H H G G G (a)分解算法 (b)重構(gòu)算法圖8.3-2 Mallat小波分解和重構(gòu)算法示意圖利用Mallat分解與重構(gòu)算法進(jìn)行信號(hào)處理時(shí)，不必知道具體的小波函數(shù)是什么樣的，此外，在對(duì)數(shù)字信號(hào)進(jìn)行處理時(shí)，通常假定相應(yīng)的連續(xù)函數(shù)屬于，但即使如此，該函數(shù)在空間的投影的系數(shù)與由采樣得到的離散序列一般不一樣，但實(shí)際上都是

21、直接把由采樣得到的信號(hào)作為最高分辨率的信號(hào)來(lái)處理，這時(shí)更多的是把小波變換當(dāng)作濾波器組來(lái)看待。在實(shí)際應(yīng)用Mallat算法時(shí)，由于實(shí)際信號(hào)都是有限長(zhǎng)的，存在如何處理邊界的問(wèn)題。比較常用的方法是周期擴(kuò)展和反射擴(kuò)展。主要目的是要降低邊界不連續(xù)性所產(chǎn)生的在邊界上變換系數(shù)衰減慢的問(wèn)題。8.3.6 二維Mallat算法 在進(jìn)行圖像處理時(shí)要用到二維小波變換，目前研究中主要以可分離小波為主，下面的定理給出了構(gòu)造二維可分離正交小波基的方法。定理8.3-112 令是的可分離多分辨分析，并令是相應(yīng)的二維尺度函數(shù)，是與尺度函數(shù)對(duì)應(yīng)的一維標(biāo)準(zhǔn)正交小波。若定義三個(gè)“二維小波” (8.3-31)則 (8.3-32) 分別是內(nèi)

22、的標(biāo)準(zhǔn)正交基。設(shè)為待分析的圖像信號(hào)，其二維逼近圖像為 (8.3-33)式中 (8.3-34)利用尺度函數(shù)和小波函數(shù)的正交性，由式(8.3-32)、(8.3-33)和(8.3-34)立即得 (8.3-35)以及 (8.3-36)引入矩陣算子，令和分別代表用尺度濾波器系數(shù)對(duì)陣列的行和列作用的算子，和分別表示用小波濾波器系數(shù)對(duì)行和列作用的算子，二維Mallat分解算法為 (8.3-37)二維Mallat重構(gòu)算法為： (8.3-38)圖8.3-3示出了二維圖像的分解和重構(gòu)算法： 對(duì)行濾波 對(duì)列濾波 G 2 1 G 2 1 H 2 1 G 2 1 H 2 1 H 2 1 (a) 分解算法示意圖 1 2

23、G 1 2 G 1 2 H 1 2 G 1 2 H 1 2 H (b) 重構(gòu)算法示意圖圖例 2 1 下采樣：對(duì)列濾波時(shí)，兩列去一列，對(duì)行濾波時(shí)，兩行去一行 1 2 上采樣：對(duì)列濾波時(shí)，兩列中加0，對(duì)行濾波時(shí)，兩行中加0圖8.3-3 二維Mallat小波分解和重構(gòu)算法示意圖對(duì)圖2.2-3所示的二維小波分解與重構(gòu)算法，利用其可分離特性，在算法實(shí)現(xiàn)時(shí)分別由對(duì)行進(jìn)行一維小波變換，然后再對(duì)按行變換后的數(shù)據(jù)按列進(jìn)行一維小波變換來(lái)完成。與一維的情形類(lèi)似，在實(shí)際應(yīng)用中，由于圖像信號(hào)總是有限區(qū)域的，也存在如何處理邊界的問(wèn)題。典型的處理方法是周期擴(kuò)展和反射擴(kuò)展。在用小波變換進(jìn)行圖像壓縮時(shí)，由于邊界的不連續(xù)性，會(huì)使

24、得在邊界處的小波變換系數(shù)的衰減變慢，從而影響圖像的壓縮比，因而在圖像壓縮應(yīng)用中，若使用的是具有對(duì)稱(chēng)性質(zhì)的雙正交小波濾波器，一般對(duì)邊界采用反射擴(kuò)展的方式，使邊界保持連續(xù)，以提高壓縮性能。8.4 利用提升方案(Lifting Scheme)構(gòu)造小波8.4.1提升方案的基本原理小波函數(shù)通常定義為一個(gè)屬于空間的母小波的二進(jìn)伸縮(Dilates)和平移(Translate)： (8.4-1)這樣的小波稱(chēng)為第一代小波。然而，在更一般的情況下，小波并不必須是彼此的伸縮與平移，但仍然具有第一代小波的特點(diǎn)，這樣的小波稱(chēng)為第二代小波，利用提升方案可以構(gòu)造它們。第一代小波具有如下性質(zhì)：P1：是空間的Riesz基，還

25、是Lebesgue、Lipschitz、Sobolev和Besov空間的無(wú)條件基。P2：小波及其對(duì)偶在空間和頻域是局域化的，有些小波還是緊支的。P3：小波分析可納入多分辨分析的框架，這導(dǎo)致了快速小波變換算法。在研究中常有如下需要：G1：第一代小波提供了定義在上函數(shù)的基，但在象數(shù)據(jù)分割、在一般定義域上的微分和積分方程的求解，需要定義在任意的、可能不光滑的域上的小波。G2：第一代小波典型地只提供具有不變測(cè)度的空間的基，而微分方程的對(duì)角化、在曲線(xiàn)或表面上的分析等需要可適應(yīng)加權(quán)測(cè)度的基。G3：第一代小波隱含對(duì)數(shù)據(jù)進(jìn)行規(guī)則采樣，而實(shí)際問(wèn)題經(jīng)常要處理不規(guī)則采樣的數(shù)據(jù)。具有性質(zhì)P1-P3而又滿(mǎn)足G1-G3性

26、質(zhì)的第一代小波的推廣稱(chēng)為第二代小波。這兒的關(guān)鍵問(wèn)題是平移與伸縮并不是屬性P1-P3所必須的，放棄平移和伸縮，隱含著傅里葉變換不能再用作構(gòu)造工具。下面介紹利用提升方案構(gòu)造第二代小波的方法?？紤]信號(hào)，把X分成二個(gè)不相交的集合：偶下標(biāo)采樣和奇下標(biāo)采樣，通常情況下這兩個(gè)集合是緊密相關(guān)的，因而從一個(gè)集合能很好地建立另一個(gè)集合的預(yù)測(cè)P (8.4-2)知道了d和奇采樣值，可立即恢復(fù)信號(hào) (8.4-3)若P性能好，則d將是一個(gè)稀疏集，換言之，我們期望d的一階熵小于的。令 取 (8.4-4)利用相鄰兩偶采樣對(duì)奇采樣進(jìn)行預(yù)測(cè)，記下差值 (8.4-5)若信號(hào)是相關(guān)的，則大多數(shù)小波系數(shù)將很小。在理論上，我們可以繼續(xù)通

27、過(guò)對(duì)施加以上操作，然而，上述簡(jiǎn)單的操作性能并不好，為此引入另一個(gè)條件，即希望系數(shù)的平均值在每一次分解時(shí)保持一致，或者說(shuō)使，此前所進(jìn)行的下采樣很顯然不具有這種特點(diǎn)，我們可通過(guò)借助于對(duì)進(jìn)行提升來(lái)實(shí)現(xiàn)這點(diǎn)： (8.4-6)現(xiàn)在，每一級(jí)小波變換由兩步構(gòu)成：首先計(jì)算小波系數(shù)，其次提升下采樣系數(shù)。逆變換可立即得到：只需把式(8.4-6)中的加號(hào)換成減號(hào)，再把式(8.4-5)的等式中的項(xiàng)作一下移動(dòng)即可。整個(gè)計(jì)算過(guò)程如圖8.4-1所示： (a) 小波系數(shù)的幾何含義 -1/2 -1/2 -1/2 -1/2 1/4 1/4 1/4 1/4 (b) 分解過(guò)程圖8.4-1 提升方案示意圖從圖8.4-1中可以看出，在進(jìn)

28、行小波變換時(shí)，可進(jìn)行同址運(yùn)算，即不需要輔助存儲(chǔ)器，這對(duì)硬件實(shí)現(xiàn)十分有利。下面的定理給出提升方案的一般方法。定理8.4-1 給定雙正交濾波器算子的初始集合，那么可通過(guò)如下方法獲得一個(gè)新的雙正交濾波器算子集式中是一個(gè)從到的算子。證明：利用矩陣形式表示提升方案因?yàn)?有 根據(jù)雙正交濾波器的定義有所以 (8.4-7)另外 (8.4-8)根據(jù)定義，滿(mǎn)足式(8.4-7)(8.4-8)兩式的即為雙正交濾波器。 證畢。把小波變換分解成基本的提升步驟6已經(jīng)證明所有FIR小波濾波器都有能分解成基本的提升步驟6。用矩陣表示時(shí)，一個(gè)提升步驟對(duì)應(yīng)一個(gè)單元(elementary)矩陣。分解的基本理論依據(jù)是矩陣代數(shù)，根據(jù)矩陣

29、代數(shù)，任何具有多項(xiàng)式元素項(xiàng)且行列式為1的矩陣都可以分解成一系列的單元矩陣。首先把求自然數(shù)的最大公約數(shù)的Euclidean算法推廣到求兩個(gè)多項(xiàng)式的最大公因子。兩個(gè)多項(xiàng)式的公因子取決于因子,而且與自然數(shù)不同的是，在多項(xiàng)式的情形下，解并不是唯一的。定理8.4-2 （多項(xiàng)式的Euclidean 算法）。設(shè)有兩個(gè)多項(xiàng)式和，而且。令，從i=0開(kāi)始循環(huán)執(zhí)行以下步驟那么，如果n是使得的最小數(shù)。定理中定義為：若，則。用矩陣形式表示為相應(yīng)地式中。這樣，能整除、，如果是一個(gè)單項(xiàng)式的話(huà)，那么是互素的。為了把FIR小波濾波器(h, g)分解成基本的提升步驟，我們首先注意到必須是互素的78，而且，利用公約數(shù)的不唯一性，總

30、是可以使公約數(shù)為常量K，即對(duì)于給定的濾波器h，通過(guò)如下操作，總可以找到一個(gè)互補(bǔ)濾波器，即令 (8.4-9)在式(8.4-9)中 (8.4-10)當(dāng)i為奇時(shí)使用式(8.4-10)的第一個(gè)等式，當(dāng)i為偶時(shí)使用第二個(gè)等式，有 (8.4-11)通過(guò)一個(gè)提升步驟可獲得濾波器g，由以上分析可得如下定理定理8.4-3 給定互補(bǔ)濾波器對(duì)(h, g)，那么總是存在多項(xiàng)式和，以及一個(gè)常量K，使得與對(duì)偶濾波器對(duì)相關(guān)的多相(polyphase)矩陣為在正交小波濾波器時(shí)有，這就對(duì)應(yīng)著兩種不同的分解，也就是說(shuō)，把FIR小波濾波器分解成基本的提升步驟時(shí)，分解是不唯一的。利用提升方案進(jìn)行的小波變換如圖8.4-2所示： 2 1

31、 1/K LP z 1 2 K HP(a)利用提升方案進(jìn)行的小波分解示意圖 LP K + + 1 2 + HP 1/K + + 1 2 (b) 利用提升方案進(jìn)行的小波重構(gòu)示意圖圖8.4-2 利用提升方案進(jìn)行分解與重構(gòu)作為例子，下面給出對(duì)具有兩階消失矩的D4正交小波的分解：其中多相矩陣是因式分解是 (8.4-12)使用式(8.4-12)作為P(z)的分解，則分析用的多相矩陣為由此可得小波分解算法由分解算法，通過(guò)反向進(jìn)行操作，并改變相應(yīng)的符號(hào)可得重構(gòu)算法利用提升方案進(jìn)行小波變換具有可進(jìn)行同址運(yùn)算優(yōu)點(diǎn)，這樣在具體實(shí)現(xiàn)時(shí)可省去大量在存貯器開(kāi)銷(xiāo)，在進(jìn)行圖像處理時(shí)，這個(gè)優(yōu)點(diǎn)更為明顯。它的另一個(gè)優(yōu)點(diǎn)是可提高

32、小波變換的速度。所以把現(xiàn)存的有限長(zhǎng)小波濾波器分解成基本的提升步驟，可加快小波變換的進(jìn)行，根據(jù)Daubechies的分析，隨濾波器長(zhǎng)度的增加，運(yùn)算速度趨于常規(guī)小波變換的2倍，換言之，在同等的硬件條件下，對(duì)一維小波變換而言，運(yùn)算時(shí)間降低一半，對(duì)二維小波變換則降為原來(lái)的四分之一。這個(gè)優(yōu)點(diǎn)在實(shí)時(shí)性要求比較高的場(chǎng)合有很大的實(shí)用價(jià)值。整數(shù)小波變換13提升方案為擴(kuò)展小波變換的應(yīng)用領(lǐng)域提供了更多的靈活性。常規(guī)的小波變換都是采用浮點(diǎn)運(yùn)算的，但利用提升方案所帶來(lái)的便利，可十分方便地構(gòu)造整數(shù)到整數(shù)的小波變換。將整數(shù)小波變換用于圖像壓縮就可以用小波變換進(jìn)行無(wú)失真的圖像壓縮。最早的整數(shù)到整數(shù)小波變換是S變換，是哈爾（H

33、aar）變換的整數(shù)形式： (8.4-13)Said和Pearlman提出了S+P( tranSform + Prediction)，就是在S變換之后，利用低通濾波器的系數(shù)來(lái)產(chǎn)生一個(gè)新的高通濾波器系數(shù)，它的一般形式是： (8.4-14)式中。S和S+P變換的逆變換由式(8.4-13)、(8.4-14)把執(zhí)行順序變動(dòng)一下，再改變一下相關(guān)項(xiàng)的符號(hào)就可以獲得。通常小波濾波器的系數(shù)都是浮點(diǎn)數(shù)，只能把整數(shù)映射成浮點(diǎn)數(shù)，要進(jìn)行無(wú)失真變換，必須構(gòu)造把整數(shù)映射成整數(shù)的小波變換，提升方案（Lifting scheme）為此提供了一種有效的方法，所有正交或雙正交小波濾波器，用提升方案進(jìn)行分解后，都可用與S+P類(lèi)似的

34、方式來(lái)構(gòu)造變換的整數(shù)版本。用提升方案構(gòu)造小波變換有如下優(yōu)點(diǎn)： 1） 同址計(jì)算：即不需要輔助存儲(chǔ)器，原信號(hào)（圖像）可被小波變換的結(jié)果覆蓋。2） 更快的小波變換：傳統(tǒng)上，快速小波變換首先把信號(hào)分解成高通和低通成份，并進(jìn)行下抽樣，然后對(duì)低通成份重復(fù)進(jìn)行該過(guò)程直到所需要的變換級(jí)數(shù)。提升方案可把變換速度提高1倍。3） 不需借助傅氏分析便可獲得逆變換。實(shí)際上，只要簡(jiǎn)單地調(diào)整一下正變換中的正負(fù)號(hào)即可。此優(yōu)點(diǎn)使得不需要很強(qiáng)的傅氏分析的背景便可理解小波的特性和小波變換。S-變換的逆變換非常容易得到： (8.4-15)表8.4-1列出了幾個(gè)常用的可逆整數(shù)到整數(shù)小波變換。表8.4-1 可逆整數(shù)小波變換NameWav

35、elet Transform(4,4)(2+2,2)D4(9,7) 表中(4,4)表示分析小波和綜合小波的消失矩(Vanishing Moments)均為4。(2+2,2)表示通過(guò)一個(gè)額外的提升步驟使(2,2)變換的消失矩增加到4。D4是常見(jiàn)的4系數(shù)緊支撐Daubechies正交小波變換的整數(shù)變換形式。(9,7)是常用于圖像壓縮的7/9小波變換的整數(shù)形式，它的分析和綜合濾波器的消失矩也都為4。8.5小波圖像編碼8.5.1 小波變換圖像編碼的基本框架當(dāng)前所有常規(guī)小波編碼器都是變換編碼形式，主要由三部分構(gòu)成：解相關(guān)變換過(guò)程、量化過(guò)程和熵編碼過(guò)程,下面分別進(jìn)行描述。.1 解相關(guān)變換過(guò)程首先要解決的問(wèn)

36、題是小波基的選擇。但是，對(duì)于圖像編碼，很難確定哪種小波基是最優(yōu)的，因?yàn)橹T如光滑性、小波基支撐的尺寸以及頻率選擇性等指標(biāo)都很重要，在不同的要求下會(huì)產(chǎn)生不同的結(jié)果。另外，現(xiàn)在幾乎所有的小波編碼器采用的都是可分離二維小波變換，這使得可把二維小波基的設(shè)計(jì)轉(zhuǎn)化為一維小波基本的設(shè)計(jì)，由于可分離性所具有的局限，有理由認(rèn)為不可分離二維小波基將更為有效。在最優(yōu)基的選擇方面，研究者們已經(jīng)做了大量的工作。Unser14的研究表明樣條小波對(duì)基于近似理論的編碼應(yīng)用較為有效。Rioul15的實(shí)驗(yàn)結(jié)果說(shuō)明在壓縮應(yīng)用中，正交基的光滑性比較重要。Antonini等人16的實(shí)驗(yàn)表明光滑性和消失矩都很重要，而且光滑性顯得比消失矩要

37、稍微重要一些。Vetterli和Herley17又指出“正則性對(duì)信號(hào)處理的重要性如何仍然是一個(gè)公開(kāi)問(wèn)題(An Open Question)”。實(shí)際中常使用的小波基介于一階和二階連續(xù)可微，更多的光滑性似乎并不能對(duì)編碼產(chǎn)生明顯的改善。Billasenor等人系統(tǒng)地研究了所有長(zhǎng)度不大于36的雙正交小波濾波器組的性能，結(jié)果表明7/9小波濾波器性能最好18。該濾波器正是在實(shí)際中應(yīng)用最廣泛的一種。然而在應(yīng)用雙正交小波基時(shí)要注意，與正交小波基不同，它在變換域的平方誤差與圖像域的平方誤差并不相等，也就是說(shuō)在進(jìn)行量化時(shí)，在變換域使平方誤差最小并不能保證在圖像域也是最小的。另一個(gè)重要問(wèn)題是邊界的處理。由于實(shí)際的圖

38、像都是有限尺寸的，在把濾波器應(yīng)用于邊界時(shí)，簡(jiǎn)單的周期擴(kuò)展或者加零都會(huì)由于引入了不連續(xù)性，導(dǎo)致降低編碼性能，一個(gè)有效的方法是采用反射來(lái)擴(kuò)展圖像，它使邊界保持連續(xù)。.2 量化過(guò)程由于小波變換具有良好的解相關(guān)性能，大多數(shù)編碼器都采用標(biāo)量量化。如果我們事先知道各子帶系數(shù)的分布特性，可以采用熵約束下的Lloyd-Max量化器對(duì)各子帶進(jìn)行量化，但遺憾的是，通常我們并不具有這些先驗(yàn)知識(shí)。實(shí)際中經(jīng)常使用的量化器是均勻量化器，而且在高碼速率下，均勻量化器是最優(yōu)的19。均勻量化器具有簡(jiǎn)單、有效的特點(diǎn)，在性能上與Lloyd-Max量化器也很接近，還有一個(gè)額外的優(yōu)點(diǎn)是它可以產(chǎn)生出嵌入式的編碼比特流。比特分配決定了每個(gè)

39、子帶量化的精細(xì)程度。最優(yōu)比特分配是在一定的約束條件下，決定各子帶應(yīng)如何量化，以使誤差最小。本文隨后將給出一個(gè)利用模擬退火算法進(jìn)行最優(yōu)比特分配的方案。如前所述，對(duì)雙正交小波，變換域的誤差與圖像域的誤差并不相同，為使二者一致，要對(duì)變換域的各子帶的誤差進(jìn)行加權(quán)，不過(guò)對(duì)常用的7/9小波，加權(quán)系數(shù)都接近1，所以在實(shí)用中對(duì)7/9小波不進(jìn)行加權(quán)。.3 熵編碼過(guò)程典型的熵編碼有游程編碼、Huffman編碼和算術(shù)編碼，游程編碼通常用于對(duì)二值圖像的編碼20，Huffman需要在編碼前進(jìn)行概率統(tǒng)計(jì)或者使用固定的編碼表，在小波編碼器中不常用，算術(shù)編碼可以進(jìn)行自適應(yīng)編碼，且一般認(rèn)為它的效率要比Huffman編碼的效率高

40、，常用在小波編碼器中。使用自適應(yīng)算術(shù)編碼時(shí)，通過(guò)使用有效的自適應(yīng)概率估計(jì)技術(shù)可使編碼效率得到提高。有效的自適應(yīng)估計(jì)過(guò)程在文獻(xiàn)97和98中進(jìn)行了討論。8.6 SPIHT算法、性能分析及其實(shí)現(xiàn)在嵌入式零樹(shù)編碼算法EZW(Embedded Zerotree Wavelet)出現(xiàn)前，圖像壓縮，特別是有失真壓縮，它的計(jì)算復(fù)雜性與編碼效率是同步增長(zhǎng)的，然而，在1993年，J. M. Shapiro所提出的EZW21算法突破了該限制，它既十分有效，計(jì)算效率又高，近年，Amir Said 和William A. Pearlman提出的SPIHT(Set Partitioning in Hierarcical

41、Trees)算法22在此基礎(chǔ)上性能又有所提高，而且，即使不加算術(shù)編碼，SPIHT算法仍可與許多復(fù)雜算法的性能相當(dāng)。這兩種方法都基于有效樹(shù)量化(Significance Tree Quantization:STQ)技術(shù)，由于它們的性能優(yōu)良，即將在下世紀(jì)初出臺(tái)的JPEG2000標(biāo)準(zhǔn)已經(jīng)把小波變換選作基本變換方法，就如同DCT在上一版JPEG標(biāo)準(zhǔn)中的地位一樣。 嵌入式零樹(shù)編碼（EZW）算法Shapiro的EZW算法的主要特點(diǎn)是：1） EZW利用了一幅圖像的小波變換在不同級(jí)之間的相似性。Shapiro假定：如果在粗分辨率一個(gè)小波系數(shù)是無(wú)效的，所有在同一空間位置和方向上的系數(shù)也極有可能是無(wú)效的。結(jié)果表明

42、，這個(gè)假定是相當(dāng)有效的。Shapiro把小波系數(shù)組織成一系列的四叉樹(shù)形結(jié)構(gòu)，如下圖8.6-1所示。零樹(shù)根節(jié)點(diǎn)意味著所有在此子樹(shù)上的小波系數(shù)都是不重要的，因而除了要對(duì)樹(shù)根進(jìn)行編碼外，其他的節(jié)點(diǎn)都不需要編碼。為了獲得很低的比特率，零樹(shù)根符號(hào)的概率必須很高。各系數(shù)編碼的順序如圖8.6-2所示。掃描從最低頻率子帶LL3（假定是三級(jí)分解）開(kāi)始，結(jié)束于HH1。在移到下一子帶之間，要把當(dāng)前子帶的系數(shù)全部掃描完，所有的父節(jié)點(diǎn)先于子節(jié)點(diǎn)被掃描。顯然，這種掃描方式在編碼端和譯碼端都是一樣的。 LL3 HL3 LH1 HH1 HL2 HL1 LH2 HH2 LH1 HH1圖8.6-1 三級(jí)DWT時(shí)的父子依賴(lài)關(guān)系 L

43、L3 HL3 HL2 LH3 HH3 HL1 LH2 HH2 LH1 HH3圖8.6-2 三級(jí)小波的掃描順序2） 在按圖8.6-2所定義的掃描順序?qū)σ饬x圖（即有效小波系數(shù)的位置）進(jìn)行主編碼過(guò)程，使用了如下碼字：i) POS(positive significant),ii) NEG(negative significant)iii) IZ(isolated zero/insignificant),andiv) ZTR(root of a zerotree).在輔助編碼過(guò)程中，對(duì)單個(gè)比特信息進(jìn)行編碼，該單比特信息用于解碼時(shí)確定某小波系數(shù)是否被認(rèn)為是有效的。3） EZW是一種嵌入式編碼，所謂嵌入式

44、編碼，就是量化過(guò)程隱含在編碼過(guò)程中，它使得可逐步進(jìn)行編碼或譯碼，可在任何時(shí)候結(jié)束編譯碼過(guò)程，因而可精確地控制比特率。 在層次樹(shù)中的集劃分（SPIHT）算法SPIHT算法繼承了EZW算法的特點(diǎn)，但在兩個(gè)方面有本質(zhì)的不同：分割系數(shù)的方式和如何傳輸有效系數(shù)的位置信息。SPIHT算法把對(duì)有效系數(shù)位置的傳輸隱含在算法的執(zhí)行過(guò)程之中，并因此可以在允許峰值信噪比下降0.30.6dB時(shí)不采用算術(shù)編碼，使執(zhí)行速度更快。.1 算法所用的數(shù)據(jù)結(jié)構(gòu)及集合操作算法中用到以下集合：l H：所有空間方向樹(shù)的樹(shù)根的坐標(biāo)的集合；l O(i, j)：節(jié)點(diǎn)(i, j)的子節(jié)點(diǎn)集合，子節(jié)點(diǎn)指直接后繼；l D(i, j)：節(jié)點(diǎn)(i,

45、j)的后繼的集合；l L(i, j) = D(i, j) O(i, j).除了根節(jié)點(diǎn)外，對(duì)所有有子節(jié)點(diǎn)的節(jié)點(diǎn)(i, j)O(i, j) = (2i, 2j), (2i, 2j+1), (2i+1, 2j), (2i+1, 2j+1).集劃分規(guī)則是：1） 初始分割由集合(i, j)和D(i, j)形成，其中;2） 如果D(i, j)是有效的，則把它分割成L(i, j)和四個(gè)單元素集，每個(gè)元素；3） 如果L(i, j)是有效的，那么把它分割成四個(gè)集合D(k, l)， 其中。它的基本運(yùn)算是集測(cè)試： (8.6-1)判斷某集合是否有效就是看式(8.6-1)集測(cè)試的結(jié)果，若值為1則表示有效，否則表示是無(wú)效的。使用了三個(gè)鏈表來(lái)記錄相關(guān)信息：l LIS：無(wú)效集合鏈表(List of insignificant sets)l LIP：無(wú)效象素鏈表(List of insignificant pixels)l LSP：有效象素鏈表(List of significant pixels)LIP和LSP都是記錄坐標(biāo)信息，而LIS記錄的是集合信息，或者為D(i, j)，標(biāo)記為A， 或者為L(zhǎng)(i, j)，標(biāo)記為B。8.6.2.2 編碼算法完整的編碼算法是：步驟1. 初始化：輸出；