詹可軍，宋建新

(南京郵電大學圖像處理與圖像通信實驗室，江蘇南京210003)

隨著信息科技的不斷進步，人們對信息的需求日益增加，需要處理和保存的數(shù)據(jù)量越來越多，在信息的采樣和壓縮過程中對采樣速度和處理速度的要求也越來越高。當前常用的視頻編碼標準，如MPEG－X，H.264等，通過使用預測編碼和可變長編碼減少了幀間的冗余度，很大程度上提高了壓縮效率。但以上基于奈奎斯特采樣定律的視頻壓縮標準也有其局限性:1)先采樣、后壓縮，在采樣的過程中由于要遵循奈奎斯特采樣定律，必然導致產(chǎn)生過多的采樣數(shù)據(jù)要存儲，尤其是對視頻信號的采樣，而龐大的數(shù)據(jù)量必然會對存儲設備提出更高的要求。2)這類視頻編碼方法產(chǎn)生的視頻編碼數(shù)據(jù)對差錯非常敏感，有時一個比特的差錯都有可能造成解碼質量的嚴重下降甚至無法解碼，當傳輸?shù)难舆t、丟包和抖動超過一定值時，視頻質量將會迅速下降。基于這些缺點，近幾年由D Donoho、T Tao等人提出壓縮感知(Compressive Sensing，CS)［1－3］理論，該理論突破了奈奎斯特采樣定律的限制，其主要思想是構造適當?shù)臏y量矩陣對稀疏信號以遠低于奈奎斯特采樣頻率進行多次隨機測量，如果測量過程滿足約束等距性(RIP)［4］條件，就能通過適當?shù)闹貥嬎惴◤臏y量數(shù)據(jù)中恢復出原始信號。由于測量值的數(shù)目遠小于原始信號的數(shù)目，另外壓縮感知理論將采樣和壓縮在一個過程中同時完成，因此待編碼的數(shù)據(jù)量就大大減少，也就降低了對存儲設備的要求。其次，由CS理論可知，測量數(shù)據(jù)中的每個值都包含原始信號的所有信息，因此每個測量值對信號的重構來說是等重要性的，因此重構信號的質量只和重構過程中用到的測量值個數(shù)有關，而與具體的哪幾個測量值無關，這樣在接收端收到的測量值越多，重構出的信號質量就越高，視頻編碼數(shù)據(jù)關于信道質量具有很好的可伸縮性。

CS理論突破了奈奎斯特采樣定律，如果將其應用到實踐中，那么信號的采樣和壓縮都可以以很低的速率進行，這將顯著提高編碼效率，降低數(shù)據(jù)存儲和傳輸?shù)拇鷥r，以及信號的處理時間傳輸成本。壓縮感知理論一經(jīng)提出，就在醫(yī)學成像、無線通信、圖像處理、信號稀疏表示、多媒體編碼等領域受到高度關注。

1 壓縮感知基本理論

信號在某些變換基下具有稀疏性是壓縮感知的前提條件，如果一個信號X∈RN能夠在某些稀疏基ΨN×N=［ψ1，ψ2，…，ψN］下稀疏表示為

寫成矩陣的形式為

如果稀疏系數(shù)α∈R N中只有S?N個非零值，那么就說該信號在基Ψ下是S稀疏的。壓縮感知的采樣過程是用一個和稀疏基Ψ不相干的測量矩陣Φ(M×N)(這里Φ的每一行相當于一個傳感器，它與原始信號相乘，獲得原始信號的一個測量值)和信號X∈R N相乘，即

則可以得到原始信號在測量矩陣上的M個投影，其中每一個線性投影都包含了原始信號的全部信息，因此這M個投影值是同等重要的。

將式(2)代入式(3)可得

式中:ACS=ΦΨ。由于M＜N，所以壓縮感知采樣是一個降維過程，由測量值y恢復原始信號X是一個解線性方程組問題，但是不可能直接得到方程的解，因為該方程的未知數(shù)個數(shù)比方程的個數(shù)要多，有無窮多解。雖然從y中恢復α是一個病態(tài)問題，但是由于稀疏系數(shù)α是稀疏的，其中存在很多零值，因此未知數(shù)個數(shù)也就相應地大大減少，使得由y重構成α成為可能。理論證明，只要矩陣ACS中任意2S列是線性獨立的，就存在一個S稀疏的向量α使得y=ACSα成立。

