一種改進(jìn)的OMP算法及其在圖像重構(gòu)上的應(yīng)用

石曼曼，李 雷

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

0 引 言

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

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

重構(gòu)是CS技術(shù)關(guān)鍵的一步，主要有三大類方法[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]等算法。組合算法是通過(guò)分組測(cè)試實(shí)現(xiàn)快速重構(gòu)。因每一類算法在重構(gòu)耗時(shí)和重構(gòu)結(jié)果上各有利弊，不少學(xué)者針對(duì)算法的各種缺點(diǎn)進(jìn)行優(yōu)化[13-14]。

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

1 壓縮感知理論

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

假設(shè)x是一維離散隨機(jī)信號(hào)，稀疏度為K，長(zhǎng)度為N，即x∈RN×1。對(duì)于x，線性觀測(cè)過(guò)程能用某個(gè)M×N維隨機(jī)矩陣Φ表示(M?N)，通過(guò)投影能夠觀測(cè)到M×1維列向量y，即

y=Φx

(1)

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

(2)

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

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

(3)

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

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

(4)

用貪婪算法求解此類問(wèn)題，重構(gòu)精度會(huì)略有降低，但縮短了運(yùn)行時(shí)間，和其他類算法相比，具有更廣泛的應(yīng)用。

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

2.1 匹配追蹤類算法

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

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

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

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

輸入：觀測(cè)矩陣Φ，觀測(cè)向量y，信號(hào)稀疏度K，閾值δ；

改進(jìn)算法在殘差不小于第一閾值α的條件下用OMP算法求解，之后引入回溯思想，采用CoSaMP算法迭代，用上一次更新得到的殘差和原子集作為第二階段初始值，并且通過(guò)第二閾值來(lái)終止迭代。且OMP算法迭代選擇出的原子大部分是精確的，從而回溯過(guò)程開始時(shí)，會(huì)因?yàn)槌跏驾斎氲木_性，使得信號(hào)得以快速重建，因此新算法是可行的。

3 實(shí)驗(yàn)結(jié)果和性能分析

給出不同算法的重構(gòu)性能對(duì)比，以此分析算法的性能。實(shí)驗(yàn)對(duì)象為一維離散隨機(jī)信號(hào)和二維圖像。實(shí)驗(yàn)結(jié)果為各算法在相同實(shí)驗(yàn)條件下運(yùn)行200次取平均所得。

3.1 重構(gòu)性能分析

為了驗(yàn)證算法的有效性及優(yōu)越性，在給定的采樣率下，給出一維高斯隨機(jī)信號(hào)的OMP與文中算法的重構(gòu)成功率和重構(gòu)時(shí)間與稀疏度的關(guān)系，并對(duì)仿真結(jié)果進(jìn)行分析。

3.1.1 重構(gòu)成功率分析

重構(gòu)對(duì)象為一維高斯隨機(jī)信號(hào)，長(zhǎng)度N=256，測(cè)量矩陣Φ:M×N為高斯隨機(jī)矩陣，分別用OMP算法和文中算法進(jìn)行重構(gòu)。第一閾值為α，第二閾值為δ，在大量實(shí)驗(yàn)基礎(chǔ)下，均衡重構(gòu)時(shí)間和精度，取α=6×10-3*‖y‖2，δ=10-5*‖y‖2。采樣率取0.5時(shí)，兩種算法在改變稀疏度的情況下，重構(gòu)成功率如圖1所示。

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

圖1 重構(gòu)成功率和稀疏度關(guān)系對(duì)比

3.1.2 重構(gòu)運(yùn)行時(shí)間比較

采樣率相同時(shí)，給出文中算法和OMP算法重構(gòu)所需時(shí)間與稀疏度的關(guān)系曲線，如圖2所示，其中采樣率取0.5。

圖2 重構(gòu)時(shí)間和稀疏度關(guān)系對(duì)比

由圖2可知，稀疏度增大時(shí)，OMP和改進(jìn)算法運(yùn)行時(shí)間均有所增加，但新算法增加緩慢且重構(gòu)時(shí)間比OMP算法少。這是因?yàn)槲闹兴惴ú捎秒p閾值兩階段迭代。首先，OMP算法迭代若干次之后，通過(guò)第一閾值控制進(jìn)入第二階段迭代；其次，引入回溯思想，使其快速正確地挑選原子，并由第二閾值約束控制，算法收斂時(shí)間變短。跟OMP算法比較，改進(jìn)算法不僅具有很強(qiáng)的重構(gòu)成功率，而且恢復(fù)速度快。

3.2 改進(jìn)OMP算法在圖像上的應(yīng)用

將文中算法用于二維圖像的重構(gòu)，實(shí)驗(yàn)對(duì)象為256×256的Lena標(biāo)準(zhǔn)灰度圖像。首先用DWT基對(duì)圖像稀疏表示，之后用高斯隨機(jī)矩陣線性觀測(cè)，得到觀測(cè)值，分別用三種算法重構(gòu)，采樣率取0.5，實(shí)驗(yàn)結(jié)果見(jiàn)圖3。

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

圖3 重構(gòu)效果對(duì)比圖

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

表1 重構(gòu)時(shí)間和采樣率的關(guān)系 s

表2 峰值信噪比和采樣率的關(guān)系 dB

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

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

4 結(jié)束語(yǔ)

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

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

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

[3] 李烈辰,李道京.基于壓縮感知的連續(xù)場(chǎng)景稀疏陣列SAR三維成像[J].電子與信息學(xué)報(bào),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ú)線傳感器網(wǎng)絡(luò)中基于數(shù)據(jù)融合樹的壓縮感知算法[J].電子與信息學(xué)報(bào),2014,36(10):2364-2369.

[6] 李少東,楊 軍,陳文峰,等.基于壓縮感知理論的雷達(dá)成像技術(shù)與應(yīng)用研究進(jìn)展[J].電子與信息學(xué)報(bào),2016,38(2):495-508.

[7] 劉 芳,武 嬌,楊淑媛,等.結(jié)構(gòu)化壓縮感知研究進(jìn)展[J].自動(dòng)化學(xué)報(bào),2013,39(12):1980-1995.

[8] 張小亞,張 慧,王紅霞.基追蹤問(wèn)題的近點(diǎn)算法及其應(yīng)用研究[J].計(jì)算機(jī)工程與科學(xué),2016,38(1):120-124.

[9] 張本鑫,朱志斌.全變差圖像恢復(fù)的自適應(yīng)步長(zhǎng)梯度投影算法[J].自動(dòng)化學(xué)報(bào),2016,42(9):1347-1355.

[10] 劉記紅,黎 湘,徐少坤,等.基于改進(jìn)正交匹配追蹤算法的壓縮感知雷達(dá)成像方法[J].電子與信息學(xué)報(bào),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].計(jì)算機(jī)應(yīng)用研究,2013,30(2):402-404.

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

[14] 陳善雄,何中市,熊海靈,等.一種基于壓縮感知的無(wú)線傳感信號(hào)重構(gòu)算法[J].計(jì)算機(jī)學(xué)報(bào),2015,38(3):614-624.

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

[16] 石曼曼,李 雷.基于分段可調(diào)節(jié)OMP算法的圖像壓縮感知算法[J].計(jì)算機(jī)技術(shù)與發(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.