安冬冬,龔曉峰,陳思南

(四川大學(xué) 電氣信息學(xué)院,成都 610065)

0 概述

傳統(tǒng)奈奎斯特采樣定律表明,想要準(zhǔn)確地還原原始信號(hào),采樣率必須大于或等于信號(hào)最高頻率的2倍。隨著數(shù)字信號(hào)處理技術(shù)的不斷發(fā)展,系統(tǒng)需要處理的數(shù)據(jù)量急劇增加,傳統(tǒng)的奈奎斯特采樣定理的弊端逐漸顯現(xiàn):采樣得到的巨大數(shù)據(jù),使得數(shù)據(jù)的傳輸與存儲(chǔ)對(duì)于存儲(chǔ)空間和硬件的數(shù)據(jù)處理能力的要求越來越嚴(yán)格,使信號(hào)采樣技術(shù)的發(fā)展受到限制。因此,有必要研究既能降低數(shù)據(jù)量,又能較好地重構(gòu)信號(hào)的技術(shù)。

文獻(xiàn)[1-2]在信號(hào)稀疏表示和信號(hào)復(fù)原等理論基礎(chǔ)上,針對(duì)稀疏可壓縮信號(hào),提出壓縮感知(Compression Sensing,CS)理論,打破了傳統(tǒng)Nyquist采樣理論對(duì)采樣頻率的限制,將壓縮和采樣合并進(jìn)行,大大減小了采樣的數(shù)據(jù)量,使得數(shù)據(jù)的傳輸處理壓力大幅減小。

在CS核心問題[3],即稀疏變換、測量矩陣構(gòu)造和重構(gòu)算法過程中,測量矩陣的相關(guān)性直接影響著重構(gòu)的效果。測量矩陣分為隨機(jī)矩陣和確定性測量矩陣2大類,隨機(jī)矩陣中常用的是高斯隨機(jī)矩陣和伯努利隨機(jī)矩陣。雖然生成的測量矩陣與大多數(shù)稀疏信號(hào)不相關(guān),重構(gòu)性能較好,但需要很大的存儲(chǔ)空間,以及由于數(shù)據(jù)隨機(jī)生成,使得硬件難實(shí)現(xiàn)等缺陷,新的方法層出不窮。有的致力于研究如何減小存儲(chǔ)空間,文獻(xiàn)[4]提出STP-CS方法打破了矩陣相乘時(shí)對(duì)維數(shù)的限制,減小了測量矩陣的大小。文獻(xiàn)[5]采用低密度奇偶校驗(yàn)碼構(gòu)造確定性測量矩陣。文獻(xiàn)[6]提出存儲(chǔ)迭代參數(shù)取代存儲(chǔ)整個(gè)矩陣的方法來減小對(duì)存儲(chǔ)空間的要求。有的致力于研究如何提高重構(gòu)精度,文獻(xiàn)[7]基于圖像分塊思想,運(yùn)用 Toeplitz的塊循環(huán)矩陣來構(gòu)造測量矩陣,在重構(gòu)效果和重構(gòu)時(shí)間上,都有所提升。文獻(xiàn)[8]采用混沌序列構(gòu)造測量矩陣。文獻(xiàn)[9]利用Legendre序列經(jīng)過二次采樣后得到確定性測量矩陣。文獻(xiàn)[10]采用范德蒙矩陣構(gòu)造的測量矩陣都在一定程度上提高了信號(hào)的重構(gòu)精度。

本文提出一種新的確定性矩陣的方法?；谡换€性表示改進(jìn)法,使用隨機(jī)數(shù)組成的行向量的循環(huán)移位法生成相關(guān)性低的正交系數(shù),將哈達(dá)瑪矩陣作為正交基。進(jìn)而構(gòu)造一種新的確定性測量矩陣,使用枚舉查找的方法打破哈達(dá)瑪矩陣的應(yīng)用局限。

1 壓縮感知基本框架

由觀測值y通過重構(gòu)算法重構(gòu)原信號(hào)x,即求解以下問題:

(1)

但是,求解式(1)是欠定問題,文獻(xiàn)[12]提出可以將式(1)的優(yōu)化目標(biāo)用l1 范數(shù)來代替:

s.t.y=Φx=Φψα

(2)

將式(1)的欠定求解問題轉(zhuǎn)換成凸優(yōu)化問題,再將其轉(zhuǎn)換成線性規(guī)劃求解的問題,完成對(duì)式(1)的求解。

文獻(xiàn)[13]提出:當(dāng)測量矩陣滿足有限等距性質(zhì)(Restricted Isometry Property,RIP)時(shí),式(1)有唯一解,稀疏信號(hào)可以得到精確重建。

