K-L變換觀測矩陣優(yōu)化算法

王海艷，佟 岐，連志鵬，汲清波

1.哈爾濱工程大學(xué) 信息與通信工程學(xué)院，哈爾濱 150001

2.北京航天發(fā)射技術(shù)研究所，北京 100076

1 引言

傳統(tǒng)的奈奎斯特（Nyquist）采樣定理表明為了不失真的重構(gòu)出模擬信號，離散信號系統(tǒng)的采樣頻率必須至少是模擬信號帶寬的兩倍。然而隨著人們對信息需求量的增加，信號帶寬也隨之不斷的增加，導(dǎo)致人們對信號的采集變得越來越困難。近年來由Candès、Donoho和華裔科學(xué)家Tao等人提出的壓縮感知（Compressed Sensing，CS）理論[1-2]，不受奈奎斯特采樣定理中采樣速率至少是信號帶寬兩倍的局限，該理論通過投影觀測得到較少觀測數(shù)據(jù)，然后利用重構(gòu)算法求解優(yōu)化問題從而高概率地從壓縮觀測數(shù)據(jù)中重構(gòu)原始信號。CS理論直接采集壓縮后的數(shù)據(jù)，避免了先采樣后壓縮編碼而產(chǎn)生大量冗余信息的情況。它在減少冗余數(shù)據(jù)，節(jié)省存儲空間上具有較大的優(yōu)勢。

壓縮感知理論中包含三個重要組成部分：信號的稀疏表示、觀測矩陣的構(gòu)造、重構(gòu)算法的設(shè)計[3]。其中觀測矩陣的構(gòu)造對信號的重構(gòu)至關(guān)重要，合理的觀測矩陣可以高精度的重構(gòu)出原始信號，目前常用的觀測矩陣包括隨機(jī)高斯矩陣、隨機(jī)伯努利矩陣、隨機(jī)傅里葉矩陣等[4]。這些直接構(gòu)造出的觀測矩陣所產(chǎn)生的性能并不是最優(yōu)的，所以許多學(xué)者針對觀測矩陣的優(yōu)化進(jìn)行了研究。研究表明優(yōu)化觀測矩陣的方法之一是減小觀測矩陣與稀疏矩陣之間的互相關(guān)性[5]，根據(jù)此方法，Xu[6]、Abolghasemi[7]、Tian[8]等人提出了相應(yīng)的優(yōu)化觀測矩陣的算法，這三種算法都是利用迭代的思想對觀測矩陣進(jìn)行優(yōu)化，但存在迭代次數(shù)較多，運(yùn)算量較大，并且在觀測數(shù)據(jù)較少的情況下重構(gòu)圖像質(zhì)量較差的問題。針對這些缺點(diǎn)，本文提出了K-L（Karhunen-Loeve）變換觀測矩陣優(yōu)化算法，該算法通過對傳感矩陣（觀測矩陣與稀疏矩陣的乘積）進(jìn)行K-L變換來減小觀測矩陣與稀疏矩陣之間的互相關(guān)性，從而實(shí)現(xiàn)優(yōu)化觀測矩陣的目的。最后通過實(shí)驗(yàn)驗(yàn)證了K-L變換觀測矩陣優(yōu)化算法的性能。

2 壓縮感知理論

壓縮感知的理論基礎(chǔ)為信號本身是稀疏的，或者信號在某一變換域是可壓縮的，因此信號的稀疏表示是壓縮感知理論首要的研究任務(wù)。 稀疏信號是指信號本身絕大多數(shù)元素為零或近似等于零，或者在某一變換域上絕大多數(shù)元素為零或近似等于零的信號。假設(shè)x是一個長度為N的實(shí)值一維離散信號，記為x∈RN×1。信號x可以稀疏表示成一組正交基的線性組合：

利用一個與稀疏矩陣Ψ不相關(guān)的矩陣Φ對信號x進(jìn)行線性隨機(jī)投影得到觀測量y：

