壓縮感知的自適應冗余字典及其圖像恢復方法研究*

蔣業(yè)文,于昕梅

(佛山科學技術學院電子與信息工程學院，廣東 佛山 528000)

壓縮感知(CS，Compressed Sensing)的稀疏信號表示理論通常基于正交線性變換, 但許多信號是各種自然現(xiàn)象的混合體, 這些混合信號在單一的正交基變換中不能非常有效地表現(xiàn)出來。例如, 一個含有脈沖和正弦波形的混合信號, 既不能用單一的脈沖基函數(shù), 也不能用單一的正弦基函數(shù)有效地表示。為此，CS理論采用一種新的信號稀疏表示技術，稱為冗余字典，來表示這類混合信號。其基函數(shù)用稱之為字典的超完備的冗余函數(shù)系統(tǒng)取代, 字典的選擇盡可能好地符合被逼近信號的結構, 其構成可以沒有任何限制, 字典中的元素被稱為原子。從字典中通過測量矩陣找到具有最佳線性組合的m項原子來表示一個信號, 稱作信號的稀疏逼近或高度非線性逼近。

CS理論的三個組成要素是信號的稀疏變換(目前的稀疏變換有離散余弦變換DCT,小波Wavelet，Curvelet，過完備原子分解(Overcomplete atom Decomposition)等)；稀疏信號的非相干測量及稀疏信號的重建算法[1]。CS主要思想是對一類具有稀疏先驗的信號，先經(jīng)小部分非線性測量矩陣進行采樣，其包含足夠信息良好逼近信號，再通過一定類型的線性或非線性解碼機制就可高概率精確重建原始信號。信號稀疏表示的一個關鍵問題就是如何設計有效的冗余字典[2]。當前已有小波包、小波和正弦函數(shù)的級聯(lián)、局部余弦等多種冗余字典，但它們不總能保證信號的稀疏性[3]。文獻[4]選取可分離Gabor函數(shù)作為語音原子庫，但離散Gabor函數(shù)中多個時頻參數(shù)所得的原子數(shù)量巨大，增加了復雜度。近兩年，通過學習、訓練來獲得冗余字典的方法也得到了發(fā)展，如文獻[5]將聚類法用于圖像字典學習；Aharon等[6]將K均值聚類法推廣為K-SVD，自適應更新字典。但這些方法需通過訓練大量樣本來更新字典，計算量和存儲空間巨大。

本文在研究稀疏表示的基礎上，力圖通過研究冗余字典尋找圖像的一種最有效的稀疏表示及其重構圖像的算法。

1 相關知識

(1)

而對于全局RIP常數(shù)則為

(2)

基于上述理論及其條件，本文主要解決的問題是，當信號不能用正交基稀疏表示時，采用冗余字典D∈Rn×k表示，并在滿足RIP要求下如何選擇合適的測量矩陣Φ∈Rn×d使傳感系統(tǒng)矩陣ΦΨT具有更少的非零值[11]，同時運用迭代閾值算法概率恢復原始的信號。也就是說，如何從字典中D中找到具有最佳線性組合的m項原子來表示一個信號, 實現(xiàn)信號的稀疏逼近或高度非線性逼近。

2 冗余字典的構造

從非線性逼近的角度來講, 高度非線性逼近包含兩個層面: 一是根據(jù)目標函數(shù)從一個給定的基庫中挑選好的或最好的基; 二是從這個好的基中揀選最好的m項組合。利用貪婪算法和凸優(yōu)化自適應追蹤, 從一個冗余函數(shù)系統(tǒng)中進行m項逼近或閾值逼近也屬此例。下面我們從非相干字典與RIP界定方法出發(fā)，研究冗余字典的構造問題。

2.1 非相干字典

要想在冗余字典中獲得高度非線性逼近的建設性結果, 我們必須首先將注意力集中在某些特別的字典上[12]。許多研究人員瞄準了非相干字典, 也就是說相干系數(shù)μ小于某個常數(shù)的字典。相干系數(shù)的定義為

(3)

當相干系數(shù)較大時, 原子間的相互關聯(lián)也較強。如果μ= 1, 則意味著字典中至少包含了兩個一模一樣的原子。反之, 當相干系數(shù)較小時, 我們就稱字典是非相干的, 正交基的相干系數(shù)為零。相干系數(shù)為字典的冗余性提供了另一種可能的測度手段。(3)式說明當μ充分小時, 字典D(雖然可能是超完備的)接近一個正交基。

