基于壓縮感知OMP改進算法的圖像重構

郎利影，王 勇，李思騫

（河北工程大學 信息與電氣工程學院，河北 邯鄲 056038）

基于壓縮感知OMP改進算法的圖像重構

郎利影，王 勇，李思騫

（河北工程大學 信息與電氣工程學院，河北 邯鄲 056038）

正交匹配追蹤（OMP）算法中迭代次數(shù)嚴格依賴信號的稀疏度K值，迭代次數(shù)選取適當會重構出高精確的圖像，反之則會對圖像重構質量造成嚴重影響。針對這一問題，提出了一種根據殘差值的相對極差來確定最佳迭代次數(shù)的新方法。該方法要求在同一次迭代中對一幅圖像的所有列同時進行迭代計算，根據極差的相對差值與門限值比較來確定最佳迭代次數(shù)，從而達到提高重構精度，消除對稀疏度K值依賴的目的。理論分析和仿真結果表明，改進的OMP算法比原有算法有更理想的重構效果，有更高的重構精度。

壓縮感知；正交匹配追蹤算法；OMP；信號重構

壓縮感知（Compressive Sensing，CS）理論[1-2]表明，當一信號在某變換基下可稀疏變換時，則可通過采集少量投影值來實現(xiàn)對信號的精確重構[3]。

CS理論關鍵技術主要包含3項：信號的稀疏表示[4]、設計觀測矩陣[5]以及對信號的重構恢復[6]。其中，信號的重構是重要組成部分。在重建算法方面，該理論自提出到現(xiàn)在出現(xiàn)了許多新的算法及改進算法。而貪婪追蹤算法是一種比較經典的重建算法，其主要包括匹配追蹤（Matching Pursuit，MP）[7]、正交匹配追蹤（Orthogonal Matching Pursuit，OMP）[8]及其相關的一些改進算法，如正則化正交匹配追蹤（Regularize Orthogo?nal Matching Pursuit，ROMP）[9]、子空間追蹤算法（Subspace Pursuit，SP）[10]、最優(yōu)正交匹配追蹤（Optimized Orthogonal Matching Pursuit，OOMP）[11]等。

在OMP算法中，迭代次數(shù)嚴格依賴稀疏度K，理論上要求迭代次數(shù)需和原本圖像的稀疏度K值相等，但現(xiàn)實中的稀疏度K卻是未知的。若在觀測端一側增加對稀疏度的計算，則必然會加重編碼段的運算負擔。因此，由于無法對稀疏度進行準確測算，便無法確定合理的迭代次數(shù)，重構質量便也無法得到有效保證。

針對上述問題，提出了一種OMP改進算法，可有效解決對稀疏度的依賴，確定算法中合理的迭代次數(shù)。該方案要求在同一次迭代時對一幅圖像的所有列都同時進行迭代運算，并對殘差值進行極差計算，以所求相對極差值為判據，通過與設定的門限值比較來確定合理的迭代次數(shù)，從而實現(xiàn)圖像的精確重構。

1 CS理論框架

式中：矩陣Φ為M×N維的觀測矩陣。若信號x不是稀疏的，則可通過M×N的變換基ψ=[ ] ψ1,ψ2,…,ψN對其進行稀疏變換，即

式中：s是信號x在變換域ψ下的K稀疏表示。

因此，壓縮感知的過程可以描述為

式中：Θ=Φψ，即傳感矩陣。

由式（1）求解x顯然是一個欠定問題，即無法直接從觀測值y中求出x。但是在滿足式（1）的所有情況中找到具有最稀疏特性的信號即為所求，問題便轉換為P0求解最優(yōu)l0范數(shù)問題

而對式（4）P0的求解卻又是一個NP難題。但CS理論指出，如果觀測矩陣Φ滿足約束等距性RIP[12]（Restricted Isome?try Proper）條件，則可高概率重構原始信號x滿足

研究證明，對于時域可壓縮信號，即信號x滿足式（2）可進行稀疏變換，如果變換矩陣ψ與觀測矩陣Φ不相關，則傳感矩陣Θ=Φψ在很大概率上滿足RIP性質[13]。于是可以把問題進一步轉換為l1范數(shù)來求解，即轉換為通過P1求解的問題

l1范數(shù)最小化問題則可使用基追蹤BP（Basis Pursuit）[14]法求解，并轉換為線性規(guī)劃LP（Linear Programming）問題，通過凸優(yōu)化算法求解。

2 OMP算法

輸入：觀測矩陣Φ，采樣值y，稀疏度K。

輸出：x的K-稀疏逼近x^。

1）令殘差r0=y，索引集Λ0=?，迭代次數(shù)t=1。

2）求殘差r和傳感矩陣的列φj內積中最大值所對應的腳注λ，即

4）最小二乘法求信號近似解

