Abstract
Since its inception, the notion of metric finds numerous applications not only in various domains of mathematics but also in computer science. Some special metrics (like Hausdorff metric on sets, Fréchet metrics on the set of curves, the Kantorovich metric on the set of probability measures as well as their versions and modifications) allow for obtaining quantitative estimations of dissimilarity between objects of different nature, in particular, images or sets of data. Comparison of objects is used in computer vision for evaluation of the accuracy of classifiers, search for objects by template, handwriting recognition. Therefore, we provide a survey of literature on the subject focusing on results concerning Fréchet metrics on the set of trees (in particular, curves) in metric space obtained by the authors. These metrics have their modifications called the Gromov-Fréchet metrics and they are defined on the isometry classes of (nonrooted) trees in metric spaces. In particular, we prove that the obtained space of trees is separable and non-complete. The consideration of the paper concern the quality of segmentation of objects that are presented in the form of polygons. Comparison of objects is based on the Fréchet metric between trees.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agarwal, P.K., Fox, K., Nath, A., Sidiropoulos, A., Wang, Y.: Computing the Gromov-Hausdorff distance for metric trees. ACM Trans. Algorithms 14, 24:1–24:20 (2018)
Akitaya, H.A., Buchin, M., Ryvkin, L., Urhausen, J.: The k-Fréchet Distance: How to Walk Your Dog While Teleporting, preprint (2019)
Alber, J., Niedermeier, R.: On multidimensional curves with Hilbert property. Theory Comput. Syst. 33(4), 295–312 (2000)
Alt, H., Behrends, B., Blomer, J.: Approximate matching of polygonal shapes. Ann. Math. Artif. Intell. 13, 251–265 (1995)
Alt, H., Buchin, M.: Can we compute the similarity between surfaces? Discrete Comput. Geom. 43(1), 78–99 (2010)
Alt, H., Godau, M.: Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geom. Appl. 5, 75–91 (1995)
Atallah, M.J.: A linear time algorithm for the Hausdorff distance between convex polygons. Inf. Process. Lett. 17, 207–209 (1983)
Bazylevych, L.E., Zarichnyi, M.M.: On metrization of the hyperspace of oriented curves. Vis. Lviv. Univ. Ser. mekh.-mat. 43, 3–5 (1996)
Berezsky, O.: Fréchet metric for trees. In: Proceedings of the 2016 IEEE First International Conference on Data Stream Mining & Processing (DSMP), Lviv, 23–27 August 2016, pp. 213–217 (2016)
Berezsky, O., Melnyk, G., Batko, Y., Pitsun, O.: Regions matching algorithms analysis to quantify the image segmentation results. In: Proceedings of the XIth International Scientific and Technical Conference Computer Sciences and Information Technologies, CSIT 2016, Lviv, 6–10 September 2016, pp. 33–36 (2016)
Berezsky, O., Pitsun, O., Batryn, N., Berezska, K., Savka, N., Dolynyuk, T.: Image segmentation metric-based adaptive method. In: Proceedings of the 2018 IEEE Second International Conference on Data Stream Mining & Processing (DSMP), Lviv, 21–25 August 2018, pp. 54–557 (2018)
Berezsky, O.M., Pitsun, O.Y.: Computation of the minimum distance between non-convex polygons for segmentation quality evaluation. In: Proceedings of the XIIth International Scientific and Technical Conference Computer Sciences and Information Technologies, CSIT 2017, Lviv, 5–8 September 2017, pp. 183–186 (2017)
Berezsky, O.M., Pitsun, O.Y.: Evaluation methods of image segmentation quality. Radio Electron. Comput. Sci. Control 1, 41–61 (2018)
Berezsky, O., Zarichnyi, M.: Fréchet distance between weighted rooted trees. MatematychniStudii 48(2), 165–170 (2017)
Berezsky, O., Zarichnyi, M.: Gromov-Fréchet distance between curves. MatematychniStudii 50(1), 88–92 (2018)
Berezsky, O., Zarichnyi, M., Pitsun, O.: Development of a metric and the methods for quantitative estimation of the segmentation of biomedical images. East.-Eur. J. Enterp. Technol. 6(4), 4–11 (2017)
Bishop, C.J., Hakobyan, H.: A central set of dimension 2. Proc. Am. Math. Soc. 136(7), 2453–2461 (2008)
Buchin, K., Buchin, M., Wenk, C.: Computing the Fréchet distance between simple polygons. Comput. Geom. 41, 2–20 (2008)
Burago, D., Burago, Y., Ivanov, S.: A Course in Metric Geometry. Vol. 33 of Graduate Studies in Mathematics. American Mathematical Society, Providence, Rhode Island, June 2001
Camarena, J.G., Gregori, V., Morillas, S., Sapena, A.: Fast detection and removal of impulsive noise using peer groups and fuzzy metrics. J. Vis. Commun. Image Represent. 19, 20–29 (2008)
Chowdhury, S.: Metric and Topological Approaches to Network Data Analysis. Ph.D thesis, The Ohio State University (2019)
Colijn, C., Plazzotta, G.: A metric on phylogenetic tree shapes. Syst. Biol. 67(1), 113–126 (2018)
Cook IV, A.F., Driemel, A., Sherette, J., Wenk, C.: Computing the Fréchet distance between folded polygons. Comput. Geom. 50, 1–16 (2015)
Deza, M.M., Deza, E.: Encyclopedia of distances, pp. 1–583. Springer (2009)
Dubuisson, M.-P., Jain, A.K.: A modified hausdorff distance for object matching. In: Proceedings of the 12th International Conference on Pattern Recognition, Jerusalem, Israel, pp. 566–568 (1994)
Edwards, D.A.: The Structure of Superspace, Published in: Studies in Topology. Academic Press (1975)
Eiter, T., Mannila, H.: Computing discrete Fréchet distance. Technical Report CDTR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria (1994)
Hahn, H.: Sur quelques points du calcul fonctionnel. Rendiconti del Circolo Mathematico di Palermo 19, 1–74 (1908)
Fremlin, D.H.: Skeletons and central sets. Proc. London Math. Soc. 74(3), 701–720 (1997)
Gromov, M.: Groups of Polynomial growth and Expanding Maps. Publications mathematiques I.H.E.S., 53 (1981)
Huttenlocher, D.P., Klanderman, G.A., William, J.R.: Comparing images using the Hausdorff distance. IEEE Trans. Pattern Anal. Machine Intell. 15(9), 850–863 (1993)
Jayanthi, N., Indu, S.: Comparison of image matching techniques. Int. J. Latest Trends Eng. Technol. 7(3), 396–401 (2018)
Katukam, R.: Image comparison methods & tools: a review. In: 1st National Conference on, Emerging Trends in Information Technology [ETIT], 28th–29th December 2015, pp. 35–42 (2015)
Kwong, S., He, Q.H., Man, K.F., Tang, K.S., Chau, C.W.: Parallel genetic-based hybrid pattern matching algorithm for isolated word recognition. Int. J. Pattern Recogn. Artif. Intell. 12(5), 573–594 (1998)
Majhi, S., Vitter, J., Wenk, C.: Approximating Gromov-Hausdorff Distance in Euclidean Space. arXiv:1912.13008v1
Mémoli, F.: Gromov-Hausdorff distances in Euclidean spaces. In: 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, Anchorage, AK, USA, pp. 1–8. IEEE, June 2008
Mosig, A., Clausen, M.: Approximately matching polygonal curves with respect to the Fréchet distance. Comput. Geom. 30, 113–127 (2005)
Parizeau, M., Plamondon, R.: A comparative analysis of regional correlation, dynamic time warping, and skeletal tree matching for signature verification. IEEE Trans. Pattern Anal. Mach. Intell. 12(7), 710–717 (1990)
Rote, G.: Computing the Fréchet distance between piecewise smooth curves. Comput. Geom. 37, 162–174 (2007)
Revaud, J., Weinzaepfel, P., Harchaoui, Z., Schmid, C.: Deep convolutional matching. In: Computer Vision & Pattern Recognition, pp. 1164–1172 (2015)
Schlesinger, M.I., Vodolazskiy, E.V., Yakovenko, V.M.: Fréchet similarity of closed polygonal curves. Int. J. Comput. Geom. Appl. 26(1), 53–66 (2016)
Schmidt, J., Gröller, E., Bruckner, S.: VAICo: visual analysis for image comparison. IEEE Trans. Vis. Comput. Graph. 19(12), 2090–2099 (2013)
Smith, Z., Wan, Z.: Gromov-Hausdorff distances on p-metric spaces and ultrametric spaces. arXiv:1912.00564v3
Touli, E.F.: Fréchet-Like Distances between Two Merge Trees. arXiv:2004.10747
Tuzhilin, A.A.: Who Invented the Gromov-Hausdorff Distance? arXiv:1612.00728v1
Zarichnyi, I.: Gromov-Hausdorff Ultrametric. arXiv preprint math/0511437 (2005)
Zhou, Y., Chen, M., Webster, M.F.: Comparative evaluation of visualization and experimental results using image comparison metrics. In: Proceedings of IEEE Visualization 2002 Conference, Boston, USA, pp. 315–322 (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Berezsky, O., Zarichnyi, M. (2021). Metric Methods in Computer Vision and Pattern Recognition. In: Shakhovska, N., Medykovskyy, M.O. (eds) Advances in Intelligent Systems and Computing V. CSIT 2020. Advances in Intelligent Systems and Computing, vol 1293. Springer, Cham. https://doi.org/10.1007/978-3-030-63270-0_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-63270-0_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-63269-4
Online ISBN: 978-3-030-63270-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)