基于稀疏子空间选择的在线目标跟踪

黄丹丹　　孙怡

基于稀疏子空间选择的在线目标跟踪

黄丹丹1孙怡1

本文在粒子滤波框架下提出一种基于稀疏子空间选择的两步在线跟踪方法.在跟踪的第一步，利用稀疏子空间选择算法筛选出与目标状态相似性较高的候选区域，并将目标与背景间的过渡区域定义为单独的类别以降低目标发生漂移的可能；第二步则通过构建有效的观测模型计算候选区域与目标状态间的相似性，其中相似性函数综合考虑二者在整体和局部特征上的相似性，且将目标的原始状态和当前状态都作为参考，因此增强了观测模型的可靠性；最后利用最大后验概率估计目标状态.此外，该算法通过对目标数据的更新来适应目标的表观变化.实验结果表明该算法能有效处理目标跟踪中的遮挡、运动模糊、光流与尺度变化等问题，与当前流行的9种跟踪方法在多个测试视频上的对比结果验证了该算法的有效性.

目标跟踪，表观变化，稀疏子空间选择，粒子滤波

引用格式黄丹丹，孙怡.基于稀疏子空间选择的在线目标跟踪.自动化学报，2016，42（7）:1077-1089

目标跟踪是对视频序列中的目标进行状态估计的过程，它是特征提取、目标检测等底层视觉技术的输出，同时为行为判定、语义理解等高级视觉分析提供输入信息，在整个视觉处理流程中起到承上启下的作用.尽管研究者们提出了大量的跟踪算法［1-3］，但是由于形变、光照、遮挡等原因导致了目标表观的复杂变化，使得目标跟踪仍是计算机视觉领域的研究难点.

一般来说，一个跟踪系统最重要的两个组成部分是运动模型和观测模型.其中运动模型对目标在当前情况下所有的可能状态进行预测，常见的运动模型包括卡尔曼滤波［4］、粒子滤波［5］等.观测模型则用于计算每个候选状态与目标间的相似性，通常根据目标表观建模的方式确定，例如基于稀疏表达的跟踪方法常采用重建误差作为度量标准［6-9］，而基于直方图的建模方法则用直方图相似进行计算［10-11］.由于观测模型与目标表观建模密切相关，因此对目标表观进行精确而鲁棒的描述是成功跟踪的基础.根据表观建模的方式不同可将现有的跟踪方法分为两类，分别是生成式方法［12-15］和判别式方法［16-19］.

生成式跟踪方法首先对目标表观建模，然后在视频序列中搜索与目标模型最相似的区域来跟踪目标.增量视觉跟踪（Incremental visual tracking，IVT）［12］基于低维子空间的方法对目标建模，并通过子空间的增量学习对模型进行自动更新以适应表观变化.视觉跟踪分解（Visual tracking decomposition，VTD）［13］将运动模型和观测模型分为若干个小模型，通过这些小模型对目标的表观进行更精确的描述，因此该方法在目标表观发生变化时仍能比较准确地捕捉到目标的位置.此外，文献［14］利用稀疏表示技术对目标区域进行稀疏编码来表征目标，并通过均值漂移搜索具有最小重建误差的区域作为跟踪结果；而超像素跟踪（Superpixel tracking，SPT）［15］则采用中等视觉线索— 超像素来描述目标表观，并定义置信图计算候选区域与目标模型间的相似性.生成式跟踪方法不考虑目标与背景之间的区分性，因此当目标处于复杂背景时，很难保持稳定的跟踪.判别式方法则将目标跟踪建模为二类的分类问题，通过训练目标表观分类器来跟踪目标.典型的判别式跟踪方法如多样例跟踪（Multiple instance learning，MIL）［16］将目标附近的多个区域定义为正样本包，以此来缓解跟踪中的漂移问题.跟踪学习检测（Tracking learning detection，TLD）［17］则更关注目标的结构性，它将检测与跟踪相结合，并在训练中根据样本结构性限制不断修正分类器从而得到更好的跟踪结果.文献［18］将图像的稀疏编码作为特征来表征样本，并训练一个线性支持向量机来区分目标与背景.判别式跟踪方法虽然考虑了目标与背景之间的判别性，但是在跟踪中常会由于累积误差而导致模型的漂移.在以上两种方法的基础上，文献［20］构建了一个基于稀疏表示的联合模型，利用生成式方法和判别式方法联合跟踪目标，跟踪的结果则由两种方法共同决定.

