一种改进的ORB算法

潘 盼

(上海海事大学 信息工程学院，上海 201703)

一种改进的ORB算法

潘 盼

(上海海事大学 信息工程学院，上海 201703)

针对目前SLAM算法对特征提取的可靠性和鲁棒性要求越来越高的问题，基于ORB(二进制定向简单描述符)特征提取算法，提出了一种基于模块化区域分割的方法，解决了特征提取过程中提取无效特征点过多和特征点分布不均匀的矛盾。该方法使得ORB算法的特征提取更加均匀和合理，也更有利于图像的特征匹配。实验研究表明，该方法提高了算法的有效性和可靠性。

ORB；模块分割；特征匹配

0 引言

研究表明，基于特征的图像匹配方法越来越受到人们的重视，特别是在视觉SLAM(Simultaneous Localization And Mapping)[1]领域更是成为不可或缺的关键技术。其在移动机器人导航[2]、运动识别、三维立体重建等方面都有极为广泛的应用。

在众多特征匹配的方法中，SIFT(Scale Invariant Feature Transform)[3]算法一直占据着主流的地位，虽然其在抗噪声、光照以及尺度变化等方面表现出良好的鲁棒性，但巨大的运算开销也使它的实时性大打折扣。随后基于SIFT的加速鲁棒性特征(Speed-Up Robust Feature,SURF)[4]的出现，简化了算法并且大大提升了特征点匹配的计算速度和鲁棒性。随着特征点提取在视觉各个领域的广泛应用，RUBLEE E等人提出基于FAST[5](Features from Accelerated Segment Test)和BRIEF[6](Binary Robust Independent Elementary Features)方法的ORB[7](Orineted FAST and Rotated,BRIEF)算法。该算法在鲁棒性和有效性方面表现优异。虽然有这么多不同特征点提取算法，但在视觉SLAM系统中如何选择依然是个需要慎重考虑的问题。因此本文通过实验对比不同的算法的有效性和鲁棒性，并依据实际的SLAM应用提出一种改进的ORB算法，同时验证其可靠性。

1 ORB算法原理

1.1 ORB算法流程

特征点提取步骤如下：

(1)利用FAST方法提取图片中的特征信息。

(2)利用Harris方法对上一步提取的特征点排序。

(3)构造图像金字塔，然后对金字塔的每一层搜索FAST特征点。

(4)应用灰度质心方法定位。

特征描述子：实际上ORB算法采用的是具有旋转不变性的BRIEF也即rBRIEF。其主要思想是依据灰度值的大小选取某个特征点附近的几个像素点对，构成二进制编码的算子，即为该点的特征描述子。

特征点的匹配：ORB算法获得所有特征点的信息和特征描述子，然后计算成对的两幅图的所有特征点之间的向量间的汉明距离[8]，若满足一定的条件(例如求最短的汉明距与次短汉明距)，当这两个数值的比不大于0.8且长度都不大于50时，则认为这对特征点满足匹配条件。算法流程如图1所示。

1.1.1FAST特征点提取

ORB使用FAST方法来搜索图像中的特征点。而FAST提取方法的核心思想是：基于加速分割测试特性，如图像中某像素点与其相邻区域内拥有足够多不同特征时，就认为该点为特征点，一般可以将大于总数3/4的点判为角点。

FAST算法提取的步骤：

(1)选取图像中像素点K，将该点像素值设为Kp，然后判断该点是否为特征点。

(2)给定一个经验阈值T，本文设为9。

(3)考虑将该点设为圆心，以3像素为半径构造一个包含16个像素N个连续像素点的离散化圆，如图2所示。

图2 FAST角点检测

(4)采用决策树ID3算法[9]构造三叉树，快速剔除掉伪角点，对于像素点K，设其邻域的16个点位置为t，t∈{1…16}的点标记为K→t，依据下列计算公式将该点分为三类：

(1)

简单来说该步骤就是先计算1、5、9、13这4个具有代表性的像素点，首先检查上下两个点，若它们都比阈值大或比阈值小，再检查左右两个位置的点，至少3个满足阈值条件，也就是绝对值大于T，才进行候补点的检测，如不满足上面的条件则把这个点剔除掉。

从上述方法可以看出，相对于其他特征点提取方法，FAST的提取方法计算速度快，可以应用到实时场景中。但FAST方法并没有对特征点进行描述子计算，因此不具备尺度和旋转不变的性质，在复杂的场景中并不会直接拿来应用。

虽然FAST角点提取算法相比于其他提取算法效率更高，但不能很好地适应旋转变化，ORB算法通过强度中心方法为FAST特征点计算一个主方向。首先在像素点局部区域确定强度中心，然后从像素点K到强度中心构造方向向量，如图3所示。

图3 强度中心

