基于最佳几何约束和RANSAC的特征匹配算法

doi:10.16182/j.issn1004731x.joss.21-0857

系统仿真学报 ›› 2022, Vol. 34 ›› Issue (4): 727-734.doi: 10.16182/j.issn1004731x.joss.21-0857

基于最佳几何约束和RANSAC的特征匹配算法

宁小娟^1,²(), 李洁茹¹(), 高凡¹, 王映辉³

^1.西安理工大学计算机科学与工程学院, 陕西西安 710048
^2.陕西省网络计算与安全技术重点实验室, 陕西西安 710048
^3.江南大学人工智能与计算机学院, 江苏无锡 214122

收稿日期:2021-08-24 修回日期:2021-12-17 出版日期:2022-04-30 发布日期:2022-04-19
通讯作者: 李洁茹 E-mail:ningxiaojuan@xaut.edu.cn;1353654876@qq.com
作者简介:宁小娟(1982-)，女，博士，副教授，研究方向为模式识别与图像处理。E-mail：ningxiaojuan@xaut.edu.cn
基金资助:
国家自然科学基金(61871320);国家重点研发计划(2018YFB1004905);教育厅重点实验室项目(17JS099)

Feature Matching Algorithm Based on Optimal Geometric Constraints and RANSAC

Xiaojuan Ning^1,²(), Jieru Li¹(), Fan Gao¹, Yinghui Wang³

^1.Institute of Computer Science and Engineering, Xi'an University of Technology, Xi'an 710048, China
^2.Shaanxi Key Laboratory for Network Computing and Security Technology, Xi'an 710048, China
^3.Institute of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi 214122, China

Received:2021-08-24 Revised:2021-12-17 Online:2022-04-30 Published:2022-04-19
Contact: Jieru Li E-mail:ningxiaojuan@xaut.edu.cn;1353654876@qq.com

摘要/Abstract

摘要：

为解决特征点匹配的质量与计算效率不能兼得的问题，研究了一种基于最佳几何约束和RANSAC(random sample consensus)的特征点匹配方法。采用KNN（k-nearest neighbor）算法对提取到的特征点完成初始匹配，根据匹配点对连接线长度相等、斜率相同的特点，基于统计排序策略构建最佳几何约束，剔除明显错误匹配。利用RANSAC算法进行二次过滤，确保特征匹配点对的正确率，同时给出实验结果加以验证。结果表明：在正常光照下，与Lowe's算法和GMS算法相比，该算法匹配到的点对数有了明显增加，同时很大程度上保证了特征点的质量。

关键词: 统计排序, 最佳几何约束, RANSAC(random sample consensus)算法, 特征点匹配

Abstract:

In order to solve the problem that it's hard to reconcile the quality and computational efficiency of feature point matching. The initial matching for the extracted feature points is implemented through k-nearest neighbor (KNN) algorithm. According to the characteristics of equal length and same slope of the connecting line between matching points, the optimal geometric constraint is constructed based on the statistical sorting strategy to eliminate the obvious matching errors. Then random sample consensus (RANSAC) algorithm is utilized for further filtering to ensure the accuracy of the feature matching point pairs. Experimental results show that the method can obtain more matched point pairs under normal light, compared with Lowe's algorithm and GMS algorithm, and can ensure the quality of feature points.

Key words: statistical ranking, optimal geometric constraint, random sample consensus algorithm, feature point match

中图分类号:

TP391.41

宁小娟, 李洁茹, 高凡, 王映辉. 基于最佳几何约束和RANSAC的特征匹配算法[J]. 系统仿真学报, 2022, 34(4): 727-734.

Xiaojuan Ning, Jieru Li, Fan Gao, Yinghui Wang. Feature Matching Algorithm Based on Optimal Geometric Constraints and RANSAC[J]. Journal of System Simulation, 2022, 34(4): 727-734.

图/表 14

图1

图2

图3

图4

表1

图5

图6

表2

几何约束实验结果

长度m和斜率n	初始匹配点数(个)	几何约束剔除后的匹配点对数(个)	运行时间/s
$m = 13 & & n = 0.03$	1 258	21	0.814 524
$m = 13 n = 0.03$	1 258	884	0.790 735
$m = 14 & & n = 0.03$	1 258	21	0.790 647
$m = 14 n = 0.03$	1 258	889	0.791 691
$m = 15 & & n = 0.03$	1 258	21	0.794 338
$m = 15 n = 0.03$	1 258	893	0.789 879

表2

表3

不同误差范围的结果

长度m和斜率n	初始匹配点数(个)	几何约束剔除后的匹配点对数(个)	运行时间/s
$m = 13, n = 0.02$	1 258	881	0.828 312
$m = 13, n = 0.03$	1 258	884	0.790 466
$m = 14, n = 0.02$	1 258	886	0.827 559
$m = 14, n = 0.03$	1 258	889	0.820 967
$m = 15, n = 0.02$	1 258	890	0.797 841
$m = 15, n = 0.03$	1 258	893	0.788 993
$m = 16, n = 0.02$	1 258	892	0.790 702
$m = 16, n = 0.03$	1 258	895	0.797 179