由上式可以很自然地想到利用解線性方程組的方法求解x，但是由于觀測矩陣Φ的維度M＜N，所以通過式（2）中y的M 個觀測值求解x是一個病態(tài)問題，方程無解或有無窮多個解。將式（1）帶入式（2）得：

式中，D是M×N(M＜N)矩陣，稱為傳感矩陣。

因?yàn)樯鲜街械膕是稀疏的，只有K(K?N)個值不為零，所以信號的重構(gòu)表示為：

式中，求解l0最小范數(shù)是一個NP難的非凸優(yōu)化問題。由Candès和Donoho提出的l1范數(shù)下的凸優(yōu)化壓縮感知重構(gòu)框架，將式（4）的非凸優(yōu)化問題轉(zhuǎn)變成了一個凸優(yōu)化問題：

通過凸優(yōu)化算法[9]便可求出s的近優(yōu)解。

3 K-L變換優(yōu)化觀測矩陣

觀測矩陣的設(shè)計是為了將信號從N維投影到M維(M＜N)從而獲得M個觀測值，并保證這M個觀測值中包含了重構(gòu)信號的足夠信息，以便可以成功地重構(gòu)出原始信號或者稀疏系數(shù)向量[10]。為了能夠從獲得的觀測值中準(zhǔn)確的重構(gòu)原始信號，Candès和Tao提出并證明了觀測矩陣Φ必須滿足有限等距性（Restricted Isometry Property，RIP）條件[11]，RIP等距特性在觀測矩陣Φ的構(gòu)造與優(yōu)化中具有重要意義[12-13]。但是RIP等距特性很難直接應(yīng)用，Baraniuk在文獻(xiàn)[14]給出了RIP準(zhǔn)則的等價條件為觀測矩陣Φ與稀疏矩陣Ψ幾乎不相關(guān)，因此減小觀測矩陣與稀疏矩陣之間的互相關(guān)性可以提高信號的重構(gòu)概率。

對于觀測矩陣的優(yōu)化，首先將觀測矩陣與稀疏矩陣之間的互相關(guān)系數(shù)μ定義為：

式中，di、dj為傳感矩陣D中的任意兩列向量?；ハ嚓P(guān)系數(shù)μ代表著觀測矩陣與稀疏矩陣之間的相關(guān)性，μ的值越大代表兩個矩陣的相關(guān)性越大，那么重構(gòu)出的原始信號質(zhì)量越差，為了能夠較高精度的重構(gòu)原始信號，希望μ的值盡量減小。同時，互相關(guān)系數(shù)還影響著信號的可稀疏度界限[15]。

式（7）表明觀測矩陣與稀疏矩陣之間的互相關(guān)性越小，則稀疏系數(shù)s的上界限越大，所以越有利于原始信號的重構(gòu)。本文的主要思想是通過對傳感矩陣D進(jìn)行K-L變換，來減小觀測矩陣與稀疏矩陣之間的互相關(guān)性。

K-L變換又稱為特征矢量變換或霍特林（Hotelling）變換，它是以原始數(shù)據(jù)協(xié)方差矩陣的特征向量構(gòu)成的正交矩陣作為變換矩陣，對原始數(shù)據(jù)進(jìn)行正交變換。用原始數(shù)據(jù)協(xié)方差矩陣的特征向量構(gòu)成的正交矩陣作為變換矩陣，會使變換后數(shù)據(jù)的協(xié)方差矩陣中除對角線之外大部分協(xié)方差等于零或者近似等于零，即原來像素間的相關(guān)性在很大程度上被減弱。K-L變換的原理是設(shè)為N×1維隨機(jī)矢量，mX=E(X)和分別為其平均值向量和協(xié)方差矩陣，ei和λi分別為CX的特征向量和特征值，其中i=1,2,…,N，則K-L變換式為Y=AX。其中變換矩陣A的每一行為協(xié)方差矩陣CX對應(yīng)于特征值λi的特征向量，即

