一种新的压缩采样匹配追踪算法

基于特征在线选择的目标压缩跟踪算法李庆武;朱国庆;周妍;霍冠英【期刊名称】《自动化学报》【年(卷),期】2015(041)011【摘要】基于压缩感知理论的压缩跟踪算法能够有效地实现对目标的跟踪, 具有良好的实时性, 但该算法对目标特征没有进行在线选择导致跟踪鲁棒性不高. 本文提出一种基于特征在线选择的目标压缩跟踪算法. 首先,在目标附近采样得到正负样本集合, 计算样本的多尺度矩形特征, 采用压缩感知中的随机投影矩阵对高维特征投影得到低维压缩域特征, 对压缩域特征进行在线选择提取最优特征, 剔除被污染的样本特征, 使用简单高效的朴素贝叶斯分类模型进行样本判断, 实现对目标的跟踪, 同时对跟踪中目标在摄像头中的尺度变化进行建模,给出目标尺度变化的定量描述,实现了适应目标尺度变化的多尺度跟踪. 实验结果表明本文算法具有更好的鲁棒性与更高的跟踪精度,对目标跟踪中的遮挡、光线突变、尺度变化和非刚性形变等因素具有较好的抗干扰能力,同时算法复杂度低,可以满足实时性要求.%The compressive tracking algorithm based on compressive sensing theory can efficiently achieve real-time object tracking, but the algorithm does not select proper object features online, resulting in low tracking robustness. In order to solve this problem, an ob ject compressive tracking algorithm with online feature selection is presented. Firstly, sets of positive and negative samples are obtained by sampling around the object, and the multi-scale rectangle features of the samples are calculated. Secondly, the compressive sensing random projection matrix is used to reduce thedimensionality of high dimensional features to obtain low-dimensional compressive domain features, and the compressive domain features are updated and selected online to extract the optimal feature to remove contaminated samples and update the classifier. Finally, a simple and efficient Bayesian classification model is utilized to achieve the object tracking. Moreover, changes of object scale in the camera are modeled and a quantitative description of changes in scale is given for multi-scale tracking which can adapt to change of the object scale. Experimental results show that the proposed algorithm can achieve a higher tracking accuracy and better robustness than several state-of-the-art algorithms and can well respond to the interferences such as block in the object tracking, light mutation, scale changes, non-rigid deformation and so on. Meanwhile, it has a low computational complexity and fully satisfies the real-time requirement.【总页数】10页(P1961-1970)【作者】李庆武;朱国庆;周妍;霍冠英【作者单位】河海大学物联网工程学院常州 213022;常州市传感网与环境感知重点实验室常州 213022;河海大学物联网工程学院常州 213022;河海大学物联网工程学院常州 213022;常州市传感网与环境感知重点实验室常州 213022;河海大学物联网工程学院常州 213022;常州市传感网与环境感知重点实验室常州 213022【正文语种】中文【相关文献】1.结合特征在线选择与协方差矩阵的压缩跟踪算法 [J], 张红颖;李灿锋2.在线矩形特征选择的压缩跟踪算法 [J], 曹义亲;程威;黄晓生3.基于特征分组的在线目标跟踪算法 [J], 姜明新;王洪玉4.基于稀疏表达特征选择的压缩感知目标跟踪算法 [J], 程中建;李康;谷懿;袁晓旭;王森5.基于稀疏表达特征选择的压缩感知目标跟踪算法 [J], 程中建;李康;谷懿;袁晓旭;王森因版权原因，仅展示原文概要，查看原文内容请购买。

一种改进的快速压缩跟踪算法潘磊;束鑫;祁云嵩【期刊名称】《江苏科技大学学报（自然科学版）》【年(卷),期】2015(000)002【摘要】为研究目标跟踪问题，构造多种不同尺度的滤波器对目标进行滤波，生成目标高维特征；利用符合有限等距性质要求的稀疏矩阵对高维特征进行采样，获得目标低维特征。

采用朴素贝叶斯分类器输出与Bhattacharyya 系数乘积的形式作为目标与候选目标之间的相似性度量，并选择最大值所对应的候选目标作为下一帧中的目标。

文中提出了一种改进的快速压缩跟踪算法。

实验表明，该改进的算法能够对目标进行有效跟踪。

%An improved fast compressive tracking algorithm is proposed in view of the issue of object tracking . Firstly, multiple filters with various scales are constructed , which are used to produce target′s high-dimensional feature by filtering .Secondly , a sparse matrix that satisfies restricted isometry property is employed to generate low-dimensional feature of the target by sampling the high-dimensional one .Finally, product of a naive Bayes classifier′s output and Bhattacharyya coefficient is adopted to measure the similarity between the target and its candidates , the candidate with the maximum product value being selected as the target in the next frame .The experiments show that the proposed method could track the target more efficiently .【总页数】5页(P175-179)【作者】潘磊;束鑫;祁云嵩【作者单位】江苏科技大学计算机科学与工程学院，江苏镇江212003;江苏科技大学计算机科学与工程学院，江苏镇江212003;江苏科技大学计算机科学与工程学院，江苏镇江212003【正文语种】中文【中图分类】TP391【相关文献】1.一种改进的长时间压缩感知跟踪算法 [J], 李宏波;郑世宝;周芹2.一种针对视频对象快速移动和遮挡的改进mean-shift跟踪算法 [J], 唐勇;孙磊;孙宾3.一种改进的实时压缩跟踪算法 [J], 钟权;周进;吴钦章;王辉;雷涛4.一种改进的压缩跟踪算法 [J], 成凌飞;关海超;王科平5.一种改进的快速相关跟踪算法 [J], 杨勇智;文远保因版权原因，仅展示原文概要，查看原文内容请购买。

一种基于压缩感知的非重构频谱检测新算法近十年来，压缩感知(Compressive Sensing, CS)已经成为一种在信号处理中引起越来越多的关注和研究的新技术，它指的是当信号被采样时，信号的采样程度比以往占用的资源更少，从而节省资源、提高效率。

最近，压缩感知技术受到了越来越多的关注，在信号处理和信息传输领域发挥着重要作用。

压缩感知技术可以有效地消除信号的冗余信息，进而得到有效的信息，可以有效提高信号处理的效率。

本文主要介绍一种基于压缩感知的非重构频谱检测新算法，并对其优势和性能进行详细介绍。

算法原理压缩感知技术是指在不改变频率分辨率的前提下，将信号采样程度从传统采样的N倍降低到只采样M（M<N）个信号点，从而提高采样效率，减少采样所需要的资源。

这种技术在很多领域都有着广泛的应用，如在频谱检测中，可以将传统的频谱检测方案中的采样程序降低到只需要采样几个信号点，从而提高采样效率，减少采样所需要的资源，有着更高的可扩展性。

基于压缩感知的非重构频谱检测新算法(Non-Redundant Compressed Spectral Detection, NCSTD)，是一种基于压缩感知技术，针对带有重构噪声的频谱检测任务的有效算法。

在这种算法中，需要采样仅仅M个信号点，而不是传统的N个信号点，从而降低采样数量，提高采样效率。

NCSTD算法运用了一种基于低秩矩阵分解的技术，通过把目标子信号分解为低秩的部分，而不需要执行正则正则化，也可以有效消除噪声，进而提高检测的准确度。

实验表明，NCSTD算法可以有效地实现目标子信号的检测，与传统的非重构频谱检测算法相比，NCSTD算法比传统方法提高了检测准确度20%。

