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

Автор: Еремеев Сергей Владимирович, Андрианов Дмитрий Евгеньевич, Титов Виталий Семенович

Журнал: Компьютерная оптика @computer-optics

Рубрика: Обработка изображений, распознавание образов

Статья в выпуске: 6 т.43, 2019 года.

Бесплатный доступ

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

Еще

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

Короткий адрес: https://sciup.org/140246527

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

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

  • Wallgrun, J. Qualitative matching of spatial information / J.O. Wallgrun, D. Wolter, K. Richter // GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems. - 2010. - P. 300-309.
  • Mustiere, S. Matching networks with different levels of detail / S. Mustiere, T. Devogele // GeoInformatica. - 2008. - Vol. 12, Issue 4. - P. 435-453.
  • 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.
  • Ефимов, А.И. Алгоритм поэтапного уточнения проективного преобразования для совмещения изображений / А.И. Ефимов, А.И. Новиков // Компьютерная оптика. -2016. - Т. 40, № 2. - С. 258-265. - DOI: 10.18287/24126179-2016-40-2-258-265
  • 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.
  • 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.
  • 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.
  • 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.
  • Садыков, С. С. Алгоритм построения выпуклой оболочки бинарного изображения и формирование его безразмерных признаков / С. С. Садыков // Алгоритмы, метода: и система: обработки данных. - 2015. - № 2(31). - С. 77-85.
  • Ломов, Н.А. Площадь дискового покрытия - дескриптор формы изображения / Н.А. Ломов, Л.М. Местецкий // Компьютерная оптика. - 2016. - Т. 40, № 4. - С. 516525. -
  • DOI: 10.18287/2412-6179-2016-40-4-516-525
  • Ломов, Н.А. Классификация двумерных фигур с использованием скелетно-геодезических гистограмм толщин-расстояний / Н.А. Ломов, С.В. Сидякин, Ю.В. Ви-зильтер // Компьютерная оптика. - 2017. - Т. 41, № 2. - С. 227-236. -
  • DOI: 10.18287/2412-6179-2017-41-2-227-236
  • 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.
  • 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.
  • Kalisnik, S. A higher-dimensional homologically persistent skeleton / S. Kalisnik, V. Kurlin, D. Lesnik // Advances in Applied Mathematics. - 2019. - Vol. 102. - P. 113142.
  • 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.
  • 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. 4552.
  • Forstner, W. Detecting interpretable and accurate scale-invariant keypoints / W. Forstner, T. Dickscheid, F. Schindler // IEEE 12th International Conference on Computer Vision. - 2009. - P. 2256-2263.
  • Su, Y. Contour guided hierarchical model for shape matching / Y. Su, Y. Liu, B. Cuan, N. Zheng // IEEE International Conference on Computer Vision (ICCV). - 2015. -P. 1609-1617.
  • 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.
  • Bendich, P. Homology and robustness of level and interlevel sets / P. Bendich, H. Edelsbrunner, D. Morozov, A. Patel // Homology, Homotopy and Applications. - 2013. Vol. 15. - P. 51-72.
  • Collins, A. A barcode shape descriptor for curve point cloud data / A. Collins, A. Zomorodian, G. Carlsson, L. Guibas // Computers and Graphics. - 2004. - Vol. 28. - P. 881-894.
  • Carlsson, E. An algebraic topological method for feature identification / E. Carlsson, G. Carlsson, V. de Silva, S. Fortune // International Journal of Computational Geometry and Applications. - 2006. Vol. 16(4). - P. 291-314.
  • Carlsson, G. Topological pattern recognition for point cloud data / G. Carlsson // Acta Numerica. - 2014. - Vol. 23. -P. 289-368.
  • 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.
  • Макаренко, Н.Г. Распознавание текстур на цифровых изображениях методами вычислительной топологии / Н.Г. Макаренко, Ф.А. Уртьев, И.С. Князева, Д.Б. Малкова, И.Т. Пак, Л.М. Каримова // Современые проблемы дистанционного зондирования Земли из космоса. - 2015. - Т. 12, № 1. - С. 131-144.
  • Zhu, X. Persistent homology: An introduction and a new text representation for natural language processing / X. Zhu // Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. - 2013. - P. 1953-1959.
  • Edelsbrunner, H. Computational topology: An introduction / H. Edelsbrunner. - American Mathematical Society, 2009.
Еще
Статья научная