闫钧华，陈少华，艾淑芳，李大雷，段 贺

(1. 南京航空航天大学 航天学院，南京 210016；2. 光电控制技术重点实验室，洛阳 471009；3. 中国电子科技集团公司 第二十八研究所，南京 210007)

基于Kalman预测器的改进的CAMShift目标跟踪

闫钧华1,2，陈少华3，艾淑芳2，李大雷2，段 贺1

(1. 南京航空航天大学 航天学院，南京 210016；2. 光电控制技术重点实验室，洛阳 471009；3. 中国电子科技集团公司 第二十八研究所，南京 210007)

CAMShift目标跟踪算法遇到目标被遮挡时容易陷入局部最大值，对快速运动目标容易跟踪失败，且无法从失败中复原。针对该问题，利用Kalman预测器改进CAMShift算法。首先利用Kalman预测器预测下帧图像中目标的位置，以此位置为中心确定CAMShift算法进行目标跟踪的搜索区域；然后利用目标匹配时的Bhattacharyya系数及目标大小来判断目标是否被遮挡以及被遮挡的程度。如果没有被遮挡，则用CAMShift算法得到的目标位置更新Kalman预测器中参数；如果遮挡不严重，则用Kalman预测器的预测值作为目标的位置和大小，且用该组值更新Kalman预测器中参数；如果遮挡非常严重，则用Kalman预测器的预测值作为目标当前位置，目标大小为固定值，用该组值更新Kalman预测器中参数。实验结果表明，改进算法能够准确地跟踪被遮挡目标和快速运动目标。

目标跟踪；Kalman预测器；目标跟踪算法；遮挡；搜索区域

运动目标跟踪在军事、工业生产、日常生活中都有着广泛的应用，如军事目标跟踪[1]、交通路口监控等等。Bradski[2]把MeanShift算法应用在连续序列图像的脸部跟踪中，并称其为CAMShift算法，其结果表明此算法对不规则目标运动、图像噪声、虚假目标、光线变化都有较好的适应性，而且算法的实时性很好。CAMShift[3]是一种有效的统计迭代算法，它在目标表示上比传统的均值漂移算法更加简单，且便于进行模型的组合。经典的CAMShift算法以颜色直方图为目标表示模型，通过迭代求解加权图的质心来跟踪目标，在背景简单的情况下能够取得较好的跟踪效果，但是遇到噪声干扰或目标被遮挡等问题时容易陷入局部最大值，同时对快速运动目标往往跟踪失败，且无法从失败中复原[4]。

本文基于Kalman预测器对CAMShift跟踪算法做出改进[5]，利用Kalman预测器预测下帧图像中目标的位置，以此位置为中心确定CAMShift算法进行目标跟踪的搜索区域[6]。利用目标匹配时的 Bhattacharyya系数及目标大小来判断目标是否被遮挡，针对目标被遮挡的程度采取相应的处理方法。

1 Camshift跟踪

Bradski在 MeanShift算法的基础上提出了CAMShift算法，该算法自动调节窗口大小以适应被跟踪目标由于形变所造成的在图像中大小的变化，从而可以有效的解决目标形变问题。CAMShift算法运算步骤如下：

① 读取一帧图像（非HSV转换成HSV的颜色空间），提取HSV三通道图像的Hue通道。

② 选择目标搜索窗。

③ 计算这个搜索区域的颜色直方图，归一化得到概率分布图I(x,y)，并将它作为查找表，将Hue通道图像上每一个像素点用它的像素值所对应的概率代替，得到概率投影图。

④ 在概率投影图上，根据搜索窗的大小，中心位置，计算搜索窗的质心位置(xc,yc)

⑤ 移动搜索窗的中心位置到质心位置。

⑥ 判断中心位置是否收敛，如果不收敛，则返回④，根据新的搜索窗继续计算质心位置，直到收敛。如果收敛则根据轴向得到目标椭圆区域大小(w, l)，此时区域的中心位置和大小就是目标在当前帧中的位置和大小，返回①，重新得到一帧新图像，并利用当前所得到的中心位置和区域大小进入③，在新的图像帧进行搜索。

经典CAMShift算法单独用于目标跟踪存在局限性，因此基于Kalman预测器改进CAMShift算法，利用Kalman预测器预测目标的位置，提高跟踪运动目标的速度。

