一種改進(jìn)的壓縮采樣匹配追蹤算法①

熊曉婷，許學(xué)杰,李素文

(淮北師范大學(xué)物理與電子信息學(xué)院，安徽 淮北 235000)

0 引 言

奈奎斯特采樣定理一直是信號(hào)處理領(lǐng)域的金科玉律，但面對(duì)當(dāng)下海量數(shù)據(jù)信息的爆發(fā)式增長(zhǎng)的形勢(shì)，其性能的缺陷使信道容量、存儲(chǔ)空間和計(jì)算機(jī)處理效率都面臨巨大的挑戰(zhàn)。進(jìn)入二十一世紀(jì)后，數(shù)字信號(hào)處理理論得到了蓬勃的發(fā)展，壓縮感知理論[1]的提出帶來了顛覆性的改變，該理論以遠(yuǎn)小于奈奎斯特采樣定理要求的采樣密度對(duì)信號(hào)進(jìn)行隨機(jī)亞采樣，通過遠(yuǎn)少于傳統(tǒng)采樣定理所需的數(shù)據(jù)量即可高精度重構(gòu)原始信號(hào)。壓縮感知強(qiáng)調(diào)從全局出發(fā)，把信號(hào)的采樣和壓縮階段合二為一，這一特點(diǎn)避免了冗余信息的采集，節(jié)省了資源和時(shí)間，使其在全息成像、語音和通信等領(lǐng)域展現(xiàn)了強(qiáng)大的生命力和廣泛的應(yīng)用前景。

信號(hào)的重構(gòu)算法設(shè)計(jì)是壓縮感知最至關(guān)重要的技術(shù)，算法的優(yōu)劣將直接影響重構(gòu)質(zhì)量的好壞，目前對(duì)重構(gòu)算法的研究主要以貪婪算法為主，貪婪算法主要包括正交匹配追蹤算法(OMP)[2]、正則化匹配追蹤算法(ROMP)[3]、壓縮采樣匹配追蹤算法(CoSaMP)[4]等。為了進(jìn)一步獲得更優(yōu)秀的重構(gòu)質(zhì)量，對(duì)典型貪婪算法的改進(jìn)勢(shì)頭愈發(fā)精益求精。徐志強(qiáng)等人引入隨機(jī)支撐選擇方法，比較迭代生成的概率值決定候選集，以此來減少?gòu)V義正交匹配算法的運(yùn)算量[5]；王麗等人提出了基于粒子群優(yōu)化的快速正交匹配追蹤算法，結(jié)合粒子群的局部選擇最優(yōu)的特點(diǎn)對(duì)算法匹配過程改進(jìn)，進(jìn)而降低了OMP的復(fù)雜度[6]；任曉奎等人在CoSaMP迭代中利用迭代次數(shù)與峰值信噪比的關(guān)系，自適應(yīng)確定迭代次數(shù)，有效提高算法的效率[7]；杜秀麗等人提出了行間支撐集相似度的CoSaMP[8]。這些研究雖然提高了重構(gòu)算法的性能，但僅僅針對(duì)單一信號(hào)進(jìn)行實(shí)驗(yàn)驗(yàn)證，且提高精度有限，基于此提出了μCoSaMP算法，通過對(duì)數(shù)據(jù)域、圖像域的多次仿真并結(jié)合絕對(duì)誤差、成功重構(gòu)概率和峰值信噪比綜合評(píng)估，驗(yàn)證了改進(jìn)算法具有更優(yōu)的重構(gòu)性能。

1 算法描述

1.1 壓縮感知理論

壓縮感知理論指出，只要信號(hào)是稀疏的或者在某一個(gè)變換域中是稀疏的,那么該信號(hào)就可以用一個(gè)觀測(cè)矩陣來測(cè)量，將高維的稀疏信號(hào)降維成低維的觀測(cè)信號(hào)，這就達(dá)到了壓縮的目的，觀測(cè)信號(hào)涵蓋了稀疏信號(hào)最重要的信息，最后再求解一系列的最優(yōu)化問題就能夠以較高的精確度重構(gòu)原始信號(hào)。

