(43-6) 12 * << * >> * Russian * English * Content * All Issues

An algorithm for matching spatial objects of different-scale maps based on topological data analysis

S.V. Eremeev1, D.E. Andrianov1, V.S. Titov2

1 Vladimir State University, Vladimir, Russia,
2 Southwest State University, Kursk, Russia

 PDF, 983 kB

DOI: 10.18287/2412-6179-2019-43-6-1021-1029

Pages: 1021-1029.

Full text of article: Russian language.

Abstract:
A problem of automatic comparison of spatial objects on maps with different scales for the same locality is considered in the article. It is proposed that this problem should be solved using  methods of topological data analysis. The initial data of the algorithm are spatial objects that can be obtained from maps with different scales and subjected to deformations and distortions. Persistent homology allows us to identify the general structure of such objects in the form of topological features. The main topological features in the study are the connectivity components and holes in objects. The paper gives a mathematical description of the persistent homology method for representing spatial objects. A definition of a barcode for spatial data, which contains a description of the object in the form of topological features is given. An algorithm for comparing feature barcodes was developed. It allows us to find the general structure of objects. The algorithm is based on the analysis of data from the barcode. An index of objects similarity in terms of topological features is introduced. Results of the research of the algorithm for comparing maps of natural and municipal objects with different scales, generalization and deformation are shown. The experiments confirm the high quality of the proposed algorithm. The percentage of similarity in the comparison of natural objects, while taking into account the scale and deformation, is in the range from 85 to 92, and for municipal objects, after stretching and distortion of their parts, was from 74 to 87. Advantages of the proposed approach over analogues for the comparison of objects with significant deformation at different scales and after distortion are demonstrated.

Keywords:
persistent homology, barcode of spatial object, comparison of objects, analysis of topological features, multi-scale maps.

Citation:
Eremeev SV, Andrianov DE, Titov VS. An algorithm for matching spatial objects of different-scale maps based on topological data analysis. Computer Optics 2019; 43(6): 1021-1029. DOI: 10.18287/2412-6179-2019-43-6-1021-1029.

Acknowledgements:
The work was funded by the Russian Foundation for Basic Research (RFBR) and Vladimir region authorities under the research project No. 17-47-330387.

References:
  1. Wallgrün J, Wolter D, Richter K. Qualitative matching of spatial information. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems 2010: 300-309.
  2. Mustière S, Devogele T. Matching networks with different levels of detail. GeoInformatica 2008; 12(4): 435-453.
  3. Biedl T, Huber S, Palfrader P. Planar matchings for weighted straight skeletons. International Journal of Computational Geometry and Applications 2016; 26(3-4): 211-229.
  4. Efimov AI, Novikov AI. An algorithm for multistage projective transformation adjustment for image superimposition [In Russian]. Computer Optics 2016; 40(2): 258-265. DOI: 10.18287/2412-6179-2016-40-2-258-265.
  5. Zhao L, Peng Q, Huang B. Shape matching algorithm based on shape contexts. IET Comp Vis 2015; 9(5): 681-690.
  6. Eremeev SV, Andrianov DE, Komkov VA. Comparison of urban areas based on database of topological relationships in geoinformational systems. Pattern Recognition and Image Analysis 2015; 25(2): 314-320.
  7. Eremeev S, Kuptsov K, Romanov S. An approach to establishing the correspondence of spatial objects on heterogeneous maps based on methods of computational topology. In Book: van der Aalst W, et al, eds. Analysis of images, social networks and texts (AIST 2017). Cham: Springer; 2018: 172-182.
  8. Zhang T, Xu C, Yang M. Multi-task correlation particle filter for robust object tracking. IEEE Conf Comp Vis Pattern Recogn 2017; 1(2): 4819-4827.
  9. Sadykov SS. Algorithm for the construction of a convex hull of a binary image and the formation of its dimensionless features [In Russian]. Algorithms, Methods and Data Processing Systems 2015; 2(31): 77-85.
  10. 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.
  11. 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.
  12. Eitz M, Richter R, Boubekeur T, Hildebrand K, Alexa M. Sketch-based shape retrieval. ACM Transactions on Graphics 2012; 31(4): 31.
  13. Bai X, Latecki LJ. Path similarity skeleton graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence 2008; 30(7): 1282-1292.
  14. Kališnik S, Kurlin V, Lesnik D. A higher-dimensional homologically persistent skeleton. Advances in Applied Mathematics 2019; 102: 113-142.
  15. Carlsson G, Zomorodian A, Collins A, Guibas L. Persistence barcodes for shapes. Proc 2004 Eurographics, ACM SIGGRAPH Symposium on Geometry Processing 2004: 124-135.
  16. Skraba P, Ovsjanikov M, Chazal F, Guibas L. Persistence-based segmentation of deformable shapes. Proc CVPRW 2010: 45-52.
  17. Förstner W, Dickscheid T, Schindler F. Detecting interpretable and accurate scale-invariant keypoints. IEEE 12th ICCV 2009: 2256-2263.
  18. Su Y, Liu Y, Cuan B, Zheng N. Contour guided hierarchical model for shape matching. IEEE ICCV 2015: 1609-1617.
  19. Ahmed M, Fasy B, Wenk C. Local persistent homology based distance between maps. Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems 2014: 43-52.
  20. Bendich P, Edelsbrunner H, Morozov D, Patel A. Homology and robustness of level and interlevel sets. Homology, Homotopy and Applications 2013; 15: 51-72.
  21. Collins A, Zomorodian A, Carlsson G, Guibas L. A barcode shape descriptor for curve point cloud data. Computers and Graphics 2004; 28: 881-894.
  22. Carlsson E., Carlsson G., de Silva V., and Fortune S. An algebraic topological method for feature identification. International Journal of Computational Geometry and Applications 2006; 16(4): 291-314.
  23. Carlsson G. Topological pattern recognition for point cloud data. Acta Numerica 2014; 23: 289-368.
  24. Lum PY, Singh G, Lehman A, Ishkanov T, Vejdemo-Johansson M, Alagappan M, Carlsson J, Carlsson G. Extractng insights from the shape of complex data using topology. Sci Rep 2013; 3: 12-36.
  25. Makarenko ND, Yuriev FA, Knyazeva IS, Malkova DB, Pak IT, Karimova LM. Texture recognition on digital images using computational topology methods [In Russian]. Modern problems of remote sensing the Earth from space 2015; 12(1): 131-144.
  26. Zhu X. Persistent homology: An introduction and a new text representation for natural language processing. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence 2013: 1953-1959.
  27. Edelsbrunner H. Computational topology: An introduction. American Mathematical Society; 2009.

 

© 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