石曼曼，李 雷

(南京郵電大學 理學院，江蘇 南京 210023)

0 引 言

傳統(tǒng)的信號采樣建立于奈奎斯特(Nyquist)定理上。其要求采樣速度必須超過原始信號兩倍頻寬，才能恢復出原始信號。隨著數(shù)字信號處理的迅猛發(fā)展，待處理的信號越來越多，導致傳輸?shù)膲毫^大。因此，迫切需要一種全新的采樣方式，去滿足采集存儲信息的要求。于是，壓縮感知(compressed sensing,CS)[1-2]理論應運而生。

CS與奈奎斯特取樣不同的是，它利用了信號更多的信息，包含稀疏性和相干性，不再受帶寬的限制，實現(xiàn)取樣、壓縮一體化，不僅節(jié)省了存儲空間，而且降低了元件損耗的風險。目前，CS廣泛應用于遙感成像[3]、醫(yī)療成像[4]、無線傳感網(wǎng)絡[5]、雷達成像[6]等眾多領域。

重構是CS技術關鍵的一步，主要有三大類方法[7]，包括最小l1范數(shù)的凸松弛算法、貪婪算法以及組合算法。凸松弛算法包含基追蹤(basic pursuit,BP)算法[8]、基于梯度投影的一類算法[9]等等。貪婪算法基于最小l0范數(shù)，包含正交匹配追蹤(orthogonal matching pursuit,OMP)[10]、正則化的正交匹配追蹤(regularized orthogonal matching pursuit,ROMP)[11]以及壓縮采樣匹配追蹤(compressive sampling matching pursuit,CoSaMP)[12]等算法。組合算法是通過分組測試實現(xiàn)快速重構。因每一類算法在重構耗時和重構結果上各有利弊，不少學者針對算法的各種缺點進行優(yōu)化[13-14]。

貪婪算法憑借重構速度快的優(yōu)勢，得到了廣泛的應用。其中OMP算法采用自下而上的方式更新，在未得到最終解時通過預設某個起始解，但是重構時間較長，重構精確度不高。OMP作為經(jīng)典的貪婪算法之一，目前有很多學者對其進行了改進[15-17]。在此基礎上，文中針對OMP算法重構時間慢、重構效果不好的缺點，加入雙閾值，在OMP迭代至殘差小于第一閾值后引入回溯思想，采用CoSaMP繼續(xù)更新，直至殘差小于第二閾值。將OMP的優(yōu)點和回溯思想相結合，通過雙閾值分階段調(diào)控迭代，提出改進的雙閾值分段迭代匹配追蹤(DTSIMP)算法。

1 壓縮感知理論

相比于奈奎斯特采樣定理，CS利用觀測矩陣直接得到可壓縮或稀疏信號的特征信息。

假設x是一維離散隨機信號，稀疏度為K，長度為N，即x∈RN×1。對于x，線性觀測過程能用某個M×N維隨機矩陣Φ表示(M?N)，通過投影能夠觀測到M×1維列向量y，即

y=Φx

(1)

在這一過程中Φ是不變的，因此觀測過程并非自適應過程。由式(1)可知，需要求解一個含M個等式的線性方程組。但由于M?N，即方程個數(shù)遠大于未知數(shù)個數(shù)，因此式(1)有無窮多解。若已知x的稀疏度為K?M，也就是說x中含N-K個零項，同時已知位置，由CS知，這個欠定問題能夠得到解決。只要觀測矩陣Φ符合約束等距(restricted isometry property，RIP)[1]特征，即Φ滿足下式：

(2)

其中，ε∈(0,1)，那么能夠由y來獲得K個稀疏觀測。

將式(1)轉(zhuǎn)化為l0范數(shù)極小化問題，求解得到原始信號，即：

(3)

在實際求解過程中，一般轉(zhuǎn)化為次最優(yōu)問題求解。即：

min‖x‖0s.t. ‖y-Φx‖2<δ

(4)

用貪婪算法求解此類問題，重構精度會略有降低，但縮短了運行時間，和其他類算法相比，具有更廣泛的應用。

2 雙閾值分段迭代匹配追蹤算法

2.1 匹配追蹤類算法

貪婪追蹤匹配算法，采用多次迭代的思想，利用不同的特定準則實現(xiàn)迭代，最終通過特定的迭代終止條件，以觀測矩陣作為原子庫，從中判斷篩選出能夠準確表達原始信號的原子。由這些匹配原子經(jīng)計算得到最優(yōu)稀疏解。這類算法的最大特點是重構速度快，重建時間短。

