基于改进CamShift的目标跟踪系统算法

敖邦乾，杨 莎，刘小雍，叶振环

(1.遵义师范学院工学院，贵州 遵义 563006；2.遵义师范学院物理与电子科学学院，贵州 遵义 563006)

0 引言

无人水面艇(unmanned surface vessel，USV)经常被用于执行特殊且不适合载人的任务，能完成情报收集、环境监测、水面搜救和水文地理勘查等任务，应用十分广泛。对于正在执行任务的USV进行检测跟踪，可以有效实施操作及控制。其中，基于区域的跟踪[1]对整个图像区域进行搜索，通过对比运动目标相邻两帧的位置变化实现区域跟踪；基于活动轮廓的算法[2]将运动目标的边界轮廓作为跟踪模板，并对轮廓进行实时的跟踪；基于模型的方法[3]通过对运动模板的外形特征建立2D或3D模型来完成跟踪任务。这些算法中，基于区域的跟踪方法需要搜索整个图像区域，计算量大，实时性较差；基于活动轮廓的跟踪方法，目标轮廓的更新比较困难；基于模型的跟踪方法则难以建立精确的模型，且易受外界影响。

基于特征的跟踪方法[4]通过提取运动目标的物理特征，利用相关的跟踪算法实现对目标有效的跟踪，其中，MeanShift是基于迭代收敛到概率最大的局部极大的非参数估计法[5]；Camshift则是对MeanShift的一种改进[6]，通过调整核函数来适应跟踪目标在图像中的大小，能有效解决目标变形和遮挡的问题，同时算法对系统资源要求不高，时间复杂度低，在较简单背景下能够取得较好的跟踪效果，但是传统的CamShift只对HSV中的H分量进行统计分析，易导致跟踪特征单一，当背景较为复杂或有许多与目标颜色相似像素干扰的情况下，会导致跟踪失败，文献[7]引入S分量，通过构建H-S二维直方图对原算法进行改进；文献[8]继续加入V分量，组成三维直方图跟踪模板进一步改进了算法，跟踪性能得到了进一步的提升，但是这类方法只是单纯地考虑颜色直方图，忽略了目标的空间分布特性。

为了提升目标跟踪效果的鲁棒性，文献[9]提出将MeanShift与Kalman滤波相结合的跟踪方法，充分发挥Kalman滤波器的预测功能和MeanShift跟踪器的搜索功能，提高了跟踪的精度和实时性；文献[10]提出了一种改进的CamShift和Kalman组合的目标跟踪算法，能对被严重阻挡或在与目标颜色相近的背景环境下的运动目标进行连续跟踪。

对于运动的跟踪目标，当运动目标发生形变或遮挡时，需要进行大量的计算，同时跟踪的实时性较差，鲁棒性不是很强，本文针对以上的问题，提出一种基于目标边缘检测的改进CamShift和Kalman滤波相结合的跟踪算法，改进了当跟踪目标与环境颜色相近时鲁棒性较差的问题，同时对于快速运动及被障碍物遮挡的跟踪目标也具有很好的跟踪性能。

1 CamShift目标跟踪算法

RGB颜色空间对光线较为敏感，为了减少光照变化对检测目标的影响，将需要检测跟踪的目标图像从RGB颜色空间转换到HSV颜色空间，转换后效果如图1所示，其中，HSV颜色空间的h值计算如下：

图1 被跟踪目标原始及转换后的图像Fig.1 The original image and converted image of the target

(1)

式(1)中，r(红色)、g(绿色)、b(蓝色)分别表示在RGB颜色空间中的坐标值，其取值为[0, 1]。在HSV颜色空间中，h取值范围为[0, 360]，它的值被归一化为介于0和180之间以匹配8位灰度图像(0，255)，HSV颜色空间的s值为：

(2)

HSV颜色空间的v值为：

(3)

本文算法采用HSV色彩空间进行处理，对于前方目标由于转向及变速等引起的形状及颜色变化具有一定的鲁棒性，通过分离出其中的H(色调)分量进行该区域的色调直方图计算，得到目标模板的颜色直方图，根据获得的颜色直方图将原始输入图像转化成颜色概率分布图像，即输入图像在已知目标颜色直方图的条件下的颜色概率密度分布图，同时对其进行归一化处理，如图2所示。其中包含了目标在当前帧中的相干信息，对于输入图像中的每一个像素点，建立目标模型颜色直方图：

图2 目标原始及归一化直方图Fig.2 The original histogram and normalized histogram

(4)

