基于PROSAC的视觉SLAM特征匹配方法

韩佳乐，徐允鹤，郭凤娟，王晓旺

基于PROSAC的视觉SLAM特征匹配方法

韩佳乐1,2，徐允鹤3，郭凤娟1,2，王晓旺1,2

（1 中国电子科技集团公司第二十研究所，西安 710068；2 陕西省组合与智能导航重点实验室，西安 710068； 3 中国航空工业集团公司沈阳飞机设计研究所，沈阳 110035）

当前视觉即时定位与地图重构技术（SLAM）的过程中，通常采用随机采样一致性（RANSAC）的图像特征匹配算法，随机估计图像模型容易造成算法时间复杂度不确定，进而导致图像匹配时耗过大，难以满足视觉SLAM实时性的要求。为了改善这一问题，使用渐进采样一致性（PROSAC）的算法对图像特征进行筛选，剔除误匹配特征点，有效改善了图像特征匹配的效率与鲁棒性，进一步增强了视觉SLAM的稳定性与实时性。试验验证表明，相比于当前视觉SLAM特征匹配算法，计算效率明显提升。

随机采样一致性；视觉即时定位与地图重构技术；图像特征匹配；快速提取描述子特征

0 引言

视觉即时定位与地图重构技术（Simultaneous Localization and Mapping，SLAM）的过程中，相机实时采集场景的图像序列，识别图像特征信息，进行前后帧图像特征匹配，然后对相机的位姿状态进行粗略地估计，生成相机运动的位置信息[1]。在工业生产、金融安防和军事交通等领域均有着越来越广泛的应用。

尽管现有的SLAM技术已经取得了一定的进展，但是面临室内外复杂场景，现有的视觉SLAM技术仍面临一些挑战。当场景中存在干扰的目标或者当载体快速运动时，会导致提取的图像特征噪声较大，影响定位精度，甚至会因为实时性不足导致跟踪丢失、中断定位的进程。在视觉SLAM过程中，图像特征匹配精度直接决定定位结果。由于像素特征信息的相似性，特征匹配过程中易产生误匹配特征点，此时需要对误匹配特征点进行剔除。传统视觉SLAM采用随机采样一致性（Random Sampling Consensus，RANSAC）[2]进行剔除误匹配特征点，RANSAC算法由于需要对整个数据集随机处理，导致系统整体时间复杂度不稳定，进而产生鲁棒性较差等问题。本文采用PROSAC[3]算法改进当前视觉SLAM中的特征匹配算法，首先采用快速提取旋转描述子（Oriented FAST and Rotated BRIEF，ORB）特征，将特征点对进行质量排序，剔除质量较低的点对（即误匹配特征点），有效改善了特征匹配的时间复杂度，提升了算法效率。有助于提升后续视觉SLAM的稳定性与实时性。

1 视觉特征点提取与匹配

视觉SLAM的过程中，通过相机的运动采集场景的图像序列，生成相机运动的位置信息，这个过程叫做视觉里程计。由于图像是由不同亮度和色彩组成的矩阵，直接对图像进行分析来估计计算相机的位姿，存在很大的难度和计算量。一般情况下是提取场景图像具有明显信息的点，也被称为特征点，通过对这些特征点进行提取与匹配，描述跟踪的特征点从而估计相机的运动轨迹。特征点的选取对于SLAM的精度和运行时耗影响巨大，因此要选取一个合适的特征提取方式，还需要对提取的特征点进行筛选，选择合适的点进行计算。

特征点的提取方法通常是选取识别度较高的点，并将特征点周围的邻近点以向量的形式表示出来。常见的方法有尺度不变特征点[4]（Scale Invariant Feature Transform，SIFT）、加速稳健特征点[5]（Speeded Up Robust Feature，SURF）和ORB特征点[6-8]等。SIFT和SURF特征综合了方向和尺度的信息，有着出色的精度和鲁棒性，在图像识别和融合等方面都有优异的表现。但是SIFT和SURF特征点的提取过程非常耗时，对于实时性要求较高的场合受到了限制，因此不适用于SLAM的过程。相比于其他特征点，ORB特征点虽然精度较低，但ORB特征的提取速度远远高于SIFT和SURF特征，因此本文在相机特征获取的过程中选取ORB特征，ORB特征同样具有尺度不变的特性，包括关键点和描述子两个部分，分别对特征点处的尺度信息和方向信息进行描述，文献[6]中经过试验对比，ORB特征点较其他类型特征点在精确度类似的情况下，速度有很大提升。

