適合于高分辨力航測圖像壓縮的低復雜度算法

李其虎 ，任國強，吳欽章

（1.中國科學院光電技術(shù)研究所，四川 成都 610209；2.中國科學院研究生院，北京 100149）

0 引言

隨著航天技術(shù)的飛速發(fā)展，空間飛行器的有效載荷數(shù)量、分辨率、采樣率等不斷增加，目前有限的信道傳輸和存儲能力已經(jīng)無法適應(yīng)空間航測、遙感圖像的海量數(shù)據(jù)，成為制約空間航測、遙感分辨力提高的瓶頸。因此必須對高分辨力航測、遙感圖像產(chǎn)生的數(shù)據(jù)進行實時的壓縮，以解決數(shù)據(jù)碼率傳輸、存儲和信道帶寬之間的矛盾。然而傳統(tǒng)的數(shù)據(jù)壓縮方法都存在不同程度上的局限性，如差分脈沖編碼調(diào)制（DPCM）[1]壓縮不高，矢量量化（VQ）方法的計算復雜度隨著維數(shù)的上升急劇增加，JPEG在壓縮比較高時又存在明顯的方塊效應(yīng)[2]。在傳統(tǒng)傅里葉分析基礎(chǔ)上發(fā)展起來的基于小波分析理論的多種圖像壓縮算法以其良好的時頻局域性和多分辨率分析能力而廣泛應(yīng)用于航測、遙感等圖像壓縮領(lǐng)域[3]。

目前，國內(nèi)外許多學者已經(jīng)提出了多種結(jié)合不同編碼措施的小波壓縮算法。其中改進和應(yīng)用較多的有EZW，SPIHT和EBCOT算法[4-6]。傳統(tǒng)的EZW和SPIHT在編碼時都是采取了鏈表式結(jié)構(gòu)，存儲空間較大，熵編碼采用算術(shù)編碼，計算量較大，不宜與硬件實現(xiàn)。EBCOT是當前流行的JPEG2000的核心編碼算法，雖然EBCOT編碼會產(chǎn)生較高的壓縮比、細致的碼流結(jié)構(gòu)和良好的穩(wěn)健性等諸多優(yōu)點，但是EBCOT算法是采用比特位平面算術(shù)編碼，在編碼時除對最高比特平面外，每個比特平面都要進行三通道掃描編碼。且在編碼時要為每個編碼碼塊分配一定的存儲空間，在第二級碼率截取時，又會丟失掉前一級編碼中產(chǎn)生的碼率，從而造成了巨大的資源浪費，算法復雜高，硬件實現(xiàn)困難較大。

考慮到算法的復雜度以及硬件實現(xiàn)的困難性，本文提出了一種基于提升小波變換的高分辨力航測圖像壓縮算法。通過對原始的圖像進行提升變換，依據(jù)正交小波變換的子帶變換增益對變換后的圖像系數(shù)進行最佳量化，利用圖像進行小波分解后的系數(shù)概率分布特點，對最低頻子帶LL進行一種基于上下文的預(yù)測編碼。對去除相關(guān)性的其他頻帶應(yīng)用游程編碼聯(lián)合哥倫布指數(shù)編碼進行圖像壓縮。實現(xiàn)結(jié)果表明，與目前常用的基于小波分析的圖像壓縮算法相比，本文方法在壓縮性能指標上接近JPEG2000，明顯優(yōu)于SPIHT算法。但算法復雜度遠比JPEG2000和SPIHT低，適合于硬件的高速實現(xiàn)。

1 算法簡介

圖像壓縮目的主要是去除圖像當中的諸多冗余，從而實現(xiàn)用較少的比特率來表示一幅圖像信息。通常圖像變換編碼框架主要由3部分組成，即變換、量化和熵編碼。變換主要是去除圖像像素之間的相關(guān)冗余，量化去除視覺冗余，而熵編碼是為了去除概率冗余。其中量化是實現(xiàn)數(shù)據(jù)壓縮最主要的方式，故如何對變換數(shù)據(jù)實施最佳量化就顯得至關(guān)重要（后面將會單獨介紹）。圖1給出了本文算法的流程框圖。

