內(nèi)蒙古工業(yè)大學(xué) 多媒體技術(shù)(第5章)

第五章小波變換和小波圖像編碼

小波介紹一維哈爾小波變換二維哈爾小波變換小波圖像編碼5.1小波介紹小波分析是近二十年才發(fā)展起來、并迅速應(yīng)用到圖像處理和語音分析等眾多領(lǐng)域的一種數(shù)學(xué)工具。它是繼一百多年前的傅立葉分析之后的一個重大突破，無論對古老的自然科學(xué)還是對新興的高新技術(shù)應(yīng)用都產(chǎn)生了強烈沖擊。小波理論是應(yīng)用數(shù)學(xué)的一個新領(lǐng)域。要深入理解小波理論需要到比較多的數(shù)學(xué)知識。本章企圖從工程應(yīng)用角度出發(fā)，用比較直觀的方法來介紹小波變換和它的應(yīng)用，為讀者深入研究小波理論和應(yīng)用提供一些背景材料。小波簡史傅立葉理論指出，一個信號可以表示成一系列正弦和余弦函數(shù)之和，叫做傅立葉展開式。用傅立葉展開式表示一個信號時，只有頻率分辮率而沒有時間分辨率，這就意味我們可以確定信號中包含的所有頻率，但不能確定具有這些頻率的信號出現(xiàn)在什么時候。為了繼承博立葉分析的優(yōu)點，同時又克服它的缺點，人們一直在尋找新的方法。

20世紀(jì)初，哈爾(AlfredHaar)對在函數(shù)空間中尋找一個與傅立葉基類似的基非常感興趣。1909年他發(fā)現(xiàn)了小波，并被命名為哈爾小波(Haarwavelets)，他最早發(fā)現(xiàn)和使用了小波。20世紀(jì)70年代，當(dāng)時在法國石油公司工作的年輕的地球物理學(xué)家JeanMorlet提出了小被變換(wavelettransform，WT)的概念。進入20世紀(jì)80年代，法國的科學(xué)家Y．Meyer和他的同事開始為此開發(fā)系統(tǒng)的小波分析方法。Meyer于1986年創(chuàng)造性地構(gòu)造出具有一定衰減性的光滑函數(shù)，他用縮放(dilations)與平移(transltions)均為2j(j＞0的整數(shù))的倍數(shù)構(gòu)造了L2(R)空間的規(guī)范正交基，使小波得到真正的發(fā)展。

小波變換的主要算法則是由法國的科學(xué)家StephaneMallat在19884年提出。他在構(gòu)造正交小波基時提出了多分辨率的概念，從空間上形象地說明了小波的多分辨率的特件、提出了正交小波的構(gòu)造方法和快速算法，叫做Mallat算法。該算法統(tǒng)一了在此之前構(gòu)造正交小波基的所有方法。它的地位相當(dāng)于快速傅立葉變換在經(jīng)典傅立葉分析中的地位。InridDaubechies，RonaldCoifman和VictorWickerhaser等著名科學(xué)家把這個小波理論引入到工程應(yīng)用方面做出了極其重要的貢獻。例如，InridDubechies于1988年最先揭示了小波變換和濾波器組(filterbanks)之間的內(nèi)在關(guān)系，使離散小被分析變成為現(xiàn)實。 在信號處理中，自從S.Mallat和InridDaubchies發(fā)現(xiàn)濾波器組與小波基函數(shù)有密切關(guān)系之后，小波在信號(如聲音信號，圖像信號等)處理中得到極其廣泛的應(yīng)用。小波概念小波是定義在有限間隔而且其平均值為零的一種函數(shù)，它的波形如圖8-1(b)所示。圖8-1(a)是大家所熟悉的正弦波，圖8-1(b)是從許多使用比較廣泛的小波中挑選出的幾種一維小波。(1)首先把原始圖象順序分割成8×8子塊;(2)采樣精度為P位(二進制),把[0,2P-1]范圍的無符號數(shù)變換成[-2P-1,2P-1]范圍的有符號數(shù),作為離散余弦正變換(FDCT)的輸入;(3)在輸出端經(jīng)離散余弦逆變換(IDCT)后又得到一系列8×8子塊,需將數(shù)值范圍[-2P-1,2P-1]變換回[0,2P-1]來重構(gòu)圖象。

量化的作用:在一定主觀保真度圖象質(zhì)量前提下,丟掉那些對視覺影響不大的信息,通過量化可調(diào)節(jié)數(shù)據(jù)壓縮比。

在眾多的小波中，選擇什么樣的小波對信號進行分析是一個至關(guān)重要的問題。使用的小波不同，分析得到數(shù)據(jù)也不同，這是關(guān)系到能否達到使用小波分析的目的問題。如果沒有現(xiàn)成的小波可用，那么還需要自己開發(fā)適用的小波。

