ORB算法由Rublee等在2011年提出[6]，该算法通过FAST[7]算法提取特征点，通过BRIEF[8]计算得到描述子，使得系统对于噪声具有更高的鲁棒性。与之前的算法相比，ORB算法在计算速度上具有绝对的优势，在计算速度上是SURF的10倍，是SIFT的100倍[9]，能满足实时性要求，但是其鲁棒性不如SIFT，且不具备尺度不变性，在图像匹配中容易造成误匹配[10]。文献[11]对传统ORB算法进行了改进，提出了一种基于模块化区域分割的ORB算法，算法虽能保证特征点均匀提取，但无法按照实际要求改变特征点的提取数量，且提取速度也要慢于传统ORB算法。文献[12]针对ORB算法不具有尺度不变性和匹配精度低的问题，提出了一种结合SURF算法和BBF(Best Bin First)算法的思想对ORB算法进行改进，算法虽然提高了匹配精度，但提取速度相较于传统ORB算法却慢很多，无法保证系统的实时性。
本文提出了一种全新的基于区域划分的ORB算法，在保证特征点提取速度的同时，使得后续的特征点匹配精度也得到了提高。
1 ORB算法原理 1.1 特征点检测 图像特征点能够简单理解为图像中更重要的点，如轮廓点、较暗区域的高光点、较亮区域的暗点等。ORB算法运用FAST算法来寻找特征点，FAST的核心思想是找出那些突出的点，即将一个点与周围的点进行比较，如果与周围的大多数点不同，则可以将其挑选出来作为一个特征点。图 1为FAST特征点的提取示意图。
 |
| 图 1 FAST特征点提取示意图 Fig. 1 Schematic diagram of FAST feature point extraction |
| 图选项 |
FAST具体计算过程如下：
步骤1? ?从图 1中挑选一个像素点P，判断它是否可以作为特征点。首先假设它的灰度值为Ip。
步骤2? ?设值一个合适的阈值t (比如Ip的20%)，当2个点的灰度值之差的绝对值大于t时，可以认为这2个点不相同。
步骤3? ?以像素点P为圆心，挑选出半径为3的圆上的16个像素点。
步骤4? ?假如这16个像素点中有连续的l个点的灰度都大于Ip+t或者都小于Ip-t，那么P就可以被认为是一个角点。这里l设定为12, 若有至少12个点超过阈值，则认为P是特征点；否则，认为P不是特征点。
步骤5? ?为了更高效地检测出特征点，可以增加一项预判操作，这样可以快速地筛选掉大部分不是角点的像素点。通过直接检查邻域圆上的1、9、5和13这4个位置的像素点灰度进行预判。
首先检查1和9，看它们是否和P点相同，如果是，再检查5和13。只有当这4个像素点中的3个同时大于Ip+t或者同时小于Ip-t时，P点才被认为是一个角点。如果不能满足上述条件，则不能作为角点，直接排除。通过该操作可以获得3种不同的点，如下：
 | (1) |
式中：Sp→x为第x个点提取到的点集；Ip→x为圆上16个点中的第x个点的灰度值；a为圆上比P点暗的点；b为圆上与P点相似的点；c为圆上比P点亮的点。
1.2 计算特征点描述子 ORB使用改进的BRIEF算法计算一个特征点的描述子。其核心思想是在特征点P的周围以特定模式选取n个点对，把这n个点对的比对结果组合起来作为描述子[13]。
计算描述子具体步骤如下：
步骤1? ?以特征点P为圆心，以d为半径做圆O。
步骤2? ?在圆O内选取n个点对。为了便于描述，令n=4。如图 2所示，将挑选出的4个点对分别标记为：P1(A, B)、P2(A, B)、P3(A, B)、P4(A, B)。
 |
| 图 2 描述子计算示意图 Fig. 2 Schematic diagram of descriptor calculation |
| 图选项 |
步骤3? ?定义操作T。
 | (2) |
式中：Iα和Iβ分别为A和B的灰度值。
步骤4? ?分别对挑选出的点对进行T操作，将得到的计算结果进行组合。
假如：
 |
则最终的描述子为：1011。
由于FAST算法无法检测到特征点方向信息，在ORB算法中，利用矩来确定特征点的方向，通过计算特征点附近的图像灰度质心[14]来表示。在一个小的图像块B中，定义图像的矩为
 | (3) |
式中：p, q=0, 1, 2, …；I(x, y)为(x, y)点处的灰度值。通过式(3)可以得到零阶矩m00、一阶矩m10和m01。
通过矩可以计算其质心为
 | (4) |