上述方法从不同角度对目标表观进行建模，针对跟踪中的难点提出各自的解决方法，但是这些方法都需要对所有的候选区域构建表观模型，然后从其中选择与目标最接近的作为跟踪结果.然而实际上，根据运动模型获得的候选状态中仅有少数与目标状态接近，大部分候选状态都与实际状态具有较大的偏离，因此对所有候选状态进行建模不仅造成大量的冗余计算，而且这些候选区域具有不同的表观特性，这种表观复杂性也加大了跟踪中表观建模和观测建模的难度.针对这一问题，本文在粒子滤波框架下提出一种两步的在线跟踪方法.在跟踪的第一步，该方法首先根据指定的目标区域构造目标数据；然后利用该数据张成的子空间对候选区域进行预处理，提取出少量与目标状态最接近的候选状态，这个预选的过程通过稀疏子空间选择算法实现.在跟踪的第二步，则对这些选出的候选状态构建简单有效的联合观测模型，最后根据最大后验概率估计目标状态.与现有的跟踪方法不同，本文提出的方法对采样得到的候选状态进行预处理，在减少候选状态个数的同时还提高了候选状态的“质量”，即：保留的候选状态比其他状态更接近目标.这使得该算法不必为了区分多样化的候选状态而对目标的表观进行复杂的建模，在避免了冗余计算的同时也使得模型的设计更简约有效.在多个测试视频上的跟踪结果验证了本文算法的有效性.

1　基于相异性的稀疏子空间选择算法［21］

稀疏子空间选择是指从大量的源数据中找到一个子空间，该子空间能够保留所有目标数据的关键性质，构成子空间的元素也称为“代表”或“样例”.在视觉系统中，尤其是在视频处理中，稀疏子空间选择算法能够将大量的图像有针对性地进行聚类并获得聚类中心［22］. 基于相异性的稀疏子空间选择算法（Dissimilarity-based sparse subset selection，DS3）将该问题描述如下：已知源数据和目标数据利用某种度量标准计算X、Y中元素之间的相异性，根据二者的相异性矩阵计算X中数据对Y中元素的表达系数.首先介绍源数据X和目标数据Y之间的相异性矩阵D，该矩阵定义如下：

式中，‖·‖p表示lp范数；I（t）表示指示函数，当t=0时，函数值为0，否则值为1.式（3）中，目标函数的第1项用于约束表达Y所使用的元素个数，即寻找的子空间中所包含的元素个数，第2项约束的是X表达Y所需要的整体代价，第3项约束的是Y中奇异元素的个数，即Y中不能用X表达的元素的个数为平衡前两项约束的参数，wj>0是惩罚因子，ej∈［0，1］表示是奇异元素的概率.式（3）可以通过乘数交替方向算法（Alternating direction method of multipliers，ADMM）［23］求解.系数矢量zzi中只有少量元素非0，所以式（3）也可视为信号的稀疏表示问题.由于子空间选择算法的目的就是从源数据中找到能够表达目标数据的子集合，因此在根据式（3）求得优化解Z∗之后，可以通过数值的大小来确定子集合中的元素.如果X中的第i个元素对应的系数矢量zi满足则为子集合中的元素，其中µ为约束系数，本文中取值为0.2.为后文表述方便起见，将子集合记为其中lc为元素 xxlc在源数据集合X中的索引，C为子集合中元素的个数.从子集合的选择过程可知，C的值与源数据和目标数据有关，是根据式（3）的计算结果自动确定的.那么自然地，目标数据集合中的元素可以用子集合中的元素稀疏地表示，可以通过下式进行聚类，

从以上描述可知，已知源数据X和目标数据Y，通过DS3算法不仅可以找到X的一个低维子空间去描述Y，还能够根据这种描述关系将源数据自动聚类，并为目标数据中的每个元素分配类别.本文将目标跟踪中的候选区域作为源数据X，利用目标模板与背景模板构建目标数据Y，根据上述DS3算法将候选区域聚类，并为目标数据分配类别，选出与目标模板同类别的候选区域进行后续跟踪处理，以减少冗余计算并降低观测建模的复杂性.

图1　源数据（样本）示意图（（a）采样得到的候选区域；（b）归一化的候选图像）Fig.1　Sketch map of source data（samples）（（a）Candidates obtained by sampling；（b）Normalized candidates）

2　基于稀疏子空间选择的两步目标跟踪方法

本节着重介绍提出的两步跟踪算法，首先给出源数据与目标数据的构造方法；然后介绍如何利用DS3算法对候选区域进行预处理；之后提出本文使用的相似性函数，最后给出目标数据的在线更新方法.

2.1源数据与目标数据的构造方法

