基于歐氏比的快速分形編碼算法

張愛(ài)華，何雨虹，張 璟

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210046)

基于歐氏比的快速分形編碼算法

張愛(ài)華，何雨虹，張 璟

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210046)

分形編解碼的時(shí)間過(guò)長(zhǎng)，主要是因?yàn)榫幋a過(guò)程中的搜索碼本塊的最佳匹配塊占據(jù)了大量時(shí)間。如果能用某種方式，盡量縮短搜索碼本塊最佳匹配塊的時(shí)間，那么分形編解碼的時(shí)間就能大大縮短。文中提出了一種基于歐氏比的分形編碼算法并給出了可行性分析。該算法將全局搜索最佳匹配塊的算法轉(zhuǎn)變?yōu)橄鄬?duì)意義下的鄰域搜索最佳匹配塊的算法，即只搜索與R塊的歐氏比相差較近的碼本塊，從而大大減少了搜索最佳匹配塊所占用的時(shí)間,進(jìn)而縮短了分形編解碼的時(shí)間。用MATLAB對(duì)文中算法進(jìn)行代碼仿真，仿真效果用主觀上觀察圖像的清晰度、圖像編解碼前后的信噪比和編解碼的時(shí)間來(lái)評(píng)價(jià)。實(shí)驗(yàn)結(jié)果表明：該算法在盡量保證圖像質(zhì)量的前提下，使得分形編解碼的時(shí)間大大縮短。

分形；分形圖像編碼；矢量叉乘向量；歐氏比

0 引 言

隨著科學(xué)技術(shù)的發(fā)展，圖像壓縮引起了人們廣泛的興趣。同時(shí)，“分形”概念為復(fù)雜的自然景物的描述提供了一種有力的數(shù)學(xué)工具，之后，分形幾何理論被應(yīng)用在圖像編碼[1]，進(jìn)而產(chǎn)生了比較新穎的圖像編碼方法—分形圖像編碼算法[2-4]。而分形圖像編碼的高壓縮比、多分辨率以及較好的重構(gòu)圖像質(zhì)量等特點(diǎn)，使得它的編碼算法研究十分活躍。目前，分形圖像編碼研究還不是很成熟[5-6]，很多問(wèn)題有待進(jìn)一步探索。而這些研究的目的主要是為了改善以下幾個(gè)方面：壓縮比、編解碼速度、重構(gòu)圖像質(zhì)量。而固有的編碼耗時(shí)限制了分形編碼的發(fā)展。

近年來(lái)，許多專(zhuān)家和學(xué)者在分形圖像編解碼時(shí)間和重構(gòu)圖像質(zhì)量等方面做了大量的研究[7-11]，也獲得了一些成果，但是在保證一定圖像質(zhì)量的前提下縮短編解碼時(shí)間仍然是研究的一個(gè)重要問(wèn)題。而分形圖像的編碼中，從海量碼本中搜索每個(gè)R塊的最佳匹配碼塊占去了分形圖像編碼的大部分時(shí)間。目前在匹配方面，主要分為對(duì)圖像子塊進(jìn)行分類(lèi)和建立子塊特征，前者將全局搜索轉(zhuǎn)化為類(lèi)內(nèi)搜索來(lái)縮短編解碼時(shí)間，后者是在子塊特征的基礎(chǔ)上將全局搜索轉(zhuǎn)化為局部搜索來(lái)縮短編解碼時(shí)間。而這種將全局搜索轉(zhuǎn)化為局部搜索(類(lèi)內(nèi)搜索)其實(shí)有時(shí)并不能準(zhǔn)確地、全面地反映子塊與父塊間的適配程度，但是文中算法研究發(fā)現(xiàn)，在一定的誤差范圍內(nèi)，局部搜索是可以代替全局搜索的。如果能按照這種方式將不太可能匹配的R塊排除，那么編碼時(shí)間將會(huì)大大減小。這是大多數(shù)快速分形圖像編碼算法的基本思想。

