陈艳良 战荫伟

贪婪重构算法StOMP及其改进

陈艳良 战荫伟

(广东工业大学计算机学院 广东 广州 510006)

为了对新型的采样定理：压缩感知理论CS(Compressed Sensing)进行深入的研究并将其应用于图像压缩编码，对压缩感知中的贪婪重构算法进行综述并分析该类算法的优缺点。通过理论分析与仿真实验，对比各算法的性能与效率。该类算法中StOMP需要人为地进行参数设置，而人为设置的参数值往往使算法的重建效果较差。针对该问题，利用粒子群优化算法对StOMP中的参数进行配置，以此来提高StOMP的重建效果。实验表明经过参数配置后的StOMP算法在重构效果上平均提高了2.62 dB，最大能提高13.63 dB。

压缩感知 重构算法 匹配追踪 粒子群算法

0 引 言

奈奎斯特采样定理指出：为了避免信号失真，采样频率不得低于信号最高频率的2倍[1]。 随着社会信息化的不断深入，人们对信息量的需求也在不断上升，需要信号的带宽也越来越宽。依照奈奎斯特采样定理定然会导致海量的采样数据，大大增加了存储和传输的代价，这无疑给信号处理的能力提出了更高的要求，也给相应的硬件设备带来极大的挑战。2006年提出的压缩感知理论[2-4]是一个充分利用信号稀疏性或可压缩性的全新信号采集、编解码理论，它克服了传统采样定理的缺陷。该理论指出：对于稀疏或可压缩的信号，能够以远低于奈奎斯特采样率对其进行采样，并通过重构算法来准确或近似地恢复该信号。压缩感知在信号获取的同时对数据进行适当压缩。传统的信号获取和处理过程主要包括采样、压缩、传输和解压四个部分，这种先对数据采样后压缩的处理方式，浪费了大量的传感元、时间和存储空间。而压缩感知能够将数据采集和压缩合二为一，这一突出的优点使其在信号处理领域中有广阔的应用前景，如在图像压缩[5]、去噪[6]和视频编码[7]等应用中都取得了较好的效果。

压缩感知理论主要包括三个部分：稀疏表示、观测矩阵和重构算法。其中，重构算法作为压缩感知的核心内容，它关系到能否快速、准确地恢复原始信号。目前，压缩感知常用的重构算法主要包括两类：一类是凸优化算法，另一类是贪婪重构算法。凸优化算法重构效果好，但其计算复杂度相当高。贪婪重构算法具有原理简单、容易实现、运行速度快等优点，虽然其重构质量略差于凸优化算法，但由于该类算法在计算复杂度方面有很大的优势，所以在实际应用中使用广泛。本文将对该类算法进行深入研究。

StOMP 算法[16]属于贪婪重构算法，该算法需要人为地设置参数值，而经验值往往不是最优的参数配置。本文通过PSO算法对参数进行搜索，寻找最优的参数配置。PSO是一种进化计算方法，同遗传算法类似，是一种基于迭代的优化算法。目前该算法已广泛应用于函数优化、神经网络训练和模糊系统控制优化等领域。

1 压缩感知理论

假设信号x∈RN和正交变换矩阵ψ∈RN×N，对信号进行变换有：

α=ψx

(1)

其中α∈RN。若K=‖α‖0且K≪N，则认为信号x是稀疏的或可压缩的，K称为信号x的稀疏度。信号是否具有稀疏性是运用压缩感知理论的前提条件。为了获得α并使K尽可能小，通常要对x进行合适的变换。目前常用的变换有小波变换、傅立叶变换、余弦变换等。在已知信号是可压缩的前提下，压缩感知过程可分为以下两步:

y=φx

(2)

(2) 利用重构算法，根据y∈RM重构原始信号x。

为了从y中恢复出信号x。将式(1)代入式(2)有：

y=φψ-1α

(3)

令Φ=φψ-1∈RM×N，Φ={φ1,φ2,…,φN}，则有：

