基于壓縮感知的數據壓縮理論及其重構算法對比研究

李逸川，于峻川，徐紅燕(.中國國土資源航空物探遙感中心，北京 0008；2.地質過程與礦產資源國家重點實驗室，中國地質大學(北京)地球科學與資源學院，北京 0008；.中國地質調查局地學文獻中心，北京 0008)

基于壓縮感知的數據壓縮理論及其重構算法對比研究

李逸川1，2，于峻川1，徐紅燕3
(1.中國國土資源航空物探遙感中心，北京 100083；2.地質過程與礦產資源國家重點實驗室，中國地質大學(北京)地球科學與資源學院，北京 100083；3.中國地質調查局地學文獻中心，北京 100083)

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

壓縮感知；圖像壓縮；重構算法；稀疏性

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

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

1 基本原理

圖1 壓縮感知與傳統信號采樣流程對比圖

Compressive Sensing(CS)理論，即壓縮感知理論又名壓縮傳感理論，是一種隨著信號稀疏性研究不斷深入而發展起來的一種新的壓縮信號采樣理論，可以地采樣率的前提下，對原始信號進行無損重建。眾所周知，傳統的信號壓縮方法主要基于奈奎斯特-香農采樣定理開展，即在保證信號重構精度的前提下，要求采樣速率大于信號帶寬的兩倍[11]。較大的采樣率產生了大量的冗余信息，并使后期壓縮、解壓縮過程效率低下。壓縮感知理論與傳統采樣原理的最大不同在于，壓縮感知理論利用了信號的稀疏性，在對原始信號采樣的同時對其進行一定程度的壓縮(圖1)，使得采樣率遠低于奈奎斯特采樣頻率的情況下，實現信號的精確重構[12]。由于采樣率的降低，一方面降低了對于硬件設施的要求，另一方面節省了數據儲存空間、傳輸的成本和信號重建時間，為該理論在各領域中的廣泛應用提供了先決條件。

2 壓縮感知理論主要構成

2.1 信號的稀疏表示

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

(1)

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

Θ=ΨTX

(2)

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

(3)

選取適當的稀疏基在壓縮感知理論中具有重要的意義，不僅可以降低采樣率，還可以減少儲存和傳輸成本。

2.2 信號的觀測矩陣

Y=ΦΘ

(4)

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

(5)

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

圖2 壓縮感知的矩陣表示

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

2.3 信號重構

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

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

(6)

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

(7)

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

3 重構算法重建仿真及效果評價

3.1 OMP算法對一維信號的仿真實驗

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

首先模擬一個長度為256的完整信號x。其中信號頻率分別為f1=50,f2=100,f3=200，f4=400；采樣頻率fs為800；采樣間隔ts為1/800；采樣序列Ts為1/256；稀疏度N為7。x的完整表達式見式(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進行重建，所得原始信號與重建信號的對比效果如圖3所示。

圖3 OMP算法在采樣率為0.25時對一維信號仿真實驗

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

3.2 OMP算法對二維信號的仿真實驗

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

表1 OMP算法對二維圖像重構的運算耗時及PSNR數值表

圖4中可見隨著采樣率的增加重構圖像效果以及信噪比PSNR的數值均有明顯的提高，且在低采樣率條件下依然能夠對原始信號進行較好的重構。

圖4中可見隨著采樣率的增加重構圖像效果以及信噪比PSNR的數值均有明顯的提高，且在低采樣率條件下依然能夠對原始信號進行較好的重構。

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

圖4 在不同采樣率下OMP算法重構圖像效果圖

圖5 在采樣率為50%時，OMP算法對不同種類影像的重構效果對比圖

表2 OMP算法對二維圖像重構的壓縮率數值表

3.3 各種重構算法的對比仿真實驗

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

GPSR算法作為一種典型的凸優化算法是基于求解最小化L1范數來實現的，其原理是沿梯度方向尋找信號原子，傳統的梯度下降法要求目標函數可微，GPSR的將其轉化為一個二次規劃問題來進行求解，顯著提高了算法的運算速度。

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

為了能更直觀的展示各種算法的重構效果，本文選擇以256px×256 px的標準圖像lena.tiff作為測試對象，在采樣率為0.6的情況下分別利用不同重構算法對其進行重構仿真實驗，實驗結果見圖6。

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

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

圖6 在采樣率為60%時，各算法重構圖像效果對比圖

圖7 不同采樣率下圖像信噪比(PSNR)和計算耗時(TIME)關系圖

4 結束語

詳細介紹了壓縮感知的理論思想和主要框架，利用OMP算法對一維和不同類型的二維影像數據進行仿真實驗，評價了在不同采樣率下OMP算法的對影像的重構效果。對幾種常見的重構算法在不

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

[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].光子學報，2012(1)：82-86.

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

[5] 袁曉玲，馮燕，賈應彪.一種高光譜圖像分布式壓縮感知重構方法[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].北京：北京交通大學，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，First 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%，Finally，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

中國地質調查項目(編號：12120113033031)、(編號：1212011085468)、“高光譜地質調查技術方法研究12120115040801”；地質過程與礦產資源國家重點實驗室科技部專項(編號：MSFGPMR201203)聯合資助

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

TN911.72

A

1004-4051(2015)12-0159-06