一种camshift算法与brisk特征点相结合的运动目标跟踪方法

陈 佳，朱长仁，罗 宾

(1.国防科技大学 电子科学与工程学院 ATR重点实验室，长沙 410073；2.武警福建总队直属支队，福州 350001)

一种camshift算法与brisk特征点相结合的运动目标跟踪方法

陈 佳1，2，朱长仁2，罗 宾2

(1.国防科技大学 电子科学与工程学院 ATR重点实验室，长沙 410073；2.武警福建总队直属支队，福州 350001)

传统的camshift算法中，当目标移动过快或背景同目标相似时容易导致目标跟踪丢失，在各种复杂情况下，如何保持跟踪的有效性及连续性成为众多研究人员不断努力的方向。为此，提出了一种brisk特征点检测与camshift算法相结合的目标跟踪方法，以及简化的搜索窗口修正方法，在camshift算法基础上，通过不同帧的目标上brisk特征点匹配来防止局部最大值的出现以及目标移动过快导致的跟踪窗口丢失。实验结果表明：该方法有效地提高了目标跟踪的连续性和稳定性，与其他特征点结合的算法相比有更好的实时性及精确性。

目标跟踪;camshift;meanshift;brisk特征点

目标跟踪是智能视频研究领域的一个热点，吸引着越来越多研究人员的关注。传统的目标跟踪方法通常分为基于检测的跟踪算法，基于模板匹配的跟踪算法，以及基于统计学习的跟踪算法。帧差分法是最简单的一种检测方法，但其不适用于移动背景下的目标检测[4]。模板匹配方法采用目标图像模板同待匹配区域进行相似度计算，把相似度最高的区域作为匹配结果，虽然算法简单，计算速度快，但相似度匹配的计算受噪音影响比较明显，对非刚体目标适应性差。基于统计学习的跟踪方法中，粒子滤波方法采用一系列带有权值的随机采样点来表示所求的目标模型的后验概率密度函数，再利用这些采样点和权值来估算目标的最终概率密度，但是不断的重采样过程中容易出现粒子的退化现象，导致跟踪结果的不稳定[5]。均值漂移是一种基于核函数的概率密度方法，其代表性的camshift算法通过计算当前跟踪窗口中目标模型概率密度最大的方向来不断调整搜索窗口的中心位置，最终得到运动目标在窗口中的稳定位置。

Camshift[8]算法是一种基于颜色直方图模型的跟踪算法，但在目标直方图模型的建立及目标跟踪过程中极易受到诸如光线、视角、摄像机参数等环境因素的影响，导致跟踪误差或丢失目标，于是，针对camshift的各种改进方法被提出来。文献[6]将目标的颜色直方图同LBP纹理特征相结合，通过定义加权融合的函数来表示目标模型，提高了跟踪的鲁棒性。文献[7]提出了一种融合H、S分量的多维直方图来表示目标模型，该方法比单纯采用一维直方图能更加精确地表示目标模型。近年来，由于快速局部特征检测算法的提出，不少研究人员尝试在跟踪过程中通过提取目标特征点的方式来防止camshift跟踪过程中对目标的误判及丢失。文献[9]提出了将sift特征融合色彩概率模型来进行目标的匹配，提高了目标跟踪的鲁棒性。文献[12]采用速度较快的快速鲁棒特征(surf特征)提高算法的实时性，但在初次化时必须预先提取目标的特征点，该方法适用于对已知目标的跟踪。文献[11]在文献[9-12]的基础上，提出了将orb特征检测同camshift结合起来，通过orb特征点匹配来修正窗口漂移的误差，并计算特征点尺度和方向的变化来重计算窗口的大小和位移。

然而，对实时跟踪系统来说，速度与准确性是制约系统性能的两大问题。传统的sift、surf特征提取方法虽然精度高，但由于其检测方法及描述符生成算法较为复杂，在现实应用中对硬件提出了较高的要求。orb算法虽然同surf、sift算法一样具有尺度不变性，运算速度也有不少改进，但其特征点精确度较易受到噪音影响，不如sift特征点稳固。本文受文献[10]启发，提出一种结合brisk特征检测算法的改进的camshift算法，在提高特征点精度的前提下，进一步优化搜索窗口的修正，可有效避免目标的误判及跟踪丢失。

