趙瑞珍王若乾 張鳳珍 岑翼剛 胡紹海

(北京交通大學(xué)信息科學(xué)研究所 北京 100044)

(現(xiàn)代信息科學(xué)與網(wǎng)絡(luò)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室 北京 100044)

分塊的有序范德蒙矩陣作為壓縮感知測(cè)量矩陣的研究

趙瑞珍*王若乾 張鳳珍 岑翼剛 胡紹海

(北京交通大學(xué)信息科學(xué)研究所 北京 100044)

(現(xiàn)代信息科學(xué)與網(wǎng)絡(luò)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室 北京 100044)

測(cè)量矩陣是壓縮感知(Compressed Sensing, CS)的重要組成部分，確定性的測(cè)量矩陣易于硬件實(shí)現(xiàn)，但是重構(gòu)信號(hào)的精度一般不如隨機(jī)矩陣。針對(duì)這一缺點(diǎn)，該文提出并構(gòu)造了一種新的確定性測(cè)量矩陣，稱作分塊的有序范德蒙矩陣。范德蒙矩陣具有線性不相關(guān)的性質(zhì)，在此基礎(chǔ)上加上分塊操作和對(duì)元素進(jìn)行有序排列得到的分塊的有序范德蒙矩陣，實(shí)現(xiàn)了時(shí)域中的非均勻采樣，特別適合于維數(shù)較大的自然圖像信號(hào)。仿真實(shí)驗(yàn)表明，對(duì)于圖像信號(hào)該矩陣具有遠(yuǎn)高于高斯矩陣的重構(gòu)精度，可以作為實(shí)際中的測(cè)量矩陣使用。

壓縮感知；測(cè)量矩陣；線性不相關(guān)；非均勻采樣；范德蒙矩陣

1 引言

壓縮感知(Compressive Sensing, CS)[1?3]是針對(duì)稀疏或可壓縮信號(hào)的壓縮采樣理論，該理論在信號(hào)的獲取方式上突破了傳統(tǒng)的奈奎斯特采樣定理。奈奎斯特采樣定理要求采樣頻率高于采樣信號(hào)的兩倍帶寬，而壓縮感知要求采樣信號(hào)是稀疏的或是在變換域是稀疏的，使得壓縮感知可以在遠(yuǎn)小于奈奎斯特采樣速率的條件下對(duì)信號(hào)進(jìn)行采樣的同時(shí)對(duì)信號(hào)進(jìn)行壓縮，因此，壓縮感知克服了采樣數(shù)據(jù)量巨

2014-06-30收到，2015-03-03改回

國(guó)家自然科學(xué)基金(61073079)，中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金(2013JBZ003)，高等學(xué)校博士點(diǎn)基金(20120009110008)和教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃(NCET-12-0768)資助課題

*通信作者：趙瑞珍 rzhzhao@bjtu.edu.cn大，傳感元、采樣時(shí)間以及數(shù)據(jù)存儲(chǔ)空間等物理資源浪費(fèi)嚴(yán)重的問(wèn)題。

壓縮感知理論主要包括信號(hào)的獲取和信號(hào)的重構(gòu)兩個(gè)部分，在這兩部分中測(cè)量矩陣都起著重要的作用。首先，在信號(hào)獲取端，測(cè)量矩陣的優(yōu)劣關(guān)系著信號(hào)測(cè)量數(shù)目的多少，相對(duì)于低劣的測(cè)量矩陣，優(yōu)良的測(cè)量矩陣可以在較少的測(cè)量數(shù)目下達(dá)到相同的重構(gòu)精度。其次，在重構(gòu)端，在相同的采樣率下得到數(shù)據(jù)，優(yōu)良的測(cè)量矩陣對(duì)信號(hào)的重構(gòu)精度要高于低劣的測(cè)量矩陣。

