基于低頻子帶列均衡的圖像稀疏表示改進算法

楊媛媛，謝 濤，陳 偉

(1.武漢理工大學 信息工程學院，湖北 武漢430070;2.南京信息工程大學 海洋科學學院，江蘇 南京210044)

隨著多媒體技術(shù)及通信技術(shù)的迅猛發(fā)展，大量圖像數(shù)據(jù)需要傳輸和處理。傳統(tǒng)壓縮都是基于奈奎斯特準則對圖像進行采樣的，因此受到了信號帶寬的限制。

2006 年，由美國科學院院士DONOHO 等提出的壓縮感知(compressed sensing，CS)理論［1-2］為數(shù)據(jù)壓縮開辟了新的道路，近幾年CS 也越來越多地用于圖像壓縮研究。在圖像壓縮感知中常用小波變換做稀疏表示，但由于其子帶分布特性，其稀疏度在列間分布不均勻，致使測量矩陣尺寸、壓縮比和恢復時間都受到制約。筆者對壓縮感知中基于小波變換的圖像信號稀疏表示方法進行了改進，提出了基于低頻子帶列均衡的圖像稀疏表示算法，并進行了實驗仿真。

1 理論基礎(chǔ)

壓縮感知技術(shù)對信號的測量是在信號進行稀疏表示后進行的，如圖1 所示，因此可以遠低于奈奎斯特準則的理論采樣率來進行采樣。壓縮感知理論最大的貢獻在于，將數(shù)據(jù)的采集和壓縮過程合二為一，避免了傳統(tǒng)理論下采集大量數(shù)據(jù)，在壓縮過程中又丟棄大量冗余數(shù)據(jù)所造成的資源浪費，大大減少了信號采集、壓縮、存儲和處理的時間和復雜度。

很多時候，待處理數(shù)據(jù)本身并不是稀疏的，因此需要對其進行稀疏表示。假設(shè)一維信號x∈RN×1，可將其用一組稀疏基Ψ={Ψ1，Ψ2，…，ΨN}進行表示，其表示形式為：

圖1 壓縮感知理論下信號處理流程

式中，αi為向量x在由Ψ 所表示的稀疏域上的投影稀疏，是N×1 的向量。若α 的取值中，非零值有k個，或者較大系數(shù)值有k個，則稱α 為k稀疏的。常用的稀疏基有小波基、DCT 基、Gabor基和冗余字典等。在測量時，用向量積對信號x進行M次測量。為保證精確重構(gòu)，M取值應(yīng)大于k而小于N。測量過程如下：式中，θ 為M×N矩陣，所得測量值y為1 ×M向量。

測量矩陣若滿足約束等距性準則(restricted isometry property，RIP)或測量矩陣和稀疏矩陣不相關(guān)，則可通過L1優(yōu)化問題求解：

目前典型恢復算法為匹配追蹤算法(matching pursuit，MP)［3］，正交匹配追蹤算法(orthogonal matching pursuit，OMP)［4］，正則正交匹配追蹤算法(regularized orthogonal matching pursuit，ROMP)［5］和壓縮采樣匹配追蹤算法(compressive sampling matching pursuit，CoSaMP)［6］等。

2 基于小波變換的圖像壓縮感知

一直以來在圖像壓縮領(lǐng)域中，各標準多采用離散余弦變換(discrete cosine transform，DCT)。其主要問題在于必須對圖像進行分塊處理，這會引起“方塊效應(yīng)”［7］。近10 年來，小波變換作為一種新興的變換技術(shù)得到了迅速發(fā)展，在圖像壓縮領(lǐng)域，離散小波變換(discrete wavelet transform，DWT)已成為主流變換方法之一。