式中，eij(i,j=1,2,…,N)表示第i個特征向量的第 j個分量，滿足A×AT=I，其中I表示單位陣。

根據(jù)K-L變換式Y(jié)=AX得到Y(jié)的平均值為：

Y的協(xié)方差矩陣為：

因?yàn)锳×AT=I，所以Y的協(xié)方差矩陣進(jìn)一步化簡為：

由上述推導(dǎo)得到變換后的矢量Y的協(xié)方差矩陣是對角矩陣，除對角線以外其他的元素全部等于零，即

在協(xié)方差矩陣中主對角線上的元素σi2(i=1,2,…,N)表示各分量的方差，它代表著各分量能量的大小以及離散程度。方差越大分量的能量越大，分布越離散，而主對角線以外的元素表示分量Yi與分量Yj之間相關(guān)程度的協(xié)方差，對角矩陣表明了經(jīng)過K-L變換得到新的分量Yi與Yj彼此之間的相關(guān)性在很大程度上被減弱，對角矩陣中主對角線上的方差分布為從大到小，即代表變換后的矢量Y中前面分量比后面分量的能量大，離散程度高。

變換后的矢量為Y=(Y1,Y2,…,YN)T，Y中各分量如下所示：

由上式看出，實(shí)際上K-L變換是使原始矢量X中各個分量加上一個權(quán)重系數(shù)，實(shí)現(xiàn)線性變換，重新組合成了矢量Y。它是綜合了原來各個分量的信息，并不是對原始矢量進(jìn)行簡單的取舍，從而使矢量Y可以較好的反映事物的本質(zhì)特征。

由于K-L變換是對一維信號的變換，所以在對二維圖像信號進(jìn)行變換時，本文將圖像按照每一行都為一個一維信號的原則，從上到下依次對圖像的每一行進(jìn)行K-L變換，具體方法如下所示：

這樣便可以使用K-L變換對M×N維傳感矩陣進(jìn)行變換，進(jìn)而得到優(yōu)化后的觀測矩陣。

K-L變換優(yōu)化觀測矩陣的步驟如下。

1.初始化i=1；

a.將傳感矩陣D的第i行轉(zhuǎn)置得到d′，計算d′的均值u=E(d′)，協(xié)方差矩陣Cd′=E{(d′-u)(d′-u)T；

b.Cd′Vj=λjVj，1≤j≤N ，式中 λj是特征值并且 (λ1＞λ2＞…＞λN)，相應(yīng)的特征向量是 Vj，特征向量矩陣為V=[V1V2…Vn]；

c.將V 正交化得V*，變換矩陣A=V*T；

d.變換后的 d′=V*T(d′-u)=A(d′-u)；

e.變換后的傳感矩陣D(i,:)=d′T；

2.i=i+1，如果 i=I，則執(zhí)行（3）；否則執(zhí)行第1步的a；

3.更新 DI=D(i,:)；

4.計算ΦI=DI×Ψ-1；

輸出：優(yōu)化后的觀測矩陣Φ=ΦI

4 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證所提算法優(yōu)化觀測矩陣的有效性和可靠性，本文選取一幅大小為256×256的Lena圖像進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)中稀疏矩陣Ψ選取DCT稀疏基，重構(gòu)算法選用凸優(yōu)化類算法中的BP算法[9，16]，本次實(shí)驗(yàn)中定義M=102，即觀測矩陣的大小為102×256，采樣率r≈0.4，分別用隨機(jī)高斯矩陣和本文算法優(yōu)化后的隨機(jī)高斯矩陣作為觀測矩陣，對Lena圖像進(jìn)行仿真實(shí)驗(yàn)，得到的仿真效果圖如圖1所示。

圖1 優(yōu)化算法在采樣率為0.4時重構(gòu)圖像效果圖

