杨弘凡，李 航，陈凯阳，李嘉琪，王晓菲

基于改进ORB算法的图像特征点提取与匹配方法

杨弘凡，李 航，陈凯阳，李嘉琪，王晓菲

(河南科技大学机电工程学院，河南 洛阳 471003)

针对传统ORB算法阈值选取固定，存在误提取、误匹配，无法满足不同图像特征点的准确提取和匹配的问题，提出了一种改进的ORB特征点提取与匹配方法。首先设定局部自适应阈值；然后通过像素分类，设计自适应阈值选取准则，达到ORB特征点的精准提取；最后在改进ORB特征点基础上通过PROSAC算法完成对特征点的匹配。实验结果表明，改进后的方法对亮度变化具有较强的适应能力，计算速度和提取精度得到了提升。匹配总时间降低，误匹配点对数量较少，正确匹配率较高，具有良好的准确性和实时性。利用匹配阶段得到的特征点进行跟踪时得到的RMSE误差较小，表明匹配精度得到了较大提升。和其他方法相比，具有更好的环境适应能力和应用价值。

特征点提取；局部自适应阈值；重复率；特征点对匹配；跟踪

同步定位与地图构建(simultaneous localization and mapping，SLAM)在智能机器人、无人驾驶、无人机、增强现实(augmented reality，AR)等方面有着巨大地应用和研究价值。其中，大多数定位和构图的研究集中于视觉SLAM，其关键问题是从视觉图像中找到具有代表性的图像特征。图像特征一般分为点特征、线特征、面特征，由于点特征具有在相机视角发生少许变化时能保持不变的独特优点而备受关注[1-2]。特征点提取与匹配是视觉SLAM环境感知的重要环节，对于目标识别、图像重构等具有非常重要的意义。

定向二进制简单描述符(oriented fast and rotated brief，ORB)适当降低了特征点的精度和健硕性，提升了计算速度、减少了计算时间，是不同类型特征点中质量和性能较好的折中[3-5]。在ORB图像特征点提取与匹配领域，专家学者围绕目标检测、减少耗时、精确匹配等问题做了许多改进。文献[6]提出了一种改进的ORB特征匹配和差分相乘算法融合的检测方法，采用基于K最近邻的特征点描述，对前后两帧特征点进行双向匹配，再通过顺序抽样一致性算法进一步提纯，该算法运算速度十分优秀。文献[7]在尺度不变特征变换(scale-invariant feature transform，SIFT)算法的基础上提出了一种改进的ORB算法。文献[8]根据投影图像像素点与三维网格端点的映射关系计算三维特征点对，并对加速稳健特征(speeded-up robust features，SURF)点进行匹配，通过匹配的特征点对求取模型变换矩阵完成配准。文献[9]提出了将ORB算法和SURF算法相结合的SURB算法用于特征点检测。文献[10]提出了一种利用ORB技术，并通过将随机抽样一致算法(random sample consensus，RANSAC)作为后处理步骤来消除多余的关键点和噪声，提高了ORB效率以便提供一个稳定的图像识别系统。文献[11]使用SURF提取特征点，渐进采样一致算法(progressive sample consensus，PROSAC)剔除误匹配点对。文献[12]利用快速近似最近邻搜索算法实现高维向量空间中的快速匹配，采用改进的PROSAC算法剔除误匹配进一步提高匹配正确率。

在道路、城市、校园等场景，由于光照不均匀和阴影等因素，会带来图像亮度的改变。虽然上述方法可以较准确地提取图像特征点并剔除误匹配点对，但在图像亮度改变时，现有方法的稳定性不高、适应能力差，并且提取的结果会出现大量重叠。针对这些缺陷本文对原始ORB算法进行了改进，采用自适应阈值的FAST关键点提取算法，根据像素的亮度自动设计、计算阈值，从而提高ORB特征点提取的精度。在特征点匹配阶段，利用改进ORB特征点的优势，在此基础上使用PROSAC算法对改进后的特征点进行匹配，从而减少匹配过程的迭代次数。实验测试在KITTI数据集的城市、居民区、道路、校园等场景进行，结果表明相较于传统算法以及当前相关类似算法，改进ORB算法提取的特征点在亮度变化时的数量、重复率更加稳定，耗时也得到了降低。在特征点对匹配阶段，改进ORB-PROSAC匹配算法减少了匹配阶段耗时，降低了误匹配点对数量，增加了正确匹配率。同时利用匹配得到的有效特征点对进行了跟踪测试，较小的均方根误差(root mean squared error，RMSE)也间接反映了匹配的准确性。

