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

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

基于分類父塊庫特征的快速分形編碼算法

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

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

基本分形圖像壓縮編碼算法雖然是一種很有前途的限失真編碼方法，但是它存在著編碼時(shí)間較長(zhǎng)、計(jì)算復(fù)雜度較高的缺點(diǎn)。為了解決分形圖像壓縮編碼算法編碼時(shí)間過長(zhǎng)的問題，基于圖像的父塊特征，提出了一種改進(jìn)算法。該算法利用圖像父塊的幾何特征預(yù)先把父塊庫分成Ds、De、Dm三大類，通過在各個(gè)類中運(yùn)用相應(yīng)的特征將搜索范圍限制在與子塊特征值相近的鄰域內(nèi)，即將類內(nèi)全局搜索最佳匹配塊轉(zhuǎn)化為類內(nèi)局部搜索最佳匹配塊，有效地減少了搜索對(duì)象，從而進(jìn)一步加快了編碼速度。應(yīng)用該算法與其他算法進(jìn)行了多次仿真對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，相對(duì)于其他算法，在保證一定重建圖像質(zhì)量的前提下，所提出算法的圖像編碼時(shí)間明顯縮短，較為顯著地提高了算法編碼的速度。

分形；分形圖像編碼；分類父塊庫；特征算法

0 引 言

分形理論(Fractal Theory)是非線性科學(xué)研究領(lǐng)域中一個(gè)十分活躍的分支，特別是近年來在計(jì)算機(jī)圖像處理和分析中已得到廣泛應(yīng)用。分形理論的數(shù)學(xué)基礎(chǔ)是分形幾何[1]，它的創(chuàng)始人是美國(guó)科學(xué)家Mandelbrot。分形圖像是一種具有復(fù)雜幾何形狀、不規(guī)則的圖像，但由于其內(nèi)部存在無窮多個(gè)自相似性，故可以用一組簡(jiǎn)單的迭代函數(shù)方程通過隨機(jī)迭代得到。在20世紀(jì)80年代末，這個(gè)思想被引入到圖像的壓縮編碼中。如果將任意圖像近似為分形圖像，那么只要找到其圖像內(nèi)部存在的自相似迭代函數(shù)的參數(shù)，圖像就可以用迭代函數(shù)的參數(shù)來表達(dá)，由此大大壓縮了圖像的信息量，從而可以解決圖像壓縮編碼中的問題。

基于分形的圖像壓縮編碼[2]算法的主要特點(diǎn)是：在獲得較高壓縮比的同時(shí)還能保持較好的解碼圖像質(zhì)量；選擇合適的分形模型可以構(gòu)造出較清晰的邊緣細(xì)節(jié)以及解碼過程快捷等。但與此同時(shí)，其計(jì)算復(fù)雜性較高、編碼時(shí)間長(zhǎng)的缺點(diǎn)也尤為顯著。因此在保證圖像質(zhì)量的前提下，如何加快編碼速度也是分形編碼的一個(gè)重要課題。其中，特征算法[3]是一種應(yīng)用廣泛的快速分形圖像編碼方法。

為此，提出了一種改進(jìn)算法[4-6]，該算法利用圖像父塊的幾何特征預(yù)先把父塊庫分成三類，通過在各個(gè)類中運(yùn)用相應(yīng)的特征將搜索范圍限制在與子塊特征值相近的鄰域內(nèi)，有效減少了搜索對(duì)象，從而進(jìn)一步加快了編碼速度。

1 特征算法

分形編碼的絕大部分時(shí)間都是在海量碼本Ω中搜索每個(gè)R塊的最佳匹配D塊，如果能把全局搜索變?yōu)榫植克阉?，并按照某種方式盡可能排除不太可能匹配的D塊，那么編碼時(shí)間將會(huì)大大減少。特征算法就是基于這種思想，它是先找到一種特征Φ，然后把搜索限制在特征Φ意義下的鄰域內(nèi)進(jìn)行。簡(jiǎn)單描述如下：

最后，在初始匹配塊Dm的k鄰域N(Dm,k)(N(Dm,k)={Di∈Ωη:|i-m|≤k})內(nèi)再進(jìn)行匹配搜索，匹配誤差最小的即為R的最佳匹配塊。

2 結(jié)合分類父塊庫特征的快速編碼算法

上述特征算法在整個(gè)過程中只考慮到圖像塊的一種特征Φ，然而大自然中圖像塊是多種多樣的，包含了圖像塊自身的紋理、邊緣等信息，這一特征Φ并不足以刻畫所有的圖像塊。由此，先對(duì)圖像塊進(jìn)行簡(jiǎn)單合理的分類[7-8]，在各個(gè)類中選取相應(yīng)的特征再進(jìn)行限制搜索。

2.1 圖像塊的幾何特征分類

(1)

其方差為：

(2)

給定閾值T1、T2、T3，對(duì)于父塊的分類[9]如下：