接下来连接图像的几何中心O与质心C求取向量
 | (5) |
由于BRIEF描述子不具备旋转不变性，在对其增加方向信息后，在(xi, yi)的位置，对n个点对定义矩阵A为
 | (6) |
变换矩阵利用特征点的方向角θ与旋转矩阵Rθ进行变换:
 | (7) |
式中：Aθ为旋转后的特征点对矩阵; Rθ=
BRIEF中点对灰度值的比较值又叫做binary test值，其定义为
 | (8) |
式中:p(x)和p(y)分别为点x和点y处的像素灰度值。随机选择n个点对(xi, yi)就可以生成一个二进制字符串，则生成的特征描述子可以表示为
 | (9) |
于是，改进后的描述子为
 | (10) |
得到改进的描述子后，再进行搜索，在像素块中挑选n个点对作为最终的描述子[15]。
2 改进ORB算法 ORB算法使用FAST算法检测图像特征点，获得的特征点分布密集，存在冗余。一般来说，特征点越多，则获得的图像匹配越准确，但特征点密集分布对后续的特征描述十分不利，并且会影响图像匹配精度[16]。本文提出一种基于区域划分的ORB算法，通过对每个区域分别进行特征点提取来解决上述问题。同时，设置自适应阈值，当提取的特征点数量达到条件数量即需要提取的特征点总数时，提前结束来减少特征提取的时间。改进ORB算法流程如图 3所示。
 |
| 图 3 改进ORB算法的流程图 Fig. 3 Flow chart of improved ORB algorithm |
| 图选项 |
算法具体步骤如下：
步骤1? ?在构建图像金字塔时，将图像均匀分割成M×N个大小相同的区域，M为分割的行数，N为分割的列数，在这些区域中，特征点会随机分布。将区域按照先行后列进行排序，表示为{h1，h2，h3，…，hM×N}。
步骤2? ?设置阈值j。
 | (11) |
式中：需要提取的特征点总数Tf与ORB算法提取的特征点总数相同，一般为500，使得特征点能够更加均匀地分布，而且可以节省筛选最佳特征点的时间。
步骤3? ?对每个区域分别进行特征点检测，将每个区域在阈值等于t时检测到的FAST特征点的个数nj与j进行比较，若nj不小于j，则选取j个最佳点；若nj小于j，则降低提取FAST特征点时的阈值t，重新检测。由于只有当两点之间的灰度值之差的绝对值大于阈值t时，才能认为2个点是不同的，才可以进行下一步检测。因此，通过降低阈值t，能够增加灰度值之差的绝对值大于阈值的点的个数，从而可以检测到更多的角点以供筛选。
步骤4? ?经过步骤3的检测，有些区域的特征点数会超过需要的特征点数，容易造成检测出来的点彼此相邻，无法成为最佳特征点，需要筛选掉这一部分点。本文采用非最大值抑制的方法。假设P和Q两点相邻，分别计算两点与周围16个点的差分和，去掉差分和最小的点，直到剩下的点与所需要的点数一致时停止筛选，剩下的即为最佳点。差分和计算公式为
 | (12) |
式中：Sbright为16个邻域像素点中灰度值大于Ip+t的像素点的集合；Sdark为灰度值小于Ip-t的像素点的集合。
步骤5? ?遍历所有图像区域，直到提取的特征总数∑nj达到条件数量时，结束提取。
由于FAST特征点不具有尺度不变性，可以采用SIFT高斯金字塔来实现，高斯金字塔的构建分为两部分：对图像做不同尺度的高斯模糊和对图像做下采样[17]。
高斯模糊常被用来模拟物体在人眼中的快速远近效应。其核心是利用高斯函数对输入图像进行模糊模板解卷积运算，去除图像的高频成分，实现图像的模糊化。高斯函数一维和二维表达式分别为
 | (13) |
 | (14) |
式中：x、y分别为原点到x轴、y轴的距离；σ为高斯函数G的标准差。
本文中通过设置一个比例因子scaleFactor和金字塔层数nlevels，将原图像I按比例因子缩小成nlevels幅图像。缩放后的图像I′为
 | (15) |
分别对nlevels幅不同比例的图像通过本文算法提取特征点，提取的特征点总数作为这幅图像的FAST特征点以解决ORB算法不具有尺度不变性的问题[18]。
本文中高斯金字塔一共生成8层不同尺度的图像，图像金字塔示意图如图 4所示。图中L0~L7分别为第1幅~第8幅下采样图像。
 |
