一种基于ORB 特征匹配和反投影直方图的目标跟踪方法

刘泓佚，常天庆，郝 娜，戴文君

(装甲兵工程学院，北京 100072)

目前的跟踪算法，如粒子滤波等，能以一定的精度跟踪发生形变的目标。但是这些算法计算量大，计算的复杂度高，进行长时间跟踪时跟踪效果差，经常丢失目标。因此本文采用ORB 特征匹配的跟踪方式，首先在视频中选取目标区域，提取这一区域以及每一帧视频中图像的ORB 特征，进行特征点匹配并连接相似的特征点，以此达到跟踪的目的，并保证一定实时性。

1 ORB 特征的相关理论

为了更好地描述物体，让计算机能通过特征点准确快速的发现和辨识目标，人们提出了很多特征点及描述符。从最初的HARRIS 角点，到SIFT、PCA-SIFT、GOLH、SURF，在2006年提出了FAST 算法，在2010年提出来了BRIEF 算法，2011年Ethan Rublee 等人使用结合了灰度质心法的FAST 特征和加入了方向信息的BRIEF 特征描述符，提出了ORB 算法，即oriented FAST and rotated BRIEF。

1.1 FAST 算法及其改进［1］

在图像中一个点的周围圆形区域中找到足够多的像素点，这些像素点跟中心像素点的差值都大于一个阈值时，这个中心点就是FAST 特征点，如图1 所示。ORB 算法中使用FAST-9，即圆形区域的半径为9。FAST 特征点的提取速度非常快，因此很受研究人员青睐。但是FAST 特征点不具有旋转不变性，因此ORB 算法采用了一种结合强度质心思想的FAST，即OFAST。

图1 FAST 特征

OFAST 在FAST 的基础上通过矩加入了主方向。一个区域内图像的矩的定义如下

通过矩的定义得到区域图像的质心

OFAST 特征点的方向定义为待测点与质心的夹角

其中atan2 是arctan 的象限感知。

1.2 BRIEF 算法及其改进

BREIF 算法用二进制的方式对图像区域进行表达，算法用τ 测试计算二进制描述子［2］。对于一个M ×M 的矩形区域Q，其τ 测试定义为

其中x 和y 表示形如(u，v)的二维坐标，而q(x)表示x 位置处的灰度值。

Brief 算法即是若干个随机选出点的τ 测试值组成的二进制bit 串:

BRIEF 算法抛弃了用直方图描述区域的方法，而是随机采点计算二进制描述子，极大的提高了描述子的建立速度，而且生成的二进制描述子也便于计算，便于在硬件上进行处理，这种二进制描述子的匹配效率非常之高，在很多情况下匹配效果超过了SURF。但是Brief 算法不具备旋转不变性，对噪声也比较敏感，因为τ 测试依靠灰度值，噪声容易对灰度产生影响，虽然在计算τ 测试前进行滤波处理，但是还是无法完全去除噪声的影响。

ORB 算法采用了rBRIEF 算法，它引入了方向信息以增加旋转不变性［3］。首先将n 比特的点集写成矩阵形式

根据Fast 算法得到的方向角θ 求出其对应的旋转矩阵Rθ，构建经过矫正的Sθ，Sθ=RθS，为原始BRIEF 加入了旋转不变性，新的描述点集为

1.3 特征提取的步骤

对于一个31 ×31 的图像，将所有的5 ×5 方块用oFAST算法检测关键点的位置以及关键点的角点方向。对每个子窗口检测到的二进制描述串求平均值，并根据均值与0.5 的偏差大小进行排序，将这些子窗口的二进制描述串存入到一个容器T 中，进行贪婪搜索算法［3］。

1)移出容器T 中的顶层的第一项，放入到一个结果容器R 中。

2)然后用容器T 的下一项与容器R 中所有的二进制描述串进行比较，如果它们之间的相关性大于一个阈值。则不必用这个含有冗余信息的描述串，否则将其添加到结果容器R。