當信號滿足在基Ψ下具有稀疏性，且測量矩陣Φ和Ψ滿足不相干性，那么壓縮感知理論就可以通過求解以下l0范數(shù)問題來重建原始信號

但是求解以上l0范數(shù)問題是一個NP－h(huán)ard的非凸優(yōu)化問題，理論證明［5－6］，在一定條件下求解l1范數(shù)等價于求解l0范數(shù)問題，因此可將上面求解過程轉化為下面的l1范數(shù)求解過程

這樣就將式(5)轉化為一個凸優(yōu)化問題，進一步可以轉化為線性規(guī)劃問題來求解。目前常用的重構算法有:基于貪婪算法的匹配追蹤(MP)［7］、正交匹配追蹤(OMP)［8］、正則化的正交匹配追蹤(ROMP)［9］、壓縮采樣匹配追蹤(CoSaMP)［10］等算法;基于凸優(yōu)化算法的梯度投影算法(GPSR)［11］、基追蹤(BP)、迭代硬閾值(IHT)等算法;基于Bayesian類統(tǒng)計優(yōu)化等算法［12］。

2 測量矩陣及其性能

2.1 測量矩陣的性能

測量矩陣的構造是壓縮感知的關鍵部分，由于壓縮感知理論中信號的測量過程就是用測量矩陣和稀疏信號相乘，因此測量矩陣的好壞直接影響到重構出來信號質量的好壞。研究測量矩陣所需滿足的性質和構造性能優(yōu)越的測量矩陣一直是壓縮感知理論研究的重點。測量矩陣所需滿足的性質主要有兩點:不相干性和約束等距性(RIP)。構造性能優(yōu)越的測量矩陣主要是指在達到相同的重構信號質量的前提下，要使所選的測量矩陣只需測量更少的數(shù)據(jù)即可實現(xiàn)重構要求。通常在選擇測量矩陣時要盡量滿足以下3個條件:1)用該測量矩陣測量時只需要較少的數(shù)據(jù);2)便于硬件實施;3)普遍適用。

影響測量矩陣性能的因素主要有兩個:不相干性和約束等距性。測量矩陣和稀疏基之間的相干性定義為

相干性用來衡量隨機測量矩陣和稀疏基之間任何兩元素間的最大相關性，如果測量矩陣和稀疏基之間包含了相關元素，相干性M就大，反之就小，相干性μ的取值范圍為μ(Φ，Ψ)∈［1，］。

在利用式(4)求解稀疏系數(shù)的過程中，測量矩陣不僅要滿足不相干性還要滿足約束等距性，用公式來表述RIP性質為

式中:v表示任意具有嚴格K稀疏的矢量;δk為等距常數(shù)，取值范圍為δk∈(0，1)。約束等距特性給出了原始信號X和測量信號y的能量約束條件，保證了信號從一個域變換到另一個域收斂不發(fā)散。RIP的等價描述為:測量矩陣和稀疏基之間不相干，即Φ的行不能由Ψ的列線性表示，且Ψ的列不能由Φ的行線性表示。

2.2 常用測量矩陣

目前常用的測量矩陣有很多，在不同的文獻中經(jīng)常會碰到不同的測量矩陣，但總體來說目前常用的測量矩陣可以分為兩類:隨機性測量矩陣和確定性測量矩陣。

Candes和Romberg等學者構造出了常用的隨機性測量矩陣，這類矩陣主要有高斯隨機測量矩陣、伯努利測量矩陣、部分傅里葉測量矩陣、部分哈達瑪矩陣、非相關測量矩陣等，這類矩陣已被證明滿足RIP性質，這類矩陣由于和絕大部分信號不相關，因此在相同的重構質量要求下只需較少的測量值即可實現(xiàn)，而且構造簡單，因此在實際中應用很廣泛，但是這類矩陣也有其固有缺點，就是其元素具有不確定性，所需的存儲空間較大，不利于硬件實現(xiàn)。