性能分析实验分析表明，NCSTD算法的性能显著优于传统的重构频谱检测方法。

NCSTD算法比传统方法提高了检测准确度20%，可以有效抑制有噪声的信号，有效提高检测的准确性，节省了采样的资源。

结论本文介绍了一种基于压缩感知的非重构频谱检测新算法，分析了它的性能，并且与传统重构频谱检测技术进行了比较。

基于自适应特征分布更新的压缩跟踪算法冷建伟;李鹏【摘要】传统压缩跟踪算法使用固定学习率更新特征分布,导致跟踪易受遮挡影响且鲁棒性较低.为此,提出一种可自动调节特征分布学习率的压缩跟踪算法.利用压缩感知理论得到样本的压缩域特征并计算其在正负类中的特征分布,结合两帧之间特征分布重叠度和正类更新阈值自适应更新特征分布,通过样本分类实现目标跟踪.在此基础上,利用相邻两帧目标改进的SIFT特征求解目标尺度变化,使跟踪窗口随目标变化实时更新.实验结果表明,该算法可有效抵抗遮挡、光线、尺度等因素对跟踪的干扰,具有较高的准确性、鲁棒性以及实时性.【期刊名称】《计算机工程》【年(卷),期】2018(044)002【总页数】7页(P264-270)【关键词】特征分布;压缩特征;稀疏矩阵;巴氏系数;SIFT特征;仿射变换【作者】冷建伟;李鹏【作者单位】天津市复杂系统控制理论及应用重点实验室,天津300384;天津理工大学自动化学院,天津300384;天津理工大学自动化学院,天津300384【正文语种】中文【中图分类】TP391.40 概述基于视频的目标跟踪是机器视觉应用的关键,也是计算机学科的一个重要分支[1]。

近年来有较多研究成果,文献[2]结合MeanShift和目标颜色直方图实现了对目标的有效跟踪,但该算法对颜色变化敏感,当目标受到光照或者目标本身颜色发生变化时,容易丢失目标;文献[3]提出的CamShift算法,在目标颜色变化时仍可以有效跟踪目标,而且能够自适应调整跟踪区域,提高跟踪精度,当目标与背景颜色区别较大时具有良好的跟踪效果,但当目标与背景颜色相近时,容易发生跟踪漂移;基于Kalman滤波[4]的跟踪算法是一种最优化自回归数据处理算法,即在视频中寻找与目标最相近的物体,该算法可很好地预测线性系统中的目标,但如果模型是非线性的,跟踪将会失败;基于粒子滤波[5]的跟踪算法对非线性模型也有很好的跟踪效果,但容易受粒子退化现象影响。