式(4)中，u,m,δ,|R|分别表示颜色向量、被量化的级数、Kronecker Delta函数和区域R内的像素点个数，h(x,y)为像素点(x,y)色度分量H量化后的值。对于目标区域内的像素，可得到该像素属于目标像素的概率，而对于非目标区域内的像素，该概率为0，这是一个反向投影过程。

算法设定阈值或最大迭代次数并进行迭代，通过寻找目标中心在当前帧中的位置来进行检测跟踪，首先在颜色概率分布图中选择搜索窗口的大小和初始位置，然后计算搜索窗口的质心位置。设像素点(x,y)位于搜索窗口内，I(x,y)为颜色直方图的反向投影图中该像素点对应的直方图概率值：

I(x,y)={H(u)|h(x,y)=u},(x,y)∈R

(5)

搜索目标窗口步骤如下：

步骤1 计算零阶矩m00，搜索窗口内所有点的概率之和：

(6)

计算一阶矩及概率在x,y方向的加权和：

(7)

步骤2 计算搜索窗口的质心(xc,yc)：

(8)

步骤3 设置初始化窗口大小，其中宽度为s，长度为l：

(9)

步骤4 计算二阶矩：

(10)

则目标运动窗口的方向为：

(11)

初始化式(9)得到移动跟踪窗口，根据式(11)提供的运动方向，将其移动到式(8)目标的质心位置，判断跟踪窗口的移动距离是否大于设定的阈值，若是，则重复步骤1到步骤4的搜索过程，直到相邻搜索窗口的质心变化小于给定的阈值或者达到迭代次数的最大值，同时为了实现连续跟踪，将上一帧图像搜索窗口的大小、质心作为下一帧搜索窗口的大小和质心，如此循环迭代，则可以完成对运动目标的连续跟踪，具体流程图如图3所示。

图3 Camshift跟踪算法流程图Fig.3 The flow chart of Camshift tracking algorithm

将目标的RGB图像转换成HSV图片空间后，对外界光照变化有了较强的鲁棒性，但当运动目标的颜色与运行环境颜色区域比较接近或运动目标被障碍物遮挡时，其跟踪效果则很容易受到干扰，如图4所示，在目标附近区域，由于被跟踪目标与环境颜色比较相似，因此其概率直方图也混淆有环境颜色的概率，目标的跟踪窗口有较大的误差，容易丢失目标，而在遇到被障碍物遮挡时，其跟踪窗口无法进行均值计算，也很容易丢失目标，需要进一步的优化算法设计。

图4 跟踪目标颜色与环境相似直方图Fig.4 The histogram of similarity between target and environment

2 目标跟踪算法设计

2.1 目标边缘算法检测

本文使用Canny边缘检测算法[11]来对跟踪目标进行边缘的提取，加强其跟踪的鲁棒性，具体设计如下：

表1 像素点I(x,y)为中心的3×3高斯滤波器Tab.1 3×3 Gaussian filter centered on pixel I (x, y)

(12)

步骤2 沿着x轴和y轴使用Sobel算子(Sx,Sy)来计算图形中每个像素点的梯度强度和方向，判断其边缘是水平、垂直还是对角线的。

(13)

(14)

(15)

(16)

Angle(θ)=arctan(Gy/Gx)

(17)

步骤3 应用非极大值抑制使得边界变细的同时锐化边缘部分，消除边缘检测算法带来的杂散响应，对于每个像素，如果它是先前计算的梯度方向的局部最大值M(x,y)，则保留该值;反之，它的像素值会被归零并且被极大值抑制。

(18)

步骤4 经过步骤3的处理，在保留下来的值中，确认强像素点是否位于边缘的最终图中，应用双阈值检测来确定真实的和潜在的边缘，根据经验设定两个阈值minVal和maxVal，任何强度梯度高于maxVal的像素都是边缘，任何强度梯度低于minVal的像素都不是边缘并丢弃，在minVal和maxVal之间具有强度梯度的像素，只有当它们连接到具有高于maxVal的强度梯度的像素才被认为是边缘，通过抑制孤立的弱边缘最终完成边缘检测。

Canny边缘检测算法能较好地完成环境中物体的轮廓边缘检测，但是其对目标以外的物体也能进行无差别的轮廓检测，如图5 所示。只有综合考虑两种算法，结合它们的优点，才能改进跟踪效果，本文使用Camshift算法和Canny边缘检测算法共同组成目标的跟踪模板，设计不同的权值ρcs、ρcn，假设跟踪过程中Camshift算法和Canny算法的反向投影分别为Fcs、Fcn，则加权后得到的合成反向投影为：