1 改进后的ORB特征点提取与匹配

ORB的特征点检测部分采用的是FAST关键点。FAST关键点是一种角点，与SIFT、SURF检测相比，具有操作快速和计算量低的特点，在计算机视觉的角点检测中被广泛使用。图1为FAST关键点示意图，在图像中为候选角点，亮度为I。图1主要分析以为圆心，半径为3的圆周上的16个像素点。

图1 FAST关键点检测示意图

FAST关键点检测如下[13]

其中，I为16个像素中第个像素的亮度；为固定阈值。当S=时，该像素归类至dark类；当S=时，归类至similar类；当S=时，归类至bright类。如果有9个连续的像素属于dark或bright类，则可以被认为是特征点(即FAST-9)[14]。当圆周上有连续9个像素的亮度属于dark或bright类，该像素为特征点，否则舍弃。在实际运算中，为了检测出连续9个符合条件的像素，需要从像素1~9，2~10，···，8~16范围内检测。最理想情况需要计算9个像素亮度，最差则需要计算54个像素亮度。

由于FAST关键点不具备方向性，因此在ORB算法中添加了对旋转的描述，实现的方法是给FAST点分配一个方向，使其成为具有方向性的FAST点(oriented-FAST，o-FAST)，方向性的计算是通过灰度质心法实现的[15]。

1.1 基于改进FAST的ORB特征点提取方法

FAST检测中的阈值是人为设定的，设置为亮度的一定百分比。在传统方法中，需将圆周上的所有像素点根据固定阈值与中心像素点比较，才能排除非特征点，计算量巨大。随着光照的变化，视觉系统所采集的图像亮度也会变化，特征点将出现误提取和误排除的现象。如果用固定全局或局部阈值，无法兼顾整幅图像的各处，难以达到理想效果，故可以采用动态局部阈值法：用自适应阈值分割的思想，将图像中每个像素设置为不同的阈值。选取方法是对每个像素定义阈值，即

其中，max为圆周上亮度最大的像素点的亮度；min为最低像素点的亮度；I为去掉max，min后剩余14个像素点亮度的平均值。由于max，min，I均不是固定值，因此是动态局部阈值。

为了减少计算量，需对候选特征点进行快速筛选，且不需要将圆周上所有像素点与中心像素点比较。方法如下：直接检测圆周上第1，5，9，13个像素点的亮度(也可以选取2，6，10，14等，需间隔3个像素)。当有3个像素同时属于dark或bright类，则该像素点可能是候选点，否则直接排除。判断3个像素为候选点后，检测3个像素包围环内覆盖的剩余6个像素亮度，若剩余6个像素点的亮度均属于dark或bright类，则该点是正确特征点。

改进FAST算法的ORB特征点提取流程图如图2所示。

图2 改进FAST算法的ORB特征点提取流程图

1.2 基于改进ORB特征点的PROSAC匹配

ORB特征点的准确快速提取为特征点对的匹配打下了良好基础。特征点对匹配可解决不同帧间的数据关联问题。匹配过程中出现的欠匹配、误匹配等情况，被称为异常值。尽管这些异常值与所有特征点对总和相比不值得一提，但其会产生很多错误，比如在双目视觉中会降低左右两帧图像之间单应性矩阵的精度，进而影响双目视觉系统的测量精度，对于初始位姿估计有很大影响，最终在整个运动中积累误差。传统的误匹配去除方法有RANSAC、松弛迭代法、最小中值法以及基于视差的滤波算法，但在匹配中耗时巨大，精度不够。本文利用基于改进ORB特征点的PROSAC算法，即以ORB-PROSAC算法对误匹配进行改进，保持系统的实时性。