小波函數(shù)在時域和領(lǐng)域中都應(yīng)該具有某種程度的平滑度(smoothness)和集中性(concentration)，這個復(fù)雜的概念在數(shù)學(xué)上使用消失矩(vanishingmoments)來描述，用N表示小波的消失矩的數(shù)目。例如，Daubechies小波簡寫成bdN，N數(shù)日的大小反映了Daubechies小波的平滑度和集中性。信號分析一般是為了獲得時間和頻率域之間的相互關(guān)系。傅立葉變換提供了有關(guān)頻率域的信息，但時間方面的局部化信息卻基本丟失。與傅立葉變換不問，小波變換通過平移母小波(motherwavelet)可獲得信號的時間消息，而通過縮放小波的寬度(或者叫做尺度)可獲得信號的頻率特性。 對母小波的縮放和平移操作是為了計算小波的系數(shù)，這些系數(shù)代表小波和局部信號之間的相互關(guān)系。本小節(jié)將介紹小波分析中常用的3個基本概念：連續(xù)小波變換、離散小波變換和小波重構(gòu)。小波分析信號分析一般是為了獲得時間和頻率域之間的相互關(guān)系。傅立葉變換提供了有關(guān)頻率域的信息，但時間方面的局部化信息卻基本丟失。與傅立葉變換不問，小波變換通過平移母小波(motherwavelet)可獲得信號的時間消息，而通過縮放小波的寬度(或者叫做尺度)可獲得信號的頻率特性。 對母小波的縮放和平移操作是為了計算小波的系數(shù)，這些系數(shù)代表小波和局部信號之間的相互關(guān)系。本小節(jié)將介紹小波分析中常用的3個基本概念：連續(xù)小波變換、離散小波變換和小波重構(gòu)。連續(xù)小波變換傅立葉分折是把一個信號分解成各種不同頻率的正弦波，因此正弦波是博立葉變換的基函數(shù)。同樣，小波分析是把一個信號分解成將原始小波經(jīng)過移位和縮放之后的一系列小波，因此小波同樣可以用作表示一些函數(shù)的基函數(shù)?？梢哉f，幾乎能夠用傅立葉分析的函數(shù)都可以用小波分析，因此小波變換也可以理解為用經(jīng)過縮放和平移的一系列函數(shù)代替傅入葉變換的正弦波。仔細(xì)觀察圖所示的正弦波和小波可以發(fā)現(xiàn)，用不規(guī)則的小波分析變化激烈的信號也許比用平滑的正弦波更有效，或者說對信號的基本特性描述得更好。數(shù)學(xué)上傅立葉分析的過程實際上是用傅立葉變換表示：這個式子的含義就是，傅立葉變換是信號f(t)與復(fù)數(shù)指數(shù)e-jwt(e-jwt=coswt-jsinwt)之積在信號存在的整個期間里求和。博立葉變換的結(jié)果是傅立葉系數(shù)F(w)，它是頻率w的函數(shù)。同樣，連續(xù)小波變換(continuouswavelettransform,CWT)用下式表示：這個式子的含義就是，小波變換是信號f(t)與被縮放和平移的小波函數(shù)ψ之積在信號存在的整個期間里求和。CWT變換的結(jié)果是許多小波系數(shù)C，這些系數(shù)是縮放因子(scale)相位置(position)的函數(shù)。CWT的變換過程可分成如下5個步驟：步驟1：把小波ψ(t)和原始信號f(t)的開始部分進行比較。步驟2；計算系數(shù)C。該系數(shù)表示該部分信號與小波的近似程度。系數(shù)C的值越高表示信號與小波越相似，因此系數(shù)C可以反映這種波形的相關(guān)程度。步驟3：把小波向右移，距離為k，得到的小波函數(shù)為ψ(t-k)，然后重復(fù)步驟1和2。再把小波向右移，得到小波ψ(t-2k)，重復(fù)步驟1和2。按上述步驟一直進行下去，直到信號f(t)結(jié)束。步驟4：擴展小波ψ(t)，例如擴展一倍，得到的小波函數(shù)為ψ(t/2)。步驟5：重復(fù)步驟1~4。小波變換完成之后得到的系數(shù)是在不同的縮放因子下由信號的不同部分產(chǎn)生的。這些小波系數(shù)、縮放因子和時間之間的關(guān)系和它們的含義可以用圖表示。該圖是用MATLAB軟件繪制的。小波的縮放因子與信號頻率之間的關(guān)系可以這樣來理解：縮放因子小，表示小波比較窄，度量的是信號細(xì)節(jié)，表示頻率w比較高；相反縮放因子大，表示小波比較寬，度量的是信號的粗糙程度，表示頻率w比較低。離散小波變換在計算連續(xù)小波變換時，實際上也是用離散的數(shù)據(jù)進行計算的，只是所用的縮放因子和平移參數(shù)比較小而已。不難想象，連續(xù)小波變換的計算量是驚人的。為了解決計算量的問題，縮放因子和平移參數(shù)都選擇2j(j＞0的整數(shù))的倍數(shù)。使用這樣的縮放因子和平移參數(shù)的小波變換叫做雙尺度小波變換(dyadicwavelettransform)，它是離散小波變換(discretewavelettransform,DWT)的一種形式。從文獻看，離散小波變換通常指的就是雙尺度小波變換。使用離散小波分析得到的小波系數(shù)、縮放因子和時間關(guān)系如圖8-5所示。圖8-5(a)是20世紀(jì)40年代使用Gabor開發(fā)的短時博立葉變換(shorttimeFouriertransform,STFT)得到的時間-頻率關(guān)系圖，圖8-5(b)是20世紀(jì)80年代使用Morlet開發(fā)的小波變換得到的時間-縮放因子(反映頻率)關(guān)系圖。執(zhí)行離散小波變換的有效方法是使用濾波器。該方法是Mallat在1988年開發(fā)的，叫做Mallat算法。這種方法實際上是一種信號的分解方法，在數(shù)字信號處理中稱為雙通道子帶編碼。用濾波器執(zhí)行離散小波變換的概念如圖8-6所示。圖中，S表示原始的輸入信號，通過兩個互補的濾波器產(chǎn)生A和D兩個信號，A表示信號的近似值(approximations)，D表示信號的細(xì)節(jié)值(Detail)。在許多應(yīng)用中，信號的低頻部分是最重要的，而高級部分起一個“添加劑”的作用。在小波分析中，近似值是大的縮放因子產(chǎn)生的系數(shù)，表示信號的低頻分量，而細(xì)節(jié)值是小的縮放因子產(chǎn)生的系數(shù)，表示信號的高頻分量。由此可見，離散小波變換可以表示成由低通濾波器和高通濾波器組成的一棵樹。原始信號通過這祥的一對濾波器進行的分解叫做一級分解。信號的分解過程可以疊代，也就是說可進行多級分解。如果對信號的高頻分量不再分解，而對低頻分量連續(xù)進行分解，就得到許多分辨率較低的低頻分量，形成如圖8-7所示的一棵比較大的樹。這種樹叫做小波分解樹(waveletdecompositiontree)。分解級數(shù)的多少取決于要分析的數(shù)據(jù)和用戶的需要。小波分解樹表示只對信號的低頻分量進行連續(xù)分解。如果不僅對信號的低頻分量進行連續(xù)分解，而且對高頻分量也進行連續(xù)分解，這樣不僅可得到許多分辨率較低的低頻分量。而且也可得到許多分辨率較低的高頻分量。這樣分解得到的樹叫做小波包分解樹(waveletpacketdecompositiontree)，這種樹是一個完整的二進制樹。圖8-8表示的是一棵三級小波包分解樹。小波包分解方法是小波分解的一般化，可為信號分析提供更豐富和更詳細(xì)的信息。例如，小波包分解樹允許信號S表示為

