特征匹配的主要过程是在2幅图像中提取特征点，并对特征点进行描述，通过比较特征点之间相似度判断是否匹配[2]。常用的图像特征提取方法包括SIFT[3]、SURF[4]、ORB[5]、LIET[6]、Key.Net[7]、RF-NET[8]等。Lowe[3]提出的SIFT特征具有尺度、旋转和光照等的不变性，但计算时间长[9]。Bay等[4]改进了SIFT特征，提出了SURF特征，提高了特征提取的速度[10]。FAST角点能够快速确定特征点的位置[11]，但不具有方向信息[12]。Calonder等[13]提出了对特征点周围图像区域进行描述的BRIEF描述子。Rublee等[5]改进FAST角点和BRIEF描述子，提出了ORB特征，其能够有效替代SIFT和SURF[14]。ORB适当降低了精度，但提取速度比SIFT、SURF快，是不同类型特征点中性能与质量的较好折中[15]。
上述方法的主要思想是改进特征点的提取方式或改进描述子使特征点更具独特性。改进特征点的方法虽然可以改善特征匹配，但无法有效剔除误匹配。此外，Muja和Lowe[16-17]通过建立kd-tree和k-means tree的方法加快了特征匹配速度，但仍无法有效剔除误匹配。
RANSAC (Random Sample Consensus)算法可以剔除误匹配，但当误匹配较多时，效果会下降[18-20]。Bian等[20]提出运动网格统计算法(Grid-based Motion Statistics, GMS)，通过统计匹配点邻域内的支持度剔除误匹配。但在图像模糊等条件下，匹配准确率下降[2, 21]。本文提出了一种改进的ORB特征匹配算法。首先, 分散化提取ORB特征点，使提取的特征点更具代表性[22]。然后，利用暴力匹配和交叉验证得到初步的匹配集合。最后，利用GMS剔除匹配集合中的误匹配，同时使用高斯核对GMS的统计结果加权，优化匹配结果。
1 特征提取 ORB特征是计算机视觉领域常用的图像特征之一，其具有旋转、尺度不变性和提取速度快的优点。由于ORB特征在确定关键点时以阈值作为判断条件，当图像中某一区域有多个像素满足阈值时，就会出现特征点集中现象。
特征点集中会降低匹配的准确性，为使特征点均匀分布，改进后的算法在特征点的提取过程中引入四叉树结构[22]，具体步骤如下：
1) 将图像划分为大小相同的网格(这里的网格与后文的GMS网格不是同一个)，在每个网格中提取FAST角点。
2) 将图像分为4个子节点，判断各个子节点中特征点的数目，如果大于1，将这个子节点再次划分为4个子节点，直至所有的子节点的数目大于预先设置的特征点数目为止。
3) 在每一个子节点中保留响应值最大的FAST角点，其余角点均删除。
2 特征匹配 2.1 改善暴力匹配结果 提取的ORB特征点通过暴力匹配获得粗匹配集合，但是暴力匹配无法剔除误匹配。在图像匹配中经常采用交叉验证的方法进行误差剔除，因此改进后的算法在暴力匹配中引入交叉验证剔除误匹配。
交叉验证虽然可以剔除部分误匹配，但得到的匹配集合中仍包含许多误匹配，因此在交叉验证后采用GMS对误匹配做进一步的剔除。
2.2 GMS基本理论 如图 1所示，GMS通过统计每一对匹配点邻域内的匹配总数，实现正确匹配与错误匹配的区分。
 |
| 图 1 GMS示意图 Fig. 1 Schematic of GMS |
| 图选项 |
在2幅图像中分别提取N个和M个特征点，每个点的匹配概率独立，设正确匹配的概率为t。通过暴力匹配得到匹配集合X={x1, x2, …, xN}。设匹配xi在2幅图像中的邻域a、b中各包含n个、m个特征点，fa为a中的1个特征点。如果xi是1个正确匹配，则fa的匹配点落在b区域的概率为
 | (1) |
式中：Tab为xi是正确匹配；fab为fa的匹配点落在b区域；fat为fa匹配正确，faf为fa匹配错误；β为1个调节因子。
同理，如果xi是1个错误匹配，则fa的匹配点落入b区域的概率为
 | (2) |
