基于有效特征点的运动目标匹配跟踪算法

郑晓萌 ，张德海

（1.中国科学院国家空间科学中心，北京100190；2.中国科学院大学北京100049）

目标跟踪是计算机视觉领域的研究热点，并得到了广泛的应用。目标跟踪算法可以分为产生式和判别式两大类。产生式跟踪方法如文献[1-2]所示，首先采用生成模型来描述目标的表观特征，然后在后续的图像中找到与该模型最为匹配的位置作为目标的位置。然而由于采用包围框的形式对目标进行初始化，在对目标建模的同时包含了一定的背景信息，当目标变化剧烈或者被遮挡时容易产生偏移。判别式跟踪方法如文献[3]所示采用训练过的分类器来区分前景目标和背景信息。与产生式算法相比，判别式算法鲁棒性更强，性能更优[4-5]。但由于受到目标姿态变化、尺度变化、目标快速运动、被遮挡或者消失等因素的影响，判别式算法也会产生漂移。

为了解决漂移现象，Kalal等将目标跟踪与检测相结合，并引入在线学习机制，提出了TLD（Tracking-Learning-Detection）视觉跟踪算法，解决了传统跟踪算法中无法获取丢失目标，无法进行长时间跟踪的问题。但TLD中存在一些明显的不足，如跟踪器稳定性不高、检测器中检测窗口过多耗时长等。Supancic[6]等采用自组织学习的方法选择训练样本更新检测器，将SVM目标方程中得分较高的跟踪结果替换样本集中早期样本，建立更有效的样本集，降低了时间复杂度。但该算法在目标发生剧烈形变时，跟踪效果较差。Alahari[7]等采用离线的方式对目标运动的轨迹进行学习，估计目标的形变变化，但该算法无法有效处理目标的尺度变化。

针对以上算法中出现的问题，文中提出了一种基于有效特征点的自适应目标跟踪算法。首先采用有效特征点代表目标物体，保证目标能被可靠地跟踪，抑制了因跟踪背景中错误的特征点而导致跟踪结果漂移的现象。其次，采用马尔科夫方向预测器来预估目标的检测区域，在可靠检测的前提下，可以有效的缩小检测范围并增强跟踪器对相似目标轨迹的判别能力。

1 ORB算法

基于特征的跟踪采用一组特征集合来描述运动目标，通过在连续帧中搜索相应的特征集合来检索运动目标，实现跟踪[8]。在实际应用中，常选取一些具有不变性的局部特征进行目标跟踪，这类方法具有抗遮挡性和鲁棒性强等优点。SIFT和SURF是两种著名的特征检测算子，在图像旋转、尺度变化和视觉变化下都具有良好的不变性，但二者的运算较为复杂，实时性差，而FAST[9]（Features from accelerated segment test）特征点检测算子，单帧处理速度可达微秒级别[10]。ORB（Oriented FAST and Rotated Brief）算法 将 BRIEF（Binary robust independent elementary features）描述子与FAST特征点进行改进与结合，使其具有旋转不变性和噪声抑制特性。

1.1 特征点提取

Drummond等人认为在灰度图像中，若某像素点的灰度值比其邻域内足够多的点的灰度值大（或小）于一定阈值，则该点可能为图像的角点。图1为以像素点P为中心，以3为半径的离散化Bresenham圆形邻域模板，该圆的边界上有16个像素值。若P点的灰度值比连续n个点的像素值大于或小于阈值T，则点P可能是一个角点。

n值可取12或9，实验证明n取9的效果更好，因此本文采用FAST-9角点检测算法。上述算法中，对于图像中的每一个点，都需要遍历其邻域圆上的16个像素点，效率非常低。因此采用一种高效算法快速排除一大部分非特征的像素点。算法假设若某点为FAST角点，则其邻域圆上将有超过34的候选点满足判断条件。首先检测P点周围1、9、5、13四个位置的像素点中是否有三个点满足判断条件，若不满足，则该点不是特征点，若满足，则继续判断该点的邻域上16个点中是否有12个满足判断条件。

求出FAST角点后，利用Harris角点检测算法，选出FAST角点中响应值最大的N个点。由于FAST算法不能产生多尺度的特征点，因此采用空间金字塔模型，在金字塔的各层上采用Harris滤波生成多尺度下的FAST特征点。

图1 FAST特征点检测模板

1.2 特征点的方向

利用灰度质心[11]算法，对目标物体所在的目标框提取其形心，与FAST特征点结合构成OFAST[12]特征向量，将特征点和质心之间的偏移向量作为该特征点的方向，解决了FAST特征点不具有旋转不变性的问题。

Rosin定义邻域矩为

从特征点O到质心C间构建OFAST特征向量OC，作为该特征点的方向，其方向角θ的大小为：

为了提高方法的旋转不变性，需确保x和y在邻域半径为r的圆形区域内，即x,y∈[-r,r]。

1.3 特征点描述子

