基于Dice系數(shù)的變步長自適應(yīng)匹配追蹤算法

張世強，馬 可，張婷娟，黃 雷，宋人杰

(1.國網(wǎng)黑龍江省電力有限公司 伊春供電公司，黑龍江 伊春153000; 2.東北電力大學(xué) 計算機學(xué)院，吉林 吉林132012)

0 引 言

在信號處理領(lǐng)域中，傳統(tǒng)的信號處理方法為奈奎斯特采樣定理，即當(dāng)采樣頻率為信號頻率的2倍時，該信號可以進行無失真的采樣。但是社會對于信號的帶寬需求越來越大，如果繼續(xù)利用奈奎斯特采樣定理進行信號處理，對于信號處理的物理硬件的研究會變得昂貴且復(fù)雜，而壓縮感知(Compressed Sensing，CS)[1]的出現(xiàn)很好地解決了這個問題。壓縮感知理論可以使信號在遠低于奈奎斯特采樣定理要求的采樣頻率下對信號進行采樣，并且?guī)缀鯚o失真地重構(gòu)出原信號。因此壓縮感知也成為當(dāng)下的研究熱點，用于電能信號[2-3]傳輸?shù)妊芯俊?/p>

壓縮感知理論主要分為3部分：第1部分為信號的稀疏化，壓縮感知要求信號必須具有稀疏性，所謂稀疏性是指信號中大部分成分為0或趨近于0，只有小部分含有信號信息。但是自然界中的信號大多不是稀疏信號，因此要對信號進行稀疏處理，信號的稀疏化是壓縮感知理論的前提；第2部分為測量矩陣的設(shè)計，信號通過測量矩陣，就是對信號進行壓縮和采樣。測量矩陣的維度就是信號壓縮后的維度，對測量矩陣的要求是在壓縮矩陣的同時不能丟失信號的重要信息；第3部分為信號重構(gòu)，目的是將壓縮后的信號無失真地恢復(fù)出來，在信號傳輸?shù)倪^程中，信號重構(gòu)是最為重要的一部分，重構(gòu)算法的好壞直接決定了壓縮感知能否應(yīng)用于實踐。

在重構(gòu)算法中，貪婪算法因其算法結(jié)構(gòu)簡單且重構(gòu)性能較好的特點而廣泛應(yīng)用在實際中。其中正交匹配追蹤(Orthogonal Match Pursuit，OMP)算法[4]是貪婪算法中最基礎(chǔ)的算法，該算法利用每次迭代挑選測量矩陣與信號殘差最相關(guān)的原子，用最小二乘法求出最優(yōu)解，進而求出重構(gòu)信號。在OMP的基礎(chǔ)上，研究人員相繼提出了正則化匹配追蹤(Regularization OMP，ROMP)算法[5]，廣義正交匹配追蹤(Generalized OMP，GOMP)算法[6]以及壓縮采樣匹配追蹤(Compression Sample Match Pursuit，CoSaMP)算法[7]。此類算法均有較高的信號重構(gòu)精度，但是都有相同的缺點，即算法必須要在已知信號稀疏度的條件下進行，但是在實際應(yīng)用中，大多數(shù)信號的稀疏度都是未知的，因此此類算法并沒有較高的應(yīng)用能力。針對這個問題，T. Thong提出了稀疏度自適應(yīng)匹配追蹤(Sparsity Adaptative Match Pursuit，SAMP)算法[8]，該算法設(shè)定1個估計稀疏度值和步長，然后通過步長使每次迭代中估計稀疏度都擴充步長大小，直至估計稀疏度與真實稀疏度相似或相等時，利用擴充集中的原子進行估計信號的計算。因此該算法可以在未知稀疏度的條件下對信號進行重構(gòu)，擁有較為廣泛的應(yīng)用前景。