假设图像中区域块的阶数(Moments)为：

(2)

式中用I(x,y)表示图片某点处的灰度值，p和q等于0或者等于1。半径为r的图像中求得其强度中心C为:

(3)

其中m00为零阶矩，m01m10为一阶矩。

求得点O与中心点C夹角为该点的主方向,用以下公式计算：

θ=arctan 2(m01,m10)

(4)

1.1.2BRIEF特征描述子

ORB算法采用rBRIEF来构造特征描述子，其实质内容为：以FAST方法得出的特征点为中心，随机选取附近若干像素的点对。利用高斯二元分布对每个点对进行像素的灰度变化二值化比较，也即大于为1小于为0。将比较结果存为一个二进制串。生成指定次数位的二进制串，就得到BRIEF的描述。具体步骤如下：

(1)定义一个经过高斯分布处理的图像邻域B，其对应的描述子准测函数τ为：

(5)

其中B(x)为邻域x位置的灰度函数。

(2)选取n对(xi,yi)测试点对，由此唯一确定了一个二进制串：

(6)

(3)为了使生成的不具有方向的描述子具备旋转不变性，将前面求得的特征点质心方向添加到描述子中。随机选取(xi,yi)则可以定义一个2×n的矩阵Q：

(7)

式中(xi,yi)为测试点对。

得到该点方向θ相应的矩阵Rθ，构造点对的矩阵：

Qθ=RθQ

(8)

最终特征点的描述算子为：

gn(B,θ)=fn(B)|(xi,yi)∈Qθ

(9)

(4)因为ORB对噪声敏感，所以普遍采用在31×31的窗口搜索5×5子窗口像素灰度平均值代替该处灰度值。即找出像素点对相关性最小的块构成所需的特征描述子。具体步骤如下：

(1)在某个像素邻域内计算点对测试值τ，对所有的τ计算与其距离为0.5的点，并排序形成向量S。

(2)贪婪法逐步搜索。

①首先将第一个τ值带入R中，并从S中剔除；

②然后将向量S下一个值与R中所有值比较。将相关度高的丢弃，否则就添加到生成描述子；

③重复以上几个步骤直到最终向量S中有256个坐标时，特征描述子则构造完成。将相关度阈值增加，再次构造。保证最终描述子有较低的相关性。

1.1.3特征点匹配

特征匹配被广泛应用在图像识别等众多领域，已成为计算机视觉研究中最常用的处理方法。在视觉SLAM中为了更好地进行位姿估计、闭环检测[10]等，需要对生成的特征描述子进行匹配与跟踪。相比于SIFT和SURF用欧式距离进行描述，这里计算欧式距离然后作为评价准则从而得到相距最近的作为相似的一对。

ORB利用二值字符特征点描述的汉明距离作为评价标准，选出汉明距离最小的作为相似的一对。由上节得到ORB的n=256维二进制描述算子，随机选取K1、K2两幅图像的描述算子：

K1=x0x1…xn，K2=y0y1…yn

(10)

ORB的描述子相似度用汉明距离做异或运算然后求和来表示，记为D(K1，K2)：

(11)

其中D(K1,K2)越小则表明特征点对相似程度越高。因为只在同位置进行求异或运算，计算汉明距离远没有计算欧式距离复杂。ORB二值特征描述子在匹配上拥有更大的优势，同时，将应用模型估计中常用的RANSAC(Random Sample Consensus)[11]方法进行外点误匹配剔除。选取两幅图像进行比较，三种不同方法得到的结果对比如图4所示，其中图(d)通过RANSAC方法消除了外点，尽管匹配的数目有所减少，但是正确率显著提高了。

图4 特征匹配结果

1.2 ORB特征提取算法的优化

视觉SLAM运动估计的正确性往往取决于算法所获取到的特征数目，同时也依赖于特征点在整张图片中的位置。一般来说特征越多估计越精确，特征越少估计越不准确，严重的甚至会导致算法失效。而在实际中，过多的特征点意味着计算量的增大，这对实时性的影响不可忽视。因此应尽可能在提取到足够多的特征点的情况下，保证特征点能均匀地分布在这个图像中。为达到实际应用的要求，本文设计一种区域模块分割的ORB特征提取算法，步骤如下：

(1)将得到的图像分割成大小均匀的模块化子区域，称之为栅格(Grid)。在这里将图像划分成M×N个子区域，也就是栅格。这样图片区域中的特征点信息会随机分布。将栅格先行后列排序表示为{h1,h2,h3,…,hm}。

(2)将检测不到特征点的栅格hi设为不感兴趣区域，且在后面检测中不再考虑该区域。将检测到nj个候选点的栅格hj设为感兴趣。判断nj与j的大小(j的设置依据经验值，这里设为5)，如果前者不大于后者则将子区域的候选特征点设为检测点；若前者大于后者，再进一步做Harris[12]角点检测排序操作，选出表现最好的j个点。其余的作为候选检测点ki。