(1)

上式中，θ是信號(hào)x在ψ域中的表示，x和θ一一對(duì)應(yīng)。若θ中有K個(gè)不為零或遠(yuǎn)大于零的系數(shù)，而剩下的N-K個(gè)系數(shù)為零或趨向于零，那么信號(hào)x在ψ域上就是K-稀疏的。其中ψ=[ψ1,ψ1,...,ψN]稱為稀疏基。若信號(hào)要稀疏或近似稀疏表示，則需選擇合適的正交或者非正交稀疏基。最常用的稀疏基有離散傅里葉變換基、離散余弦變換基等。因?yàn)殡x散余弦變換能把絕大多數(shù)的信息放置到很少的系數(shù)上，提高了編碼效率，所以本文在圖像稀疏化時(shí)選擇離散余弦變換基作為稀疏基。

獲得稀疏信號(hào)后，就要通過特別的方式采樣。傳統(tǒng)的采樣方式是均勻采樣獲取數(shù)據(jù)，照顧不到全局信息，導(dǎo)致采樣點(diǎn)之間的相關(guān)度高，存在信息冗余，而壓縮感知是從數(shù)據(jù)的全局出發(fā)，通過計(jì)算信號(hào)與一個(gè)觀測(cè)函數(shù)之間的內(nèi)積來獲得觀測(cè)數(shù)據(jù),觀測(cè)數(shù)據(jù)中包含信號(hào)最重要的信息，保證了觀測(cè)值之間的冗余度很低，所以觀測(cè)點(diǎn)的數(shù)目要比奈奎斯特采樣點(diǎn)數(shù)少的多，同時(shí)不影響信號(hào)高精度的恢復(fù)。具體地，假設(shè)x是ψ基下的K-稀疏N維信號(hào)，用一個(gè)與稀疏基不相關(guān)的觀測(cè)矩陣Φ對(duì)該信號(hào)進(jìn)行壓縮觀測(cè)：

y=Φx

(2)

上式中，原始信號(hào)x在采樣過程被壓縮成M維觀測(cè)向量y，觀測(cè)值y包含了原始信號(hào)的關(guān)鍵信息，Φ為觀測(cè)矩陣，大小為M×N，Φ的每一行相當(dāng)于一個(gè)傳感器，它與信號(hào)x有關(guān)，用于獲取信號(hào)的一部分信息。把(1)式代入(2)式得到：

y=Φx=Φψθ=Aθ

(3)

其中，A=Φψ稱為傳感矩陣。常見的觀測(cè)矩陣有隨機(jī)高斯矩陣、部分傅里葉矩陣和部分哈達(dá)瑪矩陣等。基于隨機(jī)高斯矩陣的特點(diǎn)和易實(shí)現(xiàn)性，本文壓縮感知重構(gòu)算法中的觀測(cè)矩陣選擇的是隨機(jī)高斯矩陣。

得到觀測(cè)值y后，從y中重構(gòu)出信號(hào)x是解決一個(gè)線性方程的問題。顯然，從(3)式可以看出，這是一個(gè)欠定方程。但已知壓縮感知理論的約束條件是信號(hào)K-稀疏，同時(shí)矩陣A滿足有限等距性質(zhì)[9]，這就使信號(hào)重構(gòu)成為可能，設(shè)計(jì)巧妙的觀測(cè)矩陣Φ能夠保證方程有唯一解，基于此，壓縮感知重構(gòu)信號(hào)的目標(biāo)函數(shù)可以表達(dá)為：

(4)

