一種混合快速分形圖像編碼算法

(延邊大學(xué) 計算機科學(xué)與技術(shù)系 智能信息處理研究室， 吉林 延吉 133002)

摘要：提出了一種采用兩步篩選的混合快速分形編碼算法。首先將碼本按照矩不變量進行分類，然后尋找給定Range塊在所屬區(qū)間的最好匹配碼塊，對于匹配誤差值大于給定閾值的Range塊再進行基于熵值的二次編碼。與基于矩不變量的算法比較，該方法在峰值信噪比相同的情況下時間效率提高五倍多，與基于信息熵的算法相比，PSNR值提高近一個分貝。

關(guān)鍵詞：分形；圖像壓縮；矩不變量；信息熵

中圖分類號：TP391；TP301.6文獻標(biāo)志碼：A

文章編號：1001-3695(2008)11-3498-03



Hybrid-fast fractal image coding algorithm



WANG Wei，CUI Rong-yi-|

(Laboratory of Intelligent Information Processing， Dept. of Computer Science Technology， Yanbian University， Yanji Jilin 133002， China)

Abstract:This paper proposed a fast fractal image coding algorithm based on two-step selection.Firstly，classified all the domain blocks into several categories based on their moment invariant， and then searched the best-matching domain block for every range block to be encoded in the same category or adjacent categories. Finally，coded secondarily the range blocks which were larger than threshold based on their information entropy. The proposed algorithm achieves the speed-up of over 5 times compared with the moment-feature-based fractal algorithm for the same PSNR. Experimental results show that the proposed hybrid method can improve the speed of fractal coding and the quality of decoded image.

Key words:fractal; image compression; moment invariant; information entropy

0引言

近年來在各種圖像壓縮方法中，分形編碼表現(xiàn)出了巨大的發(fā)展?jié)摿?分形編碼使用一組壓縮映射集合來近似地表示圖像，而不是直接對圖像內(nèi)容進行編碼；傳統(tǒng)方法中變換基是可逆的，而壓縮映射集是不可逆的；解碼圖像失真并不是映射參數(shù)量化造成的，而是在生成壓縮映射過程中產(chǎn)生的^[1]。

分形圖像編碼是使用迭代函數(shù)系統(tǒng)（IFS），即一組壓縮映射來表示圖像，基于圖像的自相似性進行數(shù)據(jù)壓縮。分形圖像壓縮技術(shù)存在一個最主要問題，即編碼時間過長。這一缺點阻礙了它的廣泛應(yīng)用。針對此缺點Fisher等人提出了各自有效的方案，但是隨著編碼時間的減少，相應(yīng)的解碼圖像質(zhì)量也明顯下降^[2~8]。所以分形編碼過程中的一個基本矛盾就是如何在減少編碼時間和保證重建圖像質(zhì)量的問題上保持比較理想的平衡。

針對此問題本文提出了一種采用兩步篩選的混合快速分形編碼算法，既縮短了編碼時間，解碼圖像質(zhì)量也有所提高。實驗結(jié)果顯示，與基于矩不變量的分形算法相比，該方法在峰值信噪比相同的情況下速度提高五倍多，解碼圖像質(zhì)量也有所改善。

1相關(guān)工作

注意到造成分形編碼時間過長的根本原因在于：對于給定的值域塊，為了找到它的最優(yōu)匹配塊，要在包含所有定義域塊D的搜索空間中進行全搜索，而傳統(tǒng)的分形編碼方法采用過搜索的方法，進行很多沒必要的搜索和比較。其實對于一個給定的值域塊，與它較相近的定義域塊僅有幾個至十幾個，而為了這少量的定義域塊，傳統(tǒng)的分形編碼方法卻付出了很大的代價，即在整個定義域塊集中進行搜索。這是影響分形編碼速度的主要原因。目前國內(nèi)外一些學(xué)者已提出不少的加速方法^[9~11]。其中將圖像塊進行分類是一種非常重要而有效的方法。這里，首先分析根據(jù)某些能有效描述圖像塊的灰度分布的紋理特征來對值域塊和定義域塊進行分類的方法；其次分析采用圖像塊元素間的統(tǒng)計特性來提高分形圖像編碼速度的方法。

11幾何矩

從一幅數(shù)字圖像中計算出來的矩集，通常描述了該圖像形狀的全局特征。幾何矩是矩函數(shù)中最簡單的一個，其主要優(yōu)點是：圖像坐標(biāo)變換容易用矩空間中相應(yīng)的變換來表達和分析。圖像不同階的幾何矩表示了圖像亮度分布的不同空間特性^[12]。因而一個幾何矩集可以成為一幅圖像整體形狀的描述子。

給定圖像塊B=(Bij)n×n，其(p，q)階灰度幾何矩定義為

