基于分段可調節OMP算法的圖像壓縮感知算法

石曼曼，李 雷

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

基于分段可調節OMP算法的圖像壓縮感知算法

石曼曼，李 雷

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

壓縮感知(CS)理論作用在稀疏信號或可壓縮信號，用很小的采樣速率，保證信號采樣與壓縮同時進行，并可以精確恢復原始信號。文中側重CS重構算法中經典的貪婪算法研究，介紹了四種經典的貪婪算法：正交匹配(OMP)算法、正則化正交匹配(ROMP)算法、壓縮采樣匹配追蹤(CoSaMP)算法和分段正交匹配追蹤(StOMP)算法。從重構精度和重構耗時兩個方面，結合橫向和縱向詳細的比較，詳盡地給出了不同算法的區別以及優缺點。在StOMP算法增加考慮稀疏度和觀測矩陣行列關系的可調節因子，提出了一種改進算法—分段可調節OMP重構(StrOMP)算法。通過仿真實驗發現，提出的改進算法既提高了圖像重構精度，又保證了其重構時間短的優越性。

壓縮感知；貪婪算法；圖像重構；分段可調節正交匹配追蹤算法

1 概 述

通過傳統奈奎斯特采樣定理可知，要精準恢復出原始信號，其采樣速率至少要大于信號兩倍頻寬。而壓縮感知(Compressed Sensing,CS)[1-2]有效地解決了傳統奈奎斯特定理采樣數據時的帶寬限制，減少了采樣端硬件元件損耗，因此在信息處理領域應用廣泛。

CS理論包括信號稀疏表示、觀測矩陣設計和信號重構三個關鍵問題。它指出，在某一變換域上，若信號是稀疏的或是可壓縮的，便可用一個與變換基不相關的觀測矩陣將變換所得的高維信號投影至低維空間，并保持重建所需的信息，通過求解一個優化問題，便能從少量投影中高概率重構出原始信號。

(1)

x=Ψθ

(2)

其中,Ψ=[Ψ1,Ψ2,…,ΨN]∈RN×N為正交基字典矩陣，并且ΨΨT=ΨTΨ=I；系數向量Θ=[θ1,θ2,…,θN]T。

假設θ里K?N，也就是向量θ是K-稀疏的，使用一個隨機測量陣Φ:M×N(M?N)，且這個矩陣與正交基字典X不相干，于是對x做如下投影：

y=Φx

(3)

能夠得到M個線性觀測(或稱線性投影)y∈RM，而這些線性投影擁有足夠多的信息來恢復出信號x。注意Φ的每行跟θ做乘法以后，就會獲得x的局部信息。

從觀測y還原出信號x，就轉化成一個求線性方程組解的問題，但是由于觀測y∈RM是M維的，遠小于N，沒有唯一解?？紤]把式(2)代入式(3)，記CS信息算子ACS=ΦΨ，能夠得到：

y=ΦΨθ=ACSθ

(4)

雖說從觀測y還原θ仍是一個欠定問題，可是注意到θ具有稀疏性，于是信號極有可能被恢復出來。能夠驗證的是：如果ACS里任意2K列均符合獨立這個條件，就至少有某個θ符合y=ACSθ，且θ是K-稀疏。也就是解一個非線性優化問題來精準重構出原始信號x。

2 基于CS的信息重建算法

2.1 正交匹配追蹤(OMP)類算法

OMP類算法作為貪婪算法的主流算法被廣泛應用。本節對OMP算法[3]、ROMP算法[4]、CoSaMP算法[5]和StOMP算法[6]進行研究分析，并給出四種重建算法的重構效果。該類算法是通過貪心思想，使得每迭代一步得到一個局部最優解，逐步逼近原信號。這四種算法的共同點都是利用MP算法中的原子選擇原則，選取原子更新支撐集，然后利用最小二乘法取得最優解[7]。四種算法的區別是原子的選擇方式不同。

對于OMP算法，其本質思想是：憑迭代更新找出投影矩陣Φ的列，然后更新尋求的列和當前冗余向量最相關，之后把相干原子從Φ里面剔除，更新K次。而ROMP算法依照相關性原則對原子做第一次選擇，取出K個相應的索引值放進指標集合J中；依照正則性再次挑選，原則如下：

ui≤2uj,i,j∈J

(5)

2.2 OMP類算法仿真實驗與分析

CS重構過程中，文中使用離散小波變換形成DWT基對圖像做稀疏化變換，然后選取隨機高斯矩陣[8-9]對圖像取得觀測值，最后用貪婪算法對觀測值做重建操作。實驗對象為圖像庫中的Lena圖像(512*512，jpg)，稀疏度的估計取經驗值K=M/(2*lg(N))。用PSNR(dB)值來判斷算法重建效果的好壞，值愈大愈好；用重建耗時(s)值來判斷恢復速度，值愈小愈好。

