(43-5) 14 * << * >> * Russian * English * Content * All Issues

A method for feature matching in images using descriptor structures

A.A. Zakharov1, A.L. Zhiznyakov1, V.S. Titov2

Murom Institute (branch), Vladimir State University named after Alexander and Nikolay Stoletovs, Murom, Russia,  
Southwest State University, Kursk, Russia

 PDF, 1282 kB

DOI: 10.18287/2412-6179-2019-43-5-810-817

Pages: 810-817.

Full text of article: Russian language.

A method of feature matching in images using descriptor structures is considered in the work. The descriptors in the developed method can be any known solutions in the field of computer vision. However, inaccuracies can occur when matching image pairs. It is proposed that descriptor structures should be compared to eliminate the “outliers”. Descriptor structures are described using graphs. An Umeyama method is used to find matching features using descriptor structures. The method is based on the decomposition of matrices into eigenvalues and eigenvectors for weighted graph matching problems. Thus, matches are based on the descriptor at the initial stage. Two graphs are then constructed for each image based on the resulting sets of mapped features. The weights of the graph are distances between all image features, calculated using the Gauss function. Weight matrices are built for each graph. Matrix decomposition is carried out into eigenvalues and eigenvectors. The resulting matrix is calculated based on the Umeyama method and correct matches are found. Thus, false matches are excluded from the set of matches obtained using descriptors by comparing structures. The method is invariant to zoom and in-plane image rotation. The method leads to correct results only if the number of correct matches is greater than the number of false matches. The complexity of the developed algorithm is proportional to the number of matches found.

image analysis, finding matches, image descriptors, graph matching, computer vision.

Zakharov AA, Zhiznyakov AL, Titov VS. A method for feature matching in images using descriptor structures. Computer Optics 2019; 43(5): 810-817. DOI: 10.18287/2412-6179-2019-43-5-810-817.

This work was financially supported by the RF Ministry of Education and Science under government project No. 2.1950.2017/ПЧ.


  1. Krig S. Computer vision metrics. Survey, taxonomy, and analysis. Berkeley, CA: Apress; 2014.
  2. Ojala T, Pietikainen M, Hardwood D. A comparative study of texture measures with classification based on feature distributions. Patt Recogn 1996; 29(1): 51-59.
  3. Calonder M, Lepetit V, Strecha C, Fua P. BRIEF Binary robust independent elementary features. In Book: Daniilidis K, Maragos P, Paragios N, eds. Computer Vision – ECCV 2010. Berlin, Heidelberg: Springer-Verlag; 2010. Pt IV: 778-792.
  4. Rublee E, Rabaud V, Konolige K, Bradski G. ORB: An efficient alternative to SIFT or SURF. ICCV 2011: 2564-2571.
  5. Leutenegger S, Chli M, Siegwart R. BRISK: Binary robust invariant scalable keypoints. ICCV 2011: 2548-2555.
  6. Lowe, DG. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision 2004; 60(2): 91-110.
  7. Bay H, Ess A, Tuytelaars T, Van Gool L. SURF: Speeded up robust features. Computer Vision and Image Understanding 2008; 110(3): P. 346-359.
  8. Tola E, Lepetit V, Fua P. DAISY: An efficient dense descriptor applied to wide-baseline stereo. IEEE Transactions on Pattern Analysis and Machine Intelligence 2010; 32(5): 815-830.
  9. Dalal N, Triggs B. Histograms of oriented gradients for human detection. Computer Vision and Pattern Recognition 2005; 1: 886-893.
  10. Scharstein D, Szeliski R. Taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision 2002; 47: 7-42.
  11. Jun B, Kim D. Robust face detection using local gradient patterns and evidence accumulation. Pattern Recognition 2012; 45(9): 3304-3316.
  12. Freeman H. On the encoding of arbitrary geometric configurations. IRE Transactions on Electronic Computers 1961; EC-10(2): 260-268.
  13. Gonzalez R, Woods R. Digital image processing. Upper Saddle River, NJ: Prentice-Hall; 2007.
  14. Agrawal M, Konolige K, Blas MR. CenSurE: Center surround extremas for realtime feature detection and matching. European Conference on Computer Vision 2008; 4: 102-115.
  15. Mitsuru A, Yoshida Y. CARD: Compact and real-time descriptors. International Conference on Computer Vision; 2011.
  16. Szeliski R. Computer vision: Algorithms and applications. London: Springer-Verlag; 2010.
  17. Fischer P, Dosovitskiy A, Brox T. Descriptor matching with convolutional neural networks: A comparison to SIFT. arXiv:1405.5769v1 2014. Source: <https://arxiv.org/abs/1405.5769>.
  18. Ufer N, Ommer B. Deep semantic feature matching. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2017: 6914-6923.
  19. Wu S, Lew MS. Image correspondences matching using multiple features fusion. Computer Vision – ECCV 2016 Workshops 2016.
  20. Zakharov AA, Barinov AE, Zhiznyakov AL, Titov VS. Object detection in images with a structural descriptor based on graphs. Computer Optics 2018; 42(2): 283-290. DOI: 10.18287/2412-6179-2018-42-2-283-290.
  21. Kamaev AN, Karmanov DA. Visual navigation of an autonomous underwater vehicle based on the global search of image correspondences. Computer Optics 2018; 42(3): 457-467. DOI: 10.18287/2412-6179-2018-42-3-457-467.
  22. Scott G, Longuet-Higgins H. An algorithm for associating the features of two images. Proceedings of Royal Society 1991; 244: 21-26.
  23. Shapiro LS, Brady JM. Feature-based correspondence – an eigenvector approach. Image Vision Computing 1992; 10(5): 283-288.
  24. Umeyama S. An eigen decomposition approach to weighted graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence 1988; 10(5): 695-703.
  25. Carcassoni M, Hancock E. Spectral correspondence for point pattern matching. Pattern Recognition 2003; 36(1): 193-204.
  26. Leordeanu M, Hebert M. A spectral technique for correspondence problems using pairwise constraints. Tenth IEEE International Conference on Computer Vision 2005; 1.
  27. Cour T, Srinivasan P, Shi J. Balanced graph matching. Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems 2006: 313-320.
  28. Pilu M. A direct method for stereo correspondence based on singular value decomposition. IEEE Proceedings of CVPR 1997: 261-266.
  29. Delponte E, Isgro F, Odone F, Verri A. SVD-matching using SIFT features. Graphical Models 2006; 68(5-6): 415-431.
  30. Chung FRK. Spectral graph theory. American Mathematical Society; 1997.
  31. Zakharov A, Tuzhilkin A., Zhiznyakov A. Finding correspondences in images using descriptors and graphs. Procedia Engineering 2015; 129: 391-396.
  32. Papadimitriou CH, Steiglitz K. Combinatorial optimization: Algorithms and complexity. Englewood Cliffs, NJ: Prentice-Hall; 1982.


© 2009, IPSI RAS
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20