(43-6) 12 * << * >> * Русский * English * Содержание * Все выпуски

Алгоритм совмещения пространственных объектов разномасштабных карт на основе топологического анализа данных

С.В. Еремеев1, Д.Е. Андрианов1, В.С. Титов2

1 Владимирский государственный университет
имени Александра Григорьевича и Николая Григорьевича Столетовых, Владимир, Россия,
2 ФГБОУ ВО «Юго-Западный государственный университет», Курск, Россия

 PDF, 983 kB

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

Страницы:1021-1029.

Аннотация:
В статье рассматривается проблема автоматического совмещения пространственных объектов на разномасштабных картах одной и той же местности. Для решения поставленной задачи предлагается использовать методы топологического анализа данных. Исходными данными алгоритма являются пространственные объекты, которые могут быть получены с карт разных масштабов и подвержены искажениям. Персистентная гомология позволяет идентифицировать общую структуру таких объектов в виде топологических особенностей. Основными топологическими особенностями в исследовании являются компоненты связности и пустоты объектов. В работе приводится математическое описание метода персистентной гомологии для представления пространственных объектов. Приводится определение баркода для пространственных данных, который содержит описание объекта в виде топологических признаков. Разработан алгоритм сравнения баркодов пространственных данных, который позволяет найти общую структуру объектов. Алгоритм базируется на анализе данных из баркода. Введён показатель схожести объектов по топологическим признакам. Показаны результаты исследований работы алгоритма. Проведённые эксперименты подтвердили высокое качество предложенного алгоритма. Процент схожести при сопоставлении природных объектов с учётом масштаба и деформации получился в пределах от 85 до 92, а для муниципальных при наличии растяжений и искажений частей объектов – от 74 до 87. Отражены преимущества предложенного подхода с аналогами при совмещении объектов, которые подвержены значительной деформации при масштабировании, а также при искажениях.

Ключевые слова:
персистентная гомология, баркод пространственного объекта, сопоставление объектов, анализ топологических особенностей, разномасштабные карты.

Цитирование:
Еремеев, С.В. Алгоритм совмещения пространственных объектов разномасштабных карт на основе топологического анализа данных / С.В. Еремеев, Д.Е. Андрианов, В.С. Титов // Компьютерная оптика. – 2019. – Т. 43, № 6. – С. 1021-1029. – DOI: 10.18287/2412-6179-2019-43-6-1021-1029.

Благодарности:
Исследование выполнено при финансовой поддержке РФФИ и администрации Владимирской области в рамках научного проекта № 17-47-330387.