图5 不同环境下跟踪目标边缘提取Fig.5 The edge extraction in different environment

(19)

从式(19)可以看出，在跟踪过程中，加入的Canny边缘检测算法和原来的Camshift跟踪算法共同作用于跟踪目标，当目标颜色与环境颜色较为相近时，边缘检测算法占有较大的权值，可以抑制环境的影响，而当目标颜色与环境不同时，Camshift算法占有较大的权值比重，在总的概率密度分布图中可以自适应地调整相应的权值来增加系统跟踪算法的鲁棒性。

经过上述设计以后，跟踪系统对环境颜色的变化不敏感，具有较强的稳定性，但是当跟踪目标部分或者全部被障碍物遮挡时，上述设计的算法就容易丢失目标，而且上述设计的算法对运动目标的下一步动作无法做出预测，对快速运动的目标的普适性较差。

2.2 Kalman滤波算法

Kalman滤波[12]和粒子滤波[13]是比较常用的两种预测目标下一帧位置的算法，Kalman滤波是一种线性计算算法，具有计算量小、实时性高等特点，Kalman滤波算法在目标跟踪领域得到了广泛的应用，尤其对动态目标的跟踪检测，由于其算法很容易控制，并具有较强的鲁棒性，在工程上得到了广泛的应用。该算法的核心为采用信号和噪声的状态空间模型，主要是通过在状态上和时间上的不断更新来完成对运动目标进行跟踪，其模型如图6所示。算法利用系统的观测值来更新系统的状态向量，是一种对随机信号进行最优估计的实时递推算法，滤波器通过输入的系统观测量对随机信号进行估计，更新后得到的信号作为滤波器的输出，其不断地把协方差进行递归，从而估算出系统的最优值。

图6 Kalman滤波模型Fig.6 Kalman filtering model

Kalman滤波预测算法有两个重要的方程：

系统状态方程：

X(k)=AX(k-1)+BU(k)+W(k)

(20)

系统测量值方程：

Z(k)=HX(k)+V(k)

(21)

式(20)、式(21)中，X(k)和X(k-1)为k时刻和k-1时刻的状态向量；Z(k)为k时刻的系统状态测量向量；A、B、H分别表示状态转移矩阵、控制矩阵以及测量矩阵；U(k)为外部输入控制量；W(k)和V(k)分别表示状态过程噪声和测量噪声，通常应用中假设成零均值高斯白噪声，服从正态分布，即Noise～Guasian(0,σ)，协方差矩阵分别为R和Q。 算法主要包括预测与更新两个阶段，其对系统的预测公式组为：

1) 状态预测公式：

X(k|k-1)=AX(k-1|k-1)+BU(k)

(22)

2) 相对应的误差协方差预测公式：

P(k|k-1)=AP(k-1|k-1)AT+Q

(23)

现在状态的预测结果更新公式组为：

3) 状态校正公式:

X(k|k)=X(k|k-1)+
Kg(k)[Z(k)-HX(k|k-1)]

(24)

4) 误差协方差校正公式：

P(k|k)=[I-Kg(k)H]P(k|k-1)

(25)

5) Kalman增益系数公式：

Kg(k)=P(k|k-1)HT·
[HP(k|k-1)HT+R]-1

(26)

(27)

协方差矩阵Q和R分别为：

(28)

Kalman算法对于运动速度过快或者被遮挡的目标，能够比较精确地预测其在下一帧视频图像中可能出现的位置，很大程度上解决了外界动态环境变化所引起的跟踪失败问题，在实际工程应用中具有较大的应用价值。本文基于HSV颜色空间，同时加入Canny边缘检测算法改进CamShift跟踪算法，在对运动目标与环境颜色相近时的检测跟踪时，很大地加强了跟踪检测的光鲁棒性；同时，Kalman算法的加入，使其在高速运动或有障碍物时不至于丢失目标，使其能连续跟踪，其流程图如图7所示。

图7 本文算法流程图Fig.7 The flow chart of this article

3 实验测试及分析

为验证本文算法的实用性及优越性，设置如表2所示的软硬件及参数环境，三种算法在正常环境情况下，跟踪的效率差距不是很大，不影响系统的检测跟踪性能，因此本文进行了两种较极端情况下的仿真测试。

表2 软硬件环境及相关参数Tab.2 The H/S environment and related parameters