以下不同算法的仿真實驗均采用相同的運行平臺和衡量指標，采樣率均為0.2。每個算法做5次MATLAB仿真，以平均結果作為最終算法的PSNR與重建耗時值。仿真結果如圖1所示。

圖1 原始圖像及四種算法重構效果圖

從圖1可以看到，四種算法均能完成實驗仿真。給出圖像在不同采樣率下的PSNR值(dB)與重構消耗時間t值(s)，見表1和表2。

表1 OMP類算法Lena重建PSNR變化表

從表1和表2中可以看到，貪婪算法在圖像重構應用[10-13]中，除StOMP算法外，其余算法均隨采樣率的增加，PSNR值增加，耗時增大，這表明重構效果越來越好，但與之相對應的是消耗時間變長，但能夠較好地恢復出原始圖像；而StOMP算法下的重構是隨采樣率增大，PSNR值變小，耗時增加，這與閾值的選擇有關。

表2 OMP類算法Lena重建耗時t變化表

ROMP算法好于OMP算法，在相同條件下重構效果好且重構時間短。ROMP在采樣率M/N等于0.4、0.5時，可以較為準確地重建出原來的圖像。采樣率相同時，CoSaMP算法重建出的PSNR值要略高于ROMP和OMP算法，重建效果好，重建耗時遠大于前兩種算法。StOMP算法加入了閾值，設定了迭代次數，在一定程度上簡化了OMP算法，能明顯看出重構耗時之少，但只有保證準確預測出K，才會精準恢復出原信號。閾值的選擇問題對于重構效果非常關鍵，至于究竟該選多大的閾值，則要根據實際情況在具體的實踐應用中進行選擇，一般閾值取值范圍為2≤ζ≤3。所以在StOMP算法上，閾值的選擇也是一個須要探究的方向。

3 基于分段可調節(StrOMP)算法在圖像上的運用

貪婪算法的運行速度是相當快的，不同的算法會產生不一樣的重構效果，一般來說對于重建精度比較高的算法，重建耗時會相對增多；重建出的信息精度較低的算法，重建耗時會相對較少，這是由于重構精度和耗時存在不兼容性?；诖耍闹袑tOMP算法進行改進，尋找一個折中的算法，既能提高其重構精度，又能保證其重構時間少的優越性。

3.1 經典貪婪算法的比較

為體現新算法的優勢，需先比較已有的貪婪算法的性能。由于壓縮觀測時M?N，那么重建就是求ULE問題解的過程。而結合前述四種算法，給出算法間重建結果的對比，以及重建耗時的比較。圖2展現了在采樣率M/N等于0.1，0.2，0.3，0.4與0.5的情況下，Lena重建的PSNR值和重構時間的變化圖。

圖2 采樣率不同時Lena重建PSNR變化圖

由圖2可知，隨著采樣率M/N的增加，除StOMP算法的PSNR呈緩慢下降趨勢外，其他三種算法均隨著采樣率的增加而增加，這表明ROMP、CoSaMP同OMP算法相同，隨著采樣率M/N的增加，重建精度增大，重建效果優，而StOMP算法重建精度卻緩慢下降并趨于平穩值。當采樣率低于0.5時，ROMP算法的重建結果要稍稍優于CoSaMP，CoSaMP重建結果要優于OMP，OMP又要好過StOMP。即文中給出的四種算法中重建效果最差的當屬StOMP。分析信號重構時消耗的時間t，伴隨采樣率M/N的增大，重建耗時也會跟著增大，而CoSaMP耗時最多，接著為OMP和ROMP算法，耗時最少的則是StOMP算法。這也說明一般情況下，圖像重建質量和耗時是不兼容、互相限制的。當PSNR增大時，勢必將帶來重構耗時的增加；同樣，縮短耗時就很可能會犧牲部分重構質量。另外，隨著采樣率的增加，一般算法的重構精度會變大，重構效率也會有所提高，即重構耗時增加。因此在研究探索新算法時，需要很好地把握這兩方面，找到二者的折中點。

3.2 改進的分段可調節OMP(StrOMP)算法

StOMP算法具有很強的可塑性，雖然該算法重構圖像質量較差，但具有重構時間極短的優勢。在StOMP算法中，一個關鍵問題就是閾值的選擇問題，它會直接關系到重構質量。