首先對于輸入的圖像數(shù)據(jù)進行5級二維5/3小波變換，由于圖像分辨力較大，采用5級變換可以較好地去除圖像像素之間的相關(guān)性。然后對變換后的系數(shù)進行量化，量化準則參考后面所介紹的最佳量化準則進行。為了進一步去除LL頻帶系數(shù)之間的相關(guān)性，對LL頻帶進行一種二維預(yù)測編碼方式進行編碼。而由于在其他高頻子帶量化后的系數(shù)會出現(xiàn)大量0。結(jié)合小波變換的特點，按照一定的方式進行掃描，對掃描后的系數(shù)進行自適應(yīng)游程編碼聯(lián)合哥倫布指數(shù)編碼對其他高頻子帶進行熵編碼，以較好地去除量化后像素之間的概率冗余。

2 提升小波變換與最佳量化

2.1 5/3提升小波變換

傳統(tǒng)的基于卷積的小波變換計算復雜度高，內(nèi)存需求量大，不能滿足實際工程需求。提升小波的提出很大程度上克服了這些難題。提升小波變換算法的基本思想是將Mallat算法中的每一級濾波運算分解為分裂、預(yù)測和更新三大步驟，完成對信號的分解。本文算法采用的是一種適合硬件實現(xiàn)的5/3提升小波變換。當對一副圖像進行變換時，只需對行和列進行一次提升就可以實現(xiàn)一級變換。式（1）和式（2）為5/3正向小波變換表達式

式中：Xext(n)表示對原始信號X進行對稱邊界擴展后的信號；i0，i1分別是X第一個樣本和最后一個樣本的序號。從上面2個表達式可以看出，5/3提升小波變換在變換中無須添加附加內(nèi)存，小波系數(shù)可以直接覆蓋原始數(shù)據(jù)。正反變換的提升結(jié)構(gòu)對稱、實現(xiàn)簡單、便于并行計算等優(yōu)點使得該提升結(jié)構(gòu)成為硬件實現(xiàn)的主流方法。

2.2 最佳量化準則

一般認為，同一小波子帶中各個系數(shù)值具有相同的概率分布，故對同一子帶中所有系數(shù)采用同一量化器。文獻[7]中指出小波高頻子帶系數(shù)符合廣義高斯分布。該小波系數(shù)的概率密度函數(shù)為p(x)=aexp(- ||bxr)，其中a和b是與r有關(guān)的參數(shù)，r是控制概率密度函數(shù)形狀的參數(shù)，r=2時即為高斯分布。當r=0.7時，p（x）與小波高頻子帶系數(shù)分布最為接近[8]。將問題歸一化，如果輸入數(shù)據(jù)符合方差為1的r=0.7廣義高斯分布，量化器層數(shù)為L時，帶死區(qū)的均勻量化誤差D為

式中：中Δ0為基本量化步長，通過改變Δ0可以對壓縮碼率和失真度進行調(diào)節(jié)。對于正交小波變換可以近似為Gb≈22b。結(jié)合式（6）得到5級小波變換系數(shù)最優(yōu)化量化步長如表1所示。

3 熵編碼

3.1 熵編碼結(jié)構(gòu)

由于小波變化后的圖像像素在最低頻帶仍然有著很強的相關(guān)性，故本文算法選擇對最低頻帶采用復雜度較低、準確性較高的JPEG_LS預(yù)測算法，其預(yù)測模板如圖2所示，根據(jù)預(yù)測式（7）求出Ni，j

表1 5級小波變化系數(shù)最佳量化步長

在低頻子帶中，利用預(yù)測出的 Ni，j與真實值 Ii，j進行差值計算，對殘差進行哥倫布指數(shù)編碼。具體方法為在對當前像素 Ni，j進行編碼時，首先判斷 Ni，j與 Ni，j＋1是不是相等，如果相等則進入游程編碼模式。在游程編碼模式中，對于中斷游程的像素再進行哥倫布指數(shù)編碼。而在HH，HL和LH頻帶由于小波變換的良好去相關(guān)性，這些頻帶中將會出現(xiàn)大量0區(qū)域。結(jié)合小波變換系數(shù)特點，按照圖3的掃描方式對量化系數(shù)進行自適應(yīng)游程編碼。

3.2 哥倫布指數(shù)編碼與自適應(yīng)游程編碼

