基于稀疏度自適應(yīng)的壓縮感知重構(gòu)算法研究

呂冠男， 劉海鵬， 王 蒙， 盧建宏

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院， 云南 昆明 650500)

壓縮感知(Compressed Sensing，CS)[1-3]是近年來(lái)新興的信號(hào)獲取理論，它表明當(dāng)一個(gè)信號(hào)是稀疏信號(hào)，或者說(shuō)這個(gè)信號(hào)具有稀疏性，就可以用一個(gè)與原信號(hào)不相關(guān)的測(cè)量矩陣，以遠(yuǎn)低于奈奎斯特(Nyquist)采樣率采集到的信號(hào)測(cè)量值進(jìn)行壓縮采樣，用重構(gòu)算法將壓縮采樣后的信號(hào)實(shí)現(xiàn)對(duì)原信號(hào)的高概率重建。壓縮感知具有所需采樣點(diǎn)少、數(shù)據(jù)儲(chǔ)存量低等特點(diǎn)，在信號(hào)采集[4]、雷達(dá)探測(cè)、數(shù)據(jù)通信[5]等領(lǐng)域被廣泛研究。

目前對(duì)壓縮感知理論所做的研究主要集中在信號(hào)重構(gòu)算法上，而貪婪算法由于其計(jì)算結(jié)果的有效性和穩(wěn)定性得到廣泛研究。例如，前向搜索正交匹配追蹤(Look Ahead Orthogonal Matching Pursuit，LAOMP)算法[6]。

雖然LAOMP算法目前已經(jīng)得到了較為廣泛的應(yīng)用，但是LAOMP算法是在稀疏度k已知的條件下進(jìn)行的，同時(shí)選擇的L個(gè)最大內(nèi)積值未必是最佳值，所對(duì)應(yīng)的原子索引也未必是最佳的索引值。因而通過(guò)LAR得到最小殘差也未必是最小的，這就意味著可以在提升LAOMP的重構(gòu)精度上做工作。因此，本文在繼承LAOMP算法優(yōu)點(diǎn)的同時(shí)，對(duì)其不足之處加以改正，提出了一種基于稀疏度自適應(yīng)的回溯前向搜索正交匹配追蹤(Sparsity Adaptive Backtracking Look Ahead Orthogonal Matching Pursuit，SABLAOMP)算法。SABLAOMP算法首先通過(guò)回溯策略選擇能量組最大的原子集，然后將這些能量最大的原子加入到LAR中，根據(jù)殘差性能選擇加入支撐集的原子的個(gè)數(shù)，更新支撐集，更新殘差，自適應(yīng)地更新步長(zhǎng)，使得支撐集中的原子構(gòu)造更加合理，提升了重構(gòu)效果。

1 算法描述

1.1 LAOMP算法

正交匹配追蹤(Orthogonal Matching Pursuit，OMP)算法發(fā)展較早[6]，為后面的各種同類型算法的提出奠定了基礎(chǔ)，它繼承了匹配追蹤(Matching Pursuit，MP)算法在傳感矩陣中挑選原子的方式，由于MP算法在進(jìn)行投影時(shí)，所選用的列向量之間不具備正交性，故而任意一次迭代都可能達(dá)不到理想的結(jié)果。針對(duì)MP算法的缺點(diǎn)，OMP算法作出了改進(jìn)，在投影之前通過(guò)正交化方法對(duì)篩選的原子進(jìn)行正交處理，這樣就能使反復(fù)挑選到同一個(gè)原子的概率幾乎為0，從而保證了每次迭代的最優(yōu)性，不僅能加快算法的收斂速度，同時(shí)還提高了重構(gòu)精度。但是Saikat Chatterjee[7-9]等反復(fù)試驗(yàn)發(fā)現(xiàn)OMP算法每次進(jìn)行原子選擇時(shí)不一定選擇了最優(yōu)原子，于是在OMP算法的基礎(chǔ)上提出了LAOMP算法。

