楊愛萍，張金霞，鐘騰飛，卜令勇(天津大學(xué)電子信息工程學(xué)院，天津 300072)

分塊OSTM測(cè)量矩陣構(gòu)造及自適應(yīng)壓縮感知算法

楊愛萍，張金霞，鐘騰飛，卜令勇
(天津大學(xué)電子信息工程學(xué)院，天津 300072)

針對(duì)目前隨機(jī)測(cè)量矩陣物理實(shí)現(xiàn)困難、成本較高等不足，在研究確定性測(cè)量矩陣構(gòu)造的基礎(chǔ)上，基于分塊循環(huán)結(jié)構(gòu)，提出了分塊正交對(duì)稱Toeplitz矩陣(OSTM)的構(gòu)造方法．分塊OSTM具有偽隨機(jī)循環(huán)結(jié)構(gòu)，易于硬件實(shí)現(xiàn)，其獨(dú)立變?cè)獋€(gè)數(shù)大大減少，可降低存儲(chǔ)和運(yùn)算時(shí)間．針對(duì)目前圖像分塊壓縮感知中單一采樣的缺陷，將圖像塊進(jìn)行分類，根據(jù)圖像局部結(jié)構(gòu)自適應(yīng)分配采樣率，結(jié)合分塊OSTM設(shè)計(jì)，提出了基于分塊OSTM的自適應(yīng)壓縮采樣算法．仿真實(shí)驗(yàn)結(jié)果表明，基于分塊OSTM的壓縮測(cè)量獲得的重構(gòu)圖像PSNR顯著提高，圖像主觀質(zhì)量得到了有效改善．

分塊壓縮感知；分塊正交對(duì)稱Toeplitz矩陣；圖像塊分類；自適應(yīng)采樣率

在壓縮感知過程中，測(cè)量矩陣在信號(hào)獲取和重構(gòu)環(huán)節(jié)發(fā)揮著至關(guān)重要的作用．它能使任意稀疏信號(hào)從高維空間投影到低維空間的過程中保持主要信息不丟失，保證精確重構(gòu)原始信號(hào)．已有文獻(xiàn)指出，好的測(cè)量矩陣應(yīng)該在相同稀疏度時(shí)需要更少的測(cè)量樣本，便于硬件實(shí)現(xiàn)和算法優(yōu)化，且具有普適性．目前已經(jīng)證明，隨機(jī)測(cè)量矩陣(包括高斯隨機(jī)矩陣、伯努利隨機(jī)矩陣等)滿足RIP特性，可以用來作為普適的測(cè)量矩陣[1-3]．但由于隨機(jī)性太強(qiáng)，無論在硬件實(shí)現(xiàn)還是算法重建上，這類測(cè)量矩陣并不實(shí)用．

為了克服上述矩陣存在的缺陷，相繼提出了結(jié)構(gòu)隨機(jī)測(cè)量矩陣[4]、托普利茲(Toeplitz)和循環(huán)(circulant)矩陣[5]、二進(jìn)稀疏(binary sparse)矩陣[6]等確定性測(cè)量矩陣，這類矩陣和相同尺寸的高斯隨機(jī)矩陣相比，存儲(chǔ)量和重構(gòu)復(fù)雜度大大降低，能以較少的采樣值高概率精確重構(gòu)原始信號(hào)．然而隨著處理數(shù)據(jù)量的進(jìn)一步增大，以上幾種測(cè)量矩陣的存儲(chǔ)量將會(huì)大大增加，均無法適應(yīng)實(shí)際需要．

本文基于分塊循環(huán)矩陣結(jié)構(gòu)[7]，結(jié)合正交對(duì)稱托普利茲矩陣(orthogonal symmetric Toeplitz matrices，OSTM)的設(shè)計(jì)，構(gòu)造了一種新的測(cè)量矩陣——分塊OSTM，構(gòu)造的矩陣獨(dú)立變?cè)獋€(gè)數(shù)大大減少，降低了存儲(chǔ)量；構(gòu)造過程中利用了偽循環(huán)特性，易于硬件實(shí)現(xiàn)．另外，由于壓縮感知技術(shù)應(yīng)用到二維圖像時(shí)計(jì)算非常復(fù)雜，本文研究了分塊壓縮感知理論，針對(duì)各圖像塊采用單一采樣率產(chǎn)生的不足，結(jié)合提出的分塊OSTM矩陣設(shè)計(jì)，提出了一種自適應(yīng)采樣分塊壓縮感知算法．

