用于紋理圖像壓縮的分形算法的改進

曲波 高強 李大華 于曉

摘要：紋理是圖像中的重要部分，包含了大量的信息。紋理部分大多數為背景而被人所忽視。針對紋理圖像本身很強的自相似形以及分形算法中D塊池搜索時間過長和匹配原則過于繁瑣的問題，提出了一種結合矢量量化的方法，并對R塊和D塊采用了一種新的匹配原則。首先對D塊池中的D塊進行矢量量化處理，優(yōu)化碼書以減少搜索時間。然后提出了一種新的匹配原則IAM（圖像活動能量測度）并通過這個參數來配對R塊和D塊，從而實現分形編碼。

關鍵詞：紋理圖像；分型算法；矢量量化；IAM

分形圖像編碼算法是目前研究較為廣泛的編碼方法之一，對其研究已有近二十年的歷史。Mandelblot在早期提出了分形的理論，[1]Barnsley最早將分形的概念引入到圖像壓縮編碼領域，[2]但其編碼過程需要人工干預[3]；1989年Jacquin提出局部迭代函數系統(tǒng)（PIFS）的概念，實現了分塊的自動分形圖像編碼算法，[4]使分形圖像編碼取得了突破性進展，成為后人研究和擴展的起點。該算法具有許多優(yōu)點：它突破以往熵壓縮編碼的界限，在編碼過程中，采用了類似描述的方法，而解碼時通過迭代完成的，且具有分辨率無關的解碼特性等。[5]

紋理一直都是圖像處理中的一個關注點，對紋理圖像很難下一個確切的定義，類似于布紋、草地、磚砌地面等具有重復性結構的圖像稱為紋理圖像。一般來說紋理圖像中的灰度分布具有某種周期性，即便灰度變化是隨機的，它也具有一定的統(tǒng)計特性。J.K.霍金斯認為紋理的標志有三要素：一是某種局部的序列性，在該序列更大的區(qū)域內不斷的重復；二是序列是由基本部分非隨機排列組成的；三是各部分大致都是均勻的統(tǒng)一體，紋理區(qū)域內任何地方都有大致相同的結構尺寸。[6]

對于一般性的圖像，我們可以將之看成是紋理加上細節(jié)而成，細節(jié)對于一副圖像而言是蘊含重要信息的部分，而紋理部分大部分是用來作為背景的，具有強烈的區(qū)域相似性，而這部分往往又是人眼容易忽視的地方，所以這一部分的PSNR值要求不需要很高，所以我們可以采用次最優(yōu)的方法來還原紋理圖像以便獲得更高的壓縮比。

鑒于紋理圖像自身的特殊性以及分形編碼對于自相似性的一種支持，所以本文中將分形算法應用于紋理圖像的壓縮中。對于分形算法，很多文章都提出了了改進的方法，比如文獻[7]提出叉跡的方法[7]，文獻[8]提出的分數盒維數的方法[8]和文獻[9]提出的無搜索方案[9]。在本文中，通過將矢量量化的方法引入分形算法之中，提出一種LBGfractal相結合的分形算法以獲得更高的壓縮比，并提出一種新的塊匹配標準，最后通過匹配公式的改進加快了解碼的收斂速度，這樣就在保證一定的PSNR的基礎上提高了紋理圖像的壓縮效率。

1LBGFractal算法

首先我們來回顧一下傳統(tǒng)的分形算法的流程。

1.1對圖像進行預處理分割

將初始大小為N×N的灰度圖像I分割成互不相交的大小為R×R的方塊Ri（Rangeblock，稱為值域塊），即I=∪N/RiRi，且Ri∩Rj=（代表空集），Ri是分形壓縮中的每一個編碼單元。

1.2建立搜索空間

用2R×2R的截取窗口沿原圖像的水平和垂直方向（即x、y軸）分別以步長Δh和Δv移動，每一次移動后的截取方塊就構成了匹配塊Di（Domainblock，稱為定義域塊），所有這樣的匹配塊Di，就構成了搜索空間SD。

1.3尋找最優(yōu)匹配塊

在搜索空間內，對每一值域塊Ri，通過最小均方誤差（MSE）原則尋找誤差最小的匹配塊Di，使Di經適當的仿射變換ωi來逼近Ri，即DiωiRi，使之滿足

dRi，ωiDi=‖Ri-siAGDi+oi‖2

=minDI2‖RisiAGDi+oi‖2（1）

其中，G為固定的幾何變換，完成從Domain塊到Range塊的空間壓縮映射，通常用四點平均法（2×2采樣）；A為8種對稱旋轉變換之一，si和oi分別是灰度變換的尺度因子和偏移因子。

1.4生成編碼

通過搜索得到滿足的變換群集ωixi，yi，ai，si，oi（其中xi、yi表示Di的位置）就構成了PIFS，將PIFS記錄下來并進行ωi量化編碼，即得到每個Ri得分形碼（Fractalcodes）。

1.5迭代解碼

