李逸川，于峻川，徐紅燕(.中國國土資源航空物探遙感中心，北京 0008；2.地質(zhì)過程與礦產(chǎn)資源國家重點(diǎn)實(shí)驗(yàn)室，中國地質(zhì)大學(xué)(北京)地球科學(xué)與資源學(xué)院，北京 0008；.中國地質(zhì)調(diào)查局地學(xué)文獻(xiàn)中心，北京 0008)

基于壓縮感知的數(shù)據(jù)壓縮理論及其重構(gòu)算法對比研究

李逸川1，2，于峻川1，徐紅燕3
(1.中國國土資源航空物探遙感中心，北京 100083；2.地質(zhì)過程與礦產(chǎn)資源國家重點(diǎn)實(shí)驗(yàn)室，中國地質(zhì)大學(xué)(北京)地球科學(xué)與資源學(xué)院，北京 100083；3.中國地質(zhì)調(diào)查局地學(xué)文獻(xiàn)中心，北京 100083)

壓縮感知作為一種全新的信號采樣理論，一經(jīng)提出便引起廣泛關(guān)注。本文擬在前人研究的基礎(chǔ)上，通過理論研究及仿真實(shí)驗(yàn)對常見重構(gòu)算法進(jìn)行評價(jià)為后續(xù)理論研究及應(yīng)用提供科學(xué)依據(jù)。首先對壓縮感知的理論基礎(chǔ)和主要構(gòu)成進(jìn)行闡述，以貪婪算法中的OMP算法分別對一維信號及不同類型的二維圖像進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明壓縮感知算法可以在較低采樣率下實(shí)現(xiàn)對一維或二維信號的高效重構(gòu)，在采樣率在0.5的情況下，其數(shù)據(jù)的壓縮率達(dá)53%～60%。在系統(tǒng)總結(jié)幾種常見重構(gòu)算法特點(diǎn)的基礎(chǔ)上，以標(biāo)準(zhǔn)測試影像為對象構(gòu)建仿真實(shí)驗(yàn)，分別從重構(gòu)算法的運(yùn)算效率和重構(gòu)質(zhì)量兩個(gè)方面對實(shí)驗(yàn)結(jié)果進(jìn)行評價(jià)，結(jié)果顯示IRLS算法重構(gòu)精度較高，而GPSR算法的運(yùn)算耗時(shí)較短。

壓縮感知；圖像壓縮；重構(gòu)算法；稀疏性

信號采樣是我們獲取數(shù)字信息的第一手段，而傳統(tǒng)的采樣理論要求采樣率必須為信號帶寬的兩倍。為了滿足需求，介質(zhì)的儲存能力被不斷的提升，然而在信息技術(shù)的迅速發(fā)展的背景下，硬件的發(fā)展速度依然無法追趕數(shù)據(jù)增長的速度。另一方面，各領(lǐng)域需求的多樣化更是需要采樣率低，重構(gòu)效果好，計(jì)算效率高的采樣算法。

由Candes、Romberg、Tao和Donoho等人提出的壓縮感知理論[1-2]，為有效的解決上述問題提供了新的途徑。這一理論突破了傳統(tǒng)的奈奎斯特采樣定理的約束，實(shí)現(xiàn)了信號采樣和壓縮過程同時(shí)進(jìn)行，大大提高了壓縮效率。該理論一經(jīng)提出立刻引起了學(xué)界的關(guān)注，目前已應(yīng)用在地球科學(xué)、醫(yī)學(xué)、遙感、天文等多個(gè)領(lǐng)域，尤其在地震勘探成像、遙感影像壓縮等方面的應(yīng)用潛力巨大[3-5]?；謴?fù)重構(gòu)算法作為CS理論中一個(gè)重要部分，對信號壓縮質(zhì)量具有決定性作用，一些學(xué)者提出了眾多的算法，如基追蹤(BP)、匹配追蹤(MP)、SP(子空間追蹤算法)、正交匹配蹤(OMP)、分段正交匹配追蹤(StOMP)、 采樣匹配追蹤(CoSAMP)、子空間追蹤(SP)、正則化正交匹配追蹤(ROMP)、迭代加權(quán)最小二乘(IRLS)、梯度投影稀疏重構(gòu)(GPSR)等[6-10]，探究各算法間的差異及重構(gòu)效果，對壓縮感知在各領(lǐng)域的深入應(yīng)用具有重要意義。

