壓縮感知理論及重建方法

劉 蕾，李建東，閆敬文*

（1.汕頭大學醫學院，廣東 汕頭 515063；2.汕頭大學工學院電子系，廣東 汕頭 515063）

0 引言

隨著各類醫療成像、高清遙感、視頻監控等技術的飛速發展及應用，現代化成像和信息技術獲取數據的能力得到不斷地增強，大體積高維度的海量數據使得我們急需提高快速處理數據的能力.傳統的數據獲取模式要求信號的采集頻率必須大于或等于信號帶寬兩倍，才能精確恢復原信號.按照傳統信號采集模式，采集后的信號需先儲存再壓縮傳輸，這將導致大量的冗余數據被保留下來，增大采樣硬件成本，且大量的采集數據在壓縮中被拋棄，大大降低了采樣效率和硬件的利用效率，極大限制了高效信號處理的要求.傳統信號獲取方式的缺陷促使學者們不斷研究新的信號獲取方法.2006年，論文“Compressed Sensing”的發表標志著CS理論框架正式被提出[1].Donoho等研究者指出，針對稀疏或可壓縮信號，可以采用非線性采樣，在采樣的同時對數據進行壓縮，提高傳感器的采樣效率，同時也避免大量冗余數據被保留而占用有限的儲存資源[1-2].由于壓縮感知理論運用非相關測量矩陣進行壓縮采樣，其采樣頻率可遠低于奈奎斯特頻率，再按照非線性優化的重構算法，把復雜的恢復計算部分交給數據還原的這一端來做，精確重構原始信號[1-3].圖1給出了傳統數據傳輸與CS數據傳輸的區別示意圖.

圖1 傳統數據傳輸和CS數據傳輸.

1 壓縮感知的理論框架基礎

基于壓縮感知非相關矩陣獲取的投影測量值的數據量遠遠小于傳統采樣方法所獲的數據量，這不僅突破了采樣定理對精確重構信號時采樣頻率的限制，而且提高了數據采集端的采樣、儲存及傳輸效率[2-3].尤其是針對搭載在飛機或衛星上的傳感器采集系統而言，壓縮感知理論減少了大量數據的存儲空間，提高了的傳輸效率和傳感器的利用效率.壓縮感知理論指出，信號或圖像精確重建必須滿足以下三個條件[4]：

（1）稀疏性，即在某種變換域下信號或圖像可被稀疏表示；

（2）測量矩陣滿足限制等容性準則（Restricted Isometry Property，RIP）條件，即要滿足與信號本身是互不相干的；

（3）通過非線性優化的重建模型精確重建.

1.1 壓縮感知重建的基本知識

1.1.1 稀疏信號及信號的稀疏表示

稀疏信號是指信號中只有少數元素是非零的[2].根據壓縮感知理論，圖像的重建誤差界是由稀疏逼近誤差決定的[5].對于任一信號x∈Rn，令是滿足壓縮感知條件的解，ΨT表示正變換，則ΨTx表示信號x在變換域ΨT下的稀疏表示，我們僅保留s個最大系數即可得到x在變換域ΨT下稀疏逼近表示，用（ΨTx）s表示，則重建誤差可由公式（1）給出：

其中C0，C1是很小的正數，ε表示噪聲水平[6].公式（1）顯示更加稀疏的表示可以降低重建誤差，因此稀疏性對提高信號或圖像重建質量起著關鍵作用.

鑒于我們通常獲取的自然信號或圖像都是非稀疏的，因此稀疏性的核心思想是尋找Parseval框架一組基或緊框架下的冗余字典（Ψ＝{Ψm}m），使得信號或圖像在該組基或字典上的投影只存在少數幾個大的分量，其他的分量都為零（稀疏的）或者接近零（可壓縮的）[6].常見的稀疏表示方法有傅里葉變換[7]、離散余弦變換DCT、小波變換[7]以及多尺度幾何分析、稀疏字典表示[8]等.典型的多尺度幾何分析方法包括Meyer和Coifman提出的 Brushlet變換[9]，Candès提出的緊框架 Ridgelet變換[10]和 Curvelet變換[11]，Do 提出的緊框架Contourlet變換[12-13]和Labate提出的Shearlet變換[14-15]，Lu和Do[16]提了緊框架Surfacelet變換等.尤其是針對高維數據，圖像的邊界面通常是曲面奇異的[16]，多尺度幾何分析能夠更好地捕捉高維信號的曲面奇異性，比固定方向的變換有更好的稀疏表示的性質.