2.2 RIP界定問題

為了實現(xiàn)最佳的逼近并重構稀疏信號，Candes和Tao給出并證明了傳感矩陣ΦΨT必須滿足限制等容性條件RIP[2]。Baraniuk在文獻[13]中給出RIP的等價條件是測量矩陣Φ和稀疏表示的基Ψ不相關, 即要求Φ的行φj不能由Ψ的列ψi稀疏表示, 且Ψ的列ψi不能由Φ的行φj稀疏表示。滿足RIP條件的測量矩陣有高斯隨機矩陣、貝努利矩陣、一致球測量矩陣、二值隨機矩陣、局部哈達瑪矩陣以及托普利茲(Toeplitz)矩陣等。對于大小為n×d的隨機矩陣Φ，其滿足的條件是[14]：

ε∈(0,1/3)

(4)

其中，P表示Φ滿足的條件概率，ε為信號的殘差。常數(shù)c>0，任意υ∈Rd。設D∈Rd×K為大小為K的字典，具有限制性等容常數(shù)δS(D),S∈N。對于滿足(4)式的隨機測量矩陣Φ∈Rn×d，當測量次數(shù)為[15]

n≥Cδ-2(Slog(K/S)+log(2e(1+12/δ))+t),

常數(shù)C≤9/c,δ∈(0,1),t>0

(5)

則傳感系統(tǒng)矩陣ΦD具有限制等容性常數(shù)：

δS(ΦD)≤δS(D)+δ(1+δS(D))

(6)

對于固定的δ和計數(shù)器t，測量次數(shù)可以更精確地通過字典大小K和稀疏度S表示為

(7)

2.3 正交DCT基冗余字典

δS≤μ1(S-1)≤(S-1)μ

(8)

2.4 規(guī)范正交基(Dirac基)和DCT基組成的自適應冗余字典

通常一種正交基只能對某一種類型信號的特征存在稀疏表示。為此，本文根據(jù)規(guī)范正交基(Dirac基)和DCT基的表示性質，結合兩個正交基組成一種組合變換稀疏表示方法，并通過Dirac基和DCT基構成自適應字典，實現(xiàn)信號的稀疏表示。

n≥C1(4S(2plog 2-logS)+C2+t)

(9)

如果信號僅在Dirac(Canonical Basis)基下稀疏，則測量次數(shù)為：

(10)

據(jù)此，利用Dirac基和DCT基構成自適應字典算法如下：

1)求出Dirac基向量在DCT正交基的展開系數(shù)(即基向量之間的內積)；求出S在兩個正交基的展開系數(shù)(S與基向量的內積)并確定絕對值最大的基向量作為匹配原子。

2)利用Dirac基向量在DCT正交基的展開系數(shù)快速確定殘余信號在各正交基中的展開系數(shù)，并確定其絕對值最大的基向量作為匹配原子。

以此類推得到S的稀疏表示。

2.5 基于圖像分塊的自適應冗余字典

為了說明本文提出的冗余字典有效性，我們以圖像采樣與重構作為輸入條件，在不影響重構圖像質量的前提下降低采樣率，提出了分塊自適應采樣的方法。首先利用高斯隨機投影矩陣對圖像塊進行隨機投影，再根據(jù)觀測向量的能量大小將觀測向量分為平滑和非平滑兩部分。由于平滑圖像塊和非平滑圖像塊的結構特征不同，因此本文對平滑塊和非平滑塊重構時選用不同的字典。將自然圖像庫中的圖像塊按其方向性從0°到180°共分為12類，每類數(shù)據(jù)分別用K-SVD(K-SingularValueDecomposition)方法訓練一類字典，每類字典包括64個原子，另外再加上正交DCT字典一共形成包括832個原子的冗余字典。正交DCT字典可以表示圖像塊中的各向同性特征，而規(guī)范正交基字典可以表示圖像中的角度，因此，我們用規(guī)范正交基冗余字典對非平滑圖像塊進行重構。平滑圖像塊的結構特征比較簡單，用正交DCT字典就可以表示它的各向同性特征，因此對平滑圖像塊重構時使用正交DCT字典。

圖1 正交DCT和自適應冗余字典原子,字典原子大小為8*8

