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

Abstract

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.

Keywords

• image matching
• search problems
• pattern clustering
• feature extraction
• trees (mathematics)
• computer vision
• pattern recognition
• fast feature matching algorithm
• vector-based feature
• algorithm searches
• nearest neighbourhood clusters
• complex tree
• nearest searching strategy
• NN
• searching speed
• matching rule
• wrong matches
• searching points
• priority search km-tree
• random kd-tree
• linear search
• CFI algorithm