圖像壓縮感知中常用測(cè)量矩陣的性能比較

詹可軍，宋建新

(南京郵電大學(xué)圖像處理與圖像通信實(shí)驗(yàn)室，江蘇南京210003)

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

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

1 壓縮感知基本理論

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

寫成矩陣的形式為

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

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

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

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

當(dāng)信號(hào)滿足在基Ψ下具有稀疏性，且測(cè)量矩陣Φ和Ψ滿足不相干性，那么壓縮感知理論就可以通過(guò)求解以下l0范數(shù)問(wèn)題來(lái)重建原始信號(hào)

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

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

2 測(cè)量矩陣及其性能

2.1 測(cè)量矩陣的性能

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

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

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

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

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

2.2 常用測(cè)量矩陣

目前常用的測(cè)量矩陣有很多，在不同的文獻(xiàn)中經(jīng)常會(huì)碰到不同的測(cè)量矩陣，但總體來(lái)說(shuō)目前常用的測(cè)量矩陣可以分為兩類:隨機(jī)性測(cè)量矩陣和確定性測(cè)量矩陣。

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

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

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

2.3 本文實(shí)驗(yàn)方案

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

圖1 本文圖像處理流程圖

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

圖2 分塊大小為8×8時(shí)不同測(cè)量率下幾種測(cè)量矩陣重構(gòu)信號(hào)的PSNR

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

表1 不同測(cè)量率下幾種測(cè)量矩陣重構(gòu)信號(hào)所需時(shí)間

從圖3可以看出，在測(cè)量率為50%，分塊大小為8×8時(shí)，幾種測(cè)量矩陣重構(gòu)出來(lái)的圖像視覺(jué)效果都不是很清晰，模糊效果較為嚴(yán)重，相比之下，哈達(dá)瑪矩陣和托普利茲矩陣的重構(gòu)效果相對(duì)清晰于其他幾種矩陣。

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

圖3 測(cè)量率為50%，分塊大小為8×8時(shí)各測(cè)量矩陣重構(gòu)圖像的視覺(jué)效果

表2 測(cè)量率為50%時(shí)不同分塊大小下部分哈達(dá)瑪矩陣重構(gòu)信號(hào)的PSNR和重構(gòu)時(shí)間

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

4 總結(jié)

本文對(duì)目前幾種常用的測(cè)量矩陣的性能做了一個(gè)全面的分析與比較，從重構(gòu)圖像的PSNR、重構(gòu)時(shí)間、視覺(jué)效果等方面做了綜合對(duì)比，總體來(lái)說(shuō)，哈達(dá)瑪矩陣和托普利茲矩陣相對(duì)好于其他幾種矩陣，其他幾種矩陣的性能基本上沒(méi)有多大差異。另外本文還對(duì)不同分塊大小對(duì)壓縮感知重構(gòu)信號(hào)的影響做了分析，從實(shí)驗(yàn)結(jié)果來(lái)看，綜合考慮重構(gòu)圖像的PSNR和重構(gòu)時(shí)間，分塊大小為8×8時(shí)可獲得最佳的重構(gòu)效果。

［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.