基于Camshift 和SIFT 线性融合的目标跟踪算法研究

叶家林，宋建新

(南京邮电大学 江苏省图像处理与图像通信重点实验室，江苏 南京210003)

运动物体跟踪是计算机视觉中非常重要的研究领域，在医学图像、视频监控等行业有着重要的应用。近年来，连续自适应地均值漂移算法(Camshift)［1］被广泛地应用于目标跟踪场合，可以实现对运动目标的快速跟踪。然而，Camshift 与MeanShift［2］一样，都是基于图像颜色直方图的跟踪算法，前者只是对后者的自适应改进，可以解决目标跟踪过程中发生的尺度缩放、持续跟踪等问题。但是当目标颜色与背景颜色相近，或者目标遇到旋转时，Camshift 算法容易失效。为了解决这些问题，P. Hidayatullah［3］提出了三种不同的方法来提高Camshift 算法的鲁棒性，这三种方法都可以解决因目标颜色与背景颜色相近而导致跟踪失败的问题;有人利用鱼眼镜头图像特点来改进Camshift 算法，使得改进后的算法可以有效跟踪鱼眼镜头中物体［4］;Liu 等人［5］利用Camshift 与贪婪跟踪、匹配追踪相结合来对人的脸部进行实时跟踪;Zou 等人［6］提出构建运动模板，将运动信息与颜色直方图相结合，实现快速跟踪。

SIFT(Scale Invariant Feature Transform)是一种图像局部特征的描述子，有很好的旋转不变性和尺度缩放不变性，对3D 视角和光照变化的适应性强，对杂物场景和目标遮挡具有很好的鲁棒性［7］。在MeanShift 跟踪结果的基础上，文献［8］利用SIFT 匹配来寻找SIFT 的匹配点集合，通过计算仿射变换参数来得到MeanShift 最佳跟踪结果。结合颜色信息与SIFT 特征，文献［9］利用MeanShift 自适应算法和EM 框架来进行目标跟踪。本文提出一种Camshift 与SIFT 线性融合的跟踪算法，该方法可以有效解决尺度变化、旋转、目标颜色与背景颜色相近的跟踪情况。

1 Camshift 算法

Camshift 算法是以MeanShift 算法为核心，对图像序列的所有帧进行跟踪，并将前一帧的搜素结果(搜索窗的大小和质心)作为下一次搜索窗的初始值。

具体算法流程如下:

1)将目标图像从RGB 空间转换到HSV 空间，提取H 分量构建颜色直方图。

2)初始化搜索窗口的大小和位置。

3)计算目标区域内的颜色概率分布图。

4)计算窗口的质心:

零阶距为

式中:I(x，y)是概率分布图中(x，y)处的概率值，那么窗口的质心(xc，yc)=(M10/M00，M01/M00)。

5)移动搜索窗的中心到目标区域的质心位置。如果移动距离小于预设阈值或迭代次数大于15，那么该中心就是目标的位置，此位置就为下一帧搜索的起始位置;否则，重新调整窗口大小，并返回步骤4)的计算，直到满足条件为止。

6)计算目标的移动方向与搜索窗大小，并进行下一帧跟踪处理。

2 Camshift 与SIFT 的线性融合

本文提出的算法融合了Camshift 和SIFT。首先利用Camshift 对视频流中的运动物体进行跟踪，得到初始跟踪结果，然后再利用SIFT 进行特征匹配与校准，最后将这两部分的跟踪结果进行线性融合。SIFT 特征匹配与校准的步骤主要有:1)SIFT 特征提取;2)SIFT 特征匹配;3)特征区域的重心转移计算;4)校准Camshift 的跟踪结果;5)将两部分的结果进行线性融合。算法流程图如图1 所示。

图1 融合算法示意图

2.1 SIFT 特征提取

SIFT 是一种检测图像局部特征的算法，在一定程度上既可以对目标的旋转、尺度变化保持不变性，也可以解决颜色干扰、光线变化等问题。SIFT 的提取主要有5 个步骤:

