Control Systems and Computers, N2, 2021, Стаття 2
https://doi.org/10.15407/csc.2021.02.020
Vololazskiy Ye.V. A Modification of the Frechet Distance for Nonisomorphic Trees. Control Systems and Computers. 2021. №2-3. С. 20-27.
УДК 519.6
Є.В. Водолазський, старший науковий співробітник, Міжнародний науково-навчальний центр інформаційних технологій та систем НАН та МОН України, просп. Академіка Глушкова, 40, Київ, 03187, Україна, waterlaz@gmail.com
МОДИФІКАЦІЯ МЕТРИКИ ФРЕШЕ ДЛЯ НЕІЗОМОРФНИХ ДЕРЕВ
Вступ. Скелетизація зображень для подальшого порівняння пар скелетів є поширеною практикою в розпізнаванні зображень. У більшості випадків скелет зображення є ациклічною підмножиною поля зору. Поширеною метрикою для порівняння підмножин є метрика Фреше. Проте відстань Фреше визначено лише для пар ізоморфних дерев, що зводить нанівець можливість практичного застосовування такої метрики на деревах.
Мета статті. Необхідно розробити метод порівняння дерев, ідеологічно близький до метрики Фреше, але визначений для пар неізоморфних дерев.
Результати. У статті запропоновано модифікацію метрики Фреше для неізоморфних дерев. Нова числова характеристика названа близькістю дерева до еталону і визначена в тому числі для деяких класів пар неізоморфних дерев. Запропоновано поліноміальний алгоритм розпізнавання того, що одне дерево є близьким до іншого з точністю до заданого числа.
Завантажити повний текст PDF (англійською).
Ключові слова: обчислювальна геометрія, метрика Фреше, дерева.
Надійшла 01.06.2021