前向搜索殘差[10](Look Ahead Residual，LAR)是LAOMP篩選原子的主要手段。所謂的LAR就是在算法的迭代中，通過(guò)對(duì)未來(lái)迭代的影響來(lái)選擇原子。首先，該算法選擇L個(gè)與傳感矩陣內(nèi)積最大的原子，并將這L個(gè)原子的下標(biāo)存儲(chǔ)在一個(gè)集合;然后把這L個(gè)原子逐個(gè)放入LAR中迭代，L個(gè)原子通過(guò)前向預(yù)測(cè)會(huì)得到L個(gè)殘差，殘差最小的那個(gè)原子就是最佳原子;再把最佳原子加入原子集，更新殘差，進(jìn)行下次迭代，迭代結(jié)束，輸出近似信號(hào)，完成重構(gòu)。

LAOMP算法的核心就是LAR算法，具體描述如下：

輸入：感知矩陣A，測(cè)量向量Y，稀疏度K，先前支撐集Ipre，新選擇的原子索引t。

迭代過(guò)程：

1)迭代次數(shù)k=1：K；

3)更新支撐集Ik=Ipre∪tk；

5)更新殘差rk=Y-AIkΘIk；

6)判斷是否滿足迭代停止條件‖rk‖2>‖rk-1‖2，若滿足，則停止迭代，否則，重復(fù)步驟1—6。

輸出：rk=Y-AIkΘIk。

LAR算法中A={aij}，i∈M，j∈N，Y∈RM，t∈{1，2，…，N}?；贚AR算法中LAR的迭代過(guò)程定義前向預(yù)測(cè)殘差為

r=LAR(Y,A,K,Ipre,t)。

(1)

1.2 SABLAOMP算法

雖然LAOMP算法選出的迭代原子比OMP算法選出來(lái)的質(zhì)量更高，但是LAOMP算法是在稀疏度K已知的條件下進(jìn)行的，同時(shí)選擇的L個(gè)最大內(nèi)積值未必是最佳值，所對(duì)應(yīng)的原子索引也未必是最佳的索引值，因而通過(guò)LAR得到最小殘差也未必是最小的；其次,當(dāng)?shù)啻魏髷?shù)個(gè)殘差性能均能小于τ(定義τ作為判決殘差性能趨于穩(wěn)定的門限值，τ一般取10-6)，如果每次仍然固定的選擇L個(gè)最佳原子加入到LAR中，并且每次仍只選擇一個(gè)殘差值，這樣就增加了迭代的次數(shù)耗費(fèi)了時(shí)間。為了解決這些問(wèn)題，本文提出了SABLAOMP算法，該算法在保證不失LAOMP算法優(yōu)良性能的同時(shí)克服其不足之處。SABLAOMP算法首先通過(guò)回退篩選[11]的思想選擇能量組最大的原子集，再通過(guò)最小二乘法求得此原子集中每個(gè)原子的重構(gòu)系數(shù)θ，選出系數(shù)最大的前L個(gè)原子，并將這些原子一一加入到前向預(yù)測(cè)中，根據(jù)殘差性能選擇加入支撐集的原子個(gè)數(shù)，更新支撐集，更新殘差，自適應(yīng)的更新步長(zhǎng)，判斷是否滿足終止條件，從而輸出結(jié)果。

SABLAOMP算法的核心由回溯策略和LAR子算法組成?；厮莶呗跃唧w操作如下：

輸入：感知矩陣A，測(cè)量值y，稀疏度K。

初始化：矩陣空集A0=?，索引集合Λ0=?，初始?xì)埐顁0=y，迭代次數(shù)t=1，索引值集合J0=?，重構(gòu)值初始化θ=0。

1)利用u=|Art-1|，求得u中K個(gè)較大的值，然后將這K個(gè)值對(duì)應(yīng)的序列號(hào)j構(gòu)成集合J0；