閾值T1、T2、T3是由實(shí)驗(yàn)決定的，一旦閾值定了，每個(gè)父塊庫中的父塊都可計(jì)算出屬于它的類。

2.2 各類特征的選取

對(duì)于Ds類的圖像塊，塊內(nèi)各個(gè)像素之間的灰度差很小，幾乎可看作均值。因此，取文獻(xiàn)[10]中的叉跡Φ1(X)作為特征：

(3)

對(duì)于De類的圖像塊，由于此類塊邊緣的像素以及對(duì)角線或平行線上的元素的整體變化會(huì)對(duì)塊的特征產(chǎn)生較大影響，取Φ2(X)作為特征：

(4)

對(duì)于Dm類的圖像塊，由于此類塊像素點(diǎn)之間的灰度差比較大，取Φ3(X)作為特征：

(5)

2.3 特征與誤差匹配間的關(guān)系

下面的定理給出了特征Φ2,Φ3與匹配誤差的關(guān)系。

定理：設(shè)R,D∈Rn×n(n為偶自然數(shù))，則下面的不等式成立：

E(R,D)≥σR|Φi(R)-Φi(D)|2/(4n2) (i=2,3)

(6)

(7)

且

(8)

由Φ2,Φ3的定義得：

(9)

(10)

(11)

根據(jù)式(7)和式(8)并結(jié)合上式，不難得到：

E(R,D)2=

(12)

式(6)由此推出，證畢。

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

基于上述定理，對(duì)于非平滑塊R，它的最佳匹配塊D一定屬于碼本的子集：{D∈Ω:|Φi(R)-Φi(D)|<ε}(ε>0,i=1,2,3)，即D在特征Φi(X)意義下是R的近郊。因此，可以把搜索范圍限制在特征意義下的初始匹配塊的鄰域內(nèi)，其算法步驟[11-12]如下：

(1)把圖像分割為不重疊的2×2的R塊，以縱橫方向步長(zhǎng)均為8像素生成尺寸為2n+1×2n+1的D塊，對(duì)每個(gè)D采用4-鄰域像素值平均得到2n×2n塊，這樣的子塊集合構(gòu)成碼本Ω。

(2)設(shè)定R塊的閾值T1、T2、T3，碼塊的閾值η及搜索的鄰域半徑k。

(4)求出Dj的灰階均值μj及其方差varj。

(5)對(duì)分割后的圖像塊按幾何特征進(jìn)行分類：

(6)在各個(gè)類中分別進(jìn)行特征算法的分形編碼：

當(dāng)Dj∈Ds時(shí)，計(jì)算此類特征Φ(Dj)=Φ1(X)；

當(dāng)Dj∈De時(shí)，計(jì)算此類特征Φ(Dj)=Φ2(X)；

當(dāng)Dj∈Dm時(shí)，計(jì)算此類特征Φ(Dj)=Φ3(X)。

(7)計(jì)算var(Ri)的值：

若var(Ri)

若var(Ri)>T3，計(jì)算Φ2(R)，并在De類中搜索滿足Φ(Dj)≈Φ(Ri)的Φ(Dj)，記為Dm，并在其k鄰域內(nèi)搜索最佳匹配塊；

若T1

(8)重復(fù)步驟(6)和(7)直至所有碼本全部匹配完成。

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

仿真使用的圖像是512*512，8bit量化的Lena圖像和Boat圖像，操作平臺(tái)為運(yùn)行Windows8酷睿I5(2.70GHzCPU/ 4.00G內(nèi)存)的PC，程序用MATLABR2009b編寫，測(cè)試性能參數(shù)為編碼時(shí)間(s)、峰值信噪比(PSNR)。算法采用固定分割，選取R塊大小為4×4,D塊大小為8×8，生成D塊池的滑動(dòng)步長(zhǎng)為8個(gè)像素。此外，參數(shù)s和g分別按5b和7b量化，對(duì)s的截?cái)喾桨竅13]是：若s>1，則取s=31/32；若s<0，則取s=0。根據(jù)Lena圖像和Boat圖像的實(shí)驗(yàn)數(shù)據(jù)，將兩種算法進(jìn)行比較，結(jié)果如表1和圖1所示。

表1 提出算法與叉跡算法對(duì)比的實(shí)驗(yàn)結(jié)果

由表1中數(shù)據(jù)及圖1擬合的曲線分析可得，當(dāng)解碼圖像的質(zhì)量相同或相差不大時(shí)，該算法的編碼時(shí)間較短。雖然提出的算法要對(duì)圖像塊預(yù)先分類，且特征Φ2,Φ3的計(jì)算量大，但是編碼時(shí)的匹配計(jì)算時(shí)間卻占主要部分。由于分類的原因，所提出的算法比叉跡算法編碼時(shí)間少。

當(dāng)編碼時(shí)間相同或相差不大時(shí)，提出算法的解碼圖像質(zhì)量較高。這是由于預(yù)先對(duì)圖像塊進(jìn)行分類，在類內(nèi)采用相應(yīng)的特征更能描述圖像塊，誤差匹配塊與該特征下的匹配塊距離更接近，從而容易搜索到。