mpq=ni=1

nj=1ipjqBij/M-ni=1ipnj=1jq/n2，p；q=0，1，2，…(1)

其中M=ni=1nj=1Bij為圖像的總亮度。在實際應(yīng)用中，高于三階的圖像矩由于對噪聲較敏感而很少使用，在分形編碼中一般只取前四個特征分量。本文實驗中取p，q=0，1，有

m10=ni=1nj=1

iBij/M-(n+1)/2

m01=ni=1nj=1

jBij/M-(n+1)/2 （2）

文獻[7]已證明式（3）中定義的矩特征θ∈[0，2π]在灰度仿射變換f(x)=s×x+o，x∈R下保持不變：

θ=α tan(mpq/mqp)，mpq≥0，mqp≥0

π+α tan(mpq/mqp)，mpq＜0，mqp≥0

π+α tan(mpq/mqp)，mpq＜0，mqp＜0

2π+α tan(mpq/mqp)，mpq≥0，mqp＜0p≠q

(3)

12信息熵

信息熵是信源的平均不確定性的描述，是從平均意義上來表征的信源總體信息測度。當(dāng)某一數(shù)據(jù)的概率分布已知時，就可根據(jù)概率分布情況來獲取信息熵。圖像塊中各個像素點灰度的熵值能很好地描述圖像像素點灰度的分布特征，表達圖像塊所包含的信息豐富程度，而且圖像的各種拓撲變化均不會影響熵值。信息熵定義為

H(X)=E[log 1/P(ai)]=-qi=1P(ai) log P(ai)

（4）

可以看到信息熵是信源概率空間XP(x)=a1，a2，…，aq

