基于雙交叉和特征的快速分形圖像編碼研究

張 璟，張愛華，汪瑋瑋，唐婷婷

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

基于雙交叉和特征的快速分形圖像編碼研究

張 璟，張愛華，汪瑋瑋，唐婷婷

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

針對(duì)傳統(tǒng)基本分形編碼存在的計(jì)算復(fù)雜性較高、編碼時(shí)間較長(zhǎng)的缺點(diǎn)，提出了一種基于雙交叉和的特征值編碼算法，以解決分形圖像編碼時(shí)間過長(zhǎng)的問題。該算法通過構(gòu)造圖像塊適當(dāng)?shù)奶卣飨蛄?，將“R在D集合中搜索MSE意義下的最佳匹配塊”問題轉(zhuǎn)換成“R的特征向量在D的特征向量空間中搜索最佳匹配塊”的問題，將全局搜索轉(zhuǎn)化為相對(duì)意義下的近鄰搜索，使得匹配搜索只在初始匹配塊的鄰域內(nèi)進(jìn)行，有效地減少了搜索對(duì)象，從而進(jìn)一步加快了編碼速度。采用圖像方塊分割進(jìn)行了多種算法的對(duì)比仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明相對(duì)于其他算法，所提出的算法在保證一定重建圖像質(zhì)量的前提下，提高了圖像的結(jié)構(gòu)相似度，圖像編碼時(shí)間明顯縮短，較好地實(shí)現(xiàn)了提高算法編碼速度的目的。

分形；分形圖像編碼；特征向量法；雙交叉和特征

0 引 言

當(dāng)今信息時(shí)代，人們?cè)诿鎸?duì)大量圖像信息數(shù)據(jù)時(shí)，如何進(jìn)行高效率的存儲(chǔ)和傳輸，成為了一個(gè)重要問題。而對(duì)于提高存儲(chǔ)和傳輸?shù)男?，不僅僅只依賴硬件設(shè)備自身的更新?lián)Q代，也需要高性能圖像壓縮技術(shù)的研究予以支持。分形幾何[1]作為新興數(shù)學(xué)的一個(gè)分支，對(duì)描述自然界中那些不規(guī)則的幾何形狀提供了幫助，在圖像編碼鄰域也得到了廣泛的應(yīng)用。

基于分形的圖像壓縮編碼[2]方法是一種新的編碼方法，它是利用圖像的自相似性以及比例特性，通過消除圖像的幾何冗余度來實(shí)現(xiàn)圖像數(shù)據(jù)的壓縮。在分形編碼中，一幅圖像由一組使它近似不變的壓縮仿射變換來表示，重構(gòu)圖像是壓縮變換的不動(dòng)點(diǎn)，壓縮仿射變換的參數(shù)組成原始圖像的分形碼。相對(duì)來說，這是一種簡(jiǎn)單的快速迭代過程，解碼圖像由解碼表示的壓縮變換迭代作用于任意初始圖像來逼近[3]。

分形圖像壓縮編碼的主要特點(diǎn)是：在獲得高壓縮比的同時(shí)還能夠保持較好的解碼圖像質(zhì)量，運(yùn)算速度與提高圖像分辨率的關(guān)系不大，選擇合適的分形模型可以構(gòu)造出較清晰的邊緣細(xì)節(jié)，解碼過程快捷，等等。但與此同時(shí)，其計(jì)算復(fù)雜性較高、編碼時(shí)間較長(zhǎng)的缺點(diǎn)也尤為顯著，已經(jīng)嚴(yán)重影響到了分形編碼的廣泛應(yīng)用[4]。因此在保證圖像質(zhì)量不變或更好的前提下，如何加快編碼也是分形編碼的一個(gè)重要課題。而基于特征向量法的快速分形編碼算法就實(shí)現(xiàn)了這一目標(biāo)，通過構(gòu)造圖像塊適當(dāng)?shù)奶卣飨蛄?，將全局搜索轉(zhuǎn)化為相對(duì)意義下的近鄰搜索，減少了搜索對(duì)象，從而加快了編碼速度。

文中所依據(jù)的特征向量法是Saupe提出的一種快速分形編碼方法[5]，約定碼本Ω中的碼本塊都按某種方式向量化，即D∈Ω表示線性空間Rn中的向量(n=N×N,N×N是碼本塊D的尺寸)。它首先構(gòu)造圖像塊X塊(R塊和D塊)的特征向量φ(X)，然后證明極小化MSE(R,D)的問題等價(jià)于極小化Δ(R,D)的問題：

Δ(R,D)?min(d(φ(R),φ(D)),d(-φ(R), φ(D)))

(1)

其中，d是歐氏距離。

d(FR,FD)≤δ?MSE(R,D)≤ε

(2)

其中，F(xiàn)X為圖像塊X的特征向量；δ>0、ε>0為適當(dāng)閾值。

