田香玲，席志紅

(哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱 150001)

2004年 David Donoho、T．Tao等提出壓縮感知理論［1－5］，之后又發(fā)表了諸多關(guān)于壓縮感知的文章，對信號的稀疏表示、測量矩陣和重構(gòu)算法等做了詳細(xì)的描述，分析了l0范數(shù)和l1范數(shù)的關(guān)系，為重構(gòu)算法的實現(xiàn)和改進(jìn)提供了理論支持。

壓縮感知理論包含3方面:信號的稀疏表示、觀測矩陣的設(shè)計和重構(gòu)方法。壓縮感知理論的前提是稀疏表示，關(guān)鍵是觀測矩陣的設(shè)計，核心是重構(gòu)算法。壓縮感知的理論思想是用遠(yuǎn)小于信號長度的觀測值重構(gòu)原始信號。這一理論打破了Nyquist理論對信號處理的束縛，是信號處理領(lǐng)域的一場革命。

目前，學(xué)者們已提出了眾多重構(gòu)算法及其改進(jìn)算法，但觀測矩陣的設(shè)計同樣是壓縮感知的重要部分，本文主要分析了觀測矩陣存在的不足，針對信號稀疏表示之后的特點和觀測矩陣的非相干性原則，提出一種新的算法，提高圖像的重構(gòu)精度。

1 壓縮感知理論

壓縮感知理論表明稀疏信號或在變換域稀疏的信號，可通過一個矩陣將測量值重構(gòu)出原始信號。其不再基于Nyuist采樣原則，在信號的頻率域進(jìn)行采樣，而是基于信號的結(jié)構(gòu)對信號壓縮重構(gòu)，所需的數(shù)據(jù)量大幅減少。

假設(shè)x∈RN×1是一個實值有限長的一維離散信號是 RN×1中的 N 個標(biāo)準(zhǔn)正交基，令 Ψ∈RN×N是以 Ψi為列向量的矩陣，即 Ψ=［Ψ1，Ψ2，…，ΨN］，則RN×1中的任意信號均可由正交基{Ψi}Ni=1線性表示

其中，si是內(nèi)積 si=〈x，Ψi〉=ΨTix。實際上向量s是向量x等價表示，只是表達(dá)方式不同，x是時間域或空間域的，s是x的變換域表示。若s中只有K(K?N)個值不為零，其余N－K個值均為零或近似為零，則稱信號x是K－稀疏的［6］。

壓縮感知的數(shù)學(xué)形式描述式(2)所示

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

其中，Θ=ΦΨ，Θ∈RM×N稱為觀測矩陣或者信息算子。

對于M×N維的觀測矩陣，其行數(shù)M遠(yuǎn)小于列數(shù)N，所以由y的M個觀測值重構(gòu)信號x是NP－h(huán)ard問題。但若式(3)中s中僅有K個數(shù)是非零的，就可由y精確重構(gòu)原始信號x。解式(3)的逆問題得到變換域Ψ的稀疏基的系數(shù)s，將系數(shù)s代入式(1)便可得原始信號x。因此，壓縮感知的實質(zhì)是:選擇使信號最稀疏的稀疏基，用觀測矩陣得到測量值，然后用重構(gòu)算法準(zhǔn)確快速穩(wěn)定地重構(gòu)出原始信號。

1．1 信號的稀疏表示

壓縮感知的前提條件是信號的稀疏性或可壓縮性［7］，但信號在有些基上可能是稀疏的，或是不稀疏的，即使是稀疏的，可能會在有些基上的稀疏性好，而有些稀疏性不好，而信號的重構(gòu)精度與信號的稀疏度相關(guān)，所以選擇合適的稀疏基極為重要。調(diào)和分析方法是常用的稀疏表示方法，其包括傅里葉變換、離散余弦變換和小波變換，其中小波基應(yīng)用最為廣泛;之后多尺度幾何分析法和基于超完備的圖像自適應(yīng)稀疏表示方法相繼被提出。