1.1.2 測量矩陣及不相干性

采樣矩陣和稀疏變換基之間的不相干性是壓縮感知理論成立的另一重要特點.不相關性是指壓縮感知編碼矩陣的列向量必須在相應的稀疏基上擴散[3].如果用A表示采樣矩陣Φ和稀疏變換基Ψ的乘積，若A滿足限制等容性準則（Restricted Isometry Property，RIP）條件才能保證信號成功重建[5].互相干性（mutual-coherence）提供任意兩個列向量之間相似性的最大值[17]，這是一種最壞的情況，因為兩個相似的列向量會混淆所有基追蹤算法（pursuit algorithm）[18].但是，互相干性沒有真正反映稀疏表示行為和基追蹤算法的性能.互相干性系數設為，對此，Elad提出使用平均相干性（t-averaged mutual coherence），先計算任意兩列歸一化內積，平均相干性定義為大于閾值t的所有內積的平均值，它能更好地反映稀疏表示行為和基追蹤算法的性能.常見的能使A滿足約束等距性的測量矩陣包括Gaussian矩陣[19]，局部傅立葉矩陣[20]、二值隨機矩陣[21]、局部哈達瑪矩陣[22]、一致球矩陣[23]以及托普利茲（Toeplitz）矩陣[24]等.

1.2 壓縮感知的稀疏重建模型

Candès等人證明若要精確重建原信號，可以通過求解最小l0范數的優化問題加以解決，基于壓縮感知理論的重建模型可以寫成如下的表達式[25]：

除了利用圖像在變換域的稀疏性進行的最小l1范數的稀疏重建外，圖像還可利用梯度的稀疏性進行稀疏重建，此時的稀疏重建模型轉化為最小TV求解：

1.3 壓縮感知的低秩重建模型

矩陣的低秩性是指矩陣的秩小于矩陣的行數或列數.基于此，研究人員將一維信號的最小化向量的范數擴展成二維矩陣的秩，創造出矩陣的低秩重建算法.

一個二維圖形對應一個矩陣，令xi代表第i個位置處的向量，使用K近鄰算法搜索出其第 i個位置處的 k 個相似向量，共同組成向量，由于Xi是由相似向量組成的，因此它有低秩特性.同時Xi又含有噪聲，所以對二維圖形建立模型Xi＝Li＋Ni，Ni代表高斯白噪聲矩陣，Li代表低秩矩陣，秩最小化優化模型[27]如下：

通常情況下，這個壓縮傳感重建問題的模型可以寫成：

其中 L（Li，ε）是奇異值的對數和.

圖2 不同函數對秩的逼近效果

擴展到三維數據的重建問題涉及到三維張量.建立起相應的重建模型之后，先對張量進行CP分解或者Tucker分解，使之變成二階矩陣，進而依靠矩陣的恢復算法進行重構.以CP分解為例，三維的圖像重建可以建立如下的模型：

1.4 壓縮感知深度網絡模型

近年來，隨著神經網絡和深度學習的快速發展，部分研究者借助神經網絡結構構建了基于深度網絡的壓縮感知模型，西安交通大學構建的ADMM-CSNet[28-29]模型和北京大學的ISTA-Net[29]模型是兩個典型的模型.這兩個模型都是針對圖像壓縮感知重建設計的，本質上仍然是求解一個l1范數稀疏重建問題，求解模型[28]如下：