y=Φα

(4)

由于Φ、y为已知，可以根据式(4)求解α，再根据式(1)即可恢复信号x。但由于式(4)是一个欠定方程，所以方程有无穷多解，故无法确定α。但是，如果信号x是稀疏的且Φ满足有限等距性质RIP(Restricted Isometry Property)[8]，即对任意信号f和常数ε∈(0,1)，矩阵Φ满足：

(5)

则可以通过求解以下问题来确定α：

min‖α‖0s.t.y=Φα

(6)

RIP的等价条件[9]是观测矩阵和正交矩阵不相关。研究者已证明大多数随机矩阵都满足RIP[2,22]。压缩感知中常用的观测矩阵主要有高斯随机矩阵、傅立叶随机矩阵和哈达玛矩阵等。

为了求解式(6)，许多有效的重构算法被相继提出。目前，常用于压缩感知的重构算法主要包括两类，一类是凸优化算法，另一类是贪婪重构算法。综上可知压缩感知的处理过程如图1所示。

图1 压缩感知流程图

凸优化算法是将式(6)转换为以下等价的凸优化问题来进行求解：

min‖α‖1s.t.y=Φα

(7)

该类算法中常用的有：BP(Basis Pursuit)算法[10]、 内点法[11]、 梯度投影法[12]和同伦算法[13]等。该类算法的重构精度较高而且所需要的测量值较少，但是其计算复杂度相当高，比如BP算法的计算复杂度为O(N3)，所以只适合小规模问题的求解，在进行图像处理时，常常不能满足实时性要求。

贪婪重构算法对式(6)进行直接求解，其中具有代表性的算法有匹配追踪(MP)算法[14]和正交匹配追踪(OMP)算法[15]。后来出现了许多改进的匹配追踪算法，其中包括分段正交匹配追踪(StOMP)算法[16]、正则化正交匹配(ROMP)追踪算法[18]和子空间追踪(SP)算法[19]等。贪婪重构算法具有原理简单、实现容易、运行快速等优点。虽然其重构质量略差于凸优化算法，但由于该类算法在计算复杂度方面有很大的优势，所以在实际应用中使用广泛。

2 贪婪重构算法

2.1 算法分析

贪婪重构算法主要用于求解优化问题：

min‖α‖0s.t.y=Φα

(8)

MP算法[14]是Mallat于1993年提出的，它是最早的一种贪婪重构算法。其基本思想是先从字典Φ中选择与信号最匹配的原子φi0，i0满足:

(9)

然后将y向φi0方向投影，则可分解为：

y=φi0+R1f

(10)

继续对残差R1f进行同样的分解，令R0f=y，经过K步后有：

(11)

令:

(12)

αt=t=0,1,…,K-1

(13)

由于MP算法在每次迭代中只能保证新残差与最后选择的原子是正交的，而不能保证与之前选出的所有原子正交，使得每次迭代的结果可能是次优的。这不仅减缓了算法收敛的速度、增加了计算复杂度，并且会影响重构精度。

StOMP算法[16]在OMP的基础上提出了一种分段的策略，同时该算法在每次迭代中不止选择一个原子，而是选择若干个原子，选择的规则是通过一个硬阈值τ来控制。而且StOMP算法的迭代次数n也是人为设置的。当τ设置过大，会影响算法的效率。当τ设置过小，则会增加选择错误原子的概率，使得重构精度下降。因此，该算法中阈值设置是一个比较棘手的问题。该算法描述如下：

输入:矩阵Φ,信号y,迭代次数n,阈值τ输出:α初始化:残差r0=y,支撑集I=ϕ,α=0,t=1(1)根据阈值找出Φ中与rt-1匹配原子的索引。即:J=j>τ{}(j=1,2,…,N)(2)更新索引集:I=I∪J{}(3)更新解:α=Φ+Iy(4)更新残差:rt=y-ΦIαI(5)若t=n则停止迭代,否则t=t+1,转到(1)

