基于馬爾科夫鏈的隨機測量矩陣研究

趙鴻圖,李 成

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

0 概述

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

1 測量矩陣

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

(1)

在求得s后,可重構出信號f,由于此問題的計算是一個NP-hard問題,通常使用l1范數來代替l0范數求解[8-9]。

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

(2)

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

由于在驗證矩陣是否滿足RIP特性時需要進行大量計算,驗證該問題變得十分困難,因此需要找到RIP特性的替代條件來解決該問題。文獻[12]指出低相關性的矩陣滿足RIP特性。本文根據該關系構造測量矩陣,并通過仿真得到相關數據,與常用的一些測量矩陣和基于奇異值分解的Toeplitz結構矩陣進行比較。

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

2 基于馬爾科夫鏈的測量矩陣構造

2.1 馬爾科夫鏈

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

2.2 基于馬爾科夫鏈的隨機測量矩陣

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

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

(3)

將此數值作為測量矩陣Φ的前M個列向量,即:

(4)

剩余的N-M個列向量也由馬爾科夫鏈產生的隨機數經過映射后構成。馬爾科夫鏈生成M×(N-M)個隨機數e1,e2,…,eM×(N-M),由于設置狀態空間內的數有正負性,因此在設置狀態空間時,生成服從標準正態分布的隨機數作為狀態空間內的數。根據規則將這些隨機數分別映射為1和0,具體映射規則為:

(5)

其中,gi,i=1,2,…,M×(N-M)為隨機數經過映射后得到的結果,由其構成測量矩陣的N-M個列向量φk,k=M+1,M+2,…,N。

(6)

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

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

(7)

將矩陣按列進行歸一化得到實際應用的測量矩陣Φ。歸一化公式如下:

(8)

測量矩陣被構造成一個對角陣和一般矩陣相組合的形式,矩陣的秩為M,相較于常用的測量矩陣而言,減少了計算量與存儲空間。

3 實驗結果與分析

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

(9)

重構時間t為:

t=te-ts

(10)

其中,te是結束時間,ts是開始時間。

平均重構時間為:

(11)

其中,L為重構次數。

從圖1～圖8的仿真結果可以看出,當壓縮比相同時,使用本文矩陣的重構效果最好。

圖1 壓縮比為70%時lena圖像重構對比Fig.1 Comparison of lena image reconstruction whenthe compression ratio is 70%

圖2 壓縮比為70%時baboon圖像重構對比Fig.2 Comparison of baboon image reconstruction whenthe compression ratio is 70%

圖3 壓縮比為70%時peppers圖像重構對比Fig.3 Comparison of peppers image reconstruction whenthe compression ratio is 70%

圖4 壓縮比為70%時house圖像重構對比Fig.4 Comparison of house image reconstruction whenthe compression ratio is 70%

圖5 壓縮比為50%時lena圖像重構對比Fig.5 Comparison of lena image reconstruction whenthe compression ratio is 50%

圖6 壓縮比為50%時baboon圖像重構對比Fig.6 Comparison of baboon image reconstruction whenthe compression ratio is 50%

圖7 壓縮比為50%時peppers圖像重構對比Fig.7 Comparison of peppers image reconstruction whenthe compression ratio is 50%

圖8 壓縮比為50%時house圖像重構對比Fig.8 Comparison of house image reconstruction whenthe compression ratio is 50%

表1、表2為使用各測量矩陣對4種圖像進行仿真后得到的數據,其中“—”表示文獻[6]對該類數據未進行仿真,從兩表中的數據可以看出,當壓縮比為70%時,重構圖像的PSNR在使用本文矩陣與部分阿達瑪矩陣時最高。當壓縮比變為50%時,使用本文矩陣時重構圖像的PSNR最高。本文矩陣的平均重構時間與常用測量矩陣的重構時間十分接近,能夠滿足實際的應用需求。圖9表示壓縮比小于50%時,各種矩陣對lena進行仿真后的PSNR。

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

表1 壓縮比為70%時測量矩陣的性能對比結果Table 1 Performance comparison results of measurement matrixes when compression ratio is 70%

表2 壓縮比為50%時測量矩陣的性能對比結果Table 2 Performance comparison results of measurement matrixes when compression ratio is 50%

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

4 結束語

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