1 camshift跟踪算法

Camshift算法全称为连续自适应目标跟踪算法(continuously adaptive mean-SHIFT)，其本质是在序列图像上反复调用meanshift算法来实现目标跟踪。Meanshift算法作为一种非参数的概率密度估计方法，最早在文献 [2]于1975年提出，当时主要是作为一种聚类方法用于单幅图像的分割。文献 [3]对其进行了改进，并用来寻找相似概率密度的模型。文献[8]通过改进meanshift算法，第一次把camshift算法用于人脸跟踪过程，至此camshift算法被引入目标跟踪领域并被广泛应用。

1.1 Meanshift算法基本原理

Meanshift算法的中心思想是通过建立目标的颜色概率密度模型，在待匹配模板上反复迭代，不断往概率密度最近似的位置移动，以此寻找相似像素的区域中心。具体为：从每个像素开始，首先估计有相似颜色的邻近像素点的密度(局部密度)的梯度，而后利用迭代算法求出局部密度的峰值(即重心点)，最后以该峰值为中心，并把位置作为结果输出。Meanshift作为一种高效的模式匹配算法，不需要进行全局搜索，搜索精度高，其基本流程如下：

1) 选择跟踪窗口的大小和初始位置。在meanshift跟踪算法中，核窗宽的大小(即核函数的定义域大小，即搜索框的大小)起着非常重要的作用。它不但决定了参与meanshift迭代的样本数量，而且也反映了跟踪窗口的大小。通常，核窗宽由初始跟踪窗口的尺寸决定，且在整个跟踪过程中不再发生变化。

2) 计算跟踪窗口内的质心或重心。在离散二维(2D)概率分布图像中，计算某窗口的质心同物理上计算某物体的质心一样，即利用窗口零阶矩M00和(x,y)的一阶矩(M10,M01)之间的关系，计算得到窗口的质心。则跟踪窗口的质心(Xc,Yc)计算公式为

(1)

其中，跟踪窗口的零阶矩为

(2)

跟踪窗口的一阶矩为

(3)

式中 Ic(x,y) 是(x,y)坐标的像素值，x,y的变化范围为搜索窗大小。

3) 调整跟踪窗口的中心到质心。

4) 重复第2)步和第3)步，直到跟踪窗口中心和质心“会聚”，即每次窗口移动的距离小于一定的阈值。

由此，得到的输出结果为图像上同目标模板最相似的区域。

1.2 Camshift算法基本原理

Camshift作为基于meanshift改进的一种自适应跟踪算法，与meanshift的区别是： meanshift每次迭代搜索后，搜索框大小都不会改变，而camshift每次搜索及匹配完毕后，都会根据最近一次目标匹配结果重新计算搜索框大小，来进行下一次meanshift计算。这样，当非刚体目标在运动中外观尺寸发生细微变化，或者当跟踪场景受到光照等其他因素影响时，camshift算法就能在跟踪过程中表现出比meanshift更好的适应性。其算法步骤如下：

1) 在颜色概率分布图中初始化一个搜索窗W，其大小为S；

2) 利用meanshift 算法使搜索窗口“收敛”。在概率分布图像中，通过计算搜索窗口的质心，调整搜索窗口的中心到计算的质心位置。重复该过程，直到“收敛”(即中心的位移动小于给定的阈值)。

3) 重新设置搜索窗口的大小S并计算跟踪目标的输出参数。对于颜色概率分布图像，零阶矩代表了跟踪目标在图像中的面积，又因为颜色概率分布图像是256个量化级别的灰度图像，因此，更新搜索窗口的宽度s和零阶矩M00的关系为

(4)

其中零阶矩M00由式(3)～(7)给出。并用该窗口初始化下一帧meanshift 的搜索窗口。