在壓縮感知之初，測(cè)量矩陣普遍采用隨機(jī)矩陣用于理論研究。隨機(jī)測(cè)量矩陣雖然在理論上完美，但是在硬件實(shí)現(xiàn)上非常困難。出于對(duì)實(shí)際問(wèn)題的考慮，尤其是在單像素相機(jī)[4]研制出之后，大部分學(xué)者轉(zhuǎn)向研究確定性的測(cè)量矩陣和結(jié)構(gòu)性的測(cè)量矩陣。截至目前，國(guó)內(nèi)外學(xué)者經(jīng)過(guò)嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明和反復(fù)的實(shí)驗(yàn)驗(yàn)證，已提出多種測(cè)量矩陣：確定性測(cè)量矩陣中如多項(xiàng)式測(cè)量矩陣[5]、基于混沌序列的測(cè)量矩陣[6]以及近年來(lái)將編碼理論用于該領(lǐng)域得到的各種校驗(yàn)碼測(cè)量矩陣[7,8]，其中多項(xiàng)式測(cè)量矩陣和校驗(yàn)碼矩陣對(duì)稀疏信號(hào)重構(gòu)效果較好，但是對(duì)矩陣的行數(shù)和列數(shù)要求十分嚴(yán)格，而且對(duì)可壓縮信號(hào)重構(gòu)較差，基于混沌序列的測(cè)量矩陣是稠密矩陣，需要占用較多的存儲(chǔ)空間；結(jié)構(gòu)性的測(cè)量矩陣中如分塊壓縮感知的測(cè)量矩陣[9]、稀疏隨機(jī)矩陣[10]、托普利茲矩陣[11]、廣義輪換矩陣[12]，其中構(gòu)成分塊壓縮感知測(cè)量矩陣的子矩陣和稀疏隨機(jī)矩陣是隨機(jī)矩陣，相對(duì)于確定性矩陣來(lái)說(shuō)，硬件實(shí)現(xiàn)上仍然困難，托普利茲矩陣和廣義輪換矩陣具有一定的結(jié)構(gòu)，減少了存儲(chǔ)空間，但是重構(gòu)精度一般。

針對(duì)上述測(cè)量矩陣的優(yōu)缺點(diǎn)，本文提出并構(gòu)造了一種新的確定性測(cè)量矩陣，分塊的有序范德蒙矩陣。范德蒙矩陣具有線性不相關(guān)的性質(zhì)[13]，將分塊和非均勻采樣[12,14]的思想引入其中得到的分塊的有序范德蒙矩陣具有了一定的結(jié)構(gòu)性。這種新的測(cè)量矩陣占用存儲(chǔ)空間少，易于硬件實(shí)現(xiàn)，而且仿真實(shí)驗(yàn)表明，其對(duì)自然圖像具有遠(yuǎn)高于高斯矩陣的重構(gòu)精度。

2 基本理論

設(shè)x是長(zhǎng)度為N的稀疏信號(hào)，經(jīng)過(guò)線性測(cè)量后得到長(zhǎng)度為M(M＜N)的觀測(cè)信號(hào)y，它們之間的關(guān)系可以表示為：

2.1 壓縮感知

其中矩陣Φ稱為測(cè)量矩陣，大小為M×N。如果x是可壓縮信號(hào)，可以把x變換到稀疏域中表示，即x=Ψs，其中s是N維的稀疏向量，Ψ是N×N大小的稀疏表示基。把該式代入式(1)得到：

其中矩陣Θ=ΦΨ稱為傳感矩陣，大小為M×N。

上述過(guò)程即為壓縮感知的信號(hào)獲取過(guò)程，這個(gè)過(guò)程是線性的。而信號(hào)的重構(gòu)過(guò)程是非線性的，當(dāng)x是稀疏信號(hào)時(shí)，重構(gòu)的數(shù)學(xué)表達(dá)式為

求解式(3)可以直接重構(gòu)出原始信號(hào)x。當(dāng)x是可壓縮信號(hào)時(shí)，重構(gòu)的數(shù)學(xué)表達(dá)式為

對(duì)于式(4)，為了重構(gòu)出原始信號(hào)x，需要把求得的s代入x=Ψs中。由于式(3)和式(4)的l0范數(shù)最小化問(wèn)題是一個(gè)NP-hard問(wèn)題，可以使用l1范數(shù)代替求解，具體參見文獻(xiàn)[3]。重構(gòu)過(guò)程用到的一些重構(gòu)算法具體參見文獻(xiàn)[15]。

2.2 測(cè)量矩陣

