Search academic texts

Information × Registration Number 0421U103376, Candidate dissertation Status Кандидат технічних наук Date 09-09-2021 popup.evolution o Title Efficient methods for computing image similarity in the Frechet metric Author Vodolazskyi Yevhen Valeriiovych, popup.head Schlesinger Mikhail Ivanovich popup.opponent Berezkyi Oleh M. popup.opponent Vorobel Roman Antonovych popup.review Kryvyi Sergiy Lukianovych popup.review Varfolomieiev Anton Yu. popup.review Kussul Nataliia Mykolaivna Description Робота присвячена проблемі обчислення відстані Фреше, як більш сильної метрики, ніж відстань Хаусдорфа, між різними класами підмножин метричних просторів, зокрема підмножин в R^2. Розглянуто проблеми обчислення відстані Фреше між замкненими ламаними лініями (багатокутниками), розгалуженими ламаними лініями (деревами), множинами ламаних ліній, заданих як шляхи на ациклічних орієнтованих графах, а також обчислення дискретної відстані Фреше між замкненими послідовностями (циклами). Запропоновано ефективний алгоритм розпізнавання, чи перевищує відстань Фреше між двома замкненими ламаними лініями (багатокутниками) задане число. Час роботи становить O(mn), де m,n – кількість прямолінійних відрізків у двох ламаних, відповідно. Запропоновано ефективний алгоритм обчислення значення дискретної відстані Фреше між двома замкненими послідовностями (циклами) з часом роботи O(mn log*(mn)), де log* – ітерований логарифм, а m,n – кількість точок в циклах. Розглянута ситуація, коли ламані лінія для обчислення відстані Фреше задано не однозначно, а як множини шляхів на ациклічному орієнтованому графі. Сформульована нова задача розпізнавання, чи існує така пара ламаних, кожна зі своєї множини, що відстань Фреше між ними не перевищує задане число. Запропоновано алгоритм, що розв’язує цю задачу за час O(mn), де m,n – кількість ребер в двох графах, відповідно. Сформульовано нове поняття близькості одного дерева до іншого дерева еталону. Близькість, хоча й не є метрикою, є числовою оцінкою більш слабкою ніж метрика Фреше, але більш сильною ніж метрика Хаусдорфа. Близькість одного дерева до іншого скінченна навіть для неізоморфних дерев, на відміну від метрики Фреше. Запропоновано поліноміальний алгоритм розпізнавання близькості дерева до еталону. Сформульована нова задача розпізнаванні безконфліктності двох ламаних ліній, що є в певному сенсі двоїстою до задачі розпізнавання схожості ламаних ліній в метриці Фреше. Запропоновано алгоритм розв’язку с оцінкою складності O(mn). Registration Date 2021-09-17 popup.nrat_date 2021-09-17 Close