4) 跳转到第二步进入下一帧的循环。直到中心的位移小于阈值。

1.3 Camshift算法的不足之处

Camshift算法尽管采用了动态的跟踪窗口对跟踪过程进行优化，但在其跟踪过程中依靠预先建立的目标颜色概率模型，通过不断迭代来靠近概率密度最高的点(即目标的质心)，其搜索窗口尺寸的自动调整策略是在上一帧窗口大小的基础上，长和宽分别向外扩张一定距离，在更大的空间范围内重新计算目标的质心并估计目标面积。因此，在运动目标经过的背景区域中，如果存在和目标颜色近似的物体或背景块，且其面积大于或等于当前运动目标尺寸，算法容易在“虚假的目标”上得到概率密度的最大值，搜索框因此不再跟随真正的目标移动，导致了跟踪丢失。此外，当运动目标速度突变或过快时，由于超出了搜索框的计算范围，也容易导致跟踪目标的丢失。

图1显示了序列视频中，当运动目标接近颜色相似的物体时，camshift算法对目标进行了错误的判定，导致目标跟踪失败。

图1 Camshift算法导致的目标跟踪丢失

2 brisk特征点

Brisk特征点[1]是由Leutenegger于 2011年提出的一种快速的、具有旋转及缩放尺度不变性的特征点描述及检测方法。同sift、surf特征点一样，brisk具有旋转及尺度变化适应性，但在特征点检测及描述符生成上都比sift、surf算法更为迅速，同时弥补了orb特征点不具有尺度变化适应性的不足。文献[13-14]中有详细的性能对比，下面对原理进行描述。

在特征点检测方面，brisk算法首先构建尺度空间金字塔，并通过Adaptive and Generic Accelerated Segment Test (AGAST) 角点检测算子提取连续尺度空间中亚像素级精度的稳定极值点。AGAST 角点检测算法是对著名的 FAST 角点检测算法[9]的改进。 AGAST算法流程如下：在一个像素点周边半径3的区域里，通过预设阈值T、N，然后对比该像素点同周边像素点的亮度。假设中心像素点为P,其亮度为Ip,如果周边有连续N个像素点其亮度大于Ip+T,或有连续N个像素点其亮度小于Ip-T,就把点P标识为空间中的一个角点。

在描述符生成方面，brisk描述符作为一种二进制描述符，主要由2个步骤组成：① 周边像素采样对生成；② 特征点描述符生成。首先选取周边采样对，即通过选择合适的角点周边像素信息来描述角点的唯一性。不同于surf、sift特征点通过将角点周边区域分块计算直方图方式来进行描述，也不同于orb特征点对周边区域随机采样来建立二进制描述符，brisk算法通过以角点为中心40×40 像素块(见图2)内构建多个同心圆，对这些圆进行均衡配对。

图2 以角点为中心40×40像素块内的同心圆

图3为角点周边均衡选取采样点对，每一对点之间用红色实线相连表示。brisk特征点的方向是其在匹配过程中具有旋转不变特性的关键，其计算方法如下：

1) 求出角点周边区域的不变矩

(5)

2) 计算不变矩的重心

(6)

3) 计算特征点的方向，特征点的方向为中心角点同重心的连线所表示的方向，其同水平线夹角表示为

(7)

最后，生成二进制描述符。规则为按照周边采样点对先后顺序，若左边的点大于右边的点，则该采样对的值设为1；若小于右边的点，则该采样对的值设为0。根据选取采样对的数量及精度要求，一个特征点最终可由128位、256位或512位bit串来表示。

由于brisk特征点在计算速度及精度上显示出来的优越性，本文采用brisk特征点同camshift算法相结合的方法来进行运动目标的实时跟踪。

图3 以角点为中心周边采样点对

3 结合brisk特征点匹配的改进的camshift算法