本文使用Bhattacharyya距离[14](BH系数)d(y)和有效帧率[15-16]ω作为其衡量标准。BH系数ρ(0<ρ<1)用于衡量CamShift算法中检测模块与目标模块的相似程度，其值越大，表示其相似度越高，算法跟踪效果越好；有效帧率ω则表示在目标跟踪过程中检测到的有效帧数与总帧数的比值，用来衡量目标跟踪算法的有效性。而判断某一帧是否为有效帧的方法仍然可以采用BH系数，设定适当的阈值，当BH系数超过这个阈值时，则认为其为有效帧。

测试1 运动目标颜色与环境颜色相似时测试效果

从图8可以看出，当跟踪目标颜色与环境颜色相近时，传统的CamShift算法仍然可以跟踪目标，但是其跟踪窗口会变大，总是要滞后几帧，随着颜色的越来越接近，这种滞后会更严重，而且当跟踪目标遇到有与其颜色相近的类似目标时，可能还会检测到其他目标，导致检测到的有效帧减少，其测试效果如图8(a)所示；CamShift和Kalman滤波相结合的算法，由于加入了Kalman滤波预测算法，跟踪窗口基本接近于物体的物理长宽度，能较好地跟踪目标，其测试结果如图8(b)所示；本文算法综合了CamShift和Kalman滤波的优点，同时加入了跟踪目标的边缘检测算法，因此其跟踪窗口能实时准确地跟踪到目标，不存在延时和失真等现象，尤其是在遇到颜色与跟踪目标颜色相近的障碍物或者其他物体时跟踪效果更好，采用的颜色直方图和边缘检测算法相结合的算法，对跟踪目标而言，其是唯一的，因此检测效果会更好，测试结果如图8(c)所示。

图8 不同算法测试效果Fig.8 The test result of different algorithms

对三种算法的BH系数进行了比较，如图9所示，本文算法中的BH系数达到最高，且在遇到与跟踪目标颜色相近的其他物体或在跟踪目标与环境颜色相近的极端情况时，也能达到很好的效果，其BH系数基本保持不变，同时表3中也对比了三种算法的有效帧率，本文算法可以达到对跟踪目标的完全有效跟踪，具有良好的稳定性和鲁棒性。

图9 不同算法BH系数Fig.9 BH coefficient of different algorithms

表3 颜色相似时的测试结果Tab.3 The effective frames in similar colors

测试2 有遮挡干扰下的测试结果

在跟踪目标穿过障碍物时，传统的CamShift算法在跟踪目标遇到障碍物时，跟踪窗口会停留在目标消失的最后位置，并且其窗口也会不停地变化，但是当目标出现在障碍物的前方时，跟踪窗口还是停留在原来的位置，并不会随着目标的重新出现而继续匹配窗口，其测试效果如图10(a)所示，同时从图11中也可以看出，其BH系数快速地降为零，目标继续运动后，CamShift算法失去了目标，可能导致跟踪失败；CamShift和Kalman滤波相结合的算法在遇到障碍物时，可以达到较好的效果，其BH系数也可以在跟踪目标穿过障碍物时，比较快速地恢复到一个稳定的值，同时不会丢失目标，如图10(b)所示；本文算法中，其BH系数在整个跟踪过程中都比较稳定，在遇到障碍物时，其值会减小，但是当跟踪目标重新出现时，跟踪窗口马上匹配目标，BH系数也快速地恢复到一个比较稳定的值，不会产生较大的波动，整个跟踪过程BH系数都很稳定，没有明显的波动变化过程，其测试效果如图10(c)所示。对于复杂环境中经常被障碍物遮挡的跟踪目标，在整个跟踪过程中都能表现出很好的跟踪性能，从表4的对比中也可以看出，本算法的有效率是最高的。

图10 有障碍物环境测试效果Fig.10 The test results with obstacle

图11 有障碍物环境下BH系数Fig.11 The BH coefficients of different algorithms

表4 有障碍物时测试结果Tab.4 The effective frames in different algorithms

4 结论

由于环境变化的复杂性，以及光照强度的不断变化，增加了对特定目标检测跟踪的难度，本文提出结合Canny边缘检测的改进CamShift跟踪算法，该算法克服了目标与环境颜色相近时无法检测或检测目标误差较大的难点，同时Kalman算法对目标的预测，尤其是有障碍物时的目标跟踪，具有较强的鲁棒性。仿真测试实验结果表明，算法极大地改进了原始CamShift算法在目标检测跟踪上的缺陷，本文所设计算法的跟踪效果比较稳定，具有较大的应用价值。