基于混沌序列的壓縮感知測量矩陣構(gòu)造算法

林 斌，彭玉樓

長沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，長沙 410114

基于混沌序列的壓縮感知測量矩陣構(gòu)造算法

林 斌，彭玉樓

長沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，長沙 410114

1 引言

近年來，Donoho和Cande[1-2]等人提出了一種新型采樣理論，基于稀疏表示的壓縮感知（Compressed Sensing，CS），突破了傳統(tǒng)乃奎斯特采樣理論對(duì)采樣頻率的限制，實(shí)現(xiàn)了對(duì)數(shù)據(jù)獲取的同時(shí)進(jìn)行適當(dāng)?shù)貕嚎s，克服了原始采樣數(shù)據(jù)量較大、采樣時(shí)間較長，計(jì)算機(jī)后續(xù)處理以及數(shù)據(jù)存儲(chǔ)空間等物理資源浪費(fèi)嚴(yán)重的問題。

在CS理論中，有三個(gè)核心問題[3]：一是信號(hào)稀疏變換；二是測量矩陣設(shè)計(jì)；三是重構(gòu)算法構(gòu)造。其中測量矩陣設(shè)計(jì)的好壞將直接影響后續(xù)重建信號(hào)的誤差的大小。目前廣泛使用的測量矩陣可以分為確定性和隨機(jī)性測量矩陣。

當(dāng)前國內(nèi)外有學(xué)者提出將混沌序列應(yīng)用到CS的測量矩陣之中，Nguyen Linh-Trung等人在文獻(xiàn)[4]中利用混沌序列構(gòu)造出滿足高斯分布的測量矩陣，實(shí)驗(yàn)結(jié)果表明該測量矩陣具有一般隨機(jī)測量矩陣的性質(zhì)，甚至稍勝于一般隨機(jī)測量矩陣；Lei Yu在文獻(xiàn)[5]中利用混沌序列構(gòu)造一測量矩陣，證明該矩陣滿足RIP性質(zhì)，同時(shí)也驗(yàn)證該矩陣的可行性；顧國生等人在文獻(xiàn)[6]中提出了一種通過基于符號(hào)混沌系統(tǒng)有限型子轉(zhuǎn)移生成的偽隨機(jī)序列構(gòu)造壓縮感知觀測矩陣，同時(shí)驗(yàn)證該測量矩陣的可行性和有效性，但其算法復(fù)雜度較高，計(jì)算時(shí)間較長。

由于Bernoulli測量矩陣是隨機(jī)矩陣，每次實(shí)驗(yàn)產(chǎn)生的矩陣都不相同，所以穩(wěn)定性較差。本文利用混沌序列良好的隨機(jī)性質(zhì)，針對(duì)Bernoulli隨機(jī)序列在穩(wěn)定性方面的不足進(jìn)行研究，提出一種復(fù)雜度較低的測量矩陣構(gòu)造算法。該算法在混沌序列的基礎(chǔ)上通過符號(hào)函數(shù)映射成具有Bernoulli分布的隨機(jī)序列，利用此隨機(jī)序列構(gòu)造測量矩陣。實(shí)驗(yàn)仿真證明，與其他類型的隨機(jī)測量矩陣進(jìn)行比較，基于Logistic混沌—貝努利測量矩陣是可行有效的。

2 壓縮感知理論

設(shè) X∈RN×1為一維信號(hào)，信號(hào) X在一組N×N維正交基Ψ={Ψ1Ψ2…ΨN}上展開為：

其中，θk=＜X，Ψk＞，X和θ均為 N×1維向量。當(dāng)信號(hào) X在某個(gè)正交基Ψ上僅有K＜＜N個(gè)非零系數(shù)θk時(shí)，稱Ψ為信號(hào)X的稀疏基，θ是K-稀疏的。現(xiàn)實(shí)中的信號(hào)往往不是稀疏的，需要經(jīng)過式（1）的轉(zhuǎn)換，故該步驟稱為信號(hào)的稀疏化。常用的稀疏基Ψ有：正余弦基、小波基、Chirplet基及Curvelet基等。

將信號(hào)XN×1投影到一組測量矩陣ΦM×N（其中M＜＜N）上，得到X的M個(gè)采樣數(shù)據(jù)YM×1，即

結(jié)合式（1）和式（2），可以得到采集數(shù)據(jù)Y與變換系數(shù)θ之間的關(guān)系為：

壓縮感知數(shù)據(jù)采集示意圖為如圖1所示。

圖1 壓縮感知數(shù)據(jù)采集示意圖

