基于馬爾科夫鏈的隨機(jī)測(cè)量矩陣研究

趙鴻圖,李 成

(河南理工大學(xué) 物理與電子信息學(xué)院,河南 焦作 454000)

0 概述

隨著無(wú)線通信技術(shù)的發(fā)展，信號(hào)處理過程中信號(hào)帶寬日益增加，這使得以奈奎斯特采樣定理為基礎(chǔ)的傳統(tǒng)信號(hào)處理方法對(duì)采樣率的要求越來(lái)越高。2006年,CANDES和DONOHO提出的壓縮感知理論[1]將采樣和壓縮兩個(gè)過程合并為一個(gè)過程,打破了傳統(tǒng)奈奎斯特采樣理論對(duì)采樣頻率的限制,使得采樣頻率可以低于奈奎斯特采樣頻率,進(jìn)而減少采樣的數(shù)據(jù)量[2],節(jié)約存儲(chǔ)資源。測(cè)量矩陣是壓縮感知理論的中間環(huán)節(jié),參與了信號(hào)的獲取和重構(gòu)過程的計(jì)算,對(duì)信號(hào)的重構(gòu)效果有著較大的影響,其性能越好,重建信號(hào)與原信號(hào)之間的誤差就越小,信號(hào)的恢復(fù)程度就越高[3-4]。近年來(lái),許多學(xué)者提出了新的測(cè)量矩陣。文獻(xiàn)[5]使用混沌序列構(gòu)造測(cè)量矩陣,雖然該測(cè)量矩陣易于硬件實(shí)現(xiàn),但由于混沌序列的取值需滿足統(tǒng)計(jì)獨(dú)立性,取值間隔要大于等于15,因此會(huì)產(chǎn)生大量的無(wú)用數(shù)據(jù),造成存儲(chǔ)空間的浪費(fèi)。文獻(xiàn)[6]提出基于奇異值分解的Toeplitz結(jié)構(gòu)測(cè)量矩陣,相較于高斯隨機(jī)矩陣和Toeplitz結(jié)構(gòu)矩陣,使用該矩陣信號(hào)的重構(gòu)精度得到了提高。本文使用馬爾科夫鏈生成隨機(jī)數(shù)[7],使得整個(gè)測(cè)量矩陣具有隨機(jī)性,并采用對(duì)角矩陣與一般矩陣相結(jié)合的方式來(lái)構(gòu)造測(cè)量矩陣。

1 測(cè)量矩陣

壓縮感知理論的主要內(nèi)容為:設(shè)f為N維可壓縮信號(hào),其稀疏變換為f=Ψs,Ψ是N×N維稀疏基,s是稀疏變換信號(hào),通過M×N維測(cè)量矩陣(M<

(1)

在求得s后,可重構(gòu)出信號(hào)f,由于此問題的計(jì)算是一個(gè)NP-hard問題,通常使用l1范數(shù)來(lái)代替l0范數(shù)求解[8-9]。

在壓縮感知理論中,為能夠準(zhǔn)確地重構(gòu)出原始信號(hào),要求測(cè)量矩陣滿足有限等距性質(zhì)(Restricted Isometry Property,RIP)[10-11],RIP表示為:

(2)

其中,εk∈(0,1),稱為RIP常數(shù)。

由于在驗(yàn)證矩陣是否滿足RIP特性時(shí)需要進(jìn)行大量計(jì)算,驗(yàn)證該問題變得十分困難,因此需要找到RIP特性的替代條件來(lái)解決該問題。文獻(xiàn)[12]指出低相關(guān)性的矩陣滿足RIP特性。本文根據(jù)該關(guān)系構(gòu)造測(cè)量矩陣,并通過仿真得到相關(guān)數(shù)據(jù),與常用的一些測(cè)量矩陣和基于奇異值分解的Toeplitz結(jié)構(gòu)矩陣進(jìn)行比較。

常用的高斯隨機(jī)矩陣[13-14]、伯努利矩陣[14-15]等屬于隨機(jī)測(cè)量矩陣的范疇,此類矩陣重構(gòu)精度較高,但需要的存儲(chǔ)空間及時(shí)間復(fù)雜度較大,對(duì)硬件的要求較高。確定性測(cè)量矩陣包括多項(xiàng)式矩陣、Toeplitz矩陣[14,16]等,此類矩陣需要的存儲(chǔ)空間較小,構(gòu)造速度較快,且易于硬件的實(shí)現(xiàn),但重構(gòu)效果一般。部分隨機(jī)測(cè)量矩陣包括部分阿達(dá)瑪矩陣[14,17]、部分傅里葉矩陣等,此類矩陣同時(shí)具有隨機(jī)性和確定性,其重構(gòu)的圖像效果較好,但因其需要從正交的高階方陣中隨機(jī)抽取行來(lái)構(gòu)造矩陣,因此會(huì)造成存儲(chǔ)資源的浪費(fèi)。

2 基于馬爾科夫鏈的測(cè)量矩陣構(gòu)造

2.1 馬爾科夫鏈

馬爾科夫鏈描述了一種狀態(tài)序列,其每個(gè)狀態(tài)值都取決于前面有限個(gè)狀態(tài)。馬爾科夫鏈?zhǔn)蔷哂旭R爾科夫性質(zhì)的隨機(jī)變量X1,X2,…的一個(gè)數(shù)列。這些變量的范圍,即它們所有可能取值的集合,被稱為“狀態(tài)空間”,Xn的值則是在時(shí)間n中的狀態(tài)。如果Xn+1對(duì)于過去狀態(tài)的條件概率分布僅是Xn的一個(gè)函數(shù),則P(Xn+1=x|X1=x1,X2=x2,…,Xn=xn)=P(Xn+1=x|Xn=xn),其中x為過程中的某個(gè)狀態(tài)。該恒等式可以被看作是馬爾科夫性質(zhì)。