针对camshift算法在相似颜色背景下由于误判导致跟踪丢失的问题，本文拟结合brisk特征点对camshift算法进行改进。改进的思路基于以下假设：首先，在大多数日常监控场景中，目标由远及近运动，或者由近及远运动，这样会导致目标尺寸大小的改变，但这种改变一定是平滑渐进的。在基于camshift算法的跟踪过程中，如果跟踪窗口的尺寸突然出现了大范围的变化，则有可能是因为出现局部极大值而导致搜索窗口出现错判，需要加以验证。其次，大多数情况下运动目标的移动速度及速度改变量也是平滑渐进的，如果目标运动速度过快，搜索窗口无法有效追踪目标，那么搜索窗口极有可能在当前窗口的背景区域内就近寻找概率密度最相似的背景区域，并把该区域误判为目标区域，从而导致跟踪窗口的尺寸出现较大变化或者跟踪窗口的位移量超过之前的平均值。为此，本文提出的改进方法是：通过搜索窗口内的brisk特征点匹配来对搜索窗口的大小和位置进行修正。

具体思路为：首先在每一帧跟踪窗口内先提取brisk特征点，并对跟踪窗口的尺寸及位移变化量进行记录；然后在任一帧中，当跟踪窗口的尺寸或位移变化量超过预设的阈值时，就把当前帧的brisk特征点同上一帧的brisk特征点进行匹配，以重新计算出当前跟踪窗口的大小和位置，并作为下一次camshift计算的输入参数。

3.1 特征点提取及匹配

对序列图像中每一帧中camshift的搜索框内,采用brisk算法提取特征点。

如图4所示，(a)为对行人目标进行特征提取；(b)为对运动中的车辆目标进行特征提取。通过合适的参数，brisk特征点检测方法能够在小尺寸的画面内提取足够多的特征点，以利于图像处理中后续阶段的分析和应用。

如图5所示，提取连续两帧搜索框内的特征点后，对其进行匹配计算并通过ransac算法剔除错误匹配对，保留正确匹配对Matches(left,right)。

图4 对运动目标提取特征点

图5 前后两帧搜索窗口内的特征点匹配

3.2 重新计算搜索窗口大小及位置

3.2.1 触发条件

为了防止跟踪误判，当前帧的搜索窗口尺寸同上一帧相比发生突变时，比如窗口面积变化大于10%或位移加速度超过20%(通过设定阈值T)时，根据当前有效匹配特征点计算投影变换矩阵，触发条件的公式表示如下：

条件1

(8)

其中：Sn为当前帧跟踪窗口面积；Sn-1为上一帧跟踪窗口面积；Ts为面积改变量预设阈值。

当前帧搜索窗口的位移(以窗口中心坐标为依据)变化速率改变大于一定阈值时(比如前几帧的平均位移量的30%)，重新计算并确定当前跟踪窗口大小及位置，公式表示如下：

条件2

计算绝对位移

(9)

计算位移改变量

(10)

其中：ΔP为当前跟踪窗口中心同上一帧的跟踪窗口中心的绝对位移量；Tp为预设的位移量改变阈值。当触发条件满足时，进行下一步计算投影变换矩阵并重新计算当前帧中跟踪窗口的大小及位置。

3.2.2 计算投影变换矩阵

Homography变换矩阵是一个3×3的单应性矩阵，用来描述图像A通过尺度、旋转、仿射变换到图像B后图像上各点的对应关系。当求得两幅图像中的匹配点Maches(left)、Maches(right)后，如果匹配点对数大于等于3，即可以计算出两幅图像之间的Homography变换矩阵H。

3.2.3 修正窗口大小及位置

计算出变换矩阵H后，就可以直接通过前一帧搜索窗口4个角的坐标，计算出修正后搜索窗口4个角的新坐标。其公式为：

corner2(x,y,1)=H×corner1(x,y,1)

(11)

3.3 简化的窗口大小及位置计算方法

考虑到帧与帧之间运动目标自身运动及环境影响导致的形状变化非常微小，对整个跟踪窗口的影响不大，如果采用传统的单映矩阵公式来计算需要耗费一定的计算资源。本文提出一种简化的方法重新计算跟踪窗口的大小及位置。