ORB算法采用具有旋转不变性的BRIEF[13]作为描述子。BRIEF描述子的实质是在特征点附近随机选取指定数量的像素点对，通过比较点对间的灰度值大小，组合编码成一个长度为N（一般N=256）的二进制字符串。BRIEF描述子的构建步骤如下：1）为了较少噪声干扰，先对图像进行平滑处理。

2）以特征点为中心，取S*S的邻域窗口。在窗口内选取一对（两个）M*M的子窗口，比较子窗口的像素和（可由积分图像求出），进行二进制赋值（一般S=31，M=5）。

其中p(x)，p(y)分别为两个子窗口的像素和。

3）在S*S的邻域窗口内选取N对子窗口，使其相关性最低，重复步骤2）进行二进制赋值，求出一个长度为N的二进制码串，这个码串就是该特征点的描述子。

BRIEF描述子由特征点周围的N对（2N个）子窗口生成，将这N对子窗口( )xi,yi，i=1,2,….,2n组成一个矩阵S:

为使BRIEF描述子具有旋转不变性，使用图像块旋转角度θ和相应的旋转矩阵Rθ，建立矩阵S的校正版本Sθ。

其中

θ为2.2中为特征点求得的主方向。

将式（3）中求出的特征点质心方向信息加入描述子中，加入方向后的特征描述子为：

2 有效目标点选取

2.1 特征点追踪

目标物体具有整体性，当其做平移运动时，目标上各点的运动情况相同，当目标旋转时，目标车辆瞬时加速度较小，速度不会发生较大变化，且LK[14]光流法要求相邻两帧图像间隔非常小（几十毫秒内），在此时间间隔内，可将旋转运动近似成平移运动。所以，同一目标上的特征点应具有相同的位移矢量。利用这个特性，可选出包围框内稳定的特征点。具体步骤如下：

1）对图像进行灰度处理，确定待跟踪物体的目标框boundingbox，并利用质心算法，求出第t帧中boundingbox的质心位置O(t)。

2）以O(t)为中心，划定一个矩形区域，令其为BoundingBox，其长宽比与boundingbox一致，大小是boundingbox覆盖面积的4倍。

4）用LK光流金字塔算法求出上述特征点在第t+1帧中的位置。并求出上述点的帧间位移

5）求出帧间位移中值dmed，将距离dmed过远的一半点删除，剩余点即稳定特征点。

2.2 特征点匹配

通过特征点描述子间的汉明距离大小来表示特征点之间的相似度，当距离大于某一阈值时，则认为匹配成功。特征点匹配的步骤如下：

1）求出第t帧中BoundingBox内的所有特征点的描述子，将它们作为database。

2）对第t帧中的BoundingBox进行检测区域预估确定它在第t+1帧中的位置。检测区域预估算法将在下一节中阐述。

3）求出第t+1帧中BoundingBox内的所有特征点描述子，与database进行匹配，每个描述子在database内寻找2个最佳匹配结果。其中稳定特征点的选取标准如下：

①若与背景中的特征点相匹配，则删除。

②若最佳匹配的匹配距离大于某一阈值，则删除。

③若最佳的匹配距离与次佳的匹配距离之比大于某一阈值，则删除该特征点。

2.3 特征点融合

由于噪声等外界因素的影响，经汉明距离匹配后可能存在伪匹配对造成误差。而且采用包围框对其进行初始化，会不可避免的引入背景信息，背景中的特征点会使跟踪逐渐产生偏移。但是，多数情况下，目标物体与背景环境中的特征点的运动方向不一致。

因此本文将跟踪和匹配后保留下的稳定特征点进行融合，得出能有效代表目标物体的目标点，减少了因跟踪背景中错误特征点而导致的跟踪窗口漂移的现象。上述算法框图如图2所示。

图2 有效特征点选取框图

3 基于马尔科夫模型的检测区域预估

通常对全局图像进行特征点检测时，会因检测区域过大引入一些消极目标，导致检测时间过长。此外，当目标区域中出现多个相似的目标，且这些目标在运动过程中发生重叠时，易出现跟踪失败的情况。因此，本文利用光流法预测出目标框质心位置，并加入马尔科夫方向预测器[15]，根据前一帧中目标物体的运动方向来预估当前帧中目标物体的运动方向，缩小特征点的检测范围。

3.1 马尔科夫方向预测

在视频序列中，可将目标物体的运动分解为水平和竖直方向上运动。所以，采用马尔科夫模型来分别预测目标在水平和竖直方向上的运动趋势。以竖直方向为例，令其状态空间为{1为上，0为下}。马尔科夫模型假设当前帧中目标的运动状态仅与上一帧中目标的状态和状态转移矩阵有关。令t时刻的状态转移矩阵Pt如下：

其中，st表示目标在t时刻的运动状态，状态矩阵Pt的每列之和为1。则由目标在t时刻的运动方向状态量及状态转移矩阵，可以预测目标在t+1时刻的运动方向如下：