S=A1+AAD3+DAD3+DD2順便要提及的是，在使用濾波器對真實的數(shù)字信號進行變換時，得到的數(shù)據(jù)將是原始數(shù)據(jù)的兩倍。例如，如果原始信號的數(shù)據(jù)樣本為1000個，通過濾波之后每一個通道的數(shù)據(jù)均為1000個，總共為2000個。于是，根據(jù)尼奎斯特(Nyquist)采樣定理就提出了降采樣(downsampling)的方法，即在每個通道中每兩個樣本數(shù)據(jù)取一個，得到的離散小波變換的系數(shù)(coefficient)分別用cD和cA表示。如圖8-9所示。圖中的符號表示降采樣。小波重構(gòu)離散小波變換可以用來分析或者叫做分解信號，這個過程叫做分解或者分析。把分解的系數(shù)還原成原始信號的過程叫做小波重構(gòu)(waveletreconstruction)或者叫做合成(synthesis)，數(shù)學(xué)上叫做逆離散小波變換(inversediscretewavelettransform,IDWT)。 在使用濾波器做小波變換時包含濾波和降采樣兩個過程。在小波重構(gòu)時要包含升采樣(upsampling)和濾波過程。小波重構(gòu)的方法如圖8-10所示，圖中的符號表示升采樣。升采樣是在兩個樣本數(shù)據(jù)之間插入“0”，目的是把信號的分量加長。升采樣的過程如圖8-11所示。重構(gòu)過程中濾波器的選擇也是一個重要的研究問題，這是關(guān)系到能否重構(gòu)出滿意的原始信號的問題。在信號的分解期間，降采樣會引進畸變，這種畸變叫做混疊(aliasing)。這就需要在分解和重構(gòu)階段精心選擇關(guān)系緊密但不一定一致的濾波器才有可能取消這種混疊。低通分解濾波器(L)和高通分解濾波器(H)以及重構(gòu)濾波器(L’和H’)構(gòu)成一個系統(tǒng)，這個系統(tǒng)叫做正交鏡像濾波器(quadraturemirrorfilters,QMF)系統(tǒng)，如圖8-12所示。小波定義在數(shù)學(xué)上，小波定義為對給定函數(shù)局部化的函數(shù)。小波可由一個定義在有限區(qū)間的函數(shù)ψ(x)來構(gòu)造，ψ(x)稱為母小波(motherwavelet)或者叫做基本小波。一組小波基函數(shù)，{ψa,b(x)}，可通過縮放和平移基本小波ψ(x)來生成，其中，a為進行縮放的縮放參數(shù)，反映特定基函數(shù)的寬度(或者叫做尺度)；b為進行平移的平移參數(shù)，指定沿x軸平移的位置。當(dāng)a=2j和b=ia的情況下，一維小波基函數(shù)序列定義為：或者：本教材采用下面的表示法：其中，i為平移參數(shù)，j為縮放因子。函數(shù)f(x)以小波ψ(x)為基的連續(xù)小波變換定義為函數(shù)f(x)和ψa,b(x)的內(nèi)積，在1984年，A.Grossman和Morlet連續(xù)小波的逆變換為：其中，Cψ為母小波ψ(x)的允許條件(admissiblecondition)，其中，是在平方可積的實函數(shù)空間L2(R)。為的傅立葉，而5.2一維哈爾小波變換哈爾小波是小波系列中最簡單的小波。因此本節(jié)將從哈爾小波入手，首先介紹用來構(gòu)造任意給定信號的哈爾基因數(shù)，然后介紹表示任意給定信號的哈爾小波函數(shù)，最后介紹函數(shù)的規(guī)范化和哈爾基的構(gòu)造?；瘮?shù)是一組線性無關(guān)的函數(shù)，可以用來構(gòu)造任意給定的信號。例如，用基函數(shù)的加權(quán)和表示。最簡單的基函數(shù)是哈爾基函數(shù)(Haarbisisfunction)。啥爾基函數(shù)在1909年提出，它是由一組分段常值函數(shù)組成的函數(shù)集。這個函數(shù)集定義在半開區(qū)間：[0,1)上，每一個分段常值函數(shù)的數(shù)值在一個小范圍里是“1”，其他地方為“0”，現(xiàn)以圖像為例并使用線性代數(shù)中的矢量空間來說明哈爾基函數(shù)。如果一幅圖像僅由20＝1個像素組成．這幅圖像在整個[0,1)區(qū)間中就是一個常值函數(shù)。用表示這個常值函數(shù)，用V0表示由這個常值函數(shù)生成的矢量空間，即這個常值函數(shù)也叫做框函數(shù)(boxfunction)，它是構(gòu)成矢量空間V的基。如果一幅圖像內(nèi)21＝2個像素組成，這幅圖像在[0,1)區(qū)間中有兩個等間隔的子區(qū)間：[0,1/2)和[1/2,1)，每一個區(qū)間中各有1個常值函數(shù)，分別用表示。用V1表示由2個子區(qū)間中的常值函數(shù)生成的矢量空間，即這2個常值函數(shù)就是構(gòu)成矢量空間V1

的基。如果一幅圖像由2j＝22＝4個像素組成，這幅圖像在[0,1)區(qū)間中被分成4個等間隔的子區(qū)間：[0,1/4),[1/4,1/2),[1/2,3/4),[3/4,1)，它們的常值函數(shù)分別用表示，用V2

