基于ORB+PROSAC误匹配剔除算法的视觉SLAM研究

徐子锋 石超 王永锋 陈龙

摘  要：在视觉SLAM前端特征点匹配过程中，采用RANSAC算法剔除误匹配特征点存在迭代次数不稳定、效率低、鲁棒相差等问题，从而对相机定位产生影响。与ORB算法结合，本文引入一种渐进采样一致性算法，即PROSAC（Progressive Sampling Consensus），来消除迭代次数不稳定问题。利用Kinect v2相机对改进的RGB-D SLAM算法进行实验，获得三维点云地图和相机轨迹，实现了ORB+PROSAC的误匹配剔除算法。与ORB+RANSAC的结合方式相对比，本文算法验证鲁棒性更好，实时性更强。

关键词：视觉SLAM;特征点匹配;RANSAC算法;PROSAC算法

中图分类号：TP391.4     文獻标识码：A

Abstract：In the process of feature point matching in the front of visual SLAM，a series of problems have been found when using the RANSAC algorithm to eliminate the mismatched feature points，such as unstable iterations，low efficiency and robust phase difference，resulting in an impact on camera positioning.Combined with the ORB algorithm，this paper introduces a progressive sampling consensus algorithm，PROSAC （Progressive Sampling Consensus），to eliminate the instability of iteration times.Using the Kinect v2 camera with the improved RGB-D SLAM algorithm，the 3D point cloud map and camera trajectory can be obtained in the experiment and the mismatch elimination algorithm of ORB+PROSAC can be realized.Compared with the combination with ORB+RANSAC，the proposed algorithm verifies the robustness better with a stronger real-time performance.

Keywords：visual SLAM;feature point matching;RANSAC algorithm;PROSAC algorithm

1   引言（Introduction）

移动机器人的同步定位与地图构建（Simultaneous Localization and Mapping，SLAM）[1]是实现移动机器人自主定位导航的关键技术。视觉SLAM由于传感器价格低廉，以及所能采集到的信息丰富等特点，越来越多地出现在工业应用中。

视觉SLAM前端系统中，图像在匹配过程中受到噪声干扰，会导致特征点的误匹配，影响相机定位。为了提高视觉SLAM前端特征点匹配的精确性，通常在匹配过程中加入随机采样一致性算法，即RANSAC（Random Sampling Consensus）[2]，对误匹配点进行剔除。RANSAC算法是随机过程，会导致迭代次数不稳定，且时间开销大，不能很好满足实时性要求。另外，现在越来越多的研究人员尝试着将机器学习的方法加入视觉SLAM前端中，使得图像匹配更加鲁棒，但是需要大量样本的训练，计算量也会增加。

视觉SLAM前端图像匹配既要满足精确度要求，同时还需要满足实时性要求。对此，文中提出在图像匹配过程中引入一种渐进采样一致性算法，即PROSAC（Progressive Sampling Consensus）[3]，来消除迭代次数不稳定问题，将两种误匹配点剔除方式与ORB算法结合对比。利用Kinect v2相机对改进的RGB-D SLAM[4]算法进行实验，为了使结果更加准确，利用图优化的方式对相机位姿进行优化，获得三维点云地图和相机轨迹，进而证明了ORB+PROSAC算法的优势。

2  ORB特征点匹配算法（ORB feature point matchingalgorithm）

2.1   特征点提取

2.3   特征点匹配

如图2所示为两张图片间的特征点匹配，特征匹配解决了SLAM中的前端数据关联问题。假设在图像中提取特征点，m=1，2，…，M，在图像中提取特征点，n=1，2，…，N进行特征点匹配。最简单的特征匹配方法就是暴力匹配（Brute-Force Matcher），即对每一个特征点，与所有的测量描述子的距离进行排序，取最近的一个作为匹配点。描述子距离表示了两个特征之间的相似程度，在实际运用中可以取不同的距离度量范数。对于BRIEF描述子，用汉明距离（Hamming distance）[8]为度量。两个二进制串之间的汉明距离指的是它们不同位数的个数。当特征点数量很大时，暴力匹配法运算量将变大，尤其是当匹配一个帧和一张地图的时，不能满足SLAM中的实时性需求，因此可以用快速近似最近邻（FLANN）[9]算法进行匹配。

3  基于 PROSAC 的误匹配剔除算法（Mismatch-based culling algorithm based on PROSAC）

3.1   RANSAC算法原理

RANSAC算法用于二维平面上对随机点进行采样并拟合出一条直线。具体算法：随机从二维平面中选取两个点，将两点进行连线。设定距离阈值，分别计算平面中其他点和该直线的距离，当距离小于设定阈值时，则被认为是内点;当距离大于设定阈值时，则被认为是外点，不断重复随机采样的过程，找出所有最佳距离点，拟合成直线，如图3所示为RANSAC随机采样过程。