1 基本原理

圖1 壓縮感知與傳統(tǒng)信號采樣流程對比圖

Compressive Sensing(CS)理論，即壓縮感知理論又名壓縮傳感理論，是一種隨著信號稀疏性研究不斷深入而發(fā)展起來的一種新的壓縮信號采樣理論，可以地采樣率的前提下，對原始信號進(jìn)行無損重建。眾所周知，傳統(tǒng)的信號壓縮方法主要基于奈奎斯特-香農(nóng)采樣定理開展，即在保證信號重構(gòu)精度的前提下，要求采樣速率大于信號帶寬的兩倍[11]。較大的采樣率產(chǎn)生了大量的冗余信息，并使后期壓縮、解壓縮過程效率低下。壓縮感知理論與傳統(tǒng)采樣原理的最大不同在于，壓縮感知理論利用了信號的稀疏性，在對原始信號采樣的同時(shí)對其進(jìn)行一定程度的壓縮(圖1)，使得采樣率遠(yuǎn)低于奈奎斯特采樣頻率的情況下，實(shí)現(xiàn)信號的精確重構(gòu)[12]。由于采樣率的降低，一方面降低了對于硬件設(shè)施的要求，另一方面節(jié)省了數(shù)據(jù)儲存空間、傳輸?shù)某杀竞托盘栔亟〞r(shí)間，為該理論在各領(lǐng)域中的廣泛應(yīng)用提供了先決條件。

2 壓縮感知理論主要構(gòu)成

2.1 信號的稀疏表示

壓縮感知的理論前提是原始信號在必須在某一正交空間具有稀疏性。對于任一長度為N的信號X，均可以通過尋找某種稀疏基Ψ實(shí)現(xiàn)信號X的稀疏表示(式(1))。

(1)

式中：θ為變換系數(shù)，Θ為變換系數(shù)向量，即是信號X在Ψ域的表達(dá)，見式(2)。

Θ=ΨTX

(2)

當(dāng)00的情況下，如式(2)系數(shù)滿足，則有式(3)，則說明變換系數(shù)向量Θ在稀疏基Ψ下具有稀疏性。

(3)

選取適當(dāng)?shù)南∈杌趬嚎s感知理論中具有重要的意義，不僅可以降低采樣率，還可以減少儲存和傳輸成本。

2.2 信號的觀測矩陣

Y=ΦΘ

(4)

Υ=ΦΘ=ΦΨΤΧ=ΑCSΧ

(5)

式中：ACS為隨機(jī)投影矩陣。壓縮感知的信號觀測過程如圖2所示。

圖2 壓縮感知的矩陣表示

式(5)中未知數(shù)大于方程個(gè)數(shù)，方程無解。而式中Θ具有K項(xiàng)稀疏性，且ACS具有有限等距性質(zhì)(RIP)，可利用信號稀疏分解理論中已有的分解算法，求出確定解。Candes所提出的RIP理論是壓縮感知測量矩陣的重要約束條件，也是構(gòu)建測量矩陣的關(guān)鍵所在。前人研究指出如果觀測矩陣Φ和稀疏基Ψ的不相干性越強(qiáng)，ACS滿足RIP性質(zhì)的概率越大。而大部分隨機(jī)矩陣與固定正交基之間具有不相關(guān)性，這就決定了隨機(jī)矩陣作為觀測矩陣通常可以滿足ACS的RIP性質(zhì)。通常將測量矩陣分為兩類[13]，一類是隨機(jī)測量矩陣，如高斯隨機(jī)測量矩陣、貝努利測量矩陣、傅里葉隨機(jī)測量矩陣、非相關(guān)測量矩陣等，隨機(jī)測量矩陣對原始信號的恢復(fù)效果較好，但對于硬件的要求較高；另一類是確定性測量矩陣，如托普利茲矩陣，循環(huán)矩陣，結(jié)構(gòu)化隨機(jī)矩陣等。

