分段弱選擇自適應正交匹配追蹤算法

王 烈，羅 文，秦偉萌

(廣西大學 計算機與電子信息學院，廣西 南寧 530004)

0 引 言

壓縮感知(compressive sampling，CS)[1,2]理論，作為近年來一種全新的理論引起了廣泛的關注。由于傳統的奈奎斯特采樣定律運算時間長，采樣數據量多，存在大量的冗余，且采用先采樣后壓縮的方式，既浪費了傳感器又浪費了采樣和計算的成本和時間。比較之下，壓縮感知針對稀疏信號或者在特定域上的稀疏信號，只需要采樣極少量的信號值，同時對數據進行采集和壓縮，從而減少了軟、硬件的運行成本和時間。這一系列的優勢使得壓縮感知能在信號處理領域有著更廣泛的前景[3]。

壓縮感知理論主要分成3個部分：信號稀疏矩陣的設計部分、觀測矩陣的設計部分和重構算法的設計部分，其中重構算法是壓縮感知理論研究的重要方面[4]，關鍵是如何從低維的數據中快速精確的重構出原始信號。目前重構算法可以大致分為幾個大類：組合優化算法、凸優化算法和貪婪算法等[5]。如李小靜等提出的一種改進的迭代硬閾值算法(MIHT)，是對經典的采用迭代硬閾值方法(IHT)重構信號的改進[6]。如陳小玲等提出的基于梯度投影sEIRLS算法，是對經典的基于迭代加權最小二乘方法(IRLS)重構信號的改進[7]。如孟祥瑞等提出的基于正則化正交匹配追蹤算法的改進(BRAMP)，是對經典的基于正交匹配追蹤算法(ROMP)的改進[8]。如劉杰平等提出的基于DCT頻帶能量的壓縮感知重構算法，通過對圖像分塊DCT后，采用投影Landweber算法對圖像重構[9]。在這些算法中，由于貪婪算法設計結構簡單，運算量小，重構效率高等特點，使得貪婪算法應用最廣[10]。最先經典的貪婪算法是正交匹配追蹤(orthogonal matching pursuit，OMP)[11]，這類算法設計簡單，但在信號重構時會出現過匹配的現象，且重構質量不高；隨后在OMP基礎上提出了一些改進算法，如分段正交匹配追蹤(stage-wise OMP，StOMP)[12]，利用特定閾值通過多次迭代選擇原子更新支撐集來重構原信號，但都需要大量的測量量才能達到較好的效果，故影響了重構效率；稀疏度自適應匹配追蹤(sparsity adaptive MP，SAMP)[13]，雖然能在稀疏度未知的前提下進行精確重構，但SAMP的重構速度較慢，效率低。本文在StOMP算法分段思想的基礎上，通過SAMP的自適應思想和弱選擇標準相結合，提出一種基于分段弱選擇自適應正交匹配追蹤(stage-wise weak selected adaptive matching pursuit，SWAMP)重構算法，該算法首先對原二維信號進行分塊濾波處理，再在各分塊圖像上，通過自適應設定閾值不斷優化初始候選集，利用弱選擇標準不斷更新支撐集，極大提高了重構精度和效率。實驗結果表明，該算法重構復雜度低，重構效果好。

1 壓縮感知與重構算法

1.1 壓縮感知的重構模型