OMP算法需要已知信號的稀疏度。在每一步迭代時，均從觀測矩陣中選取與當前殘差內(nèi)積最大的原子，將其加入到支撐集，然后求解最小二乘，更新殘差，進入下一次迭代。不妨假設信號是K稀疏的，則更新次數(shù)為K次。因為OMP算法在迭代中僅挑選唯一的原子來擴充支撐集，雖然得到的原子大部分是準確的，但會增大重構時間。且原子一旦并入支撐集，無論該原子是否準確，都只能保留。文中針對此缺點引入雙閾值，并將迭代分為兩部分，引入回溯思想，從而實現(xiàn)精準快速重構。

2.2 雙閾值分段迭代匹配追蹤算法

OMP算法每步更新只篩選出唯一原子加入支撐集，且加入的原子不能剔除，導致精度降低、耗時增加。而且作為一種經(jīng)典的貪婪算法，其重構精度也有很大的提升空間。因此文中考慮改變OMP算法迭代的過程。為了不增加算法復雜度，第一階段利用OMP算法迭代若干次，迭代停止閾值為α，然后引入回溯思想，利用CoSaMP算法更新，并將OMP更新所得殘差和原子集當作第二階段的輸入值，第二階段迭代停止閾值為δ，且δ<α，從而縮短重建耗時，實現(xiàn)準確重建。新算法步驟如下：

輸入：觀測矩陣Φ，觀測向量y，信號稀疏度K，閾值δ；

改進算法在殘差不小于第一閾值α的條件下用OMP算法求解，之后引入回溯思想，采用CoSaMP算法迭代，用上一次更新得到的殘差和原子集作為第二階段初始值，并且通過第二閾值來終止迭代。且OMP算法迭代選擇出的原子大部分是精確的，從而回溯過程開始時，會因為初始輸入的精確性，使得信號得以快速重建，因此新算法是可行的。

3 實驗結果和性能分析

給出不同算法的重構性能對比，以此分析算法的性能。實驗對象為一維離散隨機信號和二維圖像。實驗結果為各算法在相同實驗條件下運行200次取平均所得。

3.1 重構性能分析

為了驗證算法的有效性及優(yōu)越性，在給定的采樣率下，給出一維高斯隨機信號的OMP與文中算法的重構成功率和重構時間與稀疏度的關系，并對仿真結果進行分析。

3.1.1 重構成功率分析

重構對象為一維高斯隨機信號，長度N=256，測量矩陣Φ:M×N為高斯隨機矩陣，分別用OMP算法和文中算法進行重構。第一閾值為α，第二閾值為δ，在大量實驗基礎下，均衡重構時間和精度，取α=6×10-3*‖y‖2，δ=10-5*‖y‖2。采樣率取0.5時，兩種算法在改變稀疏度的情況下，重構成功率如圖1所示。

由圖1可知，隨稀疏度的增加兩種算法的重構成功率均降低，但文中算法的實驗結果優(yōu)于OMP算法。和OMP算法相比，新算法重構成功率大幅提高。稀疏度為40時，用OMP恢復出x的成功率約為60%，但文中算法對x恢復的成功率仍接近100%；當稀疏度為50時，OMP算法對應恢復信號成功率小于20%，無法保證重構成功，但文中算法依舊有90%以上的重構成功率，可見新算法具備成功重建信號的優(yōu)勢。

圖1 重構成功率和稀疏度關系對比

3.1.2 重構運行時間比較

采樣率相同時，給出文中算法和OMP算法重構所需時間與稀疏度的關系曲線，如圖2所示，其中采樣率取0.5。

圖2 重構時間和稀疏度關系對比

由圖2可知，稀疏度增大時，OMP和改進算法運行時間均有所增加，但新算法增加緩慢且重構時間比OMP算法少。這是因為文中算法采用雙閾值兩階段迭代。首先，OMP算法迭代若干次之后，通過第一閾值控制進入第二階段迭代；其次，引入回溯思想，使其快速正確地挑選原子，并由第二閾值約束控制，算法收斂時間變短。跟OMP算法比較，改進算法不僅具有很強的重構成功率，而且恢復速度快。

3.2 改進OMP算法在圖像上的應用

將文中算法用于二維圖像的重構，實驗對象為256×256的Lena標準灰度圖像。首先用DWT基對圖像稀疏表示，之后用高斯隨機矩陣線性觀測，得到觀測值，分別用三種算法重構，采樣率取0.5，實驗結果見圖3。

