基于CamShift和Kalman组合的改进目标跟踪算法

何 俊,樊卫华,王 冲,周维维

(南京理工大学 自动化学院，南京 210094)

基于CamShift和Kalman组合的改进目标跟踪算法

何 俊,樊卫华,王 冲,周维维

(南京理工大学 自动化学院，南京 210094)

针对应用CamShift算法进行目标跟踪过程中，当目标被严重遮挡、目标被与目标颜色相近的背景干扰时易丢失跟踪目标的问题，提出了一种基于CamShift和Kalman滤波组合的改进跟踪算法；为克服目标因严重遮挡而丢失的缺陷，利用自适应算法改进了传统的CamShift算法，扩大了搜索窗口，使运动目标位于搜索窗口内；为解决目标因颜色相近背景干扰而丢失的问题，改善跟踪准确率，利用卡尔曼滤波预测目标运动空间位置，作为下一帧搜索窗口的质心坐标；基于上述改进，利用C++语言，研发了改进的CamShift目标跟踪软件模块，给出了该模块的算法流程；实验结果表明，改进后的目标跟踪算法能有效地克服传统CamShift算法的缺陷，大大提高运动目标跟踪的准确性；所提的算法可以应用于运动小车跟踪，人脸识别等领域。

目标跟踪；CamShift算法；卡尔曼滤波

0 引言

近年来，随着机器人视觉技术的不断发展，对运动目标进行有效地识别与跟踪已经成为机器人视觉领域的重要研究方向之一。对运动目标进行实时跟踪，不仅可以获取运动目标的状态信息及运动轨迹，还可以为目标的运动分析提供数据来源，在多智能体小车编队控制中有着重要的应用[1]。在多智能体小车编队控制实验中，位于实验场地上方的广角摄像头将采集的实验场地的全局图像传输给PC端，然后利用图像控制软件解析出小车的状态信息进行后续的编队控制。但是，如果获取小车的状态信息是通过处理整幅图像获得的，这样计算量大，实时性差。因而跟踪算法的引进对多智能体小车编队控制的实时性起到关键的作用。

近年来，人们提出了许多跟踪算法，如基于区域的跟踪、基于活动轮廓的跟踪、基于模型的跟踪、基于特征的跟踪方法[2]。基于区域的跟踪方法[3]是通过相邻两帧运动目标的位置变化来完成区域跟踪的，适合多目标跟踪，在运动目标未发生形变或未被遮挡时，能实现对目标准确地跟踪，但是这种跟踪方法需要在整个图像中进行搜索，实时性比较差，同时当运动目标发生形变或被遮挡时，容易跟踪失败。基于活动轮廓的跟踪方法[4]是将运动目标的边界轮廓作为跟踪模板，实时性较好，当目标被部分遮挡时能进行连续跟踪，但是这种方法对初始轮廓比较敏感，同时轮廓的更新也比较困难。基于模型的跟踪方法[5]是对运动目标的外形特征建立2D或3D模型，该方法在运动目标姿态发生变化或被部分遮挡时能实现有效地跟踪，具有较强的鲁棒性，但是建立运动目标的准确模型比较困难，同时在模型的匹配中需要消耗大量的时间，实时性比较差。基于特征的跟踪方法[6]通过提取运动目标某些不变的特征，然后利用相关的跟踪算法实现对目标有效地跟踪，常用的跟踪算法有MeanShift算法，MeanShift算法是一种基于迭代收敛到概率最大的局部极大的非参数估计算法，目前已经被广泛地应用到目标跟踪领域[7]。该算法以目标颜色直方图为搜索特征，对噪声有较强的鲁棒性，同时其寻优过程收敛速度快，使得该算法具有较好实时性。但是，MeanShift算法固定不变的核函数影响了跟踪的准确性，当运动目标发生形变时，会导致运动目标定位不准确。CamShift算法[8]是在MeanShift算法的基础上，通过自动调整核函数窗宽来适应跟踪目标在图像中的实际大小，从而解决了目标大小变化的问题。同时，为了解决目标跟踪过程中噪声的干扰，人们充分利用目标运动状态信息获取目标更加精确的位置估计，于是引入了各种滤波算法，如卡尔曼滤波、粒子滤波等。