定義1傳感矩陣R=Φψ的等距約束系數(shù)δ∈(0,1),θ為任意k稀疏向量,若R滿足:

(3)

其中,ψ為稀疏基,Φ為測量矩陣,則Φ滿足RIP。

RIP條件很難滿足,所以,很多學(xué)者又將條件逐漸弱化。文獻(xiàn)[14]提出:當(dāng)測量矩陣Φ和系數(shù)基ψ不相關(guān)時(shí),依舊可以將原信號(hào)進(jìn)行較好的復(fù)原。這個(gè)條件與RIP是等價(jià)的,所以可以在信號(hào)稀疏表示后,通過構(gòu)造與稀疏基不相關(guān)的測量矩陣,來完成信號(hào)的采集。文獻(xiàn)[15]通過閾值收縮的方法減小Φ和ψ的不相關(guān)性,并提出一種基于最優(yōu)投影的方法提高隨機(jī)測量矩陣的非相干性;文獻(xiàn)[16]提出QR分解法,通過增大矩陣的奇異值來優(yōu)化測量矩陣;文獻(xiàn)[17]提出基于耦合觀測法降低測量矩陣與稀疏字典之間的相干性。

2 循環(huán)輪換構(gòu)造的正交系數(shù)改進(jìn)算法

文獻(xiàn)[18]指出,在壓縮比小于 0.5的情況下,正交系數(shù)的構(gòu)造沒有簡單易控制的生成算法。針對(duì)這一問題,基于循環(huán)輪換矩陣與正交基線性表示的思想,本文提出一種新的測量矩陣構(gòu)造方法。

使用正交基線性表示測量矩陣方法的關(guān)鍵在于找到合適的正交基和正交系數(shù)的組合。哈達(dá)瑪矩陣由于其突出的正交性以及硬件易實(shí)現(xiàn)的特性,作為構(gòu)造確定性測量矩陣的正交基有著獨(dú)特的優(yōu)勢。但由于部分哈達(dá)瑪矩陣[19]構(gòu)造時(shí),對(duì)于M的值有較高的特殊要求,這使得哈達(dá)瑪矩陣的應(yīng)用受到極大局限。本文通過改進(jìn),打破了構(gòu)造哈達(dá)瑪矩陣對(duì)于M的限制。對(duì)于正交系數(shù)的構(gòu)造,使用隨機(jī)行向量的循環(huán)輪轉(zhuǎn)法,使得最終構(gòu)造的測量矩陣有較低的相關(guān)性。

本文算法步驟如下:

步驟1將二維圖像信號(hào)投影到小波變換域,得到二維圖像的稀疏表示。

步驟2根據(jù)給定的N,依次找到0～N中滿足哈達(dá)瑪矩陣構(gòu)造要求的所有數(shù)值,按從小到大排列組成一個(gè)行向量v。

步驟3根據(jù)給定的M,選擇出v中第一個(gè)不小于M的符合要求的整數(shù)L,構(gòu)成L×L的哈達(dá)瑪矩陣H,得到構(gòu)造測量矩陣所需的正交基。

這樣對(duì)于任意的M,都能有對(duì)應(yīng)的L×L的哈達(dá)瑪矩陣與之對(duì)應(yīng),打破了哈達(dá)瑪矩陣的使用局限。

步驟4使用步驟3的哈達(dá)瑪矩陣H構(gòu)成測量矩陣的前L列:

H=[h1,h2,…,hL]

(4)

其中,[hi],i=1,2,…,L為哈達(dá)瑪矩陣列歸一化后的向量。

步驟5關(guān)于正交系數(shù)的構(gòu)造,本文針對(duì)壓縮比小于0.5的情況提出一種新的方法,構(gòu)造一個(gè)隨機(jī)的1×N-L行向量:

b=[b1,b2,…,bN-L]

(5)

為滿足系數(shù)的非零要求,將式(5)做了進(jìn)一步的改進(jìn):找到其中最小的值bmin,然后將式(5)中所有值都加上|bmin|。為避免有互為相反數(shù)的情況出現(xiàn),在得到的系數(shù)矩陣中各值再加上常數(shù)1,這樣得到的系數(shù)向量滿足不相關(guān)性和非零性。

步驟6按行循環(huán)輪換L-1次,得到L×N-L維的正交系數(shù)F:

(6)

因?yàn)長

步驟7將規(guī)范正交基H與系數(shù)矩陣F相乘,得到測量矩陣剩下的N-L個(gè)列向量:

