張 忠,王 瑋,丁 群

摘 要:為了避免分形編碼所固有的方塊效應(yīng),進(jìn)一步提高圖像編碼的工作效率和重構(gòu)圖像的質(zhì)量,對(duì)分形編碼和小波零樹編碼進(jìn)行優(yōu)化組合,提出一種分形與改進(jìn)的SPIHT算法相結(jié)合的圖像壓縮方法。基本方法是,對(duì)小波分解后的低頻子帶進(jìn)行基于信息熵的快速分形編碼,以減少編碼時(shí)間;對(duì)包含圖像細(xì)節(jié)邊緣信息的高頻子帶進(jìn)行改進(jìn)的SPIHT編碼,以舍去算法中對(duì)顯著系數(shù)的排序掃描過程,減少算法的復(fù)雜度,同時(shí)提高重構(gòu)圖像的峰值信噪比。實(shí)驗(yàn)表明,相對(duì)于經(jīng)典分形編碼和小波域內(nèi)的分形編碼,該方法在相同壓縮比下,提高了編碼效率和重構(gòu)圖像的質(zhì)量,是一種高效快速的編碼方法。

關(guān)鍵詞:分形;小波變換;信息熵;SPIHT;圖像壓縮

中圖分類號(hào):TN911.73文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2009)20-048-03

Image Compression Method Based on Fractal and Improved SPIHT

ZHANG Zhong,WANG Wei,DING Qun

(Department of Electronic Engineering,Heilongjiang University,Harbin,150080,China)

Abstract:In order to avoid blocking artifacts of fractal coding,to enhance the efficiency of image coding and the quality of reconstructed image,the optimum combination of fractal coding and wavelet zero-tree coding are studied.An image coding method based on the merits of improved SPIHT and fractal image compression technology is proposed.The low-frequency area after wavelet decomposition is factual coded based on entropy to shorten coding time.The high-frequency ones including detail information of image are coded by improved SPIHT,which casts out the process of significantly coefficients to reduce its complexity and improve the PSNR of reconstructed image.Experiments show that this new method can improve the speed of coding as well as the quality of encoded image compared with classical fractal coding and fractal coding based on wavelet.It is a fast and efficient image compression method.

Keywords:fractal;wavelet transform;entropy;SPIHT;image compression

0 引 言

小波變換具有良好的時(shí)頻局部特性及多分辨率特性,壓縮效率優(yōu)于傳統(tǒng)壓縮算法,但并無(wú)特別明顯的效率提高。Shapiro提出的零樹編碼方案[1]采用全新的零樹數(shù)據(jù)結(jié)構(gòu),用以表征小波系數(shù)的空間自相似性,可以有效地利用系數(shù)的空間分布特性,從而達(dá)到較高的壓縮比和信噪比。分形編碼[2,3]突破了基于局域內(nèi)相關(guān)冗余的傳統(tǒng)編碼方法的局限性,有著優(yōu)良的特性。但由于算法本身的特性,編碼過程的復(fù)雜性仍很高,耗費(fèi)時(shí)間很長(zhǎng),編碼質(zhì)量也不理想,這些不足使其應(yīng)用受到很大的限制。

小波編碼和分形編碼都是圖像壓縮技術(shù)研究的主要方向,但二者都存在一定的局限性。利用小波與分形混合的圖像編碼方法對(duì)圖像進(jìn)行壓縮,使兩種算法相得益彰,已經(jīng)成為目前發(fā)展的趨勢(shì)[4]。

1 分形圖像編碼

分形圖像壓縮的理論基礎(chǔ)是迭代函數(shù)系統(tǒng)IFS(Iterated Function System)、吸引子定理和拼貼定理[5]。分形圖像編碼的任務(wù)就是尋找方法來(lái)求出IFS的參數(shù)即圖像的分形編碼。分形圖像解碼則是用某種算法求出該IFS的吸引子。這里對(duì)其理論基礎(chǔ)不再贅述,僅簡(jiǎn)要介紹其實(shí)現(xiàn)過程,進(jìn)而提出一種基于信息熵的快速分形圖像壓縮方法。

1.1 基本分形圖像壓縮的實(shí)現(xiàn)過程

(1) 對(duì)原始圖像進(jìn)行分割。將大小為N×N的圖像I分割成互不相交且大小為K×K的值域塊R(Rangeblock),形成值域塊庫(kù);同時(shí)再將圖像I分割成相互重疊的大小為2K×2K的定義域塊D(Domainblock),形成定義域塊庫(kù)。