StrOMP算法是改進的StOMP算法，設定迭代次數不變，給StOMP算法中的閾值增加一個調節因子，用可調節閾值的辦法挑選出原子，與OMP算法的差異在于，它在篩選原子的進程中設立了如下選擇標準：

Jk={j|uj>ηtkσk}

(6)

3.3 StrOMP算法步驟

輸入：原始信號x∈RN，觀測矩陣Φ∈RM×N，觀測向量y∈RM，閾值ζ和調節因子η；

核心步驟如下：

(2)計算Cs=ΦTrs-1=<Φ,rs-1>。

(5)更新殘差值：rs=y-Φxs。

StrOMP算法的復雜度沒有增加，僅在原閾值上增加了調節因子η。由于采樣率不同，導致稀疏度和觀測矩陣列的數目發生改變，采樣率增大，則M和K也增大，于是考慮其增大的關系，最終給定調節因子為η=M/4.2K，自適應地提高圖像重構質量。

4 StrOMP算法仿真結果與性能分析

利用文中提出的StrOMP算法對圖像進行重構，重構效果圖如圖3所示，這里采樣率分別取M/N=0.5,0.3,0.1。

圖3 StrOMP算法恢復Lena效果圖

通過圖3可以發現改進的StrOMP算法在采樣率不同時能夠較為清晰地重構出原始圖像，而且可以看到采樣率越小，重構效果越好，這跟StOMP算法保持了一致性，說明算法是可以實現的。

為了更加直觀地顯示StrOMP算法在M/N取不同值時的重建效果以及為了更好地比較兩種算法，文中給出Lena圖像在不同采樣率下的PSNR值(單位：dB)和CS重建部分消耗時間t值(單位：s)，見表3。

表3 StrOMP與StOMP算法對Lena重建PSNR和耗時t變化表

從表3中可以看出，StrOMP算法重構PSNR值在相同的采樣率下總是略高于StOMP算法，這表明改進算法比原算法重構精度高，重建結果好，雖然改進算法重構時間比原算法略長，但仍然比較迅速。隨著采樣率的增大，新算法的PSNR值隨之減少，而重構耗時卻隨之變長，這一點與原算法保持一致。主要原因是StrOMP算法沒有增加算法的復雜度，僅在閾值的選擇方面加入了一個調節因子，但從效果看，文中提出的StrOMP算法在重構精度上優于原來的分段正交匹配追蹤算法。

改進算法的重構時間有所增加，但增加值很小，明顯優于CoSaMP算法，但是為了比較改進算法在重構時間跟其他算法相比是否仍然具有優勢，當采樣率不相同時給出OMP、ROMP、StOMP和StrOMP算法對Lena圖像重建耗時的變化圖及新算法PSNR對比圖，見圖4。

從圖4(a)可以看出，改進后的算法StrOMP除個別點外，隨著采樣率的增加，重建耗時在隨之增加，除采樣率為0.3時增加有些快外，其他采樣率下均明顯優于OMP和ROMP算法，雖然比原算法重構時間略長，但都少于1s，仍然保留了StOMP算法重建快的優點。提出的StrOMP算法也能明顯看出計算速度的優勢，但由于其僅在閾值選擇時加入了調節因子，使得算法的精度略有提高，雖保持了算法的操作簡單性，但在所有更新的步驟里挑選的也非最優表示，所以重建精度跟其他算法比較起來不高，效果不是特別好，但是其重構消耗時間短仍是它的優點。

圖4 Lena重構耗時t的變化圖及新算法PSNR對比圖

圖4(b)為改進的StrOMP和原始StOMP在采樣率M/N不相同時Lena的PSNR值的變化情況。伴隨采樣率M/N的變大，兩種算法的PSNR均隨之降低，而且受采樣率的影響較大。但是，在相同的采樣率下可以明顯看出，改進算法的PSNR值總是高于StOMP，平均高出0.2～0.3dB，表明改進的StrOMP重建精度增大，改進通過仿真驗證是成功的。需要指出，文中在對Lena重建時，在采樣比等于0.1和0.2時，加入調節因子后的閾值分別為3.328 4和3.074 5，均超出經驗閾值在2≤ζ≤3這個范圍，并且重建好于原閾值下的結果。

5 結束語

文中通過闡述CS理論基礎知識，詳細討論了幾種典型的CS重構算法，并將CS理論應用于圖像中，對四種經典的貪婪算法從多角度分析重構效果，比較算法的優缺點。針對其中的StOMP算法，加入考慮稀疏度和觀測矩陣行列關系的調節因子，使閾值變得更加精細，從而提出改進的分段可調節OMP算法。仿真結果表明，改進后的StrOMP算法從耗時和PSNR值上都優于StOMP算法。

