張愛(ài)華,何雨虹,張 璟

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

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

張愛(ài)華,何雨虹,張 璟

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

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

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

0 引 言

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

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

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

1 理論基礎(chǔ)

1.1 小波變換

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

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

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

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

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

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

1.2 基本分形編碼

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

1.3 歐氏比特征

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

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

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

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

1.4 算法理論依據(jù)

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

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

在分形編碼中，每個(gè)C塊由其最佳匹配塊D∈Ω的灰度變換來(lái)近似，即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è)定一個(gè)誤差閾值H,確保這種誤差不至太大,從而讓解碼圖像質(zhì)量得到保證。

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

3 算法實(shí)現(xiàn)

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

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

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

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

Step5：對(duì)于子塊R:

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

Step6：搜索最佳的匹配塊。

(1)令誤差閾值為H。

(2)設(shè)臨時(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的值和變換的類(lèi)型。

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

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

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

圖3 原圖

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

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

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

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

5 結(jié)束語(yǔ)

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

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

[2] 劉 勍,張?jiān)诜?馬義德,等.基于分形理論的圖像壓縮編碼技術(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ū)域檢測(cè)的小波分形圖像壓縮方法[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] 郝俊瑞,許紅軍.基于分類(lèi)的小波-分形混合編碼[J].無(wú)線(xiàn)電工程,2001(z1):85-88.

[10] 張愛(ài)華,盛 飛,楊 培,等.基于相似比的快速分形編碼算法[J].計(jì)算機(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] 黃 晉.混合小波-分形圖像壓縮方法的研究與實(shí)現(xiàn)[D].貴陽(yáng):貴州大學(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].計(jì)算機(jī)工程與應(yīng)用,2010,46(2):170-173.

[20] 徐 慶,劉 弘,吳曉燕.基于2-范數(shù)匹配的分形圖像編碼改進(jìn)算法[J].計(jì)算機(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í)與技術(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ò)出版時(shí)間：2017-04-28

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

張愛(ài)華(1969-),女,博士,教授,研究方向?yàn)榉蔷€(xiàn)性分析及應(yīng)用；何雨虹(1988-),女,碩士,研究方向?yàn)榉中螆D像壓縮算法改進(jìn)。

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