基于分形與改進的SPIHT算法的圖像壓縮方法

張 忠,王 瑋,丁 群

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

關鍵詞:分形;小波變換;信息熵;SPIHT;圖像壓縮

中圖分類號:TN911.73文獻標識碼:A

文章編號: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 引 言

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

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

1 分形圖像編碼

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

1.1 基本分形圖像壓縮的實現過程

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

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

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

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

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

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

根據上式算出每一個Ri塊和Di塊所對應的信息熵,分別記為EiR和EiD。設置閾值T,對每個Ri來說,找出滿足|EiR-EjD|

2 SPIHT算法與分形相結合的圖像壓縮算法

2.1 算法的總體思路

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

圖1 分形與改進的SPIHT算法的圖像編碼示意圖

2.2 改進的SPIHT 算法

SPIHT算法[10]對圖像進行編解碼時,相對于整個零樹編解碼過程,對顯著系數的排序掃描過程占用了大部分零樹編解碼過程,而且隨著量化級的逐漸精細,這個對顯著系數的排序掃描過程也因為顯著系數的增多而愈來愈長,因此舍去該排序過程,對House圖像進行了分解重構,并將其結果與包含排序過程對圖像進行分解重構的結果進行了比較,如表1所示。

表1 有無排序過程的重構圖像的峰值信噪比PSNR的比較

8∶116∶132∶164∶1128∶1

有排序過程32.2229.3127.6825.7324.71

無排序過程32.1929.2827.6825.2324.71

從表1的結果可以看出,當低碼率編碼時,零樹法中有無系數排序過程對編碼結果毫無影響,而當壓縮比較低時,增加排序過程所帶來信噪比的提高也是很小的。

圖2 分形與改進的SPIHT算法的圖像解碼示意圖

3 實 驗

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

圖3 基于分形與改進SPIHT算法的House,Lena重構圖像

表2 分形與改進的SPIHT算法對House圖像的性能測試結果

算法名稱PSNRRMSEt /s

基本分形圖像壓縮25.03204.35240.86

小波域內的分形圖像壓縮27.89105.65151.03

分形與改進的SPIHT算法27.92105.04101.43

表3 基于分形與改進的SPIHT算法對Lena圖像的性能測試結果

算法名稱PSNRRMSEt /s

基本分形圖像壓縮26.88133.35236.43

小波域內的分形圖像壓縮27.97103.54146.01

分形與改進的SPIHT算法28.4792.5598.41

以上實驗數據表明,與小波域內的分形圖像壓縮、基本分形圖像壓縮方法相比,分形與改進的SPIHT算法,其結果在相同壓縮比的情況下, PSNR有一定的提高,編碼時間得以縮減。

4 結 語

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

在保證重構圖像質量的前提下,該算法縮短了圖像編碼時間。在相同壓縮比的情況下,重構圖像的峰值信噪比 PSNR 有一定的提高,因此在圖像處理領域具有非常廣闊的應用前景。

參考文獻

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

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

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

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

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

[6]姜丹.信息論與編碼[M].合肥:中國科學技術大學出版社,2004.

[7]吳盼密.基于小波與分形的圖像壓縮技術研究[D].長沙:長沙理工大學,2005.

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

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

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