HH=H*F=[hh1,hh2,…,hhN-L]

(7)

步驟8將步驟4和步驟7得到的2個(gè)矩陣按列合并得到測量矩陣Φ:

Φ= [H,HH]=

[h1,h2,…,hL,hh1,hh2,…,hhN-L]L×N

(8)

步驟9在步驟8中得到的矩陣中任意選取M行,再進(jìn)行列單位化即可得到最終M×N的測量矩陣。

步驟10使用變步長前后追蹤算法恢復(fù)原始二維圖像。

步驟11計(jì)算相關(guān)的評(píng)價(jià)圖像恢復(fù)性能指標(biāo)的參數(shù)。

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

本次實(shí)驗(yàn)使用分辨率為256×256像素的二維Lena圖像,稀疏變換使用正交小波變換DWT將信號(hào)變換到小波域,測量矩陣分別采用Gaussian隨機(jī)矩陣、Bernoulli隨機(jī)矩陣和循環(huán)移位法生成正交系數(shù)的正交基線性構(gòu)造改進(jìn)方法,重構(gòu)算法使用變步長前后追蹤算法(Variable Step Forward Backward Pursuit,VSFBP)。使用峰值信噪比(Peak Signal to Noise Ratio,PSNR)、匹配度、運(yùn)行時(shí)間和測量矩陣的相關(guān)性作為評(píng)價(jià)重構(gòu)效果的參數(shù)。

1)二維圖像峰值信噪比pPSNR的計(jì)算:

(9)

2)匹配度的計(jì)算:

(10)

3)重構(gòu)時(shí)間為整個(gè)程序運(yùn)行1 000次的平均時(shí)間。

4)測量矩陣的相關(guān)性:

(11)

其中,ai,aj為測量矩陣的行向量,〈ai,aj〉=ai·ajT為內(nèi)積。

當(dāng)M/N=0.5,為減弱實(shí)驗(yàn)的隨機(jī)性帶來的影響,使結(jié)果更準(zhǔn)確,仿真時(shí)將每種測量矩陣生成方法都重復(fù)做了1 000次蒙特卡洛實(shí)驗(yàn),求3種算法各自性能指標(biāo)的平均值,結(jié)果如表1所示。

表1 M/N=0.5時(shí)測量矩陣的重構(gòu)性能對(duì)比

由表1可以看出:在壓縮比為0.5的條件下,本文提出的循環(huán)移位構(gòu)造正交系數(shù)改進(jìn)算法所構(gòu)造的測量矩陣圖像重構(gòu)的PSNR比Gaussian隨機(jī)矩陣和Bernoulli隨機(jī)測量矩陣要高約3.5 dB,而且匹配度比兩者高,程序運(yùn)行的時(shí)間也更低,即本文算法的算法復(fù)雜度更低。同時(shí)本文算法構(gòu)造的測量矩陣的相關(guān)性比高斯隨機(jī)矩陣和伯努利測量矩陣的相關(guān)性都低,證明了本文算法的正確性,達(dá)到了最初降低測量矩陣相關(guān)性的目的。

為更直觀地比較3種算法對(duì)二維圖像的重構(gòu)效果,只取M/N=0.5時(shí)3種測量矩陣構(gòu)造算法所恢復(fù)的圖像對(duì)比,如圖1所示。

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

從圖1可以看出,在壓縮比相同的情況下,本文提出的新的確定性測量矩陣的重構(gòu)效果比高斯隨機(jī)測量矩陣和伯努利隨機(jī)測量矩陣好,重構(gòu)圖像更清晰。為更全面地說明新的確定性測量矩陣有著更好的重構(gòu)效果,將文獻(xiàn)[20]提出的基于改進(jìn)的哈達(dá)瑪矩陣方法所構(gòu)成的測量矩陣的效果重構(gòu)結(jié)果復(fù)現(xiàn),在M/N≤0.5的情況下,與本文的測量矩陣、Gaussian測量矩陣和Bernoulli測量矩陣的重構(gòu)峰值信噪比進(jìn)行對(duì)比,結(jié)果如圖2所示。

圖2 壓縮比M/N≤0.5情況下的重構(gòu)結(jié)果

由圖2 可知,在M/N≤0.5時(shí),文中提出的基于循環(huán)移位法生成正交系數(shù)的測量矩陣改進(jìn)算法比文獻(xiàn)[20]中的改進(jìn)哈達(dá)瑪矩陣法、Gaussian隨機(jī)測量矩陣和Bernoulli測量矩陣的PSNR都要高。但當(dāng)M/N=0.1時(shí)PSNR要比文獻(xiàn)[20]中的改進(jìn)哈達(dá)瑪矩陣低,這是由于文中的測量矩陣生成時(shí)都具有隨機(jī)性,雖然已經(jīng)做了1 000次蒙特卡洛實(shí)驗(yàn)求平均值,但是這只能弱化隨機(jī)性帶來的影響,并不能消除該影響。