式中：Fab为xi是错误匹配。
xi邻域内匹配点的总数为其支持度，设为Si，Si的概率分布是二项分布：
 | (3) |
2.3 GMS网格化 如图 2所示，为提高计算效率，实际计算中一般将图像划分为20×20个网格，计算每个网格的支持度。
 |
| 图 2 图像网格化示意图 Fig. 2 Schematic of grid-based image |
| 图选项 |
每个网格支持度的统计区域为该网格及其周围的8个网格：
 | (4) |
式中：|xikjk|为2幅图中对应的2个网格的匹配点数目；Sij同样符合二项分布：
 | (5) |
式(5)说明每个网格在它的邻域内都有支持度，但支持度分布不同，其分布为双峰形式，因此通过选择合适的阈值，可以有效地判断该网格是否可以接受。设阈值为
 | (6) |
式中：nij为9个网格中匹配点数目的平均值；α为调节阈值的参数，Bian等在论文中令α的值为6[20]。
2.4 改进GMS 如图 2所示，a5为待判断网格，a1~a4，a6~a9为其邻域内的8个网格。设a5坐标为(x, y)，a6坐标为(x+1, y)，a9的坐标为(x+1, y+1)。则a1、a3、a7、a9与a5的距离均为
计算机视觉中常用高斯函数生成的高斯核对图像进行加权处理，原因如下：
1) 高斯函数是单值函数，其自变量的函数值随该点与中心点的距离单调递减。
2) 二维高斯函数具有旋转不变性，用高斯函数加权时，各个方向上的权值相同。
3) 高斯函数的宽度由标准差σ表示，且宽度和σ关系简单，通过调节σ可以很容易调节权值大小。
因此，本文选择高斯核对网格进行加权，二维高斯函数为
 | (7) |
以待判断网格a5为中心点，对高斯函数离散化采样并归一化处理，得到3×3加权矩阵：
 | (8) |
式中：A11+A12+…+A33=1。设9个网格与对应网格的匹配点数目为ni(i=1, 2, …, 9)，则网格a5的支持度：
 | (9) |
如果S5大于阈值T，则认为满足GMS要求，否则剔除。
因为a2、a4、a6、a8与中心点的距离为1，如果σ=1，则a2、a4、a6、a8权值的采样点在距中心点的±σ处，所以这里σ取1。
3 实验与结果 本文实验使用的电脑为i7处理器，内存8 GB，操作系统为Ubuntu18.04，实验图像来自Oxford VGG数据集等[23]。为验证本文算法对不同类型图像的性能，选取了4组图像，如图 3所示，分别是图像模糊、光照变化、图像压缩和高斯噪声，每组中包含6幅图片。
 |
| 图 3 实验用图 Fig. 3 Images in experiment |
| 图选项 |
图 4为4组图像的原算法和本文算法的准确率对比。实验以平均准确率、最高准确率、最低准确率和准确率的标准差评价算法的准确性。记最高准确率为H，最低准确率为L, 平均准确率为E，准确率的标准差为S。
 |
| 图 4 准确率对比 Fig. 4 Accuracy comparison |
| 图选项 |
准确率的计算方法如下：
1) 根据得到的匹配点，采用RANSAC方法，计算2幅图像之间的基础矩阵。
2) 满足该基础矩阵的匹配点为内点，并以内点数Ni占匹配点总数Nm的百分比为准确率，准确率为
 | (10) |
