基于改进CAMShift的运动目标跟踪算法

刘 超，惠 晶

LIU Chao,HUI Jing

江南大学 轻工过程先进控制教育部重点实验室，江苏 无锡 214122

Key Laboratory of Advanced Process Control for Light Industry-The Education Ministry,Jiangnan University,Wuxi,Jiangsu 214122,China

1 引言

智能视频分析技术已成为计算机视觉领域中的一个重要问题，其中目标跟踪技术应用范围广泛，在人机交互、物体识别、视频监控等方面发挥着重要作用[1]。

MeanShift目标跟踪算法以其无需参数、计算量小，对目标变形、旋转变化适应性强等特点得到普遍的重视和广泛的研究[2-3]，而CAMShift在其基础之上增添了自适应大小的功能[4]。Comaniciu等通过颜色加权直方图描述目标，用Bhattacharrya系数度量候选目标和模型之间的相似度，能够通过较少的迭代次数收敛到目标的真实位置[5]。Chu等人结合帧差法实现了CAMShift自动跟踪[6]，由于帧差法仅提取了部分的轮廓边缘，使目标内部产生孔洞，往往造成目标提取不完整或者包含背景，使颜色特征混入了更多杂色而降低跟踪质量[7]。李忠海等将CAMShift与粒子滤波相结合，用以对小目标实现跟踪[8]。

目标颜色与背景颜色的可分性对CAMShift的跟踪效果影响较大。当搜索窗口中包含背景颜色信息时，传统方法会将属于背景的像素误判为目标像素，从而引入跟踪误差；随着误差的积累，可能导致跟踪失败。在跟踪过程中如果目标被逐渐遮挡，搜索窗口的尺寸会不断减小甚至导致目标丢失，当目标重新出现后，也无法恢复对目标的跟踪。针对以上存在的问题，本文扩展和改进了传统的CAMShift算法，给出将非线性核密度估计、Kalman滤波和CAMShift相结合的抗遮挡的目标跟踪解决方案。

2 核密度估计和CAMShift跟踪算法

2.1 核密度估计

核密度估计是一种概率密度估计方法[9]。既不需要事先假定特征密度分布的形式，也不需要设置模型参数及参数优化。只要样本充足，核密度估计就能渐进收敛于任何一个概率密度函数[10]。核密度估计的目的是在已知一定数量的样本点的情况下，尽量地逼近一个未知概率密度分布函数[11]。在核密度估计中发挥作用的单元是众多具有相同尺度与形态的核函数。

假设xi(i=1，2，…，N)为未知概率密度分布产生的维度为d的N个样本点，xi∈Rd。核密度估计函数可以表示为：

其中KH为核函数，可以表示为H为d×d大小的正定带宽矩阵。当简化带宽矩阵为单参数 h时，式（1）可变为：

多维变量的核函数KS可以通过每个维度下单变量核函数Kj的乘积计算来表示：

2.2 基于非线性核密度估计的目标检测

已知一组由 N幅图像组成的序列，定义 xi∈{x1，x2，…，xN}为图像中任意一个位置的像素点在第i时刻的色彩强度。对于当前t时刻此像素点的观测值xt而言，其分布函数 p(xt)的核密度估计则可定义为：

其中，K为选择的核函数，满足性质K(t) ≥0和∫K(t) dt=1。由于图像一般为多通道彩色图像，所以样本点均为多维数据（比如RGB图像拥有3个色彩通道），利用公式（2）和（3），可以把具有d维核函数用每个色彩通道的核函数乘积来表示：

虽然普遍认为高斯核函数在样本点有限的时候能够获得比较好的核密度估计，但是计算量过大，给实际应用带来不利影响[12]。相对于高斯核函数而言，Epanechnikov函数同样具有钟形函数的形态，却可以大大减少计算量，提高运算速度。选择Epanechnikov函数作为核函数的概率密度估计函数为：

公式（6）是估计三通道彩色图像像素值的概率密度分布的最终表达式。指定Th为一个固定的阈值与计算得到的估计值进行比较决策，将此像素值离散化为前景（foreground）或者背景（background）。当所有像素点都遍历完毕，就得到二值检测图像。

2.3 CAMShift跟踪算法

