A METHOD FOR DETERMINING THE FUZZY DISCRETE FRÉCHET DISTANCE
DOI:
https://doi.org/10.15588/1607-3274-2025-4-4Keywords:
metric, fuzzy Fréchet metric, fuzzy discrete Fréchet metric, image, polygonal curvesAbstract
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.
References
Gonzalez R. C., Woods R. E. Digital Image Processing. Fourth Edition, Pearson Education, 2018, 1020 p.
Ralević N. M., Paunović M. V., Iričanin B. D. Fuzzy metric space and applications in image processing, Math. Mon., 2020, Vol. 48, pp. 103–117. DOI:10.20948/mathmontis- 2020-48-9
Gregori V., Morillas S., Sapena A. Examples of fuzzy metrics and applications, Fuzzy Sets and Systems, 2011, Vol. 170, № 1, pp. 95–111. DOI: 10.1016/j.fss.2010.10.019
Golestaneh P., Zekri M., Sheikholeslam F. Fuzzy wavelet extreme learning machine, Fuzzy Sets and Systems, 2018, Vol. 342, pp. 90–108. DOI: 10.1016/j.fss.2017.12.006
Ralević N. M., Karaklić D., Pištinjat N. Fuzzy metric and its applications in removing the image noise, Soft Computing, 2019, Vol. 23, № 22, pp.12049–12061.DOI: 10.1007/s00500-019-03762-5
Soto-Hidalgo J. M., Sánchez D., Chamorro-Martínez J., Martínez-Jiménez P. M. Color comparison in fuzzy color spaces, Fuzzy Sets and Systems, 2020, Vol. 390, pp. 160– 182. DOI: 10.1016/j.fss.2019.09.013
Vinurajkumar S., Anandhavelu S. An Enhanced Fuzzy Segmentation Framework for extracting white matter from T1- weighted MR images, Biomedical Signal Processing and Control, 2022, Vol. 71, P. 103093. DOI: 10.1016/j.bspc.2021.103093
Bloch I. Fuzzy skeleton and skeleton by influence zones: a review. In Skeletonization: Theory, Methods and Applications. Elsevier, Academic Press, 2017, pp. 71–87. DOI: 10.1016/B978-0-08-101291-8.00004-3
Soto J., Flores-Sintas A., Palarea-Albaladejo J. Improving probabilities in a fuzzy clustering partition, Fuzzy Sets and Systems, 2008, Vol. 159, № 4, pp. 406–421. DOI: 10.1016/j.fss.2007.08.016
Campomanes-Álvarez C., Campomanes-Álvarez B. R., Guadarrama S., Ibáñez O., Cordón O. An experimental study on fuzzy distances for skull-face overlay in craniofacial superimposition, Fuzzy Sets and Systems, 2017, Vol. 318, pp. 100–119. DOI: 10.1016/j.fss.2016.06.015
Leski J.M. Fuzzy c-ordered-means clustering, Fuzzy Sets and Systems, 2016, Vol. 286, pp. 114–133. DOI: 10.1016/j.fss.2014.12.007
Saha I., Sarkar J. P., Maulik U. Integrated Rough Fuzzy Clustering for Categorical Data Analysis, Fuzzy Sets and Systems, 2019, Vol. 361, № 15, pp. 1–32. DOI: 10.1016/j.fss.2018.02.007
Bandyopadhyay S., Saha S., Pedrycz W. Use of a fuzzy granulation-degranulation criterion for assessing cluster validity, Fuzzy Sets and Systems, 2011, Vol. 170, № 1, pp. 22– 42. DOI: 10.1016/j.fss.2010.11.015
Das A., Mohapatra S. K., Mohanty M. N. Design of deep ensemble classifier with fuzzy decision method for biomedical image classification, Applied Soft Computing, 2022, Vol. 115, P. 108178. DOI: 10.1016/j.asoc.2021.108178
Bazylevych L., Berezsky O., Zarichnyi M. Frechet fuzzy metric, Matematychni Studii, 2022, Vol. 57, No. 2, pp. 210– 215. DOI: 10.30970/ms.57.2.210-215.
Eiter, T.; Mannila, H. Computing Discrete Fréchet Distance. Tech. Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994.
Berezkyi M., Berezsky O., Zarichnyi M. Discrete Frechet fuzzy metric, Fuzzy Sets and Systems, 2025. (submitted).
Berezsky O., Zarichnyi M. In: Shakhovska N., Medykovskyy M. O. (eds) Metric Methods in Computer Vision and Pattern Recognition, Advances in Intelligent Systems and Computing V. CSIT 2020. Advances in Intelligent Systems and Computing, V. 1293. Springer, Cham. DOI: 10.1007/978-3-030-63270-0_13.
Berezsky O., Zarichnyi M. Fréchet distance between weighted rooted trees, Matematychni Studii, 2017, Vol. 48, No.2, pp. 165–170. DOI: 10.15330/ms.48.2.165-170
Berezsky O., Zarichnyi M. Gromov-Fréchet distance between curves, Matematychni Studii, 2018, Vol. 50, No. 1, pp. 88–92.
Berezsky O., Zarichnyi M., Pitsun O. Development of a metric and the methods for quantitative estimation of the segmentation of biomedical images, Eastern-European Journal of Enterprise Technologies, 2017, Vol. 6, № 4, pp. 4–11. DOI: 10.15587/1729-4061.2017.119493
Šostak A. George-Veeramani Fuzzy Metrics Revised, Axioms, 2018, Vol. 7, № 3, P. 60. DOI: 10.3390/axioms7030060
Repovš D., Savchenko A., Zarichnyi M. Fuzzy Prokhorov metric on the set of probability measures, Fuzzy Sets and Systems, 2011, Vol. 175, № 1, pp. 96–104. DOI: 10.1016/j.fss.2011.02.014
Gutiérrez García J., Romaguera S., Sanchis M. An identification theorem for the completion of the Hausdorff fuzzy metric, Fuzzy Sets and Systems, 2013, Vol. 227, pp. 96–106. DOI: 10.1016/j.fss.2013.04.012
Filtser O. Universal Approximate Simplification Under the Discrete Fréchet Distance, Information Processing Letters. – 2018, Vol. 132, pp. 22–27. DOI: 10.1016/j.ipl.2017.10.002
Bringmann K., Mulzer W. Approximability of the discrete Fréchet distance, Journal of Computational Geometry, 2016, Vol. 7, № 2, pp. 46–76. DOI: 10.20382/jocg.v7i2a4
Chan T. M., Rahmati Z. An Improved Approximation Algorithm for the Discrete Fréchet Distance, Information Processing Letters, 2018, Vol. 138, pp. 72–74. DOI: 10.1016/j.ipl.2018.06.011
Wylie T., Zhu B. Following a Curve with the Discrete Fré- chet Distance, Theoretical Computer Science, 2014, Vol. 556, pp. 34–44. DOI: 10.1016/j.tcs.2014.06.026
Ahn H.-K., Alt H., Buchin M., Oh E., Scharf L., Wenk C. Middle Curves Based on Discrete Fréchet Distance, Computational Geometry, 2020, Vol. 89, P. 101621. DOI: 10.1016/j.comgeo.2020.101621
Vodolazskiy E. Discrete Fréchet Distance for Closed Curves, Computational Geometry, 2023, Vol. 111, P. 101967. DOI: 10.1016/j.comgeo.2022.101967
Agarwal P.K., Ben Avraham R., Kaplan H., Sharir M. Computing the Discrete Fréchet Distance in Subquadratic Time, SIAM Journal on Computing, 2014, Vol. 43, No. 2, pp. 429– 449. DOI: 10.1137/130920526
Deza M. M., Deza E.Encyclopedia of Distances. SpringerVerlag Berlin Heidelberg,2013,583p.
Schweizer B., Sklar A. Statistical metric spaces, Pacific Journal of Mathematics, 1960, Vol. 10, pp. 313–334. DOI: 10.2140/pjm.1960.10.313
Bag T., Samanta S. K. Finite dimensional fuzzy normed linear spaces, Journal of Fuzzy Mathematics, 2003, Vol. 11, pp. 687–705.
Font J. J., Galindo J., Macario S., Sanchís M. Mazur-Ulam type theorems for fuzzy normed spaces, Journal of Nonlinear Sciences and Applications, 2017, Vol. 10, № 8, pp. 4499–4506. DOI:10.22436/jnsa.010.08.41
Sánchez J. C., González D. M. A natural correspondence between quasiconcave functions and fuzzy norms, Fuzzy Sets and Systems, 2023, Vol. 466, P. 108413. DOI: 10.1016/j.fss.2022.10.005
Godau M. On the complexity of measuring the similarity between geometric objects in higher dimensions. PhD thesis, Freie Universtät Berlin, 1999. URL: https://doi.org/10.17169/refubium-7780
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 O. M. Berezsky, M. O. Berezkyi, M. M Zarichnyi
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) as it can lead to productive exchanges, as well as earlier and greater citation of published work.