Литература:
  1. Wallgrün, J. Qualitative matching of spatial information / J.O. Wallgrün, D. Wolter, K. Richter // GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems. – 2010. – P. 300-309.
  2. Mustière, S. Matching networks with different levels of detail / S. Mustière, T. Devogele // GeoInformatica. – 2008. – Vol. 12, Issue 4. – P. 435-453.
  3. Biedl, T. Planar matchings for weighted straight skeletons / T. Biedl, S. Huber, P. Palfrader // International Journal of Computational Geometry and Applications. – 2016. – Vol. 26, Issues 3-4. – P. 211-229.
  4. Ефимов, А.И. Алгоритм поэтапного уточнения проективного преобразования для совмещения изображений / А.И. Ефимов, А.И. Новиков // Компьютерная оптика. – 2016. – Т. 40, № 2. – С. 258-265. – DOI: 10.18287/2412-6179-2016-40-2-258-265.
  5. Zhao, L. Shape matching algorithm based on shape contexts / L. Zhao, Q. Peng, B. Huang // IET Computer Vision. – 2015. – Vol. 9, Issue 5. – P. 681-690.
  6. Eremeev, S.V. Comparison of urban areas based on database of topological relationships in geoinformational systems / S.V. Eremeev, D.E. Andrianov, V.A. Komkov // Pattern Recognition and Image Analysis. – 2015. – Vol. 25, No 2. – P. 314-320.
  7. Eremeev, S. An approach to establishing the correspondence of spatial objects on heterogeneous maps based on methods of computational topology / S. Eremeev, K. Kuptsov, S. Romanov. – In: Analysis of images, social networks and texts (AIST 2017) / ed. by W. van der Aalst, [et al.]. – Cham: Springer, 2018. – P. 172-182.
  8. Zhang, T. Multi-task correlation particle filter for robust object tracking / T. Zhang, C. Xu, M. Yang // IEEE Conference on Computer Vision and Pattern Recognition. – 2017. – Vol. 1(2). – P. 4819-4827.
  9. Садыков, С.С. Алгоритм построения выпуклой оболочки бинарного изображения и формирование его безразмерных признаков / С.С. Садыков // Алгоритмы, методы и системы обработки данных. – 2015. – № 2(31). – С. 77-85.
  10. Ломов, Н.А. Площадь дискового покрытия – дескриптор формы изображения / Н.А. Ломов, Л.М. Местецкий // Компьютерная оптика. – 2016. – Т. 40, № 4. – С. 516-525. – DOI: 10.18287/2412-6179-2016-40-4-516-525.
  11. Ломов, Н.А. Классификация двумерных фигур с использованием скелетно-геодезических гистограмм толщин-расстояний / Н.А. Ломов, С.В. Сидякин, Ю.В. Ви- зильтер // Компьютерная оптика. – 2017. – Т. 41, № 2. – С. 227-236. – DOI: 10.18287/2412-6179-2017-41-2-227-236.
  12. Eitz, M. Sketch-based shape retrieval / M. Eitz, R. Richter, T. Boubekeur, K. Hildebrand, M. Alexa // ACM Transactions on Graphics. – 2012. – Vol. 31, Issue 4. – 31.
  13. Bai, X. Path similarity skeleton graph matching / X. Bai, L.J. Latecki // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2008. – Vol. 30, Issue 7. – P. 1282-1292.
  14. Kališnik, S. A higher-dimensional homologically persistent skeleton / S. Kališnik, V. Kurlin, D. Lesnik // Advances in Applied Mathematics. – 2019. – Vol. 102. – P. 113-142.
  15. Carlsson, G. Persistence barcodes for shapes / G. Carlsson, A. Zomorodian, A. Collins, L. Guibas // Proceedings of the 2004 Eurographics, ACM SIGGRAPH Symposium on Geometry Processing. – 2004. – P. 124-135.
  16. Skraba, P. Persistence-based segmentation of deformable shapes / P. Skraba, M. Ovsjanikov, F. Chazal, L. Guibas // 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition – Workshops. – 2010. – P. 45-52.
  17. Förstner, W. Detecting interpretable and accurate scale-invariant keypoints / W. Förstner, T. Dickscheid, F. Schind¬ler // IEEE 12th International Conference on Computer Vision. – 2009. – P. 2256-2263.
  18. Su, Y. Contour guided hierarchical model for shape matching / Y. Su, Y. Liu, B. Cuan, N. Zheng // IEEE International Confer-ence on Computer Vision (ICCV). – 2015. – P. 1609-1617.
  19. Ahmed, M. Local persistent homology based distance between maps / M. Ahmed, B. Fasy, C. Wenk // Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. – 2014. – P. 43-52.
  20. Bendich, P. Homology and robustness of level and interlevel sets / P. Bendich, H. Edelsbrunner, D. Morozov, A. Patel // Homol-ogy, Homotopy and Applications. – 2013. Vol. 15. – P. 51-72.
  21. Collins, A. A barcode shape descriptor for curve point cloud data / A. Collins, A. Zomorodian, G. Carlsson, L. Guibas // Com-puters and Graphics. – 2004. – Vol. 28. – P. 881-894.
  22. Carlsson, E. An algebraic topological method for feature identification / E. Carlsson, G. Carlsson, V. de Silva, S. Fortune // In-ternational Journal of Computational Geometry and Applications. – 2006. Vol. 16(4). – P. 291-314.
  23. Carlsson, G. Topological pattern recognition for point cloud data / G. Carlsson // Acta Numerica. – 2014. – Vol. 23. – P. 289-368.
  24. Lum, P.Y. Extractng insights from the shape of complex data using topology / P.Y. Lum, G. Singh, A. Lehman, T. Ishkanov, M. Vejdemo-Johansson, M. Alagappan, J. Carlsson, G. Carlsson // Scientific Reports. – 2013. – Vol. 3. – P. 12-36.
  25. Макаренко, Н.Г. Распознавание текстур на цифровых изображениях методами вычислительной топологии / Н.Г. Макаренко, Ф.А. Уртьев, И.С. Князева, Д.Б. Малкова, И.Т. Пак, Л.М. Каримова // Современные проблемы дистан-ционного зондирования Земли из космоса. – 2015. – Т. 12, № 1. – С. 131-144.
  26. Zhu, X. Persistent homology: An introduction and a new text representation for natural language processing / X. Zhu // Proceed-ings of the Twenty-Third International Joint Conference on Artificial Intelligence. – 2013. – P. 1953-1959.
  27. Edelsbrunner, H. Computational topology: An introduction / H. Edelsbrunner. – American Mathematical Society, 2009
    .

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