A method for determining the fuzzy discrete Fréchet distance

Abstract

EN: Context. The article addresses the problem of image similarity assessment based on the Fréchet distance metric and its modifications. In this context, images are approximated by polygonal curves. The problem arises from the need to quantitatively evaluate image similarity for tasks such as image generation, clustering, and recognition. Quantitative assessment of the proximity of biomedical images supports decision-making in automated diagnostic systems. The object of the study is the process of image similarity evaluation. The subject of the study is the Fréchet distance metric and its modifications. Objective. To develop a method for determining the fuzzy discrete Fréchet distance, to evaluate the computational complexity of the proposed method, to implement the algorithm for determining the fuzzy discrete Fréchet distance in software, and to conduct computational experiments to evaluate the fuzzy discrete Fréchet distance between polygons. Method. The article presents a method for determining the fuzzy discrete Fréchet distance based on the fuzzy Fréchet metric between polygonal curves. The fuzzy Fréchet metric is grounded in the classical Fréchet distance defined on the space of parameterized curves. The required approximation for practical applications is achieved through the discretization of the fuzzy Fréchet metric. The developed method estimates the fuzzy discrete Fréchet distance between polygonal curves by adapting the algorithm for computing the classical discrete Fréchet distance. Results. The computer experiments were conducted on a set of predefined regions approximated by polygonal curves. Based on the proposed method, an algorithm was developed to evaluate the discrete fuzzy Fréchet distance. The developed algorithm exhibits low computational complexity, equal to the product of the discretized segments of the polygonal curves: O(Cm·n). This enables the estimation of the discrete Fréchet distance with a specified similarity threshold. The software implementation of the method is intended to be integrated into an automatic medical diagnostic system. Conclusions. The results obtained in the study allow recommending the developed method for evaluating image similarity based on the fuzzy discrete Fréchet distance for broad application in computer vision systems, including image generation, clustering, and recognition. UK: Актуальність. У статті розглянуто проблему оцінки подібності зображень на основі метрики Фреше та її модифікацій. При цьому зображення апроксимовані полігональними кривими. Проблема обумовлена необхідністю кількісно оцінювати подібність зображень для задач генерування, кластеризації та розпізнавання зображень. Кількісна оцінка близькості біомедичних зображень допомагає підтримувати прийняття рішення в системах автоматичного діагностування. Об’єктом дослідження є процес оцінки подібності зображень. Предметом дослідження є метрика Фреше та її модифікації. Мета роботи – розробити метод визначення нечіткої дискретної відстані Фреше, оцінити обчислювальну складність розробленого методу, програмно реалізувати алгоритм методу визначення нечіткої дискретної відстані Фреше та провести комп’ютерні експерименти з визначення нечіткої дискретної відстані Фреше між полігонами. Метод. У статті розроблено метод визначення дискретної нечіткої відстані Фреше, що базується на нечіткій метриці Фреше між полігональними кривими. В основі нечіткої метрики Фреше лежить метрика Фреше на просторі параметризованих кривих. Потрібна для застосувань апроксимація задається процедурою дискретизації нечіткої метрики Фреше. Розроблений метод оцінює дискретну нечітку відстань Фреше між полігональними кривими на основі алгоритму обчислення дискретної відстані Фреше. Результати. Комп’ютерні експерименти проводились на наборі заданих областей, апроксимованих полігональними кривими. На основі запропонованого методу розроблено алгоритм оцінки дискретної нечіткої відстані Фреше. Розроблений алгоритм має низьку обчислювальну складність, яка рівна добутку дискретизованих відрізків полігональних кривих: O(Cm · n). Це дало змогу оцінювати дискретну відстань Фреше із заданим порогом подібності. Програмна реалізація методу буде інтегрована в систему автоматичного медичного діагностування. Висновки. Отримані результати дослідження дозволяють рекомендувати розроблений метод оцінки близькості зображень на основі нечіткої дискретної відстані Фреше в системах комп’ютерного зору для широкого застосування: генерування, кластеризації та розпізнавання зображень.