但是SAMP算法仍存在一定缺陷，因為該算法使用固定步長估計稀疏度，因此對固定步長比較依賴，當(dāng)步長設(shè)定較大時，在迭代后期會出現(xiàn)稀疏度過估計的情況，進而影響算法的重構(gòu)性能。當(dāng)步長設(shè)定較小時，則會增加算法的迭代次數(shù)，增加算法的運行時間，降低了SAMP算法的應(yīng)用能力。針對這個問題，提出利用殘差控制步長的方式，將信號殘差分為2個區(qū)間，當(dāng)殘差處在不同區(qū)間時，改變步長使估計稀疏度值可以逐步貼近真實稀疏度，減小稀疏度過估計的可能。同時，利用廣義Dice系數(shù)代替SAMP算法中的內(nèi)積法求取原子相關(guān)性，使求出的相關(guān)性更加準(zhǔn)確。

1 壓縮感知理論框架

壓縮感知的本質(zhì)是信號經(jīng)過測量矩陣后實現(xiàn)信號維度降低的過程，如式(1)所示。

y=Φx

(1)

式中：x為N×1維的信號；Φ為M×N的測量矩陣。其中M

當(dāng)原信號x不是稀疏信號時，需要將信號先進行稀疏化使其變?yōu)橄∈栊盘枺缡?2)所示。

x=Ψα

(2)

式中：α代表稀疏化的信號，如果α中包含K個非0元素(K=N)，或者說α中包含K個數(shù)值較大的元素，剩下的元素趨近于0。就證明經(jīng)過α信號是原信號x通過稀疏基Ψ變換而來的K稀疏信號。

結(jié)合式(1)與式(2)，可以得出壓縮感知理論的通用方法如式(3)所示。

y=Φx=ΦΨα=Aα

(3)

式中：A=ΦΨ稱為感知矩陣。

在得到了壓縮后的信號y后，就可以利用信號重構(gòu)算法，將y恢復(fù)成原信號x，如式(4)所示。

(4)

其中，x為N維且y為M維，因此有x個未知數(shù)求y個解，這本質(zhì)上是一個NP-hard問題，針對這一問題，研究人員大多用基于l0范數(shù)的貪婪算法解決。

2 SAMP算法

SAMP算法是重構(gòu)算法中應(yīng)用最廣泛的算法，因為該算法可以在未知稀疏度的條件下進行對信號的重構(gòu)。SAMP算法在迭代初始階段設(shè)定1個階段數(shù)Stage=1以及步長s，并在開始時將估計稀疏度值設(shè)定為1，每次迭代通過階段數(shù)控制估計稀疏度值的增長，如式(5)、(6)所示。

Stagek=Stagek-1+1

(5)

Lk=Stagek×s

(6)

式中：Lk為估計稀疏度值；Stagek為迭代次數(shù)。

從式(5)和式(6)可以看出，在每次迭代中估計稀疏度值都增加一個步長大小，直到估計稀疏度值與真實稀疏度值相近時，將信號重構(gòu)出來。SAMP具體步驟如圖1所示。

由SAMP的算法步驟可以看出，該算法十分依賴步長的大小，如果步長選擇過大，則會出現(xiàn)稀疏度過估計的情況，影響算法重構(gòu)結(jié)果。為了使估計稀疏度更精確，可以讓步長為1，逐步地增加稀疏度，但這樣也會加大算法的迭代次數(shù)，導(dǎo)致算法運行時間加長，降低了SAMP算法的實際應(yīng)用能力。

輸入:M×N的感知矩陣A=ΦΨ,M×1的測量值y,初始步長s,停止閾值η,階段數(shù)Stage0=1初始化:初始殘差r0=y,支撐集∧0=?,候選集C0=?,初始稀疏度估計值L0=s,迭代次數(shù)k=11)計算原子相關(guān)度u=〈rk-1,A〉,并將前Lk個最大值的列序號加入集合Sk中2)得到支撐集∧k=∧k-1∪Sk3)利用最小二乘法求信號估計值^x∧k=A+∧k·y與殘差 rk-1=y-A∧k·^x∧k4)回溯:在x∧k中選擇Lk個最大值,將這些值對應(yīng)的列序號記錄下來并加入集合F中5)利用F中的原子信息再次求取信號估計值^xF=A+F·y與殘差rnew=y-AF·^xF6)當(dāng)rnew2≥rk-12時,Stagek=Stagek-1+1,Lk=Stagek×s,k=k+1返回步驟1),如果不滿足條件,rnew=rk-1,∧k=F,k=k+1返回步驟4)。7)當(dāng)觸發(fā)rn2<η時,停止迭代,輸出重構(gòu)所得信號估計值^x∧k輸出:信號x的近似估計值^x

