基于多尺度空间的mean shift目标跟踪算法∗

（海军工程大学 武汉 430033）

1 引言

近些年目标跟踪算法已取得了很大的进步，然而为了简化跟踪模型，几乎所有的目标跟踪算法都假设目标的运动是平滑的，不存在突然变化［1～7］。在物体运动速度过快导致目标在相邻两帧中不存在重叠区域时，常常会收敛到一个错误的位置。

模板匹配算法无需任何关于目标运动的假设。然而，由于需要对整个图像进行穷尽搜索，算法时间复杂度过高。许多文献提出了加快模板匹配速度的方法，主要可以分为三类［8～11］：1）由粗及精的策略，先在低分辨率上粗匹配再在高分辨率上进行精匹配，然而这种方法要求低分辨率上的粗匹配必须取得较好的效果；2）对图像和模板进行下采样，这种方法会略去很多像素点，包括具有全局或局部最佳的点；3）估计似然函数的上界或者下界并削减不必要的操作，然而不是所有的似然函数都能找到上界或者下界。

本文提出了一种基于多尺度空间的目标跟踪算法。首先利用通过基于直方图的模板匹配算法在整个图像中寻找候选点，然后以这些点为初始点结合mean shift算法找到对应的局部极值，以最大局部极值对应点作为目标最终估计。最后利用尺度空间更新模板的尺寸和匹配窗口。

2 基于直方图的模板匹配

直方图是对旋转、形变以及部分遮掩有一定的鲁棒性。通过用直方图来表征模板T，则模板匹配过程可以定义为在当前帧中寻找与模板具有相似直方图的子图像。用来表示模板T的归一化直方图，表示以y为中心的候选子图像的直方图，每个直方图都含有m个分量。用Bhattacharyya系数作为相似度函数：

通过在当前帧中逐点比较q和p(y)可以构建一张似然图。其中ρ(y)最大的点作为目标中心位置。

3 基于尺度自动选择的由粗及精策略

设原始图像为I(x，y)，高斯金字塔采用以下迭代方式进行定义：

其中w(m，n)为加权函数。L是多分辨率分层模型中的最低分辨率。L过大会导致第L层的抽象模型与原始模型有较大差别，从而无法反映原始模型的真实形象，过小的L则无法达到降低计算复杂度的效果。最好的L使得目标的抽象模型和原始模型相似的最低分辨率。

设目标模板当前缩小l倍，此时的目标模板为M(l)，在每一层上计算M(l)与M(0)之间的相似度S(l)。

f(l)是一个度量函数，例如，Bhattacharyya系数。M(0)表示原始的最高分辨率的目标模板。Lmax是一个事先确定的多分辨率分层模型的层数的最大值。有两种方法确定最低分辨率L。一是使用固定阈值 Δ ：L=min{l|S(l)>Δ，l=1，2，…，Lmax}。二是使前后两层模型之间相似度的差值达到最大：Lmax。

4 结合mean shift算法

当前帧中的所有候选点从最低分辨率到最高分辨率分层进行匹配，在低分辨率下未通过的候选点将不会传递到更高的层次进行进一步的评估。设在最高层所保留下来的候选点集为S：

δ是事先设定的阈值。I为当前帧。ρ(p)参考式（1）。记N为S中候选点的总个数。对S中每一个点p，以该点为初始位置利用mean shift算法找到它们各自对应的局部极值。这些mean shift过程将收敛到N个目标当前位置的估计其中，具有最大值的点作为目标位置的最终估计：

5 实验

在本节，通过两个实例来展示本文方法的优势，跟踪结果将和文献［9］以及文献［12］中的算法进行比较，分别称为方法1和方法2。

如图1所示，目标是跟踪一辆静止的军用卡车。虽然卡车本身是静止的，然而由于机载平台的运动导致背景和卡车位置频繁而无规则的变化。在这种情况下，方法1和方法2都无法跟踪目标，而本文方法能有效地处理由于平台运动所造成的问题并对目标进行准确跟踪。

图1 跟踪卡车的实例

如图2所示，目标跟踪一个正在跑动中的人。该目标首先向前跑动，然后突然改变方向向后跑。运动方向的突然改变加大了跟踪难度。开始时，所有方法都能正确跟踪目标。然而，当目标突然改变运动方向时无论是方法1还是方法2都丢失了目标，只有本文方法仍然准确跟踪目标。

表1给出了三种方法的定位误差的均值和方差。跟踪速度显示在表2中。如表1所示，本文的方法比其他两种方法能更鲁棒和更准确的跟踪目标。它具有最小的误差均值和方差。如表2所示，虽然本文方法比其他两种方法要慢，但是仍能基本满足实时处理要求，特别是当目标的尺寸较小时。这种要求在大多数涉及机载平台的应用中都能满足。

第一行为方法1的结果，第二行为方法2的结果，第三行为本文的结果。

第一行为方法1的结果，第二行为方法2的结果，第三行为本文的结果。

表1 定位误差的均值和方差

表2 三种方法的跟踪速度

6 结语

本文提出了一种基于多尺度空间的mean shift目标跟踪算法。该方法在诸如运动机载平台等动态场景中能取得较好的效果。模板匹配方法用于处理全局运动而mean shift算法使得快速匹配方法具有更好的匹配结果。实验证明这两种方法的结合可以更准确和鲁棒地跟踪目标。