2.2 基于馬爾科夫鏈的隨機(jī)測(cè)量矩陣

為構(gòu)造一個(gè)隨機(jī)測(cè)量矩陣,將馬爾科夫鏈生成的隨機(jī)數(shù)作為測(cè)量矩陣中的元素,使得測(cè)量矩陣具有隨機(jī)性。又為使測(cè)量矩陣滿足RIP特性,需最大程度地保證構(gòu)造矩陣各列向量之間的非相關(guān)性。因此,本文提出將M×M維測(cè)量矩陣構(gòu)造成M×M維對(duì)角陣與M×(N-M)維矩陣相結(jié)合的形式。

當(dāng)對(duì)角陣主對(duì)角線上的元素全都不為0時(shí),即rank(D)=M,此時(shí)對(duì)角陣的行向量與列向量之間都是線性無(wú)關(guān)的。為使主對(duì)角線上的元素均不為0,在使用馬爾科夫鏈生成隨機(jī)數(shù)bl,l=1,2,…,M后,將隨機(jī)數(shù)按照規(guī)則分別映射為-1和1[11],映射規(guī)則為:

(3)

將此數(shù)值作為測(cè)量矩陣Φ的前M個(gè)列向量,即:

(4)

剩余的N-M個(gè)列向量也由馬爾科夫鏈產(chǎn)生的隨機(jī)數(shù)經(jīng)過映射后構(gòu)成。馬爾科夫鏈生成M×(N-M)個(gè)隨機(jī)數(shù)e1,e2,…,eM×(N-M),由于設(shè)置狀態(tài)空間內(nèi)的數(shù)有正負(fù)性,因此在設(shè)置狀態(tài)空間時(shí),生成服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)作為狀態(tài)空間內(nèi)的數(shù)。根據(jù)規(guī)則將這些隨機(jī)數(shù)分別映射為1和0,具體映射規(guī)則為:

(5)

其中,gi,i=1,2,…,M×(N-M)為隨機(jī)數(shù)經(jīng)過映射后得到的結(jié)果,由其構(gòu)成測(cè)量矩陣的N-M個(gè)列向量φk,k=M+1,M+2,…,N。

(6)

由式(4)與式(6)合成測(cè)量矩陣:

Φ=(φ1,φ2,…,φM,φM+1,φM+2,…,φN)=

(7)

將矩陣按列進(jìn)行歸一化得到實(shí)際應(yīng)用的測(cè)量矩陣Φ。歸一化公式如下:

(8)

測(cè)量矩陣被構(gòu)造成一個(gè)對(duì)角陣和一般矩陣相組合的形式,矩陣的秩為M,相較于常用的測(cè)量矩陣而言,減少了計(jì)算量與存儲(chǔ)空間。

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

本文實(shí)驗(yàn)的環(huán)境為Intel Core i3 CPU,64位Windows 7.0操作系統(tǒng),使用的仿真軟件為MATLAB R2014a。為驗(yàn)證本文矩陣的可靠性和有效性,使用標(biāo)準(zhǔn)圖像lena、baboon、peppers、house。圖像的尺寸為256像素×256像素,重構(gòu)算法為正交匹配追蹤算法(Orthogonal Matching Pursuit,OMP)[18-19],分別使用多種常用的測(cè)量矩陣和本文矩陣進(jìn)行仿真,并且從文獻(xiàn)[6]中可以直接得到基于奇異值分解的Toeplitz結(jié)構(gòu)矩陣的仿真數(shù)據(jù),與本文仿真結(jié)果進(jìn)行對(duì)比。為降低隨機(jī)性因素的影響,本文得到的數(shù)據(jù)都是在100次實(shí)驗(yàn)后求得的平均值。將峰值信噪比(Peak Signal to Noise Ratio,PSNR)和重構(gòu)時(shí)間t作為算法的評(píng)價(jià)標(biāo)準(zhǔn)[20-21]。PSNR的計(jì)算公式為:

(9)

重構(gòu)時(shí)間t為:

t=te-ts

(10)

其中,te是結(jié)束時(shí)間,ts是開始時(shí)間。

平均重構(gòu)時(shí)間為:

(11)

其中,L為重構(gòu)次數(shù)。