在多智能体小车编队控制实验中，采用了传统的CamShift算法和Kalman位置预测相结合的跟踪方法。此时，以CamShift算法输出的搜索窗口的大小作为下一帧的搜索窗口的大小，以CamShift算法输出的搜索窗口中心位置作为Kalman滤波的观测值，将Kalman预测出的小车最优位置作为下一帧中搜索窗口的中心。但是，当小车被与小车颜色相近的背景干扰时，此时经传统的CamShift算法输出来的搜索窗口变大，如果仍以传统CamShift算法输出的搜索窗口中心位置作为Kalman滤波的观测值，会使Kalman预测出的小车最优位置不准确。本文采用改进的Kalman位置预测，以Kalman预测值作为Kalman滤波的观测值，将Kalman预测出的小车最优位置作为下一帧中搜索窗口的质心，这样就能克服小车被与小车颜色相近的背景干扰带来的跟踪丢失问题。当小车被严重遮挡时，经传统CamShift算法得到的搜索窗口变小，可能导致小车跟踪失败。本文采用自适应地扩大搜索窗口的改进CamShift算法，即根据CamShift算法输出的搜索窗口失真的帧数来自适应地扩大搜索窗口大小，并将改进CamShift算法与改进的Kalman位置预测相结合，最终能实现小车被严重遮挡情况下的准确跟踪。实验表明，该组合跟踪算法能提高跟踪成功率。

1 传统的CamShift跟踪算法

CamShift算法是连续自适应均值漂移算法。该算法是基于颜色直方图为特征的跟踪算法，但RGB颜色空间对光照亮度变化比较敏感，为了减少光照亮度变化对小车跟踪效果的影响，CamShift算法将图像从RGB颜色空间转换为HSV颜色空间，提取跟踪小车H(hue)分量，并建立小车颜色直方图模型，将颜色直方图归一化到0～255范围内，然后将原始图像的像素用直方图中对应像素的统计值代替，即可得到反向投影图，进行后续处理。CamShift算法的基本流程图如图1。

图1 传统CamShift跟踪算法框图

CamShift算法过程如下：

1)根据反向投影图在跟踪搜索窗口内进行质心查找。

设(x,y)为搜索窗口中的像素位置，I(x,y)为反向投影图中(x,y)处的像素值，分别计算：

零阶矩：

x的一阶矩:

y的一阶矩：

计算搜索窗口的质心即目标的质心：

2) 重复1)，直到收敛，即相邻搜索窗口的质心变化小于给定的阈值或者迭代次数达到最大值；

3) 将上一帧图像的搜索窗口大小、质心作为下一帧的搜索窗口的大小和质心，从而实现对目标的连续跟踪。

2 改进的CamShift算法

在跟踪小车的过程中，当小车被严重遮挡时，由于跟踪小车只有较小部分在搜索窗口之内，此时小车的颜色概率分布值很小，经传统CamShift算法得到的搜索窗口就会严重变小，导致小车跟踪丢失。在这种情况下，即使跟踪小车再次出现在帧图像中，还是无法跟踪上小车，这就表明传统CamShift算法失效。针对搜索窗口严重缩小的问题，本文采用扩展搜索窗口的CamShift与改进的Kalman相结合的算法。

当跟踪小车因被严重遮挡而暂时丢失时，由于丢失时间较短，跟踪小车仍在丢失位置的附近区域，此时适当的增大搜索窗口的搜索范围和预测小车运动位置，就可以找到小车，从而重新跟上跟踪小车。在改进的CamShift算法中，设定一个与跟踪小车相仿的标准矩形搜索窗口，窗口的像素面积大小定义为standard_window，一个传统CamShift算法的输入搜索窗口，窗口的像素面积大小定义为search_window，一个经过传统CamShift算法计算得到的跟踪窗口为输出搜索窗口，窗口的像素面积大小定义为result_window，将输出窗口与标准窗口的比值定义为缩放比例K。首先需要判断运动小车是否出现被严重遮挡的情况。若缩放比例K<0.3(阈值视情况而定)，此时认为运动小车出现被严重遮挡的情况。此时用扩展搜索窗口大小来作为下一帧CamShift算法的小车输入搜索窗口大小，利用改进的kalman对搜索窗口质心位置的预测作为下一帧CamShift算法的小车输入搜索窗口的质心，这样进行迭代就可以实现在小车被严重遮挡时的对运动小车的连续跟踪。扩展搜索窗口调整流程图如图2。

图2 扩展搜索窗口调整流程图

令lost_frame为视频序列中连续跟踪丢失的帧数，search_window像素面积大小的调整方式如下：

3 运动小车的Kalman滤波状态估计与改进CamShift算法的结合

