改进ORB算法在单目视觉SLAM特征匹配中的应用

吕丹娅，姚剑敏，郭太良

(福州大学 物理与信息工程学院，福建 福州 350116)



改进ORB算法在单目视觉SLAM特征匹配中的应用

吕丹娅，姚剑敏，郭太良

(福州大学 物理与信息工程学院，福建 福州 350116)

针对单目视觉同步定位与地图构建问题对传统定向二进制描述符算法进行改进，结合快速鲁棒特征算法的思想，将尺度空间理论引入传统ORB算法中，同时根据机器人的运动先验信息，预测特征点的可能范围，避免在全局范围内对特征点的检测和匹配。实验表明，改进的ORB算法能显著提高匹配正确率，在多尺度方面表现出色，并能有效减少运算时间，平均耗时14 ms，处理速度约为传统ORB算法的1.3倍、SURF算法的10倍、尺度不变特征变换(Scale-invariant Feature Transform，SIFT)算法的26倍，适用于单目视觉SLAM问题。

SLAM；特征匹配；改进ORB；尺度不变性

单目视觉SLAM(Simultaneous Localization and Map-building)问题一直都是国内外研究的热点和难点。单目视觉SLAM通过在移动机器人上架设单一摄像头获取环境图像，从图像中提取特征点，在机器人移动过程中，将里程计获取的机器人运动信息与摄像头获取到的环境特征点的运动信息相融合，边构建环境地图边修正自身的位置信息，从而实现同步定位与地图构建[1]。图像特征匹配在单目视觉SLAM问题中十分关键，一旦匹配失误，很可能造成机器人定位失败，因此对图像特征匹配算法的鲁棒性要求较高。同时，由于是在机器人移动的过程中进行定位与地图构建，对算法的运算速度也有较高要求。

目前主要的图像特征匹配算法有[2]：SIFT算法、SURF(Speeded Up Robust Features)算法及ORB(Oriented Fast and Rotated Binary Robust Independent Elementary Features)算法。其中SIFT和SURF应用尤为广泛，它们的匹配精确度高，对多种图像变换都适用，但运算速度慢，无法适用于对实时性有较高要求的单目视觉SLAM问题。ORB算法[3]是目前最为快速的图像特征匹配算法之一，在光照鲁棒性方面有更加突出的表现，然而ORB算法不具有尺度不变性，这对于单目视觉SLAM问题是致命的。在机器人移动过程中，摄像头所拍摄的环境图像不断变化，图像上的环境特征尺度更是无时无刻不在变换。同时，以上3种图像特征匹配算法还存在一个共同的问题：当环境图像中存在相似度较高的区域时，容易出现误匹配[4]。这对单目视觉SLAM问题来说同样是致命的。

对此，Yanyan Qin等人在文献[5]中提出一种改进的ORB算法。该算法采用SIFT检测特征点，再使用ORB对特征点进行描述，根据Hamming距离与预设阈值的比较，实现特征点匹配。此算法有效改善了ORB的尺度不变性，但由于采用SIFT检测，算法复杂度增加，平均匹配时间比ORB增加了19.33 ms，同时，由于采用的是Hamming距离匹配，在特征点相似度较高的情况下匹配精度较低。Ye Zhu等人在文献[6]中提出，先对图像建立高斯尺度金字塔，在金字塔的每一层上分别进行ORB检测和描述，使用随机抽样一致性(RANdom SAmple Consensus，RANSAC)算法移除错误匹配对。该方法使ORB的尺度不变性有很大提高，匹配精度亦得到改善，但RANSAC的缺陷是其迭代次数没有上限，耗费大量的时间，若设置迭代次数上限，则可能得不到最优模型，甚至得到的模型是错误的，因此需要平衡精度和时间，并且匹配效果不稳定。由于RANSAC只留下符合其估计模型的匹配对，会漏掉大量正确但不完全符合模型的匹配对，匹配效率不高，且无法准确检测分布不均匀的匹配对。

针对以上问题和单目视觉SLAM这一特定应用，本文提出一种改进的ORB算法。结合SURF尺度不变性的思想，在ORB算法中引入尺度空间理论，使改进的ORB算法兼具尺度不变性和快速运算的特点。同时，根据机器人的运动先验信息，预测特征在下一帧图像中的位置，进行基于先验信息的匹配，降低误匹配率，也提高了匹配速度。

1 传统ORB算法

单目视觉SLAM问题一般采用SIFT和SURF作为图像特征匹配算法，然而这两个算法的时间复杂度较大，影响了系统的实时性。ORB的运算速度比SIFT快了两个数量级，比SURF快了一个数量级[3]，因此本文考虑在单目视觉SLAM中采用ORB算法做图像特征匹配。

1.1 原理