其中Dl表示某種稀疏或濾波變換，g（·）表示正則化函數，代表正則化參數，L是可能的分組信息.與傳統壓縮感知算法不同，這些參數在壓縮感知網絡模型中不需要提前設置，網絡模型會計算出最優參數，且迭代次數遠小于常規壓縮感知的迭代算法[29-30].除此以外，Kuldeep等研究者提出了一種基于卷積神經網絡結構的非迭代壓縮感知快速重建算法ReconNet，它以圖像的壓縮感知隨機測量值作為輸入返回重建圖像塊[31].Mousavi[32]和Iliadis[33]結合分塊壓縮感知和全連接神經網絡給出了全連接視頻壓縮感知模型.基于網絡結構的壓縮感知模型儼然成為了壓縮感知重建的發展新方向.

2 壓縮感知重建算法

重構算法一直以來是壓縮感知理論實現的重點和難點.本文分別介紹稀疏重建模型和低秩重建模型兩種不同模型下的各類重建方法.

2.1 稀疏信號的重建算法

2.1.1 凸優化算法

在稀疏重建模型中，Candès指出可以把復雜性和不穩定性較高的l0范數最優化問題轉化為等價的l1范數最優化問題，通過不斷尋找l1范數最小的來逼近我們壓縮采樣得到的信號y，當l1范數不再減少時，方程組求解成功.這種思路就引出了著名的基追蹤方法（Basis Pursuit，BP），其計算復雜度為O（N3）[18].2007年，Figueiredo等人在梯度下降法的基礎上提出了著名的稀疏梯度投影法（Gradient Projection for Sparse Reconstruction，GPSR），該算法受初始值的影響較小，而且通過調整正則因子可以有效提升算法的重建速度[34].除此以外，典型的凸優化算法還包括迭代收縮算法（iterative shrinkage thresholding algorithm，ISTA）[35]、快速迭代收縮算法（fast iterative shrinkage thresholding algorithm，FISTA）[36]、分裂 Bregman 迭代算法（Split Bregman Iteration，SBI）算法[37]和交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）[38]等.

2.1.2 貪婪迭代算法

貪婪算法出現的時間較早，解決的是最小l0范數問題，求解時利用迭代算法通過減少殘差尋找信號或圖像的最稀疏表示.最典型的貪婪算法是匹配追蹤算法（MP），由Mallat等人提出[39].隨后，Troppj引入正交的思想，通過遞歸對己選擇原子集合進行正交化以保證迭代的最優性，提出了正交匹配追蹤算法（OMP）[40].為了縮小運算時間，提高重建精度，增強重建信號對噪聲的魯棒性，在2009年，Needell等人在OMP的基礎上提出了正則正交匹配追蹤（Regularized Orthogonal Matching Pursuit，ROMP）算法[41]和壓縮采樣匹配追蹤（Compressive Sampling Matching Pursuit，CoSaMP）算法[42].同年，Donoho等人提出了一種對稀疏度K自適應的稀疏自適應匹配追蹤（Sparsity Adaptive Matching Pursuit，SAMP）算法[43]，可以在K未知的情況下獲得較好的重建效果，速度也遠快于OMP算法.

2.1.3 最小全變分法

最小全變分法求解的是公式（4）梯度稀疏問題.Candès等研究者從大量自然圖像的離散梯度都是稀疏的角度出發，提出了針對圖像重構的最小全變分法[44].

該問題的求解可以轉換為二階錐規劃問題.最小全變分模型可以有效地解決圖像壓縮重構問題，重構結果精確而且魯棒，但是運算速度較慢.

2.1.4 基于Bayesian框架的重建算法

基于Bayesian框架壓縮感知重建算法著重處理時間相關性較強的信號.在Bayesian理論框架下，我們可以通過信號的稀疏表示得到信號的先驗信息，通過壓縮感知非線性采樣得到信號的后驗信息從而恢復原信號.2001年Tipping提出了結合稀疏貝葉斯學習和相關向量機（Relevance Vector Machine，RVM）學習算法對信號進行稀疏重建信號[45].2008年Ji S等人提出了一種Bayesian壓縮感知（Bayesian Compressive Sensing）BCS算法[46].Bayesian壓縮感知的相關算法還有Wipf在2004年提出的基于單測量向量的稀疏貝葉斯學習算法（Sparse Bayesian Learning，SBL）[47]和在2007年提出的基于多測量向量的MSBL算法[48].