所以，如何選取特征向量以及在特征向量空間中的搜索方法是特征向量法的關(guān)鍵。

文中選取規(guī)范化圖像子塊水平、垂直中位線，以及兩條對(duì)角線所在直線構(gòu)成的雙交叉上像素點(diǎn)的灰度值作為特征點(diǎn)，以這些特征點(diǎn)的歸一化值的絕對(duì)值之和來定義圖像規(guī)范塊雙交叉和的特征；先在理論上證明了雙交叉和與均方誤差的關(guān)系不等式，再對(duì)碼本Ω中的碼本塊按照每一塊雙交叉和的大小進(jìn)行排序，在編碼每一R塊時(shí)，使用二分法在賦序碼本中找出其初始匹配塊，之后的匹配搜索便直接在初始匹配塊的鄰域內(nèi)進(jìn)行[7-8]。

1 算 法

1.1 算法理論依據(jù)

首先給出雙交叉和特征的定義：

定義1：設(shè)子塊X=(xi,j)∈RN×N，X的規(guī)范化為：

(3)

S(x)=

(4)

即雙交叉和為規(guī)范塊垂直水平交叉線和對(duì)角線(構(gòu)成形如“×”“+”形狀的兩個(gè)交叉的結(jié)構(gòu))上每個(gè)像素點(diǎn)灰度值的絕對(duì)值之和。

理論基礎(chǔ)為下述定理，參考并給出證明：

定理1：設(shè)R,D∈RN×N,則有下面的不等式成立：

(5)

(6)

有：

(7)

由柯西不等式：

(8)

(9)

(10)

而約束條件為：

(11)

證畢。

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

顯然，N(Dinit,k)?Ωη?Ω。搜索空間由全局搜索變?yōu)榫植克阉?，編碼時(shí)間會(huì)隨著搜索空間的縮小而減少，從而加快編碼速度。對(duì)于不同的k值，編碼加速的程度有所不同[13-14]。

2 仿真實(shí)驗(yàn)及結(jié)果分析

文中圖像采用方塊分割，仿真使用的圖像是256×256，8bit量化的Lena圖像。選取R塊大小為8×8，D塊大小為16×16，步長(zhǎng)σ=16。操作平臺(tái)為運(yùn)行Windows7的IntelPentium(2.00GHzCPU/2.00G內(nèi)存)PC，仿真程序使用MATLABr2012b編寫，測(cè)試參數(shù)為編碼時(shí)間(s)、峰值信噪比(PSNR)(dB)和結(jié)構(gòu)相似度(FSIM)[15]。

通過實(shí)驗(yàn)將文中算法與基本算法以及1-范數(shù)算法[16]的編碼性能進(jìn)行比較：雙交叉和特征算法的編碼時(shí)間與解碼圖像質(zhì)量跟R塊的分類閾值τ，容許碼本閾值參數(shù)η，搜索鄰域半徑大小k有關(guān)。根據(jù)文獻(xiàn)[9]，對(duì)于參數(shù)τ和η，固定其取值，默認(rèn)τ=4，η=3。根據(jù)Lena圖像的實(shí)驗(yàn)數(shù)據(jù)，三種算法比較結(jié)果見表1。

搜索鄰域半徑K取不同值時(shí)，三種算法的實(shí)驗(yàn)效果如圖1～3所示。

表1 基本分形算法、1-范數(shù)算法與文中算法對(duì)比結(jié)果

從表中數(shù)據(jù)分析可得，雙交叉和特征算法與基本分形算法及1-范數(shù)算法相比，從主觀上看，基于雙交叉和特征算法基本上不改變重構(gòu)圖像的質(zhì)量；從客觀上看，相比于1-范數(shù)算法，文中算法在略微提高性噪比的基礎(chǔ)上，大幅減少了運(yùn)算時(shí)間，且提高了結(jié)構(gòu)相似度，與基本分形算法相比，該算法并沒有降低太多信噪比，且編碼速度比之快了6倍，結(jié)構(gòu)相似度也顯著提高。綜上所述，文中算法可以在保證一定圖像質(zhì)量的前提下，大幅提高編碼速度和結(jié)構(gòu)相似度。

圖1 k=1的實(shí)驗(yàn)結(jié)果圖

圖2 k=2的實(shí)驗(yàn)結(jié)果圖

圖3 k=3的實(shí)驗(yàn)結(jié)果圖

3 結(jié)束語

由于傳統(tǒng)基本分形編碼有著計(jì)算復(fù)雜性較高、編碼時(shí)間較長(zhǎng)的缺點(diǎn)，依據(jù)特征向量法提出了一種基于雙交叉和特征向量的改進(jìn)方法。通過尋找最佳匹配塊的方式，在不影響圖像質(zhì)量的前提下，縮短了圖像編碼時(shí)間，實(shí)現(xiàn)了編碼速度的提升，并提高了圖像的結(jié)構(gòu)相似度。而且文中算法引進(jìn)了參數(shù)搜索鄰域半徑k，可以針對(duì)不同場(chǎng)合的需要來選擇合適的k值，有較強(qiáng)的靈活性和實(shí)用性。

