一种基于改进ORB的视觉SLAM图像匹配算法

张 洋， 吕 强， 林辉灿， 马建业

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

一种基于改进ORB的视觉SLAM图像匹配算法

张 洋， 吕 强， 林辉灿， 马建业

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

针对传统尺度不变特征变换(Scale Invariant Feature Transformation,SIFT)和加速鲁棒特征(Speed-Up Robust Feature,SURF)算法在视觉同步定位与建图(Simultaneous Localization And Mapping,SLAM)系统中耗时严重的问题，基于ORB(ORiented BRIEF(Binary Robust Independent Elementary Features))算法提出了一种改进的图像匹配算法。针对FAST(Features from Accelerated Segment Test)特征检测算子易受图像模糊和距离变化影响的缺点，建立了多尺度空间金字塔；针对BRIEF特征描述算子效率不高的问题，采用精简后的快速视网膜特征描述算子构建了特征向量；通过最邻近的交叉匹配对特征向量进行了提纯，采用顺序采样一致性算法剔除了错误匹配对。最后，通过与SIFT、SURF和ORB算法进行对比验证了改进算法的有效性。

视觉SLAM；FAST； 特征点检测； 特征匹配

视觉同步定位与建图(Simultaneous Localization And Mapping，SLAM)采用获取到的图像作为唯一的外部信息以估计机器人、相机的运动，同时构建环境地图。而视觉SLAM图像匹配算法又是地图探测、位姿调整过程中的核心问题，其主要分为基于区域的方法和基于特征的方法[1]。由于基于特征的方法对噪声、旋转、尺度变换、光照以及灰度变化等外界干扰具有更好的鲁棒性[2]，因此获得越来越广泛的研究和应用。Lowe[3]提出了尺度不变特征变换(Scale Invariant Feature Transformation，SIFT)特征检测算法，在图像进行不同尺度缩放时检测特征，实现了特征检测对尺度变化的适应性；Bay等[4]提出的加速鲁棒特征(Speed-Up Robust Feature，SURF)在SIFT的基础上运用harr图像进行积分求导，采用不同尺度的箱体滤波器与图像卷积，大大降低了计算消耗，提高了鲁棒性和计算速度。但是，SIFT和SURF特征匹配算法均难以满足对实时性要求高的应用场景需要。Rublee等[5]提出了ORB(Oriented BRIEF(Binary Robust Independent Elementary Features))特征匹配算法，计算速度比SIFT、SURF算法提高了1～2个数量级。

ORB算法是建立在FAST(Features from AcceleratedSegment Test)特征检测算子[6]和BRIEF特征描述算子[7]基础之上的特征匹配算法，近年来广泛应用于对实时性要求高的视觉SLAM系统中[8]。其特征描述算子采用了基于像素点灰度值比较的方法，通过得到的二进制位串来描述特征，比SIFT和SURF算法采用浮点运算的局部特征描述算子具有更高的实时性。然而，由于ORB算法中FAST特征检测算子缺乏对尺度变化的适应性，当待进行特征检测的图像尺度发生变化时，检测效果会下降；另外，BRIEF特征描述算子在建立特征描述向量时效率也不高。因此，笔者基于ORB算法提出一种改进的视觉SLAM图像匹配算法，并通过与SIFT、SURF和ORB算法进行对比来验证该算法的有效性。

1 ORB图像特征匹配算法

1.1 FAST特征检测算子

FAST角点定义为：若图像中某像素点灰度值比其周围邻域内足够多的像素点灰度值大或小，则将该像素点判定为候选特征点[6]。图1为FAST特征点检测示意图，具体方法如下：

图1 FAST特征点检测示意图

1)从图中选取一个像素点P，其灰度值设为IP；

2)设定一个合适的阈值t；

3)考虑以P点为中心、半径为3像素的离散化Bresenham圆，其边界上有16个像素点；

4)如果在该圆上有12个连续像素点灰度值都比IP+t大或IP-t小，则判定P点为一个特征点；

5)为加速判定过程，先计算序号为1、5、9、13的4个像素点，其中至少要有3个满足阈值条件，才进一步检测圆上其他像素点，否则丢弃P点。

据此，建立一个特征点的判定函数：

(1)

(2)

式中：Ix为圆周上任一点x处像素点灰度值；S为所有圆周点与点x特征点判定函数值的和，当S=12时，FAST算法检测到的特征点结果最准确。

