提升小波變換與分形結合的圖像壓縮算法

馬 俐，趙紅東，Hafiz Shehzad Ahmed，彭曉燦，韓鐵成

(河北工業大學 電子信息工程學院，天津 300401)

提升小波變換與分形結合的圖像壓縮算法

馬 俐，趙紅東，Hafiz Shehzad Ahmed，彭曉燦，韓鐵成

(河北工業大學 電子信息工程學院，天津 300401)

遙感圖像在環境監測、軍事偵察等多方面有著廣泛應用，然而遙感圖像包含信息量大，對其進行壓縮來提高存儲效率具有重要意義。傳統分形編碼由于壓縮比大的特點被廣泛應用到遙感圖像壓縮中，但是傳統分形編碼存在壓縮時間太長的問題。提出提升小波變換與改進分形結合的壓縮方法，把提升小波變換后的低頻分量進行基于最小方差搜索法的分形壓縮。實驗結果表明，提升小波變換與改進的分形結合的壓縮方法與小波變換與分形結合的壓縮方法相比，在峰值信噪比保持在35 dB不變的情況下，壓縮時間大約可以縮短8倍，圖像壓縮比也有提高。

提升小波變換；遙感圖像；分形編碼

近年來，遙感技術成為現代科學技術的重要組成部分，遙感圖像包含的信息量很大，對信道的傳輸提出更高的要求，有限的信道容量和傳輸海量遙感數據的需求之間的矛盾日益突出，對傳輸的遙感數據進行壓縮具有非常重要的價值和意義。目前，圖像壓縮處理的方法有很多種，但是由于遙感圖像包含數據量太大，一些典型的壓縮技術并不能得到滿意的效果[1-5]。而分形壓縮技術利用局部和整體的自相似性去除冗余信息可以獲得幾十到幾百倍的壓縮比。但是傳統的分形算法的缺點是運算時間較長、產生“塊效應”，人們想到在變換域進行壓縮，文獻的實驗結果表明在變換域進行分形壓縮的性能優于空間域[1,3,6]。小波變換具有能量集中、計算簡單、對邊緣信息處理強、能消除“塊效應”的優點[1]。因此，人們開始對小波變換和分形結合的方法進行研究。

在傳統的分形壓縮編碼中，值域塊的搜索占用大部分的編碼時間。最早人們主要研究如何通過改變值域塊的搜索方式來縮短壓縮時間。Zhu Lei[7]等人提出遙感圖像的分形壓縮算法，采用四叉樹搜索的方法，在保證圖像重構質量不下降的情況下，壓縮時間縮短了不到1 s。趙堅[4]等人提出基于小波變換的快速分形圖像編碼，該方法與傳統的分形壓縮編碼相比，縮短了編碼時間。宋憑[6]等人根據小波變換后系數能量分布特性，提出提升小波變換與分形相結合的圖像壓縮算法，經過提升小波變換后的低頻部分采用改進的分形圖像編碼，該方法提高了壓縮效率。Yuen C.Y.[8]等人提出四叉樹漸進式結構的非搜索分形壓縮算法，該算法提高了圖像恢復質量，但是壓縮時間沒有縮短。婁莉[9]等人提出基于分形的圖像編碼改進算法，對小波分解后的高層子圖進行基本分形編碼，該方法與傳統的分形壓縮編碼比，壓縮時間縮短約80%。李會[10]等人提出一種快速分形編碼方法，原始圖像通過被插值正交多小波分解達到縮小的效果，再利用分形編碼進行壓縮，該方法與傳統的分形編碼算法比，壓縮時間縮短約75%。以上提出的壓縮方法大多是與傳統分形壓縮編碼進行比較，而且壓縮時間縮短倍數不高。本文結合小波變換具有變換后能量主要集中在低頻部分和小波變換時間短的特性，先將原始圖像進行一次提升小波變換，然后低頻分量采用改進的搜索方法進行分形編碼。本文所提出的小波變換與改進的分形編碼結合的壓縮方法，在保證峰值信噪比基本不變的情況下，壓縮時間縮短了87%以上，壓縮比也得到一定提高。

1 提升小波變換與分形編碼的算法理論

