Classification of two-dimensional figures using skeleton-geodesic histograms of thicknesses and distances
N.A. Lomov, S.V. Sidyakin, Yu. V. Visilter

 

Lomonosov Moscow State University, Computational Mathematics and Cybernetics Faculty,
FGUP “State Research Institute of Aviation Systems”

Full text of article: Russian language.

 PDF

Abstract:
The paper considers a problem of shape representation and classification. We propose a skeleton-geodesic histogram of thicknesses and distances for this purpose. It is based on the statistics of pair distances between shape elements. It is computed using skeleton-geodesic distances and thickness differences between pairs of skeleton edges. This differs from conventional geodesic histograms that are calculated for all figure points. The switch to the skeleton edges and areas of their attraction significantly speeds up the calculation of skeleton-geodesic histogram of thicknesses and distances, while maintaining many useful properties inherent in usual geodesic histograms. Extensive experimentation has been conducted on the most difficult binary shape database. Obtained classification results indicate the high potential of the proposed descriptor.

Keywords:
shape analysis, classification, continuous skeletons, skeletal geodesic distances, histograms.

Citation:
Lomov NA, Sidyakin SV, Visilter YuV. Classification of two-dimensional figures using skeleton-geodesic histograms of thicknesses and distances. Computer Optics 2017; 41(2): 227-236. DOI: 10.18287/2412-6179-2017-41-2-227-236.