3 實驗結果

圖2 基于DCT字典和自適應冗余字典的圖像處理(Ⅰ)

圖3 基于DCT字典和自適應冗余字典的圖像處理(Ⅱ)

由圖2、3可見，在充分測量次數(shù)下，兩種字典算法均可高概率恢復信號。但在測量次數(shù)一定時，由重構圖像的峰值信噪比(PSNR)可見，本文提出的Dirac基和DCT基組成的自適應冗余字典具有更好的圖像恢復效果。

5 總結和展望

通過分析CS理論信號的稀疏性和RIP條件，深入研究了一個正交DCT基以及Dirac基和DCT基構成的組合基冗余字典，確定了隨機測量矩陣對信號測量次數(shù)的要求，以及測量次數(shù)與字典大小、信號稀疏度的關系。在此基礎上，通過對圖像按照能量進行分塊，并結合迭代硬閾值重構算法，提出了一種自適應冗余字典的實現(xiàn)應用方法。實驗結果證明了自適應冗余字典的有效性。我們進一步地研究方向是，結合冗余字典，尋找更優(yōu)的測量矩陣，發(fā)展更有效和低復雜度的圖像/視頻壓縮感知系統(tǒng)及其信號的重構算法。

參考文獻：

[1] DONOHO D．Compressed sensing[J]．IEEEE Trans Inform Theory，2006，51(4)：1289-1306．

[2] CANDES E，ROMBERG J，TAO T．Robust uncertainty principles：Exact signal reconstruction from highly incomplete frequency information[J]．IEEE Trans Inform ，2006，52(2)：489-509．

[3] 孫玉寶, 肖亮. 基于Gabor感知多成份字典的圖像稀疏表示算法研究[J]. 自動化學報, 2008, 34(11): 1379-1386.

[4] 井愛雯, 劉云. 基于MP算法的語音信號稀疏分解[J]. 計算機工程與應用, 2009, 45(5): 144-146.

[5] RUBINSTEIN R，ELAD M. Double sparsity: learning sparse dictionaries for sparse signal approximation[J]. IEEE Transactions on Signal Processing, 2010, 58(3): 1553-1564.

[6] AHARON M, ELAD M,BRUCKSTEIN A M. The K-SVD: an algorithm for designing of overcomplete dictionaries forsparse representation[J]. IEEE Transactions on Signal Processing, 2006, 54(11): 4311-4322.

[7] RUDELSON M, VERSHYNIN R. Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements[C]∥Proc CISS 2006 (40th Annual Conference on Information Sciences and Systems), 2006.

[8] KIM S J，KOH K，LUSTIG M，et al．A interiorpoint method for large-scale L1-regularized least-squares problems with applications in signal processing and statistics[J]．Journal of Machine Learning Research，2007，7(8)：1519-1555．

[9] TROPP J，GILBERT A．Signal recovery from random measurements via orthogonal matching pursuit[J]．IEEE Tram Inform Theory，2007，53(12)：4655-4666．

[10] 楊海蓉，張成，丁大為，等. 壓縮傳感理論與重構算法[J].電子學報，2011，39(1)：142-148.

[11] RAUHUT H, SCHNASS K, VANDERGHEYNST P. Compressed sensing and redundant dictionaries[J]. IEEE Transactions on Information Theory, 2008, 54(5): 2210-2219.

[12] CHEN S, DONOHO D, SAUNDERS M. Atomic decomposition by basis pursuit[J]. SIAMJ Science Computer, 1999, 20: 33～61.

[13] BARANIUK R G. Compressive sensing[J]. IEEE Signal Processing Magazine, 2007, 24(4): 118-121.

[14] NEEDELL D，VERSHYNIN R．Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J]．Found Comput Math, 2009，9(3)：317-334．

[15] 趙慧民，郭一縝,丁曉艷，等.用于視頻多播傳輸?shù)膲嚎s傳感實現(xiàn)方法研究[J].中山大學學報：自然科學版,2012,51(1): 45-49.

[16] 練秋生，周婷. 結合字典稀疏表示和非局部相似性的自適應壓縮成像算法[J].電子學報，2012，40(7): 1416-1422.

[17] BLUMENSATH T, DAVIES M E. Iterative thresholding for sparse approximations[J]. Journal of Fourier Analysis and Applications, 2008, 14(5/6): 629-654.