基于這種想法，文中定義了圖像子塊的一種新特征—?dú)W氏比，將“MSE意義上的最佳匹配”轉(zhuǎn)化到“圖像歐氏比特征空間的領(lǐng)域搜索”，大大減少搜索空間，加快編碼速度[12-13]。此外，分析并給出了該特征與匹配誤差之間的關(guān)系，基于這一關(guān)系提出了一種快速分形圖像編碼算法。

1 基本分形方法簡(jiǎn)介

1.1 圖像分割

假定待編碼圖像F是N×N灰度圖像，像素灰度值按照8比特量化(即把灰度值分為256級(jí))。在應(yīng)用中，N一般為2的方冪，例如256，512等。采用固定方塊分割的方法，把圖像I分割成一系列大小固定的B×B像素子塊Ri(它們互不重疊且能夠覆蓋整幅圖像)，也就是說(shuō)：

在分形編碼中，這種子塊稱(chēng)為Range塊(以下簡(jiǎn)稱(chēng)R塊)，應(yīng)用中尺寸一般為4×4，8×8，16×16等，文中取R塊為8×8。在由R塊組成的子塊中，通常按行序逐塊編碼，即把R塊排列成：

1.2 碼本構(gòu)成

圖1 收縮D塊的構(gòu)造

這種收縮子塊的全體就構(gòu)成“虛擬碼本”，記這個(gè)碼本為Ω，即

(1)恒等變換：(t0D)i,j=Di,j;

(2)關(guān)于鉛垂中軸(j=B-1/2)對(duì)稱(chēng)的反射：(t1D)i,j=Di,B-1-j;

(3)關(guān)于水平中軸(i=B-1/2)對(duì)稱(chēng)的反射：(t1D)i,j=DB-1-i,j;

(4)關(guān)于主對(duì)角線(i=j)對(duì)稱(chēng)的反射：(t3D)i,j=Dj,i;

(5)關(guān)于次主對(duì)角線(i+j=B-1)對(duì)稱(chēng)的反射：(t4D)i,j=DB-1-j,B-1-i;

(6)關(guān)于D塊的中心逆時(shí)針旋轉(zhuǎn)90°：(t5D)i,j=Dj,B-1-i;

(7)關(guān)于D塊的中心逆時(shí)針旋轉(zhuǎn)180°：(t6D)i,j=DB-1-i,B-1-j;

(8)關(guān)于D塊的中心逆時(shí)針旋轉(zhuǎn)270°：(t7D)i,j=DB-1-i,j。

1.3 編碼匹配階段

E(R,D)=

然后記下D塊位置，變換的類(lèi)型以及s和o的值。

1.4 解碼階段

分形解碼較為簡(jiǎn)單，重構(gòu)的圖像是分形碼描述的壓縮變換T的近似的不動(dòng)點(diǎn)圖像，可以按照分形碼提供的分割信息對(duì)任何初始圖像進(jìn)行迭代來(lái)生成。不動(dòng)點(diǎn)定理可保證迭代的收斂性，而拼貼定理則可保證壓縮變換T的不動(dòng)點(diǎn)就是原圖像的近似[15-16]。

2 算法理論依據(jù)

首先給出一個(gè)比較簡(jiǎn)單的結(jié)果：給定R,D∈Rn×n，以及最小值的問(wèn)題：

顯然,‖R-sD-oI‖2是關(guān)于s和o的二次多項(xiàng)式，分別對(duì)s和o求偏導(dǎo)，并令導(dǎo)數(shù)值為零，解關(guān)于s和o的一個(gè)線性方程組，解其得：

在分形編碼中，每個(gè)R塊是由它的最佳匹配塊D∈Ω的灰度變換來(lái)近似得到的，即

R≈s·D+o·I

下面定義了圖像子塊的一種新的特征，給出該特征與匹配誤差之間的關(guān)系。然后，基于這種關(guān)系提出一種快速分形圖像編碼算法[17-19]。

將每一圖像子塊R與D均分為四個(gè)部分(見(jiàn)圖2)，求出各部分的灰度均值，根據(jù)它們的空間位置，令其對(duì)角線兩元素之差組成矢量叉乘向量：

由上述方法分別求得子塊R與父塊D的子塊矢量叉乘向量r,d。