從壓縮感知的整個(gè)過(guò)程中可以看出測(cè)量矩陣起著關(guān)鍵作用，是壓縮感知的重要組成部分。為了能夠精確重構(gòu)信號(hào)，文獻(xiàn)[2]給出了測(cè)量矩陣需要滿足的3個(gè)特征：(1)由測(cè)量矩陣的列向量組成的子矩陣的最小奇異值必須大于一定的常數(shù)，也即：測(cè)量矩陣的列向量滿足一定的線性獨(dú)立性；(2)測(cè)量矩陣的列向量體現(xiàn)某種類似噪聲的獨(dú)立隨機(jī)性；(3)滿足稀疏度的解是滿足1-范數(shù)最小的向量。這3個(gè)特征對(duì)測(cè)量矩陣的構(gòu)造起著重要的指導(dǎo)作用。

測(cè)量矩陣就確定性方面可以分為隨機(jī)測(cè)量矩陣和確定性測(cè)量矩陣。隨機(jī)測(cè)量矩陣的每一個(gè)元素都是獨(dú)立同分布的，保證了測(cè)量矩陣列與列之間的不相關(guān)性，較好的滿足了上述3個(gè)特征，因此對(duì)測(cè)量信號(hào)具有普遍適用性，而且用較少的采樣便可獲得較精確的重構(gòu)。同時(shí)，正是由于隨機(jī)矩陣每一個(gè)元素都獨(dú)立地服從同一分布，之間沒(méi)有任何的相關(guān)性和結(jié)構(gòu)性，使得每一個(gè)元素都要存儲(chǔ)，耗費(fèi)大量的存儲(chǔ)空間，不利于硬件實(shí)現(xiàn)。確定性測(cè)量矩陣的元素的位置和值都是確定的，易于硬件電路實(shí)現(xiàn)，但是對(duì)上述3個(gè)特征的符合度不如隨機(jī)測(cè)量矩陣，因此在普適性和重構(gòu)能力上一般次于隨機(jī)測(cè)量矩陣。盡管隨機(jī)測(cè)量矩陣的重構(gòu)性能較為理想，但是出于對(duì)硬件電路實(shí)現(xiàn)問(wèn)題的解決，對(duì)確定性測(cè)量矩陣的研究尤為必要。

3 分塊的有序范德蒙矩陣

本文以第2.2節(jié)中提到的測(cè)量矩陣需要滿足的3個(gè)特征為出發(fā)點(diǎn)，并且注意到自然圖像在頻域的稀疏系數(shù)集中分布在低頻段的性質(zhì)[12]，通過(guò)分析范德蒙矩陣，利用有效的方法將其改造為易于硬件實(shí)現(xiàn)且重構(gòu)精度較高的測(cè)量矩陣。

3.1 范德蒙矩陣

范德蒙矩陣是一個(gè)各列或各行呈現(xiàn)出幾何級(jí)數(shù)關(guān)系的矩陣，例如，式(5)的矩陣V就是一個(gè)m×n大小的范德蒙矩陣：

范德蒙矩陣有一個(gè)良好的性質(zhì)，即，當(dāng)ai(i= 1,2,…,n)互不相等時(shí)，從矩陣V中任意選取的k(k≤min(m,n ))個(gè)列向量或者行向量都是線性無(wú)關(guān)的[13]。這與文獻(xiàn)[2]提出的測(cè)量矩陣應(yīng)具有的第(1)個(gè)特征相符，即，測(cè)量矩陣的列向量滿足一定的線性獨(dú)立性。

3.2 分塊的范德蒙矩陣

一般自然圖像信號(hào)的行列維數(shù)都比較高，可以達(dá)到102～103的數(shù)量級(jí)或者更高，即便采用分塊掃描或者逐列掃描方式采樣，直接使用范德蒙矩陣V進(jìn)行測(cè)量，行數(shù)m和列數(shù)n也都將在102～103的數(shù)量級(jí)，相對(duì)于ai(i=1,2,…,n)來(lái)說(shuō)將會(huì)是非常大(當(dāng)ai＞1)或者非常小(當(dāng)ai＜1)的數(shù)值，這樣用硬件實(shí)現(xiàn)起來(lái)將會(huì)非常困難；如果盡量使ai接近于1，使/ai不至于太大或者太小，那么會(huì)造成ai≈aj(i,j=1,2,…,n,i≠j )，這樣列向量之間的非相關(guān)性就會(huì)減弱，從而降低信號(hào)的重構(gòu)精度。因此將范德蒙矩陣直接用作測(cè)量矩陣并不是一個(gè)可取的辦法，應(yīng)該采取其他手段對(duì)范德蒙矩陣進(jìn)行改進(jìn)，使其易于硬件實(shí)現(xiàn)，同時(shí)列向量之間的非相關(guān)性不至于降低。

