基于MeanShift的跟踪学习检测目标跟踪改进算法

周爱军， 张 松， 杜宇人

（1.南京师范大学泰州学院，江苏泰州225300；2.扬州大学信息工程学院，江苏扬州225000）

0 引 言

运动目标跟踪集成了人工智能、图像处理、模式识别以及神经网络等计算机领域的复杂技术［1-2］，是当前计算机视觉领域中研究的热门课题，广泛应用于身份识别、车辆导航、视频检索、人机交互、视频监控以及工业安防等领域。目标跟踪可以理解为对视频序列的每帧图像进行分析和处理，找到目标尺度［3］、颜色［4］、形状［5］和模式［6］等信息，通过前后帧图像的匹配［7-8］计算出目标的运动轨迹。

当前主要的跟踪算法有卡尔曼滤波［9］、Cam shift［10］、粒子滤波［11］和SVM［12］等。当目标跟踪过程中存在阴影、遮挡、实时性等问题时，传统算法缺少检测和修复跟踪偏差相结合模块，只能针对特定问题进行处理，并且只能在较短的时间内达到较好的跟踪效果。当目标初始化后，这些算法都是通过不同规则预测目标位置，当遇到遮挡和光照的变化时，就可能产生跟踪漂移现象，随着长时间的漂移累加最终导致目标丢失。

跟踪学习检测（Tracking Learning Detection，TLD）由Kalal提出，在单目标长时间跟踪中具有很大优势。与传统算法相比，该算法引入了在线学习机制，找出每1 帧图像中分类出现错误的样本进行纠正，并及时反馈给训练集，更新分类器。这种算法由于将跟踪、学习和检测相结合，在学习过程中持续更新目标模板参数，所以具有优秀的鲁棒性。本文提出了一种基于MeanShift的TLD目标跟踪算法，通过TLD 跟踪框的置信度来合理选择MeanShift跟踪算法迭代起始点，提高算法抗遮挡能力。在TLD跟踪模块用Susan角点代替均匀采样点，减少计算时间，提高了跟踪的实时性。

1 TLD算法

相对于传统的目标跟踪算法，TLD 将跟踪和检测结合起来，并且引用了在线学习机制，使其在跟踪被遮挡目标和目标形变等情况下更具鲁棒性。它采用半监督的学习机制，利用少量监督数据和海量无监督数据相结合，大大提高算法的性能。TLD包括跟踪、检测与学习模块，算法框架图如图1 所示。

图1 TLD算法框架

（1）跟踪模块。TLD 跟踪器是在Median Tracker基础上增加错误检测功能的新算法。跟踪模块采用了LK光流法［13-14］，且增加了前向和后向误差检测功能。在目标区域利用Grid 采样获得100 个样本点，用LK光流法对这些点进行2 次跟踪，然后计算对应的NCC相关系数，并求得中值。最后根据这些可靠跟踪点来更新目标跟踪框。

Kalal的Forward-Backward 错误检测算法需要2次利用LK光流法。如图2 所示，点①跟踪成功；点②经过2 次光流后未到达原来的点，说明点②跟踪失败。

图2 中值流法跟踪示意图

实际情况中，2 次光流后不会刚好回到原来特征点，存在一定的偏差。假设2 次光流的偏差小于设定的阈值，则判定跟踪成功。2 次光流的差值表示为

式中：p″＝LK（LK（p）），为2 次光流后的点。

TLD算法的跟踪模块利用金字塔LK 光流跟踪和前向后向误差检测计算出跟踪误差，去除误差较大的样本点。最终通过可靠的特征点计算出当前目标的新位置。该算法称作中值流跟踪法，算法实现过程如图3 所示。

图3 中值流跟踪算法的实现

（2）检测模块。TLD 检测模块由方差分类器、级联分类器和最近邻分类器组成。它是通过滑动窗口检测图像序列。当跟踪过程中出现目标丢失，跟踪器无法从错误中恢复，这时需要利用检测器进行目标检测，找出跟踪丢失的目标。当检测窗口被3 个检测器接受可判断为目标窗口。TLD 检测模块流程图如图4所示。