2.3 信號重構(gòu)

信號重構(gòu)就是將M個(gè)測量值重構(gòu)為長度為N的稀疏信號的過程。重構(gòu)算法的優(yōu)劣決定了重構(gòu)精及運(yùn)算效率，是壓縮感知理論的重要組成部分。如前所述，由于原始信號X是稀疏的，且測量矩陣滿足RIP約束條件，使得式(5)的求解成為可能。根據(jù)Donoho的研究，如果信號X是稀疏的，那么求解欠定方程組Y=ACSX的問題轉(zhuǎn)化為最小L0范數(shù)最小化的非凸最優(yōu)化問題(式(6))。

min‖ΨTX‖0s.t，ACSX=ΦΨTX=Y

(6)

min‖ΨTX‖1s.t，ACSX=ΦΨTX=Y

(7)

最小化L1范數(shù)下求解具有唯一性和穩(wěn)定性等優(yōu)點(diǎn)，對信號重構(gòu)具有重要意義。前人將基于壓縮感知的重構(gòu)算法歸納為以下三類：貪婪算法，如MP、OMP、ROMP、SP、CoSaMP；凸優(yōu)化算法，如GPSR、IHT；非凸優(yōu)化算法，如IRLS。

3 重構(gòu)算法重建仿真及效果評價(jià)

3.1 OMP算法對一維信號的仿真實(shí)驗(yàn)

正交匹配追蹤算法OMP是較早提出的貪婪算法之一，其源于匹配追蹤MP算法，繼承了其原子選擇規(guī)則，且克服了迭代次數(shù)過多的問題，現(xiàn)以O(shè)MP算法為例對一維信號進(jìn)行模擬仿真。

首先模擬一個(gè)長度為256的完整信號x。其中信號頻率分別為f1=50,f2=100,f3=200，f4=400；采樣頻率fs為800；采樣間隔ts為1/800；采樣序列Ts為1/256；稀疏度N為7。x的完整表達(dá)式見式(8)。

x=0.3×cos(2×pi×f1×Ts×ts)+0.6×cos(2×pi×f2×Ts×ts)+0.1×cos(2×pi×f3×Ts×ts)+0.9×cos(2×pi×f4×Ts×ts)

(8)

接下來，對采樣率M/N=0.25的情況下，對該信號x進(jìn)行重建，所得原始信號與重建信號的對比效果如圖3所示。

圖3 OMP算法在采樣率為0.25時(shí)對一維信號仿真實(shí)驗(yàn)

從圖3中可以看出，重構(gòu)信號(圖3(a))與原始信號(圖3(b))具有較高的重合度，重構(gòu)誤差為4.1775E-15。表明OMP算法在較低的采樣率情況下依然能很好的對一維信號進(jìn)行恢復(fù)，且具有很好的收斂性。

3.2 OMP算法對二維信號的仿真實(shí)驗(yàn)

本文選擇256px×256px的標(biāo)準(zhǔn)測試圖像elaine.tiff作為實(shí)驗(yàn)對象，首先利用小波變換對圖像進(jìn)行稀疏分解，通過高斯隨機(jī)矩陣對小波變換后的信號進(jìn)行測量，最后實(shí)現(xiàn)OMP算法對圖像的重構(gòu)。圖4展示了采樣率M/N分別為0.2、0.4、0.6、0.8的情況下，OMP算法對二維信號重建的效果圖，利用峰值信噪比(PSNR)對重構(gòu)質(zhì)量進(jìn)行評價(jià)(表1)，PSNR=10×log(2552/(MSE×M×N))，其中MSE為均方差，M和N分表表示信號的行列數(shù)。