表示由4個子區(qū)間中的常值函數(shù)生成的矢量空間。4個常值函數(shù)就是構(gòu)成矢量空間V2的基。 可以按照這種方法繼續(xù)定義基函數(shù)和由它生成的矢量空間?？偠灾?，為了表示矢量空間中的矢量，每一個矢量空間Vj

都需要定義一個基(basis)。為生成矢量空間Vj

而定義的基函數(shù)也叫做尺度函數(shù)，這種函數(shù)通常用符號 表示。哈爾基函數(shù)定義為哈爾基尺度函數(shù)定義為其中，j為尺度因子，改變j使函數(shù)圖形縮小或者放大；i為平移參數(shù)，改變i使函數(shù)沿x軸方向平移?？臻g矢量Vj定義為：其中，sp表示線性生成(linearspan)。需要注意的是：有些文章使用負(fù)整數(shù)來定義尺度函數(shù)并且使用不同的符號規(guī)則。因此在閱讀有關(guān)小波方面的文章時要注意作者使用的符號規(guī)則。由于定義了基和矢量空間，就可以把由2j個像素組成的一維圖像看成為矢量空間Vj中的一個矢量。由于這些矢量都是在單位區(qū)間[0,1)上定義的函數(shù)，所以在Vj矢量空間中的每一個矢量也包含在Vj+1矢量空間中。這說明矢量空間Vj是嵌套的，即矢量空間Vj的這個性質(zhì)可寫成小波函數(shù)通常用 表示。與框函數(shù)相對應(yīng)的小波稱為基本哈爾小波函數(shù)(Haarwaveletfunctions)，并由下式定義：哈爾小波尺度函數(shù)定義為用小波函數(shù)構(gòu)成的矢量空間用Wj表示根據(jù)哈爾小波函數(shù)的定義，可以寫出生成W0，W1和W2等矢量空間的小波函數(shù)。用哈爾小波生成的矢量空間Wj包含在矢量Vj+1空間，這個性質(zhì)用下式表示： 在小波變換中，有時要對基函數(shù)和小波函數(shù)進行規(guī)范化。在半開區(qū)間[0,1)中，如果函數(shù)的內(nèi)積：則稱和是規(guī)范化的函數(shù)哈爾基和哈爾小波分別使用下面兩個式子進行規(guī)范化：

函數(shù)的規(guī)范化其中，常數(shù)因子2j/2用來滿足標(biāo)準(zhǔn)內(nèi)積(innerproduct)等于1的條件。如果小波函數(shù)不是在[0,1)區(qū)間中定義的函數(shù)，常數(shù)因子將改變。哈爾基的結(jié)構(gòu) 使用哈爾基函數(shù)和哈爾小波函數(shù)生成的矢星空間Vj和Wj具有下面的性質(zhì)：其中，符號“⊕”表示直和。這就是說，在矢量空間Vj+1中，根據(jù)所選擇的內(nèi)積，生成矢量空間Wj的所有函數(shù)與生成矢量空間Vj的所有函數(shù)都是正交的，即子空間Wj是子空間Vj的正交補。上式表明，在矢量空間Vj+1中，矢量空間Wj中的小波可用來表示一個函數(shù)在矢量空間Vj中不能表示的部分。因此，小波可定義為生成矢量空間Wj的一組線性無關(guān)的函數(shù)的集合。這些基函數(shù)具有兩個重要件質(zhì)：

(1)生成矢量空間Wj的基函數(shù)與生成矢量空間Vj的基函數(shù)構(gòu)成矢量中間Vj+1的—個基。

(2)生成矢量空間Wj的每—個基函數(shù)與生成矢量空間Vj的每—個基函數(shù)正交。哈爾小波變換 小波變換的基本思想是用一組小波函數(shù)或者基函數(shù)表示一個函數(shù)或者信號，例如圖像信號。為了理解什么是小波變換，下面用具體的例子來說明小波變換的過程。[例8.1]假設(shè)有一幅分辨率只有4個像素p0,p1,p2,p3的一維圖像，對應(yīng)的像素值或者叫做圖像位置的系數(shù)分別為：

[9735]計算它的哈爾小波系數(shù)。計算步驟如下：步驟1：求均值。[84]步驟2：求差值。[841-1]步驟3：重復(fù)步驟1和2。

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

(1)用V2中的哈爾基表示 圖像I(x)=[9735]有2j=22=4像素，因此可以用生成矢量空間V2中的框基函數(shù)的線性組合表示(2)用V1和W1中的函數(shù)表示根據(jù)因此，I(x)可表示為(3)用V0，W1和W2中的函數(shù)表示根據(jù)I(x)可表示成其中，4個系數(shù)c00,d00,d01,d11就是原始圖像通過哈爾小波變換所得到的系數(shù)，用來表示整幅圖像的平均值和不同分辨率下的細(xì)節(jié)系數(shù)。4個函數(shù)Φ00(x),Ψ00(x),Ψ01(x),Ψ11(x)就構(gòu)成V2空間的基。規(guī)范化算法規(guī)范化的小波變換與非規(guī)范化的小波變換相比，唯一的差別是在規(guī)范化的小波變換中需要乘一個規(guī)范化的系數(shù)。下面用例8.2說明。[例8.2]對函數(shù)

