改進轉動慣量特征的快速分形圖像編碼算法

李高平，楊軍，陳毅紅

西南民族大學計算機科學與技術學院，成都 610041

改進轉動慣量特征的快速分形圖像編碼算法

李高平，楊軍，陳毅紅

西南民族大學計算機科學與技術學院，成都 610041

1 引言

1990年Jacquin首次提出基于圖像中的局部自相似來消除冗余信息的分塊迭代函數系統（PIFS）編碼算法[1]，用壓縮仿射變換的量化參數來表達圖像，具有壓縮比大、解碼快、分辨率無關等特性。但是這種方法因其編碼過程需要全搜索而耗費大量時間[2]，限制了它在圖像壓縮領域的運用。

多年來，研究者們針對編碼過程耗時問題已提出最有創新和前途的特征向量法來加快編碼過程。但該方法存在高維特征向量需要增加額外存儲，且維數越高、性能越差的問題[3-5]。近幾年也提出許多降維的替代特征方法[6-10]，這些方法多從圖像子塊的統計數字特征考慮，沒有考慮圖像子塊上各像素點灰度值的空間分布情況，據此定義的圖像子塊特征不能全面反映其所含信息。文獻[11]借用力學中的“轉動慣量”概念來刻畫圖像子塊的特征，定義了綜合考慮圖像子塊上各像素點灰度值大小和空間分布狀況的轉動慣量，提出一種基于轉動慣量的快速算法，該算法的不足之處在于，它依據的假設（即兩個等尺寸的子塊只有轉動慣量值接近時才有可能組成匹配對）僅僅是建立在統計意義而非確定意義上。本文繼續研究這個算法，改進了文獻[11]中圖像子塊的轉動慣量定義，重新定義了轉動慣量特征，并從理論上證明了它與匹配誤差間的關系不等式。根據這個不等式，在編碼階段，一個range塊的最佳匹配domain塊只在與其轉動慣量特征值相接近的domain塊里面尋找，終止條件由預先設置的誤差閾值來控制。在本文提出的快速算法中，也融入了文獻[7]中提出的兩個措施：一是通過排除碼書Ω中的小標準差domain塊以縮減碼書容量；二是采用非搜索的方式對小方差range塊編碼。三幅測試圖像的仿真實驗表明，本文提出的改進轉動慣量特征算法是在不降低解碼圖像質量的情況下，實現加快編碼26倍左右，這改進了原轉動慣量算法[11]的結果（在PSNR下降約1.7 dB的前提下，加快編碼19倍左右）。同時，本文算法也優于全搜索分形編碼算法和三均值特征分形編碼算法[10]（簡稱三均值特征算法）。

2 全搜索分形編碼算法和三均值特征算法

便于表述，將n×n大小圖像子塊上各像素點的灰度值向量化為線性空間RN(N=n×n)中的向量。R=(r1,…,rk,…,rN)、D=(d1,…,dk,…,dN)分別表示range塊（簡稱R塊）、domain塊（簡稱D塊）像素點灰度值向量化的向量，用表示X∈RN的均值，用＜·, ·＞、||·||分別表示向量內積和2-范數，用(RN,E)代表N=n×n灰度圖像空間（R是實數集，E為均方根失真度量函數）。

2.1 全搜索分形編碼算法

在分形編碼中，圖像首先被分割成互不重疊大小為n×n的R塊和允許重疊大小為2n×2n的D塊。然后，將每個D塊通過4-鄰域像素值平均來收縮為n×n的子塊與R塊大小匹配，所有收縮后的D塊經過8個等距變換的全體D塊就構成碼書Ω。

編碼階段，對每一個R塊，按照全搜索方式在碼書Ω中尋找其最佳匹配D塊和自仿射變換w，使得w(D)與R的均方誤差達到最小。為了尋求R塊的最佳匹配塊，需要求解下面的極小化問題：

其中，m表示R塊的最佳匹配塊序號，I∈Rn×n是所有元素均為1的常值塊。

顯然，直接求解問題式（1）是十分困難的，為了減少計算復雜性，常采用的實用方法是解內層約束極小化時先忽略式（1）中約束|s|＜1，后對不滿足約束的對比度因子作截斷處理來補償。因此，問題式（1）的內層約束極小化轉化為下述問題來求解：

把問題式（1）的求解轉化為式（2）和式（5）這種次優解法后，得到的R塊分形碼為四元組(m,s?i,o?i,t)。其中s?i,o?i是si,oi的量化值，t是等距變換序號。原始圖像的分形碼由全體R塊的分形碼組成，它描述了一個使圖像近似不變的壓縮變換。

解碼用分形碼描述的壓縮變換迭代作用于任何初始圖像來生成。

2.2 三均值特征算法

