分块OSTM测量矩阵构造及自适应压缩感知算法

杨爱萍，张金霞，钟腾飞，卜令勇(天津大学电子信息工程学院，天津 300072)

分块OSTM测量矩阵构造及自适应压缩感知算法

杨爱萍，张金霞，钟腾飞，卜令勇
(天津大学电子信息工程学院，天津 300072)

针对目前随机测量矩阵物理实现困难、成本较高等不足，在研究确定性测量矩阵构造的基础上，基于分块循环结构，提出了分块正交对称Toeplitz矩阵(OSTM)的构造方法．分块OSTM具有伪随机循环结构，易于硬件实现，其独立变元个数大大减少，可降低存储和运算时间．针对目前图像分块压缩感知中单一采样的缺陷，将图像块进行分类，根据图像局部结构自适应分配采样率，结合分块OSTM设计，提出了基于分块OSTM的自适应压缩采样算法．仿真实验结果表明，基于分块OSTM的压缩测量获得的重构图像PSNR显著提高，图像主观质量得到了有效改善．

分块压缩感知；分块正交对称Toeplitz矩阵；图像块分类；自适应采样率

在压缩感知过程中，测量矩阵在信号获取和重构环节发挥着至关重要的作用．它能使任意稀疏信号从高维空间投影到低维空间的过程中保持主要信息不丢失，保证精确重构原始信号．已有文献指出，好的测量矩阵应该在相同稀疏度时需要更少的测量样本，便于硬件实现和算法优化，且具有普适性．目前已经证明，随机测量矩阵(包括高斯随机矩阵、伯努利随机矩阵等)满足RIP特性，可以用来作为普适的测量矩阵[1-3]．但由于随机性太强，无论在硬件实现还是算法重建上，这类测量矩阵并不实用．

为了克服上述矩阵存在的缺陷，相继提出了结构随机测量矩阵[4]、托普利兹(Toeplitz)和循环(circulant)矩阵[5]、二进稀疏(binary sparse)矩阵[6]等确定性测量矩阵，这类矩阵和相同尺寸的高斯随机矩阵相比，存储量和重构复杂度大大降低，能以较少的采样值高概率精确重构原始信号．然而随着处理数据量的进一步增大，以上几种测量矩阵的存储量将会大大增加，均无法适应实际需要．

本文基于分块循环矩阵结构[7]，结合正交对称托普利兹矩阵(orthogonal symmetric Toeplitz matrices，OSTM)的设计，构造了一种新的测量矩阵——分块OSTM，构造的矩阵独立变元个数大大减少，降低了存储量；构造过程中利用了伪循环特性，易于硬件实现．另外，由于压缩感知技术应用到二维图像时计算非常复杂，本文研究了分块压缩感知理论，针对各图像块采用单一采样率产生的不足，结合提出的分块OSTM矩阵设计，提出了一种自适应采样分块压缩感知算法．

1 压缩感知理论

设x是长度为N的一维信号，存在一组正交基矢量Ψ使得x=Ψθ，其中ΨN×N为稀疏基矩阵，θ是x在Ψ下的稀疏表示．θ中只有K(K≪N)个大系数或者K个非零系数，则称x是可压缩的或K稀疏的．压缩感知理论指出，可以用一个与Ψ不相关的矩阵ΦM×N(M≪N)对信号进行压缩测量，即

式中y为测量值．由RIP理论[8]可知，只要ΦΨ满足RIP特性，则由Klg(N/K)个测量值可将N维信号的K个最大值稳定地重建出来，即通过求解L1范数约束最优化问题

精确重构原始信号．

确定性测量矩阵是压缩感知推向实用化的一类重要矩阵，目前对该类矩阵RIP性质的证明仍是一个挑战性的问题．针对确定性测量矩阵的性质分析，文献[9-10]提出了RIP性质的统计学定义SRIP，指出矩阵在满足SRIP的条件下，也可以作为压缩感知的测量矩阵，取得很好的重建效果．

2 基于分块OSTM的测量矩阵设计

2.1 正交对称托普利兹矩阵(OSTM)

OSTM是Bottcher[11]提出的一类新的确定性测量矩阵，其结构如式(4)所示，矩阵的构造方法如下所述．