4 結(jié)束語

針對(duì)壓縮比小于0.5時(shí),沒有確切有效的測量矩陣構(gòu)造算法這一問題,基于正交線性表示法,本文提出遍歷查找的算法,打破了哈達(dá)瑪矩陣對(duì)被測量信號(hào)維數(shù)的限制,使得性能優(yōu)良的哈達(dá)瑪矩陣應(yīng)用可以更廣泛。并且相比傳統(tǒng)的從高維正交矩陣映射獲得測量矩陣的方法,對(duì)于壓縮比較小的情況,本文算法減小了工作量;同時(shí)使用循環(huán)移位改進(jìn)法構(gòu)造正交系數(shù),生成性能更好的測量矩陣。仿真結(jié)果表明,在壓縮比小于0.5的情況下,本文算法的圖像重構(gòu)效果依舊很清晰,比高斯和伯努利矩陣的重構(gòu)效果都好,由于采用向量的循環(huán)移位,對(duì)存儲(chǔ)空間的要求大大降低,更利于硬件的實(shí)現(xiàn),為壓縮感知的應(yīng)用提供了更廣闊的空間。

[1] CANDES 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.

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

[3] 石光明,劉丹華.壓縮感知理論及研究進(jìn)展[J].電子學(xué)報(bào),2009,37(5):1070-1081.

[4] PENG Haipeng,TIAN Ye,KURTHS J.Semitensor product compressive sensing for big data transmission in wireless sensor networks[EB/OL].[2017-03-22].https://doi.org/10.1155/2017/8158465.

[5] ZHANG Jun,HAN Guojun,FANG Yi.Deterministic construction of compressed sensing matrices from protograph LDPC codes[J].IEEE Signal Processing Letters,2015,22(11):1960-1964.

[6] RAVELOMANANTSOA A,RABAH H,ROUANE A.Compressed sensing:a simple deterministic measurement matrix and a fast recovery algorithm[J].IEEE Transactions on Instrumentation and Measurement,2015,64(12):3405-3413.

[7] 瞿廣財(cái),張淑芳,呂 衛(wèi).基于圖像分塊的Toeplitz結(jié)構(gòu)測量矩陣設(shè)計(jì)[J].計(jì)算機(jī)工程,2012,38(16):212-214,218.

[8] ZENG Li,ZHANG Xiongwei,CHEN Liang,et al.Deterministic construction of toeplitzed structurally chaotic matrix for compressed sensing[J].Circuits Systems and Signal Processing,2015,34(3):797-813.

[9] 崔 翔,萬洪杰.基于Legendre序列的確定性測量矩陣[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(16):116-120.

[10] 趙瑞珍,王若乾,張鳳珍,等.分塊的有序范德蒙矩陣作為壓縮感知測量矩陣的研究[J].電子與信息學(xué)報(bào),2015,37(6):1317-1322.

[11] 李文靜,陳紅衛(wèi).一種基于壓縮感知的ISAR成像方法[J].計(jì)算機(jī)仿真,2015,32(8):10-14.

[12] DONOHO D,TSAIG Y.Extensions of compressed sensing[J].Signal Processing,2006,86(3):533-548.

[13] CANDES E J,TAO T.Decoding by linear program-ming[J].IEEE Transaction on Information Theory,2005,51(12):4203-4215.

[14] BARANIUK R.Compressive sensing[J].IEEE Signal Processing Magazine,2007,24(4):118-121.

[15] ELAD M.Optimized projections for compressed sensing[J].IEEE Transactions on Signal Processing,2007,55(12):5695-5702.

[16] 傅迎華.可壓縮傳感重構(gòu)算法與近似QR分解[J].計(jì)算機(jī)應(yīng)用,2008,28(9):2300-2302.

[17] 吳 赟.壓縮感知測量矩陣的研究[D].西安:西安電子科技大學(xué),2012.

[18] 李 浩.用于壓縮感知的確定性測量矩陣研究[D].北京:北京交通大學(xué),2011.

[19] CANDES E.The restricted isometry property and its implications for compressed sensing[J].Proceedings of National Academy of Sciences,2008,346(9-10):589-592.

[20] 馬慶濤.壓縮感知中的信號(hào)重構(gòu)算法研究[D].南京:南京郵電大學(xué),2013.