传统ORB算法[3，7]使用FAST算法检测图像角点。对图像中某一个像素p，若它周围邻域内存在连续的n个像素与它处在不同的区域，则认为该像素点p是一个角点，取角点为图像的特征点[8]，如图1所示。

图1 FAST角点检测

(1)

特征点邻域的质心坐标C为

(2)

则质心的方向定义为

(3)

θ为该特征点的主方向。

在计算特征描述子时，事先采用穷举算法训练出n个相关系数接近0.5的随机点对。将该组点对根据特征点的质心方向进行旋转，以保证描述子的旋转不变性。

将原始图像先经过高斯滤波以降低噪声的影响，然后采用如下准则生成二进制描述子

(4)

式中:(x,y)为旋转后的随机点对；p(x)为图像块p在像素点x=(u,v)处的灰度值。由此获得n位二进制比特串描述子

(5)

通常使用K近邻(K-Nearest Neighbor，KNN)[9]做特征匹配。在单目视觉SLAM问题中，假设系统已运行一段时间，使用拍摄到的特征点的信息构建了SLAM特征库。此时机器人运动，摄像头再获取到一帧图像。首先，将摄像头获取的图像中提取到的特征点与SLAM特征库中的特征点做K=2的双向K近邻匹配。即图像中的每一个特征点，都在SLAM特征库中找到与其匹配距离最近和次近的两个特征点，分别组成匹配对，反之亦然。匹配距离可以是Hamming距离。然后，采用以下方法筛选匹配对：剔除最近邻匹配距离/次近邻匹配距离>0.6的匹配对；剔除非对称的匹配对，即如果图像中的特征点A匹配SLAM特征库中的特征点B，但特征点B不匹配特征点A，则同时剔除特征点A和特征点B各自的匹配对，反之亦然；剔除相似度不够高的匹配对。

1.2 存在问题

由1.1小节分析可知，传统ORB算法使用FAST算法检测图像中的角点，而FAST检测到的角点不具有尺度信息，因此最终获得的特征点不具有尺度不变性。当特征点发生较大尺度变化时，传统ORB算法的匹配效果极差，如图2所示。对于特征点会不断发生较大尺度变化的单目视觉SLAM来说，传统ORB算法具有极大的缺陷。

图2 传统ORB算法在大尺度变化下的匹配效果

同时K近邻匹配只是对特征点的描述子进行比较，并不考虑特征点在图像中的位置。若图像中存在相似的区域，极易导致匹配失误，而单目视觉SLAM所拍摄的是室内环境图像，很难保证没有相似的区域。

2 多尺度ORB算法

针对传统ORB算法在单目视觉SLAM中存在的问题，本文在传统ORB算法的基础上，结合SURF的思想引入尺度空间，使得改进后的ORB算法具有尺度不变性。同时采用基于先验信息的匹配，根据机器人的运动先验信息，预测特征点在下一帧图像中可能分布的范围，在此范围内进行特征点的检测及匹配，避免了K近邻在整幅图像中进行的穷举式匹配，有效地降低了误匹配率，同时减少计算量。

2.1 SURF尺度空间

尺度空间理论是指在处理图像信息时引入一个尺度参数，通过图像尺度的变换，获得不同尺度下的一系列图像，在这一系列图像上进行处理[10]。

SURF算法[11-12]使用带尺度的Hessian矩阵求取局部最大值作为特征点。

(6)

为加速计算，使用盒式滤波器近似替代高斯二阶偏导数，如图3所示。

图3 盒式滤波器

使用不同尺度的盒滤波器与积分图像中的点卷积建立尺度金字塔，积分图像定义为：图像中某点(x,y)的值为原点与该点所围成的矩形区域中像素之和，其计算公式如下

(7)

2.2 改进ORB特征检测

由于机器人的运动、环境变化等等，单目视觉SLAM问题中获取到的图像会包含较多的噪声。因此，首先对图像进行高斯滤波，以减少图像中的噪声干扰。

改进的ORB特征检测采用积分图像和盒式滤波器进行卷积，通过高斯核函数构建尺度空间并求解快速Hessian响应提取特征点，并在特征点的3×3×3邻域插值，确定特征点坐标。为简化运算，此处的尺度空间为不分组的16层尺度空间结构。

为保证获取到数量足够的特征点，单目视觉SLAM问题通常采用角度较大的摄像头，镜头边缘畸变较大。为了提高特征点的稳定性，将靠近图像边缘的特征点剔除。

由此，在机器人运动过程中，不断地使用单目摄像头获取周围环境的图像，对图像进行改进ORB特征检测，获取稳定的特征点作为环境特征信息。

2.3 基于先验信息的匹配