f(x)=[2,5,8,9,7,4,-1,1]作哈爾小波變換。 哈爾小波變換實際上是使用求均值和差值的方法進行分解。把f(x)看成是矢量空間V3中的一個向量，尺度因子j=3,因此最多可分解為3層，如圖8-22所示。fcA1cA2分解過程如下：步驟1：步驟2：步驟3：根據(jù)這個例子，可以歸納出規(guī)范化的哈爾小波變換的一般算法。假設(shè)一維陣列C有h個元素，h等于2的冪，執(zhí)行一維哈爾小波變換的偽代碼如下：procDecomposeArray(C:array[0…h(huán)-1]ofxolor):whileh>1do: h←h/2 fori←0toh-1do: C’[i]←(C[2i]+C[2i+1])/21/2 C’[h+i]←(C[2i]-C[2i+1])/21/2 endfor C←C’ endwhileendproc 5.3二維哈爾小波變換 前面已經(jīng)介紹了一維小波變換的基本原理和變換方法。這節(jié)將結(jié)合具體的圖像數(shù)據(jù)系統(tǒng)地介紹如何使用小波對圖像進行變換。 已經(jīng)知道，一幅圖像可看成是由許多像素組成的一個大矩陣，在進行圖像壓縮時，為降低對存儲器的要求，人們通常把它分成許多小塊。例如，以8×8個像素為一塊．并用矩陣表示，然后分別對每一個圖像塊進行處理。在小波變換中，由于使用的基函數(shù)的長度是可變的，雖然無需像以離散余弦變換(DCT)為基礎(chǔ)的JPEG標(biāo)準(zhǔn)算法那樣，把輸人圖像進行分塊，以避免產(chǎn)生JPEG圖像那樣的“塊效應(yīng)”，但為便于理解小被變換的奧妙，還是從一個小的圖像塊入手，并且繼續(xù)使用哈爾小波對圖像進行變換。圖像矩陣的計算假設(shè)有一幅灰度圖像，其中的一個圖像塊用陣列A表示為一個圖像塊是一個二維的數(shù)據(jù)陣列，進行小波變換時可以對陣列的每一行進行變換，然后對行變換之后的陣列的每一列進行變換，最后對經(jīng)過變換之后的圖像數(shù)據(jù)陣列進行編碼。在圖像塊陣列A中，第一行的像素值為：R0:[642361606757]N0:[3332333231-2927-25]N1:[32.532.50.50.531-2927-25]N2:[32.500.50.531-2927-25]使用求均值和求差值的方法，對矩陣的每一行進行計算，得到AR

：其中，每一行的第一個元素是該行像素值的平均值，其余的是這行的細(xì)節(jié)系數(shù)。使用同樣的方法，對AR的每一列進行計算，得到ARC

：其中，左上角的元素表示整個圖像塊的像素值，其余是該圖像塊的細(xì)節(jié)系數(shù)。根據(jù)這個事實，如果從矩陣中去掉表示圖像的某些細(xì)節(jié)系數(shù)，事實證明重構(gòu)的圖像質(zhì)量仍然可以接受。具體做法是設(shè)置一個閾值δ，例如δ≤5的細(xì)節(jié)系數(shù)就把它當(dāng)作“0”看待。這樣經(jīng)過變換之后的矩陣ARC就變成Aδ

：Aδ與ARC相比，“0”的數(shù)目增加了18個，也就是去掉了18個細(xì)節(jié)系數(shù)。這樣做的好處是可提高小波圖像編碼的效率。對Aδ

矩降進行逆變換．得到了重構(gòu)的近似矩陣：使用線性代數(shù)由于圖像可用矩陣表示，使用3個矩陣M1，M2和M3同樣可以對矩陣A進行求平均值和求差值。這3個矩陣分別是第1、第2和第3次分解圖像時所構(gòu)成的矩陣。現(xiàn)以矩陣A的第1行的數(shù)據(jù)為例，

[642361606757] 為簡化計算，可把3個矩陣相乘之后再計算。3個矩陣相乘的結(jié)果為：W=M1M2M3=如果使用規(guī)格化的小波進行計算，則W=M1M2M3=以上計算哈爾小波正變換的步驟就簡化成．

T=((AW)’W)’=(W’A’W)’=W’AW計算哈爾小波的逆變換簡化為：