為了能從式（3）中準(zhǔn)確重構(gòu)出原始信號(hào)，測量矩陣Φ和正交變換基Ψ不相關(guān)[7-8]。文獻(xiàn)[7]指出Φ必須滿足（Restricted Isometry Property，RIP）準(zhǔn)則，即對(duì)任意具有嚴(yán)格K-稀疏的矢量v，Φ滿足：

常用的測量矩陣有，隨機(jī)高斯矩陣、Bernoulli矩陣、傅里葉矩陣等與常用的正交變換基不相關(guān)，很大程度上滿足RIP性質(zhì)[9-10]。

在滿足以上條件下，可以利用l0范數(shù)優(yōu)化方法求解θ的精確解或者是一個(gè)逼近，即通過式（5）求解[1，7]：

由于式（5）的優(yōu)化問題是一個(gè)NP-hard問題，所以可用l1范數(shù)代替l0范數(shù)[11]：

關(guān)于重構(gòu)算法，早期學(xué)者提出了正交匹配追蹤（OMP）[8]、匹配追綜（MP）[12]、梯度投影法（GP）[13]等。近年來也有學(xué)者不斷提出新的重構(gòu)算法，比如修正自適應(yīng)匹配追蹤（MAMP）[14]算法，迭代硬閾值重構(gòu)算法（IIHT）[15]算法等。

3 基于Logistic混沌—貝努利測量矩陣構(gòu)造算法

混沌是非線性系統(tǒng)所獨(dú)有且廣泛存在的一種非周期運(yùn)動(dòng)形式，由于混沌系統(tǒng)產(chǎn)生的序列具有確定性和隨機(jī)性的統(tǒng)一、規(guī)律性以及遍歷性等良好的偽隨機(jī)性質(zhì)，所以在非線性控制、信號(hào)處理、保密通信等領(lǐng)域有著廣泛應(yīng)用。以下是本文利用混沌序列性質(zhì)構(gòu)造測量矩陣的算法。

已知Logistic混沌系統(tǒng)如式（7）所示：

該Logistic系統(tǒng)在參數(shù) μ∈[1.872，2.0]區(qū)間的條件下，當(dāng)初值x0=0.23，0.37，或0.7時(shí)，其Lyapunov指數(shù)均大于0，此時(shí)的Logistic系統(tǒng)是混沌系統(tǒng)[16]。

文獻(xiàn)[17]提出當(dāng)μ=2.0時(shí)，由該Logistic系統(tǒng)產(chǎn)生的序列滿足Bernoulli分布，同時(shí)也滿足RIP性質(zhì)，則由Logistic系統(tǒng)產(chǎn)生的序列可作為CS的測量矩陣。

本文構(gòu)造測量矩陣算法步驟為：

步驟1經(jīng)過反復(fù)的實(shí)驗(yàn)對(duì)比，發(fā)現(xiàn)在 μ=2.0情況下，初值x0=0.23，0.37，或0.7時(shí)，重構(gòu)誤差MSE分別為0.097 95，0.082 61和 0.089 51，取值之間有略微差異。故本文取μ=2.0，x0=0.37，通過該Logistic混沌系統(tǒng)來產(chǎn)生混沌序列，其中序列長度n=M×N-1。

步驟2將步驟1生成的混沌序列通過式子（8）符號(hào)函數(shù)映射成序列。

步驟3將步驟3生成的序列取 N長截?cái)嘈纬蒑×N維測量矩陣Φ。

文獻(xiàn)[5]中的算法復(fù)雜度要比O(N2)大，而本文算法復(fù)雜度為O(M×N)(M＜＜N)。圖2是Bernoulli隨機(jī)序列和Chaos-Bernoulli序列的對(duì)比圖以及它們之間的直方圖對(duì)比圖。

圖2 Bernoulli隨機(jī)序列和Chaos-Bernoulli序列的對(duì)比圖及直方圖對(duì)比圖

由圖2可以看出，與Bernoulli序列相比，Chaos-Bernoulli序列具有更好的平均性及穩(wěn)定性，其隨機(jī)序列中－1，1的個(gè)數(shù)比趨于1∶1。

4 實(shí)驗(yàn)結(jié)果

根據(jù)以上步驟構(gòu)造出基于Logistic的Chaos-Bernoulli的測量矩陣，本文對(duì)一維信號(hào)和二維圖像信號(hào)進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證該測量矩陣的可行性與有效性，并與Gaussian隨機(jī)矩陣和Bernoulli隨機(jī)矩陣進(jìn)行對(duì)比。

4.1 一維信號(hào)仿真實(shí)驗(yàn)

本文選取長度為N=256的一維信號(hào)，測量數(shù)M=0.5×N，壓縮比為：。重構(gòu)算法選取文獻(xiàn)[7]的OMP算法。實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 一維信號(hào)Chaos-Bernoulli測量矩陣重構(gòu)實(shí)驗(yàn)圖