DWT 對圖像進行處理，實際是對圖像在小波域進行分解。首先構(gòu)造尺度函數(shù)和小波函數(shù)，它們分別具有低通和高通濾波作用，由其組成的正交鏡像濾波器可將圖像分解為高頻子帶和低頻子帶。早期DWT 變換只局限在一層，即先在水平方向進行低通濾波，再在垂直方向進行高通濾波，然后按濾波結(jié)果將信號元素重新排列，圖2 所示為一層小波變換后的子帶分布情況。

圖2 一層小波分解子帶分布圖

其中，LL 子帶包含更多圖像中的低頻信號，HL 子帶包含更多垂直方向的高頻信息，LH 子帶包含更多水平方向的高頻信息，HH 包含更多對角線方向的高頻信息?；谛〔ㄗ儞Q的圖像壓縮感知原理框圖如圖3 所示。

圖3 基于小波變換的圖像壓縮感知原理框圖

首先采用DWT 對圖像進行小波分解，然后將其分解系數(shù)進行CS 壓縮，解壓部分用重構(gòu)算法恢復出小波域系數(shù)后，再進行小波合成，即可恢復出原圖像。

如果對一層小波分解后的系數(shù)進行CS 壓縮，幾乎恢復不出原圖像，這是因為將LL 子帶系數(shù)一起壓縮，破壞了LL 系數(shù)的相關(guān)性。因此有學者提出只對LH、HL 和HH 子帶進行CS 壓縮，LL 則用原數(shù)據(jù)進行傳輸?shù)姆椒ǎ?-9］。但該方法對數(shù)據(jù)的壓縮比不高。

考慮到LL 部分仍存在稀疏性，可將LL 部分進一步做小波分解。圖4 所示為四層小波分解子帶分布圖，進一步將低頻信號往左上角搬移，保證LL 子帶系數(shù)盡可能不稀疏，并且經(jīng)過四層小波分解后，LL 子帶系數(shù)間的相關(guān)性變?nèi)?，因此可對所有子帶系?shù)統(tǒng)一進行CS 壓縮，重構(gòu)后仍能得到理想效果。

圖4 四層小波分解子帶分布圖

3 基于小波域低頻均衡稀疏表示的圖像壓縮感知

通過壓縮感知，可以從M個測量值中還原出原始數(shù)據(jù)的N個值(M＜N)，這種壓縮的前提條件是這N個值本身是可壓縮的，或者說是稀疏的。假設(shè)x的稀疏度為k，為了恢復出這k個數(shù)據(jù)，M的值應(yīng)該大于k，且如果k增大，M值也必須增大，k減小，M值也相應(yīng)減小。以四層小波變換為例，在極限情況下，假設(shè)所有非零系數(shù)都集中在LL4，則其所在的前N/24列的稀疏度為N/24，后N-N/24列的稀疏度為0。則M應(yīng)大于N/24，壓縮比小于24：1。M值對應(yīng)的是測量矩陣的行數(shù)，故測量矩陣應(yīng)有N/24行。但實際上后N-N/24列稀疏度很低，不需要這么多行的測量矩陣對其進行測量，因此限制了壓縮比的提升。并且在重構(gòu)數(shù)據(jù)時，以O(shè)MP 算法為例，它是對測量后得到的矩陣進行逐列恢復，由于前幾列k值較大，所需迭代次數(shù)較多，每次迭代，選擇的原子就多一列，矩陣變大。即在恢復前幾列時矩陣就已經(jīng)很大了，而每次迭代都要進行矩陣的最小二乘法運算，這樣即使后面列的k很小，所需迭代次數(shù)很少，但矩陣已經(jīng)很大了，因此總體運算量很大。