由于隨機性測量矩陣存在諸多缺點，因此有學者就提出了確定性測量矩陣的概念，目前常用的確定性測量矩陣有利用元素循環(huán)移位來構造的托普利茲測量矩陣和循環(huán)測量矩陣，利用多項式方法來構造的多項式測量矩陣，還有二進制稀疏測量矩陣、結構化隨機測量矩陣等。顧名思義，這類矩陣只需一小部分元素即可確定剩余的大部分元素，因此所需的存儲空間少，確定性測量矩陣的另一個優(yōu)勢就是由于其元素的確定性，因此在硬件實現(xiàn)方面容易實現(xiàn)，因此得到很高的關注。由于本文的最終目的是將壓縮感知理論應用于實際生活中，因此以后的研究重點也會偏向于確定性測量矩陣。

下面將對目前常用的幾種測量矩陣進行性能比較，主要比較使用率較高的高斯隨機矩陣、部分哈達瑪矩陣、托普利茲矩陣、伯努利矩陣和稀疏隨機矩陣。

2.3 本文實驗方案

本文實驗方案的主要思想是將讀入的圖像分為n×n不重疊的小塊，然后對每個塊用相同的壓縮感知測量與重構方法進行編解碼。處理流程如圖1所示。

圖1 本文圖像處理流程圖

在圖1中，主要對塊大小分配模塊、測量率分配模塊、壓縮感知測量模塊分別進行變量測試。分別統(tǒng)計在不同圖像分塊大小n×n、不同測量率(M/N)和不同測量矩陣的條件下重構信號的峰值信噪比、重構時間和視覺質量。通過對實驗數(shù)據(jù)的分析對比，得出分塊大小、測量率、測量矩陣對壓縮感知信號重構的影響。

3 實驗結果與分析

本節(jié)主要對目前常用的幾種測量矩陣進行詳細的性能分析和比較，參與分析比較的幾種矩陣為高斯隨機矩陣、部分哈達瑪矩陣、托普利茲矩陣、伯努利矩陣、稀疏隨機矩陣。主要從以下幾個方面對這幾種矩陣進行分析比較:不同測量率下的峰值信噪比(PSNR)、不同測量率下的重構時間(time)、主觀視覺質量。由于本文所采用的編碼方法是基于分塊的處理方法，所以將不同分塊大小(n×n)對重構信號的影響也考慮在內(nèi)。仿真圖像為255×255的Lena圖像，仿真環(huán)境為Windows7操作系統(tǒng)，CPU主頻為2.2 GHz，運行軟件MATLAB2010b。由于這幾種矩陣每次產(chǎn)生都有一定的隨機性，因此本實驗的所有實驗結果都是運行100次后的平均值，另外，本文的實驗數(shù)據(jù)都是采用正交匹配追蹤(OMP)算法得出的結果。首先用8×8的分塊大小來研究不同測量矩陣的性能。

實驗中所用的測量率從低到高依次為25%，37.5%，50%，62.5%，75%，從圖2可以看出在25%測量率時，各測量矩陣重構信號的PSNR相差不大，基本都在25～26 dB，但當測量率提高時，各測量矩陣重構圖像的PSNR有較大的差異，比如在測量率為37.5%時，稀疏隨機矩陣的結果和隨機高斯矩陣的結果相差2 dB左右，在測量率為75%時，部分哈達瑪矩陣和稀疏隨機矩陣的結果也相差2 dB左右。從總體上來看，部分哈達瑪矩陣的重構效果比較均衡穩(wěn)定，要好于其他幾種矩陣。下面再從重構時間上來比較幾種測量矩陣的性能。

圖2 分塊大小為8×8時不同測量率下幾種測量矩陣重構信號的PSNR

從表1可知，在8×8的分塊大小下，幾種測量矩陣的重構時間基本在同一數(shù)量級，總體上都在0.8～1.0 s之間，區(qū)別不大。下面的實驗結果是在測量率為50%時，各個測量矩陣重構出來的圖像的視覺效果。

表1 不同測量率下幾種測量矩陣重構信號所需時間