在实验中高斯函数的标准差σ取1，调节GMS阈值的参数α取6。
由图 4(a)~(d)可知，在图像模糊、光照变化、图像压缩和噪声情况下，原算法的准确率曲线出现较大波动，准确率下降，本文算法不仅提高了准确率，而且减小了波动。
如表 1所示，在图像模糊条件下，本文算法平均准确率提高了3.5%，标准差下降了2.58%。在光照变化条件下，本文算法平均准确率提高了4.2%，标准差下降了0.92%。在图像压缩条件下，本文算法平均准确率提高了2.2%，标准差下降了0.93%。
表 1 实验结果 Table 1 Experimental results
| 实验图像 | 最高准确率/% | 最低准确率/% | 平均准确率/% | 准确率标准差/% | |||||||
| 原算法 | 本文算法 | 原算法 | 本文算法 | 原算法 | 本文算法 | 原算法 | 本文算法 | ||||
| 图像模糊 | 95.4 | 98.3 | 68.1 | 79.7 | 85.8 | 89.3 | 7.95 | 5.37 | |||
| 光照变化 | 96.8 | 97.8 | 87.5 | 92.7 | 91.2 | 95.4 | 2.48 | 1.56 | |||
| 图像压缩 | 99.8 | 99.7 | 91.3 | 94.3 | 95.7 | 97.9 | 2.65 | 1.72 | |||
| 高斯噪声 | 96.3 | 98.3 | 74 | 57.1 | 86.2 | 92.2 | 7.21 | 9.57 | |||
表选项
在高斯噪声条件下，本文算法平均准确率提高了6%，但标准差提高了2.36%。如果去除实验顺序为15的数据，原算法的标准差是6.97%，本文算法的标准差是2.02%，本文算法标准差下降了4.95%，平均准确率提高7.3%。
出现这种现象的原因是: 实验顺序为15的实验中，比较的是高斯噪声图像组的第5幅和第6幅图片，与其他图像相比，第6幅图像的噪声加剧，其高斯噪声的方差为102。这说明本文算法在噪声条件下可以提高匹配的准确率，但噪声过于严重时，匹配准确率下降。
在图像压缩条件下，平均准确率提高2.2%，相较于其他条件提高幅度最低。这是因为在图像压缩条件下，原算法的平均准确率为95.7%，所以本文算法虽然提高平均准确率，但提高空间有限。此外，VGG图像中使用的图像压缩方法为JPEG图像压缩，该方法虽然减少了图像的细节，但仍保留了大量的图像信息，相较于其他条件，图像压缩对特征匹配的影响较小，因此在图 2中，待判断网格与其邻域内网格中的匹配点数目差异较小，加权后对结果影响不大。
4 结论 1) 本文算法在图像模糊、光照变化、和图像压缩条件下，准确率提高。
2) 在高斯噪声条件下，当高斯噪声的方差较小时，本文算法在准确性方面超过原算法。但如果噪声加剧，则算法准确性出现下降。如何改进算法使其在噪声严重条件下实现准确匹配还需进一步研究。
3) 在图像压缩条件下，本文算法对准确率的提升有限。在以后的研究中，可以采用增加ORB描述子维度等方法提高特征点描述子的区分度，从而提高匹配准确率。
参考文献
| [1] | 王晓华, 方琪, 王文杰. 基于网格运动统计的改进快速鲁棒特征图像匹配算法[J]. 模式识别与人工智能, 2019, 32(12): 1133-1140. WANG X H, FANG Q, WANG W J. Image matching algorithm combining improved SURF algorithm with grid-based motion statistics[J]. Pattern Recognition and Artificial Intelligence, 2019, 32(12): 1133-1140. (in Chinese) |
| [2] | 程向红, 李俊杰. 基于运动平滑性与RANSAC优化的图像特征匹配算法[J]. 中国惯性技术学报, 2019, 27(6): 765-770. CHENG X H, LI J J. Optimized image feature matching algorithm based on motion smoothness and RANSAC[J]. Journal of Chinese Inertial Technology, 2019, 27(6): 765-770. (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]//Computer Vision-ECCV 2006. Berlin: Springer, 2006: 404-417. |
| [5] | RUBLEE E, RABAUD V, KONOLIGE K, et al. ORB: An efficient alternative to SIFT or SURF[C]//2011 International Conference on Computer Vision. Piscataway: IEEE Press, 2011: 2564-2571. |
| [6] | YI K M, TRULLS E, LEPETIT V, et al. LIFT: Learned invariant feature transform[C]//Computer Vision-ECCV 2016. Berlin: Springer, 2016: 467-483. |
| [7] | LAGUNA A B, RIBA E, PONSA D, et al. Key. Net: Keypoint detection by handcrafted and learned CNN filters[C]//2019 IEEE/CVF International Conference on Computer Vision (ICCV). Piscataway: IEEE Press, 2019: 5835-5843. |
| [8] | SHEN X L, WANG C, LI X, et al. RF-NET: An end-to-end image matching network based on receptive field[C]//2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). Piscataway: IEEE Press, 2019: 8124-8132. |
| [9] | 侯宏录, 李媛, 李光耀. 改进SIFT匹配的动态背景下运动目标检测算法[J]. 自动化仪表, 2019, 40(8): 60-64. HOU H L, LI Y, LI G Y. Moving target detection algorithm under dynamic background with improved SIFT matching[J]. Process Automation Instrumentation, 2019, 40(8): 60-64. (in Chinese) |
| [10] | 张明浩, 杨耀权, 靳渤文. 基于图像增强技术的SURF特征匹配算法研究[J]. 自动化与仪表, 2019, 34(9): 98-102. ZHANG M H, YANG Y Q, JIN B W. Research on SURF feature matching algorithm based on image enhancement technology[J]. Automation & Instrumentation, 2019, 34(9): 98-102. (in Chinese) |
| [11] | ROSTEN E, DRUMMOND T. Machine learning for high-speed corner detection[C]//Computer Vision-ECCV 2006. Berlin: Springer, 2006: 430-443. |
| [12] | 高翔, 张涛, 刘毅. 视觉SLAM十四讲: 从理论到实践[M]. 2版. 北京: 电子工业出版社, 2019. GAO X, ZHANG T, LIU Y. 14 lectures on visual SLAM: From theory to practice[M]. 2nd ed. Beijing: Publishing House of Electronics Industry, 2019. (in Chinese) |
| [13] | CALONDER M, LEPETIT V, STRECHA C, et al. BRIEF: Binary robust independent elementary features[C]//ECCV'10: Proceedings of the 11th European Conference on Computer Vision: Part Ⅳ, 2010: 778-792. |
| [14] | 杨炳坤, 程树英, 郑茜颖. 改进的ORB特征匹配算法[J]. 传感器与微系统, 2020, 39(2): 136-139. YANG B K, CHENG S Y, ZHENG Q Y. Improved ORB feature matching algorithm[J]. Transducer and Microsystem Technologies, 2020, 39(2): 136-139. (in Chinese) |
| [15] | 杨弘凡, 李航, 陈凯阳, 等. 基于改进ORB算法的图像特征点提取与匹配方法[J]. 图学学报, 2020, 41(4): 548-555. YANG H F, LI H, CHEN K Y, et al. Image feature points extraction and matching method based on improved ORB algorithm[J]. Journal of Graphics, 2020, 41(4): 548-555. (in Chinese) |
| [16] | MUJA M, LOWE D G. Fast approximate nearest neighbors with automatic algorithm configuration[C]//Proceedings of the Fourth International Conference on Computer Vision Theory and Applications, 2009: 331-340. |
| [17] | MUJA M, LOWE D G. Scalable nearest neighbor algorithms for high dimensional data[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(11): 2227-2240. DOI:10.1109/TPAMI.2014.2321376 |
| [18] | FISCHLER M A, BOLLES R C. Random sample consensus[J]. Communications of the ACM, 1981, 24(6): 381-395. DOI:10.1145/358669.358692 |
| [19] | SATTLER T, LEIBE B, KOBBELT L. SCRAMSAC: Improving RANSAC's efficiency with a spatial consistency filter[C]//2009 IEEE 12th International Conference on Computer Vision. Piscataway: IEEE Press, 2009: 2090-2097. |
| [20] | BIAN J W, LIN W Y, MATSUSHITA Y, et al. GMS: Grid-based motion statistics for fast, ultra-robust feature correspondence[C]//2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Piscataway: IEEE Press, 2017: 2828-2837. |
| [21] | 柳长安, 艾壮, 赵丽娟. 基于网格运动统计的自适应图像特征匹配算法[J]. 华中科技大学学报(自然科学版), 2020, 48(1): 37-40. LIU C A, AI Z, ZHAO L J. Self-adaptive image feature matching algorithm based on grid motion statistics[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2020, 48(1): 37-40. (in Chinese) |
| [22] | MUR-ARTAL R, TARDóS J D. ORB-SLAM2:An open-source SLAM system for monocular, stereo, and RGB-D cameras[J]. IEEE Transactions on Robotics, 2017, 33(5): 1255-1262. DOI:10.1109/TRO.2017.2705103 |
| [23] | ALCANTARILLA P F, BARTOLI A, DAVISON A J. KAZE features[C]//Computer Vision-ECCV 2012. Berlin: Springer, 2012: 214-227. |