CamShift算法是以小车的颜色直方图为特征进行小车跟踪，当小车为纯色时，CamShift算法的跟踪效果较好。但是当运动小车被与小车颜色相近的背景干扰时，搜索窗口会将干扰物包含在内，导致搜索窗口变大，甚至出现跟踪小车丢失的情况。当跟踪小车被严重遮挡时，通过上一帧图像计算出的搜索窗口的质心与小车质心相差甚远，从而导致搜索窗口偏离跟踪小车。为了解决以上情况，需要通过小车之前的状态信息预测小车当前的状态信息。卡尔曼滤波器是一种最优化自回归数据处理方法，它能实现实时运动状态的估计和预测功能。

3.1 卡尔曼滤波

图3 CamShift和Kalman组合的改进目标跟踪算法

卡尔曼滤波是以最小均方误差为估计的最优递推估计算法。其基本思想：采用信号和噪声的状态空间模型，利用系统当前时刻的状态观测值和前一时刻状态的估计值来更新对状态的估计，求出当前时刻的状态估计值[9]。

状态预测公式：

X(k|k-1)=AX(k-1|k-1)+Bu(K)

误差协方差预测公式：

P(k|k-1)=AP(k-1|k-1)A′+Q

状态校正公式：

X(k|k)=X(k|k-1)+Kg(k)

(Z(K)-HX(K|K-1))

卡尔曼增益：

误差协方差校正公式：

P(k|k)=(I-Kg(k))P(k-1|k-1)

式中，X(k-1|k-1)为k-1时刻小车位置最优状态，X(k|k-1)为k时刻的小车位置预测结果，P(k-1|k-1)和P(k|k-1)分别为相对X(k-1|k-1)和X(k|k-1)的误差协方差，协方差Q和R分别为正态分布的系统过程和测量噪声。

3.2 基于卡尔曼滤波的运动小车状态估计

定义小车的状态向量Xk|k=[xk|k,yk|k,vxk|k,vyk|k]T，观测向量Zk|k=(xk|k,yk|k)T，其中，xk|k，yk|k表示小车质心在图像像素坐标系中的位置，vxk|k，vyk|k为小车在x，y方向上的速度。由于相邻两帧图像相隔时间较短，假设小车在相邻两帧图像的时间T内是匀速运动的，则系统的状态转移矩阵和观测矩阵分别为：

系统的运动噪声协方差矩阵，观测噪声协方差矩阵和t=T(图像的采样周期)时刻的误差协方差分别为：

在多智能体小车编队控制实验中，初始化滤波器，选择起始窗口的质心和大小作为CamShift算法的输入，同时根据搜索窗口的位置坐标初始化状态向量X(0|0)。在正常情况下的跟踪过程中，在k时刻，把上一时刻小车的最优估计X(k-1|k-1)代入式(3.1)得到最优估计X(k|k-1)，并以CamShift算法输出的小车质心位置作为kalman观测值Z(K)，用Z(K)来修正X(k|k-1)得到k时刻小车质心的最优估计X(k|k)。这样，就实现了对运动小车最优位置的估计。但是，当小车被遮挡、小车被与小车颜色相近的背景干扰时，利用CamShift算法得到的小车质心位置是不准确的，此时将小车质心位置作为Kalman滤波器的观测值去更新Kalman滤波器，得到的下一帧中小车的预设值时不可信的。为了提高预测的准确性，此时直接将Kalman预测值作为Kalman滤波器的观测值去更新Kalman滤波器，将Kalman预测出的小车最优位置作为下一帧中搜索窗口的质心,这样就能实现对运动小车最优位置的估计。CamShift和Kalman组合的改进目标跟踪算法如图3。

4 实验结果及分析

实验硬件系统为Intel(R) Core(TM) i3-6100 3.7GHz的CPU、8GB内存；软件系统有Window10操作系统、Visual Studio 2012和开源的计算机视觉库Opencv2.4.9。

由图4和图5可知，当小车附近有相似物时，利用传统的Camshift与kalman跟踪算法，跟踪窗口会变大并包含类似物，可能导致跟踪失败。采用改进的CamShift和Kalman组合的目标跟踪算法能有效地跟踪小车。

图4 传统的Camshift跟踪算法在小车附近有类似物时跟踪效果图

图5 改进的CamShift和Kalman组合的目标跟踪算法在小车附近有类似物时跟踪效果图

由图6和图7可知，当小车被严重遮挡时，利用传统的Camshift跟踪算法，跟踪窗口会变小，导致跟踪失败。采用改进的CamShift和Kalman组合的目标跟踪算法，通过扩到索搜窗口和卡尔曼算法预测下一时刻小车位置，能有效地跟踪小车。

