循環(huán)移位正交系數(shù)的測量矩陣改進算法

安冬冬,龔曉峰,陳思南

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

0 概述

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

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

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

本文提出一種新的確定性矩陣的方法。基于正交基線性表示改進法,使用隨機數(shù)組成的行向量的循環(huán)移位法生成相關性低的正交系數(shù),將哈達瑪矩陣作為正交基。進而構造一種新的確定性測量矩陣,使用枚舉查找的方法打破哈達瑪矩陣的應用局限。

1 壓縮感知基本框架

由觀測值y通過重構算法重構原信號x,即求解以下問題:

(1)

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

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

(2)

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

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

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

(3)

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

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

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

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

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

本文算法步驟如下:

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

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

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

這樣對于任意的M,都能有對應的L×L的哈達瑪矩陣與之對應,打破了哈達瑪矩陣的使用局限。

步驟4使用步驟3的哈達瑪矩陣H構成測量矩陣的前L列:

H=[h1,h2,…,hL]

(4)

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

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

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

(5)

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

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

(6)

因為L

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

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

(7)

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

Φ= [H,HH]=

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

(8)

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

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

步驟11計算相關的評價圖像恢復性能指標的參數(shù)。

3 實驗設置與結果分析

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

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

(9)

2)匹配度的計算:

(10)

3)重構時間為整個程序運行1 000次的平均時間。

4)測量矩陣的相關性:

(11)

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

當M/N=0.5,為減弱實驗的隨機性帶來的影響,使結果更準確,仿真時將每種測量矩陣生成方法都重復做了1 000次蒙特卡洛實驗,求3種算法各自性能指標的平均值,結果如表1所示。

表1 M/N=0.5時測量矩陣的重構性能對比

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

為更直觀地比較3種算法對二維圖像的重構效果,只取M/N=0.5時3種測量矩陣構造算法所恢復的圖像對比,如圖1所示。

圖1 各測量矩陣Lena圖像重構效果對比

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

圖2 壓縮比M/N≤0.5情況下的重構結果

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

4 結束語

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

[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].電子學報,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] 瞿廣財,張淑芳,呂 衛(wèi).基于圖像分塊的Toeplitz結構測量矩陣設計[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].計算機工程與應用,2016,52(16):116-120.

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

[11] 李文靜,陳紅衛(wèi).一種基于壓縮感知的ISAR成像方法[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] 傅迎華.可壓縮傳感重構算法與近似QR分解[J].計算機應用,2008,28(9):2300-2302.

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

[18] 李 浩.用于壓縮感知的確定性測量矩陣研究[D].北京:北京交通大學,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] 馬慶濤.壓縮感知中的信號重構算法研究[D].南京:南京郵電大學,2013.