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

CAAI Transactions on Intelligence Technology

article

Ke Wang¹  Ningyu Zhu¹  Yao Cheng²  Ruifeng Li¹  Tianxiang Zhou¹  Xuexiong Long¹ 

[1] State Key Laboratory of Robotics and System, School of Mechatronics, Harbin Institute of Technology;Ltd

关键词: 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;    B0250 Combinatorial mathematics;    B6135E Image recognition;    C1160 Combinatorial mathematics;    C5260B Computer vision and image processing techniques;   

DOI  :  10.1049/trit.2018.1041

学科分类：数学（综合）

来源: Wiley

【 摘 要 】

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.

【 授权许可】

CC BY|CC BY-ND|CC BY-NC|CC BY-NC-ND