从上节可知，DS3算法从源数据张成的空间中寻找一个低维子空间来表达目标数据.本文将候选区域作为源数据，具体做法为：首先利用粒子滤波算法对目标状态进行采样，然后将采样得到的候选区域进行归一化，再对归一化后的图像进行列向量化就得到源数据其中是第个候选区域经过列向量化后得到的向量，d为的维数，m 为候选区域的个数.构造源数据的过程如图1所示，图1（a）中矩形框内的图像为采样得到的候选区域，图1（b）是经过归一化的候选图像.

目标数据是待表达的数据，本文根据指定的目标区域和背景区域进行目标数据的构造.从现有的跟踪方法可知，在目标建模时加入判别信息后会得到更好的跟踪结果［17-18］.大部分方法中，判别信息指的是目标和背景之间的差别信息，例如在基于稀疏表示的方法中，判别信息一般体现为利用目标模板和背景模板构造字典［18-19］.但是在实际中，目标区域与背景区域之间还存在过渡区域，如图2（a）中右侧上数第2个示意图所示.由于目标建模的方法不同，对过渡区域的处理也各不相同.在MIL跟踪中，将这部分区域作为正样本来包容跟踪中产生的模型漂移，而在文献［20］中则将其作为负模板以减少状态估计的误差.在本文提出的跟踪方法中，将过渡区域作为独立的一类，因此目标数据由三部分构成，分别是目标模板P=｛ pppi|i=1，···，n1｝、过渡模板H= ｛ hhhi|i=1，···，n2｝和背景模板G=｛ gggi|i=1，···，n3｝.这三类模板的位置分布分别如图2（a）中右侧三个示意图所示，具体的模板图像由左侧的矩形框表示.其中目标模板由目标区域向各个方向分别平移得到，背景模板从背景区域采样得到，过渡模板则在二者之间由采样得到，这三类模板在图2（a）中分别用实线、虚线和点划线的矩形框表示.对这些模板进行归一化和列向量化处理，即可得到由三类模板构成的目标数据其中n=n1+n2+n3为模板个数的总和，经过归一化的模板如图2（b）所示.

图2 目标数据（模板）示意图（（a）模板分布示意图；（b）归一化的模板图像）Fig.2　Sketch map of target data（templates）（（a）Sketch map of template distributions；（b）Normalized templates）

2.2基于DS3的候选区域预处理

按照上节的方法将源数据X和目标数据Y构建完成后，根据欧氏距离计算二者之间的相异性矩阵D，即通过求解式（3）可找到X的一个低维子空间用于描述Y，同时源数据X可根据表达系数矩阵Z自动聚类，目标数据Y可根据式（4）进行分类，图3给出了这一过程的示意图.图3（a）为样本图像，也即源数据X；图3（c）则是X的聚类结果，其中每个椭圆代表一类，不同线型的椭圆代表不同的类别.图3（b）表示的是目标数据Y，图像的外接矩形框给出Y中每个模板在图3（c）中所属的类别，例如目标模板 pp1的外接矩形为实线，那么 pp1与图3（c）中实线椭圆内的候选区域属于同一类别，其他模板的类别以此类推.从图3可知，经过DS3算法后，目标数据的每个元素都会在候选区域的聚类结果中找到对应的类别.由于目标数据由目标模板、过渡模板和背景模板构成，因此，根据图3所示的分类结果，可以得到与目标模板处于同一类别的候选区域，如图4所示.其中图4（a）为目标数据中的目标模板，它代表了目标在不同时刻的表观；图4（b）为图3（c）中与目标模板处于同一类别的候选区域，也就是经过预处理后保留下来的候选区域.

经过上述过程，候选状态中与目标状态接近的部分被筛选出来并根据观测模型进行最终的状态估计，而其余的则被抛弃.通过对候选区域的预处理，不仅减少了冗余计算，而且保留下来的候选区域的表观更趋于单一化，更有利于目标的状态估计.本文能成功地对候选区域进行预处理，主要有以下三个原因：一是根据稀疏表示系数筛选候选区域能够有效地适应目标的表观变化，由于大量基于稀疏表示的跟踪方法已经证明了稀疏模型能够处理局部遮挡、局部形变以及光流、尺度和位姿变化对目标表观的影响，而本文提出的粒子预判方法又是基于源数据对目标数据的稀疏表示系数，因此继承了基于稀疏表示的模型对目标表观变化的适应能力，从而使粒子预判的结果更加准确.二是采用DS3算法对候选区域进行聚类不需要预先规定类别个数，而是完全根据数据本身的特点自动聚类，避免了由于硬性规定聚类个数而导致的聚类误差，并使得同一类别内的候选区域具有更强的相似性.三是将过渡模板加入到目标数据中，使得偏离真实状态较小的候选区域也能被分离出来，降低了这部分候选区域被保留的可能性，这也保证了选出的候选区域更接近真实的目标状态.