2)更新索引集Λt=Λt-1∪J0，At=At-1∪aj(其中所有的j∈J0)；

4)更新集合Λt=ΛtK，并更新殘差rt=y-Atθt；

5)通過(guò)判斷滿足‖rk‖2>‖rk-1‖2和迭代次數(shù)t≥K來(lái)輸出重構(gòu)系數(shù)θtK和其對(duì)應(yīng)原子索引值ΛtK，否則循環(huán)(1—5)。

輸出：重構(gòu)系數(shù)θtK、θtK對(duì)應(yīng)原子索引值ΛtK。

匹配追蹤(Matching Pursuit)算法、OMP算法、正則化正交匹配追蹤[12](Regularization Orthogonal Matching Pursuit，ROMP)算法以及稀疏自適應(yīng)匹配追蹤[13](Sparsity Adapitive Matching Pursuit，SAMP)算法、LAOMP算法等，都是通過(guò)每一次的迭代來(lái)尋找最佳原子。但是由于數(shù)據(jù)的隨機(jī)不確定性，導(dǎo)致選出來(lái)的原子不一定是最佳原子。因此SABLAOMP算法在此基礎(chǔ)上引入回溯策略，該算法在不需要知道信號(hào)稀疏度的情況下，選擇出最大內(nèi)積值所對(duì)應(yīng)的若干個(gè)原子，然后在這些原子中選擇出能量組最大的原子，將原子的索引值加入到支撐集中，再將這些索引值進(jìn)行LAR處理。由于迭代初期處理后的殘差值相差較大，因此為了得到更好的殘差需要在LAR算法中迭代多次判斷殘差的性能，而隨著迭代次數(shù)的增多，相鄰內(nèi)積值間的差別逐漸縮小再迭代多次已沒(méi)必要，因此本論文選擇的迭代次數(shù)為floor(M/L)次。隨著迭代次數(shù)的增多，L也會(huì)自適應(yīng)的增大，故而迭代次數(shù)就會(huì)減少，正合本文要求。如果經(jīng)過(guò)LAR輸出的殘差值中有f個(gè)值小于τ，那么就將這f個(gè)值對(duì)應(yīng)的F位置加入到支撐集，否則直接將最小的一個(gè)殘差所對(duì)應(yīng)的F中的位置加入支撐集，更新近似系數(shù)，更新殘差，自適應(yīng)的更新步長(zhǎng)，判斷是否滿足終止條件，輸出近似系數(shù)。具體描述如下：

輸入：感知矩陣AM×N，測(cè)量矩陣YM×1，初始步長(zhǎng)S。

初始化：近似系數(shù)Θ=0，初始?xì)埐顁0=Y，支撐集I=?，步長(zhǎng)L=S，pos_theat=。

起始階段：Stage=1，最大循環(huán)次數(shù)Itermax=M，迭代次數(shù)K=floor(M/L)。

迭代過(guò)程：

1)外部循環(huán)次數(shù)k=1：Itermax；

2)A的各列與殘差的內(nèi)積P=ATrk-1；

3)從P中選取L個(gè)具有較大能量的原子所對(duì)應(yīng)的索引序號(hào)，將它們放入支撐集Jl中；

4)內(nèi)部循環(huán)次數(shù)l=1：f，

a)由LAR得到殘差值r=(Y，A，K，pos_theta，Jl)，

b)存儲(chǔ)殘差nf=‖r‖2，

c)根據(jù)殘差值的大小確定更新索引值ik的個(gè)數(shù)；

5)更新支撐集Ik=Ik-1∪ik；

7)存儲(chǔ)支撐集pos_theta=Ik；

8)更新殘差rk=Y-ΘIk；

9)若參數(shù)滿足：‖rk‖2≥‖rk-1‖2或者norm(rk，2)<τ，更新步長(zhǎng)Stage=Stage+1，L=Stage×S；

10)判斷迭代停止條件k≥Itermax或者L>M。

2 實(shí)驗(yàn)部分