3.2   PROSAC算法原理

RANSAC算法中选取的样本点是随机的，需要不断的迭代才能选取出尽量多的内点，因此整个计算过程时间增加，迭代次数不稳定。PROSAC算法和RANSAC算法有所不同，首先是将样本点进行预排序，筛选出符合的样本点，然后对匹配模型进行估计。这样减少模型的迭代次数，且模型正确率高。在二维平面随机点拟合直线过程中，首先将样本集中点部分分为两个部分，在进行距离阈值设定，选取最佳内点，从而最后拟合出最佳直线，如图4所示为PROSAC随机采样过程。

3.3   ORB+PROSAC与ORB+RANSAC特征点检测实验

为了验证ORB算法分别和RANSAC算法和PROSAC算法结合的有效性，运用OpenCV工具进行对比实验。实验结果如图6—图10所示。

4  基于RGB-D传感器的3D SLAM（3D SLAM based on RGB-D sensor）

4.1   帧间相机运动恢复

完成特征提取与匹配之后，可根据已经匹配的特征对相机进行运动估计[13]。根据特征的信息的不同，可以分为2D坐标信息和3D坐标信息。2D坐标信息可以从图像中直接获取，3D坐标深度信息可以通过其他方式获取，单双目相机可以通过三角化的方法获取，RGB-D传感器可以直接通过深度图像与RGB图像配准获得。求解相机运动有三种方式：2D-2D、3D-2D和3D-3D。2D-2D相机位姿估计计算两帧图像之间的本质矩阵，通过构建最小二乘法和SVD分解方法将本质矩阵分解，求解R和t，再乘计算的t的相对尺度，最终获得相机运动。本质矩阵有五个自由度，三个旋转加上三个平移，减去一个尺度化因子。本质矩阵的计算至少需要五组图像对应点，通常采用五点算法和八点算法计算。3D-2D的方法是最小化重投影误差的方法计算，而3D-3D的方法则是最小化三维位姿误差，因此3D-2D方法比3D-3D方法更精确，最小化重投影误差的形式是为了找到式（9）中最小的Tk：

4.2   ICP算法

迭代最邻近点（Iterative Closest Points，ICP）算法常用于对齐两组点云。假设存在两组名为Pr和Pl的点云，通过计算方程的最小值来获得两组点云的刚性变换，为了计算使方程最小的旋转和平移矩阵R和t，在两组点云Pr和Pl中根据一定的约束条件，寻找最邻近点，然后计算最优匹配参数R和t，则误差函数为：

4.3   位姿优化

传统的SLAM基于滤波和非线性优化的方式进行优化，效率较低。引入图优化[14]方式的优化方法可以完成相机局部和全局的位姿优化。图由节点和边组，pose节点代表相机位姿，point节点代表相机观测到的路标点，边代表两个节点间的约束。完全构建图后，应调整相机的姿势以满足边界约束。用误差函数表达两个节点满足约束的程度。基于图优化的SLAM系统分为两个模块，即前端和后端。在前端中，需要从传感器数据中提取几何约束，并解决数据关联的问题。最后，构造图结构的节点和边。在后端模块中，寻找状态向量，该状态向量可以使几何约束的似然函数最大化。将SLAM抽象成图的形式之后节点表示待优化变量，边表示误差项约束条件，包括相机节点间约束，以及相机位姿和路标点的约束。前者依赖于系统闭环检测产生的约束，如图12和图13所示。后者依赖于相机对路标点观测产生的约束，如图11所示。通过构建图优化的方式可以缩小系统的误差累积，从而构建信息一致的地图。

4.4   地图构建

地图的构建[15]可以分为局部地图和全局地图两种。局部地图保留了当前位置附近特征点信息，这些特征点用来与当前帧进行匹配求解当前相机位姿，随着相机的运动新的帧不断被加进来，数据维护将会变大，因此需要丢弃之前的帧以保证系统实时性。全局地图则是记录所有特征点的信息，后期通過地图的加载和匹配可用于机器人的定位导航和路径规划。系统在传感器数据中提取关键帧，估计关键帧匹配关系。可以用（Bundle Adjustment，BA）方式优化关键帧匹配点的重投影误差，由于地图点和关键帧是冗余的，需要对关键帧进行剔除，才能获得鲁棒的地图。到目前为止，已经可以获得全局一致的相机轨迹，通过引入深度信息，跟踪在全局3D坐标系中投影所有测量点坐标，可生成环境的点云地图。

5   基于kinect v2的 SLAM实验设计与分析（Design and analysis of SLAM experiment based onkinect v2）