從圖1仿真結(jié)果可知，利用本文算法優(yōu)化后的觀測矩陣重構(gòu)圖像的PSNR值大于利用未優(yōu)化的觀測矩陣重構(gòu)圖像的PSNR值，這里以PSNR值的大小來衡量圖像重構(gòu)質(zhì)量的優(yōu)劣，比較重構(gòu)出的兩幅圖像可以看出由本文算法優(yōu)化后的觀測矩陣重構(gòu)出的Lena圖像具有更加清晰的輪廓。由以上分析可知，所提優(yōu)化算法可以對觀測矩陣進(jìn)行優(yōu)化。

在以上實(shí)驗(yàn)的基礎(chǔ)上，只改變觀測數(shù)目M的大小來驗(yàn)證本文算法優(yōu)化觀測矩陣的可靠性，表1中列出了在M為26～126的情況下，分別利用優(yōu)化后的隨機(jī)高斯矩陣和未優(yōu)化的隨機(jī)高斯矩陣為觀測矩陣重構(gòu)出Lena圖像的PSNR值。從表1中可以看出隨著觀測數(shù)目的增加，由兩個觀測矩陣重構(gòu)圖像的PSNR值都隨之增大。但是在不同的觀測數(shù)目下，利用本文算法優(yōu)化后所得觀測矩陣重構(gòu)圖像的PSNR值始終大于未優(yōu)化的隨機(jī)高斯矩陣重構(gòu)圖像的PSNR值，即證明了利用所提優(yōu)化算法優(yōu)化觀測矩陣的可靠性。

表1 不同觀測數(shù)目下優(yōu)化后觀測矩陣與未優(yōu)化觀測矩陣重構(gòu)圖像的PSNR值比較

為了進(jìn)一步說明所提優(yōu)化算法的性能，繼續(xù)進(jìn)行本文算法和Xu算法、Vahid算法以及Tian算法的比較實(shí)驗(yàn)，本次實(shí)驗(yàn)選取兩幅大小均為256×256的Lena圖像和Mandi圖像進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)中稀疏矩陣Ψ依然選取DCT稀疏基，觀測矩陣Φ分別選用本文算法、Xu算法、Vahid算法以及Tian算法，重構(gòu)算法依然采用凸優(yōu)化類算法中的BP算法，用PSNR值的大小來代表兩幅圖像的重構(gòu)質(zhì)量。本次實(shí)驗(yàn)在采樣率r=0.5的情況下，得到的仿真結(jié)果如圖2所示。

從圖2和圖3可以明顯的看出，用本文算法優(yōu)化后的觀測矩陣重構(gòu)圖像的PSNR值大于用其他三種算法優(yōu)化后的觀測矩陣重構(gòu)圖像的PSNR值。從圖中可以看出，由本文算法優(yōu)化后的觀測矩陣重構(gòu)出的圖像具有更加清晰的視覺效果，重構(gòu)的兩幅圖像帽子邊沿、眼睛以及胳膊等部位的輪廓更加清晰，這說明相比較其他三種優(yōu)化算法優(yōu)化的觀測矩陣，用本文算法優(yōu)化后的觀測矩陣重構(gòu)圖像的質(zhì)量和視覺效果最好。

圖2 不同算法在采樣率為0.5時重構(gòu)Lena圖像效果對比

圖3 不同算法在采樣率為0.5時重構(gòu)Mandi圖像效果對比

表2為在采樣率r=0.5時，重構(gòu)算法為凸優(yōu)化類算法中BP算法的情況下，對兩幅大小為256×256的Lena圖像和Mandi圖像進(jìn)行仿真實(shí)驗(yàn)，對比各算法對圖像重構(gòu)時間的長短。從表2中可以看出，與Xu算法、Vahid算法、Tian算法優(yōu)化后所得觀測矩陣以及未優(yōu)化的隨機(jī)高斯矩陣重構(gòu)圖像所用的時間相比，利用本文算法優(yōu)化后所得觀測矩陣重構(gòu)的兩幅圖像所用的時間最短。這意味著，和文中所提其他優(yōu)化算法相比，本文算法在不增加重構(gòu)時間的基礎(chǔ)上可以得到更高質(zhì)量的重構(gòu)圖像。