指數(shù)哥倫布碼字是一種可變長的前綴碼，對經(jīng)常出現(xiàn)的數(shù)據(jù)指定較少的位數(shù)表示，對不常出現(xiàn)的數(shù)據(jù)指定較多的位數(shù)表示，故而得到的碼長不是固定的，總體來說節(jié)省了存儲空間。此外由于編碼時無需事先建立和存儲碼表，可以通過比訪問存儲碼字快的多的硬件計算產(chǎn)生碼字，故硬件實現(xiàn)起來更加簡單。正是由于哥倫布編碼的諸多優(yōu)點，其已被JVT的H.264和中國的音視頻編碼標準AVS所采用。哥倫布編碼時需要選定一個參數(shù)b，對于樣本n的碼字主要包含兩部分，n/b的整數(shù)部分一元碼字和n mod m的二進制表示。這些碼字對于呈幾何分布的整數(shù)n（即n的概率是（1-r）rn，其中0＜r＜1）是理想的。對任何這樣的幾何分布存在一個m值，使得基于它的哥倫布碼字可能的平均碼長最短。

以上所有討論的哥倫布編碼樣本都是非負的，但是由于小波變化后的系數(shù)不可能都為負數(shù)，故算法采用式（8）將量化后的小波系數(shù)value映射成非負值mvalue。

小波變換有效地去除了像素之間的相關(guān)性，使得在高頻子帶出現(xiàn)許多區(qū)域為全零，如果直接編碼樣本系數(shù)，則碼率必然大于系數(shù)的一階熵[10]，為提高編碼效率，本文在對高頻子帶編碼時，采用了自適應(yīng)游程編碼聯(lián)合哥倫布指數(shù)編碼方式。具體方式可描述如下：編碼時首先對輸入的樣本進行連續(xù)相同樣本個數(shù)統(tǒng)計，但是該統(tǒng)計只限于在一行中進行，對于統(tǒng)計后的樣本個數(shù)和樣本值進行哥倫布指數(shù)編碼。文獻[11]中實驗結(jié)果表明對于量化后的圖像小波系數(shù)，游程編碼可以有效地減少樣本個數(shù)，提高壓縮比。隨著量化步長的的增加，游程編碼后的樣本數(shù)也成倍的減少，但其信息熵幾乎不變。這樣的話，采用哥倫布指數(shù)算法對這些量化后樣本編碼就可以快速高效地實現(xiàn)圖像數(shù)據(jù)的壓縮。

4 實驗結(jié)果與分析

為了檢驗上述算法的效果，筆者在VC6.0環(huán)境下開發(fā)了編解碼仿真程序。實驗圖像大部分采用自行研制開發(fā)的航測相機外在場實驗拍攝的航測圖像（除常用測試圖像機場外）來檢驗本文算法。這些圖像包括航測圖像城市（City1，City2）、海洋（Ocean）、農(nóng)田（Farmland）、山丘（Mountain）和機場（Air station），測試圖像見圖4。圖像分辨力大小為2048×2048，深度為8 bit。并與常用的基于小波變換的SPIHT壓縮算法和最新的JPEG2000標準在壓縮性能上進行了比較。實驗結(jié)果數(shù)據(jù)采用最小二乘擬合得到3種算法的PSNR（Power Signal Noise Ratio）-壓縮比曲線如圖5所示。從實驗結(jié)果可以看出：

1）本文算法在壓縮性能上完全優(yōu)于常見的SPIHT算法，略低于JPEG2000標準。相對于JPEG2000和SPI?HT算法來說，本文算法編碼更加簡單，既沒有SPIHT算法中的3個鏈表LSP，LIP和LIS，也不需要像JPEG2000標準算法那樣為每個碼塊分配一個較大的存儲單元，這樣節(jié)省了硬件實現(xiàn)時大量的存儲容量。

2）本文算法在壓縮性能上（PSNR）稍遜于JPEG2000標準，這是因為JPEG2000采用了高復雜度的EBCOT編碼算法。該算法在編碼時對每個碼塊的每一個位平面都采用三通道掃描編碼方式。熵編碼效率要優(yōu)于本文所提算法。雖然JPEG2000的壓縮算法性能優(yōu)越，應(yīng)用較廣，但是若將其應(yīng)用到空間飛行器上則具有很大的局限性。首先，JPEG2000本身是基于最佳率失真的，內(nèi)部必然會有一些反饋操作[6]，這不利于硬件的并行實現(xiàn)；其次，它的編碼核心算法EBCOT相當復雜，采用硬件實現(xiàn)十分困難。該算法硬件實現(xiàn)的不易性導致它不可能廣泛應(yīng)用于數(shù)據(jù)量相當大的高空航測遙感領(lǐng)域數(shù)據(jù)的壓縮。