圖1 鄰域半徑k與時(shí)間t、峰值信噪比PSNR的數(shù)據(jù)擬合曲線圖

為了評(píng)價(jià)[14]提出算法的主觀圖像質(zhì)量，圖2給出了提出算法(k=0)和基本算法的解碼圖像對(duì)比結(jié)果。所出算法的時(shí)間為0.59s(基本算法為554s)，PSNR為29.89dB(基本算法為33.74dB)。盡管提出算法的主觀質(zhì)量不如基本算法，但是對(duì)于某些應(yīng)用場(chǎng)合還是可以接受的。

圖2 解碼圖像的對(duì)比結(jié)果

4 結(jié)束語

由于基本分形編碼算法的編碼時(shí)間長(zhǎng)且計(jì)算復(fù)雜度高，因此利用父塊庫的幾何特征并依據(jù)特征算法，提出了一種基于分類父塊庫特征的改進(jìn)方法。通過在各個(gè)類中運(yùn)用相應(yīng)的特征將搜索范圍限制在與子塊特征值相近的鄰域內(nèi)的方式，將類內(nèi)全局搜索最佳匹配塊轉(zhuǎn)化為類內(nèi)局部搜索最佳匹配塊，有效地縮小了搜索范圍，加快了編碼速度。仿真實(shí)驗(yàn)結(jié)果表明，在不影響圖像質(zhì)量的前提下，該算法縮短了圖像的編碼時(shí)間，實(shí)現(xiàn)了編碼速度的提升。

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

[2] Galabov M. Fractal image compression[C]//Compsystech.[s.l.]:[s.n.],2003:347-361.

[3] Chong S T, Man W. Adaptive approximate nearest neighbor search for fractal image compression[J].IEEE Transactions on Image Processing,2002,11(6):605-615.

[4] 田學(xué)軍,舒 忠.改進(jìn)的分形灰度圖像壓縮算法的研究[J].包裝工程,2016,37(5):172-177.

[5] 俞玉蓮.一種改進(jìn)的分形圖像壓縮算法[J].信息技術(shù),2015,39(6):55-57.

[6] Du S,Yan Y,Ma Y.Quantum-accelerated fractal image compression:an interdisciplinary approach[J].IEEE Signal Processing Letters,2015,22(4):499-503.

[7] 趙曉麗,孫 喆.基于新的父塊庫分類的自適應(yīng)圖像分形編碼算法[J].天津理工大學(xué)學(xué)報(bào),2015,31(4):12-17.

[8] 郭 慧,賀 杰,盧振坤.結(jié)合分類方法的并行分形圖像編碼算法研究[J].湘潭大學(xué)自然科學(xué)學(xué)報(bào),2015,37(1):97-102.

[9] Jacquin A E.Fractal image coding:a review[J].Proceedings of the IEEE,1993,81(10):1451-1465.

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

[11] 周一鳴,張 超,張?jiān)?基于圖像子塊特征的快速分形圖像編碼算法[J].計(jì)算機(jī)應(yīng)用研究,2008,25(2):458-459.

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

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

[14] Zhang L,Zhang L,Mou X,et al.FSIM:a feature similarity index for image quality assessment[J].IEEE Transactions on Image Processing,2011,20(8):2378-2386.

A Fast Fractal Coding Algorithm with Feature of Parent Block

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

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

The basic fractal image compression encoding algorithm is a finite lossless encoding method that has great significance,but it spends more time on encoding and is more complicated to calculate.In order to reduce the fractal image compression encoding time,an improved algorithm based on the characteristics of the parent block has been proposed in which the parent block is divided into three categories with the image block geometric features in advance,Ds,De,andDm.Thoughuseofcorrespondingfeaturesineachclass,thesearchrangeislimitedtotheneighborhoodclosedtothesub-blockcharacteristicvalues,whichmeansthatthebestmatchingblockofglobalsearchinclassisturnedintolocalsearchforthebestmatchingblock.Theproposedalgorithmhaseffectivelyreducedthesearchobjects,whichcanfurtheracceleratethespeedofcoding.Testsimulationsformultiplecomparisonshavebeenconductedwiththeproposedalgorithmandothers.Simulationresultsshowthatcomparedwithotherones,theimageencodingtimeoftheproposedalgorithmissignificantlyshortenedintheguaranteeofthequalityofthereconstructedimage,whichhasmoresignificantlyimprovedtheencodingspeed.

fractal;fractal image coding;classified parent block library;characteristics algorithm

2016-05-19

2016-09-08

時(shí)間：2017-03-07

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

汪瑋瑋(1992-)，女，碩士研究生，研究方向?yàn)榉蔷€性分析；張愛華，教授，研究方向?yàn)榉蔷€性分析與動(dòng)力系統(tǒng)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0921.040.html

TP

A

1673-629X(2017)04-0051-04

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