1.1 提升小波變換

Mallat算法是二維離散小波變換使用頻率最高的方法，該算法是通過在圖像的水平方向和垂直方向交替使用低通和高通濾波器實現的[6]。這種方法運算復雜度高，計算量和存儲量都很大。提升小波變換能有效解決這一問題，被稱為第二代小波變換。在提升小波變換過程中，雙正交濾波器是在空間域形成的，不會被傅里葉變換影響。提升算法的實現流程為，現有的濾波器首先被分解成不同的模塊，然后每個模塊依次實現小波變換。分裂、預測、更新[6]是依次實現提升變換的步驟，如圖1所示。

圖1 提升小波變換示意圖

分解過程為F(Sn)=(Sn-1,dn-1)，其中F(Sn)為分解過程。預測過程主要是去除分裂過程中產生的冗余。奇數序列dn-1被偶數序列Sn-1的預測值P(Sn-1)進行預測，也就是奇信號的預測值來自偶數序列被濾波器P濾波后的值。原始信號Sn被比其小的Sn-1和dn-1代替，重復n次以后，原始信號可以表示為{Sn,dn，…，S1，d1}。更新的目的是子集更好地保持原始信號的全局特性。提升小波變換的逆變換過程為反更新、反預測和合并操作。

1.2 傳統分形圖像編碼

1.2.1 分形圖像編碼數學理論

定義1 迭代函數系統(IFS)是由完備度量空間(X,d)和一組有限的壓縮映射ωn∶X→X及其相應的壓縮因子Sn(n=1,2,…,N)組成[2]。通常迭代函數系統(IFS)表示為{X;ωn,n=1,2,…,N},壓縮因子為S=max{Sn,n=1,2,…,N}。

定理1 拼貼定理：設(X,d)是完備度量空間，設定集合L∈H(x)及正數ε。選取一個IFS{X∶ωf,j=1,2,…,n}，它的壓縮因子是s:0≤s≤1，使得

(1)

那么

(2)

式中：A是IFS的吸引子；s是壓縮因子。

定義2 反射變換：一個變換ω：Rn→Rn如果具有如下形式

(3)

式中：a,b,c,d,e,f均為實數，則ω被稱為二維仿射變換[1,11]。對于一個方塊像素塊，通常有8種變換方式，如表1所示。

表1 8種對稱變換

變換代號矩陣含義變換代號矩陣含義01001?è???÷恒等變換40110?è???÷沿Y=X軸反射1100-1?è???÷沿Y軸反射501-10?è???÷90°旋轉2-1001?è???÷沿X軸反射60-110?è???÷270°旋轉3-100-1?è???÷180°旋轉70-1-10?è???÷沿Y=-X軸反射

1.2.2 分形壓縮的基本方法

分形編碼是利用圖像本身的自相似特性[12]，構造出迭代函數系統(IFS)，根據拼貼定理尋找出每個子圖像的IFS碼[1]。就是把一個子圖像經過分形仿射變換后去逼近同一幅圖像中的其他子圖像，只需記錄仿射變換的系數，進而完成對圖像的壓縮。

(4)

1.3 改進的分形圖像壓縮

傳統分形壓縮方法中，在給值域塊尋找最佳匹配的定義域塊時，采用的搜索方法是在全局中的每個定義域塊的8種仿射變換中，通過式(4)計算每個碼本和已知值域塊的最小誤差來找出最佳匹配塊，可以得到較好的重構圖像，但是它需要很長的時間[13]。如何減少搜索時間是提高編碼效率的關鍵，也是對分形圖像壓縮算法改進的方法之一。本文在給值域塊尋找最佳匹配的定義域塊的搜索方法上進行改進，提出基于最小方差的搜索方法，把搜索方法分為2個步驟進行：

1)先計算已知值域塊與每一個定義域塊像素值的方差，再找出方差最小時所對應的定義域塊。

(5)

式中：n代表值域塊中所包含像素值的數量；ri，di分別代表值域塊和定義域塊中所含的像素值。

2)在找出的定義域塊所對應的8種仿射變換中，根據最小二乘法和式(4)找出最佳匹配的定義域塊，并記錄最佳匹配參數。