2 Kalman预测器

Kalman预测器是一个在误差协方差最小准则下的最优估计方法，计算量小，实时性高，能利用实际的运动参数不断修正未来运动状态的估计值，提高估计精度，兼顾实时性和稳健性[7]。场景中的目标在每一帧图像中的位置构成了目标运动的轨迹，引入Kalman预测器的目的就是根据当前帧中目标位置点的信息预测下一帧中目标的可能位置，且 CAMShift跟踪算法需要设定目标搜索区域的位置和大小，所以Kalman预测器中的状态变量Xk和观测值Zk分别为：

式中，xk、yk表示目标的质心坐标，wik、hk表示目标椭圆区域外切矩形的宽和高，vx,k、vy,k、vw,k、vh,k分别表示k时刻四者的变化速度，ax,k、ay,k、aw,k、ah,k分别表示k时刻四者的加速度。

Kalman预测器的状态方程：

式中，Xk是一个12×1维向量，表示在离散时刻k的状态向量，是不可观测的；Ak,k-1描述从tk-1时刻到tk时刻的状态转移矩阵，12×12维。

式中，Δt表示连续两帧图像间的间隔，本文取1帧；Wk-1是tk-1时刻状态的随机干扰，12×1维向量，本文采用互不相关的零均值标准正态白噪声序列。

Kalman预测器的观测方程：

式中，Hk是tk时刻的观测矩阵，4×12维；Vk是tk时刻的观测噪声向量4×1维，本文采用互不相关的零均值标准正态白噪声序列。

Kalman预测器状态更新方程为：

Kalman预测器状态预测方程为：

Kk为Kalman预测器的增益矩阵：

Kalman预测器预测了目标的位置，有效地克服了目标运动速度快、少量相近背景干扰、目标被部分遮挡所导致的跟踪失败。

3 基于Kalman预测器的改进的CAMShift目标跟踪算法

CAMShift跟踪算法的当前搜索窗口是根据上一步得到的结果自适应的进行调整，故其可以自适应的跟踪动态变形的目标。当目标快速运动时，会导致目标与当前搜索窗口没有连接，造成目标丢失。当目标被较严重的遮挡或完全遮挡时，CAMShift跟踪算法得到的目标位置点是不准确的，会造成跟踪错误目标。因为当前搜索窗口中不含有再次出现的真实目标，所以当真实目标再次出现时，使用CAMShift跟踪算法跟踪不到真实目标。

针对于此，本文基于Kalman预测器改进CAMShift目标跟踪算法，对每帧图像得到的当前搜索窗口的位置进行预测和修正，从而能够跟踪快速运动的目标，且当目标发生大面积的遮挡时能够使用目标的预测值代替 CAMShift跟踪算法计算得到的目标跟踪位置，直至目标再次完全出现。基于Kalman预测器的改进的CAMShift目标跟踪算法框图如图1所示。

图1 基于Kalman预测器的改进的CAMShift目标跟踪算法框图Fig.1 Block diagram of the improved CAMShift target tracking algorithm based on Kalman predictor

3.1 目标遮挡的判断[8]

CAMShift目标跟踪算法是基于直方图的跟踪算法。直方图作为一种统计特性，其本身对目标的旋转和形变不敏感，这使得CAMShift目标跟踪算法本身对目标的背景变化以及部分遮挡有较好的鲁棒性。当目标被遮挡的面积较大时，CAMShift目标跟踪算法就会失效。因为目标点少了，CAMShift跟踪算法根据目标点计算“质心”时，对质心的作用变小了，所以得到的质心值不再向目标偏移。本文基于 Kalman预测器改进CAMShift目标跟踪算法，需要对目标的遮挡情况作出判断，判断目标何时开始被遮挡以及被遮挡的程度如何。Bhattacharyya距离d(y)非常适合衡量两个直方图之间的相似程度，其值越小表示两个直方图越匹配；CAMShift跟踪算法计算得到的目标面积是当前目标的大小。据此本文采用Bhattacharyya距离以及CAMShift跟踪算法计算得到的目标面积判断目标何时开始被遮挡以及被遮挡的程度。

① 判断目标何时开始被遮挡

Bhattacharyya系数ρ(y)：

式中，pu(y)为目标模型的颜色直方图，qu(y)为跟踪图像中当前目标子图的颜色直方图。