5.1   基于ORB+PROSAC特征提取的SLAM系统框架

如图14所示为RGB-D SLAM系统框架，共五个主要模块，包括特征检测、运动估计、ICP算法、基于图优化的位姿优化和地图构建。利用Kinect传感器获取深度图像和RGB图像，使用ORB算法进行特征检测，同时利用PROSAC算法在图像特征点匹配中剔除外点，获得更精确的匹配点，准确估计相机运动。为了获得相机的全局最优姿态和环境地图，通过将图优化方法应用于系统，提取深度信息，可生成实验室环境3D点云地图。

5.2   实验硬件平台

为检验ORB+PROSAC特征点匹配算法实际运行效果，使用事先标定好的Kinect V2相机，以及内存4GB、CPU为Intel i5 4210M、2.6GHz、显卡为Intel HD4600集成显卡笔记本电脑作为硬件平台，在实验室环境下对算法进行实际测试。如图15所示为Kinect V2相机。

5.3   实验结果及分析

由于缺少外部设备对相机进行跟踪，无法计算得到各时刻相机位置与真实相机位置之间的误差。从运行结果来看，RGB-D SLAM算法能够很好地进行初始化，且高效实时运行，如图16所示相机在特征点跟踪阶段比较稳定，无丢帧或者失帧的情况。此外，在回环检测阶段能够对相机轨迹进行全局调整，配准传感器深度信息，建立如图17和图18所示实验室环境特征点地图和3D点云地图，因此实验证明ORB+PROSAC方式效率高，鲁棒性好。

6   结论（Conclusion）

本文从RANSAC算法和PROSAC算法的对比分析入手，理论分析可知RANSAC算法迭代次数不稳定、匹配效率低，PROSAC算法引入了质量因子，通过质量因子分级质量好的内点用于估计模型的方式，可减少算法的迭代次数、降低计算和时间复杂度。通过ORB特征点匹配结合两种算法实验对比，得出PROSAC算法优于RANSAC算法。用Kinect v2相机对改进的RGB-D SLAM算法进行实际运行，获得三维点云地图和相机轨迹，进而验证了ORB+PROSAC算法在视觉SLAM的应用鲁棒性好，实时性强。

参考文献（References）

[1] Mur-Artal R，Montiel J M M，Tardós J D.ORB-SLAM：A Versatile and Accurate Monocular SLAM System[J].IEEE Transactions on Robotics，2017，31（05）：1147-1163.

[2] Bahraini MS，Bozorg M，RadAB.SLAM in dynamic environments via ML-RANSAC[J].Mechatronics，2018，49（08）：105-118.

[3] Panpan Z，Derui D，Yongxiong W，et al.An improved GMS-PROSAC algorithm for image mismatch elimination[J].Systems Science & Control Engineering，2018，6（01）：220-229.

[4] Ma L，Kerl C，Stuckler J，et al.CPA-SLAM：Consistent plane-model alignment for direct RGB-D SLAM[C].2016 IEEE International Conference on Robotics and Automation（ICRA）.IEEE，2016，8（02）：120-124.

[5] 吴金津，王鹏程，龙永新.基于FAST角点检测的图像配准算法[J].湖南工业大学学报，2014，28（04）：71-75.

[6] 张阳，许钢，张星宇.一种改进的ORB特征点匹配算法[J].重庆工商大学学报（自然科学版），2018，179（03）：73-78.

[7] 高翔，张涛.视觉SLAM十四讲：从理论到实践[M].北京：电子工业出版社，2017：133-182.

[8] 邸凯昌，万文辉，赵红颖.视觉SLAM技术的进展与应用[J].测绘学报，2018，47（06）：84-93.

[9] 許芬，王振.基于Kinect传感器和ORB特征的视觉SLAM算法设计与实现[J].计算机工程与科学，2018，40（05）：76-81.

[10] 邢凯盛，凌有铸，陈孟元.ORB特征匹配的误匹配点剔除算法研究[J].电子测量与仪器学报，2016，30（08）：1255-1262.

[11] 郑顾平，闫勃勃，李刚.基于机器学习的多车牌识别算法应用研究[J].计算机技术与发展，2018，254（06）：135-138.

[12] 李伦.基于PROSAC算法的室内定位算法研究[D].哈尔滨：哈尔滨工业大学，2018：36-50.

[13] 辛冠希.基于RGB-D摄像机的同步定位与建图研究[D].哈尔滨：哈尔滨工业大学，2016：29-54.

[14] 张毅，沙建松.基于图优化的移动机器人视觉SLAM[J].智能系统学报，2018，13（02）：290-295.

[15] 杨林志.基于视觉的移动机器人SLAM算法研究[D].成都：西南交通大学，2018：42-66.