P(a1），P(a2)，…，P(aq)的一種特殊矩函數(shù)，是描述圖像像素點灰度分布特征的灰度矩。這個矩函數(shù)的大小，與信源的符號數(shù)及符號的概率分布有關(guān)。

2改進的混合分形編碼算法

根據(jù)上述內(nèi)容，本文在文獻[4，7]的基礎(chǔ)上設(shè)計了改進的混合編碼算法。首先計算圖像塊的矩特征值，將所有定義域塊的矩特征值按照大小排序，劃分為N份區(qū)間，將所有的定義域塊進行分類。然后判斷每個值域塊所屬區(qū)間，只與其同類別的域塊進行匹配，極大地減少了比較次數(shù)，從而縮短了編碼時間。這里有一個明顯的缺點：對于矩特征值與區(qū)間邊界很接近的值域塊而言，它實際上只能與單邊的定義域塊進行匹配，可能導(dǎo)致匹配精度的降低。本文對這一缺點進行了改進，引進控制參數(shù)k，當(dāng)矩特征值與區(qū)間邊界距離小于k時，合并前后兩個區(qū)間，擴大搜索范圍，從而避免丟失最佳匹配塊。

對于匹配誤差值小于給定閾值的定義域塊進行四叉樹劃分，進行第二步熵值篩選。本文中采用的一階幾何矩是圖形關(guān)于x和y軸的亮度矩，在這兩步編碼中既采用了圖像的灰度矩，又采用了圖像的亮度矩，同時因信息熵的計算量遠遠小于矩特征值的計算量，提高了編碼效率。

混合算法描述如下：

a）將圖像I劃分為值域塊與定義域塊，建立定義域塊庫；

b）定義域塊分類，按上節(jié)所述提取矩特征值，將整個定義域塊庫分成N個區(qū)間；

c）計算值域塊矩特征值，并判斷所屬的區(qū)間，比較其與邊界的距離，如果小于k，則合并相鄰的兩個區(qū)間，找到具有最小誤差的定義域塊；否則在所屬的區(qū)間進行匹配；

d）如果該最小值小于事先給定的閾值，則停止該塊的匹配；否則將該值域塊進行四叉樹劃分，進行基于熵值的二步篩選匹配，返回b）。

上述算法中采用熵值計算公式：H(X)=ni=1log2 ki來代替原有的熵值公式，ki為圖像塊中包含某一灰度值的個數(shù)， 圖像的各種拓撲變化不會影響H(X)的值^[13]。采用此公式能減少計算量，縮短編碼時間。

3實驗結(jié)果與分析

本文選擇256×256 Lena測試圖像為實驗對象，運用MATLAB2006b進行實驗。測試性能參數(shù)是編碼時間（s）和PSNR（dB，峰值信噪比）。

在實驗中，選取R塊大小為8×8。本文算法依賴于兩個控制參數(shù)k和N。實驗結(jié)果顯示，參數(shù)k的取值在(0，1)區(qū)間（圖1），以1/2為周期，呈正弦曲線，所以k的取值應(yīng)在(0，1/2)。本文混合算法中取k=1/3，效果最佳。

定義域塊區(qū)間數(shù)N對編碼時間的影響也較大，編碼時間隨著分類數(shù)N值的變化而連續(xù)地變化。顯然，N值越大，落在同一區(qū)間中的定義域塊就越少，則對一值域塊來說，所需匹配的定義域塊數(shù)就越少，其結(jié)果就是編碼時間縮短（圖2）。但如果N的取值太大，則失去了對定義域塊分類處理的意義。在本文實驗中取N=20后，編碼時間仍逐漸減少，但PSNR值逐漸穩(wěn)定。

表1為本文算法與文獻[4]基于矩特征值編碼和文獻[7]基于熵值編碼結(jié)果的對比。隨著分類數(shù)的增加，編碼時間都有所減少，但混合編碼算法較文獻[4]加快近五倍；與文獻[7]基于熵值編碼比較，解碼質(zhì)量提高了近一個分貝。當(dāng)分類數(shù)為N=20時，混合算法的PSNR值趨于

圖3和4中星號線代表混合算法，其他線分別代表文獻[4，7]算法，可以看出本文算法不論在時間效益還是圖像解碼質(zhì)量上均有明顯改善。

實驗結(jié)果分析如下：

a）相對于文獻[4]矩特征值方法，編碼時間都隨著均勻分類數(shù)N的增大而減少，但矩特征值的計算量大。第二步篩選中，筆者選用熵作為分類標(biāo)準(zhǔn)，信息熵描述了圖像像素點灰度的分布特征，在解碼圖像質(zhì)量沒有下降的基礎(chǔ)上，編碼時間縮短近五倍。

b）相對于文獻[7]熵編碼方法，本文算法的解碼圖像質(zhì)量提高近一個分貝。一步篩選中選用的矩特征值描述了圖像的亮度分布；二步篩選的依據(jù)信息熵描述了圖像的灰度分布，所以取得了更好的解碼質(zhì)量。

4結(jié)束語

本文以圖像塊的一階幾何矩和信息熵為特征將定義域塊進行二步篩選分類，提出了混合快速分形算法，既考慮了圖像的亮度信息，又考慮了圖像灰度分布特征。混合算法與文獻[4]相比，編碼時間明顯縮短；與文獻[7]比較，解碼圖像質(zhì)量也有所改善。分類標(biāo)準(zhǔn)可以采用能夠描述圖像紋理特征的參數(shù)，這在今后的工作中還有待進一步完善。

參考文獻：

［1］

LI Wen-jing，LI Wang-chao.A fast fractal image coding technique[C]//Proc of ICSP’98.Beijing:[s.n.]，1998:775-778.

[2]SUN Yun-da，ZHAO Yao，YUAN Bao-zong.Region-based fractal image coding with freely-shaped partition[J].Chinese Journal of Electronics，2004，13(3):506-511.

[3]王秀妮，姜威，王立村.一種分形圖像編碼的新方法[J].中國工程科學(xué)，2006，8(1):54-57.

[4]譚郁松，周興銘.一種新型圖像分形壓縮的改進算法[J].電子學(xué)報，2003，31(11):1739-1742.

[5]何傳江，蔣海軍，黃席樾.基于平均偏差排序和快速分形圖像編碼[J].中國圖象圖形學(xué)報，2004，9(9):1130-1134.

[6]WOHLBERG B，JAGER G D.A review of the fractal image coding li-terature[J].IEEE Trans on Image Processing，1999，8(12):1716-1729.

[7]劉明，葉正麟，趙瑞.基于混合分類和矩形劃分的快速分形編碼方法[J].計算機應(yīng)用研究，2007，24(7):64-66.

[8]袁源，戴冠中，羅紅.基于分形思想的差值圖像壓縮技術(shù)[J].計算機應(yīng)用研究，2007，24(4):190-191.

[9]SUMAN K M，MURTHY C A，MALAY K K.Technique for fractal image compression using genetic algorithm[J].IEEE Trans on Image Processing，1998，7(4):586-593.

[10]HARTENSTEIN H，RUHL M，SAUPE D.Region-based fractal image compression[J].IEEE Trans on Image Processing，2000，9(7):1171-1184.

[11]何傳江，蔣海軍，黃席樾.快速分形圖像編碼的一種特征方法[J].電子學(xué)報，2004，32(11):1864-1867.

[12]陳作平，葉正麟，高雪峰.一種基于矩不變量的快速分形編碼方法[J].計算機工程與應(yīng)用，2004，40(33):62-66.

[13]王秀妮， 姜威，王利村.基于統(tǒng)計特性的分形圖像壓縮[J].計算機工程與應(yīng)用，2005，41(26):75-77.