1 壓縮感知理論

設(shè)x是長(zhǎng)度為N的一維信號(hào)，存在一組正交基矢量Ψ使得x=Ψθ，其中ΨN×N為稀疏基矩陣，θ是x在Ψ下的稀疏表示．θ中只有K(K?N)個(gè)大系數(shù)或者K個(gè)非零系數(shù)，則稱x是可壓縮的或K稀疏的．壓縮感知理論指出，可以用一個(gè)與Ψ不相關(guān)的矩陣ΦM×N(M?N)對(duì)信號(hào)進(jìn)行壓縮測(cè)量，即

式中y為測(cè)量值．由RIP理論[8]可知，只要ΦΨ滿足RIP特性，則由Klg(N/K)個(gè)測(cè)量值可將N維信號(hào)的K個(gè)最大值穩(wěn)定地重建出來，即通過求解L1范數(shù)約束最優(yōu)化問題

精確重構(gòu)原始信號(hào)．

確定性測(cè)量矩陣是壓縮感知推向?qū)嵱没囊活愔匾仃嚕壳皩?duì)該類矩陣RIP性質(zhì)的證明仍是一個(gè)挑戰(zhàn)性的問題．針對(duì)確定性測(cè)量矩陣的性質(zhì)分析，文獻(xiàn)[9-10]提出了RIP性質(zhì)的統(tǒng)計(jì)學(xué)定義SRIP，指出矩陣在滿足SRIP的條件下，也可以作為壓縮感知的測(cè)量矩陣，取得很好的重建效果．

2 基于分塊OSTM的測(cè)量矩陣設(shè)計(jì)

2.1 正交對(duì)稱托普利茲矩陣(OSTM)

OSTM是Bottcher[11]提出的一類新的確定性測(cè)量矩陣，其結(jié)構(gòu)如式(4)所示，矩陣的構(gòu)造方法如下所述．

首先定義符號(hào)序列σ?(σ1,σ2,…,σN)，其中(σ1,σ2,…,σN)=(γ,ε1,…,εN/2-1,β,εN/2-1,…,ε1)，參數(shù)(γ,ε1,…,εN/2-1,β)∈{-1,1}N/2+1．OSTM矩陣的第1行元素是由符號(hào)序列經(jīng)IFFT變換得到，然后通過循環(huán)移位產(chǎn)生矩陣的剩余行．令對(duì)角陣Σ=diag(σ)，得到矩陣ΦN=FN*ΣFN．這時(shí)得到的矩陣ΦN是Toeplitz結(jié)構(gòu)的正交對(duì)稱矩陣．最后隨機(jī)選取矩陣ΦN的M行，乘以系數(shù)N/M進(jìn)行規(guī)范化，獲得最終的測(cè)量矩陣Φ=N/MΦN．

在該類矩陣的構(gòu)造過程中，符號(hào)序列的選取有2N/2+1種取值，從而可以構(gòu)造出2N/2+1個(gè)相應(yīng)的矩陣，但是這些矩陣的壓縮感知性能不同，詳細(xì)證明過程和結(jié)果可參見文獻(xiàn)[12]．

2.2 分塊循環(huán)托普利茲(Toeplitz)矩陣

為了易于硬件實(shí)現(xiàn)，杜克大學(xué)的Marcia等在循環(huán)矩陣的基礎(chǔ)上引入偽隨機(jī)循環(huán)的構(gòu)造方法[13]，提出了分塊循環(huán)測(cè)量矩陣，即

則隨機(jī)抽取矩陣Φ的M個(gè)行向量構(gòu)成的分塊循環(huán)Toeplitz矩陣，能以很大的概率滿足RIP[7]．

2.3 分塊OSTM設(shè)計(jì)