圖2 D塊(左)和 R塊(右)

定義：設(shè)子塊R=(r)，記

特征C(R)是通過(guò)子塊叉乘向量的歐氏距離定義的，故把它稱(chēng)為歐氏距離比率特征，簡(jiǎn)稱(chēng)為歐氏比。

下面給出特征C(R)的可行性分析。

R≈s·D+o·I

Rin=s·Djn+o·I(n=1,2,3,4)

r=s·d

ri=s·di

顯然有

因此得

C(R)≈C(D)

3 算法分析與實(shí)現(xiàn)

3.1 算法分析

顯然，這種做法不僅提高了重構(gòu)圖像質(zhì)量，還能通過(guò)減少碼塊的數(shù)目來(lái)加快編碼的速度。

為了降低鄰域搜索較小時(shí)，局部的搜索匹配子塊代替全局的匹配塊而引起圖像質(zhì)量下降這一缺點(diǎn)，應(yīng)注意以下幾點(diǎn)[20]：

(1)設(shè)定閾值t，這一點(diǎn)可以保證在與R塊歐氏比相差最小的Dm塊的t鄰域內(nèi)尋找最佳匹配的碼塊D。

(2)設(shè)定一個(gè)誤差閾值H，來(lái)保證這種誤差不至太大，從而使得解碼圖像質(zhì)量得以保證。

3.2 算法的實(shí)現(xiàn)

基于3.1的分析，算法的具體步驟如下：

Step1：圖像的分割與碼本的構(gòu)成。把圖像分割成不重疊的B×B塊(R塊，記為R),同時(shí)，以縱橫方向步長(zhǎng)均為x像素生成尺寸為2B×2B的D塊池。對(duì)于每個(gè)D塊，采用4-鄰域像素值平均得到B×B塊，這樣的子塊集合構(gòu)成碼本Ω。

Step2：參數(shù)的初始化。設(shè)定R子塊的標(biāo)準(zhǔn)差閾值為y1，碼塊標(biāo)準(zhǔn)差閾值為η，誤差閾值為H,初始鄰域半徑為t，擴(kuò)域步長(zhǎng)為L(zhǎng)。

Step4：對(duì)于子塊R：

(2)若σR≥y1，對(duì)于每個(gè)R子塊，計(jì)算出C(R),并用二分法在上述排好序的容許碼本中搜索與C(R)相差的最小的D塊，并記為Dm。

Step5：搜索最佳的匹配塊。

(1)設(shè)定誤差閾值為H。

(2)設(shè)置臨時(shí)變量為t，并初始化t=k。

(4)否則，令t=t+L，轉(zhuǎn)步驟(3)。

Step6:記錄R的最佳匹配塊D的位置，s和o的值以及變換類(lèi)型。

Step7：對(duì)于其余子塊R，重復(fù)步驟4～6。

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

在實(shí)驗(yàn)中[22]，用MATLAB7.0作為實(shí)驗(yàn)平臺(tái)，選用512*512大小的Lena圖像進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果用峰值信噪比(PSNR)和編碼的時(shí)間來(lái)表示。t為搜索鄰域半徑，并取D塊標(biāo)準(zhǔn)差閾值η為1 225，R塊標(biāo)準(zhǔn)差閾值y1為1，實(shí)驗(yàn)結(jié)果見(jiàn)圖3～5(圖中t=3)。

分形圖像壓縮改進(jìn)主要集中在縮短編解碼時(shí)間、提高解碼圖像質(zhì)量這兩個(gè)方面。而文中算法自定義一種子塊匹配特征，旨在保證一定解碼圖像質(zhì)量的前提下盡量縮短編解碼時(shí)間。下面，以相對(duì)梯度特征來(lái)作為最新穎的特征匹配算法的一個(gè)代表，將文中算法的歐氏比C(R)換成相對(duì)梯度特征,其他量基本不變來(lái)進(jìn)行代碼仿真，并輸出其編解碼的時(shí)間以及信噪比。

圖3 原圖

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

圖5 相對(duì)梯度特征算法實(shí)驗(yàn)結(jié)果圖