将汉明距离最小的特征点视作匹配过程中最优的候选点，如果汉明距离小于给定的阈值，则认为它就是匹配点。

该方法虽然简单有效，但是效率很低。当匹配过程中存在太多特征点时，很容易造成计算量过大，耗时性太高的问题。因此可以根据一些先验信息，剔除误匹配的特征点，具体操作在第2节中说明。

2 视觉特征点剔除误匹配

2.1 传统剔除误匹配特征点方法

目前主流的视觉SLAM算法通常通过RANSAC算法来解决[9]。RANSAC算法使用迭代的方法从一组被观测的特征点集计算出需要的可靠数据模型，基本思想是：反复选取数据集中的样本点，产生一个随机的估计模型，用其他点对该估计进行测试，获取每个点在该模型下的分值，返回最高分值点作为整个集合的估计点。

RANSAC最小二乘模型只适用于误差较小的情况，如图1所示，可以直观地看到存在两个误差点可能由于采集的问题，应该不被计算到估计中，然而由于随机采样的问题将这两个点计算进去，得到的估计模型和实际模型存在一定的偏差。针对这种情况本文做了相关的改进，在下文详细讲述。

图1 RANSAC算法线性拟合

2.2 PROSAC误匹配剔除算法

RANSAC算法可以有效地剔除误差点，但存在鲁棒性较差等问题，因此本文采用一种PROSAC的算法剔除误匹配的特征点。该算法有效解决RANSAC算法迭代次数不稳定等问题，提升了算法特征匹配效率与鲁棒性。

根据文献[10]的假设“质量好的点是内点的可能性更大”，PROSAC算法在选取特征点时，从质量排序靠前的点的集合中选取。建立临时对应中使用的相似性函数，利用对应集合上定义的线性排序，避免了随机采样问题，如图2（a）所示，对应随机的在二维平面上的分布的点，将质量等级较高的点标记为红色，反之将离中心较远的点标记为绿色；如图2（b）所示，PROSAC算法拟合一条直线，将质量较高的红色的点视作内点，其他为误匹配的点。

图2 PROSAC算法线性拟合

具体而言，在图像匹配的过程中，对于两幅相互匹配的图像，第一步使用ORB特征得到一个粗略的匹配点集，计算和排序该集合中每个匹配对的相似度。第二步，利用相似度最高的匹配对计算极线几何约束模型，利用所得模型估计匹配点集中剩余的匹配对。这里有两个任务：

1）剔除不满足几何约束模型的外部点；

2）通过迭代形式的更新模型获得大量良好的匹配对。

显而易见的，可以利用8对匹配对来计算本质矩阵，如式（6）所示

通过计算几何约束模型，剔除不满足极线几何约束模型的点，得到较好的匹配点对。在特征匹配算法和改进的PROSAC算法的基础上，提出了剔除误匹配特征点算法如下：

上述算法描述了PROSAC算法通过判断匹配点与投影点的误差，如果误差小于一个阈值，即可认为它属于内点，即具有可靠性的点，然后输出这些点作为SLAM过程中特征匹配的关键点。PROSAC算法通过计算外极线几何约束来分析特征点对匹配的质量，然后选取置信度较高的匹配点对用于计算相机的位姿。相较于RANSAC随机一致性匹配算法，该算法降低了时间复杂性，缩短了特征匹配的时间。

3 PROSAC算法仿真试验分析

为了验证基于PROSAC剔除误匹配点的算法的效果，本节选取三组不同特征点丰富度的图片，分别在室内场景、相似特征场景与多干扰特征场景对PROSAC算法和传统RANSAC算法进行试验仿真验证，仿真结果如图3～图5所示。图（a）为匹配的初始图像对，将左右两幅图像进行特征匹配，图（b）为提取的ORB特征，绿色标记点即所有识别到的特征点；图（c）和图（d）分别为RANSAC算法和PROSAC算法剔除误匹配点后，进行特征匹配的结果（图5（c）为PROSAC结果），其中连线的点即为匹配成功的特征点对。

图3 室内场景

图4 相似目标场景

图5 多干扰特征场景