图3　目标数据（模板）和源数据（样本）聚类示意图（（a）样本示意图；（b）模板以及聚类结果；（c）样本聚类结果）Fig.3　Sketch map of target data（templates）clustering and source data（samples）clustering（（a）Sketch map of samples；（b）Templates and clustering results；（c）Samples clustering results）

图4　粒子预判示意图（（a）目标模板示意图；（b）与目标模板属于同一类别的样本示意图）Fig.4　Sketch map of particles pre-filter（（a）Sketch map of target templates；（b）Sketch map of samples that has the same classes with target templates）

2.3相似性函数

在目标跟踪中，观测模型用于计算候选状态与目标区域之间的相似性，该相似性反映了候选状态是参考目标的概率.为了更准确地估计当前的目标状态，本文构建了一个联合相似性函数，从整体和局部两个方面综合衡量候选区域与目标之间的相似性.令表示经过预处理后保留下来的候选区域为第个候选区域，T为目标模板，那么与T之间的相似性可通过下式计算：

2.4目标数据在线更新

目标的表观在跟踪中会由于光流、视角以及本身形变等原因而改变.随着时间的推移，根据首帧信息构造的目标模型不能完全适应这些变化，从而导致跟踪失败.因此有效的模型更新是跟踪算法能否长期稳定跟踪的一个重要因素，本文对目标数据进行在线更新以适应目标的表观变化.由于目标数据是由目标模板、过渡模板和背景模板三部分组成，因此需要分别进行更新.为了使更新方法更加高效，本文每5帧进行一次判断，如果目标模板能够很好地描述目标当前的表观，则不需要更新.如果目标模板不能适应目标当前的表观，则用当前的跟踪结果取代目标模板中权重最小的模板，权重的计算方法与文献［6］相同.同时在目标区域与背景区域之间进行重新采样以更新过渡模板，并在背景区域采样更新背景模板.在目标模板更新时，保留首帧中由指定的目标区域构成的目标模板以减轻跟踪过程中的漂移.实验结果证明该更新方法与本文提出的两步跟踪方法相结合，能够准确地捕捉目标在跟踪过程中的表观变化，获得更稳定的跟踪结果.

3　两步跟踪算法的实现

本文提出的两步跟踪方法基于粒子滤波框架，粒子滤波中包含两个重要的模型，分别是观测模型和运动模型.令表示目标在第t帧的观测表示目标在第t帧的状态，本文将观测模型定义为：

此外，运动模型建模为具有6个独立参数的高斯分布，即：

在上述框架下，本文跟踪方法的第1步包括根据粒子滤波方法对当前状态进行采样、利用DS3算法对候选状态进行预处理.而第2步则包括对保留下来的候选区域构建观测模型，根据最大后验概率估计目标状态.为了将本文算法表述的更加清楚，本节总结了该算法的各个步骤，并概括如算法1所示.

算法1.两步跟踪算法流程

初始化阶段t=1:

在指定目标区域周围提取目标模板，在背景区域采样得

到背景模板，在目标区域与背景区域之间采样得到过渡

模板，利用三类模板构造目标数据Y；

跟踪阶段:

Fort=2:FrameNum

第1步:

1）根据第t-1帧的目标状态，利用式（9）进行状态预测，并用候选区域构造源数据X；

2）利用DS3算法对源数据聚类，并根据式（4）对

目标数据中的每个模板进行分类；

3）选出与目标模板属于同一类别的候选区域，进

行第2）步的处理；

第2步:

1）根据式（5）～（7）计算保留下来的候选区

取200 g飞灰，放入不锈钢容器内，量取20%（w/w）去离子水，将稳定化药剂溶解于水中并将水溶液均匀洒在飞灰样品表面，充分搅拌后，自然养护7 d，将养护结束后的样品破碎用于重金属浸出毒性检测。

域与目标模板间的相似性；

2）根据式（8）和式（10）估计当前目标状态；

更新:

Ift是5的整数倍

根据第2.4节方法更新目标数据Y；

End

End

此外，值得指出的是，本文在粒子滤波框架下实现目标的跟踪，主要是因为粒子滤波是一种比较有效的搜索策略，它采用多个随机的采样粒子来逼近目标真实的密度分布，可以不受状态矢量非线性和非高斯的限制.由于粒子滤波的限制条件少，并且能够提供目标所有可能的状态，因此与本文提出的粒子预判方法相结合后，能够使保留下来的粒子更加接近目标的真实状态，从而提高跟踪的准确程度.实际上，本文提出的粒子预判方法和目标表观模型也可以和其他的搜索方法相结合实现目标跟踪，如Kalman滤波和穷尽搜索等.但是Kalman滤波要求目标的运动模型和观测模型均为线性，并且要求系统噪声满足高斯分布，因此当目标不满足上述条件时容易导致跟踪失败.而穷尽搜索虽然能够提供有效的采样粒子，但是计算量太大，无法应用于自然场景下的目标跟踪.