表1給出了文中算法與基本分形算法以及相對(duì)梯度算法效果的比較。其中，以t表示編解碼的時(shí)間，以信噪比表示重構(gòu)圖像質(zhì)量。

表1 文中算法與基本分形算法對(duì)比結(jié)果 (測(cè)試圖像：Lena)

分析實(shí)驗(yàn)結(jié)果可得，主觀上，基于歐氏比的快速分形編碼算法的重構(gòu)圖像質(zhì)量基本不變;客觀上，主要從兩個(gè)角度來(lái)看：其一，編解碼時(shí)間。以此來(lái)衡量基于歐氏比特征的分形編解碼的速度，而文中算法的編解碼時(shí)間和基本分形編碼以及子塊特征編碼中比較新穎的相對(duì)梯度算法比較，結(jié)果顯示，編解碼時(shí)間縮短的更加明顯；其二，重構(gòu)圖像的信噪比。以此來(lái)衡量重構(gòu)圖像的質(zhì)量，通過(guò)對(duì)比，文中算法的信噪比基本沒(méi)變，從而在盡量保證一定信噪比的前提下，編解碼時(shí)間可以大大減少。

5 結(jié)束語(yǔ)

由于基本分形編碼時(shí)間過(guò)長(zhǎng)，文中提出了一個(gè)基于歐氏比的改進(jìn)方法來(lái)尋找最佳匹配塊，以縮小碼本塊搜索的范圍，提高編解碼的速度。引進(jìn)了參數(shù)t，η和y1，在盡量保證圖像質(zhì)量不變的條件下，縮短編解碼的時(shí)間。實(shí)驗(yàn)結(jié)果表明，文中算法相對(duì)基本分形的算法應(yīng)用前景更加廣闊。

此外，文中算法還存在許多不足之處，比如信噪比基本沒(méi)有改善等，這些問(wèn)題都是今后需繼續(xù)研究改善的，也是今后研究的重點(diǎn)。而為了在縮短編解碼時(shí)間時(shí)，盡量改善圖形質(zhì)量，筆者將嘗試將文中的子塊特征與其他能夠較好描述圖像紋理細(xì)節(jié)及其他一些特征的量(如：分形維數(shù)、小波、DCT變換等)相結(jié)合來(lái)編寫(xiě)分形算法，以此來(lái)改善重構(gòu)圖像的質(zhì)量。而目前也有大量專(zhuān)家在這種混合編碼方向進(jìn)行了研究，同時(shí)也取得了不少成果。從這些成果來(lái)看，一些混合編碼對(duì)分形圖像編碼的編解碼時(shí)間和重構(gòu)圖像的質(zhì)量上都有所改善,故預(yù)計(jì)將文中算法與其他子塊特征結(jié)合進(jìn)行混合編碼能夠取得預(yù)期的效果，這也是之后研究與探索的重點(diǎn)。

[1]WohlbergB,deJagerG.Areviewofthefractalimagecodingliterature[J].IEEETransactionsonImageProcessing,1999,8(12):1716-1729.

[2]FisherY.Fractalimagecompress:theoryandapplication[M].NewYork:Spring-Verlag,1995.

[3]ShiYipen,GuWei,ZhangLiming.Somenewmethodstofractalimagecompression[J].CommunicationinNonlinerScience&NumericalSimulation,1997,13(2):80-85.

[4]ZhaoYao,YuanBaozong.Imagecompressionusingfractalsanddiscretecosinetransform[J].ElectronicsLetters,1994,30(6):474-475.

[5] 田 巖，彭復(fù)員.數(shù)字圖像處理與分析[M].武漢:華中科技大學(xué)出版社,2009.

[6] 劉忠艷,周 波,車(chē)向前.一種高效的圖像匹配算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(4):45-47.

[7]YamaguchiH.EfficientencodingofcoloredpicturesinR.G.Bcomponents[J].IEEETransactionsonCommunications,1984,32(11):1201-1209.

[8]LaiCM,LamKM,SiuWC.Afastfractalimagecodingbasedonkick-outandzerocontrastconditions[J].IEEETransactionsonImageProcessing,2003,12(11):1398-1403.