式中，‖‖lp是p階范數(shù)，壓縮感知重構(gòu)算法主要恢復(fù)有限維的信號(hào)，所以目前的重構(gòu)算分為兩類：一類是基于迭代的貪婪算法；一類是基于一階范式最小化的凸優(yōu)化算法。凸優(yōu)化算法在很大程度上能提高重構(gòu)精度，但計(jì)算復(fù)雜度高，不適合實(shí)際應(yīng)用。貪婪迭代算法具有簡(jiǎn)單、快捷和復(fù)雜度低等優(yōu)點(diǎn)而被廣泛使用。

1.2 改進(jìn)的重構(gòu)算法

貪婪算法的思想是迭代地從稀疏基中選擇合適的原子使其進(jìn)行線性組合進(jìn)而不斷地逼近觀測(cè)值。OMP算法是在MP算法的基礎(chǔ)上改進(jìn)的，ROMP算法又是在OMP算法改進(jìn)的，其在每次迭代時(shí)選擇多列，一定程度上提高重構(gòu)效率。但正交匹配追蹤算法和正則化正交匹配追蹤算法在迭代時(shí)一旦選擇某個(gè)原子，該原子會(huì)一直存在于索引集中，而在實(shí)際迭代過程中，并不能保證每次選擇的原子都是準(zhǔn)確無誤的，如果某次選擇出現(xiàn)錯(cuò)誤，則在后續(xù)的迭代中該錯(cuò)誤將無法得到修正，甚至造成累計(jì)錯(cuò)誤，進(jìn)而影響重構(gòu)精度。為了解決該問題，順勢(shì)而生的CoSaMP算法在貪婪算法家族里嶄露頭角。

該算法的獨(dú)到之處在于每次選擇的原子可能在下一次迭代時(shí)被剔除，那么初選的錯(cuò)誤原子就可以通過復(fù)選被淘汰，從而使得最終保留下來的原子集合高概率吻合于真實(shí)的支撐集。該算法的本質(zhì)思想是：利用觀測(cè)矩陣各列與殘差的內(nèi)積作為一個(gè)逼近原始信號(hào)x的“橋梁”，該“橋梁”的表達(dá)式如下：

ν=ΦTrt-1=〈ΦT,rt-1〉

(5)

CoSaMP算法在每次迭代時(shí)，都要向“橋梁”確定前K個(gè)最大的原子，以此來逼近原始信號(hào)。顯然從(5)式可以看出，計(jì)算內(nèi)積容易選擇重復(fù)原子，也不能完全反映出“橋梁”要放大重要信息數(shù)據(jù)的能力，因此如何更優(yōu)秀地選擇匹配殘差的原子，是進(jìn)一步提高CoSaMP算法重構(gòu)性能的重點(diǎn)。

基于上述問題，改進(jìn)的CoSaMP算法在選擇原子階段，把“橋梁”ν引入相干性系數(shù)μ，其定義[10]如下：

(6)

其中p和q均為向量，pi表示向量p中的第i個(gè)元素，qi表示向量q中的第i個(gè)元素，(6)式利用p、q的每個(gè)元素來計(jì)算相干性，從而有效地幫助“橋梁”區(qū)分相干性較高的原子，確保初選原子候選集的正確率。同時(shí)，在算法剔除原子階段，把信號(hào)和殘差進(jìn)行加權(quán)以獲得最終的支撐集，確保選擇和剔除原子的標(biāo)準(zhǔn)趨同，具體的算法流程如下：

步驟1：初始化r0=y，預(yù)估計(jì)信號(hào)稀疏度為K，Δ0=?，Q=?，t=1；

步驟2：計(jì)算“橋梁”ν=μΦTrt-1=μ〈ΦT,rt-1〉，μ是引入的相干性系數(shù)，選取ν中前2K個(gè)能量最大的元素，這些元素對(duì)應(yīng)的列序號(hào)組成集合Q，合并Δt=Δt∪Q，按照對(duì)應(yīng)的索引選取的原子組成支撐集ΦΔt；

算法中的終止條件可以描述為下式：

(7)

2 實(shí)驗(yàn)比較與性能分析

