基于小波與分形理論的圖像壓縮編碼算法

張愛華,何雨虹,張 璟

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

基于小波與分形理論的圖像壓縮編碼算法

張愛華,何雨虹,張 璟

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

在分形圖像編碼中,影響分形圖像編解碼速度的主要因素是從大量碼本中搜索R碼本塊的最佳匹配碼本塊。如果能夠使用一種方式盡可能縮短匹配塊的搜索范圍,那么編碼的時間就可以大大減少。然而，在提高編解碼速度的同時，重構(gòu)圖像的質(zhì)量卻有所降低。針對上述這些問題，在定義一種圖像子塊的新特征—歐氏比基礎(chǔ)上，將小波變換與分形編碼有機結(jié)合,提出了一種基于小波與分形理論的圖像壓縮編碼算法。該算法將全局搜索碼本塊轉(zhuǎn)化為局部搜索碼本塊,縮短了編解碼的時間,同時利用連續(xù)小波變換的平滑特性,進一步提高了重構(gòu)圖像質(zhì)量。仿真實驗結(jié)果表明，與特征算法中的梯度算法相比，所提出的算法不僅縮短了圖像編解碼的時間,還提高了重構(gòu)圖像的質(zhì)量。

分形圖像編碼；小波變換；歐氏比；子塊特征

0 引 言

隨著圖像存儲與傳輸量的增大,圖像壓縮編碼技術(shù)[1]受到廣泛關(guān)注，而這一技術(shù)得到迅速發(fā)展卻是近年來發(fā)生的事情。20世紀(jì)60年代末，在美國舉行的“圖像編碼會議”宣告圖像編碼正式成為一門學(xué)科[2]。在此基礎(chǔ)上,提出了許多新的算法與改進圖像壓縮算法。圖像壓縮編碼技術(shù)從總體上來說就是利用圖像數(shù)據(jù)固有的冗余性和相關(guān)性，將一個大的數(shù)據(jù)文件轉(zhuǎn)成較小的同性質(zhì)的文件,從而更加有效地存儲和傳輸數(shù)據(jù)。1975年，圖像壓縮技術(shù)的主要成果體現(xiàn)在變換編碼技術(shù)。1979年后，小波變換理論[3-5]以及分形理論的建立，為圖像壓縮編碼提供了理論基礎(chǔ)，同時使得圖像壓縮編碼能夠取得更高的比特率，并向著信噪比更高的方向發(fā)展。

Jacquin提出的方案讓分形壓縮編碼的發(fā)展進入了新的高度，并成為目前編碼研究的熱點。針對分形圖像壓縮算法存在的問題，目前大致從以下幾個方向展開:提高分形的編碼解碼速率;提高分形的編碼PSNR值;分形壓縮編碼方法與其他方法相結(jié)合的新的壓縮算法[6];開發(fā)能將圖像精確分割的有效方法，如利用小波來幫助圖像分割，是分形圖像中的一個熱門話題，也使得小波圖像壓縮成為當(dāng)前最有發(fā)展前途的壓縮方法之一。目前，對小波系數(shù)編碼的問題是小波圖像壓縮研究的主要問題之一[7]。此外,小波變換與其他壓縮方法相結(jié)合,如小波與分形相結(jié)合的圖像壓縮方法就是當(dāng)前的一個研究熱點。幾乎每一種編碼方法都有自己的優(yōu)勢，如果能利用這些優(yōu)勢，將圖像壓縮算法進行合理重組，或許能取得意想不到的效果。大多文獻采用兩種編碼混合算法[8-9],而文中嘗試將子塊特征，分形以及小波三者結(jié)合進行編碼。