5）更新殘差值

6）判斷t＞K，若滿足則停止迭代；若不滿足則執(zhí)行步驟2）。

OMP算法運用了MP算法中的原子選擇原則，但在迭代中通過遞歸對所選全部原子進行正交化處理，從而減小迭代次數(shù)。

3 OMP改進算法設計分析

3.1 一維信號MSE變化分析

從第2節(jié)OMP算法可知，迭代次數(shù)t的選取嚴格取決于原始信號的稀疏度K。而t的選取是否合適卻又會對圖像重構質量產生嚴重影響。分別對一維信號和二維圖像采用高斯隨機矩陣進行觀測，然后采用OMP算法分別進行重構，并且測出迭代次數(shù)t與均方誤差MSE（Mean Squared Error）和峰值信噪比PSNR的關系。

設其一維信號為

式中：信號頻率 f1=50Hz，f2=100Hz，f3=200Hz，f4=400Hz；采樣頻率 fs=800Hz；采樣間隔 ts=1/fs；采樣序列Ts=1∶256。

從圖1a可以看出：當?shù)螖?shù)t在較小值區(qū)間時，均方誤差MSE均隨著t的增大而減小，相應的一維信號重構質量越來越好。當繼續(xù)增大到一定程度時，MSE值保持平穩(wěn)，此時的重構質量趨于穩(wěn)定。但當t增大到一定數(shù)值時，MSE值驟然增大，且均產生了較大的波動，此時重構的一維信號變差。而且從圖1b還可以看出，在迭代過程中，殘差值的變化趨勢與MSE變化趨勢基本相同，且MSE值產生波動的轉折點恰巧是殘差值產生波動的轉折點。

3.2 二維圖像PSNR變化分析

實驗中，再分別對紋理較復雜的Lena和紋理較簡單的Flower二維圖像進行迭代次數(shù)t和PSNR值變化對比實驗。

圖1 一維信號迭代次數(shù)t與MSE和殘差值關系

從圖2b和圖2d可以看出：在開始階段PSNR增大較快，相應的重構圖像質量越來越好。當t增大到一定程度時，PSNR值均趨于平緩，重構圖像質量趨于穩(wěn)定。但當t繼續(xù)增大到一定數(shù)值時，PSNR值驟然下降，且一直保持著較低值，此時重構圖像質量變得很差。

圖2 不同紋理度的二維重構圖像的PSNR值

3.3 本文方案設計分析

在此引入“極差”的概念，將極差定義為：在同一迭代次數(shù)t時對所有列進行殘差求值，對獲得的最大殘差值和最小殘差值之和進行平均計算。OMP算法中，每一列進行不同次數(shù)迭代的過程中殘差值r是收斂減小的，故隨著迭代次數(shù)的增加，在同一迭代次數(shù)下對不同列所求得的極差值也是收斂減小的。

設M×B維觀測信號y，在不同的迭代過程中，對y的每一列yb運用OMP算法求得的殘差值r均是收斂的，即滿足

式中：rb,t和rb,t+1分別表示第t和t+1次迭代時觀測信號 y的任一列yb產生的殘差值。

基于此，可以推斷出在第t次迭代中，同時對B列觀測信號進行迭代計算，每一列求得的殘差值r，必然滿足

設在第t次迭代中，其B列觀測信號對應的最大殘差值為?t，最小殘差值為ξt，則?t和ξt滿足

則在第t次迭代中，B列觀測值所產生的殘差rb,t均介于最小殘差ξt和最大殘差?t之間，即滿足

對最大殘差值?t和最小殘差值ξt之和求平均值，即求得極差Λt為

由于最大殘差值?t和最小殘差值ξt均收斂減小，故極差Λt亦收斂減小，且能夠較好地反映殘差值的平均變化水平。

對比圖2、圖3可以看出：當?shù)螖?shù)t在較小區(qū)間時，PSNR值增大較快，極差值減小較快；隨著t的增大，在PSNR驟然增大時，極差值驟然下降；但當t增大到一定數(shù)值，PSNR值驟然降低時，極差值亦同時驟然增大；當PSNR值在較低區(qū)間值時，極差值處在較大區(qū)間值。由此可以看出，在迭代過程中，其PSNR值的增減變化趨勢與極差值的增減變化趨勢密切相關，且具有相同的趨勢變化轉折點。

圖3 不同紋理復雜度的極差值與迭代次數(shù)t的關系

為了更準確地求取PSNR增減變化的轉折點，進一步求相鄰兩次迭代運算的極差Λt和Λt+1的相對差值為

式中：Λt和Λt+1分別表示第t次和第t+1次求得的極差值。