1)构建尺度空间。一个图像的尺度空间定义为一个尺度变换的高斯函数与原图像的卷积，在实现时使用高斯金字塔来表示。为了能够检测到稳定的极值点，人们利用不同尺度的高斯差分核与图像进行卷积，构建高斯尺度空间(DoG)。

2)极值点检测。极值点必须满足在平面图像空间与高斯差分尺度空间都具有极值的点，所以每一个像素点都要与它所有的相邻点进行比较，得出极值点。

3)精确定位关键点。以上得到的极值点并不都是需要的关键点，还要通过拟合三维二次函数来去除一些不满足条件的极值点和边缘点，进而确定最终的关键点。

4)关键点方向分配。为了使得描述子具有旋转不变性，需要利用梯度方向的方法来为每一个关键点分配一个基准方向，这样就可以利用位置、尺度、方向确定一个SIFT 特征区域。

5)生成关键点描述子。最后，通过对关键点周围区域分块，计算块内的梯度直方图，生成向量，为每一个关键点建立一个描述符。

2.2 SIFT 特征匹配

SIFT 特征匹配的过程就是两幅图像中关键点相似性度量的过程，一般采用特征向量的欧氏距离来进行描述。假如目标区域的一个关键点的特征向量为Va，Camshift 跟踪区域的两个关键点的特征向量为Vb，Vc，且Vb与Va的欧式距离最近，Vc与Va次近。如果满足公式(6)，则说明匹配正确，否则排除该匹配点

式中:α 的值定义为0.8。

2.3 特征区域的重心转移计算

在上述过程中实现了目标区域与跟踪区域之间特征点的匹配，这些相匹配的特征点分别为:目标区域的特征点P={(xi，yi)，Vi}，跟踪区域的特征点P'={(x'i，y'i)，V'i}，其中i=1，2，…，N。那么结合目标区域与跟踪区域，特征点的中心是这两个区域特征点相减后的均值，具体公式为

2.4 校准跟踪结果

假设Camshift 跟踪结果为restCS，那么restCS={x0，y0，vRadius，hRadius}，其中(x0，y0)是矩形跟踪区域的中心位置，vRadius 是区域的垂直半径，hRadius 是区域的水平半径。若SIFT 的匹配校正结果为restSIFT，那么

2.5 融合Camshift 和SIFT 的跟踪结果

融合两种算法，得到最终的结果为式(9)所示

式中:α 是权重系数，介于0 ～1 之前，而rest 是最终的跟踪结果。当Camshift 算法中Bhattacharya 系数越大，Camshift 的跟踪效果越好，此时的α 也越大，反之，α 越小。

3 实验结果分析

本次实验是在Intel(R)Core(TM)2.2 GHz 的CPU、2.96 Gbyte 内存计算机上运行的，在Windows7 系统下使用VS2010+OpenCV 编程得到MeanShift、Camshift 和本文算法的跟踪结果图，再用MATLAB 分析跟踪误差，而跟踪误差表示的是目标的估计中心与实际中心之间的距离(用像素表示)，距离越小，跟踪效果越好。本文中选取了3 段视频来进行实验展现。

跟踪效果图(原图为彩图)中，黑色椭圆边框代表的是MeanShift 算法的跟踪结果，红色椭圆边框代表的是Camshift算法的跟踪结果，橘色矩形边框代表的是本文算法的跟踪结果。

当目标尺度发生变化时，3 种算法的跟踪结果和误差分析分别如图2、图3 所示。

图2 目标尺度变化时3 种算法的跟踪效果图

图3 目标尺度变化时3 种算法的跟踪误差分析图

从图2 和图3 中可以看出，在目标运动过程中，目标的尺度发生了变化，此时Camshift 算法与本文算法都比MeanShift算法好;又因为在该视频中，运动背景简单，且目标没有发生复杂运动，所以本文算法与Camshift 算法性能接近。

当目标发生旋转时，3 种算法的跟踪结果和误差分析分别如图4、图5 所示。

图4 目标发生旋转时3 种算法的跟踪效果图

图5 目标发生旋转时3 种算法的跟踪误差分析图