为了使特征点适应旋转变化，ORB算法通过强度中心方法为FAST特征点增加一个主方向，使其成为具有方向的FAST特征点(oriented FAST，oFAST)：首先在特征点的局部图块区域中确定出强度中心；然后从特征点P到强度中心构建一个方向向量。局部图块区域的p+q阶几何矩为

(3)

式中：I(x,y)为点(x,y)处的灰度值。

点(x,y)在半径为r的圆形图块区域中，得到图块区域的强度中心为

C=(m10/m00,m01/m00)，

(4)

式中：m00为零阶矩；m01、m10为一阶矩。

于是，特征点与强度中心之间的夹角θ定义为FAST特征点的主方向：

θ=atan2(m01,m10)。

(5)

式中：atan2表示四象限的反正切函数。

1.2 BRIEF特征描述算子

BRIEF用于对已检测到的特征点进行描述，它是一种二进制编码的描述算子。BRIEF算法从以FAST检测出的特征点为中心的图块区域内任意选择2个像素点a、b作为一对，利用高斯分布采样方式随机选取k组点对，通常令k=256，并对每个点对的像素灰度值进行二值化比较，每个比较结果按位存储，得到一个k位的二进制位串(即BRIEF特征描述算子)。对一个经过高斯平滑过的图像块B定义一个二值比较函数τ：

(6)

式中：p(a)、p(b) 分别为随机点a、b的像素灰度值。

对选取的k对随机点重复式(6)的步骤，得到一个二进制编码位串：

(7)

然而，得到的BRIEF特征描述算子对噪声敏感且对图像的旋转适应能力不强。为了增加ORB算法抗噪能力和对图像旋转变化的适应性，采用积分图的方法对特征点周围31×31像素区域中随机选取的5×5像素子区域求取像素灰度值的和，采用比较子区域像素灰度值之和的方法来代替比较像素点对灰度值的方法。

1.3 特征点匹配

经过BRIEF特征描述算法处理后，每幅图中的每一个特征点都得到了一个256位的二进制位串。每2幅图像之间的配准通过计算目标图像与匹配图像所有特征点的特征向量间的Hamming距离D(Vp1i,Vp2j)来完成，其中：Vp1i为目标图像中特征点p1i的特征向量；Vp2j为匹配图像中特征点p2j的特征向量。2幅图像中特征向量对应位上相同元素个数最多的特征点构成匹配对。

2 多尺度空间检测的改进匹配算法

根据以上分析发现：1)FAST特征检测算子解决了旋转变化适应性，但不具备尺度变化适应性，这将会导致图像尺度发生变化时特征点匹配率降低；2)BRIEF特征描述算子在特征点邻域内采用随机选取点对构成特征描述向量，这种描述特征的采样点对效率不高；3)特征向量匹配无法去除非同一区域的错误匹配。针对以上问题，笔者提出了多尺度空间检测的改进匹配算法。

2.1 建立多尺度空间金字塔算子

笔者通过采用高斯金字塔[3]对oFAST检测算法加入尺度信息进行改进。多尺度空间金字塔的建立过程如下：

构造n个外层(ci)和n个内层(di)，i=0,1,…,n-1，一般地令n=4。假设有图像Img，c0层为Img原图像，ci层为ci-1层的2倍降采样；d0层为Img的1.5倍降采样，di层为di-1层的2倍降采样。因此ci、di层以及原始图像的尺度关系为

s(di)=1.5×s(ci)=1.5×2i。

(8)

首先利用式(1)、(2)对每层图像进行FAST检测，判断出候选特征点；然后对每层图像进行空间上的非极大值抑制。候选特征点及其邻域点如图2所示，候选特征点一维邻域(该层8个邻域点)和三维邻域(上、下层共18个邻域点)共26个邻域点的FAST得分值应最大，否则不能当作候选特征点。在本层以及上、下2层邻域对候选特征点进行极值检测，最后通过式(3)-(5)赋予特征点主方向。

图2 候选特征点及其邻域点

多尺度空间金字塔不对每层图像采用高斯核进行模糊处理，仅对原图像进行降采样，然后在特征点的邻域检测极值，因而其检测速率比在原始的差分高斯金字塔下进行特征检测要快。通过在多尺度空间金字塔下进行特征检测，不仅保留了oFAST检测算法对旋转和光照变化的适应性，而且由于增加了对尺度变化的适应性，检测到的特征点更加稳定。

2.2 改进视网膜特征点描述算子

