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

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

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

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

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

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

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

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

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

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

1.1 提升小波變換

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

圖1 提升小波變換示意圖

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

1.2 傳統(tǒng)分形圖像編碼

1.2.1 分形圖像編碼數(shù)學(xué)理論

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

定理1 拼貼定理：設(shè)(X,d)是完備度量空間，設(shè)定集合L∈H(x)及正數(shù)ε。選取一個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均為實數(shù)，則ω被稱為二維仿射變換[1,11]。對于一個方塊像素塊，通常有8種變換方式，如表1所示。

表1 8種對稱變換

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

1.2.2 分形壓縮的基本方法

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

(4)

1.3 改進(jìn)的分形圖像壓縮

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

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

(5)

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

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

1.4 小波與改進(jìn)的分形編碼結(jié)合的圖像壓縮方法

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

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

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

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

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

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

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

(6)

(7)

(8)

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

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

解碼步驟如下：

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

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

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

4)對所得重構(gòu)圖像結(jié)合三個高頻分量進(jìn)行提升小波逆變換得到解壓縮后的原始圖像。

2 實驗分析與結(jié)論

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

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

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

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

方法運行時間/s壓縮比峰值信噪比/dB小波與分形結(jié)合118.109163.0237.101小波與改進(jìn)分形結(jié)合14.366184.2337.031

表3 實驗圖像2的計算機運行結(jié)果

方法運行時間/s壓縮比峰值信噪比/dB小波與分形結(jié)合115.844106.1036.106小波與改進(jìn)分形結(jié)合12.249115.8735.918

表4 實驗圖像3的計算機運行結(jié)果

方法運行時間/s壓縮比峰值信噪比/dB小波與分形結(jié)合118.375186.5341.114小波與改進(jìn)分形結(jié)合14.250193.9941.078

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

圖5 所用實驗圖像經(jīng)過改進(jìn)壓縮方法前后所用時間比

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

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

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

[4] 趙堅, 俞斯樂. 基于小波變換的快速分形圖像編碼[J]. 通信學(xué)報, 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] 宋憑, 劉波, 曹劍中,等. 提升小波變換與分形相結(jié)合的圖像壓縮[J]. 光子學(xué)報, 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ìn)算法[J]. 微計算機信息, 2010, 26(11):206-208.

[10] 李會, 房漢雄, 朱恒軍. 基于正交多小波變換的快速分形圖像編碼[J]. 齊齊哈爾大學(xué)學(xué)報(自然科學(xué)版), 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ìn)的分形圖像壓縮算法[J]. 信息技術(shù),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.

責(zé)任編輯：薛 京

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，等.提升小波變換與分形結(jié)合的圖像壓縮算法[J]. 電視技術(shù)，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

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

2016-05-20