设当前帧跟踪窗口内的特征点集为Fn,前一帧窗口内为fn(Fn,fn均为经过滤后完全匹配的特征点)。前一帧跟踪窗口的宽、高分别为w，h,当前窗口的宽高分别为W，H,窗口旋转角度为θ。

(12)

(13)

(14)

通过以上公式，可以近似得到新跟踪窗口的大小，无需计算矩阵投影公式。该方法简单、计算速度快，其误差对新窗口在下一步camshift迭代运算的影响微小。

最后，把计算得到的新跟踪窗口的尺寸及位置作为下一次camshift迭代的初始化窗口，继续进行camshift运算。

跟踪算法流程见图6。

图6 跟踪算法流程

4 实验

为进一步验证本文提出算法的有效性，采用pets 2001 dataset 公开数据集，分别对dataset2视频中的行人和车辆的跟踪进行了测试。实验环境为华硕笔记本电脑、intel p3处理器、2GB内存、vs2010平台。

4.1 跟踪效果对比

主要对比原始camshift算法同本文改进的算法对目标跟踪的结果。

图7为使用camshift算法对测试视频中的车辆进行跟踪的结果。如图7所示，从2 530帧开始，由于受到背景停放车辆颜色相似的影响，搜索窗口在自适应过程中进行了错误的判定，导致目标跟踪失败。图8为采用本文算法的跟踪结果，通过采用特征点匹配进行窗口及位置的修正，有效避免了目标的错误判定。

图8 本文算法对车辆跟踪结果

图9为使用camshift算法对行人进行跟踪的结果。从第2 259帧开始，跟踪窗口受到背景颜色的干扰出现了错误的判定。图10为采用本文算法的跟踪结果，通过特征点匹配及窗口重修正，有效避免了跟踪错误。

图9 原始camshift算法对行人跟踪结果

图10 本文算法对行人跟踪结果

4.2 跟踪速度及精度对比

为比较算法的跟踪速度，本文采用结合不同特征检测算子对同一测试视频，同一跟踪目标在有效跟踪时段内每一帧的平均计算时间进行对比。如表1所示，通过对比可以看出：结合brisk特征点的算法在速度上超过surf特征点，但是会比orb特征点稍慢。

表1 结合不同特征检测算法跟踪速度对比

表2 不同算法跟踪精确性对比

为比较算法精确性，本文参考文献[15]中的运动目标轨迹精确性评估方法，提取运动目标在每一帧的质心坐标和跟踪算法中每一帧跟踪窗口的中心位置坐标，然后计算两者之间的距离，最后计算出各自总测试帧数的平均值进行比较。如表2所示，通过对比可以看出，本文提出的算法在跟踪精确性上比结合orb特征点的算法有明显的提高。

5 结束语

本文主要针对传统camshift算法的不足之处，结合最新的brisk特征点检测方法，提出了一种改进的camshift算法。当目标同背景颜色近似导致跟踪丢失时，能够通过特征点匹配的方式进行验证判断，并通过前后特征点集重新计算搜索窗口的尺寸及位置。但是，brisk特征点仅从灰度图像上寻找特征点，并且在运动目标尺寸过小或者序列图像清晰度不高的情况下，难以提取出足够数量有效的特征点实施检测，影响了特征匹配及搜索窗口修正的精确性。如何使本文算法具有更多的适应性是下一步研究的方向。

[1] LEUTENEGGER S, CHLI M, SIEGWART R Y.BRISK:Binary robust invariant scalable keypoints[C]//2011IEEE International Conference on Computer Vision.2011.Spain:[s.n.],2011:2548-2555.

[2] FUKUNAGA K,HOSTETLER L.The estimation of the gradient of a density function,with applications in pattern recognition[J].IEEE Trans Info.Theory,1975,21:32-40.

[3] CHENG Y.Mean shift,mode seeking,and clustering[J].IEEE Trans.Pattern Anal Machine Intelligence,1995,17:790-799.

