基于超像素与BoF的运动目标跟踪算法

邱晓荣+彭力+刘全胜

摘 要： 针对由遮挡、光照、形变等干扰产生的漂移问题，提出基于超像素和BoF的运动目标跟踪算法。此算法首先利用SLIC方法对运动目标的观测区域进行超像素分割，然后基于超像素构造中层视觉线索的超像素字典以及低层像素特征的BoF字典，实现对运动目标表观模型的混合建模，最后引入粒子滤波框架和在线字典更新，以适应目标和背景的变化。实验结果表明，该算法能够很好地应对严重遮挡、非刚性变换、复杂背景等干扰因素的影响，具有很好的稳定性和鲁棒性。

关键词： 目标跟踪； 表观模型； 中层视觉线索； 超像素； BoF； 粒子滤波框架

中图分类号： TN820.4?34； TP391.41 文献标识码： A 文章编号： 1004?373X（2018）06?0037?04

Abstract： In allusion to the drift problems caused by occlusion， illumination and deformation， a motion target tracking algorithm based on superpixel and BoF is proposed. The SLIC method is adopted to perform superpixel segmentation for observation area of motion target. The superpixel dictionary with mid?level visual cues and BoF dictionary with low?level superpixel characteristic are constructed based on superpixel to realize hybrid modeling for motion target appearance model. Particle filtering framework and online dictionary update are introduced to adapt the variations of targets and background. The experimental results show that the algorithm can tackle the effects of severe occlusion， non?rigid deformation， complex background and other interference factors， and has good stability and robustness.

Keywords： target tracking； appearance model； mid?level visual cue； superpixel； BoF； particle filtering framework

0 引 言

作为机器视觉领域的研究热点，运动目标跟踪融合图像处理、人工智能、模式识别等众多不同领域的相关基础知识，已经被广泛应用于智能交通、工业机器人、医疗诊断等领域。Wu等人总结了近年来众多学者提出的31种有效跟踪算法[1]，用于解决常见的11种干扰问题，例如光照变换、非刚性变换、目标遮挡等。

根据算法中对运动目标表观模型相似度的判别方式，运动目标跟踪算法可以分为生成式算法和判别式算法两大类。其中，生成式算法是根据运动目标的全局特征在后续的场景中搜索最相似的状态作为跟踪结果。当运动目标受干扰因素影响发生较为剧烈的特征变化时，算法会产生较大的漂移问题。经典的生成式算法有VTD[2]，L1T[3]等。Bao等人改進了L1T方法，使用L1APG方法加速求解稀疏系数[4]，提高了跟踪的效率和精度。Cheng等人提出粒子滤波框架下目标状态的多个片段和SIFT特征点匹配相结合的算法[5]，较好地应对了遮挡、光照、尺度等复杂场景的运动变化。

判别式算法基于运动目标的局部特征建立表观模型，把运动目标跟踪转换成目标与背景的二元分类问题。此类算法能够较好地应对跟踪过程中遇到的多种复杂干扰。经典的生成式算法有MIL[6]，TLD[7]等。Yang等人提出了BoFT算法[8]，该算法基于传统的IVT算法，结合RGB和LBP两种类型的局部BoF，获得了良好的跟踪效果。近年来，综合上述两大类算法的互补性，Zhong等人提出了生成式算法和判别式算法相结合的稀疏跟踪模型[9]。Yang等人提出了SPT算法[10]，先获取目标与背景区域中超像素和特征簇的概率分布，然后通过在线字典学习和MAP方法推导出最佳的候选运动目标区域，能够较好地应对严重遮挡、大幅度非刚性变换等干扰因素的影响。

受上述研究的启发，本文提出一种新的运动目标跟踪算法，该算法在文献[10] SPT算法的基础上加入BoF特征包，结合超像素字典和BoF字典进行运动目标跟踪，克服了SPT算法对相似背景干扰应对能力较差的缺陷。同文献[5]提及的算法相比，本算法的BoF字典提取了图像低层像素对应的超像素，可以充分利用超像素对光照、速度、形变的不变性，更为鲁棒地重构受外界干扰的目标。实验结果表明，本算法构建了自适应的运动目标表观模型，提高了多种严重干扰因素影响下相似度的匹配值，降低了目标跟踪结果漂移的概率，最终提高了算法的鲁棒性和有效性。