PROSAC算法是在RANSAC算法基础上进行的改进。RANSAC算法随机抽取样本，不考虑样本之间的差异性，即优良程度。在实际情况中，样本内点概率高、低不等。PROSAC假设采样集合中正确的点集比错误的数量多，即内点数量大于外点数量。本文使用的改进ORB算法本身内点概率高，因此非常适合于PROSAC算法。PROSAC算法如下：

求特征点匹配对的最邻近和次邻近的汉明距离的比值，即

其中，为特征点的特征向量；为一幅图中最邻近点的特征向量；为一幅图中次邻近特征点的特征向量；为向量之间的距离。

匹配点与非匹配点的汉明距离有着明显的不同，故设定0.7倍最大汉明距离为阈值。当小于阈值时，对采样点集合按照匹配质量由优到差排列。其中质量函数为，如式(4)所示

改进ORB-PROSAC算法匹配流程：

(1) 设置迭代初值和最大迭代次数。

(2) 判断迭代次数是否大于最大迭代次数。若是，在未找到合适的数学模型时，给出提示；反之，进行下一步。

(3) 对采样点集合按匹配质量降序排列，选取个质量较高的数据。

(4) 从个数据中随机选取个，计算模型参数，并计算用此模型参数得到的误差小于内点误差阈值的数据数量，判断数据数量是否大于设定的阈值，若是，返回内点和模型参数；若不是，迭代次数加1，返回第(2)步。

由于改进的ORB特征点提取算法对于特征点数目起到了良好的限制，便在很大程度上减少了改进ORB-PROSAC匹配阶段的迭代次数，从而降低耗时。

2 实 验

2.1 实验环境

ORB特征点提取实验在KITTI-raw数据集上进行，KITTI是自动驾驶汽车专用数据集，囊括了众多传感器对行车环境的采集数据，数据采集系统由4台摄像机(2台灰度，2台彩色，可自由选择使用灰度或彩色数据)，一个Velodyne 3D激光雷达，4个光学镜头，以及1个GPS导航系统组成。其用于测试立体图像、光流、视觉测距、3D物体检测和3D跟踪等。本文采用路径为城市场景下的2011_09_28_drive_0016、道路场景下的2011_09_ 26_drive_0029、居民区场景下2011_09_26_drive_ 0046以及校园场景下的2011_09_28_drive_0105作为实验数据。测试环境设置为Windows 7，Inteli3- 4170，4 G RAM，matlab R2014a。设置原ORB算法程序中阈值threshold=40。经实验，当改进ORB算法程序中自适应参数取10%~30%时，特征点数量较多且出现了重叠、聚集。低于10%或高于30%时会造成判断条件过大或过小，尽管此时特征点没有重叠、聚集，但数量较少，无法准确反映整幅图像，故在以下实验中取=20%。为了使对比效果明显，特征点提取阶段不进行非极大值抑制[15]，在匹配实验中再进行非极大值抑制，匹配阶段使用的实验图像是可变基线双目立体相机在室外拍摄的一帧左右目图像。

2.2 特征点提取实验

测试在KITTI-raw数据集中的4个主要场景中进行，实验结果如图3所示。从图3(a)可以看出，原方法在提取特征点时出现3处具有大量重叠特征点，分别为框出的树干间空隙处、枝叶间空隙处及路面处，同时路面上车道标识线也有特征点聚集。从图3(b)可以看出，改进后的方法提取的特征点数量明显减少，几乎没有重叠特征点，且分布均匀，在一定程度上抑制了特征点的聚集。如图3(c)所示，尽管原方法可以检测到道路环境中的车道线，但是特征点聚集度过大，且远处车辆也未被有效检测出来。使用改进后方法可以准确地检测到居民区中的车道线、边缘线和远处的车辆，如图3(d)所示。图3(e)为原方法提取的特征点出现了大量重叠，未检测到居民区中的车辆，而图3(f)为改进方法可以均匀地检测居住区中房屋和车辆的特征点。如图3(g)和图3(h)所示，改进方法相较于原方法可以更加均匀地在校园环境中检测到行人、车辆和车道线。

