Fast feature matching based on r-nearest k-means searching
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...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2018-12-01
|
| Series: | CAAI Transactions on Intelligence Technology |
| Subjects: | |
| Online Access: | https://digital-library.theiet.org/content/journals/10.1049/trit.2018.1041 |
| _version_ | 1819176355147808768 |
|---|---|
| author | Ke Wang Ningyu Zhu Yao Cheng Ruifeng Li Tianxiang Zhou Xuexiong Long |
| author_facet | Ke Wang Ningyu Zhu Yao Cheng Ruifeng Li Tianxiang Zhou Xuexiong Long |
| author_sort | Ke Wang |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-22T21:09:26Z |
| format | Article |
| id | doaj.art-3591f2287634450fadd477ac7d4432ba |
| institution | Directory Open Access Journal |
| issn | 2468-2322 |
| language | English |
| last_indexed | 2024-12-22T21:09:26Z |
| publishDate | 2018-12-01 |
| publisher | Wiley |
| record_format | Article |
| series | CAAI Transactions on Intelligence Technology |
| spelling | doaj.art-3591f2287634450fadd477ac7d4432ba2022-12-21T18:12:35ZengWileyCAAI Transactions on Intelligence Technology2468-23222018-12-0110.1049/trit.2018.1041TRIT.2018.1041Fast feature matching based on r-nearest k-means searchingKe Wang0Ningyu Zhu1Yao Cheng2Ruifeng Li3Tianxiang Zhou4Xuexiong Long5Harbin Institute of TechnologyHarbin Institute of TechnologyChina Mobile (Hangzhou) Information Technology Co., LtdHarbin Institute of TechnologyHarbin Institute of TechnologyHarbin Institute of TechnologyFeature 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.https://digital-library.theiet.org/content/journals/10.1049/trit.2018.1041image matchingsearch problemspattern clusteringfeature extractiontrees (mathematics)computer visionpattern recognitionfast feature matching algorithmvector-based featurealgorithm searchesnearest neighbourhood clusterscomplex treenearest searching strategyNNsearching speedmatching rulewrong matchessearching pointspriority search km-treerandom kd-treelinear searchCFI algorithm |
| spellingShingle | Ke Wang Ningyu Zhu Yao Cheng Ruifeng Li Tianxiang Zhou Xuexiong Long Fast feature matching based on r-nearest k-means searching CAAI Transactions on Intelligence Technology 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 |
| title | Fast feature matching based on r-nearest k-means searching |
| title_full | Fast feature matching based on r-nearest k-means searching |
| title_fullStr | Fast feature matching based on r-nearest k-means searching |
| title_full_unstemmed | Fast feature matching based on r-nearest k-means searching |
| title_short | Fast feature matching based on r-nearest k-means searching |
| title_sort | fast feature matching based on r nearest k means searching |
| topic | 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 |
| url | https://digital-library.theiet.org/content/journals/10.1049/trit.2018.1041 |
| work_keys_str_mv | AT kewang fastfeaturematchingbasedonrnearestkmeanssearching AT ningyuzhu fastfeaturematchingbasedonrnearestkmeanssearching AT yaocheng fastfeaturematchingbasedonrnearestkmeanssearching AT ruifengli fastfeaturematchingbasedonrnearestkmeanssearching AT tianxiangzhou fastfeaturematchingbasedonrnearestkmeanssearching AT xuexionglong fastfeaturematchingbasedonrnearestkmeanssearching |