图6 传统的Camshift跟踪算法在小车被遮挡时跟踪效果图

图7 改进的CamShift和Kalman组合的目标跟踪算法在小车被遮挡时跟踪效果图

本文对传统的Camshift跟踪算法和改进的Camshift与kalman跟踪算法进行了20次实验，算法识别正确率见表1。

表1 算法识别正确率

5 结论

本文针对小车被严重遮挡、小车被与小车颜色相近的背景干扰时小车跟踪丢失的情况，提出了一种改进的CamShift和Kalman组合的目标跟踪算法。实验表明，改进的CamShift和Kalman组合的目标跟踪算法能实现当小车被严重遮挡、小车被与小车颜色相近的背景干扰时的连续跟踪。但是，Camshift算法的小车跟踪要求小车具有特定的颜色，当背景存在大面积的干扰物时，跟踪效果一般。因此，利用小车的多种特征信息来提高对小车的跟踪的成功率，这是需要进一步研究的工作。

[1] 陈汗青, 万艳玲, 王国刚. 数字图像处理技术研究进展[J]. 工业控制计算机. 2013(1):72-74.

[2]Deng Y, Wu L, He Y. A Novel Approach to Analyzing Object Motion Behavior[A]. Eighth International Conference on Intelligent Information Hiding and Multimedia Signal Processing[C]. IEEE Computer Society, 2012:395-398.

[3]Badenas J, Sanchiz J M, Pla F. Motion-based segmentation and region tracking in image sequences [J]. Pattern Recognition, 2001, 34(3):661-670.

[4]Cuenca C, González E, Trujillo A, et al. Fast and accurate circle tracking using active contour models[J]. Journal of Real-Time Image Processing, 2015(October 2015):1-10.

[5]Marmaroli P, Odobez J M, Falourd X, et al. A bimodal sound source model for vehicle tracking in traffic monitoring[A].Signal Processing Conference, 2011 19th European[C]. IEEE, 2011: 1327-1331.

[6]Prioletti A, Møgelmose A, Grisleri P, et al. Part-based pedestrian detection and feature-based tracking for driver assistance: real-time, robust algorithms, and evaluation[J]. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(3): 1346-1359.

[7]Tu J, Tao H, Huang T. Online updating appearance generative mixture model for meanshift tracking [J]. Machine Vision and Applications, 2009, 20(3):163-173.

[8]Exner D, Bruns E, Kurz D, et al. Fast and robust CAMShift tracking[A]. IEEE Computer Society Conference on Computer Vision & Pattern Recognition-workshops[C]. IEEE, 2010:9-16.

[9]Zhou S K, Chellappa R, Moghaddam B. Visual tracking and recognition using appearance-adaptive models in particle filters[J]. IEEE Transactions on Image Processing, 2004, 13(11):1491-506.

[10]Sinopoli B, Schenato L, Franceschetti M, et al. Kalman filtering with intermittent observation [J]. IEEE transactions on Automatic Control, 2004, 49(9): 1453-1464.

Improved CamShift Algorithm Combined with Kalman Filter for Moving Target Tracking

He Jun，Fan Weihua，Wang Chong，Zhou Weiwei

(School of Automation, Nanjing University of Science and Technology, Nanjing 210094，China)

A new target tracking algorithm is proposed that combines the modified CamShift algorithm with Kalman filter, aiming at several problems occurred in target tracking, such as the moving target being covered, and the target being interfered by similar background. In order to overcome the shortages of target loss due to the moving target being covered, the search window of the traditional CamShift algorithm is improved and the size of searching window is adjusted adaptively, so that the moving target is located in the search window. When the moving target is interfered by similar background, the target is lost. In order to increase the tracking accuracy, Kalman filter is used for estimating the position of the moving target which is used as the center location of search window in the next frame. An improved CamShift target tracking software module is developed using C ++ language, and the algorithm flow of the module is given. The experimental results show that the proposed algorithm can overcome the default of the traditional CamShift algorithm and improve the performance and accuracy of target tracking and location. This algorithm can be applied to the field of moving car tracking, face recognition etc.

object tracking; CamShift algorithm; Kalman filter

2016-10-19；

2016-11-21。

国家自然科学基金项目(61673219)；江苏省“六大人才高峰”项目(XNYQC-CXTD-001)；天津市科技重大专项与工程项目(15ZXZNGX00250)。

何 俊(1990-)，男，江苏省泰兴市人，硕士研究生，主要从事多智能体编队控制方向的研究。

1671-4598(2017)03-0209-04DOI：10.16526/j.cnki.11-4762/tp

TP

A