首先定义符号序列σ≜(σ1,σ2,…,σN)，其中(σ1,σ2,…,σN)=(γ,ε1,…,εN/2-1,β,εN/2-1,…,ε1)，参数(γ,ε1,…,εN/2-1,β)∈{-1,1}N/2+1．OSTM矩阵的第1行元素是由符号序列经IFFT变换得到，然后通过循环移位产生矩阵的剩余行．令对角阵Σ=diag(σ)，得到矩阵ΦN=FN*ΣFN．这时得到的矩阵ΦN是Toeplitz结构的正交对称矩阵．最后随机选取矩阵ΦN的M行，乘以系数N/M进行规范化，获得最终的测量矩阵Φ=N/MΦN．

在该类矩阵的构造过程中，符号序列的选取有2N/2+1种取值，从而可以构造出2N/2+1个相应的矩阵，但是这些矩阵的压缩感知性能不同，详细证明过程和结果可参见文献[12]．

2.2 分块循环托普利兹(Toeplitz)矩阵

为了易于硬件实现，杜克大学的Marcia等在循环矩阵的基础上引入伪随机循环的构造方法[13]，提出了分块循环测量矩阵，即

则随机抽取矩阵Φ的M个行向量构成的分块循环Toeplitz矩阵，能以很大的概率满足RIP[7]．

2.3 分块OSTM设计

对于绝大部分给定稀疏度的信号，可以构造满足SRIP的OSTM矩阵，这类矩阵是确定性的，并且在压缩性能方面与随机矩阵相当．但是，当矩阵尺寸变得很大时，仍然需要很大的数据存储量．

为了进一步提高压缩效率，降低存储量，本文基于OSTM的设计和分块循环矩阵结构，构造了一种新的测量矩阵——分块OSTM．构造方法的具体步骤如下所述．

步骤1 按照OSTM矩阵的构造方法，产生N个n×n的方阵(1≤j≤N)，每个均具有式(4)所示的结构．为了便于硬件实现和优化算法，本文构造OSTM的第1行时选用经过修正的伯努利序列作为符号序列．

步骤2 将每个Φj(1≤j≤N)看作一个元素，N个顺序排列构成一个分块行向量(,…,)．

由矩阵的构造结构分析可知，分块循环托普利兹矩阵中独立变元的个数为(2n-1)N个，由于OSTM矩阵具有对称特性，本文构造的测量矩阵中独立变元的个数为nN/2个，约为前者的1/4．因此，当所需测量矩阵尺寸较大时，本文构造的矩阵独立元素个数大大减少，从而降低了存储量，提高了运算速率．另外，本文按照分块循环结构来构造测量矩阵，利用了伪循环特性，与单纯利用元素循环构造的测量矩阵相比，更易于硬件实现．

3 基于分块OSTM的自适应分块压缩感知算法

3.1 分块压缩采样

压缩感知(compressed sensing，CS)技术可以由极少量的观测数据来重建原始信号，极大地降低了信号采样率．但是采样过程需要瞬间完成且重建算法异常复杂，不易于实时实现．尤其是应用到二维图像时，CS重构过程计算非常复杂．因此，出现了一些快速CS重构算法[14-16]，文献[16]提出了一种用于自然图像的块压缩感知框架，大大减少了运算复杂度．

一幅图像被分成BB×块，并用一个适当大小的测量矩阵采样．假设jx是输入图像x的块j以光栅扫描方式排列的向量．对块j进行压缩采样可表示为yj=ΦBxj，其中ΦB是nB×B2的测量矩阵，nB=βB2，β为采样率．对于整幅图像，采样算子Φ为块对角矩阵，即

对图像直接进行压缩采样所需测量矩阵的维数为n′×N2，n′=βN2，因此，分块压缩采样极大地降低了测量矩阵的维数．

3.2 图像块分类

目前在图像分块压缩感知方面，大多利用随机测量矩阵对所有图像块进行单一采样率压缩采样，由于不同类别的图像块局部特征不同，低采样率难以保证各块都具有较高的重构质量，而高采样率会造成资源浪费．针对这一缺点，本文将图像块进行分类，根据图像局部结构信息自适应分配采样率．

图像块可分为平滑块和细节块．平滑块的判别可利用图像块的熵[17]、局部能量或图像的局部方差．为计算简便，本文利用局部方差区分平滑块与细节块．设第i个图像块的向量形式为xi={xij}，j=1,…,NB，则该块的方差为

针对不同的图像，设定Ti(i=1,2,3)作为图像块方差的判定阈值，T1＞T2＞T3(如对256×256的Lenna图像实验中，选取了T1=1,750，T2=1,250，T3= 750)，用β1、β2、β3、β4分别表示4个不同的采样率(本文实验中选取β1、β2、β3、β4分别等于0.2、0.4、0.6和0.8)，则每块分配的采样率β为

