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

張愛華，何雨虹，張 璟

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

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

張愛華，何雨虹，張 璟

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

分形編解碼的時間過長，主要是因為編碼過程中的搜索碼本塊的最佳匹配塊占據了大量時間。如果能用某種方式，盡量縮短搜索碼本塊最佳匹配塊的時間，那么分形編解碼的時間就能大大縮短。文中提出了一種基于歐氏比的分形編碼算法并給出了可行性分析。該算法將全局搜索最佳匹配塊的算法轉變為相對意義下的鄰域搜索最佳匹配塊的算法，即只搜索與R塊的歐氏比相差較近的碼本塊，從而大大減少了搜索最佳匹配塊所占用的時間,進而縮短了分形編解碼的時間。用MATLAB對文中算法進行代碼仿真，仿真效果用主觀上觀察圖像的清晰度、圖像編解碼前后的信噪比和編解碼的時間來評價。實驗結果表明：該算法在盡量保證圖像質量的前提下，使得分形編解碼的時間大大縮短。

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

0 引 言

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

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

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

1 基本分形方法簡介

1.1 圖像分割

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

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

1.2 碼本構成

圖1 收縮D塊的構造

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

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

(2)關于鉛垂中軸(j=B-1/2)對稱的反射：(t1D)i,j=Di,B-1-j;

(3)關于水平中軸(i=B-1/2)對稱的反射：(t1D)i,j=DB-1-i,j;

(4)關于主對角線(i=j)對稱的反射：(t3D)i,j=Dj,i;

(5)關于次主對角線(i+j=B-1)對稱的反射：(t4D)i,j=DB-1-j,B-1-i;

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

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

(8)關于D塊的中心逆時針旋轉270°：(t7D)i,j=DB-1-i,j。

1.3 編碼匹配階段

E(R,D)=

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

1.4 解碼階段

分形解碼較為簡單，重構的圖像是分形碼描述的壓縮變換T的近似的不動點圖像，可以按照分形碼提供的分割信息對任何初始圖像進行迭代來生成。不動點定理可保證迭代的收斂性，而拼貼定理則可保證壓縮變換T的不動點就是原圖像的近似[15-16]。

2 算法理論依據

首先給出一個比較簡單的結果：給定R,D∈Rn×n，以及最小值的問題：

顯然,‖R-sD-oI‖2是關于s和o的二次多項式，分別對s和o求偏導，并令導數值為零，解關于s和o的一個線性方程組，解其得：

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

R≈s·D+o·I

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

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

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

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

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

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

下面給出特征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 算法分析與實現

3.1 算法分析

顯然，這種做法不僅提高了重構圖像質量，還能通過減少碼塊的數目來加快編碼的速度。

為了降低鄰域搜索較小時，局部的搜索匹配子塊代替全局的匹配塊而引起圖像質量下降這一缺點，應注意以下幾點[20]：

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

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

3.2 算法的實現

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

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

Step2：參數的初始化。設定R子塊的標準差閾值為y1，碼塊標準差閾值為η，誤差閾值為H,初始鄰域半徑為t，擴域步長為L。

Step4：對于子塊R：

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

Step5：搜索最佳的匹配塊。

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

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

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

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

Step7：對于其余子塊R，重復步驟4～6。

4 實驗仿真結果

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

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

圖3 原圖

圖4 實驗結果圖

圖5 相對梯度特征算法實驗結果圖

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

表1 文中算法與基本分形算法對比結果 (測試圖像：Lena)

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

5 結束語

由于基本分形編碼時間過長，文中提出了一個基于歐氏比的改進方法來尋找最佳匹配塊，以縮小碼本塊搜索的范圍，提高編解碼的速度。引進了參數t，η和y1，在盡量保證圖像質量不變的條件下，縮短編解碼的時間。實驗結果表明，文中算法相對基本分形的算法應用前景更加廣闊。

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

[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] 田 巖，彭復員.數字圖像處理與分析[M].武漢:華中科技大學出版社,2009.

[6] 劉忠艷,周 波,車向前.一種高效的圖像匹配算法[J].計算機技術與發展,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].北京:國防工業出版社，1997.

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

[14] 李高平.分形圖像壓縮編碼[M].成都:西南交通大學出版社，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] 莊振靜.分形圖像壓縮的兩個快速編碼算法[D].重慶:重慶大學,2009.

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

[22] 楊 帆，王志陶，張 華.精通圖像處理經典算法[M].MATLAB版.北京:北京航空航天大學出版社，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

時間：2016-01-26

國家自然科學基金面上項目(11471114,61372125);南京郵電大學攀登計劃一項(NY210018)作者簡介：張愛華(1969-)，女，教授，博士，研究方向為非線性分析及其應用。

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