圖3可以看出Chaos-Bernoulli測量矩陣幾乎可以完全重構(gòu)原始信號(hào)。在信號(hào)長度N=256，測量數(shù)M=128的條件下，表1列出了各測量矩陣在峰值信噪比（PSNR）、重構(gòu)誤差（MSE）和匹配度α各個(gè)數(shù)據(jù)方面的對(duì)比。由于隨機(jī)測量矩陣每次實(shí)驗(yàn)產(chǎn)生的矩陣都不相同，所以取20次實(shí)驗(yàn)結(jié)果取平均值作為表1的結(jié)果。其中，當(dāng) X為原始信號(hào)，Xˉ為重建信號(hào)時(shí)，峰值信噪比（PSNR）、重構(gòu)誤差（MSE）和匹配度α的計(jì)算方法為：

表1 信號(hào)長度N=256，測量數(shù)M=128，各矩陣性能比較

從表1可以看出，Chaos-Bernoulli測量矩陣相對(duì)于其他測量矩陣來說，PSNR值有1～3 dB的提高，MSE、α有一定程度的提高。在不同的壓縮比的情況下，圖4給出了重構(gòu)信號(hào)PSNR的對(duì)比圖。

圖4 一維信號(hào)在不同測量矩陣下的峰值信噪比隨壓縮比變化圖

由圖4可以看出，本文算法在不同壓縮比的條件下，Chaos-Bernoulli測量矩陣與其他測量矩陣相比具有較好的穩(wěn)定性，峰值信噪比均優(yōu)于其他測量矩陣。

4.2 二維圖像仿真實(shí)驗(yàn)

本文采用Lena、Cameraman和Barbara256×256圖像在不同壓縮比下進(jìn)行仿真實(shí)驗(yàn)，重構(gòu)算法采用OMP算法。

首先，選取Lena圖像，在壓縮比M/N=0.5情況下討論不同測量矩陣對(duì)重構(gòu)效果的影響，實(shí)驗(yàn)結(jié)果如圖5。

圖5 各測量矩陣Lena圖像重構(gòu)效果對(duì)比（M/N=0.5）

圖5直觀地給出各個(gè)測量矩陣在同一壓縮比的情況下對(duì)二維圖像的重構(gòu)效果。其中Chaos-Bernoulli矩陣的重構(gòu)效果要優(yōu)于其他測量矩陣。為了進(jìn)一步說明圖5的實(shí)驗(yàn)結(jié)果，圖6給出各個(gè)圖像在不同測量矩陣下的峰值信噪比隨壓縮比的變化圖。同理，由于其他用于對(duì)比的測量矩陣是隨機(jī)矩陣，因此取20次實(shí)驗(yàn)選取平均值作為實(shí)驗(yàn)數(shù)據(jù)。其中I是原圖像是重構(gòu)圖像，W和H分別是圖像的寬度和高度，二維圖像的PSNR計(jì)算方法為：

從圖6可以看到，本文提出測量矩陣重構(gòu)算法在重構(gòu)后的圖像PSNR方面均優(yōu)于Gaussian、Bernoulli隨機(jī)測量矩陣，且在壓縮比越大的情況下效果越明顯。

圖6 各個(gè)圖像在不同測量矩陣下的峰值信噪比隨壓縮比變化圖

5 結(jié)束語

本文針對(duì)Bernoulli測量矩陣在穩(wěn)定性方面的不足，利用混沌系統(tǒng)特征提出一種Logistic Chaos-Bernoulli測量矩陣構(gòu)造算法。對(duì)一維二維信號(hào)的重構(gòu)效果進(jìn)行數(shù)值仿真，仿真結(jié)果表明，與Bernoulli測量矩陣相比，本文提出的測量矩陣重構(gòu)效果良好，重構(gòu)信號(hào)PSNR值平均有1～3 dB的提高，并與Gaussian隨機(jī)測量矩陣相比，PSNR在壓縮比越大的情況下效果越明顯，具有一定的實(shí)用價(jià)值，今后將在基于超混沌的測量矩陣構(gòu)造算法作進(jìn)一步的研究。

[1]Donoho D.Compressed sensing[J].IEEE Transactions on Information Theory，2006，52（4）：1289-1306.

[2]Candes E.Compressive sampling[C]//Proceedings of the International Congress of Mathematicians，Madrid，Spain，2006.

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

[4]Linh-Trung N，Van Phong D，Hussain Z M，et al.Compressed sensing using chaos filters[C]//Telecommunication Networks and Applications Conference，2008.