1．2 設(shè)計觀測矩陣

觀測矩陣對觀測值的獲取和信號的重構(gòu)過程都具有較重要的作用，所以研究設(shè)計觀測矩陣至關(guān)重要。對于K－稀疏矢量v，上述重構(gòu)問題應(yīng)滿足的條件是

式(4)表明矩陣Θ必須滿足K－稀疏矢量的長度，而矩陣Φ中的K個重要向量的位置也是未知的，所以如何確定觀測矩對信號重構(gòu)至關(guān)重要。假設(shè)Ψ中K個向量構(gòu)造成觀測矩陣Φ，但該種方法精確重構(gòu)原始信號的概率僅為1/CKN，需嘗試CKN次才能得到原始信號，所以計算量較大，且由于構(gòu)造觀測矩陣是隨機(jī)選取向量，所以并不能保證觀測矩陣的列向量就是稀疏系數(shù)s的非零系數(shù)對應(yīng)的位置。因此，觀測矩陣Φ與ΨH應(yīng)極端不相似，即矩陣Φ和稀疏基Ψ的列不能相互線性表示。實際上，就是觀測矩陣Φ滿足約束等距特性(Restricted Isometry Property，RIP)［8］，RIP 性質(zhì)定義如下:

設(shè)Φ為M ×N維矩陣，且 M?N，T?{1，2，…，N}，T為集合T的勢，對任意滿足1≤K≤N的整數(shù)K，定義K－約束等距常數(shù)(K－Restricted Isometry Constants，K －RIC)為 δK，對任意T ×1維列向量c，以下不等式

為對所有按T中的元素索引的矩陣Φ各列組成的子矩陣ΦT均成立的最小數(shù)。類似地，對滿足K+K'?N的整數(shù) K、K'，定義 K、K'－約束正交常數(shù)(K，K'－Restricted Orthogonality Constants，K，K' － ROC) θK，K'為使得以下不等式

為對所有滿足 T，T'?{1，2，…，N}且T≤K'，T'≤K的子矩陣ΦT，ΦT'都成立的最小數(shù)。式(5)則稱為約束等距性質(zhì)(Restricted Isometry Property，RIP)。

由上述理論可知，觀測矩陣設(shè)計時必須滿足RIP性質(zhì)，這樣才能獲得包含較多信息量的信觀測值，得到較高的重構(gòu)精度。常見的測量矩陣分為隨機(jī)觀測矩陣和確定性觀測矩陣。

1．3 重構(gòu)算法

求解式(3)經(jīng)典方法是最小二乘法

其中，α0表示α中非零元素的個數(shù)。這是一個NP難問題。Donoho指出可將l0范數(shù)［9］問題轉(zhuǎn)化l1問題

式(9)是一個凸優(yōu)化的問題。壓縮感知的重構(gòu)過程就是尋求最優(yōu)的解決凸優(yōu)化問題的方法，其中基追蹤(Basis Pursuit，BP)算法［10］是一種最基本的解決凸優(yōu)化問題的算法。

目前將重構(gòu)算法分為貪婪追蹤算法、凸松弛算法和組合算法。其中，貪婪追蹤算法中的正交匹配追蹤(Orthogonal Matching Pursuit，OMP) 算法［11－12］應(yīng)用最為廣泛，下面介紹OMP算法的具體步驟。

輸入:觀測矩陣Φ，測量值y，稀疏度K。

初始化:殘差r0=y，索引集Λ0=?，t=1。

(1)找出殘差r0與觀測矩陣Φ的列中內(nèi)積最大的一列，記錄其角標(biāo) λ。即

(2)更新索引集 Λt= Λt－1∪{λt}，記錄重建原子集合為空矩陣;

(4)更新殘差rt=y－，t=t+1。

(5)判斷是否滿足t＞K，若是則停止迭代;否則，轉(zhuǎn)到步驟(1)繼續(xù)執(zhí)行。