ROMP算法[18]与OMP算法的不同之处在于每次迭代中选择K个最匹配的原子，用下式表示：

(14)

但并没有将这K个原子直接添加到支撑集中，而是利用正则化方法，对这些原子进行二次筛选，即先计算：

(15)

(16)

添加到支撑集中，舍弃其余原子。由上可知，正则化过程可以保证被舍弃原子的能量一定小于被选入原子的能量。从而提高重构精度，而且一次选入多个原子，重构速度也有所提高。

由式(14)可知ROMP算法的前提条件是已知信号的稀疏度，而这往往是难以做到的。对于自然信号其本身并不是稀疏的，需要经过变换才能变成稀疏信号，而且在不同的变换基下信号的稀疏度也是不尽相同的，这样估计信号的稀疏度就存在一定的困难。若稀疏度估计过小，就会经过多次迭代依然不能满足迭代停止条件；若稀疏度估计过大，则会大大影响重建效果。所以在不知道信号稀疏度的情况下，利用ROMP算法进行重构，误差会较大，这也是制约ROMP算法在实际中应用的一个关键因素。

SP算法[19]是从子空间的角度出发，首先选择一个含有K个原子的支撑集作为子空间，然后通过反复迭代更新子空间的原子，使其逐渐逼近真实支撑集。SP算法首次采用了回溯的思想，在每次迭代中对已经选入的原子同时进行检测，剔除错选的原子，选择更加匹配的原子，以达到更高的重构精度。同ROMP算法一样，SP算法也必须知道信号的稀疏度K。子空间的大小始终等于信号的稀疏度K，支撑集I中最多有2K个原子，所以每次迭代回溯时最多剔除K个原子。CoSaMP 算法与SP算法思想一致，唯一的区别在于：CoSaMP算法每次迭代时选择2K个原子，而SP算法每次选择K个，意味着CoSaMP算法[20]的运行效率要低于SP。

SAMP算法[21]是针对信号稀疏度问题提出来的，相对于ROMP算法和SP算法，其创新之处在于当信号的稀疏度未知时也可以精确地重构信号，从而在很大程度上扩大了该算法的使用范围。SAMP 算法引入了分段的思想，其稀疏度自适应过程如下：首先设定一个固定的步长s，在第一个阶段令K=s，在该稀疏度下进行迭代重建信号。若稀疏度是合适的，则迭代会一直进行下去直到满足迭代停止条件。否则，说明稀疏度太小，需要增大，令稀疏度K=2s进入第二个阶段继续迭代。SAMP 算法在每一个阶段中采用了回溯的方法来剔除错选原子，从而使原子的选择更加准确。

对初始步长的估计也是一个关键问题，步长估计准确与否直接关系到信号的重建效果。一般要求s

2.2 仿真实验

上节对OMP[15]、ROMP[18]、SP[19]和SAMP[21]等算法的原理及步骤进行了详细分析，为了说明贪婪重构算法的有效性并对比各算法的运行效率。本节将对这些算法进行仿真实验。以MATLAB 2010b作为编程实验平台，用256×256的Lena、peppers、couple和camera作为测试图像，以PSNR来衡量重建效果。n置为10，采样率为M/N=0.5，利用重构算法对图像进行恢复，表1记录了各算法的运行时间，图2显示了重建的Lena图像。

表1 运行时间比较(单位:秒)

图2 重构算法性能比较

由实验结果可知，贪婪重构算法能有效地重建原始信号，其中SAMP 算法的重构效果要优于其他算法，但运行时间最长，主要是因为它需要逐步逼近信号的真实稀疏度。StOMP算法不仅在每次迭代时选择多个原子，而且迭代次数少，因而运行时间最短。由于ROMP、SP 等算法需要信号的稀疏度作为先验知识，而图像的稀疏度是难以预测的，所以重构精度会受到影响，其中ROMP 算法所受影响较大，导致其重构效果较差。ROMP、SP 等算法比OMP 快是因为这类算法在每次迭代时能有效地选择多个原子，而OMP 只选择一个原子。整体而言，SP 算法不仅重构效果好，而且运行效率高，是一个较好的重构算法。