表1 OMP算法對二維圖像重構(gòu)的運(yùn)算耗時(shí)及PSNR數(shù)值表

圖4中可見隨著采樣率的增加重構(gòu)圖像效果以及信噪比PSNR的數(shù)值均有明顯的提高，且在低采樣率條件下依然能夠?qū)υ夹盘栠M(jìn)行較好的重構(gòu)。

圖4中可見隨著采樣率的增加重構(gòu)圖像效果以及信噪比PSNR的數(shù)值均有明顯的提高，且在低采樣率條件下依然能夠?qū)υ夹盘栠M(jìn)行較好的重構(gòu)。

為進(jìn)一步說明壓縮感知算法對于二維影像的數(shù)據(jù)壓縮效果，現(xiàn)將醫(yī)學(xué)中常用的MRI核磁共振影像、鉆孔掃描巖芯影像以及l(fā)andsat衛(wèi)星遙感影像作為測試對象利用OMP算法對其進(jìn)行仿真，試驗(yàn)中M/N采樣率為0.5，圖像均為512px×512 px，由圖5可見，在采樣率僅為0.5的情況下，壓縮感知算法依然能對原始影像進(jìn)行很好的重構(gòu)，且重構(gòu)后的影像壓縮率達(dá)53%～60%(表2)。

圖4 在不同采樣率下OMP算法重構(gòu)圖像效果圖

圖5 在采樣率為50%時(shí)，OMP算法對不同種類影像的重構(gòu)效果對比圖

表2 OMP算法對二維圖像重構(gòu)的壓縮率數(shù)值表

3.3 各種重構(gòu)算法的對比仿真實(shí)驗(yàn)

MP、OMP是早期出現(xiàn)的貪婪算法，相比于基追蹤算法、BP算法具有復(fù)雜度低的特性，OMP算法，通過遞歸的方式把已經(jīng)選擇的原子集進(jìn)行正交化處理有效的減少了迭代次數(shù)獲得更好的收斂性。GBP算法是綜合基追蹤和貪婪算法的優(yōu)勢能夠在觀測點(diǎn)少的情況下實(shí)現(xiàn)低復(fù)雜度的重構(gòu)。SP算法主要結(jié)合了具有回溯順序的編碼理論，且在迭代過程中對候選者的置信度進(jìn)行評估。ROMP 算法的特點(diǎn)是在迭代中進(jìn)行兩次索引，首先找出相關(guān)系數(shù)最大的原子作為候選集，再引入正則化思想，這樣可提高列向量提取的效率，節(jié)省運(yùn)算耗時(shí)。CoSaMP也是基于OMP算法改進(jìn)的一種貪婪算法，其特點(diǎn)是從原子的選擇并非唯一，而是從原子庫擇多個(gè)相關(guān)的原子對其進(jìn)行賽選，從而提高算法效率。

GPSR算法作為一種典型的凸優(yōu)化算法是基于求解最小化L1范數(shù)來實(shí)現(xiàn)的，其原理是沿梯度方向?qū)ふ倚盘栐?，傳統(tǒng)的梯度下降法要求目標(biāo)函數(shù)可微，GPSR的將其轉(zhuǎn)化為一個(gè)二次規(guī)劃問題來進(jìn)行求解，顯著提高了算法的運(yùn)算速度。

非凸優(yōu)化算法(如IRLS)是等距約束性準(zhǔn)則(RIP) 約束下的松弛壓縮感知算法。它的解是很稀疏的，實(shí)際應(yīng)用中非凸優(yōu)化算法重構(gòu)精度優(yōu)于L1范數(shù)重構(gòu)模型，尤其是在采樣率較低的情況下。如果待估變量的稀疏度比較高，其重構(gòu)精度會更好。