實(shí)驗(yàn)結(jié)果表明，該算法相對(duì)于基本分形算法，編碼效率更高，應(yīng)用前景更加廣闊。

[1] 法爾科內(nèi).分形幾何-數(shù)學(xué)基礎(chǔ)及其應(yīng)用[M].第2版.北京:人民郵電出版社,2007.

[2]GalabovM.Fractalimagecompression[C]//Proceedingsofthe4thinternationalconferenceoncomputersystemsandtechnologies:e-learning.[s.l.]:ACM,2003:347-361.

[3] 齊利敏,劉文耀,呂大偉.基于分形的快速壓縮編碼方法[J].西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版,2008,35(2):373-376.

[4] 馮 曄,馮忠義,朱幼蓮,等.分形編碼技術(shù)的介紹與展望[J].常州技術(shù)師范學(xué)院學(xué)報(bào),1999,5(2):1-6.

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

[6]WohlbergB,JagerGD.Areviewofthefractalimagecodingliterature[J].IEEETransactionsonImageProcessingAPublicationoftheIEEESignalProcessingSociety,1999,8(12):1716-1729.

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

[8]LaiCM,LamKM,SinWC.Improvedsearchingschemeforfractalimagecoding[J].ElectronicsLetters,2002,38(25):1653-1654.

[9] 何傳江,黃席樾.基于圖像塊叉跡的快速分形圖像編碼算法[J].計(jì)算機(jī)學(xué)報(bào),2005,28(10):1753-1758.

[10]LeeCK,LeeWK.Fastfractalimageblockcodingbasedonlocalvariances[J].IEEETransactionsonImageProcessingAPublicationoftheIEEESignalProcessingSociety,1998,7(6):888-891.

[11]HartensteinH,SaupeD.LosslessaccelerationoffractalimageencodingviathefastFouriertransform[J].SignalProcessingImageCommunication,2010,16(4):383-394.

[12] 袁宗文,魯業(yè)頻,楊漢生.半叉跡特征的快速分形圖像編碼[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(3):197-201.

[13] 李高平,楊 軍,陳毅紅.改進(jìn)轉(zhuǎn)動(dòng)慣量特征的快速分形圖像編碼算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(24):144-148.

[14] 張思思,劉 宇,趙志濱,等.一種基于相鄰匹配的分形圖像檢索算法[J].計(jì)算機(jī)科學(xué),2015,42(12):292-296.

[15]ZhangLin,ZhangLei,MouXuanqin.FSIM:afeaturesimilarityindexofimagequalityassessment[J].IEEETransactionsonImageProcessing,2011,20(8):2378-2386.

[16]HeC,YangSX,XuX.Fastfractalimagecompressionbasedonone-normofnormalizedblock[J].ElectronicsLetters,2004,40(17):1052-1053.

Investigation on Fast Fractal Image Encoding with Sum of Double Cross Eigenvalues

ZHANG Jing,ZHANG Ai-hua,WANG Wei-wei,TANG Ting-ting

(School of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

For the shortcomings of high computational complexity and long encoding time of the traditional fractal coding,an encoding algorithm based on the sum of double cross eigenvalues is proposed in order to solve the problem of long encoding time.The problem,RsearchforthebestmatchingblockofMSEsenseintheDset,isconvertedintoanotherone,theeigenvectorofRsearchforthebestmatchingblockofDintheeigenvectorspace.Thus,globalsearchistransformedintoneighborsearchbyconstructingsuitablefeaturevectorfortheimageblockintheoppositesenseandmatchingsearchiscarriedoutonlyinthefieldoftheinitialmatchingblock,whichreducessearchobjectsandthenspeedsupencoding.Throughcomparativesimulationexperiment,avarietyofalgorithmsarecomparedandsimulatedbyusingimagesegmentation.Theresultsofexperimentsshowthatthealgorithmpresentedhasimprovedthefeaturesimilarityandreducestheimageencodingtimemoreeffectivelyunderthepremiseofensuringqualityofthereconstructedimage,andthatthepurposeofimprovingtheencodingspeedprocedurehasbeenachieved.

fractal;fractal image coding;eigenvector method;sum of double cross eigenvalues

2016-04-21

2016-08-10

時(shí)間：2017-02-17

國(guó)家自然科學(xué)基金面上項(xiàng)目(11471114,61372125)

張 璟(1991-)，男，碩士研究生，研究方向?yàn)榉蔷€性分析及應(yīng)用；張愛華，教授，碩士生導(dǎo)師，研究方向?yàn)榉蔷€性分析。

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

TP

A

1673-629X(2017)03-0159-04

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