從圖3可以看出，在測量率為50%，分塊大小為8×8時，幾種測量矩陣重構出來的圖像視覺效果都不是很清晰，模糊效果較為嚴重，相比之下，哈達瑪矩陣和托普利茲矩陣的重構效果相對清晰于其他幾種矩陣。

由于實驗方案是將圖像基于塊進行處理的，下面分析一下分塊大小對實驗結果的影響，從上面的幾組數(shù)據(jù)可以看出，哈達瑪矩陣的性能相對來說要好于其他幾種矩陣，因此就以哈達瑪矩陣為測量矩陣來分析分塊對實驗結果的影響，其中測量率定為50%。表2是分塊大小分別為8×8，16×16，32×32，64×64時哈達瑪矩陣重構出圖像的PSNR和重構時間。

圖3 測量率為50%，分塊大小為8×8時各測量矩陣重構圖像的視覺效果

表2 測量率為50%時不同分塊大小下部分哈達瑪矩陣重構信號的PSNR和重構時間

從重構圖像的PSNR來看，分塊大小為8×8時效果最好，比其他分塊大小要高出1～2 dB，而分塊大小為16×16，32×32，64×64時重構效果基本相同，區(qū)別不大。從重構時間方面來看，分塊大小為8×8時的重構時間略長于分塊大小為16×16時的重構時間，總體趨勢是隨著分塊大小的增大，所需的重構時間越長，當分塊大小為64×64時重構時間已經(jīng)是分塊大小較小時重構時間的4倍左右。從以上分析可以看出，分塊大小為8×8時具有最佳的重構效果。

4 總結

本文對目前幾種常用的測量矩陣的性能做了一個全面的分析與比較，從重構圖像的PSNR、重構時間、視覺效果等方面做了綜合對比，總體來說，哈達瑪矩陣和托普利茲矩陣相對好于其他幾種矩陣，其他幾種矩陣的性能基本上沒有多大差異。另外本文還對不同分塊大小對壓縮感知重構信號的影響做了分析，從實驗結果來看，綜合考慮重構圖像的PSNR和重構時間，分塊大小為8×8時可獲得最佳的重構效果。

［1］ DONOHOD.Compressed sensing［J］.IEEE Trans.Information Theory，2006，51(4):1289－1306.

［2］ CANDESE.Compressive sampling［J］.Proceedings of the International Congress of Mathematicians，2006(3):1433－1452.

［3］ DONOHO D，TSAIC Y.Extensions of compressed sensing［J］.Signal Processing，2006，86(3):533－548.

［4］ DONOHO D.Formost large underdetermined systems of linear equations the minimal l1－norm solution is also the sparsest solution［J］.Comm.Pure Appl.Math，2006，59(6):797－829.

［5］ CHEN S，DONOHO D，SAUNDERSM.Atomic decomposition by basis pursuit［J］.Society for Industrial and Applied Mathematics，2001，43(1):129－159.

［6］ DONOHO D，ELAD M，TEMLYAKOV V.Stable recovery of sparse overcomplete representations in the presence of noise［J］.IEEE Trans.Information Theory，2006，52(1):6－18.

［7］ MALLAT S，ZHANG Z.Matching pursuits with time－frequency dictionaries［J］.IEEE Trans.Signal Processing，1993，41(12):3397－3415.

［8］ JOEL T，GILBERT A.Signal recovery from random measurements via orthogonal matching pursuit［J］.IEEE Trans.Information Theory，2008，53(12):4655－4666.

［9］ DEANNA N，ROMAN V.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit［J］.Foundations of Computational Mathematics，2009，9(3):317－334.

［10］ DEANNA N，JOEL T.CoSaMP:Iterative signal recovery from incomplete and inaccurate samples［J］.Applied and Computational Harmonic Analysis，2009，26(3):301－321.

［11］ FIQUEIREDO M，NOWAK R，WRIGHT S.Gradient projection for sparse reconstruction:application to compressed sensing and other inverse problems［J］.IEEE Journal of Selected Topics in Signal Processing，2007，1(4):586－598.

［12］ JIS，XUEY，CARIN L.Bayesian compressive sensing［J］.IEEE Trans.Signal Processing，2008，56(6):2346－2356.