图像亮度变化包括部分阴影、对比度的变化和整体图像亮度变化。部分阴影和对比度的变化可以对连续帧数据进行实验，因为汽车行进过程采集的连续帧数据包含了场景的变化，以及亮度阴影的变化，该实验在2.3节中进行详细描述。整体亮度变化可以通过人为改变整幅图像亮度进行模拟。

为了验证本文优化后的ORB算法在整体亮度变化中具有一定的适应能力，在城市场景的实验原图基础上人为分别增加和减少50%的亮度进行模拟，如图4和图5所示。从图5(a)可以看出，当亮度减少50%后，改进ORB算法特征点数量不仅未减少，反而出现了轻微增加，检测范围也扩大，特征点分布均匀无重叠；而图4(a)中，原ORB算法检测的特征点在亮度减少50%后数量剧烈减少且含有大量重叠。同样的，可以看到在亮度增加50%后，改进ORB算法具有较高的准确性。

图4 亮度变化下原方法城市场景提取效果

2.3 特征点对匹配实验

对双目相机在室外采集的图像分别应用本文算法、传统ORB算法、SURF算法[16]、SURB算法[9]进行测试。所有待匹配图像特征点与其最邻近点、次邻近点汉明距离比值的阈值设置为0.7。

匹配结果如图6所示，为了增加匹配结果的可视化效果，设黄色线段为正确匹配的线段，绿色线段为误匹配线段。从图6(a)可以看出，传统ORB算法检测范围较广，但误匹配点对多，特征点聚集程度大；从图6(b)可以看出，SURF算法只有1对误匹配点对，正确匹配率极高，但检测范围太小，无法对整幅图像进行有效检测；从图6(c)可以看出，SURB算法相较于SURF算法，误匹配点对增多，检测范围仍然有限；从图6(d)可以看出，本文算法相较于SURF、SURB算法，扩大了检测范围、对图像各个区域都有良好的检测，且没有特征点对聚集。相较于传统ORB算法，本文算法的误匹配点对大大减少，特征点对重叠现象也得到了消除。

表1是不同算法组合时的特征点对匹配指标结果数据。从表1结果可以看出：①在匹配阶段，本文方法剔除误匹配点对的时间只有48.8 ms，远远小于其他3种方法，这是因为改进的ORB特征点提取算法对于特征点数目进行了筛选，大大节省了匹配阶段的迭代时间；②本文方法的误匹配点对只有7对，正确匹配率达到了89.8%，高于传统ORB和SURB算法。尽管正确匹配率低于SURF算法，但是总耗时远远小于SURF算法，且从图7可以看到，SURF算法的检测范围远不及本文算法。

表1 不同算法特征点对匹配结果对比

为了进一步验证特征点对匹配效果的影响，使结果表达更加清晰，本文对特征点进行了路径跟踪实验。因为跟踪时坐标计算的前提即为匹配点对像素点对的坐标，故特征点的跟踪结果可以反映特征点匹配的效果。将本文方法与基于传统ORB特征的方法和中值滤波+RANSAC方法进行对比。

在KITTI原始数据集中对3种不同场景进行测试，这些原始数据集由多幅包括行人和汽车等移动对象的连续帧组成。住宅区路径为：2011_09_26_ 0046，其包含125帧；道路区路径为2011_09_26_ 0029，包含130帧；校园区路径为2011_09_28_0105，包含106帧。以上每一组数据均是在车辆行进中采集的，包含场景的逐渐改变，以及场景改变带来的图像阴影、对比度的改变。特征点提取阶段，实验图像亮度变化是通过人为改变图像整体亮度进行模拟的，而此处为实际应用情况下的部分阴影、对比度变化。因此对上述3组数据的实验可以间接证明改进ORB算法的鲁棒性。

