小波分析及應用附常用小波變換濾波器系數

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

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

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

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

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

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

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

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

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

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

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

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

13、3-4)同樣，象生成一樣，存在一個函數生成閉子空間，且有與式(8.3-2)類似的雙尺度方程 (8.3-5)式(8.3-5)稱為小波函數雙尺度方程。由式(8.3-2)、(8.3-5)可知，尺度函數與小波函數的構造歸結為系數的設計，若令，則把尺度函數和小波函數的設計可以歸結為濾波器的設計。構造正交小波時濾波器與必須滿足以下三個條件： (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)所以，要設計正交小波，只需要設計濾波器。正交小波變換式(2.2-7)式說明由一個函數的平移和伸縮所構成的正交基在對信號

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

15、的正交小波函數。崔錦泰詳細研究了用基數-B樣條函數構造小波的方法2。下面式(8.3-11)給出一個用B樣條構造的正交小波母函數的例子，是用頻域表示的，理論上其時域表示可通過傅里葉反變換獲得，不過實際中只能通過數值運算獲得其時域的函數圖形。 (8.3-11)Daubechies構造了目前實際應用中大量使用的具有有限支集的正交小波基，其對應的濾波器是有限長的10。不過無論是頻域還是時域，它們都沒有顯式的表達式，而且，除Haar基外所有其他正交緊支的小波函數、尺度函數關于實軸上的任何點都不具有對稱或反對稱性，因而所對應的濾波器都不具有線性相位。下面是Daubechies小波濾波器的一個例子D4：。更

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

45、的后繼的集合；l L(i, j) = D(i, j) O(i, j).除了根節(jié)點外，對所有有子節(jié)點的節(jié)點(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)和四個單元素集，每個元素；3） 如果L(i, j)是有效的，那么把它分割成四個集合D(k, l)， 其中。它的基本運算是集測試： (8.6-1)判斷某集合是否有效就是看式(8.6-1)集測試的結果，若值為1則表示有效，否則表示是無效的。

46、使用了三個鏈表來記錄相關信息：l LIS：無效集合鏈表(List of insignificant sets)l LIP：無效象素鏈表(List of insignificant pixels)l LSP：有效象素鏈表(List of significant pixels)LIP和LSP都是記錄坐標信息，而LIS記錄的是集合信息，或者為D(i, j)，標記為A， 或者為L(i, j)，標記為B。8.6.2.2 編碼算法完整的編碼算法是：步驟1. 初始化：輸出；置有效系數鏈表LSP為空，把所有根節(jié)點坐標加入無效系數鏈表LIP中，并且把有后繼的根節(jié)點標記為類型A加入無效系數集鏈表LIS中。步驟2.

47、 排序過程步驟2.1 對LIP中的每一表項(i, j)，進行如下操作輸出；如果，把(i, j)移至LSP，輸出的符號；步驟2.2 對LIS中的每一個表項(i, j)，進行如下操作步驟2.2.1 如果該表項具有類型A，那么，* 輸出；* 如果=1，那么對每一個，進行如下操作，- 輸出；- 若，那么把(k, l)加入LSP，輸出的符號；- 如果，那么把(k, l)加至LIP的尾部；如果，把(i, j)移到LIS的尾部，并且標記為類型B；否則，把(i, j)從LIS中刪除；步驟2.2.2 如果該表項具有類型B，那么進行如下操作，* 輸出；* 如果，那么，對每一個，將其標記為類型A，并將之加到LIS尾

48、部；把(i, j)從LIS中刪除。步驟3. 細化過程：對LSP中的每一個表項(i, j)， 不包含剛才步驟2中加入的，輸出系數的二進制表示的第n位有效位；步驟4. 量化級更新：把n減1，并轉向步驟2，直到達到要求的壓縮比。8.6.2.3 譯碼算法A. Said和 W. A. Pearlman并沒有明確給出譯碼算法，為完整起見，這里把譯碼算法也列出：步驟1. 初始化：讀入；置有效系數鏈表LSP為空，把所有根節(jié)點坐標加入無效系數鏈表LIP中，并且把有后繼的根節(jié)點標記為類型A加入無效系數集鏈表LIS中。步驟2. 排序過程步驟2.1 對LIP中的每一表項(i, j)，進行如下操作讀出一比特；如果，把(i, j)移至