Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon openaccess Fast feature matching based on r-nearest k-means searching

This is an open access article published by the IET, Chinese Association for Artificial Intelligence and Chongqing University of Technology under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0/)
Received 26/09/2018, Accepted 21/10/2018, Revised 17/10/2018, Published 22/10/2018

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.

Inspec keywords: pattern clustering; feature extraction; trees (mathematics); search problems; image matching

Other keywords: computer vision; wrong matches; priority search km-tree; nearest searching strategy; searching speed; algorithm searches; CFI algorithm; searching points; pattern recognition; complex tree; matching rule; fast feature matching algorithm; vector-based feature; NN; nearest neighbourhood clusters; random kd-tree; linear search

Subjects: Image recognition; Computer vision and image processing techniques; Combinatorial mathematics; Combinatorial mathematics

References

    1. 1)
      • [14]. Muja, M.: ‘Fast approximate nearest neighbors with automatic algorithm configuration’. Int. Conf. Computer Vision Theory and Application, Kyoto, Japan, 2009, vol. 1, pp. 331–340.
    2. 2)
      • [11]. Jia, Y., Wang, J., Zeng, G., et al: ‘Optimizing kd-trees for scalable visual descriptor indexing’, Comput. Vis. Pattern Recognit, 2010, 119, (5), pp. 3392–3399.
    3. 3)
      • [12]. Wang, C., Lu, Z., Liao, Q., et al: ‘Locality sensitive hashing based deep matching for optical flow estimation’. 2017 IEEE Int. Conf. Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA, USA, 2017, pp. 1472–1476.
    4. 4)
      • [18]. Pronobis, A., Caputo, B.: ‘The kth-INDECS database’ (KTH Royal Institute of Technology, Stockholm, Sweden, 2005).
    5. 5)
      • [20]. Ullah, M.M., Pronobis, A., Caputo, B., et al: ‘The cold database’ (Idiap, Martigny, Switzerland, 2007).
    6. 6)
      • [7]. Cai, Z., Xiao, D.G.: ‘Feature matching algorithm based on KAZE and fast approximate nearest neighbor search’. Int. Conf. Computer Science and Service System, Bangkok, Thailand, 2014, pp. 270–273.
    7. 7)
    8. 8)
      • [8]. Sinkar, S.V., Deshpande, A.M.: ‘Object recognition with plain background by using ANN and SIFT based features’. Int. Conf. Information Processing IEEE, Pune, India, 2016, pp. 575–580.
    9. 9)
      • [9]. Rublee, E., Rabaud, V., Konolige, K., et al: ‘ORB: an efficient alternative to SIFT or SURF’. 2011 Int. Conf. Computer Vision, Barcelona, 2011, pp. 2564–2571.
    10. 10)
      • [4]. Liu, T., Moore, A.W., Gray, A., et al: ‘An investigation of practical approximate nearest neighbor algorithms’. Int. Conf. Neural Information Processing Systems, Calcutta, India, 2004, vol. 17, pp. 825–832.
    11. 11)
      • [15]. Muja, M.: ‘FLANN -fast library for approximate nearest neighbors user manual’, 2013.
    12. 12)
    13. 13)
      • [10]. Calonder, M., Lepetit, V., Strecha, C., et al: ‘BRIEF: binary robust independent elementary features’. European Conf. Computer Vision, Hersonissos, Greece, 2010, vol. 6314, pp. 778–792.
    14. 14)
      • [6]. Fu, Q., Wang, H.: ‘A fast image stitching algorithm based on SURF’. IEEE/CIC Int. Conf. Communications in China, Qingdao, China, 2017, pp. 1–4.
    15. 15)
      • [17]. Rosten, E., Drummond, T.: ‘Machine learning for high-speed corner detection’. European Conf. Computer Vision 2006, Graz, Austria, 2006, pp. 430–443.
    16. 16)
      • [5]. Guo, F., Yang, J., Chen, Y., et al: ‘Research on image detection and matching based on SIFT features’. 2018 Third Int. Conf. Control and Robotics Engineering (ICCRE), Nagoya, Japan, 2018, pp. 130–134.
    17. 17)
      • [1]. Li, Y., Snavely, N., Huttenlocher, D.P.: ‘Location recognition using prioritized feature matching’. European Conf. Computer Vision, Hersonissos, Greece, 2010, vol. 6312, pp. 791–804.
    18. 18)
    19. 19)
    20. 20)
      • [13]. Hajebi, K., Abbasi-Yadkori, Y., Shahbazi, H., et al: ‘Fast approximate nearest-neighbor search with k-nearest neighbor graph’. IJCAI 2011 Proc. Int. Joint Conf. Artificial Intelligence, Barcelona, Catalonia, Spain, 2009, pp. 1312–1317.
http://iet.metastore.ingenta.com/content/journals/10.1049/trit.2018.1041
Loading

Related content

content/journals/10.1049/trit.2018.1041
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address