在定義圖像子塊特征時，通過對圖像子塊去均值后，再進行單位化來消除對比度因子的影響[8]。于是，可將圖像子塊的規范子塊定義如下：

編碼階段，一個待編碼R塊的最佳匹配塊搜索范圍僅在初始匹配塊（與R塊的三均值特征值相近的D塊）的鄰域內，搜索鄰域的大小由預先設置的誤差閾值來確定，它有效降低了算法的復雜度。

3 改進轉動慣量特征的快速編碼算法

3.1 理論基礎

全搜索分形編碼算法的編碼過程所耗費時間，主要取決于碼書Ω容量的大小。為了減少編碼過程時間，必須采取一定的措施來縮減搜索空間。下面通過定義圖像子塊的特征，將匹配搜索由全局搜索轉變為鄰域搜索。

借用力學中的“轉動慣量”概念，文獻[11]在定義圖像子塊的轉動慣量時，選用圖像子塊的重心作為轉動中心，各圖像子塊的轉動中心位置會因其上各像素點灰度值分布不同而變化。此外，將|x?i,j|視為“質量”，沒有考慮圖像子塊上像素點灰度值規范化出現的正負對轉動慣量的不同影響。

這樣定義的圖像子塊的轉動慣量特征，其轉動中心固定，且考慮了各像素點灰度值規范化出現的正負對轉動慣量的不同影響。下面的定理給出了匹配誤差與改進轉動慣量特征間的關系，它是本文算法的理論基礎。

定理若圖像子塊大小為n×n，其上的像素點灰度值向量化為R,D∈Rn×n，則有下面的不等式：

定理證畢。

3.2 快速編碼算法方案

編碼過程耗時的多少與待編碼的R塊數量、碼書Ω的容量大小和搜索方式緊密相關。

首先，確定待編碼的R塊數量。由式（4）可得，E(R,D)≤nσR，它表明σR足夠小的R塊，任意D∈RN都可以作為其匹配塊，這些R塊不需要搜索編碼，直接賦予分形碼。設置分類閾值τ＞0，若R塊的σR≤τ，就認為此類R塊為非搜索編碼塊（簡稱平滑塊），否則就認為是搜索編碼塊（簡稱非平滑塊），因此，待編碼R塊數量就是非平滑R塊的數量。

其次，確定縮減碼書Ω的容量。由匹配誤差式（4）可推出，，因此，可以預先排除碼書Ω中的小標準差D塊。設定閾值η＞τ，將原碼書Ω縮減為容許碼書Ωη，即

最后，確定待編碼的R塊(σR＞τ)在容許碼書Ωη的搜索方式。由本文證明的式（9）可知，與待編碼R塊匹配D塊的匹配誤差為：

這說明：如果D和R改進轉動慣量特征值相差較大，那么匹配誤差E(R,D)也較大，從而D不能匹配R；反之，如果D匹配R，即E(R,D)最小，那么由式（12）可知S(D)應該與S(R)非常接近。它表明R的最佳匹配D在改進轉動慣量特征意義下一定是與R最接近Dinit∈Ωη（Dinit稱為初始匹配塊）的近鄰。所以，在設計搜索方式時，首先將容許碼書中的D塊按其改進轉動慣量特征值S(D)的大小進行升序排列，即滿足S(Di)≤S(Di+1)，并使用二分法在升序容許碼本Ωη中搜索與S(R)相差最小的初始匹配塊Dinit={D∈Ωη|min|S(R)-S(D)|}，然后，搜索過程在Dinit的左右方向進行，直至滿足預先條件E(R,D)≤δ（δ為誤差閾值）為止。儲存搜索過程中匹配誤差E(R,D)≤δ對應的D塊的序號m、量化參數,、等距變換序號t，即得出搜索編碼R塊的分形碼為(m,,,t)。

4 仿真實驗結果

仿真實驗的測試圖像為Lena、Peppers和Boat（512× 512，8 bit量化），計算在運行Windows XP的AMD Athlon（3.01 GHz CPU/2 GB內存）PC上進行，程序用C++編寫。

4.1 改進轉動慣量特征的有效性驗證

本文通過重新定義的圖像子塊的轉動慣量特征，把待編碼R塊的匹配搜索空間由全局搜索變為局部搜索，在初始匹配塊（與R塊的改進轉動慣量特征值相近的D塊）的鄰域內搜索。問題是全搜索找到的最佳匹配塊（即全局匹配塊）在賦序碼書中與其初始匹配塊的遠近是不同的，若鄰域半徑取得小，那么局部搜索范圍內找到的局部匹配塊就有可能不是全局匹配塊，會導致全局匹配塊被局部匹配塊取代，使解碼圖像質量降低。下面通過仿真實驗測出全局匹配塊落在初始匹配塊鄰域U(Dinit,k)內的情況。

