改進(jìn)轉(zhuǎn)動慣量特征的快速分形圖像編碼算法

李高平，楊軍，陳毅紅

西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，成都 610041

改進(jìn)轉(zhuǎn)動慣量特征的快速分形圖像編碼算法

李高平，楊軍，陳毅紅

西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，成都 610041

1 引言

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

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

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

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

2.1 全搜索分形編碼算法

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

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

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

顯然，直接求解問題式（1）是十分困難的，為了減少計(jì)算復(fù)雜性，常采用的實(shí)用方法是解內(nèi)層約束極小化時先忽略式（1）中約束|s|＜1，后對不滿足約束的對比度因子作截?cái)嗵幚韥硌a(bǔ)償。因此，問題式（1）的內(nèi)層約束極小化轉(zhuǎn)化為下述問題來求解：

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

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

2.2 三均值特征算法

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

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

3 改進(jìn)轉(zhuǎn)動慣量特征的快速編碼算法

3.1 理論基礎(chǔ)

全搜索分形編碼算法的編碼過程所耗費(fèi)時間，主要取決于碼書Ω容量的大小。為了減少編碼過程時間，必須采取一定的措施來縮減搜索空間。下面通過定義圖像子塊的特征，將匹配搜索由全局搜索轉(zhuǎn)變?yōu)猷徲蛩阉鳌?/p>

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

這樣定義的圖像子塊的轉(zhuǎn)動慣量特征，其轉(zhuǎn)動中心固定，且考慮了各像素點(diǎn)灰度值規(guī)范化出現(xiàn)的正負(fù)對轉(zhuǎn)動慣量的不同影響。下面的定理給出了匹配誤差與改進(jìn)轉(zhuǎn)動慣量特征間的關(guān)系，它是本文算法的理論基礎(chǔ)。

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

定理證畢。

3.2 快速編碼算法方案

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

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

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

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

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

4 仿真實(shí)驗(yàn)結(jié)果

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

4.1 改進(jìn)轉(zhuǎn)動慣量特征的有效性驗(yàn)證

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

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

表1 全局匹配塊落入鄰域U(Dinit,k)內(nèi)的R塊數(shù)量（改進(jìn)轉(zhuǎn)動慣量特征）

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

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

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

4.2 改進(jìn)轉(zhuǎn)動慣量特征快速算法的有效性驗(yàn)證

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

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

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

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

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

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

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

圖2 本文算法與轉(zhuǎn)動慣量算法的編碼性能對比

5 結(jié)論

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

[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].計(jì)算機(jī)學(xué)報(bào)，2005，28（10）：1753-1759.

[8]何傳江，申小娜.改進(jìn)分形圖像編碼的叉跡算法[J].計(jì)算機(jī)學(xué)報(bào)，2007，30（12）：2156-2163.

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

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

[11]孫后山，劉曉東，黨晶濤，等.基于轉(zhuǎn)動慣量的快速分形圖像編碼算法[J].微電子學(xué)與計(jì)算機(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塊。為了改進(jìn)這個缺點(diǎn)，重新定義了圖像規(guī)范塊的轉(zhuǎn)動慣量特征，證明了它與匹配均方根誤差間的關(guān)系不等式，據(jù)此提出了一個限制搜索范圍來加快編碼過程的算法：一個待編碼range塊的最佳匹配塊搜索范圍僅在與它的轉(zhuǎn)動慣量特征值相近的domain塊的鄰域內(nèi)搜索，鄰域半徑的大小由預(yù)先設(shè)置的誤差閾值來確定。三幅圖像的仿真結(jié)果表明，它確實(shí)能夠在不降低解碼圖像質(zhì)量的情況下，通過減少搜索范圍達(dá)到了平均加快全搜索分形編碼算法的編碼速度26倍左右（誤差閾值為10），且也優(yōu)于轉(zhuǎn)動慣量算法和三均值特征算法。

圖像壓縮；分形；分形圖像編碼；改進(jìn)轉(zhuǎn)動慣量特征

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.

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

李高平（1966—），男，教授，研究方向?yàn)榉中卫碚摷捌湓趫D像處理中的應(yīng)用；楊軍（1963—），男，博士，教授，研究方向?yàn)樾畔踩?yīng)用密碼學(xué)和組密鑰管理；陳毅紅（1972—），男，博士，實(shí)驗(yàn)師，研究方向?yàn)榍度胧较到y(tǒng)研究、物聯(lián)網(wǎng)、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