Feature Matching Algorithm Based on Optimal Geometric Constraints and RANSAC

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

Abstract

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

CLC Number:

TP391.41

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.

Figures/Tables 14

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Table 1

Fig. 5

Fig. 6

Table 2

Experimental results of geometric constraints

长度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

Table 2

Table 3

Results of different error ranges

长度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

Table 3

Table 4

Table 5

Fig. 7

Table 6

Fig. 8

References 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

[1]	Jinghui Yang, Dekang Liu, Wanhe Du, Lining Xing. Research on Binocular Ranging System Based on Image Features [J]. Journal of System Simulation, 2022, 34(3): 624-632.
[2]	Tang Wenjie, Li Ruotong, Deng Xuesong, Si Weixin, Wang Qiong. ICP Optimized B-Spline Non-Rigid Registration for 4D-CT Images [J]. Journal of System Simulation, 2020, 32(7): 1301-1311.
[3]	Qian Wenhua, Xu Dan, Xu Jin, He Lei, Zhang Bo. Simulation of Dongba Art Style Painting [J]. Journal of System Simulation, 2020, 32(7): 1349-1359.
[4]	Liu Jiazhe, Chen Chunyi, Hu Xiaojuan, Liang Weidong, Xing Qiwei, Yang Huamin. Mobile-phone-oriented Stereoscopic Display and Interaction Framework for Cloud-based Virtual Reality 3D Scenes [J]. Journal of System Simulation, 2020, 32(7): 1360-1374.
[5]	Peng Liu, Si Weixin, Zheng Rui, Liao Xiangyun, Xu Dongliang, Wang Ping'an. High-fidelity Simulation of Video-Assisted Thoracoscopic Surgery Lobectomy [J]. Journal of System Simulation, 2020, 32(5): 826-836.
[6]	Li Qi, Cui Jianjiang, Xue Dingyu, Geng Hongyu. A Dorsal Hand Vein Extraction Algorithm for Region of Interest [J]. Journal of System Simulation, 2019, 31(10): 2174-2180.
[7]	Zhang Qing, Li Yijie. Hardware-in-the-loop Simulation Method for Laser Active Imaging Guidance [J]. Journal of System Simulation, 2019, 31(2): 299-305.
[8]	Zhang Qing, Zou Xiangjun, Lin Guichao, Sun Yanhui. Image Feature Extraction and Online Grading Method for Weight and Shape of Strawberry [J]. Journal of System Simulation, 2019, 31(1): 7-9.
[9]	Yuan MingZe, Xia Shihong. Facial Feature Points Tracking System and Simulation Analysis [J]. Journal of System Simulation, 2018, 30(12): 4618-4624.
[10]	Du Jinlian, Xu Shuo, Zhao Fengchao. Research of 3D Urban Modeling Based on 2D Digital Maps [J]. Journal of System Simulation, 2018, 30(10): 3710-3716.
[11]	Li Ju, Cao Mingwei, Yu Ye, XiaYu, Zhou Lifan. An Anti-occlusion Adaptive Particle Filtering Algorithm [J]. Journal of System Simulation, 2018, 30(9): 3552-3557.
[12]	Liu Fang, Lu Lixia, Wang Hongjuan, Wang Xin. Image Classification Based on Sparse Autoencoder and Support Vector Machine [J]. Journal of System Simulation, 2018, 30(8): 3007-3014.
[13]	Zhu Xiaoqiang, Pan Hongyi, Xu Hao, Song Lei, Zhu Mengyao, Wang Xiangyang. Interactive Modelling on Smooth Weighted Distance Surface in HMD VR Environment [J]. Journal of System Simulation, 2018, 30(7): 2459-2464.
[14]	Sun Shuifa, Li Zhun, Xia Kun, Shi Yunfei, Yang Jiquan, Dong Fangmin. Variable Scale Point Cloud Registration Algorithm [J]. Journal of System Simulation, 2018, 30(7): 2465-2474.
[15]	Yu Yihao, Tan Chong, Zhou Zhong, Wu Wei. Real-time Video WebGIS with Virtual-reality Fusion [J]. Journal of System Simulation, 2018, 30(7): 2568-2575.