本文针对块的不同特点采用不同数量观测值，可以使总观测值数目减少，达到低采样率下获得高质量重构图像的目的．

可见，分块OSTM能快速有效地获得测量值，减少测量系统的存储空间，降低硬件实现难度．因此本文提出基于分块OSTM的图像自适应分块压缩感知(block compressed sensing，BCS)算法．首先将一幅图像分割成T个N×N的块，按照式(6)计算块i的方差(1≤i≤T)；通过阈值判断，根据式(7)给块i分配相应的采样率；用生成的分块OSTM矩阵对向量化的块i进行压缩采样yi=Φxi，最后根据测量值进行分块重构，将各块进行拼接得到整幅重构图像．具体算法流程如图1所示．

图1 基于分块OSTM的自适应分块压缩感知算法Fig.1 Adaptive BCS algorithm based on the block OSTM

4 仿真实验及结果分析

4.1 单一采样率实验

为了验证本文设计的分块OSTM及提出的自适应采样压缩感知算法的性能，在MATLAB平台下对图像分块压缩感知进行了仿真实验．图像分块尺寸选为3232×，重构算法采用TV算法[18]．

为了验证本文提出的分块OSTM的压缩测量性能，首先进行单一采样率实验，并和常用高斯随机矩阵及综合性能较好的确定性测量矩阵——分块循环Toeplitz矩阵进行比较．分别对256256×的Lenna、Peppers、Boat和Cameraman图像进行分块压缩测量并重构的实验．表1给出了各种测量矩阵的构造时间．表2所示为各种测量矩阵重构图像的PSNR值．图2给出了采样率为0.50时不同测量矩阵对应的重构效果，测量图像为Lenna图像．图3给出了不同矩阵的PSNR值随采样率的变化曲线．

表1 不同测量矩阵的构造时间Tab.1 Construction time of different measurement matrices s

表2 不同测量矩阵下重建图像的PSNR值Tab.2 PSNR of reconstructed images based on different measurement matrices dB

图2 采样率为0.50时不同测量矩阵对应的图像重建效果Fig.2 Reconstructed images with different measurement matrices at 0.50 subrate

图3 不同测量矩阵重构图像的PSNR随采样率的变化曲线Fig.3 PSNR curves of different measurement matrices at different subrates

由表1、表2及图2、图3可见，单一采样率下，高斯随机矩阵与分块循环Toeplitz矩阵测量下的重构图像PSNR及主观效果相当，而基于本文分块OSTM测量后的重构图像PSNR显著提高，主观质量更好且构造时间减少．

4.2 自适应采样率实验

为了进一步改善图像重构质量，对提出的自适应分块压缩感知算法进行仿真实验．分别基于高斯随机矩阵、分块循环Toeplitz矩阵以及本文分块OSTM对Peppers图像进行自适应分块压缩测量并重构．图4给出了采样率为0.50时的重构效果．作为对比，图5给出了自适应采样率下各种测量矩阵的重构效果．

可见，对3种测量方法来说，采用自适应分块压缩感知比采用单一采样率压缩采样，图像重构质量均有不同程度的提高．通过实验发现本文构造的分块OSTM矩阵对图像具有很好的压缩采样性能，结合自适应采样方案用于分块压缩感知，重构图像无论是客观PSNR指标还是图像主观质量，都达到了非常理想的效果．

图4 采样率为0.50时图像重构效果Fig.4 Reconstructed images at 0.50 subrate

图5 自适应分块压缩感知的图像重构效果Fig.5 Reconstructed images based on the adaptive BCS algorithm

5 结 语

作为压缩感知的核心，测量矩阵的性能好坏直接影响到重建算法的复杂度以及硬件实现的难易程度．本文提出的分块OSTM，采用伪循环的构造方式，易于硬件实现，减少了独立变元，降低了存储和运算量．针对图像压缩感知计算复杂的特点，研究了分块压缩感知理论，将图像块进行分类并结合分块OSTM测量，提出了基于分块OSTM的自适应压缩感知算法．仿真实验表明，本文算法实现复杂度低，图像重构质量较好．

［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.

（责任编辑：金顺爱）

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.

国家自然科学基金资助项目(61002027，61372145).

杨爱萍（1977— ），女，博士，副教授.

杨爱萍，yangaiping@tju.edu.cn.

时间：2014-01-07.

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