[5]Yu L，Barbot J P，Zheng G，et al.Compressive sensing with chaotic sequence[J].IEEE Signal Processing Letters，2010，17（8）：731-734.

[6]顧國生，戰(zhàn)蔭偉.一種混沌序列在壓縮感知觀測矩陣構(gòu)造中的應(yīng)用[C]//第十五屆全國圖像圖形學(xué)學(xué)術(shù)會(huì)議，2010：111-114.

[7]Candes E，Romberg J，Tao T.Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory，2006，52（4）：489-509.

[8]Tropp J，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory，2007，53（12）：4655-4666.

[9]Donoho D，Tsaig Y.Extensions of compressed sensing signal processing[J].Signal Processing，2006，86（3）：533-548.

[10]Candes E.Compressive sampling[C]//Congress of Mathematic，2006，3：1433-1452.

[11]Baraniuk R.A lecture on compressive sensing[J].IEEE Signal Processing Magazine，2007，24（4）：118-121.

[12]Trop J A.Greed is good：algorithmic results for sparse approximation[J].IEEE Transactions on Information Theory，2004，50（10）：2231-2242.

[13]Figueiredo M A T，Nowak R D，Wright S J.Gradient projection for sparse reconstruction：application to compressed sensing and other inverse problem[J].Journal of Selected Topics in Signal Processing：Special Issue on Convex Optimization Methods for Signal Processing，2007，1（4）：586-598.

[14]甘偉，許錄平.一種自適應(yīng)壓縮感知重構(gòu)算法[J].系統(tǒng)工程與電子技術(shù)，2011，33（9）：1948-1953.

[15]張宗念，李金徽，黃仁泰.迭代硬閾值壓縮感知重構(gòu)算法——IIHT[J].計(jì)算機(jī)應(yīng)用，2011，31（8）：2123-2125.

[16]林衛(wèi)強(qiáng)，黃元石.Logistic混沌序列的隨機(jī)性分析[J].福州大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，32（3）：270-274.

[17]凌聰，孫松庚.Logistic映射擴(kuò)頻序列的相關(guān)分布[J].電子學(xué)報(bào)，1999，27（1）：140-141.

LIN Bin,PENG Yulou

College of Computer&Communication Engineering,Changsha University of Science and Technology,Changsha 410114,China

The measurement matrix construction algorithm is one of important research direction in compressed sensing.A measurement matrix algorithm based on Logistic Chaos-Bernoulli sequence is proposed according to the pseudo-random property of chaos sequence.It uses the one-dimensional Logistic chaotic system to generate the chaotic sequence,the pseudo-random sequence with Bernoulli distribution is generated by the symbol function and the sequence is used to construct the measurement matrix. Simulation results show that,the proposed algorithm performs better than the Bernoulli random measurement matrix and the PSNR of construct signal is improved about 1～3 dB,and it is feasible and effective by numerical analysis after comparing with other types of measure matrix.

compressed sensing;measurement matrix;chaotic system;Bernoulli distribution

測量矩陣的構(gòu)造算法是壓縮感知中重要的研究方向之一。提出一種基于Logistic混沌—貝努利序列（Chaos-Bernoulli）測量矩陣構(gòu)造算法，該算法利用了混沌序列良好的偽隨機(jī)性質(zhì)，通過一維Logistic混沌系統(tǒng)產(chǎn)生混沌序列，再通過符號(hào)函數(shù)生成具有貝努利分布的偽隨機(jī)序列從而構(gòu)造出壓縮感知測量矩陣。實(shí)驗(yàn)仿真結(jié)果表明，該算法優(yōu)于貝努利隨機(jī)測量矩陣，信號(hào)重構(gòu)的峰值信噪比PSNR有1～3 dB的提高，并與其他類型的測量矩陣進(jìn)行比較，數(shù)值分析結(jié)果證明該算法是可行有效的。

壓縮感知；測量矩陣；混沌系統(tǒng)；貝努利分布

A

TN911.7

10.3778/j.issn.1002-8331.1202-0344

LIN Bin,PENG Yulou.Measurement matrix construction algorithm for compressed sensing based on chaos sequence. Computer Engineering and Applications,2013,49（23）：199-202.

林斌（1987—），男，碩士研究生，主要研究方向：壓縮感知、圖像處理；彭玉樓（1968—），男，博士，副教授，主要研究方向：小波理論、圖像處理、壓縮感知。E-mail：linbin1987@163.com

2012-02-20

2012-04-18

1002-8331（2013）23-0199-04

CNKI出版日期：2012-06-15 http://www.cnki.net/kcms/detail/11.2127.TP.20120615.1726.021.html