当环境中存在相似区域时，使用K近邻会出现误匹配现象，因此本文针对单目视觉SLAM采用基于先验信息的匹配。由里程计获得机器人的运动信息，根据机器人的运动先验信息、摄像头参数、摄像头与特征点之间的位置关系，可以预测出某一特征点在下一帧图像中的位置。由于系统存在运动误差、测量误差等多种误差，必然无法精确预测特征点的位置。因此本文以特征点预测值为中心，计算出一个特征点实际位置的可能范围，下一帧图像中落在此范围内的特征点即为可能的特征点。再将这些可能的特征点与原特征点进行匹配，即可获得实际观测特征点。

本文使用EKF滤波器实现SLAM过程。假设机器人的状态变量为xk，特征观测变量yk=hk(xk)+vk，系统状态协方差Pk， 则

(8)

基于EKF滤波器的EKF-SLAM建立的是高斯模型[13]，所以状态变量服从正态分布

(9)

由于正态分布的传递性，特征点实际观测值zk亦服从正态分布

(10)

根据正态分布的参数估计理论可知

(11)

(12)

由此，基于先验信息的匹配范围确定为一个以特征点预测值为中心的椭圆，该椭圆表示特征点位置预测的不确定性，实际观测值落在此范围内的可能性为95%，如图4所示。

图4 基于先验信息的匹配

2.4 算法总体设计

本文针对单目视觉SLAM问题提出一种改进的多尺度ORB特征匹配算法，具体步骤如下：

1)对图像进行高斯滤波去除噪声。

2)建立尺度空间，使用带尺度的Hessian矩阵求取特征点。

3)去掉靠近图像边缘的特征点。

4)使用传统ORB的方法计算特征点的质心方向。

5)使用传统ORB的方法计算特征点描述子。

6)根据特征点预测值和测量余量协方差所构成的椭圆，进行基于先验信息的匹配。

3 实验结果与分析

本文采用的实验环境为Intel i5 2.67 GHz CPU，4 Gbyte内存，Windows操作系统，Visual C++ 2010。摄像头为170°广角摄像头，采用张正友法标定。图片原始分辨率640×480，裁剪为480×480。控制机器人使摄像头在室内做匀速直线运动，速度15 cm/s，每秒获取15帧图像，使用EKF-SLAM作为系统基本框架。

3.1 基于先验信息的匹配验证

图5为基于先验信息的匹配实际效果。图中展示的是当前图像中提取到的特征点与先前位置图像中提取到的特征点组合成的SLAM特征库的匹配效果。图中椭圆表示以特征点预测值为中心圈定的95%置信域，浅色椭圆表示正确匹配到特征点，所匹配到的特征点位置用十字标识。椭圆为深色表示没有匹配到特征点，原因有二：一是特征点实际观测值落在了椭圆外；二是由于在SLAM的过程中环境发生变化，当前图像中没有检测到这个特征点。从图中可以看出，绝大多数的特征点确实落在了圈定的95%置信域中，说明基于先验信息的匹配方案是可行的。

图5 基于先验信息的匹配效果

3.2 特征匹配实验

方法1采用本文提出的改进ORB算法，算法具有尺度不变性，并使用基于先验信息的匹配方法。方法2～4分别采用传统ORB[3]、SURF[11]、SIFT算法[14]，并使用K近邻匹配，方法5和方法6分别采用文献[5]和文献[6]中提出的改进ORB算法。特征匹配正确率由正确匹配对数/全部匹配对数得出，特征匹配正确率曲线如图6所示，特征匹配时间曲线如图7所示。

图6 特征匹配正确率曲线

图7 匹配时间曲线

由图6可知，本文提出的改进ORB算法在单目视觉SLAM这一应用场景下的特征匹配正确率高于其他5种匹配算法。方法2由于使用的是不具有尺度不变性的ORB算法，随着特征尺度变化的增大，匹配正确率持续下降。方法3～方法5由于使用的是与位置无关的匹配，随着SLAM过程的推进，特征点增多，特征点相似的概率增大，匹配正确率出现缓慢下降。图7展示了6种方法的匹配时间，方法1平均用时14 ms，比方法2平均快了4 ms，比方法3平均快了124 ms，比方法4快了353 ms，比方法5快了24 ms，比方法6快了51 ms。

4 小结

本文针对单目视觉SLAM问题，提出了一种改进的ORB算法。该算法结合SURF算法在传统ORB算法中引入尺度空间，实现了尺度不变性，同时根据机器人的运动信息，预测特征点在下一帧图像中的可能分布范围，有效地降低了误匹配率，并减少了计算量。