3 改進SAMP算法

針對SAMP算法出現(xiàn)的不足，在2個方面做出改進。在貪婪算法中，重構(gòu)信號的質(zhì)量在于每次迭代選擇測量矩陣與信號殘差中相關(guān)原子的準(zhǔn)確性，挑選的原子相關(guān)性越高，重構(gòu)效果越好。但是在SAMP算法中是由內(nèi)積法進行相關(guān)性的計算的。內(nèi)積法就是求2個向量的夾角余弦值，余弦值越大代表2個向量越相似。內(nèi)積法本質(zhì)如式(7)所示，可以看到內(nèi)積法中分母采用的是幾何平均數(shù)，根據(jù)平均值理論，幾何平均值的重點在于表現(xiàn)樣本總體變化趨勢，無法突出樣本中重要信息，因此在匹配過程中會有丟失部分原子信息的情況發(fā)生[9]，導(dǎo)致相關(guān)性計算不準(zhǔn)確，進而影響重構(gòu)結(jié)果。

(7)

針對這一問題，提出利用廣義Dice系數(shù)替換內(nèi)積法來計算原子相關(guān)性。式(8)中展示了廣義Dice系數(shù)的本質(zhì)，可以看出分子部分與內(nèi)積法相同，但在分母中廣義Dice系數(shù)利用算術(shù)平均值代替幾何平均值。在平均值理論中，算術(shù)平均值代表樣本個體期望的無偏估計，因此能更好地保留原子信息。

(8)

圖2為不同相關(guān)性計算方法的結(jié)果對比，將2種計算原子相關(guān)性的方法帶入到基礎(chǔ)的SAMP算法中，除了相關(guān)性計算方法不同，其他的條件完全一致。

圖2 不同相關(guān)度所計算出的殘差

由圖2可以看出，使用廣義Dice系數(shù)的重構(gòu)算法的殘差更快地趨近于0，證明廣義Dice系數(shù)計算的相關(guān)性更加精確。因此，在改進算法中用廣義Dice系數(shù)D〈x,y〉代替內(nèi)積法進行原子相關(guān)性的計算。

sk=「0.5×sk-1?

(9)

Lk=Lk-1+sk

(10)

式中：s為步長；L為估計稀疏度值；「?為向上取整。

由式(9)可知，當(dāng)殘差值處于第二區(qū)間時，步長在每次迭代中減小一半，并按照向上取整處理。這樣可以使步長迅速衰減為1，通過式(10)來計算估計稀疏度，可以看出步長越小，估計稀疏度增長越慢，因此在迭代后期步長減少至1時，可以逐步增加估計稀疏度值，減少稀疏度過估計的可能性。改進算法針對SAMP算法做出兩步改進，具體步驟如圖3所示。

輸入:M×N的感知矩陣A=ΦΨ,M×1的測量值y,初始步長S0,殘差閾值η1,η2,階段數(shù)Stage0=1初始化:初始殘差r0=y,支撐集∧0=?,候選集C0=?,初始稀疏度估計值L0=s,迭代次數(shù)k=11)計算原子相關(guān)度u=D〈rk-1,A〉,并將前Lk個最大值的列序號加入集合Sk中2)得到支撐集∧k=∧k-1∪Sk3)利用最小二乘法求信號估計值^x∧k=A+∧k·y與殘差 rk-1=y-A∧k·^x∧k4)回溯:在x∧k中選擇Lk個最大值,將這些值對應(yīng)的列序號記錄下來并加入集合F中5)利用F中的原子信息再次求取信號估計值^xF=A+F·y與殘差rnew=y-AF·^xF6)當(dāng)殘差rnew2≥η1時,如果rnew2≥rk-12,Stagek=Stagek-1+1,Lk=Stagek×s,k=k+1返回步驟1),如果不滿足條件,rnew=rk-1,∧k=F,k=k+1返回步驟4)。7)當(dāng)η1>rnew2>η2時如果rnew2≥rk-1,sk=「0.5×sk-1?,Lk=Lk-1×sk,k=k+1返回步驟1),如果不滿足條件,rnew=rk-1,∧k=F,k=k+1返回步驟4)。8)當(dāng)rn2<η2時,停止迭代,輸出重構(gòu)所得信號估計值^x∧k輸出:信號x的近似估計值^x