将目标区域、候选区域的方差进行比较，并将方差小于原始目标方差一半的区域过滤掉，方差计算式为

图4 检测模块流程图

式中：D（x）表示灰度方差；E（x2）为图像块灰度平方的均值；E2（x）为灰度均值的平方。利用方差检测器将图像中不可能成为前景目标的区域滤除。

TLD级联分类器就是对比一些像素的亮度值，对每个检测窗口计算其概率PPOS，满足PPOS＞0.5 才能被接受。

通过方差检测器和级联检测器的窗口最后需要通过最近邻检测器的筛选，选择与上1 帧目标相似度高的为最后的检测结果。这两个图像块之间的相似性度量为

（3）学习模块。TLD学习模块应用半监督学习方法，使用P-N学习的方法对检测器中的每1 帧进行估计，利用P专家找出错误的负样本，N专家找出错误的正样本。把结果反馈给训练集，从而更新分类器。这样就可以不断在线更新学习。

2 基于MeanShift的TLD跟踪算法

2.1 MeanShift算法原理

假设给定d 维空间Rd中n 个样本点xi（i ＝1，2，…，n）。在x点的MeanShift向量的基本形式定义为

式中：k是落入Sh区域内的所有样本点的个数；Sh是一个高维球区域，半径为h。满足以下关系的y 点的集合

采样点平均偏移量常用MeanShift向量表示，模板匹配时往样本分布占比多的区域迭代。一般而言，Sh中与x越靠近的样本点，其与x 周围的统计特征关联越大，所以引入核函数，并根据每个样本点位置不同赋予其对应的权值，扩展的MeanShift向量表示为

式中：G（x）是核函数，一般选择高斯核函数；wi为样本点的权值。对于样本空间中某一点z的概率密度可由核概率密度通过下式进行估计：

式中，k（x）表示核函数K（x）的轮廓函数。

MeanShift算法是一个不断迭代直至达到最佳位置的过程。如果假设初始点为x，允许的误差为ε，则MeanShift算法的具体步骤：①计算Mh（x）；②把Mh（x）赋给x；③如果mh（x）-x ＜ε，结束循环，否则执行①。

2.2 基于MeanShift的TLD跟踪算法

首先对MeanShift 搭建模型和参数选择。选择RGB空间计算目标模板的直方图，目标模板的像素个数用N 表示，选择Epanechikov 核函数计算其核颜色直方图，则目标模板的概率密度估计可以表示为

根据上1 帧的跟踪结果确定当前帧的搜索中心坐标y。以y为中心的区域中的每个像素用｛xi，i ＝1，2，…，n｝表示，则候选模板的概率密度估计为

采用式（11）求Bahttacharyya（BH）系数，计算待匹配目标和待选模板间的相似度，BH系数越大，相似度越高

在迭代搜索候选目标的过程中，常用的偏移量小于阈值。实际应用中，迭代次数更多用来控制搜索，通常情况下择迭代次数设为20。如果只用迭代，只能适应单一尺度的目标，不能适应目标的尺度变化。若前1 帧核函数带宽hp，则可以分别利用以下3 种核函数（h ＝hp，h ＝hp＋Δh，h ＝hp-Δh）来迭代搜索3 次。将BH系数最大的带宽作为最优带宽。为避免过度调节，将当前帧中的带宽修正

式中：χ是一个调节参数，经过试验测试本文选择0.1。

基于MeanShift的TLD跟踪算法步骤如下：

（1）读入视频帧，利用鼠标手动标定待跟踪目标，然后分别初始化TLD和MeanShift跟踪器。

（2）分别启动TLD 和MeanShift 跟踪器。通过TLD跟踪器预估目标位置，判断其置信度。当置信度较高时，以TLD 输出的目标中心位置作为MeanShift跟踪算法的迭代起点；当置信度低时，将前1 帧中目标跟踪框的中心位置作为跟踪的迭代开始点。