小波變換能很好地分解圖像，其本身雖然并不具有壓縮功能，但對于圖像信號的處理有著獨特的優(yōu)良特性。它把圖像信號分解為具有不同尺度和空間選擇性的一系列子空間信號，并可以由這些信號重構(gòu)圖像?；镜姆中尉幋a具有高壓縮比，但是壓縮過程的編碼解碼的速度和重構(gòu)圖像的質(zhì)量都嚴(yán)重影響了分形圖像編碼的效果。連續(xù)小波變換具有一定的平滑性，對編碼圖像先進行小波變換能有效提高重構(gòu)圖像的質(zhì)量。小波分解的低頻信息保持了圖像的主要能量，高頻部分涵蓋的信息較少，如果對低頻部分利用“歐氏比”特征對圖像碼本進行匹配[10-11]，或許能取得較優(yōu)的效果。實驗結(jié)果表明，這樣的混合編碼，不僅能提高重構(gòu)圖像的質(zhì)量，還能有效縮短編解碼的時間。

1 理論基礎(chǔ)

1.1 小波變換

定義1：所謂小波變換,即存在于一個較小區(qū)域的波，其數(shù)學(xué)定義為：設(shè)φ(t)為一平方可積函數(shù),即φ(t)∈L2(R),若其變換φ(w)滿足條件[6]:

則稱φ(t)為一個基本小波或小波母函數(shù)。

定義2：將小波母函數(shù)進行伸縮或平移,設(shè)其尺度因子為a,平移因子為τ,并記平移伸縮后的函數(shù)為:

并稱φa,τ(t)是參數(shù)a和τ的小波基函數(shù)。由于a和τ均取連續(xù)變換的值,因此又稱為連續(xù)小波基函數(shù),它們是由同一母函數(shù)φ(t)經(jīng)伸縮和平移后得到的一組函數(shù)系列。對于二維圖像信號,分別在水平和垂直方向進行濾波，實現(xiàn)二維小波多分辨率分解。原始信號f(x,y)通過一級小波分解被分成4個子帶,即一個逼近信號LL和三個細(xì)節(jié)信號LH,HL,HH。其中，LL是低頻分量,蘊含圖像的主要能量；LH,HL,HH是高頻分量,給出的是圖像信號的細(xì)節(jié)與差別。

為了更加清楚地說明圖形經(jīng)過小波分解后,各個方向系數(shù)矩陣所代表的信息的不同特點,分別給出Lena圖像經(jīng)過一級小波分解的LL,LH,HL,HH方向的系數(shù)矩陣圖像。從這四幅圖像不難看出，水平、垂直方向都為低頻的LL部分,集中了原始圖像的主要能量,其他三個方向,即高頻部分，顯示了圖像邊緣、輪廓的紋理特征[12-14],如圖1所示。

圖1 一級小波分解各方向系數(shù)矩陣圖

1.2 基本分形編碼

然后記錄D塊的位置，變換類型w，s和o的值。

1.3 歐氏比特征

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

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

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

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

1.4 算法理論依據(jù)

首先給出一個簡單結(jié)果：給定R,D∈Rn×n，以及最小值問題[19-20]:

顯然,‖R-s·D-o·I‖2是s、o的二次多項式，分別對s、o求偏導(dǎo)，并令導(dǎo)數(shù)為零，求解關(guān)于s、o的線性方程組，得到問題的解為：

在分形編碼中，每個C塊由其最佳匹配塊D∈Ω的灰度變換來近似，即R≈s·D+o·I。

下面給出特征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)

2 算法分析

(1)設(shè)定閾值t,確保在與R塊的歐氏比相差最小的Dm塊的t鄰域內(nèi)尋找到最佳的匹配碼塊D。

(2)設(shè)定一個誤差閾值H,確保這種誤差不至太大,從而讓解碼圖像質(zhì)量得到保證。

首先要在預(yù)設(shè)鄰域N(Dm,t)內(nèi)尋找局部的匹配碼塊,若H小,則局部匹配塊就可以作為最佳匹配塊；否則的話,按照步長L來擴大鄰域的搜索區(qū)域,繼續(xù)進行搜索,直到搜索到鄰域擴大為整個碼本時停止。

3 算法實現(xiàn)

基于上述分析并結(jié)合小波變換,文中算法步驟可歸納如下:

Step1：對灰度圖像進行小波分解,量化,提取低頻系數(shù)矩陣圖,并調(diào)整其尺度得到低頻系數(shù)矩陣圖。