CAMShift算法主要通过视频图像中运动物体的颜色信息来达到跟踪的目的[13]。算法思想如下：（1）初始化搜索窗口；（2）把搜索窗口图像转化为颜色概率图并求质心；（3）移动搜索窗口中心到其质心处，重新搜索直到窗口中心与质心间的移动距离小于预设的阈值或者运算次数达到预设值；（4）重复（2）、（3）步骤至跟踪结束。

设(u，v)为搜索窗口中的像素点坐标，I(u，v)是投影图中对应(u，v)点的灰度值。定义搜索窗口的零阶矩M00和一阶矩M10、M01分别如下：

可以求得当前搜索窗口的质心位置为：

然后调整搜索窗口的大小，并将搜索窗口的中心移动到质心。直到窗口中心与质心间的移动距离小于预设的阈值或者运算次数达到预设值，则认为满足收敛条件，进入下一帧图像进行新的目标搜索。相对于当前帧，下一帧中搜索窗口的长度l和宽度w分别按下式更新。

其中：

CAMShift算法以逐帧处理视频序列的方式完成目标的连续跟踪[14]。

3 非线性核密度估计与CAMShift相结合的运动目标跟踪

非线性核密度估计对样本数据用核函数进行估计，选出概率密度最大的样本数据作为背景。该方法能适应不同的场景，不同于混合高斯模型。它充分利用最近的历史帧信息来表示背景模型，能够适应复杂的像素分布密度，克服像素值在短时间内频繁变化，得到准确的估计。CAMShift算法通过视频图像中运动物体的颜色信息来达到跟踪的目的，它采用目标的颜色直方图作为搜索特征，通过不断迭代均值偏移向量使得算法收敛于目标的真实位置，从而实现跟踪。将两者结合，在背景减法的基础上用CAMShift做目标跟踪，能提高跟踪准确性，易于实现且运行速度快，能够达到实时跟踪的目的。

图1是算法流程图，上面的虚线框是核密度估计过程，左下的虚线框是Kalman滤波过程，右下的虚线框是CAMShift算法执行过程。首先用像素级非线性核密度估计算法检测运动目标，通过检测得到的二值图像进行连通区域分析提取感兴趣目标。然后用提取的感兴趣目标建立目标直方图并初始化目标作为CAMShift的输入，CAMShift算法用来在下一帧搜索目标。收敛的搜索结果用以更新Kalman滤波然后预测下一帧目标的状态。下一帧在预测位置附近进行CAMShift搜索目标，能够减少运算量，提高效率。跟踪过程中，用非线性核密度估计的检测结果辅助目标直方图的更新。采用非线性核密度估计提取感兴趣目标，能实现运动目标的自动跟踪并能去除背景颜色，为下步建立只包含前景颜色的目标直方图提供保障。由于目标位置不会突变，CAMShift算法仅在Kalman滤波预测位置附近搜索目标，能够保证在搜索准确率不变的前提下减少运算量、提高效率。CAMShift搜索结果用以更新Kalman滤波，相当于用真实位置更新Kalman滤波，提高预测准确率。

图1 改进CAMShift目标跟踪算法流程图

3.1 感兴趣目标的获得及直方图的建立

在原图中选择一个包含运动目标的初始窗口建立直方图，使得初始窗口不仅包含了跟踪目标，还混入了背景颜色信息。针对上述问题给出将背景减法与CAMShift相结合的方法。运用非线性核密度估计先对视频中的运动目标进行检测，该模型能很好地处理光照变化的影响，适应在噪声环境下目标的复杂运动和场景长时间的变化。检测后得到了包含完整目标的最小窗口作为CAMShift的初始窗口，并将检测出的前景像素相同位置的原图像素信息建立直方图。不仅使CAMShift实现了跟踪自动化，也有效地去除了背景颜色信息的干扰。本文的解决方案如下：

（1）运用非线性核密度估计方法采用多帧建立背景模型并对当前帧（图2（a））进行目标检测，得到二值图像（图 2（b））。

（2）对检测得到的目标进行连通区域分析，画出包围目标的最小窗口，如图2（c），记录该窗口的坐标。

（3）将二值图2（b）与原图2（a）相比较，如果二值图中的某位置像素值为255，则原图的同位置像素值保持不变；如果二值图中的某位置像素值为0，则原图的同位置像素值也变为0。得到图2（d）。

（4）把图2（d）转化到HSV空间并提取H分量。