实际轨迹、本文算法的轨迹和其他轨迹的定性比较如图7所示。表2是在KITTI原始数据集中不同场景中3种不同方法在3次执行中的RMSE，RMSE在文中衡量的是模拟轨迹与真实轨迹的偏离程度，其值越大说明与真实轨迹偏离越远，反之贴合程度越近。从表2可以看出在居民区场景和校园场景的RMSE误差均小于1.00 m，且低于传统ORB特征的方法和中值滤波+RANSAC方法。在道路场景下RMSE误差增加为2.21 m，低于其他同类算法，略大于其他2个场景下的误差，这是由于所测试的道路场景面积较大，误差积累所致。

表2 不同场景下的RMSE误差对比

3 结束语

本文针对亮度变化下ORB特征点提取不稳定、正确匹配率较低等问题，提出了一套特征点提取、匹配流程的方法。首先设计了一种基于自适应阈值的ORB特征点提取算法，实现了亮度变化下室外场景图像ORB特征点的稳定、精确提取。其次利用改进ORB特征点无聚集、数量少的优势，在匹配阶段基于改进ORB特征点的基础上使用PROSAC算法来对改进后的特征点进行匹配，以减少迭代次数。

实验结果表明改进ORB算法切实有效，提高了在不同场景下、不同光照变化下的稳定性、鲁棒性，能够有效去除误匹配点对、提高正确匹配率、减小RMSE误差。整套特征点提取和匹配流程尤其适用于对系统速率和稳定性要求高的场合。该研究对ORB-SLAM的环境感知，定位导航研究具有良好的实用价值。下一步工作是用视觉系统执行所改进的算法，完成运动位姿估计和地图构建。

[1] BAYRAKTAR E, BOYRAZ P. Analysis of feature detector and descriptor combinations with a localization experiment for various performance metrics[J]. Turkish Journal of Electrical Engineering & Computer Sciences, 2017, 25(3): 2444-2454.

[2] 刘国忠, 胡钊政. 基于SURF和ORB全局特征的快速闭环检测[J]. 机器人, 2017, 39(1): 36-45. LIU G Z, HU Z Z. Fast loop closure detection based on holistic features from SURF and ORB[J]. Robot, 2017, 39(1): 36-45 (in Chinese).

[3] 柴江龙, 樊彦国, 王斌, 等. 尺度及主方向改正的ORB特征匹配算法[J]. 计算机工程与应用, 2019, 55(13): 178-185. CHAI J L, FAN Y G, WANG B, et al. Improved ORB feature matching algorithm for scale and main orientation correction[J]. Computer Engineering and Applications, 2019, 55(13): 178-185 (in Chinese).

[4] ZHAO Q, FENG W, WAN L, et al. SPHORB: a fast and robust binary feature on the sphere[J]. International Journal of Computer Vision, 2015, 113(2): 143-159.

[5] 李兵, 刘磊, 魏志强. 一种具有强实时性、强鲁棒性的图像匹配算法[J]. 软件学报, 2014, 25(7): 1583-1592. LI B, LIU L, WEI Z Q. A strong robust real-time image matching algorithm[J]. Journal of Software, 2014(7): 219-228 (in Chinese).

[6] 刘威, 赵文杰, 李成, 等. 基于改进ORB特征匹配的运动小目标检测[J]. 光电工程, 2015, 42(10): 13-20. LIU W, ZHAO WJ, LI C, et al. Detecting small moving target based on the improved ORB feature matching[J]. Opto-Electronic Engineering, 2015, 42(10): 13-20 (in Chinese).

[7] QIN Y Y, XU H K, CHEN H R. Image feature points matching via improved ORB[C]//2014 IEEE International Conference on Progress in Informatics and Computing. New York: IEEE Press, 2014: 204-208.

[8] 童立靖, 刘博文. 基于投影图像SURF特征提取的三维模型配准[J]. 图学学报, 2018, 39(6): 1117-1122. TONG L J, LIU B W. 3D model registration based on SURF feature extraction of projection images[J]. Journal of Graphics, 2018, 39(6): 105-110 (in Chinese).