從上述OMP算法的步驟可看出，OMP算法是用迭代的方法，每次迭代從觀測矩陣Φ中選取與殘差最相關(guān)的一列作為原子。然后更新殘差，并將該列向量從觀測矩陣中去掉，將所有迭代得到的原子正交化，再繼續(xù)進(jìn)行下一步迭代。如此迭代，直到滿足迭代次數(shù)或迭代閾值為止。OMP算法在每次迭代時均將得到的原子正交化，這就能保證每次得到的原子與殘差均是最相關(guān)的，所以O(shè)MP算法所需迭代次數(shù)較少，故應(yīng)用較為廣泛。

2 觀測矩陣的優(yōu)化

觀測矩陣將稀疏信號從高位空間投影到低維空間，在保證信號的重構(gòu)精度的條件下，要求投影空間維數(shù)越低越好。

2．1 矩陣奇異值分解

假設(shè) A∈Rm×n，存在正交矩陣 U∈Rm×m、V∈Rn×n和對角矩陣∑使得

且∑1=diag(δ1，δ2，…，δr)，其對角元素按照順序 δ1≥δ2≥…≥δr＞0，r=rank(A)排列。這就是矩陣的奇異值分解定理，其中 δi(i=1，2，…，r－ 1，r)為矩陣 A 的奇異值，而式(10)稱為矩陣A的奇異值分解。

奇異值具有良好的穩(wěn)定性、比例不變性、旋轉(zhuǎn)不變性和降維壓縮的特性，所以對觀測矩陣進(jìn)行奇異值分解，可較好地反映觀測矩陣的性質(zhì)。

2．2 優(yōu)化算法

稀疏信號的非零系數(shù)集中在低頻段，而零系數(shù)或近似為零的系數(shù)集中在高頻段。因此，提高測量矩陣前半段的測量系數(shù)，可在采樣次數(shù)相同的情況下獲得更多信號的信息，從而準(zhǔn)確重構(gòu)原始信號。然而增大觀測矩陣前半部分系數(shù)的必然會降低矩陣的非相干性。由矩陣奇異值分解的性質(zhì)可知，最大奇異值越小矩陣的非相干性就越好。因此，本文主要工作是設(shè)計合理的觀測矩陣，提高矩陣的非相干性。實驗結(jié)果表明，奇異值修正后觀測矩陣相對于原矩陣具有更好的RIP性質(zhì)，重構(gòu)效果有明顯提高。

下面介紹矩陣優(yōu)化算法的步驟:

(1)生成測量矩陣Φ∈RM×N。

(2)對測量矩陣Φ奇異值分解，求出奇異值，即Φ=U∑VT，其中δr)，(δ1≥δ2≥…≥δr＞0)。

(3)針對信號稀疏表示的觀測矩陣的優(yōu)化。

1)構(gòu)造一個M×N的全1矩陣H。

2)求出對角矩陣對角線元素的均值ave1，找出大于等于ave1的所有奇異值，記下≥ave1的奇異值的總數(shù)j。

3)令矩陣H的前j列乘以加權(quán)系數(shù)t(t＞1)，得到矩陣H1。

4)將優(yōu)化矩陣H1與觀測矩陣Φ點乘，得到優(yōu)化的矩陣Φ1。

(5)生成新的觀測矩陣Φ2=U1∑'2V1。

3 實驗及結(jié)果分析

在 CPU 為 Intel T5200(2．00 GHz)，內(nèi)存為2．00 GB的聯(lián)想電腦，Matlab7．0的條件下，對隨機(jī)高斯測量矩陣按照本文的算法進(jìn)行優(yōu)化，如圖1所示對二維圖像做了仿真實驗，實驗選用的是512×512的Baboon圖像，壓縮比為0．4，分別采用傅里葉基、離散余弦基和小波基對圖像稀疏表示，重構(gòu)算法采用OMP算法，對比改進(jìn)前后重構(gòu)的圖像。圖2所示為Baboon(512×512)圖像在不同壓縮比時重構(gòu)圖像的重構(gòu)精度和時間。經(jīng)過多次試驗證明在t=5時，重構(gòu)效果較好，故取t=5。