由上面的分析可知，范德蒙矩陣V的行數(shù)m和列數(shù)n應(yīng)該取很小的值，這樣易于硬件實(shí)現(xiàn)，同時(shí)ai(i=1,2,…,n)之間不能太接近，以確保列向量之間較強(qiáng)的非相關(guān)性。結(jié)合這兩點(diǎn)，本文采用分塊的方法對(duì)范德蒙矩陣進(jìn)行改進(jìn)，使范德蒙矩陣作為測(cè)量矩陣的子塊(子矩陣)，對(duì)角排列成一個(gè)維數(shù)較大的測(cè)量矩陣，并稱該測(cè)量矩陣為分塊的范德蒙矩陣。對(duì)一個(gè)m×n的范德蒙矩陣V，對(duì)角排列成M×N的分塊的范德蒙矩陣ΦB，而ΦB的非對(duì)角子矩陣全為零矩陣，即：

其中M/m=N/n=L 為塊數(shù)。這樣構(gòu)造的測(cè)量矩陣使得范德蒙矩陣V的行數(shù)m和列數(shù)n都可以是非常小的整數(shù)，同時(shí)也可以使ai(i=1,2,…,n)之間的取值有一定差距，保證了列向量之間較強(qiáng)的非相關(guān)性。

3.3 分塊的有序范德蒙矩陣

如果分塊的范德蒙矩陣ΦB中子矩陣V的元素ai(i=1,2,…,n ?1)滿足ai＜ai+1，本文稱這種分塊的范德蒙矩陣為分塊的有序范德蒙矩陣ΦBO。這種元素的有序排列可以保證自然圖像信號(hào)進(jìn)行稀疏分解時(shí)稀疏基和稀疏系數(shù)的對(duì)應(yīng)結(jié)構(gòu)性，在時(shí)域采樣時(shí)實(shí)現(xiàn)非均勻采樣，加強(qiáng)對(duì)低頻段的采樣，提高信號(hào)的重構(gòu)精度。需要強(qiáng)調(diào)的是文獻(xiàn)[12]和文獻(xiàn)[14]的非均勻采樣需要把信號(hào)變換到變換域后實(shí)現(xiàn)，而分塊的有序范德蒙矩陣的非均勻采樣可以直接在時(shí)域采樣中實(shí)現(xiàn)。

由上述測(cè)量矩陣ΦBO的構(gòu)造過(guò)程，可以發(fā)現(xiàn)對(duì)ΦBO分的塊越小越利于硬件實(shí)現(xiàn)。不僅如此，在信號(hào)采樣時(shí)，塊越小計(jì)算復(fù)雜度越低。因?yàn)槌砻芫仃囋诓蓸訒r(shí)需要進(jìn)行MN次乘法運(yùn)算，M(N?1)次加法運(yùn)算，分塊的有序范德蒙矩陣只需要Mn次乘法和M(n?1)次加法運(yùn)算，而n比N要小得多。但是這并不意味著分的塊越小越好，塊越小往往會(huì)導(dǎo)致重構(gòu)的精度越低，這是因?yàn)閴K越小零元素越多，采樣時(shí)得到的信息量一般就越少。因此在實(shí)際問(wèn)題中需要對(duì)塊的大小和重構(gòu)精度進(jìn)行折中考慮。同時(shí)，本文還可以發(fā)現(xiàn)，稠密矩陣與分塊的有序范德蒙矩陣在采樣時(shí)的總體計(jì)算復(fù)雜度之比約為N/n，當(dāng)信號(hào)維數(shù)N越大時(shí)(n固定不變)，比值N/n越大，這說(shuō)明分塊的有序范德蒙矩陣相比稠密矩陣更利于采樣維數(shù)較高的信號(hào)。