视网膜特征点描述算子[9]是一种通过模拟人眼视觉神经元感受视景的方式来获取特征点信息的描述算子，其具备对旋转、光照和仿射变化的适应性。笔者对FAST算子建立多尺度空间后，通过模仿人眼视网膜的成像特点来选取点对描述特征点，采取接收图像信息更接近于人眼视网膜的采样模型，缩短了构建描述算子的过程，并且使其具有在特征点周围集中采样的性质。传统的视网膜特征点描述算子由8层43个采样点构成，如图3所示。

精简后的模型为6层结构，包含31个采样点，如图4所示。该模型展示了人眼视网膜拓扑结构，Fovea区域主要对特征点附近高精度的图像信息进行处理；Para和Peri区域主要对周围低精度的图像信息进行处理。该模型是由很多大小不同且有重叠的圆构成，中心点是特征点，采样点均匀分布于以特征点为圆心的同心圆上，靠近中心点的采样点更密集，离中心点越远，采样点越稀疏。

图3 视网膜特征点采样模型

图4 精简后的采样模型

在采样模型中采样点为6、6、6、6、6、1，其中1为中心的特征点。经过多尺度oFAST特征点检测后，利用精简后的视网膜采样模型构建特征点描述算子：

(9)

(10)

为了让生成的特征点描述算子更具有辨识度，笔者对特征点描述算子D进行维度处理，具体如下：

2)对矩阵M每一列计算均值，由于M的元素由0和1构成，均值越接近0.5，说明该列方差越大，对所有列按照方差从高到低进行排序；

3)为了便于计算，选取前256列作为最终的特征点描述算子。

经过以上维度处理和各列方差排序后发现：低维度的高方差列由特征点描述算子外侧的采样区域获得；高维度的低方差列由特征点描述算子中心的采样区域获得。而高方差代表模糊信息，低方差代表细节信息，与人眼视网膜相似，人眼先处理模糊信息，再处理细节信息，由此可知：描述算子外侧区能够获得目标的轮廓信息；描述算子中心区能够获得目标的高精度信息。

视网膜描述算子自身的圆形对称采样结构使其具有对旋转变化的适应性；采样点的位置和半径随着尺度的变化使其具有对尺度变化的适应性；采样点的像素强度对比使其具有对光照变化的适应性。因此，所构造的二进制特征点描述算子能够很好地进行特征匹配。

2.3 特征描述向量的分级匹配

所构建的精简视网膜特征描述向量是256位的二进制位串，对2幅图像特征点的特征描述向量间进行Hamming距离D(Vp1i,Vp2j)的计算，设置一个判断匹配点是否为内点(符合匹配条件的匹配点)的误差阈值ε，当D(Vp1i,Vp2j)<ε时，它们被认为是一组匹配的特征点。ε需要合理设置，太大会造成误匹配增加，太小可能无法得到匹配结果，ε值最终由实验确定。由于特征矩阵M的列按照方差从高到低排序，因此可以先把M的列分为维度相等的2级，再进行匹配比较。先对描述算子的前128位进行第1级匹配，计算其Hamming距离，如果距离小于阈值ε，则继续对后128位进行第2级匹配；如果距离大于阈值ε，则认为是错误匹配。这种分级匹配的方法可以通过前128位的匹配筛除掉90%的错误匹配，加速了匹配过程。

2.4 剔除错误匹配点对

特征描述向量经过分级匹配之后仍会存在错误匹配，为此，笔者对特征点的特征描述向量进行基于Hamming距离的2-NN交叉匹配，以剔除2幅图像中不在同一区域的错误匹配点对。经过交叉匹配后，对匹配点对的质量进行打分，按照得分进行排序，选取最小采样子集，采用顺序采样一致性(PROgressive SAmple Consensus, PROSAC)算法[10]取代传统的随机采样一致性(RANdom SAmple Consensus，RANSAC)算法进行一致性模型参数估计，能够更快地找到近似的模型参数。

借鉴K最邻近(K-Nearest Neighbor,KNN)算法[11]的思想，在匹配图像中剔除掉非同一区域的匹配点对，为了减少运算耗时，这里取2个最近邻特征点进行比较。

在剔除非同一区域的匹配点对之后，对匹配点对比值进行排序，通过PROSAC算法对模型参数进行迭代估计。经过2-NN交叉匹配之后，根据匹配点对的比值对模型参数进行估计，这样最有可能得到最佳参数的采样会较早出现，提高了估计速度。待匹配图像点对(xi,yi)T和(mi,ni)T间的模型为