Step2：圖像的分割與碼本的構(gòu)成。把低頻圖像分割成不重疊的B×B塊(記為R),同時,以橫縱方向步長均為x的像素形成大小為2B×2B的D塊池。對于其中每個D塊,采用4-鄰域像素值平均得到B×B塊,而由這些子塊構(gòu)成的集合稱為碼本Ω。

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

Step5：對于子塊R:

(2)如果σR≥y1,對于每個給定的R子塊,計算出C(R)的值,并用二分法在已排序的可行碼本中搜索與C(R)的值相差最小的一個D塊,并將其記作Dm。

Step6：搜索最佳的匹配塊。

(1)令誤差閾值為H。

(2)設(shè)臨時變量為t,并初始化其值,令t=k。

(3)在Dm的t鄰域范圍內(nèi)搜索最佳匹配塊D,若E(R,D)

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

Step7：記錄下R的最佳匹配塊D的位置,s,o的值和變換的類型。

Step8：對其余的子塊R,重復(fù)進行步驟(4)～(6)。

4 實驗結(jié)果及分析

用Matlab7.0對尺寸為512*512的Lena圖像進行實驗[24],用峰值信噪比(PSNR)以及編碼時間作為評價算法性能的指標(biāo),其中t是搜索鄰域的半徑,并取D塊的標(biāo)準(zhǔn)差閾值η的大小為1 225,R塊標(biāo)準(zhǔn)差閾值y1的大小為1。將得到的實驗結(jié)果分別與基本分形算法、特征算法中具有代表性的相對梯度算法進行比較,結(jié)果如圖3～5以及表1所示(其中t=3)。

圖3 原圖

圖4 文中算法結(jié)果

圖5 相對梯度算法結(jié)果

表1 算法對比結(jié)果

對上面的實驗數(shù)據(jù)進行分析可得,與基本分形算法相比,文中算法在保證一定重構(gòu)圖像質(zhì)量的前提下,大大縮短了編解碼的時間,與相對梯度算法相比,文中算法不僅提高了編解碼的速度,而且改善了重構(gòu)圖像的質(zhì)量。

5 結(jié)束語

由于基本分形編碼的時間較長,定義一種子塊新特征,以縮短編解碼的時間,但同時也影響了重構(gòu)圖像的質(zhì)量。為了在進一步縮短編解碼時間的同時改善重構(gòu)圖像質(zhì)量，提出了一種基于小波與分形理論的圖像壓縮編碼算法。實驗結(jié)果表明，相對于基本分形算法以及一些同類特征算法,提出算法的仿真效果更優(yōu),應(yīng)用前景也更加廣闊。今后，可嘗試多種編碼結(jié)合的混合編碼算法，進一步加強改善重構(gòu)圖像質(zhì)量的研究。

[1] 楊延寧.圖像壓縮編碼技術(shù)[J].有線電視技術(shù),2003,10(21):38-40.

[2] 劉 勍,張在峰,馬義德,等.基于分形理論的圖像壓縮編碼技術(shù)[J].信息與電子工程,2004,2(4):246-251.

[3] 尹顯東,唐 丹,鄧 君,等.圖像小波變換的分形編碼技術(shù)[J].信息與電子工程,2003,1(3):23-27.

[4] Li J,Kuo C C J.Image compression with a hybrid wavelet-fractal coder[J].IEEE Transactions on Image Processing,1999,8(6):868-874.

[5] 陳明夫.基于區(qū)域檢測的小波分形圖像壓縮方法[D].哈爾濱：哈爾濱理工大學(xué),2013.

[6] Davis G M.A wavelet-based analysis of fractal image compression[J].IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society,1998,7(2):141-154.

[7] 杜廣環(huán).基于小波分析的圖像壓縮算法應(yīng)用[D].大連：大連理工大學(xué),2008.

[8] 向 輝.基于小波理論的圖像壓縮算法研究[D].上海:華東師范大學(xué),2005.