图5　粒子预判算法对多余粒子的滤除性能Fig.5　Performance of the particles pre-filter algorithm for filtering the redundant particles

4　实验结果及分析

4.1粒子预判算法的有效性分析

本节选取四个测试视频进行粒子预判算法的有效性分析，分别是Faceocc、Singer1、Dollar和Owl序列.本节的实验包括两部分，一是分析算法对多余粒子的滤除情况，二是分析算法对跟踪性能的增强情况.图5是测试视频在粒子预判算法对多余粒子的滤除性能，其中横轴为初始的粒子数目，纵轴为经过粒子预判后保留下来的粒子数目，该数据是测试视频在所有帧的平均值.从图中可知，经过粒子预判后，保留的粒子数目有了大幅度的减少，证明了粒子预判的有效性.表1是测试视频在粒子预判前后的平均跟踪结果，包括中心位置误差和重合面积参数，中心位置误差PosErr定义为当前跟踪结果的中心位置坐标与参考值之间的均方根，面积重合参数定义为其中Rg和Rt分别表示目标区域面积的参考值和实际跟踪结果.表1中的数据是在初始粒子数目为300的条件下得到跟踪结果.无预判是没有经过粒子预判，直接对所有粒子都进行观测.建模的跟踪结果；有预判则是本文提出的两步跟踪算法的跟踪结果.从表中可知，经过粒子预判算法后，跟踪结果的准确性都得到了不同程度的提高，这是因为本文提出的粒子预判算法利用稀疏表示来建模目标和样本之间的结构关系，因此继承了稀疏表示模型对目标表观变化的适应能力，能够有效地去除距离目标真实位置较远的粒子，从而提高了算法的跟踪性能.

4.2定性分析

本节给出本文算法以及其他9种对比算法在测试视频上的跟踪结果，并从四个角度对这些算法的性能进行测试与比较.为了使图片中的结果更清晰，本文只给出效果最好的5种方法的跟踪结果并只对这5种方法的性能进行讨论与分析.

表1　有无粒子预判处理的跟踪结果对比Table 1　Tracking results comparing between the method with particle pre-filter and the method without particle pre-filter

图6　目标存在遮挡时的跟踪结果Fig.6　Tracking results when targets are occluded

测试1.目标存在遮挡时本文算法的跟踪性能. 图6（a）所示的Race序列中，目标不仅经历严重的遮挡而且目标的尺度和外观都发生了巨大的变化，从结果图像中可知，只有本文的算法能够在整个序列中保持稳定准确的跟踪.在150帧，当目标几乎被完全遮挡时，其他算法都不能对目标进行准确定位.而在576帧，尽管除了IVT外的方法都捕捉到目标的位置，但是只有本文算法能够对目标的尺度进行正确的估计.随着时间推移，到了719帧，除本文算法外的其余算法都已经丢失了目标，跟踪失败. 图6（b）所示的Faceocc序列中，人脸图像被频繁地遮挡，尽管图中所示的5种方法都能成功跟踪目标，但是本文的算法在尺度以及定位精度上要优于其他方法，具体数值如表3所示.图6（c）的Dollar序列中，目标纸币经过折叠后，从目标呈现的表观来看相当于该纸币被部分遮挡.IVT、MIL和DSSM在纸币被折起时，就产生了漂移，并且除MIL外其他方法并没有在后续图像中恢复正确的跟踪.而本文的算法在根据稀疏子空间选择算法对候选区域进行预处理时，将目标区域与背景区域间的过渡区域单独定义为一类，因此减少了这部分区域被保留下来参与最终状态估计的可能性，避免了漂移的发生.