1 构建超像素字典和BoF字典的表观模型

1.1 超像素字典的构建

为了能够在跟踪阶段快速准确地找到运动目标，一般选取前5帧待测图像作为训练阶段的训练图像，并以此构建运动目标表观模型中的字典信息。超像素字典的构建共分为4个步骤：endprint

1） 以前5幀待测图像中的运动目标为中心，构建一个包含运动目标前景和背景的矩形观测区域，该区域的边长为运动目标区域对角线长度的1.5倍。如图1a）所示，白色虚线矩形内部为观测区域，白色实线矩形内部为运动目标区域。

2） 运用SLIC算法对各训练帧的观测区域进行超像素分割，分割时设置超像素个数为300、颜色空间相似度为10。结果如图1b）所示，并用[sp（n，r）]表示第[n]帧的第[r]个超像素。

3） 对训练阶段得到的所有超像素进行特征提取。由于超像素在通常情况下具有不规则的形状，不能简单地提取其边缘特征或纹理特征。因此，本文选用的是归一化后的HIS颜色直方图，并用[frn]表示第[n]帧第[r]个超像素的特征向量，如图1c）所示。

4） 使用K?Means算法对前[n]帧获取的所有超像素特征向量进行聚类，聚类所得的结果就是超像素字典Dsp。该字典中的第[i]个聚类包含3部分信息：聚类的前景背景置信值[ciclst]，如式（1）所示；聚类中心对应超像素的特征向量[fi]；该聚类中所含超像素特征向量的集合为[frnfrn∈cluster（i）]。

[ciclst=s+（i）s+（i）+s-（i）] （1）

式中：[s+（i）]表示该超像素聚类与前景的重合面积；[s-（i）]表示该超像素聚类与背景的重合面积。[ciclst]的取值范围是[0，1]，某一时刻[ciclst]越大，表明该超像素聚类是运动跟踪目标的可能性更大。如图1d）所示，当某超像素聚类中所有超像素都位于目标区域时，其置信值为1；当某超像素聚类中的所有超像素都在目标区域外的观测区域中时，其置信值为0。

1.2 BoF字典的构建

为了更好地提高运动目标跟踪算法的精度和鲁棒性，本文在超像素字典的基础上进一步引入了BoF字典。该BoF字典只基于运动目标的前景，整个过程为：

1） 如图2a）所示，先运用SLIC算法对前5帧图像中的运动目标区域进行超像素分割。再使用传统的规则网格分割方法将待测图像分割为尺寸大小完全相同的矩形块（本文选定为5×5像素）。

2） 以各矩形块中心点像素为基准点，获取该像素所属超像素的HIS颜色直方图特征向量[frn]，见图2b）所示。

3） 使用K?Means算法对前5帧图像中所有矩形块对应超像素的特征向量进行聚类，生成BoF字典DBoF，如图2c）所示。

4） 最后根据该BoF字典生成训练阶段各帧图像的BoF直方图，并用[bn]表示第[n]帧图像的BoF直方图特征向量，如图2d）所示。

2 基于超像素和BoF的运动目标跟踪

2.1 粒子滤波框架

粒子滤波是一种基于贝叶斯重要性采样原理的序贯蒙特卡洛方法，在非线性、非高斯分布的目标跟踪系统中，具有较好的鲁棒性，一般可以分为预测和更新两个阶段，如下：

[p（XtY1：t-1）=p（XtXt-1）p（Xt-1Y1：t-1）dXt-1] （2）

[p（XtY1：t）∝p（YtXt）p（XtXt-1）p（Xt-1Y1：t-1）dXt-1] （3）

式中：[p（YtXt）]表示目标的表观模型；[p（XtXt-1）]表示目标的运动模型。在粒子滤波框架下，[p（XtY1：t）]可以通过t时刻N个带有重要性权值[ωit]的采样粒子[Xiti=1，2，…，N]通过MAP方法近似求解。

2.2 相似度度量