通過(guò)上述分析，本文可以得到分塊的有序范德蒙矩陣具有以下優(yōu)點(diǎn)：分塊方法的采用使矩陣產(chǎn)生了大量的零元素，而且ai(i=1,2,…,n)可以取整數(shù)，使得測(cè)量矩陣易于硬件實(shí)現(xiàn)；ai(i=1,2,…,n)的取值不同，使列向量之間有較強(qiáng)的非相關(guān)性，保證了信號(hào)的較高重構(gòu)精度；矩陣元素有序性的排列實(shí)現(xiàn)了時(shí)域中的非均勻采樣，加強(qiáng)了低頻段的采樣，進(jìn)一步提高了對(duì)信號(hào)的重構(gòu)精度；不同塊的列向量之間非零元素的位置是不重疊的，采樣的信號(hào)段也會(huì)不同，因此可以進(jìn)行并行采樣，減少采樣時(shí)間；相對(duì)于稠密矩陣，分塊的測(cè)量矩陣降低了信號(hào)采樣時(shí)的計(jì)算復(fù)雜度，更利于采樣維數(shù)較高的信號(hào)；測(cè)量矩陣的生成并沒(méi)有復(fù)雜的運(yùn)算，只有冪乘和復(fù)制操作，因此生成時(shí)間也非常短；分塊和對(duì)角排列使測(cè)量矩陣具有很強(qiáng)的結(jié)構(gòu)性，對(duì)M×N大小的測(cè)量矩陣ΦBO只需存儲(chǔ)m×n 的范德蒙矩陣V和塊數(shù)L，極大地減少了存儲(chǔ)空間。進(jìn)一步，根據(jù)有序性，可以使ai(i=1,2,…,n)為等差數(shù)列，這時(shí)只需存儲(chǔ)初始值a1、公差d、子塊的行數(shù)m、子塊的列數(shù)n以及塊數(shù)L這幾個(gè)數(shù)值就可以生成整個(gè)矩陣。因此，這樣構(gòu)造的測(cè)量矩陣對(duì)硬件是極其友好的，而且有利于自然圖像信號(hào)重構(gòu)。

4 仿真與分析

本文采用2維圖像信號(hào)進(jìn)行仿真實(shí)驗(yàn)，對(duì)分塊的有序范德蒙矩陣的重構(gòu)性能進(jìn)行了驗(yàn)證，作為對(duì)比實(shí)驗(yàn)的測(cè)量矩陣有常用的高斯隨機(jī)矩陣、確定性測(cè)量矩陣中的基于混沌序列的測(cè)量矩陣以及結(jié)構(gòu)性測(cè)量矩陣中常用的托普利茲矩陣。同時(shí)，為了驗(yàn)證元素的有序性排列實(shí)現(xiàn)了非均勻采樣并且提高了信號(hào)的重構(gòu)精度，本文加入了對(duì)元素?zé)o序排列的分塊的范德蒙矩陣的比較。本文所有實(shí)驗(yàn)都是在Matlab2012a下進(jìn)行的，使用的是3.00 GHz的雙核臺(tái)式計(jì)算機(jī)。稀疏基Ψ采用DCT基，重構(gòu)算法采用SL0算法[16]。首先，分別對(duì)大小為256×256的Lena, Peppers, Cameraman和Boats圖像在時(shí)域中進(jìn)行了采樣并重構(gòu)。為了便于實(shí)驗(yàn)，本文對(duì)2維圖像進(jìn)行逐列采樣和重構(gòu)，因此各測(cè)量矩陣Φ的列數(shù)N=256。當(dāng)采樣率R=M/N=0.5時(shí)各測(cè)量矩陣對(duì)圖像重構(gòu)的結(jié)果如表1所示。

表1中分塊的有序范德蒙矩陣的子矩陣V大小為4×8, ai采用等差序列，初值a1=1，公差d=1；分塊的范德蒙矩陣是對(duì)分塊的有序范德蒙矩陣進(jìn)行隨機(jī)亂序后得到的，由于隨機(jī)性因素的存在，由它和高斯隨機(jī)矩陣以及托普利茲矩陣所得到的結(jié)果都是在重復(fù)進(jìn)行1000次實(shí)驗(yàn)后求得的平均值，下面的實(shí)驗(yàn)也如此處理。

表1 采樣率為0.5時(shí)，各測(cè)量矩陣對(duì)圖像重構(gòu)PSNR(dB)的比較

由表1可以看出，高斯隨機(jī)矩陣和基于混沌序列測(cè)量矩陣對(duì)信號(hào)重構(gòu)的PSNR比較接近，托普利茲矩陣的重構(gòu)精度最低；分塊的范德蒙矩陣對(duì)信號(hào)的重構(gòu)精度高于上述3個(gè)測(cè)量矩陣，說(shuō)明矩陣列向量的非相關(guān)性有利于信號(hào)重構(gòu)；分塊的有序范德蒙矩陣的重構(gòu)精度比分塊的范德蒙矩陣有進(jìn)一步的提升，說(shuō)明元素的有序性排列起了作用，但是還無(wú)法說(shuō)明它實(shí)現(xiàn)了非均勻采樣。