References:

  1. Mestetskiy LM. Continuous morphology of binary images: figures, skeletons, circulars [In Russian]. Moscow: “Fizmatlit”; 2009. ISBN: 978-5-922110-50-1.
  2. Chui H, Rangarajan A. A new point matching algorithm for non-rigid registration. Computer Vision and Image Understanding 2003; 89(2-3): 114-141. DOI: 10.1016/S1077-3142(03)00009-2.
  3. Aslan C, Erdem A, Erdem E, Tari S. Disconnected skeleton: shape at its absolute scale. IEEE Trans Pattern Anal Mach Intell 2008; 30(12): 2188-2203. DOI: 10.1109/TPAMI.2007.70842.
  4. Bai X, Latecki L. Path similarity skeleton graph matching. IEEE Trans Pattern Anal Mach Intell 2008; 30(7): 1282-1292. DOI: 10.1109/TPAMI.2007.70769.
  5. Belongie S, Malik J, Puzicha J. Shape matching and object recognition using shape contexts. IEEE Trans Pattern Anal Mach Intell 2002; 24(4): 509-522. DOI: 10.1109/34.993558.
  6. Latecki L, Lakamper R. Shape similarity measure based on correspondence of visual parts. IEEE Trans Pattern Anal Mach Intell 2000; 22(10): 1185-1190. DOI: 10.1109/34.879802.
  7. Ling H, Jacobs D. Shape classificaton using the inner-distance. IEEE Trans Pattern Anal Mach Intell 2007; 29(2): 286-299. DOI: 10.1109/TPAMI.2007.41.
  8. Felzenszwalb PF, Schwartz JD. Hierarchical matching of deformable shapes. CVPR '07 2007: 1-8. DOI: 10.1109/CVPR.2007.383018.
  9. Bronstein AM Bruckstein AM, Kimmel R. Analysis of two-dimensional non-rigid shapes. International Journal of Computer Vision 2008; 78(1): 67-88. DOI: 10.1007/s11263-007-0078-4.
  10. Sebastian TB, Klein PN, Kimia BB. Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 2004; 26(5): 550-571. DOI: 10.1109/TPAMI.2004.1273924.
  11. Siddiqi K, Shokoufandeh A, Dickinson S, Zucker S. Shock graphs and shape matching. International Journal of Computer Vision 1999; 35(1): 13-32.
  12. Domakhina LG. Skeleton segmentation and circular morphology of polygons [In Russian]. PhD Thesis. Moscow: "MSU" Publisher; 2012.
  13. Mestetskiy LM. Medial width of a figure – an image shape descriptor [In Russian]. Machine Learning and Data Analysis 2014; 1(9): 1291-1318.
  14. Bai X, Liu W, Tu Z. Integrating contour and skeleton for shape classification. ICCV Workshops 2009: 360-367. DOI: 10.1109/ICCVW.2009.5457679.
  15. Shen W, Wang X, Yao C, Bai X. Shape recognition by combining contour and skeleton into a mid-level representation. Proceedings of the 6th China Conference on Pattern Recognition (CCPR) 2014: 391-400. DOI: 10.1007/978-3-662-45646-0_40.
  16. Sun KB, Super BJ. Classification of contour shapes using class segment sets. Proceedings of the 2005 IEEE Conference on Computer Vision and Pattern Recognition (CVPR '05) 2005; 2: 727-733.
  17. Lafon S. Diffusion maps and geometric harmonics. PhD Thesis. Yale University, Dept of Mathematics & Applied Mathematics 2004.
  18. Coifman R, Lafon S. Diffusion maps. Applied and Computational Harmonic Analysis 2006; 21(1): 5-30. DOI: 10.1016/j.acha.2006.04.006.
  19. Osada R, Funkhouser T, Chazelle B, Dobkin D. Matching 3D models with shape distributions. Shape Modeling International 2001: 154-166. DOI: 10.1109/SMA.2001.923386.
  20. Hamza AB, Krim H. Probabilistic shape descriptor for triangulated surfaces. IEEE International Conference on Image Processing 2005; 1: 1041-1044. DOI: 10.1109/ICIP.2005.1529932.
  21. Wang X, Feng B, Bai X, Liu W, Latecki LJ. Bag of contour fragments for robust shape classification. Pattern Recognition 2014; 47(6): 2116-2125. DOI: 10.1016/j.patcog.2013.12.008.
  22. Bai X, Rao C, Wang X. Shape vocabulary: A robust and efficient shape representation for shape matching. IEEE Transactions on Image Processing 2014; 23(9): 3935-3949. DOI: 10.1109/TIP.2014.2336542.
  23. Lomov NА, Mestetskiy LM. Area of the disk cover as an image shape descriptor. Computer Optics 2016; 40(4): 516-525. DOI: 10.18287/2412-6179-2016-40-4-516-525.
  24. Sivic J, Zisserman A. Video google: A text retrieval approach to object matching in videos. Proceedings of the 9th International Conference on Computer Vision 2003; 2: 1470-1477. DOI: 10.1109/ICCV.2003.1238663.
  25. Wang J, Yang J, Yu K, Lu F, Huang T, Gong Y. Locality-constrained linear coding for image classification. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2010: 3360-3367. DOI: 10.1109/CVPR.2010.5540018.
  26. Sidyakin SV. Morphological pattern spectra algorithm development for digital image and video sequences analysis [In Russian]. PhD Thesis. Moscow: Institution of Russian Academy of Sciences Dorodnicyn Computing Centre of RAS (CC RAS); 2013.
  27. Li Y, Zhu J, Li F. A hierarchical shape tree for shape classification. 25th International Conference of Image and Vision Computing New Zealand 2010: 1-6. DOI: 10.1109/IVCNZ.2010.6148820.
  28. Lim K-L, Galoogahi HK. Shape classification using local and global features. Fourth Pacific-Rim Symposium on Image and Video Technology (PSIVT) 2010: 115-120. DOI: 10.1109/PSIVT.2010.26.
  29. Ozay M, Aktas UR, Wyatt JL, Leonardis A. Compositional hierarchical representation of shape manifolds for classification of non-manifold shapes. IEEE International Conference on Computer Vision (ICCV) 2015: 1662-1670. DOI: 10.1109/ICCV.2015.194.
  30. Johnson DB. Efficient algorithms for shortest paths in sparse networks. JACM 1977; 24(1): 1-13. DOI: 10.1145/321992.321993.

© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; E-mail: journal@computeroptics.ru; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20