以任意灰度圖像（與待解碼圖像尺寸相同）作為初始點集，讀取PIFS中每一編碼塊Ri對應的仿射變換的參數，按與編碼過程中相同的順序作用到初始點集。反復迭代至收斂后，所得到的吸引子就是最終的解碼圖像。[10]

通過上述編碼流程我們可以看出，Domain塊所構成的D塊池SD是相當龐大的，對于一副512×512的圖像來說，R塊大小定義為4×4，D塊大小定義為8×8，那么SD就會有4096個D塊，這不管對于搜索還是存儲都是很大的負擔。而在這4096個D塊中，存在著相當大的冗余，也就存在繼續(xù)壓縮的可能性。[11]因此我們引入矢量量化中的LBG算法。LBG算法的中心思想是最近鄰合并原則，通過將距離最近的兩個矢量進行合并產生一個新的矢量來代替原來的兩個矢量從而達到縮減碼書大小的目的。

將LBG算法與傳統(tǒng)的Fractal算法結合的LBGFractal算法的流程如下：

1）將原始大小N×N的圖像（本實驗中采用的是512×512大小）分割成R×R大小的R塊（本實驗中采用的是4×4大小），構成初始編碼塊的集合。

2）用2R×2R大小的截取窗口沿原圖像的水平和垂直方向分別以一定步長移動（本實驗步長大小取的是R塊大小），每次截取的窗口就成為一個D塊，通過這種方法最終得到初始的D塊池。

3）采用LBG算法對于初始的D塊池進行矢量量化，縮減碼書大小。

4）對于每一個R塊，在新形成的D塊池中通過匹配原則（本文采取的是IAM匹配原則）來尋找最優(yōu)匹配快。

5）通過搜索最后形成R塊的分形碼，這種算法的分形碼由4部分構成，D塊池碼字的編號，尺度因子s，亮度偏移因子o和旋轉因子a。

通過上面的算法流程可以看出，由于原始的分形算法要記錄D塊的位置（橫坐標和縱坐標），而本算法中只需要記錄相應碼字的索引號，因此減少了分形碼的存儲和傳輸的壓力，也達到了進一步壓縮的要求。

對于紋理圖像而言，它具有相對于普通的自然圖或者肖像圖更強的全局自相似性，這也從一個側面暗示出紋理圖像形成的D塊池的碼書可以擁有更少的碼字，因此LBGFractal算法對于紋理圖像能得到更好的壓縮效果。

2評價標準的改進

傳統(tǒng)的分形編碼所采用的塊相似評價標準是MSE，MSE的中心思想就是圖像塊相應像素點相減，然后做平方和。由于MSE中涉及到了乘法運算，所以在程序處理的時候會有額外的消耗。

本文中采用另外一種評價標準IAM[12]（ImageActivityMeasure），定義如下：

LAM=1X×Y[∑X-1i=1∑Yj=1Ii，j-Ii+1，j

+∑Xi=1∑Y-1j=1Ii，j-Ii，j+1]（2）

從公式（2）可以看出，IAM主要是用來計算圖像的水平和垂直方向的梯度值，下面來說明塊相似和IAM之間的關系。

對于傳統(tǒng)的分形編碼來說，最后誤差公式為：

E（R，D）=‖R-r-I‖2-s2·‖D-d-I‖2（3）

從公式（3）我們可以看出，如果要使最后的誤差很小，就是要讓R-r-I與s·D-d-I盡量接近，在這里我們做一下改動，如果Ri，j-r-I與s·Di，j-d-I的差值很小，并且Ri+1，j-r-I與s·Di+1，j-d-I的差值也很小，那么從這個角度來看Ri，j-r-I-Ri+1，j-r-I的差值就會與s·Di，j-d-I-s·Di+1，j-d-I很接近，根據a-b

SymbolcB@ a-b，所以從上述結果上可以推斷出Ri，j-Ri+1，j與s·Di，j-Di+1，j（梯度）會大體上接近，也就是說我們找的R塊和D塊之間的匹配性可以用這兩個量之間的比較來得到大體的結果。而如果匹配塊的每一個梯度值都比較接近的話，它們的和也會比較接近，也就說∑Ri，j-Ri+1，j的結果值和∑s·Di，j-Di+1，j的結果值會很接近，現在討論的橫向的梯度，可以用同樣的方法說明縱向的梯度也滿足這個性質，最后得到的∑Ri，j-Ri+1，j+Ri，j-Ri，j+1和∑s·Di，j-Di+1，j+s·Di，j-Di，j+1很接近，也就說明如果兩個塊相匹配的話，IAMR應該和s·IAMD很接近，而從s=〈R-r-I，D-d-I〉/‖D-d-I‖2可以看出，如果兩個塊很接近的話，s的值應該接近于1，也就說最后我們可以認定如果R塊和D塊相似的話，IAMR應該相似于IAMD。

通過上面的證明可以看出，IAM可以作為一個塊的特征值來作比較，我們也可以用塊的IAM值來進行相似度比較，但是這種比較并不是最優(yōu)匹配，只能達到一種次最優(yōu)的匹配。由于我們采用的圖像大小都是2的整數冪，所以IAM的計算中只涉及到加法和右移的計算，算法復雜度也小于MSE。