3）支持無損壓縮，如果不對變換后的小波系數(shù)進行量化，直接按照上述掃描方式進行編碼，則可以完全解碼出原始圖像，而不丟失任何信息。仿真結(jié)果表明本文無損壓縮效果要好于JPEG2000算法，和JPEG_LS算法相當。

由此可見，本文算法在算法的復雜度和壓縮性能上進行了較好的平衡。當然在壓縮性能上也明顯優(yōu)與傳統(tǒng)的一些圖像壓縮算法。

5 小結(jié)

針對航測圖像數(shù)據(jù)量龐大，難以實時存儲和傳輸?shù)膯栴}。本文提出了一種基于小波分析的低復雜圖像壓縮算法。該算法首先將圖像進行5級5/3小波變換，基于統(tǒng)計意義對變換后的圖像數(shù)據(jù)進行了最優(yōu)量化。針對低頻子帶的數(shù)據(jù)相關(guān)性，引入了JPEG_LS預(yù)測編碼。而對于高頻子帶采用了復雜度低，易于硬件實現(xiàn)的自適應(yīng)游程編碼聯(lián)合哥倫布指數(shù)編碼對量化后的數(shù)據(jù)進行編碼。本文算法具有以下優(yōu)點：1）復雜度低；2）無需建立鏈表，沒有復雜的上下文關(guān)系；3）整個算法過程中無需存儲大量數(shù)據(jù)，大大地節(jié)省了硬件實現(xiàn)的存儲器需要；4）最佳量化準則的引入使得整個算法在編碼過程中，無需涉及過多的乘法和小數(shù)運算；5）支持無損到有損的圖像壓縮，適應(yīng)范圍廣。實驗結(jié)果表明本文算法針對不同的航測圖像都具有較好的壓縮效果，從而驗證了算法的可行性，為研制高性能、高速的VLSI圖像壓縮芯片提供算法基礎(chǔ)。

[1]徐康興.低碼率場內(nèi)預(yù)測DPCM圖象編碼及其圖象質(zhì)量評價[J].電視技術(shù)，1987,11（10）：2-6.

[2]吳樂南.數(shù)據(jù)壓縮[M].2版.北京：電子工業(yè)出版社，2005.

[3]徐欣鋒，黃廉卿，徐抒巖，等.高空間分辨率遙感圖像實時壓縮進展[J].光學精密工程，2004，12（3）：266-271.

[4]SHAPIRO J M.Embedded image coding using zerotree of wavelet coeffieients[J].IEEE Transactions on Signal Proeessing，1993，42（12）：3445-3462.

[5]SAID A，PEARLMAN W A.A new fast and efficient image codec based on set partitioning in hierarchical trees[J].IEEE Transactions on Circuits and Systems for Video Technology，1996，6（6）：243-250.

[6]TAUBMAN D S，MARCELLIN M W.JPEG2000 image compression fundamentals，standards and pracyice[M].[S.l]：Kluwer Academic Publishers，2001.

[7]ANTONINI M，BARLAUD M，MATHIEU P，et al.Image coding using wavelet transform[J].IEEE Transactions on Image Processing，1992，1（2）：205-220.

[8]LAZAR D，AVERBUCH A，ISRAELI M.Image compression using vector quantization on wavelet coefficients[J].IEEE Transactions on Image Processing，1996，5（1）：4-15.

[9]譚毅華，王振華，田金文，等.率失真最優(yōu)的多分辨率小波圖像壓縮方法[J].中國圖象圖形學報，2004，8（9）：927-933.

[10]姜丹.信息論與編碼[M].合肥：中科學技術(shù)大學出版社，2004.

[11]徐勇，徐智勇，張啟衡，等.適合硬件實現(xiàn)的低復雜度圖像壓縮[J].光學精密工程，2009，9（17）：2262-2268.