Bhattacharyya距离d(y)：

设定一个阈值Tb，如果满足d(y)＜Tb，则说明目标没有被遮挡。如果满足d(y)≥Tb，则说明目标开始被遮挡。本文中Tb取0.4。

② 判断目标被遮挡的程度

CAMShift跟踪算法计算得到的目标椭圆区域大小(w, l)为目标面积area，这是当前跟踪图像中目标的大小。如果area＞min area，则说明遮挡不严重；如果满足area＜min area，则说明遮挡非常严重。本文中min area是这样确定的：对目标没有被遮挡前的20帧图像，利用CAMShift跟踪算法计算得到目标的面积 area，从中选取一个最小值，这个最小值的 40﹪即为 min area。如果目标运动速度快，可以增大目标没有被遮挡前的图像帧数以确定mina rea。

3.2 基于Kalman预测器的改进的CAMShift目标跟踪算法流程图

本文针对目标快速运动，目标被遮挡这两类问题对CAMShift算法进行了相应的改进。对于目标被遮挡问题，采用Bhattacharyya距离以及CAMShift跟踪算法计算得到的目标面积判断目标何时开始被遮挡以及被遮挡的程度；基于Kalman预测器对目标快速运动以及被遮挡过程中的目标位置进行预测[9-10]。具体的流程图如图2所示。

图2 基于Kalman预测器的改进的CAMShift目标跟踪算法流程图Fig.2 Flowchart of the improved CAMShift target tracking algorithm based on Kalman predictor

基于Kalman预测器的改进的CAMShift目标跟踪算法流程图针对目标的质心位置和目标被遮挡进行预测和判断。由CAMShift跟踪算法根据相应的目标颜色模型计算得到目标的质心位置，根据跟踪的结果判断目标是否被遮挡。首先根据目标的质心位置和目标大小得到目标椭圆区域，然后计算目标模型的颜色直方图与目标椭圆区域的当前目标子图的颜色直方图两者的Bhattacharyya距离。据此判断目标是否被遮挡，如果d(y)＜Tb，则说明目标没有被遮挡。利用CAMShift算法得到的目标位置更新Kalman预测器，同时预测下一帧的目标位置和大小。如果d(y)≥Tb，则说明目标开始被遮挡，此时不利用CAMShift算法得到的目标位置更新Kalman预测器，而将Kalman预测器根据上一帧图像预测得到的目标位置和大小作为当前帧的目标位置和大小，同时预测下一帧的目标位置和大小。当已经判断目标被遮挡时，需进一步判断目标被遮挡的程度。根据 CAMShift跟踪算法计算得到的当前跟踪图像中目标的大小area判断目标被遮挡的程度，如果area＞min area，则说明遮挡不严重；此时将当前跟踪图像中的目标位置和大小记录到lastrect（目标椭圆区域外切矩形的宽和高分别为lastrect.width 和lastrect.height），同时将Kalman预测器根据上一帧图像预测得到的目标位置和大小作为观测值 Zk，修正 Kalman预测器的参数，再预测下一帧目标的位置和大小。如果area＜min area，则说明遮挡非常严重，此时Kalman预测器中的观测值Zk中wik=lastrect.width，hk=lastrect.height，目标的质心位置(xk, yk)为 Kalman预测器根据上一帧图像预测得到的目标位置，修正Kalman预测器的参数，再预测下一帧目标的位置和大小。在此过程中需要判断目标连续被严重遮挡的帧数累加值 k是否已经达到极限K0，如果k＜K0，则说明虽然目标被遮挡，但是仍然在可以接受的范围内，跟踪继续；如果k＞K0，则说明目标连续被严重遮挡的时间非常长，可能已经错误跟踪或者丢失目标，则终止跟踪。

4 实验结果

本文实验源程序在VC++6.0环境下开发，针对目标被遮挡、目标快速运动进行实验。

4.1 目标被遮挡实验

① 经典的CAMShift跟踪算法

实验结果如图3所示。从实验中可以看到CAMShift跟踪算法可以抗部分遮挡，当目标被完全遮挡时不能持续跟踪目标。当目标再次出现时，如果目标在上次消失的地方出现，则能再次跟上目标（如图(a)所示）；如果目标从其它地方再次出现，则不能再次跟踪目标(如图(b)所示)。这主要是由于CAMShift跟踪算法容易陷入局部极大值中，只能搜索到与搜索区有交集的目标。由于经典CAMShift算法的搜索区域在目标消失之后会变得非常小，只能在小的搜索区中搜索是否有目标出现，当目标从其它地方出现时，目标不在该搜索区域中，故不能搜索到目标。只有当目标再次出现在搜索区域中，才能再次跟上目标。