為了能更直觀的展示各種算法的重構(gòu)效果，本文選擇以256px×256 px的標(biāo)準(zhǔn)圖像lena.tiff作為測試對象，在采樣率為0.6的情況下分別利用不同重構(gòu)算法對其進(jìn)行重構(gòu)仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見圖6。

由圖6可見，在60%采樣率的情況下，所有算法都能較好的對影像進(jìn)行重構(gòu)，所得重構(gòu)影響信噪比在27～32dB之間，其中IRLS算法所獲得的重構(gòu)圖像的效果最好，與原始圖像最為接近，而GPSR的重構(gòu)圖像效果相對較差(圖6)。從圖7(a)中可見隨著采樣率的增大，各算法的信噪比隨之提高。其中IRLS算法在不同采樣率下均能獲得較好的信噪比，而GBP算法在采樣率較低的情況下能夠獲得較好的信噪比。各貪婪算法OMP、ROMP、SP等重構(gòu)精度較為接近，均優(yōu)于GPSR算法。

從運(yùn)算耗時(shí)上來看(圖7(b))，隨著采樣率的增加各算法的運(yùn)算耗時(shí)也變長。其中，IRLS算法的運(yùn)算耗時(shí)最長，在采樣率較高的情況下，需要耗時(shí)幾十秒。而GPSR算法在運(yùn)算耗時(shí)上表現(xiàn)突出，且在不同采樣率情況下運(yùn)算耗時(shí)較為穩(wěn)定。在在采樣率大于0.4的情況下，ROMP能在相對較短的時(shí)間內(nèi)獲得較好的重構(gòu)質(zhì)量。對于重構(gòu)圖像質(zhì)量的評價(jià)，性噪比具有重要參考意義，然而算法的穩(wěn)定性和運(yùn)算耗時(shí)長短也是不可忽略的因素。因此，對于重構(gòu)算法的選擇要綜合考慮實(shí)際應(yīng)用的需求，如對于信噪比有較高要求，選擇IRLS算法能夠獲得較高的重構(gòu)精度；如對于運(yùn)算耗時(shí)有較高要求可以選擇GPSR算法；如對于二者沒有特殊需求則可以選擇貪婪算法，如ROMP。

圖6 在采樣率為60%時(shí)，各算法重構(gòu)圖像效果對比圖

圖7 不同采樣率下圖像信噪比(PSNR)和計(jì)算耗時(shí)(TIME)關(guān)系圖

4 結(jié)束語

詳細(xì)介紹了壓縮感知的理論思想和主要框架，利用OMP算法對一維和不同類型的二維影像數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，評價(jià)了在不同采樣率下OMP算法的對影像的重構(gòu)效果。對幾種常見的重構(gòu)算法在不

同采樣率下的運(yùn)算耗時(shí)和信噪比進(jìn)行對比分析，重構(gòu)圖像精度越高所耗費(fèi)時(shí)間越長，各算法具有各自的優(yōu)勢，如IRLS算法可獲得較高信噪比的重構(gòu)圖像，而GPSR算法的運(yùn)算耗時(shí)最短，算法的選擇主要取決于實(shí)際應(yīng)用的需求。作為一種新的理論，依然存在很多問題有待于解決。構(gòu)建穩(wěn)定高效的重構(gòu)算法，減少壓縮時(shí)間，提升壓縮效果對壓縮理論在各領(lǐng)域中的應(yīng)用具有重要意義。

[1] Candes E，Tao T.Decoding by linear programming[J].IEEE Trans，Inf，Theory，2005，51(12)： 4203-4215.

[2] Donoho D L.Compressed sensing[J].IEEE Trans，Inf，Theory，2006，52(4)： 1289-1306.

[3] 計(jì)振興，孔繁鏘.基于譜間線性濾波的高光譜圖像壓縮感知[J].光子學(xué)報(bào)，2012(1)：82-86.