4 仿真實驗

針對所提SAMP的改進算法進行仿真，來驗證其重構(gòu)性能。采用長度為256的高斯隨機稀疏信號作為原始信號，測量矩陣為隨機產(chǎn)生且服從高斯分布的矩陣。所得實驗數(shù)據(jù)均是在4核Matlab2014b的條件下進行500次所取的平均值。

表1為2種算法估計稀疏度與真實稀疏度的差距，為了體現(xiàn)出固定步長的不足，仿真選取步長為3，測量數(shù)M=128。所提算法中殘差閾值分別為η1=10-2，η2=-10-6，SAMP的停止閾值設(shè)為10-6?？梢钥闯?，SAMP算法中估計稀疏度值受限于步長，只能做到貼近真實稀疏度，會出現(xiàn)稀疏度過估計或估計不足的情況。但是所提算法由于迭代后期改變了步長，因此可以做到與真實稀疏度相等，具有較好的重構(gòu)結(jié)果。

表1 估計稀疏度與真實稀疏度的比較Table 1 Comparison between real sparsity and estimated sparsity

表2記錄了所提算法與SAMP算法的平均重構(gòu)誤差對比。仿真選取測量值M∈[115,140]，K=30。其他實驗條件與上一個實驗條件相同?？梢钥闯?，由于使用了變步長的策略以及廣義Dice系數(shù)，因此所提算法的重構(gòu)誤差要遠小于SAMP算法。證明了所提算法在多頻帶信號重構(gòu)上有著更高的重構(gòu)精度。

表2 算法在不同測量值下誤差的比較Table 2 Error comparison of two algorithms under different measured values (×10-14)

表3比較了2種算法的平均運行時間，雖然所提算法使用了變步長的策略，后期步長減小會增加迭代次數(shù)，但是由于使用了廣義Dice系數(shù)計算原子相關(guān)度，因此在原子的選擇上更加精確，可以使算法更快地收斂，因此所提算法的運行速度比SAMP算法高出10%～20%?；诒?和表3可以得出，在一維信號的重構(gòu)表現(xiàn)上，所提算法擁有更好的重構(gòu)性能。

表3 算法在不同測量值下運行時間的比較Table 3 Comparison of running time of algorithm under different measured values s

在驗證了所提算法在一維信號中有較好的重構(gòu)性能后，用二維圖像信號驗證所提算法的普適性，圖4為所提算法與SAMP算法對二維圖像的重構(gòu)結(jié)果。

圖像采用256×256的2張實際電廠圖像[10-11]作為二維信號，稀疏基采用小波稀疏基，仿真中用峰值信噪比(Peak Signalto Noise Ratio，PSNR)來表示重構(gòu)的精度，PSNR值越高代表重構(gòu)效果越好。測量值M=128，所提算法與SAMP算法的步長均為3。圖4表示所提算法與SAMP算法對圖像信號的重構(gòu)結(jié)果，可以看出所提算法的PSNR值相比SAMP算法要高2 dB左右，證明所提算法在圖片的細節(jié)上重構(gòu)得更加精細，重構(gòu)效果更好。

5 結(jié) 語

針對SAMP算法中固定步長會影響估計稀疏度值計算的問題。采取了2種改進方案：

1)用廣義Dice系數(shù)代替原有的內(nèi)積法，使計算出的原子相關(guān)性更準(zhǔn)確。

2)利用殘差控制步長，當(dāng)殘差值處于一定區(qū)間時，逐步減小步長，減少稀疏度過估計的情況。

利用一維信號與二維信號的仿真實驗證明所提算法具有良好的重構(gòu)性能。