2.1 數(shù)據(jù)域的評(píng)估標(biāo)準(zhǔn)

1)絕對(duì)誤差

在數(shù)學(xué)概念中絕對(duì)誤差指的是測(cè)量值與真實(shí)值之差，其計(jì)算簡(jiǎn)單且具有正負(fù)方向性，但信號(hào)是一個(gè)矢量，無法直接比較大小，因此在估計(jì)算法重構(gòu)信號(hào)誤差時(shí)需要對(duì)絕對(duì)誤差進(jìn)行改進(jìn)。首先得到誤差向量：

(8)

δ=‖δ0‖2

(9)

δ值越小說明重構(gòu)信號(hào)與原始信號(hào)之間的誤差越小，重構(gòu)效果越好。

2)成功重構(gòu)概率

如果通過算法恢復(fù)的殘差rt其二范數(shù)值小10-6則認(rèn)為重構(gòu)信號(hào)成功，成功次數(shù)記為P*，定義在有限次迭代次數(shù)下成功重構(gòu)概率為：

(10)

式中，CNT為迭代次數(shù)。

2.2 圖像域的評(píng)估標(biāo)準(zhǔn)

對(duì)于兩幅質(zhì)量差別較大的圖像，人眼能夠輕易的辨別出哪幅圖像質(zhì)量好哪副質(zhì)量差。但當(dāng)人眼無法分辨哪副圖像更勝一籌時(shí)，可以把峰值信噪比PSNR作為評(píng)估重構(gòu)圖像質(zhì)量的指標(biāo)。峰值信噪比常通過均方誤差(MSE)來定義：

(10)

其中，M×N為圖像的尺寸，A(i,j)和B(i,j)表示圖像重構(gòu)前后的數(shù)據(jù)。PSNR常定義為：

(11)

上式中，max表示圖像的最大像素值，PSNR的單位為dB，PSNR值越大，重構(gòu)失真越小。

3 實(shí)驗(yàn)比較與性能分析

3.1 一維信號(hào)的重構(gòu)結(jié)果

本實(shí)驗(yàn)選用rand()函數(shù)生成長(zhǎng)度N=256的隨機(jī)信號(hào)，觀測(cè)值M=64，稀疏度K=12，迭代次數(shù)CNT=100，μCoSaMP算法與CoSaMP算法平均重構(gòu)結(jié)果如圖1所示。

圖1 μCoSaMP算法和CoSaMP算法平均重構(gòu)結(jié)果

取迭代次數(shù)CNT=1000，稀疏度K分別取4、12，測(cè)量數(shù)與成功重構(gòu)概率關(guān)系曲線如圖2所示。

圖2的橫軸為測(cè)量點(diǎn)數(shù)，縱軸為信號(hào)成功重構(gòu)概率。從圖中可以看出，對(duì)于原始算法和改進(jìn)算法，信號(hào)成功重建概率均隨著觀測(cè)點(diǎn)數(shù)的增加而增大。當(dāng)K=4時(shí)，改進(jìn)算法在M=30的成功重構(gòu)概率接近1，而原始算法所需的觀測(cè)點(diǎn)數(shù)至少需要40；當(dāng)K=12時(shí)，改進(jìn)算法在M=55的成功重構(gòu)概率接近1，明顯少于原始算法所需的觀測(cè)點(diǎn)數(shù)；通過對(duì)比不同稀疏度下兩種算法的成功重構(gòu)概率發(fā)現(xiàn)，K=4的成功重構(gòu)概率誤差比K=12的要大很多，這意味著相對(duì)于原始算法，改進(jìn)算法在K=4時(shí)的重構(gòu)性能優(yōu)越性更大。因此，改進(jìn)算法成功重建信號(hào)的穩(wěn)定性更強(qiáng)，且信號(hào)越稀疏，性能優(yōu)勢(shì)越明顯。

圖2 測(cè)量數(shù)與成功重構(gòu)概率關(guān)系曲線