表2 不同算法在采樣率為0.5時重構(gòu)圖像時間對比

對比四種算法優(yōu)化后的觀測矩陣以及未優(yōu)化的隨機(jī)高斯矩陣，在采樣率為0.2～0.65之間對Lena圖像和Mandi圖像重構(gòu)的重構(gòu)誤差值，兩幅圖像重構(gòu)誤差曲線圖如圖4所示。

圖4 各優(yōu)化算法在采樣率為0.2到0.65之間兩幅圖像重構(gòu)誤差關(guān)系曲線

圖5 各優(yōu)化算法在采樣率為0.2到0.65之間兩幅圖像重構(gòu)的峰值信噪比關(guān)系曲線

從圖4可以看出，在采樣率為0.2～0.65之間，隨著采樣率的增加4種算法優(yōu)化后的觀測矩陣以及未優(yōu)化的隨機(jī)高斯矩陣對于圖像的重構(gòu)誤差都逐漸減小。在采樣率為0.2～0.5之間，利用本文方法優(yōu)化后的觀測矩陣與另外三種方法優(yōu)化后的觀測矩陣以及未優(yōu)化的隨機(jī)高斯矩陣相比具有更低的圖像重構(gòu)誤差，圖像的重構(gòu)誤差越小代表著圖像的重構(gòu)質(zhì)量越高。由仿真圖可知，在采樣率為0.5～0.65時，相比于另外三種方法優(yōu)化后的觀測矩陣以及未優(yōu)化的隨機(jī)高斯矩陣重構(gòu)圖像的重構(gòu)誤差，利用本文方法優(yōu)化后的觀測矩陣重構(gòu)圖像的重構(gòu)誤差存在優(yōu)劣交替的不穩(wěn)定現(xiàn)象。兩幅圖像重構(gòu)的峰值信噪比值曲線圖如圖5所示。

從圖5中可以看出，所有的方法重構(gòu)得到的PSNR值都隨著采樣率的增加而增大，這是因?yàn)椴蓸勇试黾铀玫降挠^測數(shù)目隨之增多，采樣得到原始信號的信息也會隨之增加，所以重構(gòu)信號的PSNR值越大，即重構(gòu)質(zhì)量越好。相比較來說，本文方法在采樣率為0.2～0.5的時候重構(gòu)質(zhì)量最好，這說明使用本方法重構(gòu)的觀測矩陣在較少的觀測數(shù)據(jù)下就可以較好的重構(gòu)出原始信號。由仿真圖可知，在采樣率為0.5～0.65時重構(gòu)質(zhì)量幾乎持平于Xu方法、Vahid方法以及Tian方法。通過分析以上仿真實(shí)驗(yàn)結(jié)果，得出了在觀測數(shù)目較少的情況下，本文算法相對于文中所提其他算法對圖像的重構(gòu)具有更好的效果。

5 結(jié)束語

根據(jù)減小觀測矩陣與稀疏矩陣之間互相關(guān)性的思想，本文提出了利用K-L變換減小觀測矩陣與稀疏矩陣之間的互相關(guān)系數(shù)來優(yōu)化觀測矩陣的方法。通過對實(shí)驗(yàn)結(jié)果進(jìn)行分析，本文提出的觀測矩陣優(yōu)化算法能夠?qū)τ^測矩陣進(jìn)行優(yōu)化，利用本文所提優(yōu)化算法優(yōu)化后的觀測矩陣重構(gòu)出的圖像具有較高的精度，尤其是在采樣率較小時本文提出的優(yōu)化算法相對于其他優(yōu)化算法的優(yōu)勢更加明顯，這將為今后在壓縮感知方面的研究工作提供一定的參考。