(2) 尋找最優(yōu)匹配塊。對(duì)每一值域塊Ri,在定義域塊庫(kù)中找到一個(gè)與之相匹配的定義域塊Di及一種合適的仿射變換ωi,使其在所規(guī)定的失真下ωi(Di)與Ri最接近。

(3) 獲得分形碼。通過比較ωi(Di)與Ri之間的誤差,記錄下ωi(xi,yi,ai,si,oi)。其中ai為8種對(duì)稱旋轉(zhuǎn)變換之一;si和oi分別是灰度變換的尺度因子和偏移因子。對(duì)ωi(xi,yi,ai,si,oi)進(jìn)行量化、編碼、傳輸(或存儲(chǔ)),完成該值域塊的編碼。待所有的Ri都被編碼后,即完成了對(duì)原始圖像的分形編碼。

1.2 基于信息熵的快速分形圖像壓縮

編碼速度太慢一直是基本分形圖像壓縮實(shí)用化的最大障礙。為了縮短搜索時(shí)間,在匹配之前按照?qǐng)D像的特征,將D塊和R塊進(jìn)行分類,匹配時(shí)只在同一類中進(jìn)行搜索比較。信息熵是圖像所含信息的度量。由于圖像塊的信息熵是惟一的,即使該圖像塊經(jīng)過仿射變換后,其信息熵始終不變[6,7]。因此利用信息熵作為一種分類標(biāo)準(zhǔn)對(duì)R塊和D塊進(jìn)行分類。

假設(shè)具有灰度m(0≤m≤255)的像素點(diǎn)在圖像中出現(xiàn)的概率為pm,對(duì)于灰度圖像,圖像的信息熵[8]可定義為:E=∑255m=0H(pm)=-∑255m=0pmlog pm(其中pm表示整幅圖像中灰度為m像素出現(xiàn)的概率)。

根據(jù)上式算出每一個(gè)Ri塊和Di塊所對(duì)應(yīng)的信息熵,分別記為EiR和EiD。設(shè)置閾值T,對(duì)每個(gè)Ri來(lái)說,找出滿足|EiR-EjD|

2 SPIHT算法與分形相結(jié)合的圖像壓縮算法

2.1 算法的總體思路

在充分考慮小波變換后能量分布的特點(diǎn)[9],對(duì)小波變換的低頻子帶單獨(dú)進(jìn)行基于信息熵的快速分形圖像壓縮,這樣在不顯著影響重構(gòu)圖像質(zhì)量的基礎(chǔ)上,大幅度提高壓縮速度;同時(shí)考慮到小波變換后的高頻系數(shù)存在大量的零樹,且越到高分辨帶,零樹越密集。然而分形圖像編碼只是對(duì)重要系數(shù)的編碼性能較好,對(duì)于較多的零樹情況,壓縮比較低,所以對(duì)包含原圖像中豐富的細(xì)節(jié)邊緣信息的高頻系數(shù)則采用改進(jìn)的SPIHT算法,以增加重構(gòu)圖像的質(zhì)量,從而減少由分形圖像壓縮所帶來(lái)的方塊效應(yīng)。如圖1,圖2所示。

圖1 分形與改進(jìn)的SPIHT算法的圖像編碼示意圖

2.2 改進(jìn)的SPIHT 算法

SPIHT算法[10]對(duì)圖像進(jìn)行編解碼時(shí),相對(duì)于整個(gè)零樹編解碼過程,對(duì)顯著系數(shù)的排序掃描過程占用了大部分零樹編解碼過程,而且隨著量化級(jí)的逐漸精細(xì),這個(gè)對(duì)顯著系數(shù)的排序掃描過程也因?yàn)轱@著系數(shù)的增多而愈來(lái)愈長(zhǎng),因此舍去該排序過程,對(duì)House圖像進(jìn)行了分解重構(gòu),并將其結(jié)果與包含排序過程對(duì)圖像進(jìn)行分解重構(gòu)的結(jié)果進(jìn)行了比較,如表1所示。

表1 有無(wú)排序過程的重構(gòu)圖像的峰值信噪比PSNR的比較

8∶116∶132∶164∶1128∶1

有排序過程32.2229.3127.6825.7324.71

無(wú)排序過程32.1929.2827.6825.2324.71

從表1的結(jié)果可以看出,當(dāng)?shù)痛a率編碼時(shí),零樹法中有無(wú)系數(shù)排序過程對(duì)編碼結(jié)果毫無(wú)影響,而當(dāng)壓縮比較低時(shí),增加排序過程所帶來(lái)信噪比的提高也是很小的。