1.4 小波與改進的分形編碼結合的圖像壓縮方法

提升小波變換中利用9/7雙正交小波，該小波具有對稱性、光滑性好和壓縮性好的優點[6]。三個高頻分量和一個低頻分量可以通過把原始圖像進行一次9/7提升小波變換得到。原始圖像的大多數信息分布在低頻部分，圖像的細節和邊緣部分位于高頻分量。對低頻分量進行壓縮可以進一步減少分塊數量，從而縮短壓縮時間。將提升小波變換后的低頻分量進行改進的分形壓縮算法，具體的壓縮步驟如下：

1)將原始大小為256×256的圖像進行小波提升變換，分解成大小為128×128的4個部分。取低頻分量LL進行分形壓縮算法。

2)把LL圖像分解成大小為4×4的值域塊(記Ri),構成R塊池。相鄰R塊之間不重疊，所有R塊構成LL圖像。

3)把LL圖像分解成大小為8×8的定義域塊(記Di)，構成D塊池。相鄰D塊之間可以重疊。把每個D塊取4鄰域像素平均值，得到4×4的像素塊，再把得到的像素塊進行8種仿射變換，即得到碼本Ω。

4)對于每一個值域塊Ri，按以下步驟在碼本Ω中找出最佳匹配塊tkDi(m)。

(1)給定的一個Ri，在所有Di中找到與Ri所含像素值的方差最小的Di(m)；

(2)根據式(6)、(7)計算參數si和oi(s代表對比度，o代表亮度)，在Di(m)的8個等距變換子塊中，根據式(8)求出誤差最小的、與已知值域塊Ri最佳匹配的定義域子塊tkDi(m),即

(6)

(7)

(8)

式中：n代表值域塊中像素點個數；s,o分別代表對比度和亮度；ri,di代表值域塊和定義域塊。

5)找到每個值域塊的分形碼，即得到了分形編碼文件。

解碼步驟如下：

1)從分形編碼文件中讀出LL圖像、R塊、D塊的大小。

2)對于R塊中的每個Ri，根據分形編碼文件中的分形碼，在D中找到對應的Di，根據Ri=si·(tk(S(Di(m))))+oi·1得到所有R塊后，根據拼貼定理得到第一次迭代圖像。

3)通常情況下，迭代8～10次后，圖像不再會有明顯變化，此時得到了重構圖像。

4)對所得重構圖像結合三個高頻分量進行提升小波逆變換得到解壓縮后的原始圖像。

2 實驗分析與結論

在實驗中，分別選用張家口市陽原縣的3幅遙感圖像進行測試。所用圖像是10 m空間分辨率的多光譜數據(MUS影像)，波譜范圍分別為0.52～0.59 μm(band2)，0.63～0.69 μm(band3)，0.77～0.89 μm(band4)；對每幅圖像分別采用提升小波變換與分形結合的方法和提升小波變換與改進的分形結合的方法進行測驗，采用MATLAB7.0在內存為4 Gbyte的計算機上運行程序，所使用圖像大小為256×256，得到的結果如圖2～4、表2～4所示。

圖2 實驗運行圖像(圖像1)

圖3 實驗運行圖像(圖像2)

圖4 實驗運行圖像(圖像3)

方法運行時間/s壓縮比峰值信噪比/dB小波與分形結合118.109163.0237.101小波與改進分形結合14.366184.2337.031

表3 實驗圖像2的計算機運行結果

方法運行時間/s壓縮比峰值信噪比/dB小波與分形結合115.844106.1036.106小波與改進分形結合12.249115.8735.918

表4 實驗圖像3的計算機運行結果

方法運行時間/s壓縮比峰值信噪比/dB小波與分形結合118.375186.5341.114小波與改進分形結合14.250193.9941.078

由表2、表3、表4得到的結果看出，本文提出的提升小波變換與改進的分形結合的壓縮算法重構的圖像質量變化不大。通過對改進方法前后的壓縮時間進行分析，由圖5得出，在保證圖像壓縮前后峰值信噪比基本保持不變的情況下，本文改進的算法比傳統的小波變換與分形結合的壓縮方法的運行時間減少了87.5%，壓縮比也有所增加，具有一定的使用價值。