3 StOMP参数配置

StOMP 算法需要经验性的设置阈值τ和迭代次数n，然而在不同的情况下，经验设置往往不可靠。针对该问题，本文结合粒子群优化算法对指定范围的参数进行搜索，寻找最优的参数配置。

粒子群优化算法是美国电气工程师Eberhart和社会心理学家Kenndy基于鸟群觅食行为所提出的优化算法，简称粒子群算法PSO (Particle Swarm Optimization)[17]。该算法实现方便、收敛速度快、参数设置简单，是一种高效的寻优算法。在PSO中每个优化问题的潜在解都可以想象成搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个被优化函数决定的适应值，每个粒子还有一个速度决定其飞翔的方向和距离。粒子群体追随当前的最优粒子在解空间中搜索。PSO首先初始化一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己，第一个就是粒子本身所找到的最优解，这个解称为个体极值，另一个极值是整个种群目前找到的最优解，这个极值为全局极值。粒子始终跟随这两个极值变更自己的位置和速度直到找到最优解。设由m个粒子组成的群体在Q维空间进行搜索，每个粒子表示为：xi=(xi1,xi2,…,xiQ)，速度：vi=(vi1,vi2,…,viQ)，全局极值表示为：pg，个体极值表示为：pi(i=1,2,…,m)。则速度和位置的更新公式为：

vi=ωvi+c1ξ(pi-xi)+c2η(pg-xi)

(17)

xi=xi+vi

(18)

其中ω、c1、c2为算法中的参数，ξ、η为区间[0,1]的随机数。该算法描述如下：

输入:粒子数m和迭代次数K输出:全局极值pg初始化:c1=c2=2,ω=1,t=0(1)随机的初始化位置xi和速度vii=1,2,…,m()(2)计算适应值fi(i=1,2,…,m)(3)找出最大适应值对应下标,即^i=argmaxifi()(4)令个体极值pi=xi,全局极值pg=x^i(5)若t=K则停止迭代,否则t=t+1,转入(6)(6)根据式(17)、式(18)更新vi,xi,转入(2)

图3 StOMP 算法性能比较

算法LenaPeppersCameraHouseGoldhillStOMP24.8223.4923.8122.5817.11DStOMP27.1026.0324.2927.2020.33

4 结 语

本文对压缩感知中贪婪重构算法进行了深入的研究，并分析了各算法的优缺点。SAMP能够自适应地逼近信号真实的稀疏度，获得很好的重构效果。但该算法运行时间较长，不适合处理大规模的重构问题。ROMP与SP算法在迭代中需要稀疏度的先验知识，而自然信号的稀疏度往往是难以估计的，因而会影响该些算法的重构精度。总体而言，SP 算法兼顾了重建效果与运行效率，是一个较优的重构算法。

粒子群算法是一种新的进化算法，它从随机解出发，通过迭代寻找最优解，根据适应度来评价解的优劣。该算法实现容易、精度高、收敛快。本文通过粒子群优化算法对StOMP中的参数进行配置，从而提高了StOMP算法的性能。并通过实验对比说明了经过配置后，该算法的重构效果得到了较大改善。

[1] Nyquist H.Certain topics in telegraph transmission theory [J].Proceedings of the IEEE,1928,90(2):617-644.

[2] 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(2):489-509.

[3] Candes E,Wakin M.An introduction to compressive sampling [J].IEEE Signal Processing Magazine,2008,25(2):21-30.

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

[5] Zhu S,Zhang B,GABBOUJ M.Adaptive reweighted compressed sensing for image compression [C]//IEEE International Symposium on Circuit and Systems,2014:1-4.