(W’)-1TW-1=A (W-1)’TW-1=A變換實例 為進一步理解小波變換的基本原理和在圖像處理中的應(yīng)用，可使用MATLAB軟件中的小波變換工具箱(wavelettoolbox)編寫小波變換程序，對原始圖像進行分解和重構(gòu)。 圖8-25表示圖像分解和重構(gòu)過程。利用小波變換，用戶可以按照應(yīng)用要求獲得不問分辨率的圖像，如圖8-26所示。圖8-26(a)表示原始的Lena圖像；圖8-26(b)表示通過一級小波變換可得到1/4分辨率的圖像；圖8-26(c)表示通過二級小波變換可得到1/8分辨率的圖像；圖8-26(d)表示通過3級小波變換可得到1/16分辨率的圖像。閾值處理可用于去除圖像中的噪聲。在取不同閾值的情況下重構(gòu)圖像，可觀察到圖像質(zhì)量發(fā)生的變化。如圖8-27所示。圖8-27(a)表示原始的Lena圖像；圖8-27(b)表示閾值δ≤5的重構(gòu)圖像；圖8-27(c)表示閾值δ≤10的重構(gòu)圖像，而圖8-27(d)表示閾值δ≤20的重構(gòu)圖像。從圖中可以看到。隨著閾值的增大，圖像質(zhì)量也隨之降低。二維小波變換方法用小波對圖像進行變換有兩種方法：一種叫做標(biāo)準(zhǔn)分解(standarddecomposition)，另一種叫做非標(biāo)準(zhǔn)分解(nonstandarddecomposition)。標(biāo)準(zhǔn)分解力法是指首先使用一維小波對圖像每一行的像素值進行變換、產(chǎn)生每一行像素的平均值和細(xì)節(jié)系數(shù)；然后使用一維小波對這個經(jīng)過行變換的圖像的列進行變換．產(chǎn)生這個圖像的平均值和細(xì)訪系數(shù)。標(biāo)準(zhǔn)分解的過程如下：圖8-28表示標(biāo)準(zhǔn)分解方法，圖像是使用MATLAB編寫的程序分解得到的。非標(biāo)準(zhǔn)分解是指使用一維小波交替地對每一行和每一列像素值進行變換。首先對圖像的每一行計算像素對的均值和差值；然后對每一列計算像素對的均值和差值。這樣得到的變換結(jié)果只有1/4的像素包含均值。再對這1/4的均值重復(fù)計算行和列的均值和差值。依此類推。非標(biāo)唯分解的過程如下：圖8-29表示非標(biāo)準(zhǔn)分解方法，圖像是使用MATLAB編寫的程序分解得到的。標(biāo)準(zhǔn)分解方法和非標(biāo)準(zhǔn)分解方法相比，它們得到的變換結(jié)果是完全相同的，只是非標(biāo)準(zhǔn)算法的計算量可以少一些。5.4小波圖像編碼由于小波變換技術(shù)在20世紀(jì)90年代初期已經(jīng)比較成熟，因此從那時起就開始出現(xiàn)各稱新穎的小波圖像編碼方法。這些編碼方法包括EZW（embeddedzerotreewavelet,嵌入式零樹小波算法），在EZW算法基礎(chǔ)上改進的SPIHT（setpartitioninginhierarchicaltrees層樹分集算法）和EBCOT（embeddedblockcodingwithoptimizedtruncation,最佳截斷嵌入碼塊編碼）等。由于EZW算法的開拓給后來者帶來很大的啟發(fā)，它是一種有效而且計算簡單的圖像壓縮技術(shù)，因此本節(jié)將重點介紹。從子帶編碼到小波編碼子帶編碼(subbandcoding,SBC)的基本概念是把信號的頻率分成幾個子帶，然后對每個子帶分別進行編碼，并根據(jù)每個子帶的重要性分配不同的位數(shù)來表示數(shù)據(jù)。在20世紀(jì)70年代，子帶編碼開始用在語音編碼上。由于子帶編碼可根據(jù)子帶的重要性分別進行編碼等優(yōu)點，20世紀(jì)80年代中期開始在圖像編碼中使用。1986年Woods,J.W.等科學(xué)家曾經(jīng)使用一維正交鏡像濾波器組(quadraturemirrorfilterbanks,QMF)把信號的頻帶分解成4個相等的子帶，如圖9-1所示。圖9-1(a)表示分解方法，圖9-1(b)表示其相應(yīng)的頻譜。這個過程可以重復(fù)，直到符合應(yīng)用要求為止。這樣的濾波器組稱為分解濾波器樹(decompositionfiltertrees)。多分辨率分析S.Mallat于1988年在構(gòu)造正交小波基時提出了多分辨率分析(multiresolutionanalysis)的概念。從空間上形象地說明了小波的多分辨率的特性，提出了正交小波的構(gòu)造方法和快速算法，叫做Mallat算法。根據(jù)Mallat和Meyer等科學(xué)家的理論，使用一級小波分解方法得到的圖像如圖9—2所示。如果在一級分解之后繼續(xù)進行分析，這種分解過程叫做多分辨率分析，實際上就是多級小波分解的概念。使用多級小波分解可以得到更多的分辨率不同的圖像，這些圖像叫做多分辨率圖像(multiresolutionimages)。圖9-3表示Lena的多分辨率圖像。其中，粗糙圖像1的分辨率是原始圖像的l/4，粗糙圖像2的分辨率是粗糙圖像1的1/4。濾波器組與多分辨率為了壓縮語音數(shù)據(jù)，在1976年Croisier,Esteban和Galand介紹了一種可逆濾波器組(invertiblefilterbank)，使用濾波和子采樣(subsampling)的方法用來把離散信號f(n)分解成大小相等的兩種信號，并且使用叫做共軛鏡像濾波器(conjugatemirrorfilters)的一種特殊濾波器來取消信號的混疊(aliasing)，這樣可從子采樣的信號中重構(gòu)原始信號f(n)。這個發(fā)現(xiàn)使人們花費了10多年的努力來開發(fā)一套完整的濾波器組理論。正交小波的多分辨率理論(multiresolutiontheory)已經(jīng)證明，任何共軛鏡像濾波器都可以用來刻畫一種小波ψ(t)，它能夠生成L2(R)實數(shù)空間中的正交基，而且快速離散小波變換可以使用串聯(lián)這些共軛鏡像濾波器來實現(xiàn)。連續(xù)小波理論和離散濾波器組之間的等效性揭示了數(shù)字信號處理和諧波分析之間關(guān)系，這就便人們一直在致力于解決它們之間的關(guān)系問題。從子帶編碼到小波編碼在過去的年代里，人們做了許多的努力來改進濾波器組的設(shè)計和子帶編碼技術(shù)。在小波編碼(waveletcoding,WC)技術(shù)的旗號下，人們提出了許多與子帶編碼技術(shù)非常類似和密切相關(guān)的方法。小波編碼技術(shù)中的一個重要的問題是如何構(gòu)造正交的小波基函數(shù)系列。正交的小波基函數(shù)系列可以在連續(xù)的時間域中構(gòu)造，但如何在離散的時間域中構(gòu)造是一個現(xiàn)實問題。在眾多的研究者中，Inrid