[4] 徐明華，李瑞，路交通，等.基于壓縮感知理論的缺失地震數(shù)據(jù)重構(gòu)方法[J].吉林大學(xué)學(xué)報(bào)：地球科學(xué)版，2013(1)：282-290.

[5] 袁曉玲，馮燕，賈應(yīng)彪.一種高光譜圖像分布式壓縮感知重構(gòu)方法[J].電子設(shè)計(jì)工程，2013(14)：181-184.

[6] Mallat S G.Zhang Z.Matching pursuits with time-frequency dictionaries[J].IEEE Transactions on Signal Processing，1993，41(12):3377-3415.

[7] Chen S B，Donoho D L，Saunders M A.Atomic decomposition by basis pursuit[J].Computing，1998，20(1)：33-61.

[8] Tropp J.Greed is good：Algorithmic results for sparse approximation[J].IEEE Trans，on Information Theory，2006，50：2231-2342.

[9] Candes E.Compressive sampling[C]//Proceedings of the International Congress of Mathematicians，Madrid，Spain，2006.[10] Needell D，Tropp J A.CoSaMP：Iterative signal recovery from incomplete and inaccurate samples[J].Appl Comp Harmonic Anal，2009，26(3)：301-321.

[11] Whittaker E T.On the functions which are represented by the expansions of the interpolation-theory[J].Proc，Roy，Soc.，Edinburgh，1915(35):181-94.

[12] Candes E，Romberg J.Quantitative robust uncertainty principles and optimally sparse decompositions[J].Foundations of Comput Math，2006，6 (2)：227-254.

[13] 李小波.基于壓縮感知的測量矩陣研究[D].北京：北京交通大學(xué)，2010.

A theoretical introduction to compressive sensing theory and a comparative studies of reconstruction algorithm

LI Yi-chuan1,2，YU Jun-chuan1，XU Hong-yan3

(1.China Aero Geophysical Survey and Remote Sensing Center for Land and Resources, Beijing 100083,China;2.State Key Laboratory of Geological Processes and Mineral Resources,School of Earth Science and Mineral Resources,China University of Geosciences, Beijing 100083,China;3.China Geoscience Documentation Center.CGS, Beijing 100083,China)

The compressive sensing is a new theory，which attracted wide attentions from the world once it was proposed，In this study，we evaluated the advantages and disadvantages among various reconstruction algorithm through theoretical summary and simulation experiment，aiming at providing theoretical support for the research and application in the future，F(xiàn)irst of all，this thesis systematically summarized the theoretical framework and the main components of Compressive Sensing，and then carried out one-dimensional and two-dimensional simulation experiment by using OMP reconstruction algorithm，The result shows that the Compressive Sensing algorithm can reconstruct the original signal in a high probability even under a low sampling rate，In the case of the sampling rate is 0.5，the compressing rate was achieved to 53%-60%，F(xiàn)inally，in order to estimate the time spent during reconstructing and reconstruction precision of various reconstruction algorithm，we carried out another simulation experiment through standard test image based on the brief summary of the characteristics of these algorithms，The study shows that IRLS algorithm can provide a higher reconstruction accuracy，while the GPSR algorithm costs the minimum time to reconstruct the image.

compressive sensing；image compression；reconstruction algorithm；sparsity

2014-10-22

中國地質(zhì)調(diào)查項(xiàng)目(編號：12120113033031)、(編號：1212011085468)、“高光譜地質(zhì)調(diào)查技術(shù)方法研究12120115040801”；地質(zhì)過程與礦產(chǎn)資源國家重點(diǎn)實(shí)驗(yàn)室科技部專項(xiàng)(編號：MSFGPMR201203)聯(lián)合資助

于峻川(1984-)，男，博士研究生，主要從事遙感地質(zhì)及相關(guān)領(lǐng)域研究工作。E-mail：jasonyu@live.cn。

TN911.72

A

1004-4051(2015)12-0159-06