為了便于從視覺(jué)角度上進(jìn)行比較，圖1列出了上述實(shí)驗(yàn)各測(cè)量矩陣對(duì)Lena圖像重構(gòu)后的效果圖，從視覺(jué)角度看，分塊的有序范德蒙矩陣也遠(yuǎn)遠(yuǎn)優(yōu)于其他測(cè)量矩陣。

為了進(jìn)一步驗(yàn)證本文提出的測(cè)量矩陣相比其它測(cè)量矩陣在重構(gòu)精度上具有明顯優(yōu)勢(shì)，本文在不同的采樣率下，用上述測(cè)量矩陣對(duì)Lena圖像在時(shí)域進(jìn)行了采樣并重構(gòu)，重構(gòu)結(jié)果如圖2所示(在不同采樣率下的分塊的有序范德蒙矩陣按以下方式取得：采樣率為0.1～0.8時(shí)，子塊V的行m固定為4，采樣率為0.9時(shí)，m固定為9；列n根據(jù)采樣率取大于等于mN/M的最小整數(shù)，對(duì)得到的整個(gè)矩陣取前M行和前N列即為測(cè)量矩陣。分塊的范德蒙矩陣是在對(duì)應(yīng)采樣率的分塊的有序范德蒙矩陣的基礎(chǔ)上進(jìn)行隨機(jī)亂序得到的)。由圖2結(jié)果可見，分塊的有序范德蒙矩陣在任何采樣率下都優(yōu)于其它測(cè)量矩陣。

圖1 各測(cè)量矩陣對(duì)Lena圖像重構(gòu)效果比較

圖2 各測(cè)量矩陣對(duì)Lena圖像在不同采樣率下重構(gòu)結(jié)果比較

上述實(shí)驗(yàn)，從分塊的有序范德蒙矩陣和分塊的范德蒙矩陣的對(duì)比中可以看出，元素的有序性排列的確提高了信號(hào)的重構(gòu)精度，但是還不能說(shuō)明分塊的有序范德蒙矩陣實(shí)現(xiàn)了非均勻采樣。為了驗(yàn)證其實(shí)現(xiàn)了非均勻采樣，加強(qiáng)了對(duì)低頻部分的采樣，本文進(jìn)行了如下實(shí)驗(yàn)：用不同的測(cè)量矩陣在采樣率R=0.5下分別對(duì)Lena圖像在時(shí)域進(jìn)行采樣并重構(gòu)，然后再分別比較重構(gòu)圖像的高頻部分和低頻部分的相對(duì)誤差。相對(duì)誤差公式為100%，其中fr表示重構(gòu)圖像的DCT系數(shù)，fo表示原始圖像的DCT系數(shù)，計(jì)算高頻部分相對(duì)誤差時(shí)，fr, fo采用高頻部分DCT系數(shù)，計(jì)算低頻部分相對(duì)誤差時(shí)，fr, fo采用低頻部分DCT系數(shù)(不包含直流系數(shù))，計(jì)算總的相對(duì)誤差時(shí)，fr, fo采用全部DCT系數(shù)。實(shí)驗(yàn)結(jié)果如表2所示。

由表2可以看出，高頻部分，除分塊的有序范德蒙矩陣的相對(duì)誤差相對(duì)較大外，其余測(cè)量矩陣的相對(duì)誤差比較接近；而低頻部分，各個(gè)測(cè)量矩陣的相對(duì)誤差差距較大。這是因?yàn)閳D像信號(hào)低頻系數(shù)數(shù)值較大，容易重構(gòu)，而高頻系數(shù)較小且普遍接近于零，不易精確重構(gòu)，所以各個(gè)測(cè)量矩陣重構(gòu)誤差主要體現(xiàn)在低頻部分。分塊的有序范德蒙矩陣和分塊的范德蒙矩陣只有元素排列順序的差別，從兩者對(duì)Lena圖像高低頻相對(duì)誤差的差距中可以看出，分塊的有序范德蒙矩陣加強(qiáng)了對(duì)低頻部分的采樣，使得低頻部分的重構(gòu)誤差有較大幅度的降低，高頻部分的重構(gòu)誤差有一定增加，又由于該實(shí)驗(yàn)是在時(shí)域中進(jìn)行的，這說(shuō)明分塊的有序范德蒙矩陣在時(shí)域中實(shí)現(xiàn)了非均勻采樣。通過(guò)表2中的總的相對(duì)誤差可以看出，這種非均勻采樣從整體上提高了測(cè)量矩陣對(duì)圖像的重構(gòu)精度。