對(duì)于絕大部分給定稀疏度的信號(hào)，可以構(gòu)造滿足SRIP的OSTM矩陣，這類矩陣是確定性的，并且在壓縮性能方面與隨機(jī)矩陣相當(dāng)．但是，當(dāng)矩陣尺寸變得很大時(shí)，仍然需要很大的數(shù)據(jù)存儲(chǔ)量．

為了進(jìn)一步提高壓縮效率，降低存儲(chǔ)量，本文基于OSTM的設(shè)計(jì)和分塊循環(huán)矩陣結(jié)構(gòu)，構(gòu)造了一種新的測(cè)量矩陣——分塊OSTM．構(gòu)造方法的具體步驟如下所述．

步驟1 按照OSTM矩陣的構(gòu)造方法，產(chǎn)生N個(gè)n×n的方陣(1≤j≤N)，每個(gè)均具有式(4)所示的結(jié)構(gòu)．為了便于硬件實(shí)現(xiàn)和優(yōu)化算法，本文構(gòu)造OSTM的第1行時(shí)選用經(jīng)過修正的伯努利序列作為符號(hào)序列．

步驟2 將每個(gè)Φj(1≤j≤N)看作一個(gè)元素，N個(gè)順序排列構(gòu)成一個(gè)分塊行向量(,…,)．

由矩陣的構(gòu)造結(jié)構(gòu)分析可知，分塊循環(huán)托普利茲矩陣中獨(dú)立變?cè)膫€(gè)數(shù)為(2n-1)N個(gè)，由于OSTM矩陣具有對(duì)稱特性，本文構(gòu)造的測(cè)量矩陣中獨(dú)立變?cè)膫€(gè)數(shù)為nN/2個(gè)，約為前者的1/4．因此，當(dāng)所需測(cè)量矩陣尺寸較大時(shí)，本文構(gòu)造的矩陣獨(dú)立元素個(gè)數(shù)大大減少，從而降低了存儲(chǔ)量，提高了運(yùn)算速率．另外，本文按照分塊循環(huán)結(jié)構(gòu)來構(gòu)造測(cè)量矩陣，利用了偽循環(huán)特性，與單純利用元素循環(huán)構(gòu)造的測(cè)量矩陣相比，更易于硬件實(shí)現(xiàn)．

3 基于分塊OSTM的自適應(yīng)分塊壓縮感知算法

3.1 分塊壓縮采樣

壓縮感知(compressed sensing，CS)技術(shù)可以由極少量的觀測(cè)數(shù)據(jù)來重建原始信號(hào)，極大地降低了信號(hào)采樣率．但是采樣過程需要瞬間完成且重建算法異常復(fù)雜，不易于實(shí)時(shí)實(shí)現(xiàn)．尤其是應(yīng)用到二維圖像時(shí)，CS重構(gòu)過程計(jì)算非常復(fù)雜．因此，出現(xiàn)了一些快速CS重構(gòu)算法[14-16]，文獻(xiàn)[16]提出了一種用于自然圖像的塊壓縮感知框架，大大減少了運(yùn)算復(fù)雜度．

一幅圖像被分成BB×塊，并用一個(gè)適當(dāng)大小的測(cè)量矩陣采樣．假設(shè)jx是輸入圖像x的塊j以光柵掃描方式排列的向量．對(duì)塊j進(jìn)行壓縮采樣可表示為yj=ΦBxj，其中ΦB是nB×B2的測(cè)量矩陣，nB=βB2，β為采樣率．對(duì)于整幅圖像，采樣算子Φ為塊對(duì)角矩陣，即

對(duì)圖像直接進(jìn)行壓縮采樣所需測(cè)量矩陣的維數(shù)為n′×N2，n′=βN2，因此，分塊壓縮采樣極大地降低了測(cè)量矩陣的維數(shù)．

3.2 圖像塊分類

目前在圖像分塊壓縮感知方面，大多利用隨機(jī)測(cè)量矩陣對(duì)所有圖像塊進(jìn)行單一采樣率壓縮采樣，由于不同類別的圖像塊局部特征不同，低采樣率難以保證各塊都具有較高的重構(gòu)質(zhì)量，而高采樣率會(huì)造成資源浪費(fèi)．針對(duì)這一缺點(diǎn)，本文將圖像塊進(jìn)行分類，根據(jù)圖像局部結(jié)構(gòu)信息自適應(yīng)分配采樣率．