2.2 低秩矩陣的重建算法

2.2.1 凸松弛法

凸松弛算法主要解決公式（5）和（6）的重建問題，Cai等人在2008年提出了SVT（Singular Value Thresholding）算法，該算法是基于線性伯格曼迭代（Linearized Bregman Iteration）的軟閾值門限迭代收縮算法，但該算法的計算復雜度較高，收斂速度緩慢，且其重構解沒有理論保證[49].2010年，Toh K.C.等人提出了NNLS（Nuclear-norm Regularized Least Squares）算法，該算法基于一種加速的近端梯度算法，用ε-最優解迭代，求解無約束核范數非光滑凸優化問題[50].同年，Mazumdar R等人利用核范數作為正則化子，提出了一個簡單而有效的凸算法，即Soft-Impuse算法，它使重構誤差在核范數上有界時達到最小，該算法軟填充迭代替換丟失的元素與從軟閾值SVD獲得的那些元素[51].2012年，Wen等人提出LMAFit（Low-Rank Matrix Fitting）算法[52]，該算法提出了一個低階因子分解模型，并構造了一個非線性連續超松弛（SOR）算法，只需每次迭代求解一個線性最小二乘問題.大量的數值實驗表明，LMAFit能夠以比許多核范數最小化算法快幾倍的速度可靠地解決各種各樣的問題[53].

2.2.2 迭代閾值算法

低秩迭代閾值算法有迭代軟閾值和迭代硬閾值兩類算法，典型的算法包括SVP（Singular Value Projection）算法[54]、NIHT（Normalized Iterative Hard Thresholding）算法[55]和FPCA（Approximate SVD Based FPC Algorithm）算法[56]等.Jain P等人在2010年提出的SVP（Singular Value Projection）算法[54]屬于硬閾值迭代算法，該算法將零矩陣作取為初始矩陣，用投影梯度下降法進行迭代更新，算法的收斂速度較快，對重構解的精確性也進行了詳細分析，受采樣值個數和原始矩陣的秩影響較小[54].2011年，Ma S等人利用同倫方法和近似奇異值分解過程，提出FPCA算法，該算法求解的是無約束版的核范數最小化問題[56].2013年，Tanner等人提出NIHT算法，它使用計算為精確地用于受限子空間的自適應步長，該方法被證明具有接近最優的從密集測量掩?；謴碗A的保證，并且被觀察到在某些方面具有優于用于密集測量掩模和進入測量的其它矩陣完成算法的平均情形性能[55].特別地，所提出的算法能夠從非常接近所需的最小測量次數恢復矩陣[55].

2.2.3 貪婪追蹤類算法

貪婪追蹤類算法每次迭代時選取一個局部最優解來逐步逼近原始矩陣.2009年，Haldar和Hernando提出使用冪分解（PF）算法作為秩約束矩陣恢復的工具，提出了Incremented Rank Power Factorization算法[56].結果表明，增秩PF在恢復低秩矩陣方面明顯優于核范數最小化（NNM），而且速度更快[56].2010年，Lee K等人對CoSaMP算法進行推廣，提出了ADMiRA（Atomic Decomposition for Minimum Rank Approximation）算法[57].ADMiRA算法結構簡單，計算量較小，并從理論上嚴格分析了重構解的精確性，但缺點是其受采樣值個數和原始矩陣的秩影響較大[57].

3 結論與展望

壓縮感知理論一經問世即得到廣大研究者的青睞，目前壓縮感知理論在通訊、圖像處理、醫學成像、生物傳感等眾多領域發揮著重要的作用.本文在闡述了壓縮感知理論框架和重建模型的基礎上，針對不同重建模型對壓縮感知重構算法進行總結和評述.盡管研究者對壓縮感知理論及重建算法的研究已經獲得了很多有意義的成果，然而，隨著新技術的產生與發展，將會不斷涌現出更多的壓縮感知模型和求解方法，如隨著機器學習與深度學習模型在大數據處理中所展現的優勢，使得壓縮感知理論與深度學習網絡結構的結合成為新的研究熱點等.