王 烈，羅 文，秦偉萌

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

0 引 言

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

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

1 壓縮感知與重構(gòu)算法

1.1 壓縮感知的重構(gòu)模型

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

(1)

(2)

1.2 壓縮感知的重構(gòu)算法

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

2 分段弱選擇自適應(yīng)正交匹配追蹤算法

2.1 對圖像信號的預(yù)處理

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

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

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

2.2 初始步長選擇

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

(3)

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

2.3 原子弱選擇標(biāo)準(zhǔn)

由初始步長得到初始候選集，而初始候選集不能直接重構(gòu)出原信號，本文提出的重構(gòu)算法通過引入弱選擇標(biāo)準(zhǔn)更新候選集，最終重構(gòu)出原信號。

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

{gk≥a·maxgk}

(4)

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

將弱選擇標(biāo)準(zhǔn)引入StOMP中，結(jié)合SAMP的自適應(yīng)性，在不需要已知稀疏度的前提下，利用殘差r和觀測矩陣Φ之間相關(guān)性的差異挑選原子，且通過自適應(yīng)性調(diào)節(jié)閾值大小，更有效表示出原子集，進(jìn)而提升重構(gòu)算法的有效性和穩(wěn)定性。

2.4 算法具體步驟

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

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

輸出：重構(gòu)信號x′。

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

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

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

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

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

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

3 仿真結(jié)果與分析

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

3.1 一維信號的重構(gòu)驗(yàn)證

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

(1)對SWAMP重構(gòu)精度驗(yàn)證，重構(gòu)效果如圖1所示。

從上述實(shí)驗(yàn)可以得出，SWAMP算法能準(zhǔn)確恢復(fù)原信號且相對誤差小。

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

圖1 SWAMP算法重構(gòu)效果

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

從圖2可以看出，隨著稀疏度的增加，各個(gè)算法重構(gòu)成功概率呈現(xiàn)降低的趨勢。當(dāng)K<50時(shí)SWAMP比OMP,ROMP, SP的重構(gòu)效果好，與SAMP的重構(gòu)效果相當(dāng)，當(dāng)K>60時(shí)，SWAMP才會(huì)有較多的信號不能成功重構(gòu)。

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

圖3 同類算法運(yùn)行時(shí)間隨稀疏度的變化情況

從圖3可以看出，SWAMP算法比OMP與ROMP算法耗時(shí)長，與SP耗時(shí)相當(dāng)，比SAMP耗時(shí)短，因?yàn)镾WAMP是雙閾值更新支撐集，故通過增加一定時(shí)間量換取重構(gòu)精度。

3.2 參數(shù)的選取

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

表1 不同的閾值和參數(shù)對算法重構(gòu)質(zhì)量的影響

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

3.3 圖像信號的重構(gòu)

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

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

(2)在采樣率相同的情況下，比較算法之間對不同圖像Lena, Goldhill, Mandrill, Peppers的重構(gòu)質(zhì)量，參數(shù)設(shè)定不變，設(shè)置采樣率為M/N=0.5。實(shí)驗(yàn)結(jié)果見表3。

本節(jié)采用峰值信噪比PSNR(dB)和運(yùn)行時(shí)間TIME(s)作為客觀評價(jià)標(biāo)準(zhǔn)。

表2 不同采樣率下各算法重構(gòu)質(zhì)量比較

表3 采樣率M/N=0.5時(shí)不同圖像重構(gòu)質(zhì)量比較

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

從表3可以得出，對比在相同采樣率下不同圖像的重構(gòu)質(zhì)量，依然可以看出SWAMP算法對比其他算法有更高的PSNR值，重構(gòu)質(zhì)量高，且耗時(shí)短，再次驗(yàn)證本文提出的算法有很強(qiáng)的重構(gòu)能力和很高的運(yùn)行效率，體現(xiàn)了很好的適用性。

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

3.4 對含有噪聲圖像的重構(gòu)

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

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

本節(jié)采用峰值信噪比PSNR(dB)和運(yùn)行時(shí)間TIME(s)作為客觀評價(jià)標(biāo)準(zhǔn)。

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

圖4 不同重構(gòu)算法圖像比較

算法σ=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 對含相同程度的噪聲的不同圖像重構(gòu)質(zhì)量比較

4 結(jié)束語

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