由圖3不難看出，文中算法的重建結果更接近原始圖像，而OMP和CoSaMP重建的某些部分較為模糊，因此文中算法在圖像上的重構也是可行且效果較好。

圖3 重構效果對比圖

表1和表2分別在采樣率取0.5、0.6和0.7時，對比了不同算法的重構時間和峰值信噪比(PSNR)。

表1 重構時間和采樣率的關系 s

表2 峰值信噪比和采樣率的關系 dB

由表1可知，隨采樣率的增大，三種算法重構時間變長，但文中算法在采樣率相同時，耗時均最短，較CoSaMP算法耗時大幅減少，也比OMP算法平均快2 s，算法的速度快、耗時短。

由表2可知，隨采樣率的增加，PSNR增大，即圖像恢復的更好。相同采樣率時，文中算法的PSNR值略高于CoSaMP算法，且平均比OMP算法高出1 dB，重建結果最好。結合表1表明，文中算法重構性能更好。

4 結束語

提出了一種改進的OMP算法，利用雙閾值兩階段控制迭代。首先利用OMP算法迭代若干次，至殘差小于第一閾值時引入回溯思想，采用CoSaMP繼續(xù)更新，殘差小于第二閾值時停止迭代，從而精確快速地重構出稀疏信號。實驗結果表明，與OMP算法相比，文中算法對一維的隨機高斯信號和二維圖像信號的重構成功率高，重構迅速且重構效果好。

[1] KUTYNIOK G.Compressed sensing:theory and applications[M].[s.l.]:Cambridge University Press,2012.

[2] 邵文澤,韋志輝.壓縮感知基本理論:回顧與展望[J].中國圖象圖形學報,2012,17(1):1-12.

[3] 李烈辰,李道京.基于壓縮感知的連續(xù)場景稀疏陣列SAR三維成像[J].電子與信息學報,2014,36(9):2166-2172.

[4] LIU Y,ZHAN Z,CAI J,et al.Projected iterative soft-thresholding algorithm for tight frames in compressed sensing magnetic resonance imaging[J].IEEE Transactions on Medical Imaging,2016,35(9):2130-2140.

[5] 黃海平,陳九天,王汝傳,等.無線傳感器網(wǎng)絡中基于數(shù)據(jù)融合樹的壓縮感知算法[J].電子與信息學報,2014,36(10):2364-2369.

[6] 李少東,楊 軍,陳文峰,等.基于壓縮感知理論的雷達成像技術與應用研究進展[J].電子與信息學報,2016,38(2):495-508.

[7] 劉 芳,武 嬌,楊淑媛,等.結構化壓縮感知研究進展[J].自動化學報,2013,39(12):1980-1995.

[8] 張小亞,張 慧,王紅霞.基追蹤問題的近點算法及其應用研究[J].計算機工程與科學,2016,38(1):120-124.

[9] 張本鑫,朱志斌.全變差圖像恢復的自適應步長梯度投影算法[J].自動化學報,2016,42(9):1347-1355.

[10] 劉記紅,黎 湘,徐少坤,等.基于改進正交匹配追蹤算法的壓縮感知雷達成像方法[J].電子與信息學報,2012,34(6):1344-1350.

[11] NEEDELL D,VERSHYNIN R.Signal recovery from inaccurate and incomplete measurements via regularized orthogonal matching pursuit[J].IEEE Journal of Selected Topics in Signal Processing,2010,4(2):310-316.

[12] 蔣留兵,黃 韜.一種新的壓縮采樣匹配追蹤算法[J].計算機應用研究,2013,30(2):402-404.

[13] 劉盼盼,李 雷,王浩宇.壓縮感知中基于變尺度法的貪婪重構算法的研究[J].通信學報,2014,35(12):98-105.

[14] 陳善雄,何中市,熊海靈,等.一種基于壓縮感知的無線傳感信號重構算法[J].計算機學報,2015,38(3):614-624.

[15] 曾春艷.匹配追蹤的最佳原子選擇策略和壓縮感知盲稀疏度重建算法改進[D].廣州:華南理工大學,2013.

[16] 石曼曼,李 雷.基于分段可調(diào)節(jié)OMP算法的圖像壓縮感知算法[J].計算機技術與發(fā)展,2016,26(11):14-18.

[17] ZHANG D,ZHANG Y,HU X,et al.Fast OMP algorithm for 3D parameters super-resolution estimation in bistatic MIMO radar[J].Electronics Letters,2016,52(13):1164-1166.