一种基于特征点的快速跟踪算法

刘雪琴，杨 媛，李 洁，宋焕生，b

(长安大学a.信息工程学院;b.陕西省道路交通智能检测与装备工程技术研究中心，陕西西安710064)

随着监控系统的逐渐应用，视频检测技术迅速发展，交通事件检测、交通参数检测和交通状况检测等算法研究具有广阔的研究背景。所以利用目标跟踪算法获取车辆的准确位置和运动轨迹线，并为交通事件检测、交通参数检测和交通状况检测提供可靠的基础数据成为国内外专家研究的热点。

目前常用的目标跟踪算法有基于区域的跟踪、基于活动轮廓的跟踪和基于特征的跟踪等。基于区域的跟踪［1］方法的主要思想是利用区域的时间相关性来实现目标的跟踪，就是在时域上检测出的一个个像素连通块，这些块组成矩形模板，然后实现跟踪。这种方法对于单目标跟踪效果很好，对于多目标跟踪，则相对复杂一些，而且需要消耗较多的时间。基于活动轮廓的跟踪［2－4］是利用封闭的曲线轮廓来表达运动目标，并且在后续帧图像中更新轮廓来达到目标连续跟踪的目的。相对于基于区域的跟踪，此方法减少了算法复杂度，但是合理地区分多个运动目标并实现轮廓曲线的初始化是十分困难的。基于特征的跟踪方法［5］是利用相邻帧中运动目标的个体特征的匹配来实现跟踪。与基于区域的跟踪方法的不同的是基于特征的跟踪方法使用运动目标的某一个或者多个体特征作为相关时的对象。用于匹配的个体特征可以是全局特征，如运动目标的周长、面积、质心等，也可以是线段、角点等局部特征。基于特征的跟踪方法比较简单，但计算量大，实时性差［6］。

本文提出了一种基于特征点的快速跟踪算法，能够快速地实现运动初始化，准确提取特征角点，快速匹配，实现稳定跟踪。

1 算法介绍

本算法是基于特征点的跟踪算法，主要包括特征角点提取和特征匹配两个过程。

1.1 运动目标检测

通过运动目标检测提取出图像序列中的运动信息，可以限定特征角点的提取范围，减少计算量。本文选择对光线等场景变化不太敏感的帧间差分法［7－8］来检测运动目标。帧间差分法主要是利用当前帧与之前相邻帧的像素差值来确定运动区域。有运动目标的区域，像素灰度变化较大，没有运动目标的区域，像素灰度变化较小，以此来区分。

图1是基于块的帧差法检测到的运动目标区域。

图1 帧差法的运动目标检测

图1是用当前帧(k帧)与之前相隔3帧(k－3帧)的图像差分而得到的目标区域，可以看到，由于车辆在k－3帧时的位置相对于k帧滞后，则k－3帧车尾处在当前帧上已成路面，检测到的运动区域正好包含了这部分路面，如图1b中方框所示。误选的路面区域会对角点提取产生影响，有时选择的角点就是在路面上。

为了尽量将检测到的区域定位在车辆身上，为防止误选，更准确地分割出运动车辆，将两次帧差结果相与来判断运动目标。具体表达式为

式中:fk(x，y)，fk－i(x，y)和fk+i(x，y)分别代表第k帧图像、第k－i帧图像和第k+i帧图像;Dk(x，y)表示第k帧图像与第k－i帧图像帧差结果;Sk(x，y)表示第k帧图像与第k+i帧图像帧差结果。

式中:T是二值化设定的阈值。处理结果如图2所示。

图2 改进后的帧差法效果图

上述处理结果说明将两次帧差结果相与，能够消除误选中的路面，更准确地进行运动车辆检测。

1.2 角点提取

得到运动区域后，对其进行角点提取。目前常用的角点提取算法有Sobel和Moravec等算法。

1)Sobel算法［9］