| 图 4 图像金字塔示意图 Fig. 4 Image pyramid illustration |
| 图选项 |
3 实验结果与分析 本实验在Linux系统+Opencv3.4.1平台上实现，原始图像如图 5所示。
 |
| 图 5 原始图像 Fig. 5 Original images |
| 图选项 |
传统ORB算法和本文算法提取的特征点分别如图 6所示。图像匹配结果分别如图 7所示。
 |
| 图 6 不同算法提取结果 Fig. 6 Extraction results of different algorithms |
| 图选项 |
 |
| 图 7 不同算法匹配结果 Fig. 7 Matching results of different algorithms |
| 图选项 |
从图 6可以看出，相较于图 6(a), 图 6(b)的特征点分布更加均匀，大大减少了重叠特征点的数量，说明本文算法提取的特征点更具有代表性，后续的图像匹配也更加准确稳定。匹配准确率对比如表 1所示。
表 1 匹配精度对比 Table 1 Matching accuracy comparison
| 算法 | 总提取点数 | 正确匹配点数 | 匹配准确率/% |
| ORB算法 | 500 | 339 | 67.8 |
| 本文算法 | 469 | 329 | 70.1 |
| 文献[12]改进的ORB算法 | 253 | 233 | 92.1 |
表选项
通过表 1可以看出，本文算法在匹配精度方面较ORB算法提升了3.4%，较文献[12]改进的ORB算法存在一定差距，通过该数据指出了本文算法未来的优化方向。
另一方面，算法运行速度是衡量一个算法优劣的重要标准，在平台相同的情况下，若匹配结果基本相同，则速度越快的算法越好；若运行时间基本相同，则匹配结果越好的算法越优秀。本文将10次实验结果取平均值，实验运行时间的部分截图如图 8所示，算法运行时间和匹配时间比较如表 2、表 3所示。
 |