式中，p(st=1)（p(st=0)）分别为目标在t时刻向上（下）的运动概率。若目标在t时刻向下运动，则令p(st=0)=1，反之，令其为0；若目标在t时刻上下方向上没有运动，则令p(st=1)=0.5；等式左端为预测的目标物体在t+1时刻向下或向上的运动概率，令概率大的那个方向为目标在t+1时刻的运动方向。

根据目标运动状态的估计，可以求出其状态转移矩阵如下：

式中，n0，n1表示在0～t时间内，视频中目标分别向下、上运动的帧数，n11（n00）表示在0～t时间内，目标在前一帧和当前帧中都向上（下）运动的帧数，n01（n10）表示在0～t时间内，目标在上一帧中向下（上）运动但当前帧中向上（下）运动的帧数。本文通过相邻两帧中目标中心位置在竖直方向上的差值来判断其向上（下）运动。

3.2 检测区域预估算法

在对图像进行特征点检测前，需要根据目标的运动状态预测出目标可能出现的位置范围，检测区域预估算法步骤如下：

1）利用灰度质心算法，求出第t帧中Bounding⁃Box的质心位置O（t），并利用LK光流法求出其在第t+1帧中的质心位置O（t+1）。

2）利用马尔科夫方向预测器，根据目标在第t帧中的运动方向分别预测出目标在第t+1帧中水平竖直方向的运动趋势。确定目标在第t+1帧中的大致范围。

4 实验结果及分析

4.1 实验环境及测试数据说明

硬件实验环境：Intel Core i5-4300U 1.90GHz CPU，NVIDIA GTX 950M显卡。

软件实验环境：Windows 10.0，Visual Studio 2013，opencv2.4.9。

文中采用了4个典型的视频序列对算法性能进行测试，并与TLD算法（参数为默认值，具体参考相应文献）进行对比。表1列出了所选测试视频的属性，基本涵盖了跟踪过程中常遇到的一些场景变化。图2为各视频序列在测试过程中的一些截图。本文将目标超过50%以上的遮挡或者90°以上的空间旋转视为“目标不可见”。

4.2 跟踪精度及运算速度

本文采用目标重叠率[16]overlap、综合评价指标F、平均误差衡量算法的跟踪精度。采用视频序列的总帧数与跟踪所用时间的比值即算法每秒处理的帧数fps衡量算法的运算速度。计算公式如下：

表1 视频序列信息

图3 视频序列测试截图

其中：RT表示跟踪得到的窗口，RG表示目标实际所在窗口，area为窗口面积。当重叠率大于0.5时

其中：P（precision）为准确率，是算法正确跟踪的样本数与总样本数之间的比值。R（recall）为召回率，是算法正确跟踪的样本数与总的正确样本数之间的比值，用来衡量算法的查全度。P和R的计算公式如下：

其中，Nall为含有目标的帧数，Ntrack为算法跟踪得到的帧数为正确跟踪的帧数。

平均误差为算法估测出的目标框与实际目标框之间的中心距离。实验结果如表2所示。

上述视频序列均存在目标的部分遮挡或完全遮挡，因此无法获得目标的连续轨迹。本文采用LK金字塔光流法对目标框质心的位置进行预测，并加入马尔科夫方向预测器，对目标物体的运动方向进行预测，缩小了检测区域的范围，较TLD算法的全局检测，具有更快的处理速度。同时，此方法可排除图像中相似目标的干扰，提高追踪器对相似目标的辨识能力，实验效果如图4所示。

表2 两种算法实验结果对比

TLD算法的跟踪模块在目标上均匀地选取点进行跟踪，这些点并不能有效的代表包围内的目标物体，而且采用包围框的方式进行初始化会不可避免的引入背景信息，导致目标中心误差越来越大[17]。本文将特征点跟踪和特征点匹配相结合，求出能有效代表目标物体的稳定目标点。抑制了因跟踪均匀选取的目标点和背景中错误的目标点而造成的跟踪结果偏移现象，尤其当目标快速运动或发生形变时，本算法较TLD算法具有更低的中心错误率。实验效果如图5所示。通过对上述实验结果的定量分析，本文算法在目标物体快速运动、遮挡或者消失、视野中存在相似目标、光照变化、目标大小和外观发生变化等情况都具有较高的跟踪精度和跟踪速度。

图4 CarChase跟踪效果图（左侧为TLD算法，右侧为本文算法）

图5 motocross跟踪效果图

5 结论

TLD算法和本文所提出的算法在长时间的视频序列跟踪中都具有良好的跟踪效果。本文将特征点跟踪和特征点匹配相结合[18]，得出能代表目标物体的有效特征点，并在多个视频序列上对TLD算法和本文算法进行了测试，实验结果显示，基于有效点的匹配跟踪算法具有更高的跟踪精度、处理速度和鲁棒性，尤其当目标快速运动或发生形变时，中心错误率明显降低，且具更强的对相似目标的辨识能力。在今后的工作中将对本算法做进一步改进，并将之运用在更多的数据集上进行测试，以实现对多目标物体的追踪。