測試圖像采用方塊分割方案，R塊、D塊大小分別取為4×4、8×8，生成碼書的步長取為8，此時，待編碼R塊的數量為16 384。在改進轉動慣量特征意義下，三幅測試圖像的編碼R塊的全局匹配塊落入鄰域U(Dinit,k)內的數量列于表1，表中標識“M-N”表示k的取值區間為(|Ω|×M%,|Ω|×N%]，其中|Ω|為碼本容量。

表1 全局匹配塊落入鄰域U(Dinit,k)內的R塊數量（改進轉動慣量特征）

從表1可以看出，當鄰域半徑k≤|Ω|×10%時，三幅測試圖像的編碼R塊的全局匹配塊落在鄰域內的比例分別為35.6%、33.5%、37.2%；當鄰域半徑k≤|Ω|×30%時，三幅測試圖像的編碼R塊的全局匹配塊落在鄰域內的比例分別為73.5%、70.4%、75.7%；當鄰域半徑k≤|Ω|×50%時，三幅測試圖像的編碼R塊的全局匹配塊落在鄰域內的比例分別為89.3%、87.8%、91.7%；只有極少數的R塊的全局匹配塊，幾乎需要全搜索才能找到，其比例分別為0.7%、0.8%、0.3%。這些數據充分表明，絕大多數的待編碼R塊的全局匹配塊就在其初始匹配塊附近，不需要進行全搜索就能找到，驗證了鄰域搜索是可行的。

在原轉動慣量特征[11]、三均值特征[10]意義下，用同樣方法得到三幅測試圖像編碼R塊的全局匹配塊落入鄰域U(Dinit,k)內的數量列于表2。

將表2與表1中的數據進行對比不難發現，在鄰域半徑k相同的情況下，三幅測試圖像的編碼R塊的全局匹配塊落在鄰域內的數量比較結果為：改進轉動慣量特征最多，其次是三均值特征，最后才是原轉動慣量特征。表明改進轉動慣量特征比三均值特征和原轉動慣量特征更能準確全面刻畫圖像子塊的信息。

4.2 改進轉動慣量特征快速算法的有效性驗證

在上面設計的改進轉動慣量特征快速編碼方案中，首先應選取R塊的分類閾值τ和容許碼書閾值η，根據文獻[7]的研究結果，可取τ=4，η=20。其次，通過實驗確定誤差閾值δ，顯然，編碼過程時間會隨著δ增大而減少，其解碼圖像質量也會相應地降低。

表2 全局匹配塊落入鄰域U(Dinit,k)內的R塊數量（轉動慣量特征[11]、三均值特征[10]）1）

圖1顯示的是三幅圖像的解碼圖像質量（以PSNR度量）在不同誤差閾值δ下的變化情況。當δ≤10時，解碼圖像質量下降比較緩慢，當δ＞10時，解碼圖像質量下降比較快，綜合考慮編碼時間和解碼圖像質量兩個因素，取δ=10比較合適。

圖1 解碼圖像質量隨誤差閾值變化情況

為了驗證本文提出的快速算法的有效性，選編碼時間（s）和峰值信噪比PSNR（dB）為測試性能參數。本文算法(τ=4,η=20,δ=10)與全搜索算法的對比實驗結果列于表3。為比較結果公正，原轉動慣量算法[11]也融入了文獻[7]中提出的兩個措施，它和本文的對比結果見圖2。

表3 本文算法與全搜索分形算法對比結果

從表3可知，對選用的三幅標準測試圖像，本文提出的算法與全搜索算法相比，從平均意義角度看，在基本保持解碼圖像質量不降低的情況下，編碼速度加快達26倍左右。

圖2 本文算法與轉動慣量算法的編碼性能對比

5 結論

從綜合考慮圖像子塊上各像素點灰度值及其空間分布的角度，本文借用力學中的“轉動慣量”概念，重新定義了圖像子塊的轉動慣量特征，并從理論上證明了它與均方根誤差間的關系不等式，以此為基礎，把耗時的R塊與碼書D塊的匹配搜索問題轉化為轉動慣量特征意義下初始匹配塊Dinit的鄰域搜索問題，有效降低了算法的復雜度。通過對三幅測試圖像進行仿真實驗，驗證了絕大多數的待編碼R塊，在其初始匹配塊鄰域內搜索得到的局部匹配塊就是全局匹配塊，表明了鄰域搜索是可行的。與轉動慣量特征和三均值特征相比，改進轉動慣量特征更能準確全面刻畫圖像子塊的信息。本文基于圖像子塊的改進轉動慣量特征提出的快速分形編碼算法，在解碼圖像質量基本相同的情況下，平均加快編碼過程的速度26倍左右。該快速算法不僅有理論基礎，而且也得到了仿真實驗的驗證，為加快分形圖像編碼過程提供了一個有效的方法。