[6] Hosseini S H,Shayesteh M G.Compressed sensing for denoising in adaptive system identification[C]//20th Iranian Conference on Electrical Engineering,2012:1238-1242.

[7] Fan N F,Zhu X,Liu Y,et al.Scalable Distributed Video Coding Using Compressed Sensing in Wavelet Domain[C]//IEEE 78th Vehicular Technology Conference,2013:1-5.

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

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

[10] Chen S,Donoho D,Saunders M A.Atomic decomposition by basis pursuit [J].SIAM journal on scientific computing,2006,20(1):33-61.

[11] Kimon F,Jacek G,Pavel Z.Matrix-free Interior Point Method for Compressed Sensing Problems [J].Mathematical programming computation,2014,6(1):1-31.

[12] Harmany Z,Thompson D,Willett R,et al.Gradient projection for linearly constrained convex optimization in sparse signal recovery[C]//17th IEEE International Conference on Image Processing.2010:3361-3364.

[13] Donoho D,Tsaig Y.Fast Solution of l1-norm minimization problems when the solution may be sparse [J].IEEE Transactions on Information Theory,2008,54(11):4789-4812.

[14] Mallat S G,Zhang Z.Matching pursuits with time-frequency dictionaries [J].IEEE Transactions on Signal Processing,1993,41(12):3397-3415.

[15] Pati Y C,Rezaiifar R,Krishnaprasad P S.Orthogonal matching pursuit:Recursive function approximation with applications to wavelet decomposition[C]//Conference Record of the Twenty Seventh Asilomar Conference on Signals,Systems and Computers.1993,1:40-44.

[16] Donoho D,Tsaig Y,Drori I,et al.Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit [J].IEEE Transactions on Information Theory,2012,58(2):1094-1121.

[17] Kennedy J,Eberhart R C.Particle swarm optimization[C]//Proc.IEEE International Conference on Neural Networks,1995,4:1942-1948.

[18] Needell D,Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit [J].Foundations of computational mathematics,2009,9(3):317-334.

[19] Dai W,Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction [J].IEEE Transactions on Information Theory,2009,55(5):2230-2249.

[20] Needell D,Tropp J A.CoSaMP:Iterative signal recovery from incomplete and inaccurate samples [J].Applied and Computational Harmonic Analysis,2009,26(3):301-321.

[21] Do T,Lu G,Nguyen N,et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]//42nd Asilomar Conference on Signals,Systems and Computers.2008:581-587.

[22] Baraniuk R,Davenport M,Devore R,et al.A Simple Proof of the Restricted Isometry Property for Random Matrices [J].Constructive Approximation,2008,28(3):253-263.

GREEDY RECONSTRUCTION ALGORITHM StOMP AND ITS IMPROVEMENT

Chen Yanliang Zhan Yinwei

(SchoolofComputer,GuangdongUniversityofTechnology,Guangzhou510006,Guangdong,China)

In order to carry out in-depth research on novel sampling theorem:the compressed sensing (CS),and to apply it to image compression coding,we give an overview on the greedy reconstruction algorithms in CS and analyse the advantages and disadvantages of each algorithm.According to theoretical analysis and simulation experiments,we give a comparison on performances and efficiencies of each algorithm.Among them,the StOMP algorithm shall set parameter values artificially,which usually lowers down the reconstruction effect of the algorithm.To solve this problem,we use PSO algorithm to configure the parameters of StOMP so as to improve the reconstruction quality of the algorithm.Experiment illustrates that the StOMP algorithm with parameters configured can increase the reconstruction effect by 2.62 dB in average and the maximum improvement reaches 13.63 dB.

Compressed sensing Reconstruction algorithm Matching pursuit Particle swarm optimisation (PSO)

2014-12-06。广东省教育厅高等院校学科建设专项资金项目(12ZK0362)。陈艳良，硕士生，主研领域：计算机视觉，图像处理，人工智能。战荫伟，教授。

TP391

A

10.3969/j.issn.1000-386x.2016.04.060