[9] 戴雪梅, 郎朗, 陈孟元. 基于改进ORB的图像特征点匹配研究[J]. 电子测量与仪器学报, 2016, 30(2): 233-240. DAI X M, LANG L, CHEN M Y. Research of image feature point matching based on improved ORB algorithm[J]. Journal of Electronic Measurement and Instrumentation, 2016, 30(2): 233-240 (in Chinese).

[10] VINAY A, RAO A S, SHEKHAR V S, et al. Feature extractionusing ORB-RANSAC for face recognition[J]. Procedia Computer Science, 2015, 70: 174-184.

[11] 李伦. 基于PROSAC算法的室内定位算法研究[D]. 哈尔滨: 哈尔滨工业大学, 2018. LI L. Research on indoor localization based on PROSAC algorithm[D]. Harbin: Harbin Institute of Technology, 2018 (in Chinese).

[12] 张皖南, 杨学志, 董张玉. 一种改进的SAR与可见光图像的快速配准算法[J]. 图学学报, 2018, 39(2): 209-213. ZHANG W N, YANG X Z, DONG Z Y. Registration between SAR and optical images based on an improved rapid algorithm[J]. Journal of Graphics, 2018, 39(2): 209-213 (in Chinese).

[13] HUANG J J, ZHOU G Q, ZHOU X, et al. A new FPGA architecture of FAST and BRIEF algorithm for on-board corner detection and matching[J]. Sensors, 2018, 18(4): 1014.

[14] ROSTEN E, DRUMMOND T. Machine learning for high-speed corner detection[M]//Computer Vision – ECCV 2006. Heidelberg: Springer, 2006: 430-443.

[15] 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, 2008, 32(1): 105-119.

[16] CHEON S H, EOM I K, MOON Y H. Fast descriptor extraction method for a SURF-based interest point[J]. Electronics Letters, 2016, 52(4): 274-275.

Image feature points extraction and matching method based on improved ORB algorithm

YANG Hong-fan, LI Hang, CHEN Kai-yang, LI Jia-qi, WANG Xiao-fei

(School of Mechatronics Engineering, Henan University of Science and Technology, Luoyang Henan 471003, China)

Thefixed threshold selection of traditional ORB algorithm results in many false extractions and mismatches, which cannot meet the requirements of accurate extraction and matching of different image feature points. To solve this problem, an improved ORB feature point extraction and matching method was proposed. Firstly,the local adaptive threshold was set up. Then, an adaptive threshold selection criterion was designed by classifying the pixels, and thus the precise extraction of ORB feature points was achieved. Finally, the PROSAC algorithm was used to complete the matching of feature points based on the improved ORB feature points. The experimental results indicate that the improved method has a high adaptability to variations in brightness, and both the calculation speed and extraction accuracy are greatly improved. The total matching time is reduced, the number of mismatches is less, and the accurate matching rate is increased, which indicates that this improved method is characterized with accuracy and real-time performance. In addition, the RMSE error obtained by tracking the feature points acquired at the matching stage is small, which demonstrates a significant improvement in matching accuracy. Compared with other existing methods, this method has better environmental adaptive capacity and application value.

feature point extraction; local adaptive threshold; repetition rate; point pairs matching; tracking

TP 391

10.11996/JG.j.2095-302X.2020040548

A

2095-302X(2020)04-0548-08

2020-02-06；

2020-03-13

13March，2020

6 February，2020；

国家重点研发计划重点专项(2018YFB200502)；河南省科技攻关项目(182102110420)

National Key Research and Development Program (2018YFB200502); Key Science and Technology Program of Henan Province (182102110420)

杨弘凡(1994-)，男，河南洛阳人，硕士研究生。主要研究方向为计算机视觉。E-mail：hongfan1017@sina.com

YANG Hong-fan (1994-), male, master student. His main research interest covers computer vision. E-mail：hongfan1017@sina.com