圖像塊可分為平滑塊和細(xì)節(jié)塊．平滑塊的判別可利用圖像塊的熵[17]、局部能量或圖像的局部方差．為計(jì)算簡(jiǎn)便，本文利用局部方差區(qū)分平滑塊與細(xì)節(jié)塊．設(shè)第i個(gè)圖像塊的向量形式為xi={xij}，j=1,…,NB，則該塊的方差為

針對(duì)不同的圖像，設(shè)定Ti(i=1,2,3)作為圖像塊方差的判定閾值，T1＞T2＞T3(如對(duì)256×256的Lenna圖像實(shí)驗(yàn)中，選取了T1=1,750，T2=1,250，T3= 750)，用β1、β2、β3、β4分別表示4個(gè)不同的采樣率(本文實(shí)驗(yàn)中選取β1、β2、β3、β4分別等于0.2、0.4、0.6和0.8)，則每塊分配的采樣率β為

本文針對(duì)塊的不同特點(diǎn)采用不同數(shù)量觀測(cè)值，可以使總觀測(cè)值數(shù)目減少，達(dá)到低采樣率下獲得高質(zhì)量重構(gòu)圖像的目的．

可見，分塊OSTM能快速有效地獲得測(cè)量值，減少測(cè)量系統(tǒng)的存儲(chǔ)空間，降低硬件實(shí)現(xiàn)難度．因此本文提出基于分塊OSTM的圖像自適應(yīng)分塊壓縮感知(block compressed sensing，BCS)算法．首先將一幅圖像分割成T個(gè)N×N的塊，按照式(6)計(jì)算塊i的方差(1≤i≤T)；通過閾值判斷，根據(jù)式(7)給塊i分配相應(yīng)的采樣率；用生成的分塊OSTM矩陣對(duì)向量化的塊i進(jìn)行壓縮采樣yi=Φxi，最后根據(jù)測(cè)量值進(jìn)行分塊重構(gòu)，將各塊進(jìn)行拼接得到整幅重構(gòu)圖像．具體算法流程如圖1所示．

圖1 基于分塊OSTM的自適應(yīng)分塊壓縮感知算法Fig.1 Adaptive BCS algorithm based on the block OSTM

4 仿真實(shí)驗(yàn)及結(jié)果分析

4.1 單一采樣率實(shí)驗(yàn)

為了驗(yàn)證本文設(shè)計(jì)的分塊OSTM及提出的自適應(yīng)采樣壓縮感知算法的性能，在MATLAB平臺(tái)下對(duì)圖像分塊壓縮感知進(jìn)行了仿真實(shí)驗(yàn)．圖像分塊尺寸選為3232×，重構(gòu)算法采用TV算法[18]．

為了驗(yàn)證本文提出的分塊OSTM的壓縮測(cè)量性能，首先進(jìn)行單一采樣率實(shí)驗(yàn)，并和常用高斯隨機(jī)矩陣及綜合性能較好的確定性測(cè)量矩陣——分塊循環(huán)Toeplitz矩陣進(jìn)行比較．分別對(duì)256256×的Lenna、Peppers、Boat和Cameraman圖像進(jìn)行分塊壓縮測(cè)量并重構(gòu)的實(shí)驗(yàn)．表1給出了各種測(cè)量矩陣的構(gòu)造時(shí)間．表2所示為各種測(cè)量矩陣重構(gòu)圖像的PSNR值．圖2給出了采樣率為0.50時(shí)不同測(cè)量矩陣對(duì)應(yīng)的重構(gòu)效果，測(cè)量圖像為L(zhǎng)enna圖像．圖3給出了不同矩陣的PSNR值隨采樣率的變化曲線．

表1 不同測(cè)量矩陣的構(gòu)造時(shí)間Tab.1 Construction time of different measurement matrices s

表2 不同測(cè)量矩陣下重建圖像的PSNR值Tab.2 PSNR of reconstructed images based on different measurement matrices dB