[4] 张娟,毛晓波,陈铁军.运动目标跟踪算法研究综述[J].计算机应用研究,2009(12):4407-4410.

[5] 黄凯奇,陈晓棠,康运锋,等.智能视频监控技术综述[J].计算机学报,Chinese Journal of Computers,2015(6).

[6] YIN J,HAN Y,LI J,et al.Research on real-time object tracking by improved Camshift[Z].International Symposium on Computer Network and Multimedia Technology,Wuhan,2009:1-4.

[7] SUN L,WANG B R,IKENAGA T.Real-time non-rigid object tracking using CAMShift with weighted back projection[C]//International Conference on Computational Science and Its Applications.Fukuoka:[s.n.],2010:86-91.

[8] BRADSKI G R.Computer vision face tracking for use in a perceptual user interface[J].Intel Technology Journal,2nd Quarter,1998.

[9] QIU X N,LIU S R,LIU F.An adaptive kernel based target tracking method based on multiple features fusion[J].EEJ Transactions on Electrical and Electronic Engineering,January 2012,7(1):91-97.

[10]ELMAR MAIR,GREGORY D,HAGER,et al.Adaptive and Generic Corner Detection Based on the Accelerated Segment Test[J].Computer Vision-ECCV 2010 Lecture Notes in Computer Science,2010,6312:183-196.

[11]钟华民,王伟,张慧华.结合ORB特征和色彩模型的视觉跟踪算法[J].模式识别与人工智能，2005(1):90-96.

[12]YUNJI ZHAO,HAILONG PEI,HONGBO ZHOU.Improved Vision-Based Algorithm for Unmanned Aerial Vehicles Autonomous Landing[J].Journal of Multimedia,2013,8(2):90.

[13]SCHAEFFER C.A Comparison of Keypoint Descriptors in the Context of Pedestrian Detection:FREAK vs.SURF vs.BRISK[Z].International Journal of Computer Applications,2014.

[14]MIKSIK O,MIKOLAJCZYK K.Evaluation of Local Detectors and Descriptors for Fast Feature Matching[C]//Pattern Recognition (ICPR),2012 21st International Conference.Japan:[s.n.],2012.

[15]李鹏飞,陈朝武,李晓峰.智能视频算法评估综述[J].计算机辅助设计与图形学学报,2010(2):352-360.

(责任编辑 杨黎丽)

A Combination of Camshift Algorithm and Brisk Feature Point for Real Time Moving Target Tracking

CHEN Jia1,2, ZHU Chang-ren2, LUO Bin2

(1.ATR Key Laboratory, College of Electronic Science and EngineeringNational University of Defense Technology, Changsha 410073, China;2.The Fujian Province Armed Police Corps Directly Under Detachment Team,Fuzhou 350001, China)

In traditional camshift algorithm, when the target moves too fast or the background has similar color, it will lead to the loss of target easily, and how to maintain the effectiveness and continuity of the tracking becomes the direction for many researchers under various complex situations. Therefore, we proposed a improved camshift algorithm based on combination of camshift and brisk feature point and a simplified search window correction method, which prevent the emergence of a local maximum and the loss of tracking window with matching different frames on the goal of your brisk feature point. Experiments show that our method effectively improve the continuity and stability of target tracking. In combination with other feature points algorithm, it has better real-time comparison and accuracy

target tracking; camshift; meanshift; brisk feature point

2015-4-20 作者简介：陈佳(1983—),男,硕士研究生,主要从事图像处理与模式识别研究。

陈佳，朱长仁,罗宾.一种camshift算法与brisk特征点相结合的运动目标跟踪方法[J].重庆理工大学学报(自然科学版)，2015(12):112-119.

format：CHEN Jia, ZHU Chang-ren, LUO BinA Combination of Camshift Algorithm and Brisk Feature Point for Real Time Moving Target Tracking [J].Journal of Chongqing University of Technology(Natural Science)，2015(12):112-119.

10.3969/j.issn.1674-8425(z).2015.12.019

TP301.6

A

1674-8425(2015)12-0112-08