圖5 所用實驗圖像經過改進壓縮方法前后所用時間比

[1] 王惠溧，鄒峰嶸．基于四鄰域的分形遙感圖像壓縮[D]．長沙：中南大學，2012.

[2] 張豆豆．幾種改進的快速分形圖像壓縮算法[D]．大連：大連理工大學，2015.

[3] 鄭秋梅, 趙敏, 王風華,等. 基于不規則區域分割及灰度排序分類的分形壓縮算法[J]. 中國石油大學學報(自然科學版), 2014, 38(3):169-173.

[4] 趙堅, 俞斯樂. 基于小波變換的快速分形圖像編碼[J]. 通信學報, 1999, 20(3):85-87.

[5] DU S L,YAN Y P,MA Y D．Quantum-accelerated fractal image compression: an interdisciplinary approach[J]．IEEE ieee signal processing letters ,2014,22(4): 499-503.

[6] 宋憑, 劉波, 曹劍中,等. 提升小波變換與分形相結合的圖像壓縮[J]. 光子學報, 2006, 35(11):1784-1787.

[7] ZHU L, YANG J. Fast multi-spectral image coding algorithm based on fractal[C]//Proc. International Symposium on Intelligence Information Processing and Trusted Computing. [S.l.]：IEEE, 2010:446-449.

[8] YUEN C H, LUI O Y, WONG K W. Hybrid fractal image coding with quadtree-based progressive structure[J]. Journal of visual communication & image representation, 2013, 24(8):1328-1341.

[9] 婁莉, 劉天時. 一種基于分形的圖像編碼改進算法[J]. 微計算機信息, 2010, 26(11):206-208.

[10] 李會, 房漢雄, 朱恒軍. 基于正交多小波變換的快速分形圖像編碼[J]. 齊齊哈爾大學學報(自然科學版), 2011, 27(1):1-6.

[11] MEKHALFA F, AVANAKI M R, BERKANI D. A Lossless hybrid wavelet-fractal compression for welding radiographic images[J]. Journal of X-ray science and technology, 2016(8):610-625.

[12] 俞玉蓮. 一種改進的分形圖像壓縮算法[J]. 信息技術,2015(6):55-57.

[13] WANG X Y, ZHANG D D, WEI N. Fractal image coding algorithm using particle swarm optimization and hybrid quadtree partition scheme[J]. IET image processing, 2015, 9(2):153-161.

[14] WU M S. Genetic algorithm based on discrete wavelet transformation for fractal image compression[J]. Journal of visual communication & image representation, 2014, 25(8):1835-1841.

責任編輯：薛 京

Image compression algorithm based on combination of lifting wavelet transform and fractal

MA Li, ZHAO Hongdong, Hafiz Shehzad Ahmed, PENG Xiaocan, HAN Tiecheng

(ElectronicandInformationEngineering,HebeiUniversityofTechnology,Tianjin300401，China)

Remote sensing image is widely applied in environmental monitoring, military reconnaissance and other aspects. However, remote sensing images contain a large amount of information, it is important to improve storage efficiency. Traditional fractal coding has been widely applied to the remote sensing image compression due to the high compression ratio. But the compression time of the traditional fractal coding is too long. A compression method based on the combination of lifting wavelet transform and the fractal is proposed in this paper, making the best of the coefficients distribution, the algorithm is consisted of improved fractal coding in low-frequency of lifting wavelet transform coefficients. Experimental results show that the compression time can be shorted about 8 times, and the compression ratio is improved compared with the former unimproved method based on the peak signal to noise ratio(PSNR) is maintained at 35 dB unchanged.

lifting wavelet transform; remote sensing image; fractal coding

馬俐，趙紅東，Hafiz Shehzad Ahmed，等.提升小波變換與分形結合的圖像壓縮算法[J]. 電視技術，2017,41(2)：11-15. MA L, ZHAO H D, AHMED H S , et al.Image compression algorithm based on combination of lifting wavelet transform and fractal[J]. Video engineering，2017,41(2)：11-15.

TN919.81

A

10.16280/j.videoe.2017.02.003

河北省自然科學基金項目(F2013202256)

2016-05-20