（5）把步骤（2）得到的窗口坐标作为CAMShift的初始窗口坐标，并对图2（d）此窗口内的像素H分量建立直方图，由于去除V和S值较低的部分，建立的直方图不统计框内黑色像素，只包含目标像素的H分量。

图2 非线性核密度估计检测结果

3.2 直方图的更新

通过上述五步实现了CAMShift的自动化跟踪，并建立了不包含背景颜色信息的目标颜色直方图[15]。接下来就是用CAMShift对目标进行跟踪，并且非线性核密度估计与CAMShift相结合来更新直方图，以适应目标颜色的变化。用一个物体的色彩分布来描述这个物体，假设物体中心位于x0，则该物体可以表示为：

候选的位于y的物体可以描述为：

因此物体跟踪可以简化为寻找最优的y，使得 pu(y)与qu最相似。 pu(y)与qu的相似性用Bhattacharrya系数 ρ^(y)来度量，ρ^(y)越大，表示候选目标与模板目标越匹配[16]，即

如果没有发生遮挡并且Bhattacharyya系数 ρ大于某一阈值Th则认为跟踪得到的候选目标即为模板目标，此时利用候选目标的H分量直方图更新模板目标直方图，即

由于非线性核密度估计的前景检测方法计算量较大，所以选择定时更新，即每6帧运行一次目标检测计算并更新一次目标直方图。

3.3 抵抗目标遮挡

Bhattacharyya系数表征当前跟踪到的候选目标直方图与模板目标直方图的相似度。当Bhattacharyya系数减小到一定的阈值并且目标大小急剧减少时，说明跟踪目标可能发生了遮挡。若目标披遮挡，搜索窗口的尺寸将不断变小，此时难以判定跟踪物体的位置并可能出现当目标重新出现后难以恢复跟踪的情况。

当发生遮挡时的跟踪策略为：假如第k帧目标发生遮挡，则在k-1帧还没发生遮挡，此时不更新目标直方图，并且用k-1帧跟踪到的目标框大小及位置预测k帧的跟踪框。这里有两种情况，分析如下：

Case 1：当发生部分遮挡时，假设实线框 A为第k帧跟踪到的跟踪框，虚线框B为实际的跟踪框，框B的大小为第k-1帧没发生遮挡时跟踪得到的跟踪框大小，它们的可能位置如图3（a）所示。根据跟踪框附近位置非线性核密度估计方法检测的二值图中白色连通区域的位置，可认为发生了某种情况的遮挡，用这种情况的跟踪框B代替跟踪得到的跟踪框A，即为实际可能的目标位置。

Case 2：如图3（b）所示当发生完全遮挡时，此时Bhattacharyya系数会急剧减小，跟踪框的大小也会急剧变化，用此前没发生遮挡时跟踪得到的跟踪框大小代替当前帧的跟踪框大小，跟踪框的中心设定为非线性核密度估计检测得到的二值图像中没发生遮挡时跟踪得到的跟踪框附近白色连通区域的中心位置。

图3 两种目标遮挡情况

由于直方图一直没有更新，当目标重新出现时仍能搜索得到跟踪框，并且Bhattacharyya系数大于某一阈值，说明遮挡已经结束。对符合条件的跟踪块进行背景减法与CAMShift相结合的运动目标跟踪，即恢复正常目标的无遮挡跟踪过程。

4 运动目标跟踪仿真实验

本文实验均在2.5 GHz*2 CPU、1 GB内存的PC机上进行，采用VC++6.0开发环境；对AVSS 2007、PETS 2003等图像序列测试跟踪算法。

如图4所示，在AVSS 2007序列中对序列中的一辆红色车进行跟踪，图中蓝色矩形框为Kalman滤波的预测目标状态（包括位置和宽高等），红色矩形框为CAMShift的跟踪结果。从结果可以看出，CAMShift的跟踪结果能提供完美的观测值来修改运动目标的预测状态；Kalman滤波不仅能发现汽车的正确位置，适应性也随着车的增大而逐渐扩大。

图4 AVSS 2007序列运动目标跟踪结果