PSNR是最普遍的客觀評價圖像質(zhì)量的方法，PSNR值越大重構(gòu)精度越高，PSNR的計算公式如下

實驗結(jié)果表明優(yōu)化算法對傅里葉變換、離散余弦變換、小波變換3種稀疏表示方法都有效果，其中采用傅里葉稀疏表示重構(gòu)的圖像，在觀測矩陣優(yōu)化后，精度增大的幅度最小(1～2 dB)，離散余弦稀疏表示次之，小波變換的精度增大最多，尤其是在壓縮比較小時，PSNR可增大8～9 dB，且3種方法經(jīng)優(yōu)化矩陣觀測重構(gòu)圖像所需的時間雖然增加，但增加量較小，可認(rèn)為基本相同。

圖2 Baboon圖像不同壓縮比的重構(gòu)效果圖

由以上結(jié)論可知，本文的改進(jìn)算法，不僅適用于大壓縮比的情況，且適用于小壓縮比的情況，特別的相比傳統(tǒng)方法，在小壓縮比時的重構(gòu)效果較好，可大幅提高圖像的重構(gòu)精度，且消耗時間只有小幅增加，可認(rèn)為與傳統(tǒng)方法所用時間相同。

5 結(jié)束語

為克服基于壓縮感知的圖像重構(gòu)算法存在的不足，結(jié)合圖像稀疏表示之后再變換域的性質(zhì)，給觀測矩陣賦以權(quán)值，并根據(jù)矩陣奇異值分解的性質(zhì)降低矩陣的相干性。根據(jù)這一理論對圖像進(jìn)行仿真實驗，實驗結(jié)果表明，改進(jìn)算法提高了重構(gòu)圖像的重構(gòu)精度，特別是在小壓縮比時，基于小波變換的重構(gòu)圖像的精度大幅提高。

［1］ Baraniuk R．A lecture on compressive sensing［J］．IEEE Signal Processing Magazine，2007，24(4):118 －121．

［2］ Candès E J，Romberg J，Tao T．Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information ［J］．IEEE Transactions on Information Theory，2006，52(2):489 －509．

［3］ Candès E J，Romberg J．Quantitative robust uncertainty principles and optimally sparse decompositions［J］．Foundations of Computational Mathematics，2006，6(2):227 －254．

［4］ Donoho D．Compressed sensing［J］．IEEE Transactions on Information Theory，2006，52(4):1289 －1306．

［5］ Donoho D，Tsaig Y．Extensions of compressed sensing［J］．Signal Processing，2006，86(3):533 －548．

［6］ Emmanuel Candès，Justin Romberg，Terence Tao．Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information［J］．IEEE Transactions on Information Theory，2006，52(2):489 －509．

［7］ Penne E K，Mallat S．Image compression with geometrical［C］．Proceeding of ICIP，2000:661 －664．

［8］ Candès E J，Romberg J．Sparsity and incoherence in compressive sampling ［J］．Inverse Problems，2007，23(3):969－985．

［9］ Fang Hong，Zhang Quanbing，Wei Sui，et al．A method of image reconstruction based on sub－gaussian random projection［J］．Journal of Computer Research and Development，2008，45(8):1402 －1407．

［10］ Scott Shaobing Chen，David L Donoho，Michael A Saunders．Atomic decomposition by basis pursuit［J］．Society for Industrial and Applied Mathematics，2001，43(1):129 －159．

［11］ Tropp J A，Gilbert A C．Signal recovery from random measurements via orthogonal matching pursuit［J］．IEEE Transactions on Information Theory，2007，53(12):4655 －4666．

［12］ Mallat S，Zhang Z．Matching pursuits with time－ frequency dictionaries［J］．IEEE Transactions on Signal Processing，1993，41(12):3397 －3415．