（3）将最大迭代次数设为20，在每1 次迭代搜索中，移动搜索中心位置至相似度大的中心位置。

（4）为了进行自适应尺度变化，动态调整Mean Shift跟踪的核函数半径。利用相似度最大候选目标的核函数半径求解最后的候选目标尺度。

（5）将MeanShift输出的目标框作为最终的跟踪预测框。

（6）判断它是否是最后1 帧。如果不是，返回步骤（2）判断新的1 帧；如果是，循环结束。

3 算法改进

基于MeanShift 的TLD 目标跟踪算法计算量大，无法实现跟踪的实时性。本文在TLD 算法的跟踪模块引入Susan角点，将Susan算法与TLD算法结合，用角点替换原均匀采样点，大大减少了采样点数量，降低了跟踪器的运行时间。

3.1 Susan角点

Susan 算法通过圆形模板遍历图像，选择圆形模板圆心作为核心点，对比模板内像素灰度值和核心点灰度值［15］，表示为

式中：I（x，y）是圆形模板中像素点的灰度值（核心像素点除外）；I（x0，y0）表示圆形模板核心像素点灰度值；C（x0，y0）为相似比较函数；t是设定的阈值。圆形模板中的像素点是否在USAN 区域，由该像素点的C值决定。模板中所有符合条件的像素组成核相似区。一般情况选择37 像素的模板，Susan 圆形模板如图5所示。

如图6 所示，当模板位于a 处，USAN 面积和模板面积一样；当模板往直线边沿挪动过程中，USAN 区域面积逐渐减小；当窗口模板核心点为c 和d 处，USAN区域面积等于模板面积的1／2；当模板进入b 处，USAN区域又会慢慢变大。当模板继续移动，到达图6中的h所示目标区域，此时USAN区域面积达到最大。当模板核心点到达角点时（如图6 中的e，f，g），此时USAN区域面积略等于模板面积1／4，这时USAN面积最小。

USAN区域面积表示图像局部特征强度。面积越小，核心点越有可能是角点，像素点处的USAN区域面积可用下式计算：

式中，n（x0，y0）的值表示USAN区域的面积。

对比每个像素点的USAN 值和几何阈值g，通过下式计算当前像素点的初始响应函数值。

式中：g可根据需要动态调整，不同g 值，Susan 算子具有不同检测结果。通常角点检测中g ＝0.5Amax（Amax对应USAN最大面积，通常由模板大小决定，大多数情况下Amax＝37）。满足R响应的像素点作为候选角点，在此基础上利用非极大值抑制确定其是否为角点。

Susan算法的具体步骤如下：①利用圆形模板遍历整个图像，判断USAN区域；②计算核心点USAN面积值；③用式（15）计算角点初始响应函数；④计算待选所有角点的非极大值的抑制。

图5 Susan圆形模板

图6 Susan特征检测原理

3.2 算法改进

原TLD算法的跟踪模块中均匀采样的100 个样本点集有很多会成为无用样本点，这样不仅会导致跟踪器的漂移，而且还会造成大量的计算量。本文为了解决均匀采样随机产生的特征点无法精确描述跟踪目标，将Susan算法与TLD算法相结合，利用Susan 算法获得的角点作为跟踪点，舍弃原Grid 采样点，大大提高了跟踪的鲁棒性。改良的跟踪模块如图7 所示。

图7 改良的跟踪模块示意图

4 实验分析

本文实验硬件配置：Core i7 ＠ 2.8 GHz，8 GB 内存，软件环境为：Visual Studio2012 和Matlab2012a，Opencv2.4.9。

4.1 跟踪稳定性

实验中跟踪器部分采用MeanShift 算法迭代寻找最相似目标，并且在跟踪器初始化时引入Susan 角点。学习模块和检测模块与原TLD 保持一致，对公开的Motocross、David、Car视频序列以及摄像头获取的视频进行跟踪测试。图8 基于Motocross视频序列，对比了本文算法和原TLD算法目标跟踪的结果，红色框标是原TLD算法，黄色框为本文算法跟踪标记。