基于目标特征提取的改进型压缩跟踪算法庄哲民;龚家铭;谢光成;袁野【摘要】本文在传统的尺度不变特征子(Scale Invariant Feature Transform,SIFT)算法的基础上,提出了一种新的基于改进的SIFT压缩感知跟踪算法.该方法一方面通过改进压缩跟踪算法中分类器的更新策略来提高算法的实时性;另一方面,通过改进SIFT向量邻域的选取方法来实现降低向量维度,从而减少计算复杂度.仿真实验表明,该方法不仅可以提高跟踪目标的实时性,而且能够在发生目标尺度变化、遮挡、漂移的情况下对运动目标进行准确跟踪.%An improved SIFT target tracking algorithm based on compressed sensing is proposed in this paper.The real-time performanceis improved by improving updating strategy of the classifier in the compressive theory.On the other hand,The vector neighborhood of SIFT has been improved to decrease the vector dimension and the complexity of calculation.Simulations and experiments show that this method not only can improve the real-time performance of tracking target,but also can carry on the tracking of moving target accurately in the event of a target scale variation,occlusion shelter,drifting.【期刊名称】《测试技术学报》【年(卷),期】2017(031)002【总页数】7页(P93-99)【关键词】运动目标跟踪;特征提取;SIFT;压缩感知【作者】庄哲民;龚家铭;谢光成;袁野【作者单位】汕头大学电子工程系,广东汕头515063;汕头大学电子工程系,广东汕头515063;汕头大学电子工程系,广东汕头515063;汕头大学电子工程系,广东汕头515063【正文语种】中文【中图分类】TN911.73在视频图像处理技术日益成熟以及相关应用领域日益广泛的背景下，视频跟踪技术已成为当前研究与关注的热点[1]. 由于视频内容的复杂性、多变性以及场景的变化，实时跟踪某个运动的对象具有一定的难度，特别是当对象发生形变以及对象被严重遮挡时，实时跟踪将变得更为困难. 目前常用的视频跟踪方法主要有均值偏移算法[2]、卡尔曼滤波、粒子滤波、基于模板匹配[3]以及尺度不变性特征子(Scale Invariant Feature Transform， SIFT)算法[4]等.SIFT作为图像的一个局部特征算子，最早是David Lowe在1999年提出的. 由于SIFT算法具备对图像变换较强的适应能力，在图像匹配以及重建中都有着很好的应用，但因为SIFT算法的复杂性，导致匹配过程中花费的时间较长. 因此，本文提出了SIFT的改进算法，其核心一方面是在进行特征提取过程中改进SIFT的处理邻域，精简生成的SIFT算子的维度，从而减轻计算的复杂度；另一方面将压缩感知技术[5]用于视频数据的压缩，并改进压缩感知中分类器学习因子的更新策略，从而提高了整个算法的实时性.仿真实验结果表明，在处理运动目标发生尺度变化、旋转、遮挡等的情况下，基于目标特征提取的改进型压缩跟踪算法能够准确并且高效率地追踪运动目标，而且能够自适应应对光照改变引起的问题.1.1 改进的SIFT视频跟踪算法标准SIFT算法利用目标的尺度不变性的特征，整合相应的特征点来锁定目标并加以跟踪. 针对SIFT算子维度过高的缺点，本文提出从特征算子的生成邻域入手，对SIFT算子进行改进. 为了保证生成的描述算子具有旋转不变性，该邻域是以SIFT特征点为圆心，以8个像素单位为半径绘制的圆形邻域D. 我们将整个圆形领域划分为4个部分，半径为2个像素单位的内圆D1以及环宽为2个像素单位的3个圆环D2， D3， D4，圆形邻域D的数学表达如式(1)所示改进后的SIFT圆形邻域D如图 1(a) 所示.图1(a)表示的是一个16×16像素单位的局部圆形邻域图，其中不同的区域代表不同的子区域Di(其中i=1， 2， 3， 4)，图中每一个小方格代表一个像素.传统SIFT算子首先记录0°，45°，90°，135°，180°，225°，270°，315°这8个方向的子向量，通过整合2×2的像素子单元生成一个8维向量，最后生成一个高达128维的向量. 而在本文中，指定圆形邻域D对应4个部分，其中每个部分Di分别由10个子向量构成，这些子向量的方向分别是0°，36°，72°，108°，144°，180°，216°，252°，288°，324°. 因此，圆形邻域任意一部分Di的构成可由式(2)表示式中：向量组(di1，di2,...,di10)是由改进后SIFT邻域所生成的10个子向量构成，由于整个圆形邻域D生成的SIFT算子向量维度仅为40维，大大地降低了计算复杂度.我们以整个圆形邻域中的D1部分作为示例，在图1(b)中的向量d11～d110就是构成向量D1的10个子向量，显然向量D1的维度为10维，而D2， D3， D4 3个向量的生成步骤与D1一致，改进后的SIFT算子通过将圆形邻域的4个部分整合在一起后，最终算子的维度为40维.之所以选定圆形邻域，是由于其对旋转不敏感，从而减少一些特殊状况对跟踪结果的影响. 为了能够进一步处理复杂场景中目标发生较大尺度的旋转的问题，则需要在邻域的每个部分Di中寻找幅值最大的那个子向量dij(i=1，2，3，4；j=1，2， ...， 10)，并将dij以及之后的所有子向量同时进行相应的左移. 假设在D1找到其中最大的子向量，假设该子向量就是d11, 那么D1则不需要进行左移，因为该向量集的第一个子向量即为本向量集中幅值最大的一个. 否则就需要把幅值最大的这个子向量以及其后的所有向量提前，相应地，在该幅值最大的子向量之前的所有子向量右移到后部分. 也就是说假设D1中最大的子向量是d14, 那么前面3个向量则右移到最后，其他子向量全部一致性地左移. 最后结果如式(3)所示在传统SIFT算法中，只将特征点(极值点)梯度的相角作为旋转角度，而不是把邻域内其他点的相角作为旋转角度，故在本文中，只将子向量集中第一个子向量作为左移的参考来处理发生旋转的状况.实际的跟踪过程中很容易发生光照的骤变或者渐变，为了减轻相应的影响，故在生成完整的特征算子之前对其进行归一化处理在处理非线性光照的情况时，根据实验经验设置临界值为0.2，当向量中某子向量的幅值超过了临界值，则重置为0.2，相应地再重新进行归一化处理使得每个子向量符合要求.可见对SIFT算子的生成邻域进行改进后，优化后的SIFT算子不仅能够保留传统算子的优秀性能，而且大大降低了算子的维度，从而降低了算法的计算复杂度，为了进一步提高整个算法的实时性，将引入压缩感知理论，将视频目标跟踪结果进行优化.1.2 基于特征提取的压缩跟踪算法的实现压缩感知理论在视频跟踪的应用当中最大的优点即为减少计算复杂度，本文将压缩感知理论与特征提取算法相结合，一方面利用压缩感知使算法降低计算量，另一方面利用特征提取来优化跟踪效果. 同时针对传统的压缩跟踪算法和特征提取算子存在的缺点，分别对SIFT算子以及压缩跟踪算法中分类器的更新参数进行优化，提高跟踪算法的实时性以获取更好的跟踪结果.基于压缩感知理论，可以利用满足RIP条件的测量矩阵R=R n×m，将数据从较高维度的信号x∈R m 投影到较低维度的信号v∈R n，如式(5)所示式中： n≪m，在理想情况下，稀疏矩阵R能够保留下每个点对的初始距离，并且满足Johnson-Lindenstrauss定律，测量矩阵由式(6)的规则生成在此设置s=m/4，通常情况下s=2或3，可以获取一个非常稀疏的随机矩阵. 之后利用测量矩阵就可获取一个低维的特征集v(v1,v2,v3,…,vn)， n≪m, 同时为了能够更高效地进行建模，采用贝叶斯分类器对候选者进行分类跟踪，分类器生成方式如下[6-8]式中：p(·)表征的是测量值y=1或者y=0时的概率值或是基于不同的y的测量值时的条件概率.当运动目标发生漂移时，由于压缩跟踪算法无法控制不断累计的误差，最终很容易导致失败，为了能够满足实时性要求，并且控制在跟踪过程中累加的误差，我们引入学习率来权衡分类器中高斯参数的比重[9]式中： d 和 b 分别表示采样特征集的前一帧与新的采样值的参数(均值μ以及协方差σ)的差值，学习率λ就是影响分类器函数内高斯参数权重的因子[10,11]. 由于分类器的参数分为两个部分，一部分是前一帧中目标特征的模版参数，另一部分是当前帧中搜寻位置处新的模版参数. 当相邻两帧中运动物体运动量较小时，那么由于新的模版参数改变量很少，则将学习率设置得大一点，使得分类器参数基本维持上一帧时的状态；如果相邻两帧中的运动目标发生了剧烈运动，则需要将λ设置得小一点，毕竟最新的跟踪结果更加依赖于新的一帧中的信息. 综合来说，学习率λ间接反应了运动目标的实时状况.为了使学习率λ反映运动目标的实时状况，需要一个能够自适应调整的学习率来权衡相邻帧的变动情况，从而控制分类器的效果. 为了更好地表征相邻帧图片的“距离”，首先计算出每幅图片中我们感兴趣的追踪区域的归一化直方图，并利用巴氏系数来度量两帧图片的“距离”，如式(10)所示式中： pi为前一帧图像追踪区域直方图的离散分布概率，而qi表征当前帧所追踪区域最可能的预测目标区域直方图的离散分布概率. 距离ρ就是前后两帧图像之间差异的度量，根据设定好的阈值来确定是否对分类器相应参数进行更新，判定规则如式(11)所示新的学习率可定义为学习率λ′的取值范围是(0，1)，它与两帧距离ρ 成反比，在实际的跟踪过程中，首帧与末帧图像变化不大时，学习率λ′的取值会较小；相应的，若是首帧与末帧中运动目标的位置情况相差甚大，则λ′会被调整变大. 因此，自适应的学习率能够有效地控制误差的累积，当发生漂移和旋转的情况时，能较好地避免跟踪失败，采用自适应的学习率不仅没有给整个解决方案增加很多的计算量，且能改善复杂场景下的运动目标跟踪效率.改进的SIFT特征集是从前一帧的目标区域采样获得，然后从初始特征点里面随机选择固定数量的特征点作为初始特征点库，其中随机选取的特征点数量f事先会设置好. 本文的式(13)～式(15)为各个特征库内是互不影响的特征点，分别以u, v, w进行表示，其中第一级特征点库Sf表示为提取当前帧的特征点集，与前一帧所提取获得特征点库Sf进行匹配，匹配之后的特征点集则可表示为显而易见，匹配的数量m一定不会超过f.RANSC(Random Sample Concensus) 优化算法则用来将现有匹配之后的特征点进行优化，除去错误匹配的特征点，然后获得更准确的特征点集Sp，如式(15)所示此外，还可以利用已经获取的特征点集求取变换矩阵中的未知数，然后用来求解前一帧与当前帧目标尺寸的缩放比例和角度. 选取已经净化获得的特征点集，并在当前帧中随机选择若干数量的特征点，最终构成固定数量f的新的特征点库. 将上述步骤从初始帧到最后一帧，往复地在相邻两帧中施行，就可以求得目标尺寸的缩放比例，算法就可以自适应地调整追踪窗口的大小，减小跟踪误差.针对发生遮挡、光照以及旋转的场景中的目标跟踪，我们分别从公共目标跟踪视频库中选取face片段与coke片段，并在i7-4710MQ， 8G主机上进行调试，获取如图 2 的跟踪结果，其中a矩形框为原始压缩跟踪算法的跟踪结果， b矩形框则是基于特征提取改进型压缩感知跟踪算法的追踪结果. 从整个跟踪过程当中随机抽取6帧出来进行对比，可见人脸在从未遮挡到遮住部分再到完整再现整个过程中两种方法的跟踪结果.如图 2 所示，第1帧为初始化跟踪目标，在发生遮挡以前， a框与b框的效果基本一致，然后从第22帧开始有书籍分别从各种角度遮挡住人脸，在第27帧、第92帧、第157帧时a框都不能像b那样稳定地追踪运动目标，而且在最后目标重新暴露在视频中的时候， a框也无法恢复跟踪. 我们可以看出b框不论在哪种遮挡的情况下都能稳定地追踪到目标，而采用原始压缩跟踪算法的a框跟踪效果并不理想. 其原因一是在改进型的压缩跟踪算法的分类器参数λ是实时更新的，而在传统算法中该学习率的值是设置为固定的0.85；二是改进型的算法融合了优化的特征提取算法SIFT来强化跟踪效果，能在复杂的场景下跟踪目标.在第二个场景中，视频流中会出现光照、遮挡和旋转这几种常见的问题，同样采用传统的压缩跟踪算法与改进型压缩跟踪算法分别进行实验，随机选取其中的6帧进行对比，其中b框代表的是采用基于特征提取的改进型压缩跟踪算法的实验结果， a框代表的是传统压缩跟踪算法的跟踪结果，具体见图 3.如图 3 所示，同样第一帧为初始化选定跟踪目标，当人拿着罐头在灯泡以及植被附近运动且罐头仅仅自身旋转时，我们可以看到在第16帧附近时两种算法的跟踪效果基本一致；但在第34帧时，当罐头在移至离灯泡较远处并被植被的叶子所遮挡的时候，a框已经部分脱离了要跟踪的物体；第102帧时罐头自身发生旋转，此时的a框依然脱离了想要跟踪的目标；再到第274帧时， a框完全脱离目标，无法再跟上运动目标的节奏，然后b框却从始至终稳定地将目标跟踪在框内.可见由于物体的运动不可预测，跟踪过程中的分类器参数如果只单凭借经验设置固定值而不随物体实际运动实时更新的话，则跟踪效果总是不能如意；再则就是在复杂场景中，对运动目标进行高效率的特征提取，那样才能保证在发生了光照变化、遮挡、目标旋转等情况下仍然能稳定追踪到前景目标.为了数值化测量本方法的计算复杂度，显示其优越性，故将改进型压缩感知跟踪算法与传统压缩跟踪算法(CT)分别在同一PC机上重复进行调试运行20遍，取各个过程的均值记录如表 1 所示.本文算法除了具有较高的实时性的优点之外，经过改进后的SIFT算子与压缩感知理论融合后的算法还能够在跟踪的准确度上有较高的优越性. 中心位置错误率是用来定量评估追踪矩形的中心和实际目标中心的欧几里德距离. 为了提高该数据的准确性，在软-硬件平台分别进行仿真本文的算法、传统的CT算法、 TLD算法以及OAB(Online AdaBoost)算法20遍，分别取中心位置错误率的平均值进行对比.通过观察表 2 中的数据，相比于其他算法，本文算法在两个视频流中的跟踪具有较强的鲁棒性.本文在传统SIFT 算法的基础上，通过将改进的SIFT算法与压缩感知理论进行融合，获得基于改进SIFT特征提取的压缩跟踪算法. 该算法一方面利用SIFT算子对目标进行实时检测跟踪的优秀性能，并且克服了原算子高维度的缺点；另一方面将压缩感知理论引入到视频跟踪算法中来，进一步优化跟踪结果，提高实时性能，从而在复杂的环境下，能够鲁棒地跟踪运动目标.【相关文献】[1] Kalal Z, Mikolajczyk K, Matas J. Tracking-learning-detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7)： 1409-1422.[2] David G. Lowe. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2)： 91-110.[3] Grabner H, Leistner C, Bischof H. Semi-supervised on-line boosting for robust tracking[C]. European Conference on Computer Vision, Marseille, France, October 12-18, 2008： 234-247.[4] 李新德，刘苗苗，徐叶帆. 一种基于2D和3D SIFT特征级融合的一般物体识别算法[J]. 电子学报， 2015， 43(11)： 2277-2283. Li Xinde, Liu Miaomiao, Xu Yefan. A recognition algorithm of generic objects based on feature-level fusion of 2D and 3D SIFT descriptors[J]. Acta Electronica Sinica, 2015, 43(11)： 2277-2283. (in Chinese)[5] 石光明，刘丹华，高大化，等. 压缩感知理论及其研究进展[J]. 电子学报， 2009， 37(5)：1070-1081. Shi Guangming, Liu Danhua, Gao Dahua, et al. Advances in theory and application of compressed sensing[J]. Acta Electronica Sinica, 2009, 37(5)： 1070-1081. (in Chinese)[6] 谢昕，徐殷，熊焕东，等. 基于压缩感知的SIFT图像匹配算法的研究[J]. 华东交通大学学报，2015， 32(6)： 115-121. Xie Xin, Xu Yin, Xiong Huandong, et al. Research on SIFT image matching algorithm based on compressed sensing[J]. Journal of East China Jiaotong University, 2015， 32(6)： 115-121. (in Chinese)[7] Babu R, Patrick P, fez, et al. Robust tracking with motion estimation and local Kernel-based color modeling[J]. Image Vision Computing, 2007, 25(8)： 1205-1216.[8] Kim T K, Woodley T, Stenger B, et al. Online multiple classifier boosting for object tracking[C]. Computer Vision and Pattern Recognition Workshops (CVPRW), IEEE Xplore, 2010： 1-6.[9] Matthews I, Ishikawa T, Baker S. The template update problem[J]. IEEE transactions on pattern analysis and machine intelligence, 2004, 26( 6)： 810-815.[10] Javed O, Ali S, Shah M. Online detection and classification of moving objects using progressively improving detectors[C]. Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2005： 696-701.[11] Williams O, Blake A, Cipolla R. Sparse bayesian learning for efficient visual tracking[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2005, 27( 8)： 1292-1304.。

压缩感知研究的新方法【摘要】经典的香农采样定理认为，为了不失真地恢复模拟信号，采样频率应该不小于奈奎斯特频率（即模拟信号频谱中的最高频率）的两倍。

但是其中除了利用到信号是有限带宽的假设外，没利用任何的其它先验信息，采集到的数据存在很大程度的冗余。

Donoho等人提出的压缩感知方法（Compressed Sensing 或Compressive Sampling，CS）充分运用了大部分信号在预知的一组基上可以稀疏表示这一先验信息，利用随机投影实现了在远低于奈奎斯特频率的采样频率下对压缩数据的直接采集。

该方法不仅为降低采样频率提供了一种新思路，也为其它科学领域的研究提供了新的契机。

该文综述性地阐述了压缩感知方法的基本原理，给出了其中的一些约束问题和估计方法，并介绍压缩感知理论的相关问题——矩阵填充，最后讨论了其未来可能的应用前景。

【关键词】压缩感知；贪婪算法；线性规划；随机投影1.引言当前大部分数据采集系统都是基于传统的香农采样定理来设计，按照这种方式采集的数据能够充分表示原始信号，但是它们存在较大的冗余。

因此，这些方法往往导致采集数据的泛滥和传感器的浪费。

研究如何根据信号的一些特征来实现低于乃奎斯特采样频率的采集，以减少所需采集的数据量具有重要的意义。

在过去的30年里，从噪声中提取正弦信号的方法吸引了许多科学家的关注，但是利用信号的可压缩性进行数据采样却是一个新兴的课题。

其起源于对具有有限信息率信号（finite-rate-of-innovation signal，即单位时间内具有有限自由度的信号）进行采集的研究，利用固定的结构性基函数（structured fixed deterministic sampling kernels）以两倍于新息率而不是两倍于奈奎斯特采样频率对连续信号进行采集。

Donoho等人提出的压缩感知方法是一种可以广泛应用于可压缩信号的采集方法。

该方法所需要的传感器数目大大减少，采集到的数据也具有更小的冗余度。

面向压缩感知的稀疏信号重构算法研究一、内容概括本文旨在深入研究面向压缩感知的稀疏信号重构算法。

压缩感知作为一种新兴的信号处理技术，其核心思想在于通过引入信号的稀疏性先验信息，实现在远低于传统Nyquist采样定理所要求的采样率下对原始信号的准确重构。

这一技术的出现，极大地拓宽了信号采样与处理的研究与应用领域，为众多实际问题提供了全新的解决思路。

我们重点关注稀疏信号重构算法的研究，这不仅是压缩感知理论的重要组成部分，也是实现压缩感知技术实际应用的关键环节。

我们介绍了压缩感知的基本理论框架，包括信号的稀疏表示、压缩采样以及重构算法等核心概念。

我们详细探讨了现有的稀疏信号重构算法，包括基于贪婪策略的重构算法、基于凸优化的重构算法以及混合重构算法等，并对这些算法的性能特点进行了对比分析。

为了克服现有算法的不足，我们提出了一种新型的基于最优化导向的稀疏信号重构算法。

该算法充分利用了信号的稀疏性先验信息，通过优化目标函数来寻找最优的信号重构解。

我们设计了一种高效的支撑集估计策略，能够准确地识别出信号的非零元素位置，并在此基础上实现信号的高效重构。

我们还针对多信源联合稀疏信号重构问题进行了深入研究，提出了一种基于混合支撑集模型的联合重构算法，能够有效地处理多个相关信源之间的信息交互与融合。

为了验证所提出算法的有效性，我们进行了大量的仿真实验。

实验结果表明，本文提出的稀疏信号重构算法在重构精度、计算复杂度以及鲁棒性等方面均表现出优越的性能。

我们还讨论了算法在实际应用中的潜在价值与挑战，为未来的研究提供了有益的参考与启示。

本文面向压缩感知的稀疏信号重构算法进行了深入研究，提出了一系列创新的算法与策略，为压缩感知技术的发展与应用奠定了坚实的基础。

1. 压缩感知理论概述压缩感知（Compressed Sensing，CS）理论，作为信号处理领域的一种革命性技术，其核心思想在于突破了传统信号采样与重构的范式，实现了采样与压缩过程的融合。

基于压缩感知的水下图像去噪作者：丁伟王国宇王宝锋来源：《现代电子技术》2013年第02期摘要：水下环境复杂，水下摄像得到的图像较为模糊。

采集数据时会采集到大量不包含任何有用信息的数据，噪声影响更严重。

压缩感知理论提出，能用较低采样率高概率重构信号。

为研究压缩感知对水下图像噪声的抑制作用，采用OMP，SP，COSAMP不同贪婪重构算法对水下图像进行不同采样率重构分析。

实验结果表明，选取合适采样率既可以以少量数据重构图像，又可以抑制水下噪声，且OMP算法效果最好。

关键词：压缩感知；水下图像；图像重构；图像去噪中图分类号：TN919⁃34 文献标识码：A 文章编号：1004⁃373X（2013）02⁃0019⁃030 引言随着地球上人口的激增，陆上资源的不断消耗，海洋逐渐成为人类赖以生存的发展新空间。

人类在对海洋进行探索发现时，往往采取水下摄像的方式获取有价值的信息。

相机在处理过程中需要采集大量数据，但经过变换后只需存储一小部分，大量不包含任何有用信息的冗余数据也被采集，这就对设备要求高，并且采集到的水下图像噪声的影响也会增大。

压缩感知的方法可以直接获取少量包含绝大部分目标信息的数据，经过重构得到需要的水下图像。

基于压缩感知的图像去噪方法，将图像中的有用信息部分作为图像中的稀疏成分，而将图像中的噪声作为图像去除其中稀疏成分后得到的残差，并以此作为图像去噪处理的基础。

本文主要研究贪婪重构算法系列对水下图像有色噪声的抑制作用[1]。

1 压缩感知理论介绍1.1 压缩感知理论的提出在日常生活中，人们接触的信号大多数是模拟的，但是目前在信息处理过程中能处理的信号却只能是数字化的，所以人们要得到信号，首先就要进行A/D转换，即模拟/数字信号转换。

转换过程主要包括采样、压缩、传输和解压缩4个部分。

其中采样过程必须满足奈奎斯特采样定理，即采样频率大于等于模拟信号频谱中最高频率的2倍。

然而随着时代发展，人们对信息需求量逐渐增加，携带信息的信号带宽越来越宽，所要求的处理速度和采样速率越来越高，这就使得相应的硬件条件难以实现，给信号的转换过程带来巨大的压力。

压缩传感总结报告摘 要 随着信息技术的不断发展，人们对信息需求量越来越大，这给信号采样、传输和存储的实现带来的压力越来越大。

传统的采样方法容易造成信息的冗余，因此，人们寻求新的方法避免信息的冗余。

压缩传感的问世，打破了常规的信号处理的思路，它将压缩和采样合并进行，突破了香农采样定理的瓶颈。

本文主要围绕稀疏表示、编码测量、重构算法三个方面对压缩传感进行基本的介绍。

最后介绍了压缩传感的应用以及展望。

关键词 压缩传感，稀疏表示，编码测量，重构算法1 引言传统的信号获取和处理过程主要包括采样、压缩、传输和解压缩四个部分。

其采样过程必须满足香农采样定理, 即采样频率不能低于模拟信号频谱中最高频率的2倍。

在信号压缩中,先对信号进行某种变换,如离散余弦变换或小波变换, 然后对少数绝对值较大的系数进行压缩编码, 舍弃零或接近于零的系数。

通过对数据进行压缩,舍弃了采样获得的大部分数据, 但不影响“感知效果”[1]。

但是，信号压缩实际上是一种严重的资源浪费，因为大量的采样数据在压缩过程中被丢弃了，而它们对于信号来说是不重要的或者只是冗余信息。

从这个意义而言，可得到以下结论：带宽不能本质地表达信号的信息，基于信号带宽的Nyquist 采样机制是冗余的或者说是非信息的。

如果信号本身是可压缩的, 那么是否可以直接获取其压缩表示(即压缩数据),从而略去对大量无用信息的采样呢？换句话说，是否存在一种基于信息的采样理论框架，使得采样过程既能保持信号信息，又能只需远少于Nyquist 采样定理所要求的采样数目就可精确或近似精确重建原始信号？Cand és 在2006年从数学上证明了可以从部分傅立叶变换系数精确重构原始信号, 为压缩传感奠定了理论基础。

Cand és 和Donoho 在相关研究基础上于2006年正式提出了压缩传感的概念。

其核心思想是将压缩与采样合并进行,首先采集信号的非自适应线性投影(测量值), 然后根据相应重构算法由测量值重构原始信号[7]。

一种基于压缩感知的非重构频谱检测新算法随着频谱检测技术的发展，以及各种应用的出现，如防窃、军事安全、无线传输等，如何精确快速地检测出传输信号中窃听信号的存在变得越来越重要，频谱检测技术也就成为了高级安全技术的核心组成部分。

压缩感知（Compressed Sensing，CS）算法是一种在收集频谱信号时，可以大幅减少所需采样数目的技术。

压缩感知算法一般由三个步骤组成：（1）重构原始信号中的主要特征；（2）用重构的特征构建压缩感知模型；（3）使用压缩感知模型重建源信号，以得到压缩后的信号。

压缩感知技术的优势在于可以使用更少的采样点，从而大大减少传输信号检测所需的计算时间。

然而，压缩感知技术需要重构原始信号的特征以构建压缩感知模型，在这个过程中容易出现重构误差，精确检测到窃听信号存在的几率会大大降低。

因此，为了解决这一问题，本文提出了一种基于压缩感知的非重构频谱检测算法，也就是说，不需要重构原始信号的特征，而是直接使用压缩感知模型对传输信号进行检测，以提高检测外窃听信号存在的准确率。

首先，我们建立一个基于压缩感知的模型，这个模型是通过希尔伯特空间的投影来实现的。

具体来说，我们将源信号投影到希尔伯特空间中，作为稀疏表示，然后根据投影结果，使用压缩感知模型对源信号进行检测。

由于不需要重构源信号，因此可以显著地减少源信号检测的计算时间。

其次，本文提出了基于压缩感知的非重构频谱检测算法的改进方法。

该方法将正则化和准变量等优化方法结合，以改善压缩感知模型的性能。

此外，本文还提出了一种新的检测准则，以实现更准确的频谱检测。

最后，我们验证了基于压缩感知的非重构频谱检测算法的有效性。

结果表明，本文提出的算法比基于重构频谱检测的算法更加准确，可以更快更准确地检测出传输信号中的窃听信号。

本文提出的一种基于压缩感知的非重构频谱检测算法可以有效地检测出传输信号中的窃听信号，并且可以显著地减少检测计算时间。

本研究的结果和方法有助于提高频谱检测的精确性以及高效性，可以为今后频谱检测的应用提供重要的理论及实践参考。

基于压缩感知的 OMP 改进重构算法王军;孔令斌;赵洁【摘要】针对无线通信网络近些年出现的大数据量信号的情况，在对信号采样的同时进行适当压缩，利用合适的重构算法实现了用少量的采样值或观测值对信号进行重构。

在原有基于 OMP(正交匹配追踪)的压缩感知重构算法的基础上引入AS(交替步长)，提出一种新的改进算法———GP-OMP(梯度正交匹配追踪)算法。

实验结果表明，该改进算法利用前一感知时刻获得的频谱信息，不仅能有效地降低重构算法的计算量，还能有效地减少重构耗时，并得到与原有方法基本一致的重构效果。

%In view of the emergence of mega data signals in wireless communication networks in recent years,this paper proper-ly compresses these signals while performing signal sampling and realizes their reconstruction with small amount sampling val-ue or observed value by using an appropriate reconstruction algorithm.On the basis of the original Orthogonal Matching Pur-suit (OMP)-based compressed sensing reconstruction algorithm,the Alternating Step-size (AS)is introduced andan improved algorithm,i.e.GP-OMP algorithm proposed.Experimental results show that the spectrum information this algorithm ob-tained by using the previous sensing moment can not only effectively reduce the amount of computations by the reconstruction algorithm,but also the reconstruction time,with almostthe same results as those by using the original method.【期刊名称】《光通信研究》【年(卷),期】2016(000)001【总页数】5页(P74-78)【关键词】重构算法;压缩感知;交替步长;频谱感知【作者】王军;孔令斌;赵洁【作者单位】西安邮电大学通信与信息工程学院，西安 710121;西安邮电大学通信与信息工程学院，西安 710121;西安邮电大学电子工程学院，西安 710121【正文语种】中文【中图分类】TN911.23近年来,一种新型的采样理论——压缩感知[1]在信号处理领域诞生。

压缩感知中迂回式匹配追踪算法裴廷睿;杨术;李哲涛;谢井雄【摘要】迂回式匹配追踪(detouring matching pursuit,DMP)是一种计算复杂度低、准确率高、对传感矩阵列相关性要求低的贪婪重构稀疏信号算法.DMP中子内积逆和系数矩阵递增递减核心式被提出并证明,DMP利用子内积逆和系数矩阵减少残差误差变化量的计算量,达到降低计算复杂度的目的.另外,DMP采用先逐个最优缩减、后逐个最优扩增假定支撑集元素的方法提高重构准确率和扩大重构稀疏信号的稀疏度范围.DMP算法复杂度分析表明,DMP算法中获取、缩减和扩增假定支撑集的复杂度分别为O(K2N),O(b(K-b)N)和O(b(K-b)N).加权间接重构0-1稀疏信号实验结果表明,对于稀疏度为M/2的0-1稀疏信号,DMP、逐步贪婪追踪(greedy pursuit algorithm,GPA)、子空间追踪(subspace pursuit,SP)、压缩采样追踪(compressive sampling matching pursuit,CoSaMP)、正交匹配追踪(orthogonal matching pursuit,OMP)的重构准确率分别为99％,65％,0％,0％和13％.非零值服从正态分布的稀疏信号实验结果也表明DMP的重构准确率优势显著.【期刊名称】《计算机研究与发展》【年(卷),期】2014(051)009【总页数】7页(P2101-2107)【关键词】压缩感知;贪婪算法;迂回式匹配追踪;分块矩阵;稀疏解【作者】裴廷睿;杨术;李哲涛;谢井雄【作者单位】湘潭大学信息工程学院湖南湘潭 411105;智能计算与信息处理教育部重点实验室(湘潭大学)湖南湘潭 411105;湘潭大学信息工程学院湖南湘潭411105;智能计算与信息处理教育部重点实验室(湘潭大学)湖南湘潭 411105;湘潭大学信息工程学院湖南湘潭 411105;智能计算与信息处理教育部重点实验室(湘潭大学)湖南湘潭 411105;国防科学技术大学计算机学院长沙 410073;湘潭大学信息工程学院湖南湘潭 411105;智能计算与信息处理教育部重点实验室(湘潭大学)湖南湘潭 411105【正文语种】中文【中图分类】TP391自然信号在某些特定变换域下是稀疏的，这种稀疏特性是同类自然信号背后的共性．利用变换后的稀疏特性，压缩感知实现以远低于奈奎斯特速率采样，同时能够完全重构自然信号［1－6］．压缩感知重构算法是依据观测矩阵和观测值重构原始稀疏信号的技术．压缩感知重构问题可以描述为如下数学模型：假设信号s∈RN，在变换矩阵Θ下能够获得稀疏信号x∈RN，x0＝K，x＝Θs，s ＝Θ－1 x，稀疏信号x通过传感矩阵Φ能获取观测数据y∈RM，M＜N，y＝Φx ＝ΦΘs，ΦΘ为观测矩阵．从观测数据y恢复未知稀疏信号x，进而恢复原始信号的问题可表述为L0问题：L1问题是一个广义线性规划问题，解法主要有凸优化算法和贪婪重构算法．凸优化算法是一种全局优化算法，以牺牲计算复杂度来实现准确重构，如对数障碍法［7］、原对偶内点法［7］、预计梯度法［8］和硬阈值迭代法［9－10］等．贪婪重构算法则是一类低复杂度重构稀疏信号算法．它主要是利用残差rS、观测值y 与传感矩阵Φ中列向量的关系来扩增或缩减假定支撑集S，以残差rS＝0判定假定支撑集为正确支撑集（矩阵全集Λ表示矩阵所有行号或列号组成的集合，子矩阵ΦS＝Φ（Λ，S），残差rS＝y－ΦS（ΦTSΦS）－1ΦTSy）．正交匹配追踪（orthogonal matching pursuit，OMP）是一种最简易有效的贪婪重构算法［11］．它通过逐个加入与当前残差相关性最大的列向量φi到子矩阵ΦS，更新假定支撑集S＝［S，i］（符号［］为并集符号，表示将［］内的数值集合或数值合x∈RN该问题被证明是NP难问题．通常将其转换为一个L1问题：并为一个数值集合）．由于OMP并未对假定支撑集进行修正，导致OMP可重构稀疏信号的稀疏度范围受限．压缩抽样匹配追踪（compressive sampling matching pursuit，CoSaMP）［12］和子空间追踪（subspace pursuit，SP）［13］通过扩增缩减方法修正假定支撑集，具有重构准确率高于OMP的特点，但不能保证更新假定支撑集对应的残差rS始终趋向于0．逐步贪婪追踪（greedy pursuit algorithm，GPA）是一种逐个最优增减假定支撑集的贪婪重构算法［14］．它依据残差误差ΔS＝ rS22最快趋向于0来更新假定支撑集，保证新残差比迭代更新前的残差趋向于0．由于CoSaMP，SP和GPA先扩增后缩减假定支撑集，导致子矩阵ΦS 列数过多，使重要中间参数x＾S＝（ΦTSΦS）－1ΦTSy计算复杂度高且精确度低．不同于以往先扩增后缩减假定支撑集的贪婪重构稀疏信号算法，本文提出的迂回式匹配追踪（detouring matching pursuit，DMP）算法主要思想是先逐个最优缩减、后逐个最优扩增假定支撑集元素，保证ΦS的列数不超过K，使DMP重构稀疏信号的计算复杂度低和重构准确率高．1 迂回式匹配追踪1．1 符号定义和定理推导全集Ω＝｛1，2，…，N｝；矩阵全集Λ，Λ表示矩阵所有行号或列号组成的集合；子集S⊂Ω，｜S｜表示子集中元素个数；补集，∩S＝∅∪S＝Ω，S/｛i｝补集为［i，］，［S，i］补集为/｛i｝；定位函数LS（i），i∈S，表示i在集合S中的位置；end指向向量（矩阵）最后一个元素（行/列）；增广矩阵B＝［Φ，y］；内积矩阵Ψ＝BTB；子内积逆PS＝（ΦTSΦS）－1＝Ψ（S，S）－1；系数矩阵CS＝（ΦTSΦS）－1ΦTS［ΦS－，y］；公因子fS（i）＝Ψ（i，i）－Ψ（i，S）CS（Λ，LS（i）），i∈S－；最小均方误差估计定理1．当i∈S－，且PS，P［S，i］存在时，有：证明．依据分块矩阵求逆理论得：将式（8）～（11）代入式（7），并联立CS 和PS 定义可证式（3）．依据CS定义得：将式（8）和式（10）代入式（12）可证式（4）．依据CS定义得：将式（9）和式（11）代入式（13）并联立式（4），可证式（5）．依据ΔS定义联立式（4）、式（5）和式（15）可证式（6）．证毕．定理2．当i∈S，且P ［S/｛i｝，i］，PS/｛i｝存在，有：证明．依据式（3）易知：联立式（20）和式（21）可证式（16）．由CS 定义易证式（17）．依据式（5）知：联立式（17）和式（22）可证式（18）．根据式（4）、式（6）和式（8）易知：联立式（23）～（25）可证式（19）．证毕．1．2 算法描述DMP先依据逐步最小化残差误差ΔS来获取初始假定支撑集S，然后通过缩减扩增过程迭代更新假定支撑集，当ΔS等于0或ΔS小于容限值tol，结束缩减扩增过程，输出正确支撑集S＊和稀疏信号x．DMP伪代码如算法1所示．在算法1中，DMP以来选择ΦS－中φi添加至ΦS，并更新假定支撑集S＝［S，i］，以arg min（ΔS/｛i｝－ΔS）来删除ΦS 中φi，并更新假定支撑集S＝S/｛i｝．DMP选择子内积逆PS和系数矩阵CS 来优化ΔS －Δ［S，i］和ΔS/｛i｝－ΔS 计算．DMP采用先缩减后扩增假定支撑集的方法，以最小缩减扩增假定支撑集元素个数保证残差误差Δ［S/｛ω1，…，ωb｝，νb，…，ν1］＜ΔS，更新假定支撑集 S＝［S/｛ω1，…，ωb｝，νb，…，ν1］．算法1．迂回式匹配追踪．输入：Ψ，N，K，tol；输出：S，x．初始化：S＝∅；S－＝Ω；CS＝∅；x＝0．/＊获取初始假定支撑集＊/for t＝1：K；/＊缩减扩增假定支撑集过程＊/PS＝Ψ（S，S）－1；b＝0；while b＜K－1/＊缩减支撑集＊//＊扩增支撑集＊/for t＝b：－1：1/更新支撑集＊//＊输出重构稀疏信号＊/1．3 算法分析1．3．1 算法复杂度分析在获取假定支撑集过程中，已知参数CS，｜S｜∈｛1，2，…，K｝．依据式（6），arg max（ΔS－Δ［S，i］）计算i∈S－复杂度为O（｜S｜N）．依据式（4）和式（5），C［S，i］计算复杂度为Ο（｜S｜N）．因此获取假定支撑集过程的总复杂度为 O（K2 N）．在缩减过程中，已知参数PS/｛ω1，…，ωb－1｝，CS/｛ω1，…，ωb－1｝，｜S｜＝K 和b∈｛1，2，…，K－1｝．依据式（19），计算复杂度为O（K－b）．依据式（16），PS/｛ω1，…，ωb｝计算复杂度为O（（K－b）2）．依据式（17）和式（18），CS/｛ω1，…，ωb｝计算复杂度为O（（K－b）N）．因此缩减b个元素的总复杂度为O（b（K－b）N）．在扩增过程中，已知参数 P［S/｛ω1，…，ωb｝，νb，…，νt＋1］，C［S/｛ω1，…，ωb｝，νb，…，νt＋1］，｜S｜＝K 和t∈ ｛1，2，…，K－1｝．依据式（6）Δ［S/｛ω1，…，ωb｝，νb，…，νt］）计算复杂度为 O （（K－t）N）．依据式（3），P［S/｛ω1，…，ωb｝，νb，…，νt］计算复杂度为 O（（K－t）2）．依据式（4）和式（5），C［S/｛ω1，…，ωb｝，νb，…，νt］计算复杂度为O（（K－t）N）．因此扩增b个元素的总复杂度为O（b（K－b）N）．1．3．2 算法对比分析与OMP相比，DMP能够选取使残差误差ΔS衰减最快的φi到子矩阵ΦS，更新假定支撑集S＝［S，i］，能保证获取初始的假定支撑集优于OMP获取的假定支撑集．与CoSaMP，SP和GPA采用先扩增后缩减方法不同，DMP采用先缩减后扩增的方法迭代更新假定支撑集．DMP缩减扩增过程中的假定支撑集元素个数｜S｜≤K，而SP和GPA扩增缩减过程中的｜S｜≤2 K，CoSaMP中｜S｜甚至最大值可以达到3 K．最小均方误差估计x＾S＝（ΦTSΦS）－1ΦTSy 是贪婪重构算法中一个重要的中间参数．若已知ΦTSΦS，（ΦTSΦS）－1的计算复杂度为O（｜S｜3）．对任意S，（ΦTSΦS）－1都存在的前提是要求Φ中至少任意｜S｜列不相关，SP和GPA要求传感矩阵Φ中至少任意2 K列不相关，CoSaMP要求至少3 K 列不相关，DMP只要求传感矩阵Φ中至少任意K 列不相关．另外，当｜S｜接近M时，x＾S精确度低且计算复杂度高．因此SP和GPA（CoSaMP）不能高准确率地重构稀疏度K＝M/2（K＝M/3）的稀疏信号，且在K接近M/2（M/3）时重构稀疏信号准确率锐减，而DMP能高准确率地重构稀疏度K＝M/2，且不存在K接近M/2时重构稀疏信号准确率锐减．2 实验与结果分析2．1 加权间接重构0－1稀疏信号选取稀疏信号x长度为N＝256，观测向量y长度M＝128，随机生成M×N维高斯矩阵Φ．随机选择x中的K 个元素，设置为1，其他N－K个元素设置为0，然后对x进行加权，加权向量t＝［1/N2，22/N2，…，N2/N2］．实验目的是对于给定的M，观察OMP，CoSaMP，SP，GPA 和 DMP准确重构率、平均重构时间与信号稀疏度K（0≤K≤M/2）之间的关系．对于每一个K值进行1 000次实验，图1（a）和图1（b）分别是重构准确率和平均重构时间的实验统计结果：Fig．1 Comparison of indirect reconstructive weighted 0－1sparse signal．图1 加权间接重构0－1稀疏信号对比图 1（a）显示，OMP，CoSaMP，SP，GPA 和DMP分别在K≤27，K≤39，K≤49，K≤53和K≤61时保证100%准确重构稀疏信号；在49＜K≤61时，OMP，CoSaMP，SP已经不能保证准确重构，而DMP依旧能够保证100%准确重构；在61＜K≤64时，DMP依旧能够保证99%以上的重构准确率；对于稀疏度K＝M/2的0－1稀疏信号，DMP，GPA，SP，CoSaMP，OMP重构准确率分别为99%，65%，0%，0%和13%；CoSaMP，SP和GPA分别在稀疏度接近M/3，M/2和M/2时重构准确率迅速下降．图1（b）显示，在K≤49时，DMP平均重构时间和OMP，CoSaMP，SP平均重构时在同一数量级，而小于GPA平均重构时间；在49＜K≤64时，DMP平均重构时间大于OMP，CoSaMP，SP平均重构时间．图1（a）和图1（b）显示，在1≤K≤64时，DMP重构准确率和平均重构时间始终优于GPA．2．2 重构非零值服从正态分布的稀疏信号随机选择x中的K个元素，设置为服从高斯分布的非零值，其他N－K个元素设置为0．其他设置同加权间接重构0－1稀疏信号实验一致．对于每一个K 值进行1 000次实验，图2（a）和图2（b）分别是重构准确率和平均重构时间的实验统计结果．Fig．2 Comparison of reconstructive sparse signals in which the non－zero values obeys normal distribution．图2 重构非零值服从正态分布的稀疏信号对比图2（a）显示，OMP，CoSaMP，SP，GPA 和 DMP分别在K≤22，K≤35，K≤43，K≤46和K≤52时保证100%准确重构稀疏信号；在43＜K≤52时，OMP，CoSaMP，SP已经不能保证准确重构，而DMP依旧能够保证100%准确重构；在52＜K≤64时，DMP依旧能够保证80%以上的重构准确率；对于稀疏度K＝M/2的0－1稀疏信号，DMP，GPA，SP，CoSaMP，OMP重构准确率分别为80%，30%，0%，0%和0%；CoSaMP，SP和GPA分别在稀疏度接近M/3，M/2和M/2时重构准确率迅速下降．图2（b）显示，在K≤43时，DMP平均重构时间和OMP，CoSaMP，SP平均重构时间在同一数量级，而小于GPA平均重构时间；在43＜K≤64时，DMP平均重构时间大于OMP，CoSaMP，SP平均重构时间．图2（a）和图2（b）显示，在1≤K≤64时，DMP重构准确率和平均重构时间始终优于GPA．3 总结本文提出的DMP是一种保证高准确率的低计算复杂度贪婪重构稀疏信号算法．它只需传感矩阵Φ满足至少任意K 列不相关．DMP利用子内积逆和系数矩阵减少残差误差变化量的计算复杂度，采用先缩减后扩增假定支撑集方法提高重构稀疏信号准确率和扩大可重构稀疏信号的稀疏度范围．实验结果表明，DMP先逐个最优缩减、后逐个最优扩增假定支撑集元素的方法优于CoSaMP，SP和GPA先扩增或缩减修正假定支撑集的方法，DMP能高准确率地重构稀疏度高达M/2的稀疏信号．参考文献［1］ Donoho D． Compressed sensing ［J］．IEEE Trans on Information Theory，2006，52（4）：1289－1306［2］Candès E， Wakin M． An introduction to compressive sampling ［J］．IEEE Signal Processing Magazine，2008，25（2）：21－30［3］ Shi Guangming，Liu Danhua，Gao Dahua，et al．Advance in theory and application of compressed sensing ［J］．Acta Electronica Sinica，2009，37（5）：1070－1081（in Chinese）（石光明，刘丹华，高大化，等．压缩感知理论及其研究进展［J］．电子学报，2009，37（5）：1070－1081）［4］ Jiao Licheng，Yang Shuyuan，Liu Fang，et al．Development and prospect of compressive sensing ［J］．Acta Electronica Sinica，2011，39（1）：18－22（in Chinese）（焦李成，杨淑嫒，刘芳，等．压缩感知回顾与展望［J］．电子学报，2011，39（1）：18－22）［5］ Li Zhetao，Xie Jingxiong，Yu Zuguo，et al．Compressed sensing based on best wavelet packet basis for image processing［J］．Journal of Computers，2013，8（8）：1947－1950［6］ Li Zhetao，Xie Jingxiong，Tu Dengbiao，et al．Sparse signal recovery by stepwise subspace pursuit in compressed sensing［J/OL］． International Journal of Distributed Sensor Networks，2013．［2013－08－06］．http：//dx．doi．org/10．1155/2013/798537 ［7］ Boyd S， VandenBerghe L．Convex Optimization ［M］．Cambridge：Cambridge University Press，2004［8］ Figueiredo M，Nowak R，Wright S．Gradient projection for sparse reconstruction：Application to compressed sensing and other inverse problems［J］．IEEE Journal of Selected Topics in Signal Processing，2007，1（4）：586－598［9］ BlumensathT，Davies M．Iterative hard thresholding for compressed sensing ［J］． Applied and Computational Harmonic Analysis，2009，27（3）：265－274［10］ Blumensath T．Accelerated iterative hard thresholding［J］．Signal Processing，2012，92（3）：752－756［11］ Tropp J， Gilbert A． Signal recovery from random measurements via orthogonal matching pursuit ［J］．IEEE Trans on Information Theory，2007，53（12）：4655－4666［12］ Needell D，Tropp J．CoSaMP：Iterative signal recovery fromincomplete and inaccurate samples ［J］． Applied and Computational Harmonic Analysis，2009，26（3）：302－321［13］ Dai W，Milenkovic O．Subspace pursuit for compressive sensing signal reconstruction ［J］． IEEE Trans on Information Theory，2009，55（5）：2230－2249［14］ Varadarajan B，Khudanpur S．Stepwise optimal subspace pursuit for improving sparse recovery ［J］．IEEE Signal Processing Letters，2011，18（1）：27－30。