测试2.目标由于快速运动而产生运动模糊时本文算法的跟踪性能.Jumping序列中的目标由于快速跳跃而产生模糊，而背景区域的复杂性也增加了跟踪的难度.IVT和Frag在构建目标模型时不考虑目标与背景间的区别信息，同时根据模糊目标图像构建的表观模型又不能准确地描述目标，从而导致跟踪失败.DSSM算法虽然利用了判别信息，但是对过渡区域所属类别的定义并不明确，因此当目标区域存在模糊时，极易导致模型的漂移.如图7（a）所示，DSSM的跟踪结果总是在实际位置周围，这说明该方法构建的目标模型虽然能在一定程度上区分目标与背景，但是模型已经产生漂移以至于不能准确地定位目标.此外SCM算法则由于其采用的联合模型而使得跟踪比较准确.相对于以上几种方法，本文算法在跟踪的第1步利用了目标与背景间的判别信息，而且将过渡区域明确规定为一个独立的类别，在减少漂移的同时也保证了筛选出的候选区域更接近目标的真实状态；此外，算法第2步建立的观测模型不仅从整体与局部两个方面综合衡量候选状态与目标之间的相似性，而且采用原始目标状态和经过表观变化的目标状态作为相似性函数的参考标准，因此本文的观测模型在存在模糊时仍能对目标当前的状态进行准确地估计.图7（b）所示的Owl序列中，目标区域的准确轮廓在快速的运动下几乎不能用肉眼分辨.从结果图像可见，除本文算法外，其余几种方法都有不同程度的漂移，这说明本文算法能够有效地处理跟踪中由于快速运动而产生的模糊现象.

图7　目标快速运动产生模糊时的跟踪结果Fig.7　Tracking results when targets appearance is blurry because of quick movement

图8　光流发生变化时的跟踪结果Fig.8　Tracking results when targets undergo illumination changes

图9　目标发生形变（（a），（b））以及场景中存在相似区域（（b），（c））时的跟踪结果Fig.9　Tracking results when targets occur deforms（（a）and（b））and results when there are similar regions in scenes（（b）and（c））

测试3.光流变化时本文算法的跟踪性能.图8（a）所示的Singer1序列中，场景的光流与目标的尺度都发生巨大的变化.L1和LSK不考虑目标与背景间的判别信息，因此不能很好地应对光流和尺度的变化.VTD、SCM和本文算法都能在整个序列中成功地跟踪目标，但是本文算法采用两步跟踪，不仅能够减少漂移，而且由于观测模型的有效性而使跟踪的结果更加准确.在Car11序列中，目标车辆在低照度情况下行驶，并且在运动中伴随着光流的变化以及由于相机抖动引起的轻微模糊.由于目标的表观在整个序列中只发生了刚性变化，因此大多数方法都能很好地跟踪目标.只有TLD方法从跟踪开始不久就产生漂移，并且随着时间推移，这种漂移越来越严重，如图8（b）所示.

测试4.目标表观发生变化或场景中存在与目标相似区域时本文算法的跟踪性能.在图9（a）所示的Sylv序列中，目标在不同光照下由于位姿变化而导致目标表观的变化.虽然这几种方法都成功地对目标进行了跟踪，但是DSSM和TLD算法在355帧到542帧之间发生了轻微的漂移，而SCM在613帧也偏离了目标的真实位置，本文算法一直保持着稳定的跟踪，并且取得了最好的跟踪结果，如表2和表3所示.图9（b）所示的Football序列中，目标经历快速运动并且场景中存在与目标相似的区域.从结果图像可见，IVT与Frag在181帧开始产生偏移，在309帧，VTD与DSSM也产生漂移，只有本文算法在整个序列中都能正确地估计目标的状态，从而保持着准确的跟踪结果.在Stone序列的背景中存在大量与目标类似的区域，这些区域增大了发生错误跟踪的可能性.在387帧，当目标被部分遮挡时，VTD将遮挡物误认为是目标，并在后续跟踪中无法恢复.而IVT、TLD与SCM在跟踪中不能很好地处理目标的尺度变化，对比而言，本文算法的跟踪结果取得了较小的定位误差，同时与参考目标具有最大的重合面积.

表2　跟踪结果的平均中心位置误差（像素）Table 2　Average center location errors of tracking results（pixel）

表3　跟踪结果的平均面积重合误差（像素）Table 3　Average overlap scores of tracking results（pixel）

4.3定量分析

本节采用中心位置误差PosErr和面积重合参数SC对所有跟踪算法的性能进行定量分析.表2、表3分别给出包括本文算法在内的10种跟踪方法在10个测试视频上的跟踪结果，分别为跟踪结果的平均中心位置误差和平均面积重合参数，其中最优以及次优的跟踪结果分别用粗体和斜体表示，“—”表示跟踪出现中断.从表2可知，本文提出的两步跟踪算法在这些测试视频上均取得最优或次优的结果，而在表3所示的重合面积参数中，本文算法在跟踪的准确性上优于其他所有的跟踪方法.

为了更直观地表现所有对比方法的跟踪结果，图10给出了上述两个对比结果的曲线图，点划线为本文算法的跟踪结果.图10（a）中的中心误差越小越好，而图10（b）中的重合参数越大越好.图中横轴测试视频的序号代表的视频序列分别为：1.Car11；2.Faceocc；3.Sylv；4.Dollar；5.Football；6.Jumping；7.Owl；8.Stone；9.Race；10.Singer1.从图10中可知本文算法的跟踪性能优于其他方法.