为了展示本文提出算法的优越性，分别采用传统CAMShift跟踪算法和本文提出的跟踪算法对PETS2003视频序列进行检测，序列分辨率为720×576，目标在运动过程中存在遮挡；测试时每5帧采样一次，得到原图的第345、350、355、360、363、375、380、385、390帧图像，在第350帧两个运动员之间发生了局部遮挡，在第363帧目标几乎被完全遮挡，在385帧遮挡结束。当第363帧目标被完全遮挡后，由于传统CAMShift跟踪算法不更新直方图，跟踪了临近的另一个穿红衣服的运动员，导致跟踪失败，如图5所示。

图5 传统CAMShift目标跟踪结果

图6展示了采用本文提出的改进CAMShift算法跟踪结果，图中两个运动员突然向右运动，此时Kalman滤波器产生了一个不准确的结果，如图6（f）。然而本文算法设计的Kalman滤波器有自适应的性质，它会根据当前CAMShift的跟踪结果调整滤波器的参数，使得预测的位置逐步趋向于CAMShift的跟踪结果，如图6（g）～（i）；每次CAMShift算法均在Kalman滤波预测位置附近搜索，提高运算速度。跟踪过程中算法的平均运行时间为88.9ms，算法完全能够满足实时的要求，目标跟踪轨迹如图7所示。

图6 改进CAMShift目标跟踪结果

图7 PETS 2003目标的跟踪轨迹

5 结束语

本文扩展和改进了传统的CAMShift算法，将核密度估计、Kalman滤波器、CAMShift与遮挡策略相结合，给出一种以前景检测为辅，CAMShift为主的目标跟踪方法，实现了运动目标的自动跟踪。当目标正常跟踪时，用非线性核密度估计的检测结果对目标直方图进行自适应更新；当检测到目标发生遮挡时，用前面遮挡前的目标尺寸和位置修正当前跟踪结果的目标尺寸及位置；当目标遮挡结束，重新运用核密度估计与CAMShift相结合的跟踪策略进行跟踪。实验结果证明了给出的算法兼具效率和准确，并且有比较强的鲁棒性。

[1]侯志强，韩崇昭.视觉跟踪技术综述[J].自动化学报，2006，32（4）：603-617.

[2]吴慧敏，郑晓势.改进的高效Camshift跟踪算法[J].计算机工程与应用，2009，45（27）：178-180.

[3]Brox T，Rousson M，Deriche R.Colour，texture，and motion in levelsetbased segmentation and tracking[J].Image and Vision Computing，2010，28（3）：376-390.

[4]Yang Changjiang，Duraiswami R，Davis L.Efficient meanshifttracking via a new similarity measure[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2005：176-183.

[5]Chu Hongxia，Ye Shujiang，Guo Qingchang，et al.Object tracking algorithm based on CAMShift algorithm combinating with difference in frame[C]//IEEE International Conference on Automation and Logistics，2007：51-55.

[6]Dai Guojun，Zhang Yun.A novel auto-CAMShift algorithm use in object tracking[C]//CCC2008，2008：369-373.

[7]Elgammal A，DuraiswamiR，HarwoodD，etal.Background and foreground modeling using nonparametric kernel density estimation for visual surveillance[J].Proc of the IEEE，2002，90（7）：1151-1163.

[8]李忠海，王莉，崔建国.基于Camshift和Particle Filter的小目标跟踪算法[J].计算机工程与应用，2011，47（9）：192-195.

[9]Scott D W.Multivariate density estimation[M].New York：Wiley-Interscience，1992.

[10]Comaneci D，Meer P.Meanshift：a robust approach toward feature space analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（5）：603-619.

[11]Jeyakar J，Venkatesh Babu R，Ramakrishnan K R.Robust object tracking with background-weighted local kernels[J].Computer Vision and Image Understanding，2008，112（3）：296-309.

[12]McHugh J M，Konrad J，Saligrama V，et al.Foregroundadaptive background subtraction[J].IEEE Signal Processing Letters，2009，16（5）：390-393.

[13]徐萧萧，杨浩，陈宗海.一种基于改进CamShift的目标跟踪算法[J].系统仿真技术及其应用，2009（11）：851-854.

[14]Comaniciu D，Ramesh V，Meer P.Kernel-based object tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）：564-577.

[15]刘曼华，朱秀丽.基于改进CAMShift的多目标自动跟踪[J].河南大学学报，2010，40（5）：525-528.

[16]宁纪锋，姜光，吴成柯.CAMSHIFT与基于核的目标跟踪算法的比较与分析[J].计算机工程与应用，2009，45（28）：177-179.