图3 目标被遮挡时经典CAMShift算法目标跟踪效果图Fig.3 Effect diagram of the classic CAMShift target tracking algorithm with targets occluded

② 基于Kalman预测器的改进的CAMShift目标跟踪算法

实验结果如图4所示，其中图4(a)所示实验针对目标静止时被遮挡，图4(b)所示实验针对目标运动时被遮挡。针对(a)的情况，Kalman预测器得到的参数中目标的位置基本不变，而CAMShift算法根据当前的位置得到的目标大小如果变化较大或 Bhattacharyya距离 d(y)≥Tb，则说明已经发生了遮挡，此时更新Kalman预测器，同时将Kalman的预测值作为搜索窗口的位置。针对(b)的情况，当目标进入的较多时，则其结果使用Kalman预测值替代。在目标被完全遮挡的过程中，CAMShift算法一直在运算，但是由于其 Bhattacharyya距离大于0.4及目标面积非常小，此时使用Kalman的预测值作为结果值，直到目标从右边再次出现时。当目标出现到了一半时，Bhattacharyya距离小于0.4以及目标的面积已经大于阈值，则使用CAMShift的跟踪结果作为目标最终的位置。在目标被遮挡时，如果连续几帧出现CAMShift的目标面积小于最小面积min area，则使用固定大小的搜索区域和固定的目标大小。

从实验中可以看出，在目标被遮挡时，经典的CAMShift算法对于遮挡和非遮挡同样处理，因此目标被遮挡时的跟踪效果不好；改进的CAMShift算法结合了Kalman预测器，可以有效地判断目标何时开始被遮挡以及被遮挡的程度，适当地扩大目标的搜索窗口及用 Kalman的预测值来确定搜索窗口的位置等，保证目标再次出现时能够很快地被捕捉到。

图4 目标被遮挡时改进的CAMShift算法目标跟踪效果图Fig. 4 Effect diagram of target tracking with the improved CAMShift algorithm when the target is occluded

4.2 目标快速运动时被遮挡实验

实验结果如图 5所示：当汽车快速运动并且被路灯遮挡时，基于Kalman预测器的改进的CAMShift目标跟踪算法能够准确有效地跟踪目标。算法针对经典CAMShift跟踪算法的局部最大值的缺点，引入了Kalman预测器进行改进。Kalman预测器利用目标运动的规律很好地预测出下一帧目标的搜索区域，在目标被遮挡时仍然能够准确地跟踪目标。

图5 目标快速运动时被遮挡改进的CAMShift算法目标跟踪效果图Fig.5 Effect diagram of target tracking with the improved CAMShift algorithm when the target is moving fast and occluded

5 结 论

本文针对目标帧间位移过大时导致目标在搜索区域内消失的问题，利用Kalman预测器预测下帧图像中目标的位置，以此位置为中心确定搜索区域，采用CAMShift算法进行目标跟踪搜索。利用目标匹配时的Bhattacharyya系数及目标大小来判断目标是否被遮挡：如果没有被遮挡，则将CAMShift算法得到的目标位置作为测量值代入Kalman预测器中更新参数；如果遮挡不严重，则用Kalman预测器的预测值作为目标的位置和大小，且将该组值作为测量值代入Kalman预测器中更新参数；如果遮挡非常严重，则用Kalman预测器的预测值作为目标当前位置，目标大小为固定值，将该组值作为测量值代入Kalman预测器中更新参数。实验结果表明，基于Kalman预测器的改进的CAMShift目标跟踪算法能够准确地跟踪被遮挡目标。

[1] 曾伟，朱桂斌，唐丁丁. 一种基于边缘特征的地面军事目标相关跟踪方法[J]. 通信对抗，2009(4)：14-17.

ZENG Wei, ZHU Gui-bin, TANG Ding-ding.A correlation tracking method based on edge feature of ground military target[J]. Communication Countermeasures, 2009(4): 14-17. [2] Bradski G R. Real-time face and object tracking as a component of a perceptual user interface[C]//Proceeding of IEEE Workshop on Applications of Computer Vision，Princeton,NJ,USA,Oct 19-21,1998.Washington D C,USA：IEEE Computer Society，1998：214-219.