| 图 8 不同算法运行截图 Fig. 8 Screenshot of running of different algorithms |
| 图选项 |
表 2 算法运行时间比较 Table 2 Comparison of algorithm running time
| 算法 | 总提取点数 | 总运行时间/ms | 平均运行时间/ms |
| ORB算法 | 500 | 32.7 | 0.065 4 |
| 本文算法 | 469 | 25.8 | 0.055 0 |
| 文献[11]改进的ORB算法 | 262 | 32.36 | 0.123 5 |
| 文献[12]改进的ORB算法 | 253 | 88.37 | 0.349 3 |
表选项
表 3 算法匹配时间对比 Table 3 Comparison of matching time
| 算法 | 总匹配点数 | 总匹配时间/ms | 平均匹配时间/ms |
| ORB算法 | 339 | 1.50 | 0.004 4 |
| 本文算法 | 329 | 1.31 | 0.004 0 |
表选项
从表 2可以看出，本文算法在提取速度方面比传统的ORB算法提升了16%，较文献[11]改进的ORB算法速度提升了55%，较文献[12]改进的ORB算法速度提升了84%。从表 3可以看出，在匹配算法相同的前提下，本文算法在匹配速度方面比传统ORB算法提升了9%左右。本文算法不仅提升了特征点提取速度，也使得所提取的特征点分布更加均匀，匹配速度也得到了提升。
4 结论 1) 针对传统ORB算法提取的无效特征点较多且不具有尺度不变性的问题，本文提出了一种基于区域划分的改进的特征点提取算法。
2) 算法将图像进行区域划分，提取的特征点都是在区域中表现最佳的点，通过设置自适应阈值，在特征点提取速度方面获得了较大提升，在图像匹配精度较ORB算法得到了提升，但对比文献[12]改进的ORB算法还存在一定差距。在接下来的工作中，可以通过以下方法对该算法做进一步的优化：在构建图像金字塔时，可以对图像信息进行计算，并自动调节尺度信息，以保证图像的尺度信息更加合理，使算法在尺度不变性方面得到进一步提升。
参考文献
| [1] | 高翔, 张涛. 视觉SLAM十四讲:从理论到实践[M]. 北京: 电子工业出版社, 2017: 10-14. GAO X, ZHANG T. 14 lectures on visual SLAM:From theory to practice[M]. Beijing: Publishing House of Electronics Industry, 2017: 10-14. (in Chinese) |
| [2] | 张全, 盛妍, 吴佐平, 等. 公共区域监控视频数据目标特征跟踪定位方法[J]. 自动化与仪器仪表, 2020(1): 51-54. ZHANG Q, SHENG Y, WU Z P, et al. Target tracking and location method for common area surveillance video data[J]. Automation & Instrumentation, 2020(1): 51-54. (in Chinese) |
| [3] | LOWE D G. Distinctive image features from scale invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110. DOI:10.1023/B:VISI.0000029664.99615.94 |
| [4] | BAY H, TUYTELAARS T, VAN GOOL L.Surf: Speeded up robust features[C]//European Conference on Computer Vision.Berlin: Springer, 2006: 404-417. |
| [5] | ROSTEN E, PORTER R, DRUMMOND T. Faster and better:A machine learing approach to corer detection[J]. Analysis and Machine Intelligence, 2008, 32(1): 105-119. |
| [6] | RUBLEE E, RABAUD V, KONOLIGE K, et al.ORB: An efficient alternative to SIFT or SURF[C]//Proceedings of IEEE International Conference on Computer Vision.Piscataway: IEEE Press, 2011: 2564-2571. https://www.researchgate.net/publication/221111151_ORB_an_efficient_alternative_to_SIFT_or_SURF |
| [7] | VISWANATHAN D G.Features from accelerated segment test(FAST)[EB/OL].(2016-04-15)[2020-01-10].https://www.cnblogs.com/ronny/p/4078710.html?utm_source=tuicool. |
| [8] | CALONDER M, LEPETIT V, STRECHA C, et al.Brief: Binary robust independent elementary features[C]//European Conference on Computer Vision.Berlin: Springer, 2010: 778-792. |
| [9] | 刘伟, 钱莉. 基于OpenCV环境的SIFT、SURF、ORB算法比较分析[J]. 化工自动化及仪表, 2018, 45(9): 714-716. LIU W, QIAN L. Comparative analysis of SIFT and SURF and ORB algorithms based on OpenCV environment[J]. Control and Instruments in Chemical Industry, 2018, 45(9): 714-716. (in Chinese) |
| [10] | ZHAO H Y, ZHAO H C, LV J F, et al. Multimodal image matching based on multimodality robust line segment descriptor[J]. Neurocomputing, 2016, 177: 290-303. DOI:10.1016/j.neucom.2015.11.025 |
| [11] | 潘盼. 一种改进的ORB算法[J]. 微型机与应用, 2017, 36(20): 23-26. PAN P. An improved ORB algorithm[J]. Microcomputer & Its Applications, 2017, 36(20): 23-26. (in Chinese) |
| [12] | 马丹, 赖惠成. 改进ORB算法的图像匹配[J]. 计算机仿真, 2018, 35(10): 274-278. MA D, LAI H C. Image matching based on improved ORB[J]. Computer Simulation, 2018, 35(10): 274-278. (in Chinese) |
| [13] | 陈思聪, 刘晶红, 何林阳, 等. 一种用于图像拼接的改进BRISK算法[J]. 液晶与显示, 2016, 31(3): 324-330. CHEN S C, LIU J H, HE L Y, et al. Improved BRISK algorithm used in image mosaic[J]. Chinese Journal of Liquid Crystals and Displays, 2016, 31(3): 324-330. (in Chinese) |
| [14] | 范新南, 顾亚飞, 倪建军. 改进ORB算法在图像匹配中的应用[J]. 计算机与现代化, 2019(2): 1-6. FAN X N, GU Y F, NI J J. Application of improved ORB algorithm in image matching[J]. Computer and Modernization, 2019(2): 1-6. (in Chinese) |
| [15] | HUANG C, ZHOU W D. Fast scene matching navigation algorithm based on ORB[J]. Journal of Information and Computational Science, 2014, 11(11): 3857-3863. |
| [16] | 李玉峰, 李广泽, 谷绍湖, 等. 基于区域分块与尺度不变特征变换的图像拼接算法[J]. 光学精密工程, 2016, 24(5): 1197-1205. LI Y F, LI G Z, GU S H, et al. Image mosaic algorithm based on area blocking and SIFT[J]. Optics and Precision Engineering, 2016, 24(5): 1197-1205. (in Chinese) |
| [17] | 王健, 于鸣, 任洪娥. 一种用于图像拼接的改进ORB算法[J]. 液晶与显示, 2018, 33(6): 520-527. WANG J, YU M, REN H E. Improved ORB algorithm used in image stitching[J]. Chinese Journal of Liquid Crystals and Displays, 2018, 33(6): 520-527. (in Chinese) |
| [18] | 姚海芳, 郭宝龙. 一种基于ORB的特征匹配算法[J]. 电子设计工程, 2019, 27(16): 175-179. YAO H F, GUO B L. An ORB-based feature matching algorithm[J]. Electronic Design Engineering, 2019, 27(16): 175-179. (in Chinese) |