粒子滤波框架下，需要度量粒子候选目标与表观模型中字典的相似度，从中选出相似度最大的最优粒子作为当前帧的跟踪结果，相关过程如下：

1） 新一帧图像的特征提取：以上一帧运动目标的跟踪结果为均值，随机生成600个候选粒子。然后以每个候选粒子为中心，构建包含目标区域的观测区域，经超像素分割后，用[fjm]表示候选粒子[m]的第[j]个超像素的HIS直方图特征向量，[εjm]表示该超像素包含的像素个数。

2） 求解候选粒子[m]与超像素字典的相似度[Ψspm]：先求出候选粒子中第[j]个超像素与超像素字典中第[i]个聚类的最大相似度[ωspm（j，i）]，如式（4）所示。[ωspm（j，i）]越大，表明该超像素与聚类[i]的相似度越高。

[argmaxiωspm（j，i）=argmaxiexp-fjm-fi22] （4）

再由[ωspm（j，i）]、对应聚类的前景背景置信值[ci]以及该超像素所含像素数目[εjm]进行加权求和，最终得到[Ψspm]，如下：

[Ψspm=εjm*ωspm（j，i）*ciclst] （5）

3） 求解候选粒子[m]与BoF字典的相似度[ΨBoFm]：先求出候选粒子[m]的第[j]个超像素[fjm]与BoF字典中第[i]个聚类[DiBoF]之间的最大相似度，如下：

[Ijm=argmaxiexp-DiBoF-fjm22] （6）

然后由[Ijm]得到该候选粒子基于超像素BoF字典的特征向量[bm]。再由式（7）求解该候选粒子与各训练帧BoF特征向量[bn]的最大相似值，即得该候选粒子与BoF字典的相似度[ΨBoFm]：

[ΨBoFm=argmaxiexp-bm-bn22] （7）

4） 由[Ψspm]和[ΨBoFm]可以得到候选粒子[m]与运动目标表观模型的相似度[Ψm]，如式（8）所示，并由此求出相似度最大的最优粒子。

[Ψm=μ1Ψspm+μ2ΨBoFms.t. μ1+μ2=1] （8）endprint

2.3 在线字典更新

为了能够使算法更好地应对遮挡、光照、形变等干扰因素的影响，需要在运动目标跟踪过程中对表观模型中的字典进行在线更新。通过更新可以及时获取运动目标表观模型前景和背景的变化，更新得越频繁，得到的表观模型越相似，但计算量会急剧增大。本算法中，字典的在线更新包括样本选择和聚类更新两个阶段，其中字典样本集中包含12帧图像的跟踪结果。

样本选择阶段，需要判定是否存在遮挡。本算法根据式（5）和式（7）求解最优粒子的[Ψsp]和[ΨBoF]，当两者分别低于指定阈值[λsp]和[λBoF]，即判定存在遮挡。当不存在遮挡时，剔除样本集中第一帧（时间最早）的相关信息，并把当前帧的相关信息放在样本集的末尾。当存在遮挡时，同样剔除时间最早一帧的相关信息，但在样本集中保留最后3帧的位置不变，将当前帧的信息存放到倒数第4帧的位置。聚类更新阶段，本算法每隔12帧（也就是常用帧率的[12）]，通过聚类算法更新一次超像素字典和BoF字典，更新的方式可参考第1.1节和1.2节中的相关内容。因此在实际跟踪过程中，当运动目标被遮挡时，聚类结果仍然保留了未遮挡时运动目标的相关信息，提高了跟踪算法的有效性和鲁棒性。

3 实验结果与分析

为了验证本文算法能在复杂环境下实现有效而准确的跟踪，本文基于bird2，lemming，woman等复杂场景的视频图像序列，将其与MIL，L1APG，SPT，TLD四种算法做了定量和定性两方面的对比分析。相关视频序列和算法源码可参考文献[1]提供的网址：http：//cvlab.hanyang.ac.kr/tracker_benchmark/index.html。本文相关实验都基于Matlab平台，遮挡阈值[λsp]和[λBoF]统一设定为0.8。

3.1 定量分析

本算法使用以下2个评价标准进行定量分析：

1） 跟踪成功率：定义如式（9）所示，当[P>0.5]时表明算法跟踪成功。