3)重复1)、2)步骤，直到结果容器R 中有256 个二进制字符串。如果完成一次循环后容器中二进制字符串仍低于256 个，则提高相关性阈值，重新进行贪婪搜索，直到搜索到256 个二进制描述字符串。

2 ORB 特征的优势及特征匹配方案

2.1 ORB 特征的优势［4］

SURF、SIFT 和ORB 同样为性能优良的特征检测和描述方法。SIFT 和SURF 都使用了高斯金字塔，以及Hessian 变换，检测得到的特征有尺度和旋转不变性，而ORB 没有考虑尺度不变性，避免了耗时的高斯卷积，因此ORB 特征的检测和描述耗时最短。当目标图像像素大小为352 ×169 时的特征点提取结果及时间如图2 所示，提取SURF、SIFT 和ORB特征分别耗时27 ms、134 ms、20 ms。

当目标图像像素大小为1 280 ×720 时的特征点提取结果及时间如图3 所示，提取SURF、SIFT 和ORB 特征分别耗时264 ms、1 459 ms、54 ms。

图2 从左到右为SURF、SIFT、ORB 特征点检测和描述的结果

图3 从左到右为SURF、SIFT、ORB 特征点检测和描述的结果

2.2 ORB 特征的匹配方案

实现基于ORB 特征匹配的目标跟踪任务时，首先需要选定目标区域，分别计算目标区域和整个场景图像的ORB特征，然后分别对其进行描述，而后在每帧图像中将目标和场景的特征描述符进行匹配，标记出匹配点，达到跟踪的目的。匹配的质量影响跟踪的效果，因此匹配方式的选取很重要。最简单的匹配方式是暴力匹配。本文使用局部敏感哈希(LSH)算法。

暴力匹配是预先存储目标图像的特征，用每一个已知特征逐个的匹配待测图像中所有的特征，这种方法虽然计算量较大，但如果是对简单数据集进行匹配，计算时间较短。

LSH 方法的主要思想是将在特大数据集中找相邻元素的问题简化为新空间的哈希桶内找相邻元素的问题。具体的做法如下［5-6］:

1)对于一个向量，通过将欧式空间转换到汉明空间，得到其n 维的二值向量。

2)找到m 个符合一定条件的哈希函数，每一个函数都随机抽取二值向量中的k 位作为输入，并将输出结果(哈希值)保存。

3)计算样本库中所有向量分别经过m 个哈希函数作用的结果，将经过相同哈希函数作用且哈希值大致相同的不同向量放在新的位置(哈希桶)。

4)对待测向量进行匹配时，通过m 个哈希函数作用，根据哈希值，只需将对应的多个哈希桶中的元素取出进行比较。避免匹配与其相邻概率小的向量，从而提高了匹配效率。

局部敏感哈希算法中哈希桶的数量、随机抽取二进制向量的位数等会影响匹配效果，设置哈希桶个数为6，抽取的二进制向量位数为12。

2.3 仿真与对比

提取鼠标选中的目标区域，计算此区域与视频帧图像的ORB 特征，并进行匹配。选取了在野外录制的车辆视频进行跟踪，分别采用暴力匹配和SLH 匹配，如图4 和图6 所示，图5 和7 分别显示了匹配的时间。

图4 暴力匹配ORB 特征的效果图

图5 暴力匹配ORB 特征所用的时间

图6 局部敏感哈希法匹配ORB 特征

图7 局部敏感哈希法匹配ORB 特征的时间

3 基于反直方图投影的辅助跟踪策略

3.1 辅助跟踪策略

ORB、SURF 以及SIFT 描述符都是在灰度图像的基础上计算特征点，而后进行描述的，没有利用颜色信息，因此我提出一种基于反投影直方图的辅助跟踪策略，利用所选区域的颜色直方图对整个待处理图像进行相关性的重构。