3解碼收斂速度的改進

分形算法的解碼速度雖然很快，但是仍有改進的余地，比如減少收斂次數。下面的公式改進就可以減少一半的收斂次數。首先將拼貼公式做一下改變，將幾何變換因子和旋轉變換因子都融入進尺度因子s中，這樣最開始的公式變?yōu)椋?/p>

R=s·D+o·I（4）

這里的s=〈R-r-I，D-d-I〉/‖D-d-I‖2，o=r--s·d-，把o里面的后一項s·d-和前面的s·D合并，產生的新的R塊的匹配公式是：

R=s·（D-d-I）+r-I（5）

這樣就把后面的分成兩部分，前一部分代表搜索過程的影響，而后面的是要編碼的R塊的本質屬性，跟搜索的方案是無關的，而且這樣收斂的速度也會加快。

4實驗結果及結論

實驗計算機配置為IntelPentium4D506CPU、1GBDDRRAM，軟件采用QT圖形界面、C++語言編寫，實驗圖像普通肖像圖選擇的是512×512大小的Lena灰度圖，紋理圖像選擇的是512×512大小的Brick圖，512×512大小的Chips圖和512×512大小的Grassland圖。

實驗圖選用的是Lena和Brick。通過圖1可以看出紋理圖像只需要原始碼書大小的三分之一就可以得到和原始碼書相同的解碼效果，而普通的肖像圖則需要更大的碼書才能得到和原始差不多的結果，換言之，就是碼書大小對于普通圖像的影響要強于紋理圖，普通圖像所需要的信息更多，這也是由于紋理圖像具有更強的全局自相似性決定的。

實驗圖選用的是Chips紋理圖。通過結果可以發(fā)現在碼書比較小的時候使用IAM作為評價標準和MSE很類似，因為在D塊池小的情況下出現錯誤匹配的概率也會相應減少。

實驗圖選用的是Grassland紋理圖。通過圖3可以看出原公式需要6次迭代才能達到穩(wěn)定，而新的公式只需要3次就達到穩(wěn)定。

實驗圖選用的是Lena和Brick。通過圖4的率失真曲線可以看出，隨著壓縮倍數的提高，普通肖像圖（lena）的PSNR值下降很明顯，而紋理圖（brick）在壓縮倍數高于3的時候才產生明顯下降，到壓縮倍數15的時候，肖像圖的PSNR值降幅達到5，而紋理圖只有1，這說明在肉眼接受的范圍內，紋理圖比肖像圖具有更好的壓縮性。

通過上述實驗結果可以看出，本文提出的LBGFractal算法可以加快紋理圖像的編碼速度，加大紋理圖像的壓縮比和加快解碼的收斂速度，從而可以得到對于紋理圖像較好的壓縮效果。后面的工作可以將現有方法和其他圖像的特征量，比如盒維數，[13]結合起來，以期待得到更好的結果。

參考文獻：

[1]MandelbrotB.B.，TheFractalGeometryofNature[J]，SanFrancisco：Freeman，1982.

[2]BarnsleyM.F.，FractalEverywhere，AcademicPress[J]，Boston，1988.

[3]BarnsleyM.F.，HurdL.P.，FractalImageCompression[J]，AKPetersLtd.，Boston，1992.

[4]JacquinA.G.，FractalImageCoding：AReview[J]，ProceedingsoftheIEEE，1993.81（10）.

[5]JacquinA.G.，ImageCodingBasedonAFractalTheoryofIteratedContractiveImageTransformations[J]，IEEETrans.ImageProcess，1992.1（1）.

[6]阮秋琦.數字圖像處理學（第二版）.電子工業(yè)出版社，413417.

[7]何傳江，蔣海龍，黃席樾.快速分形圖像編碼的一種特征方法[J].電子學報，2004，（11）.

[8]何傳江，黃娟娟，李高平.基于分數盒維數的快速分形圖像編碼[J]，中國圖象圖形學報，2007，（03）.

[9]ShenFurao，OsamuHasegawa，Afastnosearchfractalimagecodingmethod[J]，SignalProcessing：imagecommunication，2004，（6）.

[10]何傳江，黃席樾.分形圖像編碼技術的算法研究[D]/重慶大學博士學位論文，2004.

[11]FengJ.，Fractionalfractalgeometryforimageprocessing[D].EvanstonIllinois，USA：NorthwesternUniversity，2000.

[12]崔朝輝，劉冀偉，王志良，曲波.分形圖像編碼算法的參數選擇對算法性能的影響[J].智能系統(tǒng)學報，2010，（31）.

[13]于子凡，杜貴君，林宗堅.圖像盒子維數特征計算方法改進[J].測繪科學，2006，（31）.

作者簡介：曲波（1984），男，漢族，山東煙臺人，碩士，工程師，海上平臺中控系統(tǒng)及設備設施維護。