筆者提出一種改進算法，對低頻子帶進行列均衡，將LL4 中的大值系數(shù)均分到每一列的頂端，而各層HL 和HH 子帶保持不變。由于經(jīng)過四層小波分解后，降低了低頻子帶系數(shù)間的相關(guān)性，因此在將該部分系數(shù)均分到每一列后，再對全部小波系數(shù)進行壓縮感知，也可獲得較高的壓縮比和較好的重構(gòu)質(zhì)量。由于優(yōu)化后降低了前面LL4 子塊對應(yīng)列的稀疏度，因此在測量時，可以將測量矩陣的M值設(shè)置得更小，以獲取更高的壓縮比，在同等壓縮比的基礎(chǔ)上，獲得更高的圖像質(zhì)量。由于OMP 恢復算法是逐列重構(gòu)數(shù)據(jù)，故可減少LL4 子塊對應(yīng)列重構(gòu)時的迭代次數(shù)，減小恢復這些列所產(chǎn)生的恢復矩陣的大小，抑制計算量的激增，減少運算時間。

假設(shè)待處理圖像為N×N大小，則經(jīng)過四層小波分解后，LL4子帶大小為假設(shè)LL4子帶是完全不稀疏的，將其均分到每一列，則在這種理想情況下每一列的稀疏度都變?yōu)椋?/p>

在非理想情況下，LL4 子帶也有一定稀疏性，但相對于各層LH 子帶來說，其稀疏度明顯要高出很多。通過優(yōu)化，同樣可使LL4 對應(yīng)列的稀疏度變低，其具體均衡方法如圖5 所示，其中陰影部分表示大值系數(shù)。

圖5 四層小波變換低頻子帶列均衡原理圖

具體操作步驟如下：

(1)將LL4 的低頻分量進行上下分塊，將其下半部分數(shù)據(jù)與LH4 的上半部分數(shù)據(jù)對調(diào)，形成新的低頻子帶，大小為

(2)將步驟(1)得到的低頻子帶再進行上下分塊，將其下半部分數(shù)據(jù)與LH3 的上半部分數(shù)據(jù)對調(diào)，形成新的低頻子帶，大小為

(3)將步驟(2)得到的低頻子帶再進行上下分塊，將其下半部分數(shù)據(jù)與LH2 的上半部分數(shù)據(jù)對調(diào)，形成新的低頻子帶，大小為

(4)將步驟(3)得到的低頻子帶再進行上下分塊，將其下半部分數(shù)據(jù)與LH1 的上半部分數(shù)據(jù)對調(diào)，形成新的低頻子帶，大小為即均勻分布到每一列。

上述方法既實現(xiàn)了低頻子帶列均衡，也方便了之后對全部小波系數(shù)進行CS 壓縮和OMP 重構(gòu)。重構(gòu)后的數(shù)據(jù)按照之前的均衡步驟進行反變換，再進行小波合成，即可還原出原始圖像。將該方法用于圖像壓縮感知時的具體流程如圖6 所示。

圖6 基于低頻子帶列均衡的圖像壓縮感知原理框圖

通過優(yōu)化，在設(shè)計測量矩陣時即可將M取更小的值且獲得更大的壓縮比。在同樣的壓縮比下，由于M遠大于每列的k值，因此可獲得更好的恢復效果。由于每列的k值很平均且很小，在恢復算法中，前幾列的迭代次數(shù)較少，矩陣擴大的速度較低，因此整體運算量會顯著下降。

4 仿真結(jié)果

4.1 峰值信噪比對比

采用256 ×256 大小的Lena 圖像作為原始圖像，對圖像進行四層小波變換，測量矩陣采用高斯隨機矩陣，用OMP 算法進行圖像重構(gòu)，對傳統(tǒng)四層小波變換圖像壓縮感知和小波域低頻均衡圖像壓縮感知進行了仿真和結(jié)果對比。

分別取M值為32、64、96、128 和164，比較兩種算法的峰值信噪比(peak signal to noise ratio，PSNR)，結(jié)果如表1 所示。

表1 傳統(tǒng)算法與優(yōu)化算法PSNR 對比

由仿真數(shù)據(jù)可知，優(yōu)化算法明顯比傳統(tǒng)算法的PSNR要高，特別是在采樣率較低的情況下，傳統(tǒng)算法性能會出現(xiàn)嚴重惡化，而優(yōu)化算法在這種情況下可大幅提高PSNR，這與之前理論分析是相符的。