以下仿真結(jié)果均在MATLAB R2017a環(huán)境下進(jìn)行得到，稀疏基矩陣和觀測(cè)矩陣[14-15]均選擇小波變換正交基和高斯隨機(jī)矩陣[16-17]。

2.1 一維試驗(yàn)仿真及分析

首先，為了驗(yàn)證本文提出的改進(jìn)算法，即SABLAOMP算法，能否實(shí)現(xiàn)信號(hào)的高精度重構(gòu)，先對(duì)其進(jìn)行一維點(diǎn)目標(biāo)重構(gòu)實(shí)驗(yàn)，其中信號(hào)的個(gè)數(shù)設(shè)置為256，稀疏度K設(shè)定為12，測(cè)量值的個(gè)數(shù)為128，實(shí)驗(yàn)結(jié)果如圖1所示。圖中不帶點(diǎn)的線表示原始信號(hào)，帶點(diǎn)的線表示重構(gòu)信號(hào)，在這個(gè)圖中可以看出帶點(diǎn)線和不帶點(diǎn)線基本是重合的，且重構(gòu)誤差為5.532 5×10-15，算法收斂時(shí)間約為0.17 s。由此可以看出，本文算法可以實(shí)現(xiàn)一維信號(hào)的高精度重構(gòu)。

圖1 SABLAOMP算法的一維重構(gòu)實(shí)驗(yàn)

然后,在不考慮噪聲的情況下，通過(guò)精確重構(gòu)率(ERP)性能指標(biāo)測(cè)試SABLAOMP算法的重構(gòu)性能，并與OMP算法、LAOMP算法、ALAOMP算法對(duì)比。設(shè)原始信號(hào)X為長(zhǎng)度N=700的高斯隨機(jī)信號(hào)和N=500的二值信號(hào)，當(dāng)X為高斯隨機(jī)信號(hào)時(shí)采樣率區(qū)間設(shè)為[0.1，0.2]共11個(gè)點(diǎn)，測(cè)量次數(shù)為200次。當(dāng)X為二值信號(hào)時(shí)采樣率區(qū)間設(shè)為[0.1，0.3]共11個(gè)點(diǎn)，測(cè)量次數(shù)為200次。由于OMP算法、LAOMP算法、ALAOMP算法需要知道信號(hào)的稀疏性，因此設(shè)稀疏度K=20，LAOMP算法的前向參數(shù)設(shè)為L(zhǎng)=5，SABLAOMP算法的初始步長(zhǎng)設(shè)為S≤5，判決門限τ=10-12。對(duì)比結(jié)果如圖2、圖3所示。

圖2 高斯信號(hào)下的ERP對(duì)比圖 圖3 二值信號(hào)下的ERP對(duì)比圖

隨著壓縮率的增大，4種算法的ERP均增大，但本文算法的增大效果更明顯。在高斯隨機(jī)信號(hào)下當(dāng)采樣率相同時(shí)，本文算法的ERP要比其他4種算法效果好，同時(shí)隨著壓縮率的增大ERP增長(zhǎng)的更快，在采樣率達(dá)到0.15時(shí)ERP就已趨近于1(見圖2)，優(yōu)于其他3種算法。而在二值信號(hào)下，由于二值信號(hào)的二值固定性，導(dǎo)致采樣率低于0.16時(shí)效果不明顯(見圖3)，但當(dāng)采樣率高于0.16時(shí)，ERP明顯上升，SABLAOMP算法的ERP在0.24時(shí)就已趨近于1，其他3種算法均未達(dá)到此效果，這充分體現(xiàn)了本文算法的優(yōu)越性。

2.2 二維圖像重構(gòu)實(shí)驗(yàn)比較