除了上述平均跟踪结果，本文还给出了Benchmark［2］中用于衡量算法整体跟踪性能的曲线：OPE（One-pass evaluation）的曲线下面积（Area under curve，AUC），如图11所示.其中图11（a）为精确度曲线，图11（b）为跟踪成功率曲线.从图11可知，当误差阈值设为20个像素时，本文算法的跟踪精确度达到90.25%，而当成功跟踪的阈值设为重合面积之比为0.6时，本文算法的成功跟踪率达到75.38%，这充分说明本文算法在整个跟踪过程中均能够保持比较准确而稳定的跟踪.

4.4算法的运行时间分析

本节对本文算法的运行时间进行分析.由于LSK方法要求运行环境为64位的处理器，无法与其他跟踪方法在同一实验平台上实现，因此本节只对包括本文算法在内的9种跟踪方法在相同实验平台上的运行时间进行对比.表4给出了这些跟踪方法的运行时间，从表中的数据可知，本文提出的两步跟踪算法虽然未能达到实时的跟踪，但是其运行时间在表中的跟踪方法中仍然处于中上水平.此外，本文算法采用文献［21］的作者提供的代码进行粒子预判的计算，该代码并没有经过优化或并行处理，是本文算法中最耗时的部分.在测试过程中，大概有3/4的运行时间耗费在粒子预判阶段，因此本文算法的计算效率仍有提升的空间.

图10　所有跟踪方法在全部测试视频上的跟踪性能（（a）平均中心误差曲线；（b）平均重合面积参数曲线）Fig.10　Performance of all the tracking methods in test sequences（（a）Average center error curve；（b）Average overlap area parametric curve）

图11　OPE曲线（（a）跟踪精度的统计曲线；（b）跟踪成功率的统计曲线）Fig.11　One-pass evaluation curve（（a）Precision plot of OPE；（b）Success plots of OPE）

表4　本文跟踪算法与对比跟踪算法的平均运行时间比较Table 4　Average running times comparing between the proposed method and other methods

5　总结

本文在粒子滤波框架下提出一种基于稀疏子空间选择的两步跟踪算法.该算法对采样粒子进行预处理，减少候选区域个数的同时提高了剩余候选状态与目标真实状态间的近似程度，从而减少冗余计算并降低了目标建模的复杂度.定义的相似性函数综合考虑候选区域与目标状态在整体与局部特征上的相似性，并且将目标的原始状态和经过表观变化后的状态同时作为参考，因此能够提供更为准确的观测模型，提高目标估计的准确性.此外，该算法采用的更新策略也增强了其对目标表观变化的适应能力.与其他跟踪方法的对比实验结果证明本文算法的有效性.

References

1 Yilmaz A，Javed O，Shah M.Object tracking：a survey. ACM Computing Surveys（CSUR），2006，38（4）：1-45

2 Wu Y，Lim J，Yang M H.Online object tracking：a benchmark.In：Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition.Portland，USA：IEEE，2013.2411-2418

3 Smeulders A W M，Chu D M，Cucchiara R，Calderara S，Dehghan A，Shah M.Visual tracking：an experimental survey.IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，36（7）：1442-1468

4 Kalman R E.A new approach to linear filtering and prediction problems.Transactions of the ASME，Journal of Basic Engineering，1960，82：35-45

5 Doucet A，Freitas N，Gordon N.Sequential Monte Carlo Methods in Practice.New York：Springer-Verlag，2001.

6 Mei X，Ling H B.Robust visual tracking using L1minimization.In：Proceedings of the 2009 International Conference on Computer Vision.Kyoto，Japan：IEEE，2009.1436-1443

7 Zhang T Z，Ghanem B，Liu S，Ahuja N.Robust visual tracking via multi-task sparse learning.In：Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition.Providence，USA：IEEE，2012.2042-2049

8 Hong Z B，Mei X，Prokhorov D，Tao D C.Tracking via robust multi-task multi-view joint sparse representation.In： Proceedings of the 2013 International Conference on Computer Vision.Sydney，NSW：IEEE，2013.649-656

9 Zhang S P，Yao H X，Zhou H Y，Sun X，Liu S H.Robust visual tracking based on online learning sparse representation. Neurocomputing，2013，100：31-40

10 Adam A，Rivlin E，Shimshoni I.Robust fragments-based tracking using the integral histogram.In：Proceedings of the 2006 IEEE Conference on Computer Vision and Pattern Recognition.New York，USA：IEEE，2006.798-805

11 He S F，Yang Q X，Lau R W H，Wang J，Yang M H.Visual tracking via locality sensitive histograms.In：Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition.Portland，USA：IEEE，2013.2427-2434