Daubechies在離散的時間域中構(gòu)造小波基函數(shù)方而做出了杰出的貢獻。她于1988年最先揭示了小波變換和濾波器組之間的內(nèi)在關(guān)系：離散時間濾波器(discrete-timefilters)或者正交鏡像濾波器(quadraturemirrorfilter,QMF)可以被疊代，并在某一種勻稱(regularity,可粗略理解為函數(shù)的平滑性)條件下可獲得連續(xù)小波。這是一個非常實際和極其有用的發(fā)現(xiàn)，意味著可使用有限沖擊響應(yīng)(finiteimpulseresponse,FIR)的離散時間濾波器來執(zhí)行小波分解，使用相同的濾波器可重構(gòu)小波分解之后的信號。由此可見，早期開發(fā)的子帶編碼實際上是一種小波變換。在Daubechies揭示小波變換和濾波器組之間的關(guān)系之前，在圖像編碼中小波技術(shù)并不流行。從20世紀(jì)90年代開始，Cohen,Daubechies和Feauveau,簡稱為CDF,系統(tǒng)地開發(fā)了構(gòu)造緊支持雙正交小波(compactlysupportedbiorthogonalwavelets)的方法，以及其他學(xué)者提出的各種算法，使小波技術(shù)在圖像編碼中得到廣泛的應(yīng)用。在構(gòu)造小波和開發(fā)小波變換算法中，比利時成長的年輕學(xué)者WimSweldens在1994年的博士論文中首先提出了“TheLiftingScheme”，簡稱Lifting/lifting(提升法)。該方法的基本思想是首先把信號分成偶數(shù)號樣本和奇數(shù)號樣本。根據(jù)信號本身的相關(guān)性，奇數(shù)樣本使用偶數(shù)樣本進行預(yù)測，由預(yù)測丟失的信號叫做信號的細(xì)節(jié)信息，然后調(diào)整偶數(shù)樣本以保存原始信號的粗糙信息和細(xì)節(jié)信息。該方法保留了小波分析的特性(時間頻率局部化和快速計算)，通過放棄小波的平移和縮放，并且放棄用傅立葉分析來構(gòu)造小波，從而解決了非無限信號或者非周期信號的小波和小波變換問題。也使計算速度得到很大的提高，因此被稱為第二代小波(secondgenerationwavelets)，現(xiàn)在也成為制定JPEG2000標(biāo)準(zhǔn)中小波部分的基礎(chǔ)。小波分解圖像方法使用小波變換把圖像分解成各種子帶的方法有很多種。例如，均勻分解(uniformdecomposition)，非均勻分解(non-uniformdecomposition)，八帶分解(octave-banddecomposition)和小波包分解(wavelet-packetdecomposition)，根據(jù)不同類型的圖像選擇不同小波的自適應(yīng)小波分解(adaptivewaveletdecomposition)等。其中，八帶分解是使用最廣泛的一種分解方法。這種分解方法屬于非均勻頻帶分割方法，它把低頻部分分解成比較窄的頻帶，而對每一級分解的高頻部分不再進一步分解。圖9-4表示Lena圖像的數(shù)據(jù)分解。失真的度量方法 在圖像編碼系統(tǒng)中，評估編碼系統(tǒng)性能的一種方法是失真度量法，用峰值信號噪聲比(peaksignaltonoiseratio,PSNR)來衡量，定義為最大像素值與均方差(meansquareerror,MSE)之比，對8位二進制圖像，其中，其中，為原始圖像的像素值，為解壓縮之后的像素值。 在文獻中，評估編碼系統(tǒng)性能還使用其他方法。這些方法包括使用規(guī)格化均方差(normalizedmeansquareerror,NMSE)、信號噪聲比(signaltonoiseratio,SNR)和平均絕對誤差(meanabsoluteerror,MAE)來度量，分別定義為：其中，為原始圖像的像素值，為解壓縮之后的像素值。在電子工程中，信號噪聲比(SNR)一直是最流行的誤差度量指標(biāo)，在大多數(shù)情況下可提供很有價值的信息，在數(shù)學(xué)上也比較容易計算。信號噪聲比雖然也用在圖像編碼中，但由于它的數(shù)值與圖像編碼系統(tǒng)中高壓縮比的關(guān)系不容易體現(xiàn)，因此提出了其他的幾種度量方法，包括平均主觀評分(meanopinionscore，MOS)。5.4.1EZW編碼在1992年，Lewis,A.S.和Knowles,G.首先介紹了一種樹形數(shù)據(jù)結(jié)構(gòu)來表示小波變換的系數(shù)。在1993年，Shapiro,J.M.把這種樹形數(shù)據(jù)結(jié)構(gòu)叫做“零樹(zerotree)”，并且開發(fā)了一個效率很高的算法用于熵編碼，他的這種算法叫做嵌入(式)零樹小波(embeddedzerotreewavelet,EZW)算法。EZW主要用于與小波變換有關(guān)的二維信號的編碼、但不局限于二維信號。嵌入(式)零樹小波中的“小波”是指該算法以離散小波變換為基礎(chǔ)，以大的小波變換系數(shù)比小的小波變換系數(shù)更重要，以及高頻子帶中的小系數(shù)可以被拋棄的事實為背景?！傲銟洹笔侵感〔ㄗ儞Q系數(shù)之間的一種數(shù)據(jù)結(jié)構(gòu)，因為離散小波變換是一種多分辨率的分解方法。每一級分解都會產(chǎn)生表示圖像比較租糙(低頻圖像)和比較精細(xì)(高額圖像)的小波系數(shù)；在同一方向和相同空間位置上的所有小波系數(shù)之間的關(guān)系可用一棵樹的形式表示，如果樹根和它的子孫的小波系數(shù)的絕對值小于某個給定的閾值T(threshold)，那么這棵樹就叫做零樹?！扒度搿笔菨u進編碼(progressiveencoding)技術(shù)的另一種說法。其含義是指一幅圖像可以分解成一幅低分辨率圖像和分辨率由低到高的表示圖像細(xì)節(jié)的許多子圖像，圖像合成的過程與分解的過程相反，使用子圖像生成許辨率不同的圖像。EZW編碼指的是，按照用戶對圖像分辨率的要求，編碼器可以進行多次編碼；每進行一次編碼，閾值降低1/2，水平和垂直方向上的圖像分辨率各提高1倍。編碼從最低分辨率圖像開始掃描，每當(dāng)遇到幅度大于閾值的正系數(shù)就用符號P表示，幅度的絕對值大于閾值的負(fù)系數(shù)用符號N表示，樹根節(jié)點上的系數(shù)幅度小于閾值而樹枝中有大于閾值的非零樹用符號Z表示，零樹用符號T表示。小波圖像編碼(waveletimagecoding)的一般結(jié)構(gòu)如圖9-5所示，它主要由小波變換(wavelettransform)、量化(quantization)和熵編碼(entropyencoding)等3個模塊組成。小波變換不損失數(shù)據(jù)，但它是EZW算法具有漸進特性的基礎(chǔ)；量化模塊對數(shù)據(jù)會產(chǎn)牛損失，數(shù)據(jù)損失的程度取決于量化閾值的大小，EZW算法指的就是這個模塊的算法，它的輸出是符號集{P,N,T,Z,0,1}中的一系列符號；熵編碼模塊對每個輸入數(shù)據(jù)值精確地確定它的概率，并根據(jù)這些概率生成一個合適的代碼，使輸出的碼流(codestream)小于輸入的碼流。EZW算法是多分辨率圖像的一種編碼方法。對整幅圖像編碼一次，生成一種分辨率圖像，編碼一次叫做一遍掃描。每一遍掃描大致包含3個步驟：設(shè)置閾值、每個小波系數(shù)與閾值進行比較、量化系數(shù)和重新排序。在掃描過程中需要維護兩種表，一種是小波系數(shù)的符號表，另一種是量化表。零樹回顧二維小波變換的計算過程，不難想象各級子圖像中的系數(shù)是相關(guān)的。在說明零樹的概念之前，需要對小波變換得到的系數(shù)名稱和符號加以說明。現(xiàn)以3級分解的離散小波變換為例，圖9-6表示Lena圖像使用三級濾波器組做小波變換輸出的子圖像(subimage)。需要注意的是：分解之后的圖像的名稱在文獻上有很多種，除了子圖像之外，有的叫做子帶圖像(sub-bandimage)，有的把子圖像進一步區(qū)分為高頻子圖像和低頻子圖像，或者粗糙圖像和精細(xì)圖像等名稱。這些名稱從不同的角度反映圖像的特性，在不同的場合下使用可以收到異曲同工的效果。圖9-6中的數(shù)字1，2和3表示分解的級數(shù)編號，LL3表示第3級的低頻子圖像，在這個例子中，它是分辨率最低的子圖像。HL3表示第3級分解在水平方向上的子圖像，LH3表示第3級分解在垂直方向上的子圖像，HH3表示第3級分解在對角線方向上的子圖像，其他的組合符號依此類推。由于低頻于圖像的系數(shù)要比高頻子圖像的系數(shù)大，零樹編碼技術(shù)就是利用這個事實來設(shè)計編碼／解碼過程中每一級使用的量化器。各級子圖像中的系數(shù)之間的關(guān)系可以用樹的形式描述。如圖9-7(a)所示，最低頻率的子圖像在左上角，最高頻率的子圖像在右下角，由同一方向和相同空間位置上的所有小波系數(shù)組成一棵樹。例如，從第3級子圖像HH3、第2級子圖像HH2到第1級子圖像HH1的相應(yīng)位置上的所有系數(shù)構(gòu)成一棵下降樹。按箭頭所指的方向，各級系數(shù)的名稱分別用祖系數(shù)、父系數(shù)、子系數(shù)和孫系數(shù)來稱呼。舉例來說，LL3的系數(shù)為{63}，HH2和HH1中的系數(shù)分別為{3}和{4,6,3,-2}，由這些系數(shù)構(gòu)成的樹如圖9-7(b)所示。如果把{63}指定為父系數(shù),{3}就稱為子系數(shù)，而{4,6,3,-2}中的4個系數(shù)就稱為孫系數(shù)?，F(xiàn)在再來看零樹的概念。為便于比較，把圖9-7(b)所示的兩棵樹用圖9-8(a)和圖9-8(b)表示。假設(shè)編碼時開始的閾值T0＝32，由于63比32大，這樣的樹叫做非零樹，如圖9-8(a)所示。假設(shè)下一次編碼時的閾值T1＝16，把-13當(dāng)作父系數(shù)，它的幅度比16小，而它的所有4個子系數(shù)的幅度都比16小，這樣的樹叫做零樹，系數(shù)-13叫做零樹根，如圖9-8(b)所示。根據(jù)以上的分析，零樹的定義可概括為一句話：子孫系數(shù)都為零的樹。定義零樹的重要意義在于，如果一棵樹是零樹，那么這棵樹就可以用一個預(yù)先定義的符號來代表整棵樹，從而提高了壓縮比。 順便要指出的是，小波圖像系數(shù)結(jié)構(gòu)的形式不只是上面介紹的一種，也可能不是最好的一種。掃描方法EZW算法對小波系數(shù)進行編碼的次序叫做掃描。掃描子圖像系數(shù)的方法有兩種：一種叫做光柵掃描(rasterscan)，如圖9-9(a)所示；另一種叫做迂回掃描(mortonscan)，如圖9-9(b)所示。算法EZW算法可歸納為下面幾個主要步驟。(1)閾值T的選擇開始時的閾值T0通常按下式估算，其中，MAX(.)表示最大的系數(shù)值，Xi表示小波變換分解到第i級時的系數(shù)。以后每掃描一次，閾值減少一半。(2)給系數(shù)分配符號使用EZW算法編碼圖像時每一次掃描需要執(zhí)行兩種掃描，并產(chǎn)生兩種輸出的符號。第一種掃描叫做主掃描(dominantpass)，它的任務(wù)是把小波系數(shù)X與閾值T進行比較，然后指定表9-1中的4個符號之一，筆者把這種符號叫做系數(shù)符號，對整幅圖像掃描之后產(chǎn)生系數(shù)符號序列。第二種掃描叫做輔掃描(subordinatepass)，其任務(wù)是對主掃描取出的帶有符號P或者N的系數(shù)進行量化，產(chǎn)生代表對應(yīng)量化值的符號“0”和“1”，筆者把這種符號稱為量化符號。主掃描：掃描每一個系數(shù)以產(chǎn)生系數(shù)符號。

(1)如果系數(shù)幅度大于閾值(T)且為正數(shù)，輸出符號P(positive)，

(2)如果系數(shù)幅度的絕對值大于閾值(T)且為負(fù)數(shù)，輸出符號N(negative)，

(3)如果系數(shù)是零樹根，輸出T(zerotree)，

(4)如果系數(shù)幅