Sobel算法是一种快速的边缘提取算法，包含横向和纵向两组的3×3模板，通过与图像数据做平面卷积，得到横向与纵向的灰度差值变化，来检测边缘变化情况。其横向和纵向模板如图3所示。

图3 Sobel算法模板

Sobel算法抗噪性能差，容易选中伪角点，而且不能保证选中角点具有良好的可跟踪性。图4中只有一个角点，该角点位于车辆前端与道路的临界处，对它进行跟踪，发现轨迹线并不光滑，说明这个角点不适合作为跟踪初始点。

图4 Sobel算法提取到的不稳定跟踪点

2)Moravec 算法［10］

Moravec是一种利用灰度方差提取角点的算法。主要思想为:以像素点(x，y)为中心确定大小为w×w的窗口(如5×5的窗口)，如图5、图6所示。

图5 Moravec检测窗

将图6与图4相比，Moravec算法没有在车辆前端提取角点，而是在车身上提取了3个角点，这3个角点比So-bel算法提取的角点更加稳定。所以本文选取Moravec算法进行角点检测。

图6 Moravec算法提取角点及跟踪效果

1.3 构造模板

传统的匹配模板使用以角点为中心的一整块矩形区域的灰度数据来构造，常常是将平滑区域与不平滑区域都包含了进来。这种模板需要记录的信息少，使用方便，但是会导致后续跟踪计算量大。因此，本文使用一种改进的模板。

改进的模板在基本模板的基础上，去掉平滑区域，只用不平滑区域来构建模板。将整个模板分成5×5个小块，采用分层处理，并使用外螺旋顺序进行标记，以块1为中心，块2～块9为内层，块10～块25为外层，如图7所示。

图7 模板示意图

对于新建的结构化模板，选取6个小块构建新的模板。对于这25个小块。理论上认为越靠近中心块的小块，对跟踪影响越大，因此尽可能选取靠近中心的小块。新的模板保留中心块块1，在内层8个块中选取3个，外层16个块中选取2个。

除中心块外，其他5个块的选择采用改进的角点选择算法，也就是对其他24个块运用公式计算每个块的角点度量值，然后分别对内层和外层的各个块进行比较，分别留下角点度量值最大的3个和2个块。

改进的模板表示方法相对于基本的模板表示方法来说，减少了跟踪匹配计算至少19/25的时间消耗。为车辆的实时跟踪提供了必要的条件。

1.4 匹配搜索

本文使用块匹配跟踪算法，块匹配跟踪算法对运动模板跟踪的思想［11］是:对于第N－1帧图像中的角点(x1，y1)，在其周围一定区域内构造一个匹配模板template1，在当前帧(第N帧)图像上的一定范围(成为匹配窗)内按照一定的匹配准则搜索和该模板最接近的模板template2(称为预测模板)，那么就认为该模板的中心位置(x2，y2)为前一时刻的模板移动后现在的新位置。如图8所示。

图8 块匹配跟踪算法示意图

搜索策略使用全搜索法。全搜索法，即对搜索范围内的所有位置依次进行计算，选择与模板最相似的小块作为匹配块，该方法计算量大，但是精确度最高。

待匹配小块与目标模板的相似性由匹配准则得到。匹配准则选取了运算次数小且运算复杂度低的SAD算法。表达如下

式中:f(i，j)表示待匹配块中(i，j)位置处像素的灰度值;g(i，j)为模板中(i，j)位置处像素的灰度值。

起始搜索位置为角点的当前位置，搜索范围为以角点为中心的一个一定宽度的正方形区域。如果跟踪目标进行频繁的不规则运动，这样的搜索窗设置是恰当的。但是本文跟踪的运动目标是道路上行驶的车辆，其运动路线和方向都是有一定规律的。这样，再选择这样的设置，就会在非目标区域做了很多的无用工作，所以考虑利用过去时刻角点的位置和运动矢量，来对当前时刻匹配角点的大概位置进行预测，以预测结果来设置初始搜索位置和搜索窗，这样至少可以将搜索窗缩小到原来的1/4，相应地至少可以减少3/4的时间消耗，提高实时性。

