刘美枝，杨 磊，高 海

(山西大同大学物理与电子科学学院，山西大同037009）

运动目标跟踪一直以来都是机器视觉的一个重要研究方向，但是，环境背景和目标姿态发生变化，或者多目标出现相互干扰等因素都会加大目标跟踪的难度。在目标跟踪过程中，选用较好的目标特征和合适的搜索算法很重要。目标跟踪算法主要从提高搜索匹配的速度和精度两个方面来对运动目标的性能加以提高[1]。CamShift（Continuosly Adaptive Mean-Shift）算法是一种经典的运动目标跟踪算法，但该算法仅仅依靠目标的颜色特征，当出现相近颜色的目标或背景时，都会使跟踪发生漂移，甚至失效。针对该问题，本文通过融合角点特征对CamShift算法进行改进，进而实现目标准确稳定地跟踪。

1 Harris角点检测算法

角点[2]是图像的一个重要局部特征，Harris角点在光照、噪声、旋转、平移及灰度变化时具有不变性，所以在目标跟踪领域有着重要的意义[3-5]。Harris 角点最直观的解释就是，在两个相互垂直的方向，都有较大变化的点，数学描述如下。首先，定义自相关函数：

在Harris角点检测中，使用的是高斯窗口，wu,v表示的是高斯窗口中的权重。I为灰度值，E(x,y)表示的是图像偏移导致窗口内像素的平均变化。若窗口不变，则E(x,y)为x,y的函数。Harris 角点是当(x,y)在两个相互垂直的方向上，E(x,y)取较大值的点。

若令D(x,y)=Ix+u,y+v-Iu,v，则D(x,y)在原点(0,0)Taylor展开，得到

显然有D(0,0)=Ix,y-Ix,y=0 ，将高阶无穷小0(x2,y2)忽略，可以将

代入自相关函数

从而有

其中

那么E(x,y)可表示为

由于

那么A，B分别表示x,y方向窗口中图像的一阶差分平方和，C表示窗口中x方向与y方向一阶差分的乘积。用sobel 算子[6-9]求一阶差分，即I⊗(-1,0,1)和I⊗(-1,0,1)T。那么可得到H矩阵，该矩阵是对E(x,y)的Hessian 矩阵的近似。可借助频率域研究，令

从而得到H是Hessian 矩阵的另一种表达，由于求导运算并不严格，所以只能认为这是一种近似。Harris 可以对任意方向统计，对于一个给定方向，只要取到合适(x,y)，就能统计(x,y)对应角度上窗口灰度值发生的变化。

如何去计算这个合适的(x,y)呢，对每一个角度都去计算，显然是不合适的。这要从Harris 角点的定义来考虑，前面已经说过Harris角点是当(x,y)取两组相互垂直的值时，E(x,y)都取得较大值对应的点。所以，首先考虑找出使E(x,y)取最大值的(x,y)，如果该方向E(x,y)有较大的取值，再考虑其垂直方向。

要判断一个点是否为特征点，本质上是要求该点的H矩阵，以及H矩阵的两个特征值的分布情况。

1.1 Harris角点检测步骤

应用Harris角点检测方法提取图像中角点的过程可以分成以下几步：

1）计算每一帧图像中像素点在水平方向和垂直方向上的梯度，以及两者乘积的运算结果，得到一个如下所示的M矩阵：

2）对图像进行高斯滤波，重新得到M矩阵。

3）计算图像上对应的每一个像素点的R值

式中：α为经验值，取值范围介于[0.04,0.06]。

4）选取局部极值点。特征点反映的是局部范围内R极大值对应的像素点。

5）设定阈值，选取一定的角点。

1.2 Harris角点匹配

在实际应用中，由于目标遮挡，形变等易造成部分角点丢失，而且由于Harris 角点检测算法是通过手动设置阈值，实验发现：当取大阈值时，其提取的角点较准确，但是不能完全反映目标的角点信息；当取小阈值时，易产生虚假角点。在这样的情况下，两幅图像提取到的角点个数不一定相等，这时就很有必要对它们进行角点匹配，得出一一对应的角点对。

传统的NCC 匹配算法[10-12]计算量比较大，复杂度较高，而且会产生误匹配等问题。本文在NCC匹配的基础上进行改进，使用距离约束减少搜索的范围，距离约束的前提条件是认为两幅图像的相对位置和旋转角度变化均不大，认为两幅图像的投影点的位置也相差不大。若要在图像I2中找出与图像I1匹配的特征点时，只需要计算I1在I2中给定范围内的特征点的NCC值，对不在范围之内的特征点则不予计算。

采用BGNCC方法的匹配步骤如下：

1）第一幅图像I1中的特征点记为di,i=1,2…m1 ，坐标表示为在第二幅图像I2中对应坐标位置的(-4n,4n)邻域内搜索特征点（可能无，一个或多个），记为dj，若存在特征点，以第一幅图像I2中特征点di的n×n区域为匹配窗口计算与第二幅图像I2中特征点dj,j=1,2…m2 的等大小的窗口的相关系数。设定阈值a，若Cjj大于a，将满足条件的特征点即为匹配点，依次类推得到第一组匹配点集。

2）根据互匹配原理，按照上面的方法搜索第二幅图像I2中特征点dj,j=1,2…m2 在第一幅图像I1中的匹配点，得到第二组匹配点集。

3）（第一组特征点集）⋂（第二组特征点集），至此完成特征点匹配。

图1是通过对两幅图像采用双向最大归一化相关系数进行特征点匹配的结果图。

图1 图像角点匹配结果

由图1 两幅图像的匹配结果可知，在相邻两帧图像中目标变化缓慢的情况下，采用双向最大归一化相关系数进行特征点匹配，在很大程度上可以去除一部分虚假角点，有利于目标进行正确的匹配。

2 结合角点特征的Camshift算法

本文采用结合角点特征和颜色特征的Cam-Shift 目标跟踪算法，仅用经过匹配后的每个特征点周围N×N的区域建立目标的相关模型，那么得到的新的目标模型以少量特征点信息表示目标区域的主要特征。由于Harris 角点检测算法和匹配算法的复杂度较高[7]，采用少量的关键点信息在一定程度上降低了整个算法的复杂度，增强目标与背景的可分性，加速目标的收敛，减少迭代次数。下面是结合角点特征的CamShift 算法的流程图，其中k表示帧数，初始值为0。其算法流程图如图2所示。

图2 结合角点的CamShift算法流程图

3 实验结果及分析

实验环境为Windows XP 系统，在Visual Studio2010 下编程实现。测试的视频为室内颜色相近的多目标在短时间相互干扰的跟踪情况。在实验中，目标的初始位置通过手动标记，先后采用传统CamShift 跟踪算法和本文算法进行跟踪，通过对比跟踪结果，验证本文算法的可行性。

图3 是采用传统CamShift 跟踪算法的跟踪结果，从图中可以看出，当两辆小车相距较远时，跟踪情况良好，从第58帧开始，两辆颜色相近的小车慢慢靠近，跟踪框开始漂移，到第72帧跟踪框包含了两辆小车，整个跟踪失败。这是由于两辆小车的颜色相近，而CamShift跟踪算法只是简单的依据颜色信息进行跟踪，所以就会出现跟踪漂移，误差累积到一定程度，出现跟踪失效。

图3 传统CamShift跟踪算法的跟踪结果

图4 是采用本文跟踪算法的跟踪结果，从图中可以看出，开始目标相距较远时，跟踪效果与传统算法相似，都可以完成准确有效地跟踪，当目标慢慢靠近时，跟踪框稍有形变，但形变不大，跟踪过程中可以自适应地调整跟踪框的大小和形状，顺利完成跟踪。由此可知本文算法与传统算法相比，在很大程度上减少了背景信息，充分利用目标信息，使得较短时间相互靠近的目标能够完全分离。通过上面的实验可知，加入角点特征可以改善由于颜色特征产生的跟踪的不稳定现象，提高了目标跟踪的鲁棒性。

图4 本文跟踪算法的跟踪结果

表1是对实验分别采用原始的CamShift算法和基于角点的CamShift算法的跟踪性能比较结果。

表1 跟踪算法性能比较

由表1知，改进后算法的平均误差相比传统的CamShift 跟踪算法有所减少，但由于Harris 角点的提取和匹配过程的计算量比较大，复杂度较高，所以导致基于Harris角点的CamShift 跟踪算法的每帧的迭代次数和平均处理时间比传统的CamShift跟踪算法大。

4 结论

本文采用基于角点特征和颜色特征的CamShift目标跟踪算法。首先进行Harris 角点提取，由于Harris 角点的提取过程中，阈值是人为设定的，而且受周围环境的影响，每一帧中提取出来的角点的个数是不固定的，为了剔除虚假角点，确定目标的真实角点，采用BGNCC角点匹配方法，提取匹配后的角点特征周围N×N区域，将此区域设为感兴趣区域并生成直方图，将生成的直方图转化为概率密度反向投影，最后利用MeanShift 算法搜索目标。实验结果表明该算法能够有效解决多目标运动时产生的干扰现象。