(11)

令

其中:A为旋转矩阵；T为平移矩阵。由于变换矩阵包含α、tm和tn三个参数，因此至少需要3组匹配点对来估计模型参数。

剔除错误匹配点对的具体步骤如下：

2)反复进行迭代，统计每组参数返回匹配点对数量最多的模型参数值。

3)迭代到最大次数后，返回匹配点对数量最多的变换矩阵模型参数。

3 实验结果及分析

对本文改进算法与SIFT、SURF和ORB算法进行比较，通过旋转变换、尺度变换、模糊变换、光照变换和仿射变换多种环境的变化评估算法性能，并对改进算法的整体实时性进行检验。

3.1 实验方法

采用VS2010和OpenCV作为评估平台，计算机为Win7操作系统，Intel酷睿i5双核M480处理器，不使用GPU进行并行处理。实验图像来自文献[12]中Mikolajczyk和Schmid的数据集，其中：graffiti图像组用于测试仿射变化适应性、特征点检测数量和特征检测时间；boat图像组用于测试尺度和旋转变化适应性；bike图像组用于测试模糊变化适应性；Leuven图像组用于测试光照变化适应性。注：在以下各图中，a、b、c、d图像分别对应本文改进算法、ORB算法、SIFT算法和SURF算法；所有待匹配图像特征点与其最邻近点、次邻近点Hamming距离比值的阈值设置为0.55；本文改进算法中特征点检测数量的阈值设置为50。

3.2 结果分析

3.2.1 特征点检测对比

特征点检测对比的实验评估选取graffiti图像组第1、2幅图像，如图5所示，对比分析本文改进算法与ORB、SIFT以及SURF检测算法的平均特征点数量和平均检测时间，结果如表1所示。

图5 graffiti图像组

表1 检测算法平均特征点数量和平均检测时间

从表1中可以看出：各个算法检测的平均特征点数量关系为SIFT>本文改进算法>SURF>ORB，各个算法的特征点检测速度关系为本文改进算法>ORB>SURF>SIFT；虽然SIFT算法检测的平均特征点数量最多，但是耗时也最长，达到了1 698ms；本文改进算法耗时最短，比ORB算法快了7倍左右，并且本文改进算法检测的平均特征点数量仅次于SIFT算法。

3.2.2 仿射变化适应性对比

graffiti图像组的每个图像具有不同的视角，选取其中的第1、2幅图像，如图5所示，对本文改进算法与ORB、SIFT和SURF算法的仿射变化适应性进行对比分析，结果如表2所示。可以看出：本文改进算法对仿射变换图像的匹配率为80%，高于SURF和ORB算法，但是低于SIFT算法。

表2 仿射变化适应性对比

3.2.3 尺度和旋转变化适应性对比

boat图像组的每个图像具有不同的尺度和旋转变换，选取其中的第1、2幅图像，如图6所示，对本文改进算法与ORB、SIFT和SURF算法的尺度和旋转变化适应性进行对比分析，结果如表3所示。可以看出：本文改进算法的匹配率为80%，高于SURF和ORB算法，但是低于SIFT算法。

表3 尺度和旋转变化适应性对比

3.2.4 模糊变化适应性对比

bike图像组的每个图像具有不同的模糊程度，选取其中的第1、2幅图像，如图7所示，对本文改进算法与ORB、SIFT和SURF算法的模糊变化适应性进行对比分析，结果如表4所示。可以看出：本文改进算法的匹配率为93%，高于SURF和ORB算法，与SIFT算法相同。

图7 bike图像组

表4 模糊变化适应性对比

3.2.5 光照变化适应性对比

Leuven图像组的每个图像具有不同的光照强度，选取其中的第1、6幅图像，如图8所示，对本文改进算法与ORB、SIFT和SURF算法的光照变化适应性进行对比分析，结果如表5所示。可以看出：本文改进算法的匹配率为89%，高于其他3种算法。

图8 Leuven图像组

表5 光照变化适应性对比

3.2.6 实时性分析

如果图像匹配算法耗时严重，则会对视觉SLAM系统的实时性影响较大，为评估本文改进算法与ORB、SIFT和SURF算法的实时性，选取graffiti图像组第1、2幅图像(图5)进行统计分析，实时性对比结果如表6所示。可以看出：SIFT和SURF算法耗时严重，而ORB算法与本文改进算法的实时性相近，略差于本文改进算法。