从图4 和图5 中可以看出，当目标发生旋转时，本文的算法性能比Camshift 算法和MeanShift 算法都要好;又因为Camshift 与MeanShift 都是仅基于颜色直方图的跟踪算法，物体旋转时的跟踪效果差，所以二者的性能接近。

当目标颜色与背景颜色相近时，3 种算法的跟踪结果和误差分析分别如图6、图7 所示。

图6 目标颜色与背景颜色相近时3 种算法的跟踪效果图

图7 目标颜色与背景颜色相近时3 种算法的跟踪误差分析图

从图6 和图7 中可以看出，当目标颜色与背景颜色相近时(白色汽车与白色路面的颜色相近)，本文的算法的跟踪结果比Camshift 算法和MeanShift 算法都要好，而此时MeanShift算法性能比Camshift 算法差。

4 总结

均值漂移算法(MeanShift)是基于颜色直方图的跟踪算法，它容易在目标尺度发生变化时跟踪失败。Camshift 算法是对均值漂移算法的一种改进，它可以在目标尺度发生变化时自适应地进行跟踪。但是，当目标出现旋转、颜色与背景颜色相近时，Camshift 算法也容易失效。所以本文提出一种融合算法，该算法结合了Camshift 算法与SIFT 算子。第一个算法用来对运动目标进行初步跟踪，第二个算法是利用SIFT 对初步跟踪结果进行匹配，并进行一定的校准，最后将这两种算法的结果进行线性融合，实现有效跟踪。实验表明该融合算法可以解决旋转、目标颜色与背景颜色相近时的跟踪问题，并可以得到较好的跟踪结果。

［1］张宏志，张金换，岳卉，等.基于CamShift 的目标跟踪算法［J］.计算机工程与设计，2006，27(11):2012－2014.

［2］李睿，刘涛，李明.基于Mean－shift 的粒子滤波算法在遮挡目标跟踪中的应用［J］.科学技术与工程，2008，8(14):3957－3960.

［3］HIDAYATULLAH P，KONIK H. CAMSHIFT improvement on multi－hue and multi－object tracking［C］//Proc. 2011 International Conference on Electrical Engineering and Informatics(ICEEI).［S.l.］:IEEE Press，2011:1－6.

［4］WU Jianhui，ZHANG Guoyun，GUO Longyuan. Study the improved CAMSHIFT algorithm to detect the moving object in fisheye image［C］//Proc. 2013 International Conference on Mechatronic Sciences，Electric Engineering and Computer(MEC).［S.l.］:IEEE Press，2013:1017－1020.

［5］LIU Q，CAI C，NGAN K N，et al. Camshift based real－time multiple faces match tracking［C］//Proc.International Symposium on Intelligent Signal Processing and Communication Systems，2007.［S.l.］:IEEE Press，2007:726－729.

［6］ZOU T，TANG X，SONG B. Improved Camshift tracking algorithm based on silhouette moving detection［C］//Proc. 2011 Third International Conference on Multimedia Information Networking and Security(MINES).［S.l.］:IEEE Press，2011:11－15.

［7］LOWE D G. Distinctive image features from scale－invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91－110.

［8］ZHOU H，YUAN Y，SHI C. Object tracking using SIFT features and mean shift［J］.Computer Vision and Image Understanding，2009，113(3):345－352.

［9］CHEN A，ZHU M，WANG Y，et al. Mean shift tracking combining SIFT［C］//Proc.9th International Conference on Signal Processing，2008.［S.l.］:IEEE Press，2008:1532－1535.

［10］朱胜利. MeanShift 及相关算法在视频跟踪中的研究［D］.杭州:浙江大学，2006.

［11］李睿，刘涛，李明.基于Mean－shift 的粒子滤波算法在遮挡目标跟踪中的应用［J］.科学技术与工程，2008，8(14):3957－3960.

［12］董蓓，谢勤岚，贾茜. 基于Camshift 算法的运动目标实时跟踪系统［J］.现代电子技术，2008，31(19):116－118.

［13］王新红，王晶，田敏，等.基于空间边缘方向直方图的MeanShift跟踪算法［J］.中国图象图形学报，2008，13(3):586－592.