圖2 分形與改進(jìn)的SPIHT算法的圖像解碼示意圖

3 實(shí) 驗(yàn)

為了測(cè)試本算法的性能,選取大小256×256的House,Lena圖像進(jìn)行了壓縮實(shí)驗(yàn)。選取“Harr”小波基[8],其中小波變換的層數(shù)選為3。這樣既兼顧了保證圖像的大部分低頻部分,同時(shí)有利于分形方法的有關(guān)圖像空間結(jié)構(gòu)的分析過程。測(cè)試結(jié)果如圖3所示。實(shí)驗(yàn)數(shù)據(jù)見表2、表3。

圖3 基于分形與改進(jìn)SPIHT算法的House,Lena重構(gòu)圖像

表2 分形與改進(jìn)的SPIHT算法對(duì)House圖像的性能測(cè)試結(jié)果

算法名稱PSNRRMSEt /s

基本分形圖像壓縮25.03204.35240.86

小波域內(nèi)的分形圖像壓縮27.89105.65151.03

分形與改進(jìn)的SPIHT算法27.92105.04101.43

表3 基于分形與改進(jìn)的SPIHT算法對(duì)Lena圖像的性能測(cè)試結(jié)果

算法名稱PSNRRMSEt /s

基本分形圖像壓縮26.88133.35236.43

小波域內(nèi)的分形圖像壓縮27.97103.54146.01

分形與改進(jìn)的SPIHT算法28.4792.5598.41

以上實(shí)驗(yàn)數(shù)據(jù)表明,與小波域內(nèi)的分形圖像壓縮、基本分形圖像壓縮方法相比,分形與改進(jìn)的SPIHT算法,其結(jié)果在相同壓縮比的情況下, PSNR有一定的提高,編碼時(shí)間得以縮減。

4 結(jié) 語(yǔ)

提出一種改進(jìn)的SPIHT算法與分形相結(jié)合的圖像壓縮算法,即在進(jìn)行零樹量化之前,對(duì)低頻子帶進(jìn)行基于信息熵的快速分形圖像壓縮。這樣不僅可以使對(duì)重構(gòu)圖像起重要作用的低頻系數(shù)損失較少,而且使得在進(jìn)行零樹量化時(shí)的零樹結(jié)構(gòu)更加合理;對(duì)高頻子帶采用改進(jìn)的SPIHT算法,即舍去占用大部分零樹編碼時(shí)間對(duì)顯著系數(shù)的排序掃描過程,在不影響圖像整體壓縮比的情況下,提高了編碼效率和重構(gòu)圖像的質(zhì)量。

在保證重構(gòu)圖像質(zhì)量的前提下,該算法縮短了圖像編碼時(shí)間。在相同壓縮比的情況下,重構(gòu)圖像的峰值信噪比 PSNR 有一定的提高,因此在圖像處理領(lǐng)域具有非常廣闊的應(yīng)用前景。

參考文獻(xiàn)

[1]Shapiro J.Embedding Image Coding Using Zerotrees of Wavelet Coefficients[J].IEEE Trans.on Image Processing,1993,2(4):160-176.

[2]蔡光興,王后珍.一種圖像分形壓縮的改進(jìn)算法[J].湖北工業(yè)大學(xué)學(xué)報(bào),2006,21(1):1-3.

[3]郭京蕾,吳勇.基于分類方法的分形圖像壓縮[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(4):890-892.

[4]楊靜,崔志會(huì).小波分形混合圖像編碼[J].科技信息,2008(18):64-65.

[5]張春田,蘇育挺,張靜.數(shù)字圖像壓縮編碼[M].北京:清華大學(xué)出版社,2006.

[6]姜丹.信息論與編碼[M].合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社,2004.

[7]吳盼密.基于小波與分形的圖像壓縮技術(shù)研究[D].長(zhǎng)沙:長(zhǎng)沙理工大學(xué),2005.

[8]李天鋼,王素品,秦辰.基于信息熵窗的小波低頻子帶弱目標(biāo)圖像的增強(qiáng)[J].西安交通大學(xué)學(xué)報(bào),2006,40(2):187-190.

[9]劉文耀.小波圖像編碼與專用VISI設(shè)計(jì)[M].北京:電子工業(yè)出版社,2006.

[10]顧海明,王明翠.SPIHT算法的改進(jìn)[J].青島科技大學(xué)學(xué)報(bào):自然科學(xué)版,2008,29(2):185-188.