[1]DonohoDL.Compressedsensing[J].IEEETransactionsonInformationTheory,2006,52(4):1289-1306.

[2]CandèsEJ,RombergJ,TaoT.Robustundertaintyprinciples:exactsignalreconstructionfromhighlyincompletefrequencyinformation[J].IEEETransactionsonInformationTheory,2006,52(2):489-509.

[3]TroppJA,GilbertAC.Signalrecoveryfromrandommeasurementsviaorthogonalmatchingpursuit[J].IEEETransactionsonInformationTheory,2007,53(12):4655-4666.

[4]NeedellD,VershyninR.SignalrecoveryfromincompleteandinaccuratemeasurementsviaROMP[J].IEEEJournalofSelectedTopicsinSignalProcessing,2010,4(2):310-316.

[5]NeedellD,TroppJA.CoSaMP:iterativesignalrecoveryfromincompleteandinaccuratesamples[J].Applied&ComputationalHarmonicAnalysis,2008,26(3):301-321.

[6]DonohoDL,TsaigY,DroriI,etal.Sparsesolutionofunderdeterminedsystemsoflinearequationsbystagewiseorthogonalmatchingpursuit[J].IEEETransactionsonInformationTheory,2012,58(2):1094-1121.

[7] 楊真真.壓縮感知重構技術及其在圖像融合中的應用研究[D].南京:南京郵電大學,2014.

[8]CandesEJ,WakinMB.Anintroductiontocompressivesampling[J].IEEESignalProcessingMagazine,2008,25(2):21-30.

[9] 石光明，劉丹華，高大化,等.壓縮感知理論及其研究進展[J].電子學報,2009,37(5):1070-1081.

[10] 高 睿，趙瑞珍，胡紹海.基于壓縮感知的變步長自適應匹配追蹤重建算法[J].光學學報，2010(6):1639-1644.

[11] 甘 偉，許錄平,張 華,等.一種貪婪自適應壓縮感知重構[J].西安電子科技大學學報，2012,39(3):50-57.

[12]PeyréG.Bestbasiscompressedsensing[M]//Scalespaceandvariationalmethodsincomputervision.Berlin:Springer,2007:2613-2622.

[13]MunS,FowlerJE.Blockcompressedsensingofimagesusingdirectionaltransforms[C]//IEEEinternationalconferenceonimageprocessing.[s.l.]:IEEE,2009:3021-3024.

[14]TramelEW,FowlerJE.Videocompressedsensingwithmultihypothesis[C]//Proceedingsofthe2011datacompressionconference.[s.l.]:IEEEComputerSociety,2011:193-202.

[15] 李 博.壓縮感知理論的重構算法研究[D].長春：吉林大學，2013.

An Image Compressed Sensing Algorithm Based on Novel Stagewise Regulation OMP Algorithm

SHI Man-man,LI Lei

(College of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

Compressed Sensing (CS) theory uses small frequency,which is mainly for sparse or compressible signal.Sampling and compressing are also implemented successfully at the same time,and can accurately recover the original signal.It focuses on the classical greedy algorithm in this paper for compressed sensing reconstruction algorithm,including four classical matching pursuit algorithms like Orthogonal Matching Pursuit (OMP),the Regularized Orthogonal Matching Pursuit (ROMP),Compressive Sampling Matching Pursuit (CoSaMP) and Stagewise Orthogonal Matching Pursuit (StOMP).Considering the reconstruction accuracy and time as evaluation standards,the advantages and disadvantages of algorithms and difference of them are given by combining with horizontal and vertical comparison.The adjustment factor for StOMP at each iteration is put considering the sparsity and the observation matrix ranks,and an improved algorithm is proposed,which makes innovations for StrOMP algorithm,named Stagewise regulation Orthogonal Matching Pursuit (StrOMP).The simulation shows the proposed algorithm can raise the accuracy of image reconstruction,and guarantee the priority of the reconstruction time of the new algorithm.

compressed sensing;greedy algorithm;image reconstruction;stagewise regulation orthogonal matching pursuit reconstruction algorithm

2016-01-18

2016-05-11

時間：2016-10-24

國家自然科學基金資助項目(61501251)；南京郵電大學引進人才科研啟動基金資助項目(NY214191)

石曼曼(1992-)，女，碩士研究生，研究方向為信息處理理論與應用；李 雷，博士，教授，研究方向為智能信號處理和非線性科學及其在通信中的應用。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1113.032.html

TP301.6

A

1673-629X(2016)11-0014-05

10.3969/j.issn.1673-629X.2016.11.004