表6 实时性对比 ms

4 结论

针对视觉SLAM系统中图像匹配性能和实时性要求高的问题，笔者基于ORB提出了一种改进的视觉SLAM图像匹配算法。该算法不但继承了ORB算法特征检测的高效率，增加了对尺度变化的适应性，而且在特征描述阶段能够更快速、准确地对特征点进行描述。通过实验表明：该算法具备很强的实时性，与原始ORB算法相比，其对图像在尺度、模糊、光照等条件变化的适应性均增强，特征点检测效率较高，能够快速、准确地实现图像匹配。

[1]Zitova B,Flusser J.Image Registration Methods:A Survey[J].Image and Vision Computing,2003,21(11):977-1000.

[2]Park C H,Kim N H.Precise and Reliable Positioning Based on the Integration of Navigation Satellite System and Vision System[J].International Journal of Automotive Technology,2014,15(1):79-87.

[3]Lowe D G.Object Recognition from Local Scale-invariant Features[EB/OL].(1999-09-20)[2016-03-09].http:∥www.cs.cmu.edu/～efros/courses/AP06/Papers/lowe-iccv-99.pdf

[4]Bay H,Tuytelaars T,Van Gool L.SURF:Speeded up Robust Features[J].Computer Vision&Image Understanding,2006,110(3):404-417.

[5]Rublee E,Rabaud V,Konolige K,et al.ORB:An Efficient Alternative to SIFT or SURF[EB/OL].(2011-11-06)[2016-03-09].http:∥www.cs.ubc.ca/～lowe/papers/iccv99.pdf[6]Rosten E,Porter R,Drummond T.Faster and Better:A Machine Learning Approach to Corner Detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(1):105-119.

[7]Calonder M,Lepetit V,Strecha C,et al.Brief:Binary Robust Independent Elementary Features[EB/OL].(2010-09-05)[2016-03-09].http:∥vision.stanford.edu/teaching/cs231b_spring1415/papers/BRIEF.pdf

[8]Mur-Artal R,Montiel J M M,Tardos J D.ORB-SLAM:A Versatile and Accurate Monocular SLAM System[J].IEEE Transactions on Robotics,2015,31(5):1147-1163.

[9]Vandergheynst P,Ortiz R,Alahi A.FREAK:Fast Retina Keypoint[EB/OL].(2012-06-16)[2016-03-09].https:∥infoscience.epfl.ch/record/175537/files/2069.pdf

[10]Chum O,Matas J.Matching with PROSAC:Progressive Sample Consensus[EB/OL].(2005-06-20)[2016-03-09].http:∥perso.telecom-paristech.fr/～sahbi/chum-prosac-cvpr05.pdf

[11]Muja M.Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration[EB/OL].(2009-02-05)[2016-03-09].http:∥www.ee.oulu.fi/research/imag/courses/Vedaldi/09muja.pdf

[12]Mikolajczyk K,Tuytelaars T,Schmid C,et al.A Comparison of Affine Region Detectors[J].International Journal of Computer Vision,2005,65(1/2):43-72.

(责任编辑： 尚彩娟)

An Improved Image Matching Algorithm Based on ORB for Visual SLAM

ZHANG Yang, LÜ Qiang, LIN Hui-can, MA Jian-ye

(Department of Control Engineering, Academy of Armored Force Engineering, Beijing 100072, China)

To solve the long time-consuming problem of traditional feature matching algorithms based on SIFT(Scale Invariant Feature Transformation) and SURF (Speed-Up Robust Feature) in visual SLAM (Simultaneous Localization And Mapping) system, an improved image matching algorithm is proposed based on ORB (ORiented BRIEF (Binary Robust Independent Elementary Features) ). Firstly, a multi-scale space pyramid is constructed in accordance with the defect that the FAST (Features from Accelerated Segment Test) detectors are susceptible to image blurring and distance variance. Secondly, the feature vectors are built by the refined fast retina key point descriptors for inefficiency of BRIEF descriptors. Finally, the feature vectors are purified by the nearest cross matching pairs and the false matching pairs are eliminated by using progressive sample consensus algorithm. The validity of the proposed algorithm is verified by comparing with SIFT, SURF and ORB algorithms.

visual SLAM; FAST; feature points detection; feature matching

2016-03-09

张 洋(1987-)，男，博士研究生。

TN911.73

：ADOI：10.3969/j.issn.1672-1497.2016.06.016

1672-1497(2016)06-0082-07