Fast feature matching based on r-nearest k-means searching

• 作者: Ke Wang Ningyu Zhu Ruifeng Li Tianxiang Zhou Xuexiong Long Yao Cheng
• 来源期刊: 智能技术学报
• 学科: 社会科学
• 关键词: FEATURE MATCHING
• 年，卷（期）: znjsxb_2018,（4）
• 页码范围: 198-207
• 页数: 10页
• 分类号: G

摘要

Feature matching has been frequently applied in computer vision and pattern recognition.In this paper,the authors propose a fast feature matching algorithm for vector-based feature.Their algorithm searches r-nearest neighborhood clusters for the query point after a k-means clustering,which shows higher efficiency in three aspects.First,it does not reformat the data into a complex tree,so it shortens the construction time twice.Second,their algorithm adopts the r-nearest searching strategy to increase the probability to contain the exact nearest neighbor(NN)and take this NN as the global one,which can accelerate the searching speed by 170 times.Third,they set up a matching rule with a variant distance threshold to eliminate wrong matches.Their algorithm has been tested on large SIFT databases with different scales and compared with two widely applied algorithms,priority search km-tree and random kd-tree.The results show that their algorithm outperforms both algorithms in terms of speed up over linear search,and consumes less time than km-tree.Finally,they carry out the CFI test based on ISKLRS database using their algorithm.The test results show that their algorithm can greatly improve the recognition speed without affecting the recognition rate.