Control Systems and Computers, N1, 2021, Стаття 3
https://doi.org/10.15407/csc.2021.01.029
Vodolazskiy Ye.V. Frechet Similarity Between Two Ambiguously Defined Polygonal Lines. Control Systems and Computers. 2021. №1. pp. 29-34.
Є.В. Водолазський, старший науковий співробітник, Міжнародний
науково-навчальний центр інформаційних технологій та систем НАН та МОН України,
просп. Академіка Глушкова, 40, Київ, 03187, Україна, waterlaz@gmail.com
РОЗПІЗНАВАННЯ СХОЖОСТІ НЕОДНОЗНАЧНО ЗАДАНИХ
ЛАМАНИХ ЛІНІЙ У МЕТРИЦІ ФРЕШЕ
Вступ. В практиці розпізнавання образів проблему порiвняння пари зображень часто зводять до пошуку контурів на зображеннях, що є кривими без самоперетинів, та порівнянню цих кривих. Однією з найпоширеніших метрик для аналізу схожості таких кривих є метрика Фреше, обчисленню якої для пари ламаних ліній присвячено багато публікацій. На жаль, у більшості випадків виділення контурів на зображенні не є однозначним. Отже при розгляді пари зображень замість порівняння пари кривих необхідно аналізувати пару сукупностей кривих.
Мета статті. Необхідно розробити алгоритм, який би за двома множинами ламаних ліній та заданому числу визначав би, чи існує в цих множинах така пара ламаних (по одній з кожної множини), що відстань Фреше між ними не перевищує задане число.
Результати. В статті наведено алгоритм, який в якості вхідних даних отримує пару орієнтованих ациклічних графів, вершинами якого є точки метричного простору, а ребрами – прямолінійні відрізки, що з’єднують вершини, та додатнє число. Таким чином, кожний шлях на графі задає ламану лінію, а граф у цілому задає множину ламаних ліній. На виході алгоритм дає відповідь, чи існує в двох графах така пара ламаних, що відстань Фреше між ними не перевищує задане число. Час роботи алгоритму пропорційний добутку кількості ребер одного графа на кількість ребер другого.
Висновки. Відомі алгоритми, що за парою ламаних визначають, чи перевищує відстань Фреше між ламаними задане додатнє число, потребують часу, що пропорційний добутку кількості прямолінійних відрізків однієї ламаної на кількість прямолінійниз відрізків іншої ламаної. Отже отриманий результат є узагальненням відомого алгоритму.
Завантажити повний текст PDF (англійською ).
Ключові слова: обчислювальна геометрія, метрика Фреше, алгоритмічна складність.
Надійшла 10.03.2021