圖2 采樣率為0.50時(shí)不同測(cè)量矩陣對(duì)應(yīng)的圖像重建效果Fig.2 Reconstructed images with different measurement matrices at 0.50 subrate

圖3 不同測(cè)量矩陣重構(gòu)圖像的PSNR隨采樣率的變化曲線Fig.3 PSNR curves of different measurement matrices at different subrates

由表1、表2及圖2、圖3可見，單一采樣率下，高斯隨機(jī)矩陣與分塊循環(huán)Toeplitz矩陣測(cè)量下的重構(gòu)圖像PSNR及主觀效果相當(dāng)，而基于本文分塊OSTM測(cè)量后的重構(gòu)圖像PSNR顯著提高，主觀質(zhì)量更好且構(gòu)造時(shí)間減少．

4.2 自適應(yīng)采樣率實(shí)驗(yàn)

為了進(jìn)一步改善圖像重構(gòu)質(zhì)量，對(duì)提出的自適應(yīng)分塊壓縮感知算法進(jìn)行仿真實(shí)驗(yàn)．分別基于高斯隨機(jī)矩陣、分塊循環(huán)Toeplitz矩陣以及本文分塊OSTM對(duì)Peppers圖像進(jìn)行自適應(yīng)分塊壓縮測(cè)量并重構(gòu)．圖4給出了采樣率為0.50時(shí)的重構(gòu)效果．作為對(duì)比，圖5給出了自適應(yīng)采樣率下各種測(cè)量矩陣的重構(gòu)效果．

可見，對(duì)3種測(cè)量方法來說，采用自適應(yīng)分塊壓縮感知比采用單一采樣率壓縮采樣，圖像重構(gòu)質(zhì)量均有不同程度的提高．通過實(shí)驗(yàn)發(fā)現(xiàn)本文構(gòu)造的分塊OSTM矩陣對(duì)圖像具有很好的壓縮采樣性能，結(jié)合自適應(yīng)采樣方案用于分塊壓縮感知，重構(gòu)圖像無論是客觀PSNR指標(biāo)還是圖像主觀質(zhì)量，都達(dá)到了非常理想的效果．

圖4 采樣率為0.50時(shí)圖像重構(gòu)效果Fig.4 Reconstructed images at 0.50 subrate

圖5 自適應(yīng)分塊壓縮感知的圖像重構(gòu)效果Fig.5 Reconstructed images based on the adaptive BCS algorithm

5 結(jié) 語

作為壓縮感知的核心，測(cè)量矩陣的性能好壞直接影響到重建算法的復(fù)雜度以及硬件實(shí)現(xiàn)的難易程度．本文提出的分塊OSTM，采用偽循環(huán)的構(gòu)造方式，易于硬件實(shí)現(xiàn)，減少了獨(dú)立變?cè)?，降低了存?chǔ)和運(yùn)算量．針對(duì)圖像壓縮感知計(jì)算復(fù)雜的特點(diǎn)，研究了分塊壓縮感知理論，將圖像塊進(jìn)行分類并結(jié)合分塊OSTM測(cè)量，提出了基于分塊OSTM的自適應(yīng)壓縮感知算法．仿真實(shí)驗(yàn)表明，本文算法實(shí)現(xiàn)復(fù)雜度低，圖像重構(gòu)質(zhì)量較好．

［1］ Candès E. Compressive sampling[C]//Int Congress of Mathematic. Madrid，Spain，2006：1433-1452.

［2］ Donoho D，Tsaig Yaakov. Extensions of compressed sensing[J]. Signal Processing，2006，86(3)：533-548.

［3］ Candès E，Justin R. Practical signal recovery from random projections[C]//IS&T/SPIE’s，17th Annual Symposium on Electronic Imaging. San Jose，CA，2005，54(19)：76-86.

［4］ Do T，Gan L，Nguyen N，et al. Fast and efficient compressive sensing using structurally random matrices[J]. IEEE Trans Signal Process，2012，60(1)：139-154.

［5］ Yin Wotao，Morgan S，Yang Junfeng，et al. Practical compressive sensing with Toeplitz and circulant matrices[C]// Proceedings of SPIE，Visual Communications and Image Processing 2010. Huangshan，China，2010，7744：77440K.