以匹配精度作为评价指标：本文PROSAC算法和传统RANSAC算法大多数情况均能剔除误匹配点。如图3（c）和图3（d）所示，在特征干扰较少的情况下，RANSAC与PROSAC算法剔除误匹配特征点结果差别不大，均能得到较好的结果。在图4（c）和图4（d）中，左右两幅图片若正确匹配，所匹配的特征点连线均应为水平连线，易得RANSAC算法误匹配特征点较多（蓝线存在许多交叉部分），而PROSAC算法能有效剔除误匹配特征点。如图5所示，当场景中出现多干扰特征信息，经过传统RANSAC算法会导致匹配中断，而本文使用的PROSAC算法依旧可以剔除误匹配点，实现特征匹配。

以匹配时间作为评价指标，如表1所示，对匹配得到剩余匹配点的数量占初始观测到的匹配点的数量作比较，称为内点比例，对其进行统计。

表1 PROSAC算法与RANSAC算法剔除误差点性能比较

由表1可得，RANSAC和PROSAC在匹配上具有接近的内点比例，因此在剔除误匹配误差点的精度上类似，然而在匹配时间上，PROSAC通过置信度高的点进行匹配计算，而不是随机的选取全部特征点，有效降低了系统的迭代次数，减少了系统的运行时间，特别是当系统干扰特征点非常多时，RANSAC因随机性选取的数据，造成系统中断，而PROSAC则可以顺利完成剔除误匹配特征点。

4 结语

PROSAC在保证剔除误匹配精度的同时，还具备更高效的算法效率。通过PROSAC算法有效节省了系统特征匹配的时间，有助于提升视觉SLAM的实时性与稳定性，能更好地支撑视觉SLAM定位的工程应用。

[1] Durrant Whyte H，Bailey Tim. Simultaneous Localization and Mapping：Part I [J]. IEEE Robotics&Amp Automation Magazine，2006，13（2）：99-110.

[2] Martin，Fischler，et al. Random sample consensus：a paradigm for model fitting with applications to image analysis and automated cartography [J]. Communications of the ACM，1981.

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

[4] Lowe D G. Distinctive image features from scale-invariant key points[J]. International journal of computer vision，2004，60（2）：91-110.

[5] Bay H，Tuytelaars T，Van Gool L. Surf：Speeded up robust features[C]. European Conference on Computer Vision，Springer，2006：404-417.

[6] Mur-Artal Raúl，J. M. M. Montiel，J. D. Tardós. ORB-SLAM：A Versatile and Accurate Monocular SLAM System [J]. IEEE Transactions on Robotics，2015，31（5）：1147-1163.

[7] Mur-Artal Raul，Juan D. Tardós. ORB-SLAM2：An open-source slam system for monocular，stereo，and rgb-d cameras[J]. IEEE Transactions on Robotics，2017，33（5）：1255-1262.

[8] Campos C，Elvira R，Juan J. Gómez Rodríguez，et al. ORB-SLAM3：An Accurate Open-Source Library for Visual，Visual-Inertial and Multi-Map SLAM[J]. 2020.

[9] Davison，Andrew J，et al. MonoSLAM：Real-time single camera SLAM [J]. IEEE transactions on pattern analysis and machine intelligence，2007，29（6）：1052-1067.

[10] Chum O，Matas J. Matching with PROSAC-Progressive Sample Consensus[C]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005.

Visual SLAM Feature Matching Algorithm Based on PROSAC

HAN Jiale, XU Yunhe, GUO Fengjuan, WANG Xiaowang

In the process of visual Simultaneous Localization and Mapping (SLAM), the image feature matching algorithm of Random Sampling Consensus (RANSAC) is usually used to estimate the image model randomly, which is easy to cause the uncertainty of algorithm time complexity, and then lead to excessive image matching time consumption. It is difficult to meet the real-time requirements of visual SLAM. In order to improve the problem, the algorithm of Progressive Sampling Consensus (PROSAC) is used to screen image features and reject mismatched feature points, which effectively improves the efficiency and robustness of image feature matching, and further enhances the stability and real-time performance of visual SLAM. Experimental verification shows that compared with the current visual SLAM feature matching algorithm, the computational efficiency is significantly improved.

Random Sampling Consensus; Visual Simultaneous Localization and Mapping; Image Feature Matching; Oriented FAST and Rotated BRIEF Feature

TP242

A

1674-7976-(2023)-04-248-08

2023-04-19。

韩佳乐（1997.01—），陕西西安人，硕士，主要研究方向为视觉导航定位。