一般直方图反投影的结果是一幅像素值在0 ～255 之间变化的灰度图［7］。亮度越高的地方代表这个区域与所选区域的相关度高，否则说明相关度低。为了利用这种灰度图像，进行了下述操作。首先通过设置阈值，将灰度图像2 值化，得到离散的黑白图像，然后用大像素的膨胀单元对黑白图像进行膨胀，尽可能使白色区域包含目标所在区域，并且去除白色区域中的噪点，最后用膨胀后的图像与原图像作与运算，得到了优化后的原始图像。对单个图像空间进行反投影、阈值分割、膨胀等上述操作，耗时约30 ms。对3 个空间进行上述操作并将结果叠加，耗时约60 ms。上述过程如图8所示。

图8 H 空间反投影直方图辅助跟踪的过程

3.2 ORB 特征点跟踪与反投影直方图相结合

在选取目标后首先对原始图像进行优化，而后提取目标区域以及优化后图像的ORB 特征进行匹配。下面对比了在反直方图的辅助下，暴力匹配和LSH 匹配的跟踪效果，如图9 和图11 所示，在每帧图像上应用上述两种方法消耗的时间分别如图10 和图12 所示。

图9 RGB 空间反投影辅助SLH 匹配ORB 特征的跟踪方法效果图

图10 反投影辅助LSH 匹配方法消耗的时间

图11 RGB 空间反投影辅助暴力匹配ORB 特征的跟踪方法效果图

图12 反投影辅助暴力匹配方法消耗的时间

4 跟踪结果的比较

TLD 和CT 算法是目前热门的两种优秀跟踪算法。TLD算法分为3 个模块，分别是跟踪、检测和学习。其中跟踪器是Lucas 光流跟踪器，它是基于两帧差分的光流估计方法。检测模块采用随机森林算法，它作为一种分类器，相比于其他算法有很大优势，它能处理维度很高(特征量很大)的数据，而且不需要对特征进行优化。学习模块采用PN 学习，用来对检测器产生的错误进行识别。上文中的视频用TLD 算法跟踪，处理每帧图像消耗约73 ms，但是随着跟踪时间的增加，当目标逐渐缩小时，跟踪失败，如图13 和14 所示。

图13 TLD 跟踪算法效果图

CT 算法是基于检测和学学习的算法，用稀疏矩阵对特征降维，用朴素贝叶斯分类器进行训练和分类，能对模板进行在线更新。待测视频采用CT 算法跟踪每帧耗时约40 ms，跟踪效果如图15 和图16 所示。当目标变小时跟踪失败。

而本文采用的方法在初始跟踪时有较好的效果，当目标变小时虽然特征的匹配线减少，但是目标始终显现。除此之外，图像的边缘产生了很多检测点，对结果产生了一定的干扰;设置的匹配门限不够合适，当目标大小变化时，匹配效果变差，这都是算法有待提高的地方。

图14 tld 跟踪算法效果图

图15 CT 跟踪算法效果图

图16 CT 跟踪算法效果图

5 结论

本文提出的反投影直方图辅助跟踪策略结合ORB 特征匹配的跟踪方法，既利用了颜色信息，又利用了灰度图中目标的特征，跟踪1 副1 080 ×720 的视频序列，每帧只需约200 ms。

［1］章杰.基于ORB 特征和粒子滤波的目标跟踪算法的研究［D］.长春:吉林大学，2014.

［2］孟凡清.基于背景差分法与ORB 算法的运动目标检测与跟踪算法研究［D］.北京:北京印刷学院，2014.

［3］刘铭.基于ORB 算法的双目视觉测量与跟踪研究［D］.哈尔滨:哈尔滨工业大学，2014.

［4］谢成明.基于ORB 特征的目标检测与跟踪的研究［D］.合肥:合肥工业大学，2013.

［5］史世泽.局部敏感哈希算法算法的研究［D］.西安:西安电子科技大学，2013.

［6］刘英帆. 基于局部敏感哈希的近似最近邻查询研究［D］.西安:西安电子科技大学，2014.

［7］Robert Laganière.Opencv2 计算计视觉编程手册［M］.北京:科学出版社，2013.