由实验结果可知，本文提出的改进ORB算法具有优秀的尺度不变性，当图像发生尺度变化时，改进ORB算法的匹配效果远远优于传统ORB算法，亦胜过SURF、SIFT和文献[5-6]中提出的改进ORB算法。同时，本文提出的改进ORB算法较好地保留了ORB算法运算速度快的优点，加之使用了基于先验信息的匹配，相比SURF，特别是SIFT，在速度上具有极大的优势，也比文献[5-6]中提出的改进ORB算法快。实际项目实验表明，改进的ORB算法在特征匹配正确率、运算时间上都有出色的表现，能很好地适用于单目视觉SLAM问题。

[1]孙凤池，黄亚楼，康叶伟．基于视觉的移动机器人同时定位与建图研究进展[J]．控制理论与应用，2010，27(4)：488-495．

[2]GAUGLITZ S，HOLLERER T，TURK M．Evaluation of interest point detectors and feature descriptors for visual tracking[J]．International journal of computer vision，2011，94(3)：335-360．

[3]RUBLEE E，RABAUD V，KONOLIGE K，et al．ORB： An efficient alternative to SIFT or SURF[C]//Proc. IEEE International Conference on Computer Vision(ICCV).Barcelona，Spain：Computer Vision，2011：2564-2571．

[4]索春宝，杨东清，刘云鹏.多种角度比较SIFT、SURF、BRISK、ORB、FREAK算法[J]. 北京测绘，2014(4)：22-26.

[5]QIN Y Y，XU H K，CHEN H R．Image feature points matching via improved ORB[C]//Proc. 2014 IEEE International Conference on Progress in Informatics and Computing．Shanghai：IEEE Beijing Section，2014：5．

[6]ZHU Y，SHEN X J，CHEN H P．Copy-move forgery detection based on scaled ORB[J]．Multimedia tools and applications， 2015， 75(6)：3221-3233.

[7]李小红，谢成明，贾易臻，等．基于ORB特征的快速目标检测算法[J]．电子测量与仪器学报，2013，27(5)：455-460．

[8]MIROSLAV T，MARK H．Fast corner detection[J]．Image and vision computing，1998，16(1)：75-87．

[9]HWANG W J，WEN K W．Fast KNN classigication algorithm based on partial distance search[J]．Electron letters，1998，34(21)：2062-2063．

[10]胥斌．图像多尺度不变特征研究及其应用[D]．重庆：重庆大学，2013．

[11]BAY H，ESS A，TUYTELAARS T，et al．SURF： Speeded Up Robust Features[J]．Computer Vision and Image Understanding (CVIU)，2008，110(3)：346-359．

[12]纪利娥，杨风暴，王志社，等.图像配准中特征点检测算法的探讨[J].电视技术，2013，37(19)：27-31.

[13]CIVERA J，GRASA O G，DAVISON A J，et al．1-Point RANSAC for extended Kalman filtering：Application to real-time structure from motion and visual odometry[J]．Journal of field robotics，2010，27(5)：609-631．

[14]LOWE D G．Distinctive image features from scale-invariant keypoints[J]．International journal of computer vision，2004，60(2)：91-110．

吕丹娅(1990— )，女，硕士生，主研计算机视觉、图像处理等；

姚剑敏(1978— )，博士，副研究员，硕士生导师，本文通信作者，主要从事图像处理、模式识别、三维显示技术等研究；

郭太良(1963— )，研究员，博士生导师，主要从事图像显示等研究。

责任编辑：闫雯雯

Improved ORB algorithm for monocular vision SLAM

LÜ Danya， YAO Jianmin， GUO Tailiang

(CollegeofPhysicsandInformationEngineering，FuzhouUniversity，Fuzhou350116，China)

In order to make traditional ORB algorithm suitable for the monocular visual SLAM， an improved ORB algorithm is proposed， combines the traditional ORB with SURF by added the scale space to the traditional ORB， and predicts possible position range of feature points according to the movement of the robot to avoid calculation in the global scope. Experiments show that the improved ORB algorithm can significantly improve the correct matching rate and has good scale invariance. The improved ORB algorithm effectively reduces the operation time， the average time of which is 14 ms， and processing speed is about 1.3 times of the traditional ORB， 10 times of SURF， 26 times of SIFT， it is very suitable for the monocular vision SLAM.

Simultaneous Localization and Map-building； feature matching； improved ORB algorithm； scale invariance

吕丹娅，姚剑敏，郭太良. 改进ORB算法在单目视觉SLAM特征匹配中的应用[J]. 电视技术，2016，40(11)：107-111. LÜ D Y， YAO J M， GUO T L. Improved ORB algorithm for monocular vision SLAM [J]. Video engineering，2016，40(11)：107-111.

TP391

A

10.16280/j.videoe.2016.11.022

国家“863”重大专项(2013AA030601)；国家自然科学基金项目(61101169)

2016-01-18