假設原始信號x的長度為N，觀測信號y的長度為M，測量矩陣為Φ的大小為M×N(M

(1)

(2)

1.2 壓縮感知的重構算法

傳統的貪婪算法根據式(2)的最小1-范數問題來精確重構原信號,結合考慮貪婪算法的不同特點,本文重點討論在稀疏度未知條件下的重構算法。分段正交匹配追蹤(StOMP)，一種基于OMP的改進方法，通過設定閾值，從殘差r與觀測矩陣Φ的內積中選取大于設定閾值的一組原子，通過不斷迭代最終逼近原信號。另一個最具代表性的是稀疏度自適應匹配追蹤(SAMP)，在稀疏度K未知的情況下，通過設定一個可變步長，利用自適應性通過殘差判定控制步長大小從而逐步迭代逼近原始信號。利用StOMP與SAMP的突出優勢，引入弱選擇標準，本文提出了采用分段弱選擇自適應正交匹配追蹤算法(SWAMP)，能夠在稀疏度K未知的情況下保證重構信號的有效性和穩定性。

2 分段弱選擇自適應正交匹配追蹤算法

2.1 對圖像信號的預處理

現流行的一些算法，將整幅圖像作為一個整體，故在重構過程中，計算復雜度較高，隨機觀測矩陣存儲量大，且重構圖像質量差等問題，使得這些算法很難實際應用。因此，在2007年GAL.L等提出，將整個圖像分成多個塊，通過針對塊的采樣和重構方法，使得降低計算復雜度，通過引入維納濾波器以消除圖像分塊所導致的塊效應。為了兼顧圖像的重構質量和CS的計算開銷，借鑒BCS-SPL實現技術[16]，本文提出的算法對一個圖像整體進行分塊預處理，后采用維納濾波器消除塊效應，進而提高重構效率。

對于一維信號測量矩陣直接采用高斯隨機矩陣，但對于二維信號，若直接對整體圖像進行稀疏處理，如512×512的圖像信號，則N的長度有106等級，故會影響重構效率。針對CS在二維圖像中的應用限制，采用分塊CS技術(block-based CS，BCS)，把圖像分成B×B塊。使得重構對象不再是512×512大小的圖像整體，而是分塊后B×B大小的塊圖像。

采用Z行掃描技術對二維圖像進行掃描，對掃描后圖像的第i個圖像塊用xi表示，那么有yi=Φψxi。其中測量矩陣Φ的大小為M×B2, 其中B的大小根據圖像的重構速率和重構質量要求綜合決定，本文中取B=32。ψ為稀疏矩陣，本文采用小波變換對信號進行稀疏表示。

2.2 初始步長選擇

在SAMP重構原始信號的過程中，算法的每次迭代都是依據殘差r與觀測矩陣Φ的相關性，挑選步長L個原子最值的角標選為候選集J，通過候選集J重建出信號并計算出與原信號之間的殘差r，再通過殘差判定控制步長進一步選擇更匹配的原子，從而更新候選集，直到滿足停止迭代條件，完成重構。然而，對步長L的選取直接影響到原信號重構的效率和質量，如果步長過大，則可能導致重構失敗[17]，而步長過小，則會影響重構效率。此外，通過步長來選擇原子的方式不能充分體現不同的殘差r與觀察矩陣Φ中各個原子間相關性的差異。

(3)

其中，j∈J。ts的取值范圍為2

2.3 原子弱選擇標準

由初始步長得到初始候選集，而初始候選集不能直接重構出原信號，本文提出的重構算法通過引入弱選擇標準更新候選集，最終重構出原信號。

令g=ΦTr,則g中第k個元素gk就表示原子向量vk與殘差r的內積，即，引入弱選擇參數a，即

{gk≥a·maxgk}

(4)

其中，k∈J,a∈(0,1)。特別的，當a=1時，只選取一個相關性最大的原子角標存入候選集，與OMP相同。SWAMP算法選取所有滿足式(4)的原子對應的角標存入候選集J中，則完成了一次對原子的弱選擇。a值的大小決定選擇原子的個數。當a取值較小時，步長較大，運行效率高，但影響重構質量；而a取值較大時，重構質量較高，但運行效率低。針對本文提出的重構算法，通過驗證不同取值下的重構質量與運行時間，當a=0.8時，重構效果最好。通過弱選擇，使得SWAMP能有效的依據殘差r和觀測矩陣Φ中各相關性的差異選取原子。

將弱選擇標準引入StOMP中，結合SAMP的自適應性，在不需要已知稀疏度的前提下，利用殘差r和觀測矩陣Φ之間相關性的差異挑選原子，且通過自適應性調節閾值大小，更有效表示出原子集，進而提升重構算法的有效性和穩定性。

2.4 算法具體步驟

本節將給出分段弱選擇自適應正交匹配追蹤算法的具體步驟，算法停止迭代條件為殘差值小于ε。

輸入：M×B2維的高斯隨機矩陣Φ，原信號x，參數ts=2.8,a=0.8。

輸出：重構信號x′。

初始化參數：ε=10-6,n=0。稀疏矩陣ψ采用小波稀疏化，Λ、J、x′為空集。

(1)圖像分塊：對原信號x按照Z字形掃描得到掃描后的塊圖像xi，并對塊圖像xi采用維納濾波器消除塊效應，由yi=Φψxi得到對應yi。

(2)原子初選：計算相關性gi=ΦTri(初選時ri=yi)，找出所有滿足式(3)的觀察矩陣的原子角標值j，存入角標集J中。

(4)弱選擇：找出所有滿足式(4)的觀察矩陣的原子角標值k，存入角標集J中，進入步驟(4)。

(5)更新原子支撐集，即Λ=Λ∪J，合并支撐集得ΦΛ。

(9)整合圖像：對輸出的重構塊圖像xi通過逆Z字形掃描整合圖像，得到重構信號xi。

3 仿真結果與分析

以下實驗都是通過MATLAB R2009a版本運行，為了驗證分段弱選擇自適應正交匹配追蹤算法的有效性與精確性，采用兩種方式對算法進行驗證，第一部分采用一維稀疏信號；第二部分采用二維圖像信號。

3.1 一維信號的重構驗證

為了驗證本文提出算法的可行性，本節針對一維信號進行驗證。本節選取隨機生成的長度N=256，稀疏度K=20的高斯信號，觀測矩陣Φ為M×N的高斯隨機矩陣，觀測個數M=128。參數設置：SAMP步長L=128，SWAMP閾值ts=2.8，參數a=0.8。

(1)對SWAMP重構精度驗證，重構效果如圖1所示。

從上述實驗可以得出，SWAMP算法能準確恢復原信號且相對誤差小。

(2)為了驗證SWAMP算法的可行性，本節選取與OMP，SP，ROMP，SAMP同類算法做重構成功概率比較，令K取值0至70，并進行1000次實驗，各算法重構效果如圖2所示。

圖1 SWAMP算法重構效果

圖2 同類算法重構成功概率隨稀疏度的變化情況

從圖2可以看出，隨著稀疏度的增加，各個算法重構成功概率呈現降低的趨勢。當K<50時SWAMP比OMP,ROMP, SP的重構效果好，與SAMP的重構效果相當，當K>60時，SWAMP才會有較多的信號不能成功重構。

(3)為了驗證SWAMP算法的重構效率，本節選取與OMP，SP，ROMP, SAMP同類算法的運行時間比較，令K取值0至40，并進行1000次實驗，各算法耗時如圖3所示。

圖3 同類算法運行時間隨稀疏度的變化情況

從圖3可以看出，SWAMP算法比OMP與ROMP算法耗時長，與SP耗時相當，比SAMP耗時短，因為SWAMP是雙閾值更新支撐集，故通過增加一定時間量換取重構精度。

3.2 參數的選取

為了確定SWAMP中閾值ts與參數a，本節選取大小為512×512的二維圖像Barbara作為原信號。設定采樣率為M/N=0.5，高斯隨機矩陣作為觀測矩陣，令a=0.8時，閾值分別選取ts=2.6,2.7,2.8,2.9,3。再令ts=2.8時，參數分別選取a=0.6,0.7,0.8,0.9,1。本節采用峰值信噪比PSNR(dB)和算法消耗時間TIME(s)作為客觀評價標準，得到仿真實驗結果見表1。

表1 不同的閾值和參數對算法重構質量的影響

從表1可以得出，當采樣率M/N=0.5時，對于參數a，當a>0.6時重構效果好，并且隨著a的增大，運行時間在降低。對于閾值ts，選取不同的閾值重構效果的差異不大，并且隨著閾值的增大，重構時間在降低。綜合重構的質量與運行時間，當選取參數a=0.8，閾值ts=2.8時，SWAMP算法能平衡重構精度與重構效率，重構質量最高。

3.3 圖像信號的重構

對二維圖像信號重構，首先對圖像進行預處理。利用BCS技術，將512×512的圖像分成32×32的塊圖像，并把塊圖像拉直作為向量。對每個向量做一維小波變換稀疏化，測量矩陣選取高斯隨機矩陣。為了驗證本文提出的算法能很好的應用于二維圖像信號，本文提出的算法分別對比迭代硬閾值算法(IHT)，迭代加權最小二乘法(IRLS)，SAMP算法與基于離散余弦變換的平滑投影Landweber重構算法(BCS-SPL-DCT，BSD)。

(1)在同一張圖像Barbara上進行重構對比。采樣率分別設置為M/N=0.3,0.4,0.5,0.6。參數選擇：SAMP步長L=10，BCD塊圖像大小為32×32，實驗結果見表2。

(2)在采樣率相同的情況下，比較算法之間對不同圖像Lena, Goldhill, Mandrill, Peppers的重構質量，參數設定不變，設置采樣率為M/N=0.5。實驗結果見表3。

本節采用峰值信噪比PSNR(dB)和運行時間TIME(s)作為客觀評價標準。

表2 不同采樣率下各算法重構質量比較

表3 采樣率M/N=0.5時不同圖像重構質量比較

從表2可以得出，隨著采樣率的增加，各算法的重構質量也越來越好，其運行時間也不斷增加。SWAMP在同類算法比較中，重構質量最好。當采樣率為0.5時對比各重構算法，SWAMP算法PSNR值相對IHT算法，IRLS算法與SAMP算法分別提高47.48%,12.26%,6.70%。與BSD算法PSNR值相當，但BSD算法通過消耗大量的運行時間換取重構精度，相對BSD算法，本文提出的算法耗時較小。綜合得出，本文提出的算法重構質量好，運行效率高。

從表3可以得出，對比在相同采樣率下不同圖像的重構質量，依然可以看出SWAMP算法對比其他算法有更高的PSNR值，重構質量高，且耗時短，再次驗證本文提出的算法有很強的重構能力和很高的運行效率，體現了很好的適用性。

圖4中所述幾種重構算法都是采用圖4(a)作為源圖像進行圖像重構，得到的重構圖像結果如圖4所示。圖4中得知基于SWAMP重構圖像都能較好的對源圖像進行圖像重構，重構圖像整體良好，圖像邊緣輪廓清晰。比較圖4中不同算法的重構結果，本文所述的方法細節紋理特征突出，手臂的輪廓，人物的圍巾與褲子等細節紋理都明顯優于其他融合算法。其余幾種融合方法中，基于IHT的重構圖像與基于IRLS的重構圖像有明顯的噪聲，基于SAMP的重構圖像整體良好，但細節模糊特別是手臂處呈現鋸齒狀，基于BSD的重構圖像在圖像整體與細節方面優于其余3種算法的重構圖像，但其耗時長，且在細節紋理上不及本文提出的重構算法。故本文提出的方法能較好對源圖像進行重構，且重構圖像整體清晰度較高，視覺效果最好。

3.4 對含有噪聲圖像的重構

(1)在圖像信號中加入高斯噪聲，在含噪環境下，采用不同噪聲程度對同一幅圖像Barbara使用不同算法進行圖像重構。參數選擇：SAMP步長L=10，SWAMP參數a=0.8，閾值ts=2.8，設定采樣率M/N=0.5，設定噪聲是由均值為0，方差分別為σ=0.1,0.01,0.001的高斯噪聲，得到的實驗結果見表4。

(2)采用相同噪聲程度對不同圖像Lena, Goldhill, Mandrill, Peppers使用不同算法進行圖像重構對比，參數設定不變，設置采樣率M/N=0.5，設定噪聲是由均值為0，方差為σ=0.001的高斯噪聲，得到的實驗結果見表5。

本節采用峰值信噪比PSNR(dB)和運行時間TIME(s)作為客觀評價標準。

從表4我們得出，當原圖像引入高斯噪聲時，各算法重構質量下降。當噪聲方差擴大時，各算法重構質量下降明顯。IRLS算法抗噪性最好，隨著噪聲方差擴大，PSNR值衰減最小，但運行時間長。本文提出的算法，隨著噪聲方差的擴大，衰減較明顯，但運行時間短，且重構質量也略好于其它算法。綜合重構質量與運行效率，本文提出的算法在含噪環境下，仍具有很強的重構能力。從表5中，對比不同圖像加入均值為0方差為σ=0.001的高斯噪聲，本文提出的算法PSNR值最好，且運行效率高。綜合比較不同算法的重構質量與重構效率，本文提出的SWAMP算法具有實用性好，抗噪性強，運行效率高的優勢。

圖4 不同重構算法圖像比較

算法σ=0σ=0.001σ=0.01σ=0.1PSNRTIMEPSNRTIMEPSNRTIMEPSNRTIMEIHT15.73800.6215.58800.5615.04650.5714.07490.55IRLS25.691841.2225.031435.7923.422937.6919.035636.39SAMP27.32242.8625.465410.8421.406810.7414.220712.60BSD29.146873.6327.596473.2021.549855.1714.056245.51SWAMP29.28292.7627.00232.6521.59582.6714.68542.67

表5 對含相同程度的噪聲的不同圖像重構質量比較

4 結束語

本文在結合現有的壓縮感知重構算法，借鑒BCS技術對圖像信號進行分塊預處理，以提高重構效率，引入StOMP的分段思想，自適應性調節閾值選取初始候選集，采用弱選擇標準更新支撐集，提出一種分段弱選擇自適應正交匹配追蹤算法，該算法可以在稀疏度未知的前提下，實現精確重構。結合對一維信號的重構實驗結果表明，相較同類算法，綜合重構效率與重構質量本文提出的SWAMP算法優于其他同類算法；結合對圖像信號的重構實驗結果表明，相較不同算法，本文提出的SWAMP算法相對IHT算法，IRLS算法與SAMP算法PSNR值分別提高47.48%,12.26%,6.70%，PSNR值與BSD算法相當，但SWAMP算法運行時間短，重構效率高；且SWAMP算法具有很強的抗噪性。綜合得知，SWAMP算法在重構質量與重構效率上都有很好的效果，具有很強的可靠性與實用性。