從圖1～圖8的仿真結(jié)果可以看出,當(dāng)壓縮比相同時(shí),使用本文矩陣的重構(gòu)效果最好。

圖1 壓縮比為70%時(shí)lena圖像重構(gòu)對(duì)比Fig.1 Comparison of lena image reconstruction whenthe compression ratio is 70%

圖2 壓縮比為70%時(shí)baboon圖像重構(gòu)對(duì)比Fig.2 Comparison of baboon image reconstruction whenthe compression ratio is 70%

圖3 壓縮比為70%時(shí)peppers圖像重構(gòu)對(duì)比Fig.3 Comparison of peppers image reconstruction whenthe compression ratio is 70%

圖4 壓縮比為70%時(shí)house圖像重構(gòu)對(duì)比Fig.4 Comparison of house image reconstruction whenthe compression ratio is 70%

圖5 壓縮比為50%時(shí)lena圖像重構(gòu)對(duì)比Fig.5 Comparison of lena image reconstruction whenthe compression ratio is 50%

圖6 壓縮比為50%時(shí)baboon圖像重構(gòu)對(duì)比Fig.6 Comparison of baboon image reconstruction whenthe compression ratio is 50%

圖7 壓縮比為50%時(shí)peppers圖像重構(gòu)對(duì)比Fig.7 Comparison of peppers image reconstruction whenthe compression ratio is 50%

圖8 壓縮比為50%時(shí)house圖像重構(gòu)對(duì)比Fig.8 Comparison of house image reconstruction whenthe compression ratio is 50%

表1、表2為使用各測(cè)量矩陣對(duì)4種圖像進(jìn)行仿真后得到的數(shù)據(jù),其中“—”表示文獻(xiàn)[6]對(duì)該類數(shù)據(jù)未進(jìn)行仿真,從兩表中的數(shù)據(jù)可以看出,當(dāng)壓縮比為70%時(shí),重構(gòu)圖像的PSNR在使用本文矩陣與部分阿達(dá)瑪矩陣時(shí)最高。當(dāng)壓縮比變?yōu)?0%時(shí),使用本文矩陣時(shí)重構(gòu)圖像的PSNR最高。本文矩陣的平均重構(gòu)時(shí)間與常用測(cè)量矩陣的重構(gòu)時(shí)間十分接近,能夠滿足實(shí)際的應(yīng)用需求。圖9表示壓縮比小于50%時(shí),各種矩陣對(duì)lena進(jìn)行仿真后的PSNR。

本文測(cè)量矩陣使用對(duì)角陣與一般矩陣相結(jié)合的形式，對(duì)角陣元素根據(jù)規(guī)則分別映射成 1和1，一般矩陣中的元素又根據(jù)正負(fù)性分別映射成1和0，在壓縮比相同的情況下，使用本文矩陣進(jìn)行壓縮感知所得到的PSNR要高于高斯隨機(jī)矩陣和伯努利矩陣。Toeplitz矩陣屬于確定性測(cè)量矩陣，此類矩陣雖然在硬件上容易實(shí)現(xiàn)，具有較高的實(shí)用性，但是重構(gòu)效果一般。學(xué)者針對(duì)此缺點(diǎn)對(duì)Toeplitz矩陣加以改進(jìn)，提出基于奇異值分解的Toeplitz結(jié)構(gòu)矩陣，但通過仿真結(jié)果可知效果仍差于本文矩陣。部分隨機(jī)測(cè)量矩陣雖然重構(gòu)效果較好，但浪費(fèi)存儲(chǔ)資源的情況比較嚴(yán)重。

表1 壓縮比為70%時(shí)測(cè)量矩陣的性能對(duì)比結(jié)果Table 1 Performance comparison results of measurement matrixes when compression ratio is 70%

表2 壓縮比為50%時(shí)測(cè)量矩陣的性能對(duì)比結(jié)果Table 2 Performance comparison results of measurement matrixes when compression ratio is 50%

圖9 壓縮比小于50%時(shí)測(cè)量矩陣峰值信噪比Fig.9 PSNR of measurement matrixes when the compressionratio is less than 50%

4 結(jié)束語(yǔ)

本文構(gòu)造一種新的壓縮感知測(cè)量矩陣,考慮到對(duì)角陣具有良好的正交性和線性非相關(guān)性,采用對(duì)角陣與一般矩陣相結(jié)合的形式得到M×N維壓縮感知測(cè)量矩陣,使用馬爾科夫鏈生成隨機(jī)數(shù),并將隨機(jī)數(shù)按照兩種規(guī)則進(jìn)行映射,映射后的結(jié)果作為兩部分矩陣中的元素。仿真結(jié)果表明,在壓縮比相同的條件下,本文提出測(cè)量矩陣的PSNR比其他測(cè)量矩陣高出約2 dB～3 dB。下一步可將壓縮感知技術(shù)與變分法和分?jǐn)?shù)階Fourier變換法相結(jié)合，應(yīng)用于圖像去噪及磁共振成像問題研究中。