Object detection in images with a structural descriptor based on graphs
Zakharov A.A., Barinov A.E., Zhiznyakov A.L., Titov V.S.

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

We discuss the development of a structural descriptor for object detection in images. The descriptor is based on a graph, whose vertices are the centers of mass of segment features.  The embedding of the graph in a vector space is implemented using a Young-Householder decomposition and based on differential geometry. Compound curves are used to describe the relationship between the points. The image graph is described by a matrix of curvature parameters. The distance matrix for the graphs of the candidate object and the reference object is calculated using the Hausdorff metric. A multidimensional scaling method is used to represent the results. Images of test objects and images of human faces are used to study the developed approach. A comparison of the developed descriptor with the Viola-Jones method is performed when detecting a human head in the image. The advantage of the developed approach is the image rotational invariance in the plane while searching for objects. The descriptor can detect objects rotated in space by angles of up to 50 degrees. Using the mass centers of segments of features as the graph vertices makes the approach more robust to changes in image acquisition angles in comparison with the approach that uses image features as the graph vertices.

image analysis, objects detection, structural descriptor, graph embedding, computer vision.

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.


  1. Krig S. Computer vision metrics. Survey, taxonomy, and analysis. Apress, Berkeley, CA; 2014. ISBN: 978-1-4302-5929-9
  2. Jain M, Singh D. A survey on CBIR on the basis of different feature descriptor. British Journal of Mathematics & Computer Science 2016; 14(6): 1-13. DOI: 10.9734/BJMCS/2016/24000.
  3. Ojala T, Pietikainen M, Hardwood D. A comparative study of texture measures with classification based on feature distributions. Pattern Recognition 1996; 29(1): 51-59. DOI: 10.1016/0031-3203(95)00067-4.
  4. Calonder M, Lepetit V, Strecha C, Fua P. BRIEF-Binary robust independent elementary features. ECCV 2010; IV: 778-792.  DOI: 10.1007/978-3-642-15561-1_56.
  5. Rublee E, Rabaud V, Konolige K, Bradski G. ORB: an efficient alternative to SIFT or SURF. ICCV 2011: 2564-2571. DOI: 10.1109/ICCV.2011.6126544.
  6. Leutenegger S, Chli M, Siegwart R. BRISK: Binary robust invariant scalable keypoints. ICCV 2011: 2548-2555. DOI: 10.1109/ICCV.2011.6126542.
  7. Lowe DG. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision 2004; 60(2): 91-110. DOI: 10.1023/B:VISI.0000029664.99615.94.
  8. Bay H, Ess A, Tuytelaars T, Van Gool L. SURF: Speeded up robust features. Computer Vision and Image Understanding 2008; 110(3): 346-359. DOI: 10.1016/j.cviu.2007.09.014.
  9. 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. DOI: 10.1109/TPAMI.2009.77.
  10. Dalal N, Triggs B. Histograms of oriented gradients for human detection. CVPR 2005; 1: 886-893. DOI: 10.1109/CVPR.2005.177.
  11. Scharstein D, Szeliski R. Taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision 2002; 47(1-3): 7-42. DOI: 10.1023/A:1014573219977.
  12. Jun B, Kim D. Robust face detection using local gradient patterns and evidence accumulation. Pattern Recognition 2012; 45(9): 3304-3316. DOI: 10.1016/j.patcog.2012.02.031.
  13. Freeman H. On the encoding of arbitrary geometric configurations. IRE Transactions on Electronic Computers 1961; EC-10(2): 260-268. DOI: 10.1109/TEC.1961.5219197.
  14. Gonzalez R, Woods R. Digital image processing. 3rd ed. Upper Saddle River, NJ: Prentice-Hall; 2007.
  15. Bracewell R. The Fourier transform and its applications. 3rd ed. New York: McGraw-Hill Science; 1999. ISBN: 978-0-07-303938-1.
  16. Fei-Fei L, Fergus R, Torralba A. Recognizing and learning object categories. Conference on Computer Vision and Pattern Recognition 2007.
  17. Matas J, Chum O, Urban M, Pajdla T. Robust widebaseline stereo from maximally stable extremal regions. British Machine Vision Conference 2002: 384-393.
  18. Belongie S, Malik J, Puzicha J. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence 2002; 24(4): 509-522. DOI: 10.1109/34.993558.
  19. Lomov NA, Mestetskiy LM. Area of the disk cover as an image shape descriptor [In Russian]. Computer Optics 2016; 40(4): 516-525. DOI: 10.18287/2412-6179-2016-40-4-516-525.
  20. Sidyakin SV, Vizilter YV. Morphological shape descriptors of binary images based on elliptical structuring elements. Computer Optics 2014; 38(3): 511-520. DOI: 10.18287/0134-2452-2014-38-3-511-520.
  21. Bauckhage C, Tsotsos JK. Bounding box splitting for robust shape classification. IEEE International Conference on Image Processing 2005: 478-481. DOI: 10.1109/ICIP.2005.1530096.
  22. Sonka M, Hlavac V, Boyle R. Image processing, analysis and machine vision. London: Chapman and Hall; 1993. ISBN: 978-0-412-45570-4.
  23. Abbasi S, Mokhtarian F, Kittler J.  Enhancing CSS-based shape retrieval for objects with shallow concavities. Image and Vision Computing 2000; 18(3): 199-211. DOI: 10.1016/S0262-8856(99)00019-0.
  24. Siddiqi K, Kimia B. A shock grammar for recognition.   CVPR '96 1996: 507-513. DOI: 10.1109/CVPR.1996.517119.
  25. Zakharov AA, Tuzhilkin AYu, Zhiznyakov AL. Finding correspondences between images using descriptors and graphs. Procedia Engineering 2015; 129: 391-396. DOI: 10.1016/j.proeng.2015.12.131.
  26. Barinov AE, Zakharov AA. Clustering using a random walk on graph for head pose estimation // 2015 International Conference on Mechanical Engineering, Automation and Control Systems (MEACS) 2015. DOI: 10.1109/MEACS.2015.7414876.
  27. Barinov AE, Zakharov AA, Zhyznyakov AL. The algorithm of spectral clustering with restrictions for the selection of a person's face in images [In Russian]. Dynamics of systems, mechanisms and machines 2016; 2(1): 222-228.
  28. Zakharov AA, Barinov AE, Zhyznyakov AL. Recognition of human pose from images based on graph spectra. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 2014; XL-5/W6: 9-12. DOI: 10.5194/isprsarchives-XL-5-W6-9-2015.
  29. Chung FRK. Spectral graph theory. Provides, Rhode Island: AMS; 1997. ISBN: 0-8218-0315-8.
  30. ElGhawalby H, Hancock ER. Measuring graph similarity using spectral geometry. In book: Campilho A, Kamel M, eds. Image Analysis and Recognition: ICIAR '08 2008; 5112: 517-526. DOI: 10.1007/978-3-540-69812-8_51.
  31. Borg I, Groenen P. Modern multidimensional scalling: theory and applications. New York, NY: Springer-Verlag; 2005: 207-212. ISBN: 0-387-25150-2.
  32. Viola P, Jones M. Rapid Object detection using a boosted cascade of simple features. CVPR 2001: 511-518. DOI: 10.1109/CVPR.2001.990517.

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: ko@smr.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20