表3

表4

表5

图7

表6

图8

参考文献 18

1	Lowe D G. Object Recognition from Local Scale-Invariant Features[C]// 7th International Conference on Computer Vision. Greece: Corfu, 1999: 1150-1157.
2	Scitovski R, Majstorović S, Sabo K. A Combination of RANSAC and DBSCAN Methods for Solving the Multiple Geometrical Object Detection Problem[J]. Journal of Global Optimization (S0925-5001), 2021, 79(3): 669-686.
3	Ro Sung-Hyok, Kim Se-Hun. An Image Stitching Algorithm for the Mineralogical Analysis[J]. Minerals Engineering (S0892-6875), 2021, 169(6): 106968.
4	Steven M S, Charles R D. Photorealistic Scene Reconstruction by Voxel Coloring[J]. International Journal of Computer Vision (S0920-5691), 1999, 35(2): 151-173.
5	Zhu Qing, Wang Zhendong, Hu Han, et al. Leveraging Photogrammetric Mesh Models for Aerial-Ground Feature Point Matching Toward Integrated 3D Reconstruction[J]. ISPRS Journal of Photogrammetry and Remote Sensing (S0924-2716), 2020, 166(8): 26-40.
6	Jiang Xingyu, Ma Jiayi, Xiao Guobao, et al. A review of Multimodal Image Matching: Methods and Applications[J]. Information Fusion (S1566-2535), 2021, 73(9): 22-71.
7	Harris C G, Stephens M. A Combined Corner and Edge Detector[C]// 4th Alvey Vision Conference. Manchester: AVC, 1988: 147-151.
8	Lowe David G. Distinctive Image Features from Scale-Invariant Keypoints[J]. International Journal of Computer Vision (S0920-5691), 2004, 60(2): 91-110.
9	Bay H, Tuytelaars T, van Gool L. SURF: Speeded Uprobust Features[C]// European Conference on Computer Vision. Graz: Springer, 2006: 404-417.
10	Calonder M, Lepetit V, Strecha C, et al. Binary Robust Independent Elementary Features[C]// European Conference on Computer Vision. Crete: Springer, 2010: 778-792.
11	Rublee E, Rabaud V, Konolige K, et al. ORB: An Efficient Alternative to SIFT or SURF[C]// IEEE International Conference on Computer Vision. New York: IEEE, 2011: 2564-2571.
12	Lin W Y D, Cheng M M, Lu J, et al. Bilateral Functions for Global Motion Modeling[C]// 13th European Conference on Computer Vision. Zurich, Switzerland: Springer, 2014: 341-356.
13	王心醉, 董宁宁, 李欢利. 基于SIFT算法的图像特征点提取和匹配研究[J]. 南京医科大学学报 (自然科学版), 2013, 33(2): 286-290.
	Wang Xinzui, Dong Ningning, Li Huanli. Research of Features Extraction and Matching in the Image Based on the SIFT Algorithm[J]. Journal of Nanjing Medical University (Natural Science Edition), 2013, 33(2): 286-290.
14	Fischler M A, Bolles R C. Random Sample Consensus: a Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J]. Communications of the ACM (S0001-0782), 1981, 24(6): 381-395.
15	Bian J W, Lin W Y, Matsushita Y, et al. GMS: Grid-Based Motion Statistics for Fast, Ultra-Robust Feature Correspondence[C]// IEEE Conference on Computer Vision and Pattern Recognition. Los Alamitos: IEEE, 2017: 4181-4190.
16	Mulyawan Bagus, Jovianto Nicholas, Hendryli Janson, et al. Land Mapping with Least Median of Squares Regression Using Landsat Imagery: a Case Study Jakarta and Sorrounding Area[J]. IOP Conference Series: Materials Science and Engineering (S1757-8981), 2020, 852(1): 012024.
17	Muja M, Lowe D G. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration[C]// IEEE Conference on Computer Vision Theory and Applications. Lisbon, Portugal: IEEE Computer Society, 2009: 331-340.
18	Huang Jiawei, Liu Shiguang. Robust Simultaneous Localization and Mapping in Low-Light Environment[J]. Computer Animation and Virtual Worlds(S1546-4261), 2019, 30(3/4): e1895.

算法	特征点个数(个)	运行时间/s
SIFT	478	0.167
SURF	1 344	0.200
ORB	500	0.018

算法	匹配到的点对数(个)	运行时间/s
Lowe's	795	0.825 712
GMS	757	1.393 039
本文	850	0.881 369

算法	匹配到的点对数(个)	运行时间/s
Lowe's	608	0.694 027
GMS	592	1.244 794
本文	713	0.693 211

光线强度	匹配的点对数(个)	运行时间/s
光线1	510	0.589 114
光线2	713	0.693 211
光线3	786	0.948 643
光线4	561	0.731 228

基于最佳几何约束和RANSAC的特征匹配算法

Feature Matching Algorithm Based on Optimal Geometric Constraints and RANSAC

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 18

相关文章 1

编辑推荐

Metrics

本文评价