曲波 高強(qiáng) 李大華 于曉

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

關(guān)鍵詞：紋理圖像；分型算法；矢量量化；IAM

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

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

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

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

1LBGFractal算法

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

1.1對(duì)圖像進(jìn)行預(yù)處理分割

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

1.2建立搜索空間

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

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

在搜索空間內(nèi)，對(duì)每一值域塊Ri，通過最小均方誤差（MSE）原則尋找誤差最小的匹配塊Di，使Di經(jīng)適當(dāng)?shù)姆律渥儞Qωi來逼近Ri，即DiωiRi，使之滿足

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

=minDI2‖RisiAGDi+oi‖2（1）

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

1.4生成編碼

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

1.5迭代解碼

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

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

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

1）將原始大小N×N的圖像（本實(shí)驗(yàn)中采用的是512×512大小）分割成R×R大小的R塊（本實(shí)驗(yàn)中采用的是4×4大?。?，構(gòu)成初始編碼塊的集合。

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

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

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

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

通過上面的算法流程可以看出，由于原始的分形算法要記錄D塊的位置（橫坐標(biāo)和縱坐標(biāo)），而本算法中只需要記錄相應(yīng)碼字的索引號(hào)，因此減少了分形碼的存儲(chǔ)和傳輸?shù)膲毫?，也達(dá)到了進(jìn)一步壓縮的要求。

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

2評(píng)價(jià)標(biāo)準(zhǔn)的改進(jìn)

傳統(tǒng)的分形編碼所采用的塊相似評(píng)價(jià)標(biāo)準(zhǔn)是MSE，MSE的中心思想就是圖像塊相應(yīng)像素點(diǎn)相減，然后做平方和。由于MSE中涉及到了乘法運(yùn)算，所以在程序處理的時(shí)候會(huì)有額外的消耗。

本文中采用另外一種評(píng)價(jià)標(biāo)準(zhǔn)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主要是用來計(jì)算圖像的水平和垂直方向的梯度值，下面來說明塊相似和IAM之間的關(guān)系。

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

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

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

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

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

3解碼收斂速度的改進(jìn)

分形算法的解碼速度雖然很快，但是仍有改進(jìn)的余地，比如減少收斂次數(shù)。下面的公式改進(jìn)就可以減少一半的收斂次數(shù)。首先將拼貼公式做一下改變，將幾何變換因子和旋轉(zhuǎn)變換因子都融入進(jìn)尺度因子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里面的后一項(xiàng)s·d-和前面的s·D合并，產(chǎn)生的新的R塊的匹配公式是：

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

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

4實(shí)驗(yàn)結(jié)果及結(jié)論

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

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

實(shí)驗(yàn)圖選用的是Chips紋理圖。通過結(jié)果可以發(fā)現(xiàn)在碼書比較小的時(shí)候使用IAM作為評(píng)價(jià)標(biāo)準(zhǔn)和MSE很類似，因?yàn)樵贒塊池小的情況下出現(xiàn)錯(cuò)誤匹配的概率也會(huì)相應(yīng)減少。

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

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

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

參考文獻(xiàn)：

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

[2]BarnsleyM.F.，F(xiàn)ractalEverywhere，AcademicPress[J]，Boston，1988.

[3]BarnsleyM.F.，HurdL.P.，F(xiàn)ractalImageCompression[J]，AKPetersLtd.，Boston，1992.

[4]JacquinA.G.，F(xiàn)ractalImageCoding：AReview[J]，ProceedingsoftheIEEE，1993.81（10）.

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

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

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

[8]何傳江，黃娟娟，李高平.基于分?jǐn)?shù)盒維數(shù)的快速分形圖像編碼[J]，中國圖象圖形學(xué)報(bào)，2007，（03）.

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

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

[11]FengJ.，F(xiàn)ractionalfractalgeometryforimageprocessing[D].EvanstonIllinois，USA：NorthwesternUniversity，2000.

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

[13]于子凡，杜貴君，林宗堅(jiān).圖像盒子維數(shù)特征計(jì)算方法改進(jìn)[J].測繪科學(xué)，2006，（31）.

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