[9] 郝俊瑞,許紅軍.基于分類的小波-分形混合編碼[J].無線電工程,2001(z1):85-88.

[10] 張愛華,盛 飛,楊 培,等.基于相似比的快速分形編碼算法[J].計算機技術(shù)與發(fā)展,2012,22(11):176-178.

[11] Zhang Y,Zhai G.Wavelet-based fractal image compression[C]//Third international symposium on multispectral image processing and pattern recognition.[s.l.]:International Society for Optics and Photonics,2003:396-399.

[12] 黃 晉.混合小波-分形圖像壓縮方法的研究與實現(xiàn)[D].貴陽:貴州大學(xué),2007.

[13] Barnsley M,Vince A.Fractal tilings from iterated function systems[J].Discrete & Computational Geometry,2014,51(3):729-752.

[14] Davoine F,Robert G,Chassery J M.How to improve pixel-based fractal image coding with adaptive partitions[M]//Fractals in engineering.London:Springer,2001:292-306.

[15] Barnsley M F,Hurd L P.Fractal image compression[M].Wellesley:AK Peters,1992.

[16] Wohlberg B,Jager G.A review of the fractal image coding literature[J].IEEE Transactions on Image Processing,1999,8(12):1716-1729.

[17] Jacobs E W,Fisher Y,Boss R D.Image compression:a study of the iterated transform method[J].Signal Processing,1992,29(3):251-263.

[18] Fisher Y.Fractal image compress:theory and application[M].New York:Spring-Verlag,1995:49-51.

[19] 莊振靜,何傳江,申小娜.基于規(guī)范塊半范數(shù)的快速分形編碼算法[J].計算機工程與應(yīng)用,2010,46(2):170-173.

[20] 徐 慶,劉 弘,吳曉燕.基于2-范數(shù)匹配的分形圖像編碼改進算法[J].計算機工程,2010,36(4):205-206.

[21] 李高平.分形幾何及其在圖像壓縮編碼中的應(yīng)用研究[D].重慶:重慶大學(xué),2005.

[22] Shi Yipen,Gu Wei,Zhang Liming.Some new methods to fractal image compression[J].Communication in Nonliner Science & Numerical Simulation,1997,13(2):80-85.

[23] Polvere M,Nappi M.Speedup in fractal image coding:comparison of methods[J].IEEE Transactions on Image Processing,2000,9(6):1002-1009.

[24] 黃小虎,胡 清,黃 杰.基于MATLAB的分形仿真研究[J].電腦知識與技術(shù),2007(5):847-849.

Image Compression Coding Algorithm Based on Wavelet and Fractal Theory

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

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

In fractal image coding,it is the main factor that affects the decoding speed to search the best D sub block of the R sub block from a large number of code-book.However,the time of encode-decode would be significantly reduced if the search range of blocks could be cut down as much as possible.It is the problem that while the speed of encoding being improved the quality of reconstructed image would be getting worse.Aiming at above problems,after a new feature of the image sub-blocks,Euclidean ratio,has been defined,a fractal coding algorithm integrated wavelet transform with fractal encoding has been proposed,which converts the global search code-book to the local search code-book for having shortened the decoding time and employs the smooth property of continuous wavelet transform for improvement of the reconstructed image quality.The simulation results show that the proposed algorithm has not only decreased encode-decode time but also promoted the reconstructed image quality compared with the relative gradients algorithm of the characteristic algorithm.

fractal image coding;wavelet transform;Euclidean ratio;sub block feature

2016-03-04

2016-07-13 網(wǎng)絡(luò)出版時間：2017-04-28

國家自然科學(xué)基金面上項目(11471114，61372125)；江蘇省自然科學(xué)基金項目(BK20150867)；南京郵電大學(xué)攀登計劃一項(NY210018)

張愛華(1969-),女,博士,教授,研究方向為非線性分析及應(yīng)用；何雨虹(1988-),女,碩士,研究方向為分形圖像壓縮算法改進。

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

TN919.81

A

1673-629X(2017)06-0046-05

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