[9]PopescuDC,DimcaA,YanH.Anonlinearmodelforfractalimagecoding[J].IEEETransonImageProcessing,1997,6(3):372-382.

[10]HeC,YangSX,HuangX.Variance-basedacceleratingschemeforfractalimageencoding[J].IEEEElectronicsLetters,2004,40(2):115-116.

[11]JacquinAE.Anovelfractalblock-codingtechniquefordigitalimage[C]//ProceedingsofIEEEinternationalconferenceonASSP.[s.l.]:IEEE,1990.

[12] 陳衍儀.圖像壓縮的分形理論和方法[M].北京:國(guó)防工業(yè)出版社，1997.

[13] 陳守吉，張立明.分形與圖像壓縮[M].上海:上?？萍冀逃霭嫔?，1998.

[14] 李高平.分形圖像壓縮編碼[M].成都:西南交通大學(xué)出版社，2010.

[15]BeaumontJM.Imagedatacompressionusingfractaltechniques[J].BritishTelecomTechJournal,1991,9(4):93-109.

[16]BarnsleyMF,HurdLP.Fractalimagecompression[M].Wellesley:AKPeters,1992.

[17]PolvereM,NappiM.Speedupinfractalimagecoding:comparisonofmethods[J].IEEETransactionsonImageProcessing,2000,9(6):1002-1009.

[18]MelnikovG,KatsaggelosAK.Anonuniformsegmentationoptimalhybridfractal/DCTimagecompressionalgorithm[C]//ProcofIEEEinternationalconferenceonacoustics,speech&signalprocessing.[s.l.]:IEEE,1998:2573-2576.

[19]TruongTrieu-Kien,JengJyh-Horng,ReedIS.AfastencodingalgorithmforfractalimagecompressionusingtheDCTinnerproduct[J].IEEETransactionsonImageProcessing,2000,9(4):529-534.

[20] 莊振靜.分形圖像壓縮的兩個(gè)快速編碼算法[D].重慶:重慶大學(xué),2009.

[21]JacobsEW,FisherY,BossRD.Imagecompression:astudyoftheiteratedtransformmethod[J].SignalProcessing,1992,29(3):251-263.

[22] 楊 帆，王志陶，張 華.精通圖像處理經(jīng)典算法[M].MATLAB版.北京:北京航空航天大學(xué)出版社，2014.

A Fast Fractal Image Coding Algorithm Based on Euclidean Ratio

ZHANG Ai-hua,HE Yu-hong,ZHANG Jing

(College of Science,Nanjing University of Posts and Telecommunications,Nanjing 210046,China)

Searching for the best matching block in coding processing occupies a lot of time,which is the main reason for the time of fractal encoding and decoding being too long.If one way is applied to shorten the time of searching the best matching block,the time of fractal encoding and decoding could be sharply decreased.A fractal image coding algorithm based on Euclidean ratio was proposed and the feasibility analysis was given.The algorithm transforms the global searching to the neighborhood searching,which means that only need to search the code block whose Euclidean ratio closes to R block’,the time of searching for the best matching block could be greatly reduced,thus shortening the time of fractal encoding and decoding.Code simulation was conducted for this algorithm by MATLAB.The indicators include image clarity,PSNR before and after encoding and decoding,and the time for encoding and decoding.The experimental results show the algorithm have been improved in terms of encoding time on the premise of guaranteeing the image quality.

fractal;fractal image coding;vector cross product of vectors;Euclidean ratio

2015-03-30

2015-09-04

時(shí)間：2016-01-26

國(guó)家自然科學(xué)基金面上項(xiàng)目(11471114,61372125);南京郵電大學(xué)攀登計(jì)劃一項(xiàng)(NY210018)作者簡(jiǎn)介：張愛(ài)華(1969-)，女，教授，博士，研究方向?yàn)榉蔷€性分析及其應(yīng)用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160126.1521.072.html

TN919.81

A

1673-629X(2016)02-0061-05

10.3969/j.issn.1673-629X.2016.02.014