通過圖4可以看出，在PSNR值轉折點（圖4a中t=110和圖4b中t=81）之前，極差值d<0，且變化幅度較??；從圖4c、圖4d中可看出，在PSNR值轉折點之后，極差值d<0，變化幅度亦較??；從圖4e、圖4f可看出，在PSNR值轉折點之時，相對差值d產生了較大幅度的跳躍。

圖4 迭代次數(shù)與相對極差值關系

于是可以通過設定一相對極差門限值，在迭代過程中其相對極差值小于此門限值時，則可認為是合理的迭代次數(shù)，此時重構出的圖像質量較高，反之則是不合理的迭代次數(shù)。

3.4 OMP改進算法步驟

Φ為觀測矩陣，y為M×B維采樣值，x^為x的稀疏逼近。

1）令殘差r0=y，索引集Λ0=?，迭代次數(shù)t=1，采樣信號y列數(shù)b=1。

2）求第t次迭代時殘差r和觀測矩陣的列?j內積中最大值，其對應的腳注λ為

3）更新索引集

記錄重建原子集合

4）最小二乘法求近似解

5）更新殘差值

6）判斷b=B，不滿足則執(zhí)行步驟2）；反之則執(zhí)行下一步。

7）求極差

8）求相對極差值

9）與給定門限值δ比較，若dt＞δ則停止迭代，輸出上一次迭代求解值；若dt<δ滿足，則t=t+1，并再回到步驟2）進行下一次迭代。

4 實驗仿真結果

4.1 實驗一：相同采樣率和稀疏度時兩種算法比較

為檢驗改進算法的重構性能，實驗中，在同一采樣率和相同的稀疏度時，對256×256像素大小的二維Cameraman標準圖像運用快速傅里葉變換進行稀疏分解，再分別用兩種算法各自進行150次重構實驗，并計算測量次數(shù)變化過程中的PSNR值和重構誤差率的平均值。實驗中設門限值δ=5，其測試對比結果如圖5、圖6所示。

圖5 兩種重構算法PSNR值比較

圖6 兩種重構算法重構誤差率比較

通過圖5、圖6可以看出，當采樣率和稀疏度一定時，隨著測量次數(shù)的增加重構概率均增大，重構誤差率減小，但改進后的OMP算法在PSNR值和誤差率上比原有算法都有了較大水平的提高，而且測量次數(shù)在小于100的范圍時，OMP改進算法的優(yōu)勢較為凸顯，當大于100時，隨著測量次數(shù)的增大，OMP算法和本文算法的差距趨于減小。

4.2 實驗二：相同采樣率、不同稀疏度時多種重構算法比較

為了驗證稀疏度的改變對此改進算法重構性能的影響，實驗中，又在同一采樣率下（M/N=0.6），對絕對稀疏的0-1隨機信號進行采樣重構，以高斯隨機矩陣作為觀測矩陣，稀疏度K從10開始，每次增大5，運用多種重構算法對每個稀疏度K各進行150次實驗比較，并最后對其求平均值，實驗中設門限值δ=5，實驗結果如圖7所示。

圖7 改變稀疏度時各種重構算法成功率比較

由圖7可以看出，當測量次數(shù)一定時，隨著稀疏度的增大，各種重構算法的重構成功率逐漸減小。當信號稀疏度較大時，對比原有OMP算法本文算法有著較為明顯的優(yōu)勢（如稀疏度K在50時）。與其他重構算法相比，本文算法在重構成功率上也有了較大程度的提高。稀疏度K在30～50之間，效果尤為明顯，比其他重構算法提高了5.71%～27.53%。

4.3 實驗三：相同稀疏度、不同采樣率時多種重構算法效果比較

為了驗證采樣率的改變對改進算法重構效果的影響，實驗中選用Lena標準圖像進行驗證。同時為了提高運算速度，運用分塊壓縮感知方法，先對Lena圖像進行16×16的分塊，再通過加權的高斯隨機矩陣作觀測矩陣，最后對每個圖像分塊進行重構恢復。

實驗中分別選用不同采樣率（M/N）為0.3，0.4，0.5，0.6進行測試，設其門限值δ=1，運用多種重構算法，在同一采樣率下對每種算法反復進行150次試驗，獲得不同情形下的峰值信噪比PSNR值，并對求其平均值，其測試結果如表1所示。

通過表1可以看出，在相同稀疏度時，隨著采樣率的增大，各種算法的PSNR值均相應增大，且在不同采樣率下OMP改進算法的PSNR值都比原OMP算法均有較大程度的提高，在較小采樣率下其優(yōu)勢更為凸顯，在采樣率為0.3，0.4時分別提高了2.36 dB和2.11 dB。同時，與其他重構算法相比，本文算法的PSNR值也有了較大程度的提高。采樣率在0.3～0.6間對比SAMP算法提高了1%～1.83%，對比ROMP算法提高了3.64%～6.59%，此時相應的重構效果也有了較大程度的改善。