考慮到塊大小對(duì)實(shí)際應(yīng)用有著重要的影響作用，本文還對(duì)不同塊大小情況下的分塊的有序范德蒙矩陣進(jìn)行了實(shí)驗(yàn)。在采樣率R=0.5以及塊大小分別為3×6, 4×8, 5×10和6×12的情況下，分別對(duì)大小為256×256的Lena, Peppers, Cameraman和Boats圖像在時(shí)域中進(jìn)行了采樣并重構(gòu)，重構(gòu)效果如表3所示。

通過(guò)表3的縱向比較，可以得出分的塊越大，圖像的重構(gòu)精度越高，這和第3.3節(jié)中的分析是一致的。但是隨著分塊大小的逐漸變大，重構(gòu)精度的提升也越來(lái)越小，這主要是因?yàn)樽泳仃囍衋n和an?1的相對(duì)差距越來(lái)越小(即越來(lái)越小)，導(dǎo)致了相應(yīng)列的非相關(guān)性降低。同時(shí)，還應(yīng)注意到，并不是分塊越大越好，分塊越大反而增加了硬件電路實(shí)現(xiàn)的難度(太大的塊也毫無(wú)實(shí)際意義，因?yàn)橹笖?shù)增長(zhǎng)太快了，硬件難以實(shí)現(xiàn))，也增加了采樣時(shí)的計(jì)算復(fù)雜度。所以，在實(shí)際的應(yīng)用情況中，應(yīng)有一個(gè)折衷的考慮。

表2 采樣率為0.5時(shí)，各測(cè)量矩陣重構(gòu)Lena圖像的高、低頻相對(duì)誤差(%)

表3 分塊的有序范德蒙矩陣在不同塊大小情況下對(duì)各圖像重構(gòu)PSNR(dB)的比較

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

本文提出了一種新的確定性測(cè)量矩陣，即分塊的有序范德蒙矩陣。范德蒙矩陣具有線性不相關(guān)的優(yōu)良性質(zhì)，但是其元素呈現(xiàn)出的幾何級(jí)數(shù)關(guān)系限制了其直接作為測(cè)量矩陣的使用。本文采用分塊的技術(shù)，將其改造為矩陣元素可以是整數(shù)且極其稀疏的矩陣，同時(shí)還保留了向量線性不相關(guān)的性質(zhì)。注意到自然圖像在頻域的稀疏系數(shù)集中分布在低頻段的特點(diǎn)，本文又將范德蒙矩陣的元素進(jìn)行了有序排列，實(shí)現(xiàn)了時(shí)域的非均勻采樣。大量實(shí)驗(yàn)表明，通過(guò)分塊和排序得到的分塊的有序范德蒙矩陣對(duì)2維圖像信號(hào)的重構(gòu)精度遠(yuǎn)遠(yuǎn)高于高斯隨機(jī)矩陣等。同時(shí)，該矩陣還具有構(gòu)造簡(jiǎn)單、占用存儲(chǔ)空間少和計(jì)算復(fù)雜度低等優(yōu)點(diǎn)。因此，分塊的有序范德蒙矩陣是一種極易于硬件實(shí)現(xiàn)且重構(gòu)精度較高的測(cè)量矩陣。

[1] Candes E J, Romberg J, and Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.

[2] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[3] Donoho D L and Tsaig Y. Extensions of compressed sensing[J]. Signal Processing, 2006, 86(3): 533-548.

[4] Duarte M F, Davenport M A, Takhar D, et al.. Single-pixel imaging via compressive sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2): 83-91.

[5] DeVore R. Deterministic constructions of compressed sensing matrices[J]. Journal of Complexity, 2007, 23(46): 918-925.

[6] 林斌, 彭玉樓. 基于混沌序列的壓縮感知測(cè)量矩陣構(gòu)造算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2013, 49(23): 199-202.

Lin Bin and Peng Yu-lou. Measurement matrix construction algorithm for compressed sensing based on chaos sequence[J]. Computer Engineering and Applications, 2013, 49(23): 199-202.

