石曼曼，李 雷

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

基于分段可調(diào)節(jié)OMP算法的圖像壓縮感知算法

石曼曼，李 雷

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

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

壓縮感知；貪婪算法；圖像重構(gòu)；分段可調(diào)節(jié)正交匹配追蹤算法

1 概 述

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

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

(1)

x=Ψθ

(2)

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

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

y=Φx

(3)

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

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

y=ΦΨθ=ACSθ

(4)

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

2 基于CS的信息重建算法

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

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

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

ui≤2uj,i,j∈J

(5)

2.2 OMP類算法仿真實(shí)驗(yàn)與分析

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

以下不同算法的仿真實(shí)驗(yàn)均采用相同的運(yùn)行平臺(tái)和衡量指標(biāo)，采樣率均為0.2。每個(gè)算法做5次MATLAB仿真，以平均結(jié)果作為最終算法的PSNR與重建耗時(shí)值。仿真結(jié)果如圖1所示。

圖1 原始圖像及四種算法重構(gòu)效果圖

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

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

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

表2 OMP類算法Lena重建耗時(shí)t變化表

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

3 基于分段可調(diào)節(jié)(StrOMP)算法在圖像上的運(yùn)用

貪婪算法的運(yùn)行速度是相當(dāng)快的，不同的算法會(huì)產(chǎn)生不一樣的重構(gòu)效果，一般來說對(duì)于重建精度比較高的算法，重建耗時(shí)會(huì)相對(duì)增多；重建出的信息精度較低的算法，重建耗時(shí)會(huì)相對(duì)較少，這是由于重構(gòu)精度和耗時(shí)存在不兼容性?；诖?，文中對(duì)StOMP算法進(jìn)行改進(jìn)，尋找一個(gè)折中的算法，既能提高其重構(gòu)精度，又能保證其重構(gòu)時(shí)間少的優(yōu)越性。

3.1 經(jīng)典貪婪算法的比較

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

圖2 采樣率不同時(shí)Lena重建PSNR變化圖

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

3.2 改進(jìn)的分段可調(diào)節(jié)OMP(StrOMP)算法

StOMP算法具有很強(qiáng)的可塑性，雖然該算法重構(gòu)圖像質(zhì)量較差，但具有重構(gòu)時(shí)間極短的優(yōu)勢(shì)。在StOMP算法中，一個(gè)關(guān)鍵問題就是閾值的選擇問題，它會(huì)直接關(guān)系到重構(gòu)質(zhì)量。

StrOMP算法是改進(jìn)的StOMP算法，設(shè)定迭代次數(shù)不變，給StOMP算法中的閾值增加一個(gè)調(diào)節(jié)因子，用可調(diào)節(jié)閾值的辦法挑選出原子，與OMP算法的差異在于，它在篩選原子的進(jìn)程中設(shè)立了如下選擇標(biāo)準(zhǔn)：

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

(6)

3.3 StrOMP算法步驟

輸入：原始信號(hào)x∈RN，觀測(cè)矩陣Φ∈RM×N，觀測(cè)向量y∈RM，閾值ζ和調(diào)節(jié)因子η；

核心步驟如下：

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

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

StrOMP算法的復(fù)雜度沒有增加，僅在原閾值上增加了調(diào)節(jié)因子η。由于采樣率不同，導(dǎo)致稀疏度和觀測(cè)矩陣列的數(shù)目發(fā)生改變，采樣率增大，則M和K也增大，于是考慮其增大的關(guān)系，最終給定調(diào)節(jié)因子為η=M/4.2K，自適應(yīng)地提高圖像重構(gòu)質(zhì)量。

4 StrOMP算法仿真結(jié)果與性能分析

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

圖3 StrOMP算法恢復(fù)Lena效果圖

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

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

表3 StrOMP與StOMP算法對(duì)Lena重建PSNR和耗時(shí)t變化表

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

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

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

圖4 Lena重構(gòu)耗時(shí)t的變化圖及新算法PSNR對(duì)比圖

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

5 結(jié)束語

文中通過闡述CS理論基礎(chǔ)知識(shí)，詳細(xì)討論了幾種典型的CS重構(gòu)算法，并將CS理論應(yīng)用于圖像中，對(duì)四種經(jīng)典的貪婪算法從多角度分析重構(gòu)效果，比較算法的優(yōu)缺點(diǎn)。針對(duì)其中的StOMP算法，加入考慮稀疏度和觀測(cè)矩陣行列關(guān)系的調(diào)節(jié)因子，使閾值變得更加精細(xì)，從而提出改進(jìn)的分段可調(diào)節(jié)OMP算法。仿真結(jié)果表明，改進(jìn)后的StrOMP算法從耗時(shí)和PSNR值上都優(yōu)于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] 楊真真.壓縮感知重構(gòu)技術(shù)及其在圖像融合中的應(yīng)用研究[D].南京:南京郵電大學(xué),2014.

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

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

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

[11] 甘 偉，許錄平,張 華,等.一種貪婪自適應(yīng)壓縮感知重構(gòu)[J].西安電子科技大學(xué)學(xué)報(bào)，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] 李 博.壓縮感知理論的重構(gòu)算法研究[D].長(zhǎng)春：吉林大學(xué)，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

時(shí)間：2016-10-24

國(guó)家自然科學(xué)基金資助項(xiàng)目(61501251)；南京郵電大學(xué)引進(jìn)人才科研啟動(dòng)基金資助項(xiàng)目(NY214191)

石曼曼(1992-)，女，碩士研究生，研究方向?yàn)樾畔⑻幚砝碚撆c應(yīng)用；李 雷，博士，教授，研究方向?yàn)橹悄苄盘?hào)處理和非線性科學(xué)及其在通信中的應(yīng)用。

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