[P=area（Rgt?Ral）area（Rgt?Ral）] （9）

式中：[Rgt]表示各视频序列中原先标定好的真实目标区域；[Ral]表示算法实时在线跟踪后得到的目标区域。表1显示了5种算法跟踪成功率的平均值，并用黑色粗体标识了各视频图像序列的最优算法。

3.2 定性分析

视频序列的跟踪结果比较见图4。

1） 实验一：bird2图像序列中的运动目标主要受到遮挡、非刚性变换、快速移动等内外部因素的影响。例如，13帧处目标被遮挡，58帧处目标外观第一次反转，97帧处发生第二次反转。本文算法和SPT算法精确跟踪目标，且本文算法的跟踪精度更高。主要原因是在传统SPT算法的基础上结合了超像素BoF字典，使表观模型能够更好地反应低层像素所对应的超像素特征信息。

2） 实验二：lemming图像序列中的目标在运动过程中主要受到遮挡、快速移动、尺度变换等干扰因素的影响。例如，557帧处目标部分移出了取景框，896帧处目标受到了相似背景的干扰，1 130帧前目标经历了多次前后翻转。传统SPT算法发生了较大的漂移甚至完全丢失目标，在结合了BoF字典的相关信息后，使得本文算法精准地跟踪到了目标。

3） 实验三：woman图像序列中的运动目标受到了遮挡、光照变换、尺度变换、运动模糊等干扰因素的影响。例如，126帧处运动目标的下半部分受到了相似背景的大面积遮挡，MIL，L1APG，TLD算法产生了漂移并丢失了目标，513帧处运动目标的头部受到了相似背景的遮挡，562帧处目标发生了快速的尺度变化。本文算法能够比SPT算法更快更准地追踪到目标的变化，其原因主要是基于规格网格中心点像素对应超像素BoF字典的辅助作用。

4 结 语

本文提出一种粒子滤波框架和在线字典更新相结合的运动目标跟踪算法。该算法将运动目标表观问题转化为中层视觉线索的超像素字典和低层像素特征的BoF字典的最大相似度匹配，实现对运动目标表观模型的混合建模。其优点在于当目标处于重度遮挡、非刚性变换、相似背景等严重干扰因素的影响下，该算法仍能准确地跟踪到物体，具有较好的稳定性和鲁棒性。

参考文献

[1] WU Y， LIM J， YANG M H. Object tracking benchmark [J]. IEEE transactions on pattern analysis and machine intelligence， 2015， 37（9）： 1834?1848.

[2] KWON J， LEE K M. Visual tracking decomposition [C]// Proceedings of IEEE Computer Society Conference on Computer Vision & Pattern Recognition. San Francisco： IEEE Computer Society， 2010： 1269?1276.

[3] MEI X， LING H. Robust visual tracking and vehicle classification via sparse representation [J]. IEEE transactions on pattern analysis and machine intelligence， 2011， 33（11）： 2259?2272.

[4] BAO C， WU Y， LING H， et al. Real time robust L1 tracker using accelerated proximal gradient approach [C]// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Providence： IEEE， 2012： 1830?1837.endprint

[5] CHENG X， LI N， ZHANG S， et al. Robust visual tracking with SIFT features and fragments based on particle swarm optimization [J]. Circuits systems & signal processing， 2014， 33（5）： 1507?1526.

[6] BABENKO B， YANG M H， BELONGIE S. Visual tracking with online multiple instance learning [C]// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Miami： IEEE， 2009： 983?990.

[7] KALAL Z， MIKOLAJCZYK K， MATAS J. Tracking?learning?detection [J]. IEEE transactions on pattern analysis and machine intelligence， 2012， 34（7）： 1409?1422.

[8] YANG F， LU H， ZHANG W， et al. Visual tracking via bag of features [J]. IET image processing， 2012， 6（2）： 115?128.

[9] YANG M H， LU H， ZHONG W. Robust object tracking via sparsity?based collaborative model [C]// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Providence： IEEE， 2012： 1838?1845.

[10] YANG F， LU H， YANG M H. Robust superpixel tracking [J]. IEEE transactions on image processing， 2014， 23（4）： 1639?1651.endprint