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

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

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

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

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

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

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

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

0 引 言

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

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

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

1 特征算法

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

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

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

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

2.1 圖像塊的幾何特征分類

(1)

其方差為：

(2)

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

閾值T1、T2、T3是由實驗決定的，一旦閾值定了，每個父塊庫中的父塊都可計算出屬于它的類。

2.2 各類特征的選取

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

(3)

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

(4)

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

(5)

2.3 特征與誤差匹配間的關系

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

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

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

(6)

(7)

且

(8)

由Φ2,Φ3的定義得：

(9)

(10)

(11)

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

E(R,D)2=

(12)

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

2.4 算法分析與實現

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

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

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

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

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

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

當Dj∈Ds時，計算此類特征Φ(Dj)=Φ1(X)；

當Dj∈De時，計算此類特征Φ(Dj)=Φ2(X)；

當Dj∈Dm時，計算此類特征Φ(Dj)=Φ3(X)。

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

若var(Ri)

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

若T1

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

3 仿真實驗及結果分析

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

表1 提出算法與叉跡算法對比的實驗結果

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

當編碼時間相同或相差不大時，提出算法的解碼圖像質量較高。這是由于預先對圖像塊進行分類，在類內采用相應的特征更能描述圖像塊，誤差匹配塊與該特征下的匹配塊距離更接近，從而容易搜索到。

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

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

圖2 解碼圖像的對比結果

4 結束語

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

[1] 法爾科內.分形幾何-數學基礎及其應用[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] 田學軍,舒 忠.改進的分形灰度圖像壓縮算法的研究[J].包裝工程,2016,37(5):172-177.

[5] 俞玉蓮.一種改進的分形圖像壓縮算法[J].信息技術,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] 趙曉麗,孫 喆.基于新的父塊庫分類的自適應圖像分形編碼算法[J].天津理工大學學報,2015,31(4):12-17.

[8] 郭 慧,賀 杰,盧振坤.結合分類方法的并行分形圖像編碼算法研究[J].湘潭大學自然科學學報,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].計算機學報,2005,28(10):1753-1758.

[11] 周一鳴,張 超,張曾科.基于圖像子塊特征的快速分形圖像編碼算法[J].計算機應用研究,2008,25(2):458-459.

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

[13] 何傳江,申小娜.改進分形圖像編碼的叉跡算法[J].計算機學報,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

時間：2017-03-07

國家自然科學基金面上項目(11471114，61372125)

汪瑋瑋(1992-)，女，碩士研究生，研究方向為非線性分析；張愛華，教授，研究方向為非線性分析與動力系統。

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