表1 不同采樣率各種算法PSNR值比較

圖8是在門限值δ=10，采樣率分別為0.4，0.5，0.6，0.7時，應用OMP改進算法獲得的重構圖像。

圖8 采用OMP改進算法獲得的重構圖像

5 結束語

本文提出了一種OMP算法中確定合理迭代次數(shù)的新方法，通過理論驗證和實驗證明，該方法可有效消除迭代次數(shù)對稀疏度K值的依賴，其重構成功率和重構質量比原有OMP算法和其他重構算法均有了較大程度的提高，重構圖像有了較好的改善。但該方法也存在不足之處，比如該方法會在迭代中增加一定的運算量，相應地會增大其運算復雜度，故在這方面有待進一步研究改善。

[1] DONOHO D.Compressed sensing[J].IEEE Trans.Information Theory，2006，51（4）：1289-1306．

[2] CANDS E.Compressive sampling[J].Proceedings of the Interna?tional Congress of Mathematicians，2006（3）：1433-1452.

[3] BARANIUK R.A lecture Compressive sensing[J].IEEE Signal Processing Magazine，2007，24（4）：118-121.

[4] 王天荊，鄭寶玉，楊震.基于自適應冗余字典的語言信號稀疏表示算法[J].電子與信息學報，2011，33（10）：2372-2377.

[5] 李炳杰，呂園，葉萌，等.基于非相干準則的壓縮感知觀測矩陣設計的極大極小方法[J].空軍工程大學學報：自然科學版，2011，12（5）：81-85.

[6] 吳昊，朱杰.一種用于圖像重構的新型貝葉斯壓縮感知技術[J].信息技術，2012（3）：98-101.

[7] MALLAT S，ZHANG Z.Matching pursuit with time-frequency dictionaries[J].IEEE Trans.Signal Processing，1993，41（12）：3397-3415.

[8] TROPP J，GILBERT A.Signal recovery from random measure?ments via orthogonal matching pursuit[J].IEEE Trans.Informa?tion Theory，2007，53（12）：4655-4666.

[9]NEEDELL D，VERSHYNIN R.Uniform uncertainty principle and signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit[J].Foundations of Computational Mathematics，2009，9（3）：317-334.

[10] DAI W，MILENKOVIC O.Subspace pursuit for compressive sensing[J].IEEE Trans.Information Theory，2009，55（5）：2230-2249.

[11] REBOLLO N，LOWE D.Optimized orthogonal matching pursuit approach[J].IEEE Signal Processing Letters，2002（9）：137-140.

[12] CANDES E，ROMBERG J，TAO T.Robust uncertainty princi?ples：exact signal reconstruction from highly incomplete frequen?cy information[J].IEEE Trans.Information Theory，2006，52（4）：489-509.

[13]TROPP J，GILBERT A C.Signal recovery from random measure?ments via orthogonal matching pursuit[J].IEEE Trans.Informa?tion Theory，2007，53（12）：4655-4666.

[14]CHEN S B，DONOHO D L，SAUNDERS M A.Atomic decom?position by basis pursuit[J].SIAM Journal on Scientific Comput?ing，1998，20（1）：33-61.

Image Reconstruction Based on Improved OMP Algorithm in Compressive Sensing

LANG Liying，WANG Yong，LI Siqian
（College of Information and Electrical Engineering，Hebei University of Engineering，Hebei Handan 056038，China）

The iterative number of Orthogonal Matching Pursuit（OMP）algorithm strictly dependents on the signal sparsity K，and an image can be reconstructed with high precision if the number of iteration is appropriate，on the contrary may severely reduce the quality of the reconstructed image.To solve this problem，a new method is proposed to determine the optimal number of iteration which bases on the relative extreme difference of the residual value.In this method，all the columns of an image is required to iterative calculation simultaneously at the same iteration.The optimal number of iteration is determined by comparing the relative difference and the threshold value，so that the reconstruction accuracy can be improved，and the dependence on the sparsity of K can be eliminated.Theoretical analysis and simulation results show that this improved OMP algorithm not only has better results than the original algorithm in reconstruction，but also has higher reconstruction accuracy.

compressive sensing（CS）；orthogonal matching pursuit algorithm；OMP；signal reconstruction

TN911.73 文獻標志碼：A DOI：10.16280/j.videoe.2015.06.003

【本文獻信息】郎利影，王勇，李思騫.基于壓縮感知OMP改進算法的圖像重構[J].電視技術，2015，39（6）.

河北省自然科學基金項目（F2014402094）

郎利影（1974—），女，博士，教授，碩士生導師，研究方向為人臉識別、模式識別、人工智能；

王 勇（1987—），碩士生，研究方向為模式識別；

李思騫（1989—），女，碩士生，研究方向為人工智能。

時 雯

2014-06-30