[3] Bradski G R. Computer vision face tracking for use in a perceptual user interface[J]. Intel Technology Journal (51535-864X), 1998, 2(2): 1-15.

[4] 邸男，朱明. 一种复杂背景下的实时目标跟踪算法[J].中国图象图形学报，2009，13(9)：1758-1765.

DI Nan, ZHU Ming. An algorithm for real-time tracking target in complex environment[J]. Journal of Image and Graphics, 2009, 13(9): 1758-1765.

[5] Wang Zhaowen, Yang Xiaokang, Xu Yi, Yu Songyu. CamShift guided particle filter for visual tracking[J]. Pattern Recognition Letters, 2009, 30(4): 407-413.

[6] 牛春峰，刘世平，王中原. 制导炮弹飞行姿态的卡尔曼滤波估计方法[J]. 中国惯性技术学报，2012，20(5)：510-514.

NIU Chun-feng, LIU Shi-ping, WANG Zhong-yuan.Approach of Kalman filtering estimation of guided projectile attitude[J].Journal of Chinese Inertial Technology, 2012, 20(5): 510-514.

[7] Ruiming Liu, Xuelong Li, Lei Han, Jiao Meng. Track infrared point targets based on projection coefficient templates and non-linear correlation combined with Kalman prediction[J]. Infrared Physics & Technology, 2013, 57(3): 68-75.

[8] 储珺，杜立辉，汪凌峰，潘春洪. 基于局部背景感知的目标跟踪[J]. 自动化学报，2012，38(6)：1985-1995.

CHU Jun, DU Li-hui, WANG Ling-feng, PAN Chunhong.Local background-aware target tracking[J].Acta Automatica Sinica, 2012, 38(6): 1985-1995.

[9] Karavasilis V, Nikou C, Likas A. Visual tracking using the Earth mover's distance between Gaussian mixtures and Kalman filtering[J]. Image and Vision Computing, 2011, 29(4): 295-305.

[10] Mazinan A H, Amir-Latifi A. Applying mean shift, motion information and Kalman filtering approaches to object tracking[J]. ISA Transactions, 2012, 51(5): 485- 497.

Target tracking with improved CAMShift based on Kalman predictor

YAN Jun-hua1,2, CHEN Shao-hua3, AI Shu-fang2, LI Da-lei2, DUAN He1

(1. College of Astronautics, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China; 2. Science and Technology on Electro-optic Control Laboratory, Luoyang 471009, China; 3. The 28th Research Institute of China Electronics Technology Group Corporation, Nanjing 210007, China )

CAMShift(Continuously Adaptive Mean Shift) target tracking algorithm is liable to fall into a local maxima when the target is occluded, and is prone to failure when the targets move fast, and can not be recovered from the failure.To solve this problem, the CAMShif algorithm is improved by using Kalman predictor.First, the position of the target in the next frame image is predicted by using the Kalman predictor and this position is used as the center to determine the searching area of CAMShift target tracking algorithm. Then the Bhattacharyya coefficient of target matching and the size of the target are utilized to determine whether the target is occluded and the degree of occlusion.If not occluded, the parameters of Kalman predictor are updated by the position of the target with CAMShift algorithm.If the occlusion is not serious, the current location and size of the target are determined by the predictive values of Kalman predictor, and this set of values are used to update the parameters of Kalman predictor.If the occlusion is very serious, the current location is determined by the predictive values of the Kalman predictor and the target size is a fixed value, then this set of values are used to update the parameters of Kalman predictor.The experimental results show that the improved algorithm is able to accurately track the occluded and/or fast moving targets.

target tracking; Kalman predictor; target tracking algorithm; occlusion; searching area

闫钧华（1972—），女，副教授，光电控制技术重点实验室客座研究人员，从事多源信息融合、目标检测跟踪与识别研究。E-mail：yjh9758@126.com

1005-6734(2014)04-0536-07

10.13695/j.cnki.12-1222/o3.2014.04.021

TP391. 4

A

2014-03-14；

2014-07-17

光电控制技术重点实验室和航空科学基金联合资助（20135152049）；航天科技创新基金（CASC02）