4.2 重構(gòu)時間對比

分別取M值為32、64、96、128 和164，比較兩種算法的重構(gòu)時間，其結(jié)果如圖7 所示。

圖7 兩種算法重構(gòu)時間對比圖

由圖7 可見，隨著采樣率的增大，改進算法的運行速度相比原始算法越來越快。采樣率低時，迭代次數(shù)很少，區(qū)別不大。隨著采樣率增加，低頻均衡效果越來越明顯，其前面列向量的恢復所需迭代次數(shù)明顯少于傳統(tǒng)算法，矩陣擴充速度減緩，因此整體運算速度大大加快。

4.3 小波域及空域圖像對比

經(jīng)過四層小波分解，得到小波域圖像。其左上角有一亮塊，對應(yīng)LL4 中密集的低頻分量。經(jīng)優(yōu)化處理后，該部分低頻分量在列方向上的分布趨于均勻，在小波域圖像中表現(xiàn)為亮塊消失，分散于各列頂端。

對比M=64 時兩種算法所得空域圖像，如圖8 所示。此時壓縮比已經(jīng)達到了4：1，圖8(b)經(jīng)過優(yōu)化算法可以恢復出大致圖像，而圖8(a)采用傳統(tǒng)算法，幾乎不能恢復。這說明在處理大幅圖像信息時，可采用該算法，以較高的采樣率獲得較好的恢復效果。

5 結(jié)論

筆者介紹了壓縮感知和稀疏表示的基本理論，對于現(xiàn)有的小波域圖像稀疏表示及其在壓縮感知中的應(yīng)用和存在問題進行了分析。根據(jù)小波分解系數(shù)的分布特點，提出了小波域低頻均衡的圖像稀疏表示改進算法，通過將低頻子帶均分到每一列，降低前面列的稀疏度。將其應(yīng)用于壓縮感知，則可減小測量矩陣大小，提高壓縮比，降低恢復時間，或在同樣的壓縮比下提高圖像恢復質(zhì)量。在不同壓縮比下對傳統(tǒng)算法和優(yōu)化算法進行了仿真對比，結(jié)果顯示該算法與傳統(tǒng)基于小波變換的壓縮感知算法相比，在恢復效果和節(jié)省運算時間上均有一定程度的改善。

圖8 M=64 時恢復空域圖像對比

［1］DONOHO D. Compressed sensing［J］. IEEE Transactions on Information Theory，2006，52(4)：1289-1306.

［2］CANDES E. Compressive sampling［C］∥Proceedings of the International Congress of Mathematicians. Madrid：［s.n.］，2006：1433 -1452.

［3］MALLAT S，ZHANG Z. Matching pursuit in a time -frequency dictionary［J］. IEEE Trans Signal Processing，1993，41(12)：3397 -3415.

［4］TROPP J，GILBERT A. Signal recovery from random measurements via orthogonal matching pursuit ［J］.IEEE Trans Inform Theory，2007，53(12)：4655-4666.

［5］NEEDELL D，VERSHYNIN R. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit［J］. Found Comput Math，2009，9(3)：317-334.

［6］NEEDELL D，TROPP J A. CoSaMP：iterative signal recovery from incomplete and inaccurate samples［J］.Applied and Computational Harmonic Analysis，2008，26(3)：301 -321.

［7］CHEN J L，YANG J. Improved image coding algorithm based on embeded zerotree wavelet［J］. Image and Signal Processing，2009，9(2)：1 -4.

［8］張礪佳. 基于小波變換的圖像壓縮編碼研究［D］.北京：中國科學院研究生院，2007.

［9］CEN Y G，CHEN X F，CEN L H，et al. Compressed sensing based on the single layer wavelet transform for image processing［J］. Journal on Communications，2010，31(8A)：52 -55.