[1]Jacquin A E.Image coding based on a fractal theory of iterated contractive image transformations[J].IEEE Transactions on Image Processing，1992，1（1）：18-30.

[2]Fisher Y.Fractal image compression：theory and application[M]. New York：Springer-Verlag，1995.

[3]Saupe D.Accelerating fractal image compression by multi-dimensional nearest neighbour search[C]//Proc Data Compression Conf，1995：222-231.

[4]Wohlberg B，De Jager G.A review of the fractal image coding literature[J].IEEE Trans on Image Process，1999，12：1716-1729.

[5]Selvi S S，Makur A.Variable dimension range and domain block-based fractal image coding[J].IEEE Transactions on Circuits and Systems for Video Technology，2003，4：343-347.

[6]He C，Yang S X，Xu X.Fast fractal image compression based on one-norm of normalised block[J].Electron Lett，2004，40（17）：1052-1053.

[7]何傳江，黃席樾.基于圖像塊叉跡的快速分形圖像編碼算法[J].計算機學報，2005，28（10）：1753-1759.

[8]何傳江，申小娜.改進分形圖像編碼的叉跡算法[J].計算機學報，2007，30（12）：2156-2163.

[9]李高平，向慧芬，趙正武.四分位數特征的快速分形圖像編碼算法[J].計算機工程與應用，2011，47（22）：145-148.

[10]李高平.三均值特征的快速分形圖像編碼算法[J].中國圖象圖形學報，2011，16（1）：1-7.

[11]孫后山，劉曉東，黨晶濤，等.基于轉動慣量的快速分形圖像編碼算法[J].微電子學與計算機，2009，26（5）：92-95.

LI Gaoping,YANG Jun,CHEN Yihong

College of Computer Science&Technology,Southwest University for Nationalities,Chengdu 610041,China

Fractal image encoding with full search typically requires a very long runtime,which is essentially spent on searching for the best-matched block to an input range block in a large domain pool.This paper thus proposes an effective method to improve the drawback,which is mainly based on certified inequality linking the root-mean-square and Improved Moment of Inertia（IMI）feature of normalized block.During the search process,the IMI feature is utilized to confine efficiently the search space to the vicinity of the domain block having the closest IMI feature to the input range block being encoded,aiming at reducing the searching scope of similarity matching to accelerate the encoding process.Besides,a beforehand error threshold is used to determine the size of search neighbourhood.Simulation results of three standard test images show that the proposed scheme not only reduces the searching scope of best-matched to averagely obtain the speedup of 26 times or so by error threshold set 10,but also can obtain the same quality of the decoded images as the baseline algorithm with full search.Moreover,it is better than the moment of inertia algorithm and the three-mean feature algorithm.

image compression;fractal;fractal image coding;improved moment of inertia feature

全搜索分形圖像編碼過程特別耗時的原因在于，每個range塊都需要在一個很大的domain塊池里尋找最佳匹配domain塊。為了改進這個缺點，重新定義了圖像規范塊的轉動慣量特征，證明了它與匹配均方根誤差間的關系不等式，據此提出了一個限制搜索范圍來加快編碼過程的算法：一個待編碼range塊的最佳匹配塊搜索范圍僅在與它的轉動慣量特征值相近的domain塊的鄰域內搜索，鄰域半徑的大小由預先設置的誤差閾值來確定。三幅圖像的仿真結果表明，它確實能夠在不降低解碼圖像質量的情況下，通過減少搜索范圍達到了平均加快全搜索分形編碼算法的編碼速度26倍左右（誤差閾值為10），且也優于轉動慣量算法和三均值特征算法。

圖像壓縮；分形；分形圖像編碼；改進轉動慣量特征

A

TN919.81

10.3778/j.issn.1002-8331.1306-0259

LI Gaoping,YANG Jun,CHEN Yihong.Fast fractal image encoding algorithm based on improved moment of inertia feature. Computer Engineering and Applications,2013,49（24）：144-148.

國家民族事物委員會科研項目（No.12XN05）；西南民族大學自然科學項目（No.2012NYT001）。

李高平（1966—），男，教授，研究方向為分形理論及其在圖像處理中的應用；楊軍（1963—），男，博士，教授，研究方向為信息安全、應用密碼學和組密鑰管理；陳毅紅（1972—），男，博士，實驗師，研究方向為嵌入式系統研究、物聯網、RFID。

2013-06-24

2013-08-09

1002-8331（2013）24-0144-05

CNKI出版日期：2013-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20131011.1653.006.html