图8 Motocross视频序列的跟踪

由图8 可知，图像在第96 帧和第291 帧分别发生了较大的尺度变化和遮挡，原TLD算法出现跟踪目标丢失。由于本文引入MeanShift算法，所以具有较强的抗遮挡能力，同时加入了角点后的改进算法有效解决了目标尺度变化，所以能够准确跟踪目标。相比于原TLD算法，本文算法跟踪成功率大大提升。表1 为TLD算法和本文算法分别对Motocross、David、Car序列进行多次反复实验，最终取平均值作为统计结果。

表1 跟踪结果对比

从表1 可看出，由于本文算法结合了MeanShift算法，有效地解决遮挡和尺度变化问题，跟踪成功率进一步提高。

对发生遮挡的车辆进行跟踪测试，视频序列共159 帧，如图9 所示。

图9 遮挡车辆跟踪结果

本文TLD算法能够检测更多稳定点数目，从而增强了跟踪的鲁棒性。当目标存在尺度变化、旋转、遮挡、消失后重现等情况时，原TLD 算法产生跟踪漂移甚至跟踪失败，本文算法能够准确跟踪目标。如图9所示，红色框标记为原TLD 算法跟踪结果，黄色框标记是基于MeanShift的TLD算法跟踪结果。在第10 帧黄色框和红色框都初始化选定了红色轿车（如图9 中的a），在第30 ～53 帧之间出现遮挡后，原TLD算法跟踪样本点出现扩散漂移和跟踪错误的情况；在第71 帧目标重新出现后，原TLD 算法没能重新获取目标，出现了跟踪丢失。本文算法能够重新捕捉到目标（结果如134 帧），成功跟踪被遮挡的目标，具有很强的鲁棒性。

对摄像头获取的视频跟踪测试结果如图10 所示。图10（a）为通过人工标定跟踪目标对象，图10（b）目标在外界条件良好的情况下的跟踪结果，图10（c）表示跟踪过程遇到严重遮挡时的跟踪效果。实验表明，本文算法相对于原TLD算法具有较强的抗遮挡能力。

图10 摄像头采集目标遮挡下跟踪测试

4.2 跟踪实时性

由图11 和表2 可以看出，由于均匀采样产生了很多无用点，导致原TLD算法特征点丢失严重。虽然本文算法具有较少特征点，但经过LK光流跟踪后，特征点基本保持不变。经过Susan算法得到的采样点能够有效表达目标特征，且大大减少跟踪中的计算量。证明本文算法具有更快的跟踪速度，满足实时跟踪要求。

图11 特征点提取

表2 特征点数量的变化

本文选用跟踪帧率的平均值作为衡量跟踪实时性指标，通过视频对Motocross、David、Car 视频序列以及摄像头输出的视频序列作为实验样本。各个视频序列在不同跟踪算法下的平均帧率见表3。

表3 不同算法处理速度的比较

通过表3 的比较可以看出：原TLD 算法和基于MeanShift的TLD算法的平均帧率基本相差不大。本文算法由于在跟踪模块中引入了角点算法，大大减少了计算量，所以实时性有明显提高。上述视频序列经过本文的改进算法实时性基本都有20%左右的提高。

5 结 语

针对跟踪过程中目标被遮挡容易丢失，本文研究了一钟将MeanShift 和TLD 结合的目标跟踪改进算法。当TLD跟踪框有较高的可信度时，以TLD输出的目标中心位置作为MeanShift跟踪算法的迭代起点；当置信度低时，将前1 帧中目标跟踪框的中心位置作为跟踪的迭代开始点。实验结果表明，改进算法能实现稳定跟踪。同时针对TLD 算法均匀采样获得的特征点中存在较多的无用点，在TLD跟踪模块引入了更具鲁棒性的Susan角点作为目标的特征点。选择角点后采用金字塔LK 光流法跟踪，跟踪过程中保留信息丰富的特征点，抑制了目标关键信息点集较少导致的跟踪漂移。通过实验表明，本文算法具备比较高的鲁棒性和实时性。