基于积分直方图分块的MeanShift跟踪算法

陈瑞卿

摘 要：该文提出了一种新的基于积分直方图分块的MeanShift运动目标跟踪算法，采用积分图分块作为目标描述算子，融合了颜色直方图和空间信息，有效地解决了原始MeanShift跟踪算法仅仅利用了颜色信息，而造成颜色相似运动目标之间的误匹配，大量的试验结果表明，该文提出的方法，即使在复杂的场景中，也能够鲁棒准确地实现运动目标的定位并跟踪。

关键词：MeanShit算法 跟踪算法 改进

中图分类号：G420 文献标识码：A 文章编号：1674-098X（2015）03（a）-0056-01

视频图像中运动目标跟踪是计算机视觉领域中一个关键问题，在视觉监控、智能交通、感知用户接口、虚拟现实、智能房间、远程医疗以及视频编码等领域都有着广泛的研究价值和应用前景。MeanShift算法作为一种高效的模式匹配算法，就是在每一帧图像中寻找一个与目标模板特征最相似的候选目标区域，由于不需要进行穷尽式的搜索，已经成功地应用在实时目标跟踪领域中。MeanShift算法仅仅考虑到跟踪目标的颜色信息，没有考虑到空间信息，所以当场景中出现和运动目标颜色直方图相似的目标时，MeanShift算法会跟踪失效。

该文所提出的运动目标跟踪算法，融合了目标的颜色直方图和空间信息，与单纯地应用基本的MeanShift相比，跟踪的鲁棒性和效果要提升很多。积分图算法大大降低了邻域匹配中不必要的计算，提高了算法的实时性。

该文第1节介绍基本的MeanShift跟踪算法和基于积分直方图的分块跟踪算法，第2节介绍本文提出的改进算法，试验结果在第3节给出，最后是结论和展望。

1 MeanShift算法与基于积分直方图的分块跟踪算法

MeanShift算法对运动目标进行描述，采用了RGB颜色空间中的三通道彩色直方图。在给定的RGB特征空间中，以概率密度函数q来表达目标模型，候选目标模型记作为p（y）。q与p（y）的相似性度量就是考虑目标模板图像和候选目标图像各个样本点对之间的距离关系。距离越大表明相似性越小，反之相似性越大。故目标的定位就转化为测量相邻两帧图像之间目标模型和候选目标模型的相似性系数。

文献中介绍了一种基于积分直方图的分块跟踪算法，其较MeanShift算法对目标的定位准确，但计算量较大，因为在跟踪过程中，要计算图像序列中各帧的积分直方图和跟踪目标区域的积分直方图，用20个跟踪块来描述运动目标，且每一块都要计算其积分直方图，每一块的搜索都是在给定区域中穷尽式搜索，这些都大大增加了跟踪的时间消耗，对于跟踪实时性无疑是一个巨大的挑战。但这种跟踪方法考虑了运动目标的空间信息，较基本的MeanShift算法对目标的定位是准确的。

2 对目标模型描述的改进

MeanShift算法中对运动目标的描述中，没有考虑到运动目标各个部分的空间信息，也就是说，对于一个框定目标的矩形框或椭圆框来说，目标处于该框的任何位置，其直方图都是一样的，假设在一种很极端的情况下，即要跟踪的目标上半部分是白色，下半部分是黑色，而后在视频帧的某一帧中，在该目标的附近出现了一个上半部分是黑色，下半部分是白色的目标，其直方图的分布可以看到，只利用目标的颜色信息，其直方图的分布是相似的，这时，如果利用MeanShift算法跟踪时，很有可能跟踪错误，但利用积分直方图的分块跟踪方法时，由于其在描述目标的时候，考虑到了跟踪目标各部分之间的空间信息，不会跟错目标，但跟踪的实时性得不到满足。

2.1 对分块跟踪算法的改进

首先将分块跟踪算法中对于目标的分块操作进行修改，即在选定的特征空间里，并假设运动目标是用矩形框框住的前提下，对运动目标分为五部分来描述，即将运动目标从目标中心位置开始，水平方向分为上下两部分，垂直方向分为左右两部分，并且在与跟踪窗口的中心位置重合处得到一个小的跟踪窗口，用这五部分的描述来反应给定的跟踪目标。在跟踪的过程中，也是分开跟踪这五部分，最终将这五部分的跟踪结果进行加权组合，从而得到目标在当前帧中的最终位置。

2.2 综合分块跟踪算法和MeanShift算法

为了满足实时性的要求，不是将运动目标的各个跟踪块在给定的区域进行穷尽式搜索，而是用颜色直方图来描述运动目标的五部分，这样会考虑到运动目标的空间信息，不会像基本的MeanShift算法那样丢失了目标的空间信息，然后在给定搜索区域内对每一部分进行MeanShift算法的跟踪，从而每一块都会得到当前帧中的目标的位置，从而根据该块与目标中心的关系，可得到5个目标位置，最后，将这5个位置进行加权组合，从而得到目标在当前帧中的最终位置。

3 试验结果

我们所做的跟踪测试，都是在初始帧图像中选定一个固定形状的区域，譬如圆形、矩形或者是椭圆等等，并使得这个固定的区域能够将运动目标包围，在随后的各帧图像中，只要搜索到的区域和这个固定区域包含的区域最相似即可。

4 结论和展望

该文算法只是考虑到了在对目标模板进行描述的过程中，加入了目标模板的空间信息，与基本的MeanShift跟踪算法相比，只是目标的定位准确了一些，但时间的消耗比基本的MeanShift算法大，且没有考虑到所选择的特征空间的更新和目标模板的更新操作。

特征空间是从跟踪一开始就给定了，在跟踪的过程中，没有对特征空间进行更新，并且在整个跟踪过程中，目标模板始终保持不变，目标在运动过程中，其外观和背景都会发生相应的变化，在跟踪开始选定的特征空间或许就不能很好的区分跟踪过程中的目标和背景，肯定需要重新选择合适的特征空间，也需对目标模板进行某种更新操作来达到跟踪准确的目的。

在下一步的工作中，我们将尽力解决这个问题。

参考文献

[1] D.Comaniciu，V.Ramesh， and P.Meer.Kernel-based object tracking.IEEE Trans.Pattern Anal.Mach.Intell.2003，25（5）：564-577.

[2] D.Comaniciu，V.Ramesh，and P.Meer.Real-Time tracking of non-rigid objects using mean shift.In：Werner B，ed.IEEE Intl Proc.of the Computer Vision and Pattern Tecognition，Vol 2.Stoughton：Printing House，2000：142-149.