[7] Mohades M M, Mohades A, and Tadaion A. A reed-solomon code based measurement matrix with small coherence[J]. IEEE Signal Processing Letters, 2014, 21(7): 839-843.

[8] Liu Xin-ji and Xia Shu-tao. Constructions of quasi-cyclic measurement matrices based on array codes[C]. Proceedings of the IEEE International Symposium on Information Theory, Istanbul, Turkey, 2013: 479-483.

[9] Gan L. Block compressed sensing of natural images[C]. 15th IEEE International Conference on Digital Signal Processing, Cardiff, Wales, 2007: 403-406.

[10] 張波, 劉郁林, 王開. 稀疏隨機(jī)矩陣有限等距性質(zhì)分析[J]. 電子與信息學(xué)報(bào), 2014, 36(1): 169-174.

Zhang Bo, Liu Yu-lin, and Wang Kai. Restricted isometry property analysis for sparse random matrices[J]. Journal of Electronics & Information Technology, 2014, 36(1): 169-174.

[11] Bajwa W U, Haupt J, Raz G, et al.. Toeplitz-structured compressed sensing matrices[C]. Proceedings of the IEEE Workshop on Statistical Signal Processing (SSP), Madison, USA, 2007: 294-298.

[12] Zhao Rui-zhen, Li Hao, Qin Zhou, et al.. A new construction method for generalized Hadamard matrix in compressive sensing[C]. Proceedings of the 2011 Cross-Strait Conference on Information Science and Technology, Danshui, China, 2011: 309-313.

[13] 居余馬. 線性代數(shù)[M]. 第2版, 北京: 清華大學(xué)出版社, 2002: 17-18.

Ju Yu-ma. Linear Algebra[M]. 2nd Edition, Beijing: Tsinghua University Press, 2002: 17-18.

[14] Jalbin J, Hemalatha R, and Radha S. Two measurement matrix based nonuniform sampling for wireless sensor networks[C]. Proceedings of the 3rd International Conference on Computing Communication & Networking Technologies (ICCCNT'2012), Coimbatore, India, 2012: 1-4.

[15] 李珅, 馬彩文, 李艷, 等. 壓縮感知重構(gòu)算法綜述[J]. 紅外與激光工程, 2013, 42(S1): 225-232.

Li Kun, Ma Cai-wen, Li Yan, et al.. Survey on reconstruction algorithm based on compressive sensing[J]. Infrared and Laser Engineering, 2013, 42(S1): 225-232.

[16] Mohimani H, Babaie-Zadeh M, and Jutten C. A fast approach for overcomplete sparse decomposition based on smoothed l0norm[J]. IEEE Transactions on Signal Processing, 2009, 57(1): 289-301.

趙瑞珍： 男，1975年生，博士，教授，研究方向?yàn)閳D像處理、小波變換、壓縮感知等.

王若乾： 男，1986年生，碩士生，研究方向?yàn)閴嚎s感知測(cè)量矩陣構(gòu)造與優(yōu)化.

張鳳珍： 女，1983年生，博士生，研究方向?yàn)閴嚎s感知及其應(yīng)用.

Research on the Blocked Ordered Vandermonde Matrix Used as Measurement Matrix for Compressed Sensing

Zhao Rui-zhen Wang Ruo-qian Zhang Feng-zhen Cen Yi-gang Hu Shao-hai
(Institute of Information Science, Beijing Jiaotong University, Beijing 100044, China)
(Key Laboratory of Advanced Information Science and Network Technology of Beijing, Beijing 100044, China)

The measurement matrix is an important part of Compressed Sensing (CS). Although the deterministic matrix is easy to implement by the hardware, it performs not so well as a random matrix in the signal reconstruction. To solve this problem, a new deterministic measurement matrix which is called as the blocked ordered Vandermonde matrix is proposed. The blocked ordered Vandermonde matrix is constructed on the basis of the Vandermonde matrix, whose the vectors are linearly independent. Then the block operation is taken and its elements are sorted. The proposed new measurement matrix realizes the non-uniform sampling in the time domain and is specifically suitable for the natural images whose the dimension is usually high. The simulation results show that the proposed matrix is much superior to the Gaussian matrix in the image construction, and can be used in practice.

Compressed Sensing (CS); Measurement matrix; Linear independence; Non-uniform sampling; Vandermonde matrix

TN911.7

：A

：1009-5896(2015)06-1317-06

10.11999/JEIT140860