(a)原圖 (b)μCoSaMP (c)CoSaMP

(a)原圖 (b)μCoSaMP (c)CoSaMP

基于對(duì)平均重構(gòu)結(jié)果和測(cè)量數(shù)與成功重構(gòu)概率關(guān)系曲線的分析，改進(jìn)的壓縮采樣匹配追蹤算法在重構(gòu)一維信號(hào)上具有重構(gòu)精確度高和魯棒性強(qiáng)的特點(diǎn)。

(a)原圖 (b)μCoSaMP (c)CoSaMP

(a)原圖 (b)μCoSaMP (c)CoSaMP

3.2 二維圖像的重構(gòu)結(jié)果

本實(shí)驗(yàn)先采用離散余弦變換基作稀疏處理，再采用隨機(jī)高斯矩陣進(jìn)行觀測(cè)降維，最后采用CoSaMP算法和本文提出的μCoSaMP算法分別對(duì)Lena圖像和Vegetables圖像進(jìn)行重構(gòu)，比較兩種算法在各采樣率(M/N)下的PSNR值如表1所示。

表1 不同采樣率下圖像重構(gòu)的PSNR值比較

從表1的數(shù)據(jù)看出，雖然兩種算法都能成功恢復(fù)實(shí)驗(yàn)圖像，但是不論在何種采樣率下μCoSaMP算法重構(gòu)的PSNR值均不同程度的高于CoSaMP算法，當(dāng)采樣率為0.5或低于0.5時(shí)，這種差距更加明顯。圖3至圖6分別為兩幅實(shí)驗(yàn)圖像在不同采樣率下重構(gòu)圖像對(duì)比，以便直觀地分析改進(jìn)算法的重構(gòu)優(yōu)勢(shì)。

從圖3和圖5中，能清晰地觀察出在采樣率為0.8下兩種算法重構(gòu)的圖像失真小，圖像細(xì)節(jié)紋理處無明顯顆粒，帽沿線條和蔬菜輪廓清晰；但采樣率降低為0.4時(shí)，從圖4和圖6中看到重構(gòu)圖像失真現(xiàn)象明顯，相對(duì)于CoSaMP算法而言，改進(jìn)算法的重構(gòu)圖像人物五官和蔬菜邊緣的模糊程度要低?；谏鲜霾煌貥?gòu)算法對(duì)二維圖像重構(gòu)質(zhì)量的分析，低采樣率下改進(jìn)的壓縮采樣匹配追蹤算法的重構(gòu)效率更高，重構(gòu)質(zhì)量更優(yōu)，避免了時(shí)間和硬件資源的浪費(fèi)。

4 結(jié) 語

通過對(duì)壓縮采樣匹配追蹤算法性能的分析，提出了μCoSaMP算法，選擇原子階段引入相干性系數(shù)，改變內(nèi)積原則，提高初選原子準(zhǔn)確率，同時(shí)提出在剔除原子階段將信號(hào)和殘差加權(quán)的思想，保證選擇與剔除標(biāo)準(zhǔn)一致，準(zhǔn)確估計(jì)支撐集。從對(duì)一維隨機(jī)信號(hào)、二維圖像的重構(gòu)實(shí)驗(yàn)結(jié)果可以得出，μCoSaMP算法比CoSaMP算法在絕對(duì)誤差、成功重構(gòu)概率和峰值信噪比上都有較大的優(yōu)勢(shì)，因此μCoSaMP算法具有重構(gòu)精確度高和魯棒性強(qiáng)的特點(diǎn)。但值得思考的是，μCoSaMP算法也需要同CoSaMP算法一樣把已知信號(hào)的稀疏度作為先驗(yàn)條件，在實(shí)際情況下往往無法預(yù)知信號(hào)的稀疏度，因此進(jìn)一步的設(shè)計(jì)稀疏度自適應(yīng)的μCoSaMP算法是接下來研究的重點(diǎn)內(nèi)容。