当稳定跟踪得到一定数量的匹配点后，可以对目标进行预测。根据最近几帧的n个匹配点之间的距离预测下一帧的匹配点，公式如下

式中:dis_x和dis_y为最近几帧的n个匹配点之间的横向距离和纵向距离;block［k］.position［count］为第k条轨迹的第count个匹配点的位置信息;predictx和predicty为x和y方向预测值。

预测结果显示了新匹配点最可能出现的位置，则搜索范围可以相应地缩小到包含预测点的小范围区域中，减少了计算量和时间消耗。如图9所示。

图9 改进的搜索范围示意图

2 实验结果

本文给出了几种不同的场景(见图10)对本文的算法进行验证。第1种场景摄于下午，图像较为清晰;第2种场景摄于傍晚，且为阴天天气，图像较暗，对比度不高;第3种场景摄于隧道内，图像比较清晰;第4种场景摄于雨雾天气，图像清晰度低，噪声干扰较大。

图10 不同场景下跟踪结果

由4种场景中的跟踪轨迹可见，运动本文的算法能够在不同场景下实现运动目标的实时有效跟踪，跟踪效果准确度高，本算法对噪声、夜晚环境、雾雪等环境具有良好的鲁棒性。

3 总结

常用的跟踪算法时间复杂度大、实时性差，本文提出的一种基于特征点的快速跟踪算法，有效解决了这个问题。本文在基础算法上，采用两次帧差结果相与来进行运动检测，为更准确地提取角点提供有了有利条件;为提高跟踪的准确性和实时性，利用不平滑区域来构造模板;最后针对该方法的计算量大、实时性差的缺点，使用了目标匹配点预测算法，并根据预测点缩小搜索范围，减少运算量，提高搜索效率和实时性。实验表明，该算法能够克服计算量大、实时性差等缺点，并能得到较好的跟踪效果，为后续处理提供可靠的数据。

［1］ GU C，LEEM.Semiautomatic segmentation and tracking of semantic video objects［J］.IEEE Trans.Circuits and Systems for Video Technology，1998，8(5):572－584.

［2］ PARAGIOSN，DERICHE R.Geodesic a tive contours and levelsets for the detection and Tracking of moving objects［J］.IEEE Trans.Patern A-nalysis and Machine Intelligence，2000，22(3):266－280.

［3］ BERTALMIO M，SAPIROO G，RANDLL G.Morphing active contours［J］.IEEE Trans.Patern Analysis and Machine Intelligence，2000，22(7):733－737.

［4］ PETERFREUND N.Robust tracking of position and velocity with Kalmans nakes［J］.IEEE Trans.Patern Analysis and Machine Intelligence，2000，22(6):564－569.

［5］ ZHOU H，YUAN Y，SHI C.Object tracking using SIFT features and meanshift［J］.Computer Vision and Image Understanding，2009，113(3):345－352.

［6］丁艳，金伟其，薛雪.基于加权相关的图像匹配跟踪算法研究［J］.弹箭与制导学报，2009，29(4):58－62.

［7］ WANG J，WANG D.Particle swarm optimization with a leader and followers［J］.Progress in Natural Science，2008，18(11):1437－1443.

［8］ LONGW，YANG Y.Stationary background generation:an alternative to the difference of two images［J］.Pattern Recognition，1990，23(12):1351－1359 .

［9］江雯，陈更生，杨帆，等.基于Sobel算子的自适应图像缩放算法［J］.计算机工程，2010，36(7):214－216.

［10］卢瑜，郝兴文，王永俊.Moravec和Harris角点检测方法比较研究［J］.计算机技术与发展，2011，21(6):95－100.

［11］刘海华，雷奕，谢长生.基于块匹配的运动估计搜索算法研究与实现［J］.计算机应用，2006，26(6):1354－1364.