12 Ross D A，Lim J，Lin R S，Yang M-H.Incremental learning for robust visual tracking.International Journal of Computer Vision，2008，77（1）：125-141

13 Kwon J，Lee K M.Visual tracking decomposition.In：Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition.San Francisco，USA：IEEE，2010. 1269-1276

14 Liu B Y，Huang J Z，Yang L，Kulikowsk C.Robust tracking using local sparse appearance model and k-selection. In：Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition.Providence，USA：IEEE，2011.1313-1320

15 Yang F，Lu H C，Yang M H.Robust superpixel tracking.IEEE Transactions on Image Processing，2014，23（4）：1639-1651

16 Babenko B，Yang M H，Belongie S.Visual tracking with online multiple instance learning.In：Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition.Miami FL，USA：IEEE，2009.983-990

17 Kalal Z，Matas J，Mikolajczyk K.P-N learning：bootstrapping binary classifiers by structural constraints.In：Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition.San Francisco，USA：IEEE，2010. 49-56

18 Xie Y，Zhang W S，Li C H，Lin S Y，Qu Y Y，Zhang Y H.Discriminative object tracking via sparse representation and online dictionary learning.IEEE Transactions on Cybernetics，2014，44（4）：539-553

19 Zhuang B H，Lu H C，Xiao Z Y，Wang D.Visual tracking via discriminative sparse similarity map.IEEE Transactions on Image Processing，2014，23（4）：1872-1881

20 Zhong W，Lu H C，Yang M H.Robust object tracking via sparsity-based collaborative model.In：Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition.Providence，USA：IEEE，2012.1838-1845

21 ElhamifarE，SapiroG，SastryS.Dissimilarity-based sparsesubsetselection.IEEETransactionsonPatternAnalysisandMachineIntelligence， 2014.DOI：10.1109/TPAMI.2015.2511748

22 Elhamifar E，Vidal R.Sparse subspace clustering： algorithm，theory，and application.IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（11）：2765-2781

23 Boyd S，Parikh N，Chu E，Peleato B，Eckstein J.Distributed optimization and statistical learning via the alternating direction method of multipliers.Foundations and Trends in Machine Learning，2010，3（1）：1-122

黄丹丹大连理工大学信息与通信工程学院博士研究生.2007年获得长春理工大学电子信息工程学院电子信息科学与技术系学士学位.主要研究方向为视频序列中的目标检测与目标跟踪.

E-mail:dluthuang@163.com

（HUANG Dan-DanPh.D.candidate at the School of Information and Communication Engineering，Dalian University of Technology.She received her bachelor degree from Changchun University of Science and Technology in 2007.Her research interest covers object detection and object tracking.）

孙怡大连理工大学信息与通信工程学院教授.1986年获得大连理工大学电子系学士学位.主要研究方向为图像处理，模式识别与无线通信.本文通信作者.E-mail:lslwf@dlut.edu.cn

（SUN YiProfessor at Dalian University of Technology.She received her bachelor degree from Dalian University of Technology in 1986.Her research interest covers image processing，pattern recognition，and wireless communication.Corresponding author of this paper.）

Online Object Tracking via Sparse Subspace Selection

HUANG Dan-Dan1SUN Yi1

This paper proposes a two-stage online tracking method based on sparse subspace selection in the particle filter framework.At the first stage of the tracking，those candidates that highly similar to the target state are selected using the sparse subspace selection algorithm.The transition region between target and background region is defined as a separate category to alleviate the drifting.And at the second stage，a simple but effective observation model is built to calculate the similarities between the candidates and the target.The similarity measuring function not only considers the integral and local similarities comprehensively but also uses both the original target state and the state after appearance changes as references to enhance the reliability of the measurement model.Finally，the state of target is estimated according to the maximum posterior probability.Furthermore，the target appearance changes are captured by update strategy.The experimental results show that the proposed method can effectively handle the occlusion，motion blur，as well as illumination and scale changes in tracking.Comparative results on challenging benchmark image sequences show that this method performs favorable against the 9 other state-of-the-art algorithms.

Object tracking，appearance changes，sparse subspace selection，particle filter

10.16383/j.aas.2016.c150493

Huang Dan-Dan，Sun Yi.Online object tracking via sparse subspace selection.Acta Automatica Sinica，2016，42（7）:1077-1089

2015-07-30录用日期2016-01-23
Manuscript received July 30，2015；accepted January 23，2016本文责任编委刘跃虎
Recommended by Associate Editor LIU Yue-Hu
1.大连理工大学信息与通信工程学院大连116024
1.School of Information and Communication Engineering，Dalian University of Technology，Dalian 116024