為了進(jìn)一步說(shuō)明改進(jìn)后算法的優(yōu)良性，本文給出了OMP算法、LAOMP算法、ALAOMP算法、SABLAOMP算法在采樣率分別為0.3、0.4和0.5時(shí)的二維圖像重構(gòu)直觀視覺(jué)效果對(duì)比圖。仿真結(jié)果如圖4—圖6所示?？梢钥闯?，對(duì)于同一張圖片，隨著采樣率的增加圖像變得越來(lái)越清晰，當(dāng)采樣率為0.3時(shí)圖像相對(duì)來(lái)說(shuō)最模糊，采樣率為0.4時(shí)圖像比采樣率為0.3時(shí)要清晰許多，而采樣率為0.5時(shí)圖像最為清晰；而不論采樣率為何值時(shí)，本文提出的SABLAOMP算法重構(gòu)后的圖像均比其他算法重構(gòu)后的圖像清晰。

(a)原始圖像 (b)OMP重構(gòu)圖像 (c)LAOMP重構(gòu)圖像

(a)原始圖像 (b)OMP重構(gòu)圖像 (c)LAOMP重構(gòu)圖像

(a)原始圖像 (b)OMP重構(gòu)圖像 (c)LAOMP重構(gòu)圖像

以重構(gòu)圖像的峰值信噪比(PSNR)和相對(duì)誤差(RE)作為圖像恢復(fù)質(zhì)量的評(píng)判依據(jù)，不同的采樣率下4種算法的結(jié)果見表1。從表中可知，當(dāng)采樣率固定為某個(gè)值時(shí)，SABLAOMP算法的PSNR最大，RE最小，說(shuō)明SABLAOMP算法的重建質(zhì)量?jī)?yōu)于其他算法；隨著壓縮比的增大，各算法的PSNR均增大，RE均減小，且SABLAOMP的效果最為明顯，其PSNR相比于其他3種算法提高了約25%，而RE相比于其他算法減少量超過(guò)了三分之一。進(jìn)一步說(shuō)明的本算法的重構(gòu)效果優(yōu)于其他3種算法。

表1 壓縮比為0.3時(shí)二維圖像重建質(zhì)量比較

3 結(jié)論

本文就LAOMP的不足之處進(jìn)行改進(jìn)，引入了回溯策略，加強(qiáng)了對(duì)原子的選擇，提出了稀疏度自適應(yīng)的回溯前向搜索正交匹配追蹤算法，即SABLAOMP算法。該算法不需要知道信號(hào)的稀疏度，也不需要確定每次篩選的原子個(gè)數(shù)，只需設(shè)定初始的步長(zhǎng)，通過(guò)回溯策略選出能量最大的若干原子，然后將這些原子加入LAR算法中判斷其對(duì)最終性能的影響效果，通過(guò)判斷選擇殘差性能滿足閾值條件的若干原子加入支撐集，然后進(jìn)行后續(xù)迭代，進(jìn)而判斷是否更新迭代步長(zhǎng)。經(jīng)過(guò)一維點(diǎn)目標(biāo)仿真和二維圖像仿真對(duì)比，發(fā)現(xiàn)該算法的重構(gòu)質(zhì)量明顯優(yōu)于同類算法。但是，在運(yùn)行時(shí)間上SABLAOMP算法并沒(méi)有做到最好。比如在一維信號(hào)重構(gòu)實(shí)驗(yàn)中，SABLAOMP算法的運(yùn)行時(shí)間約為0.17 s，OMP算法的運(yùn)行時(shí)間只有大概0.06 s，ALAOMP算法的重構(gòu)時(shí)間約為0.15 s，但是相比于LAOMP算法約為0.19 s的運(yùn)行時(shí)間還是有所改進(jìn)的。所以說(shuō)，相比于LAOMP算法而言，本文提出的SABLAOMP算法在降低了運(yùn)算速度的同時(shí)還提高了重構(gòu)精度。但這是在運(yùn)行多次求取平均值后獲得的，復(fù)雜度高，速度慢，因此，如何通過(guò)在提高重構(gòu)精度的同時(shí)，保證重構(gòu)速度基本不變，是需要研究的一個(gè)方向。