［6］ Berinde R，Indyk P. Sparse Recovery Using Sparse Random Matrices[EB/OL]. http：//people. csail. mit. edu/ indyk/repo-rt. pdf，2008-04-26.

［7］ Sebert F，Zou Y M，Ying L. Toeplitz block matrices in compressed sensing and their applications in imaging process[C]// Proceedings of International Conference on Technology and Applications in Biomedicine. Washington，USA：IEEE，2008：47-50.

［8］ Candes E，Tao T. Decoding by linear programming[J]. IEEE Transactions on Information Theory，2005，51 (12)：4203-4215.

［9］ Gurevich S，Hadani R. The Statistical Restricted Isometry Property and the Wigner Semicircle Distribution of Incoherent Dictionaries[EB/OL]. http：//arxiv.org/abs/ 0812.2602，2008-12-14.

［10］ Calder B R，Howard S，Jafarpour S. Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property[J]. IEEE J Selected Topics in Signal Processing，2010，4(2)：358-374.

［11］ Bottcher A. Orthogonal symmetric Toeplitz matrices[J]. Complex Analysis and Operator Theory，2008，2(2)：285-298.

［12］ Li Kezhi，Gan Lu，Ling Cong. Orthogonal Symmetric Toeplitz Matrices for Compressed Sensing：Statistical Isometry Property [EB/OL]. http：//arxiv. org/abs/1012. 5947，2010-12-29.

［13］ Bajwa W U，Haupt J D，Raz G M，et al. Toeplitzstructured compressed sensing matrices[C]// IEEE/SP 14th Workshop on Statistical Signal Processing，2007. Madison，WI，USA，2007：294-298.

［14］ Figueiredo M T，Nowak R D，Wright S J. Gradient projection for sparse reconstruction：Application to compressed sensing and other inverse problems[J]. IEEE Journal on Selected Areas in Communications，2007，1(4)：586-597.

［15］ Do T T，Gan L，Nguyen N. Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]// Proceedings of the 42th Asilomar Conference on Signals，Systems，and Computers. Pacific Grove，California，2008：581-587.

［16］ Gan L. Block compressed sensing of natural images[C]// Proceedings of the International Conference on Digital Signal Processing. Cardiff，UK，2007：403-406.

［17］ Pun T. Entropic thresholding，a new approach[J]. Computer Graphics and Image Processing，1981，16(3)：210-239.

［18］ Li C. An Efficient Algorithm for Total Variation Regularization with Applications to the Single Pixel Camera and Compressive Sensing[D]. Rice，USA：Rice University，2009.

（責(zé)任編輯：金順愛）

Construction of Block OSTM and the Adaptive Compressed Sensing Algorithm

Yang Aiping，Zhang Jinxia，Zhong Tengfei，Bu Lingyong
(School of Electronic Information Engineering，Tianjin University，Tianjin 300072，China)

In order to resolve the problems of physical implementation difficulties and high cost of the existing random measurement matrices, the construction method of block orthogonal symmetric Toeplitz matrices(OSTM) was put forward in this paper based on the research of the deterministic measurement matrices. The block OSTM could more easily achieve physical implementation due toits pseudo random cyclic structure. The storage and computing time could be shortened as the matrix’s independent variable number was greatly reduced. To overcome the shortcoming of single sampling in image block compressed sensing (BCS), the image blocks were firstly classified according to the local structure of image, and then allocated to different sampling ratesadaptively. Finally, this paper proposed an adaptive BCS algorithm based on the block OSTM. Simulation results show that the proposed method can acquire higher PSNR and eliminate the block effect significantly.

block compressed sensing；block orthogonal symmetric Toeplitz matrices；image block classification；adaptive sampling rate

TN911.7

A

0493-2137(2014)06-0535-06

10.11784/tdxbz201211006

2012-11-02；

2013-02-06.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61002027，61372145).

楊愛萍（1977— ），女，博士，副教授.

楊愛萍，yangaiping@tju.edu.cn.

時(shí)間：2014-01-07.

http：//www.cnki.net/kcms/doi/10.11784/tdxbz201211006.html.