基于上述方法的ORB特征提取算法的优点可总结为：

(1)每个选择的特征点都是子区域中表现最优的特征点。

(2)选取特征点的数量可根据实际应用灵活变化。

(3)最终选取出的点尽量平均分布在整张图片的区域中。

2 实验结果与分析

本文实验是在Windows 7 + OpenCV2.4.9平台上实现的，采用的原始图像如图5所示，像素大小640×480，图像格式为.bmp。

图5 原始参考图像

未优化的ORB特征提取结果见图6。最终的优化过的ORB特征提取如图7所示。由图可得,相比于图6，由于进行了Harris方法的二次排序，图7避免了选取到性能较差的特征点；优化后的提取结果更加均匀，也更具代表性。

图6 ORB特征提取示意图

图7 优化后的ORB特征提取示意图

速度测试：算法的耗费时间是评价一个方法优劣的重要方面。在硬件平台近似相同的情况下，若匹配的结果相似或者是为了满足系统实时性的要求，运行的速度越快，表示该算法越好。本文算法运行时间比较结果如表1所示。

表1 算法运行时间比较

由上述实验可以看出，优化后的ORB在提取相同级别数量的特征点的情况下并未损失过多的运行速度。相反，优化后的算法提升了特征提取的性能，提取的特征点也更加均匀。这能大大提高SLAM算法的稳定性。

3 结论

本文从理论上介绍了ORB特征提取的算法流程和原理，针对特征点数量与质量的矛盾这一问题采用了一种基于模块化分割的ORB特征提取优化方法使提取的特征点更均匀地分布在整个图像区域，分析比较了原算法和改进算法的速度性能和提取效果，实验结果表明在不影响特征提取数量的条件下提取的质量得到了一定程度的提高，从而获得了更好的性能。

[1] 权美香,朴松昊,李国. 视觉SLAM综述[J]. 智能系统学报,2016,11(6):768-776.

[2] 王志文,郭戈. 移动机器人导航技术现状与展望[J]. 机器人,2003,25(5):470-474.

[3] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision, 2004, 60(2): 91-110.

[4] BAY H, TUYTELAARS T, VAN GOOL L. Surf: speeded up robust features[C].European Conference on Computer Vision, Springer Berlin Heidelberg, 2006: 404-417.

[5] VISWANATHAN D G. Features from accelerated segment test (FAST)[EB/OL].(2016-04-15)[2017-03-30]https://wenku.baidu.com/view/af9743d725c52cc58ad6beac.html.

[6] CALONDER M, LEPETIT V, STRECHA C, et al. Brief: binary robust independent elementary features[C].European Conference on Computer Vision, Springer Berlin Heidelberg, 2010: 778-792.

[7] RUBLEE E, RABAUD V, KONOLIGE K, et al. ORB: an efficient alternative to SIFT or SURF[C].2011 IEEE International Conference on Computer Vision (ICCV), IEEE, 2011: 2564-2571.

[8] NOROUZI M, FLEET D J, SALAKHUTDINOV R R. Hamming distance metric learning[C].Advances in Neural Information Processing Systems, 2012: 1061-1069.

[9] 王永梅,胡学钢. 决策树中ID3算法的研究[J]. 安徽大学学报(自然科学版),2011,35(3):71-75.

[10] 杨恒. 基于局部特征提取匹配的视觉SLAM闭环检测方法研究[D].衡阳：南华大学,2015.

[11] FISCHLER M A, BOLLES R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[12] HARRIS C, STEPHENS M. A combined corner and edge detector[C]. Proceedings of Fourth Alvey Vision Conference, 1988: 147-151.

An improved ORB algorithm

Pan Pan

(School of Information Engineering, Shanghai Maritime University, Shanghai 201703, China)

Aiming at the improvement of the reliability and robustness of the feature extraction in SLAM algorithm, an improved method of feature extraction is proposed. Based on the ORB (Oriented fast and Rotated Brief) feature extraction algorithm, an area segmentation method is proposed. It solves the problems of too more invalid feature points and the uneven distribution of feature points. This method makes the feature extraction of ORB algorithm more uniform and reasonable, and is more conducive to the image feature matching. The experimental results show that this method improves the effectiveness and reliability of the algorithm.

ORB; module segmentation; feature matching

TP911.73

A

10.19358/j.issn.1674- 7720.2017.20.007

潘盼.一种改进的ORB算法[J].微型机与应用，2017,36(20)：23-26.

2017-03-31)

潘盼(1989-)，男，硕士，主要研究方向：移动机器人导航、机器视觉。