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

Abstract

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