×

zbMATH — the first resource for mathematics

Natural pseudo-distance and optimal matching between reduced size functions. (English) Zbl 1198.68224
Summary: This paper studies the properties of a new lower bound for the natural pseudo-distance. The natural pseudo-distance is a dissimilarity measure between shapes, where a shape is viewed as a topological space endowed with a real-valued continuous function. Measuring dissimilarity amounts to minimizing the change in the functions due to the application of homeomorphisms between topological spaces, with respect to the \(L _{\infty }\)-norm. In order to obtain the lower bound, a suitable metric between size functions, called matching distance, is introduced. It compares size functions by solving an optimal matching problem between countable point sets. The matching distance is shown to be resistant to perturbations, implying that it is always smaller than the natural pseudo-distance. We also prove that the lower bound so obtained is sharp and cannot be improved by any other distance between size functions.

MSC:
68T10 Pattern recognition, speech recognition
58C05 Real-valued functions on manifolds
49Q10 Optimization of shapes other than minimal surfaces
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Biasotti, S., De Floriani, L., Falcidieno, B., Frosini, P., Giorgi, D., Landi, C., Papaleo, L., Spagnuolo, M.: Describing shapes by geometrical-topological properties of real functions. ACM Comput. Surv. 40(4) (2008, in press)
[2] Brucale, A., d’Amico, M., Ferri, M., Gualandri, L., Lovato, A.: Size functions for image retrieval: a demonstrator on randomly generated curves. In: Lew, M., Sebe, N., Eakins, J. (eds.) Proc. CIVR02, London. Lecture Notes in Computer Science, vol. 2383, pp. 235–244. Springer, Berlin (2002) · Zbl 1015.68784
[3] Cagliari, F., Fabio, B.D., Ferri, M.: One-dimensional reduction of multidimensional persistent homology (2007). arXiv:math/0702713v1 · Zbl 1214.68424
[4] Cerri, A., Ferri, M., Giorgi, D.: Retrieval of trademark images by means of size functions. Graph. Models 68, 451–471 (2006) · Zbl 05140239 · doi:10.1016/j.gmod.2006.07.001
[5] Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discrete Comput. Geom. 37, 103–120 (2007) · Zbl 1117.54027 · doi:10.1007/s00454-006-1276-5
[6] d’Amico, M.: A new optimal algorithm for computing size function of shapes. In: CVPRIP Algorithms III, Proceedings International Conference on Computer Vision, Pattern Recognition and Image Processing, pp. 107–110 (2000)
[7] Dibos, F., Frosini, P., Pasquignon, D.: The use of size functions for comparison of shapes through differential invariants. J. Math. Imaging Vis. 21, 107–118 (2004) · doi:10.1023/B:JMIV.0000035177.68567.3b
[8] Donatini, P., Frosini, P.: Lower bounds for natural pseudodistances via size functions. Arch. Inequal. Appl. 2, 1–12 (2004) · Zbl 1067.58008
[9] Donatini, P., Frosini, P.: Natural pseudodistances between closed manifolds. Forum Math. 16, 695–715 (2004) · Zbl 1085.58009 · doi:10.1515/form.2004.032
[10] Donatini, P., Frosini, P.: Natural pseudodistances between closed surfaces. J. Eur. Math. Soc. 9, 231–253 (2007) · Zbl 1125.58006
[11] Donatini, P., Frosini, P.: Natural pseudodistances between closed curves. Forum Math. (to appear) · Zbl 1125.58006
[12] Donatini, P., Frosini, P., Landi, C.: Deformation energy for size functions. In: Hancock, E.R., Pelillo, M. (eds.) Proceedings Second International Workshop EMMCVPR’99. Lecture Notes in Computer Science, vol. 1654, pp. 44–53. Springer, Berlin (1999)
[13] Efrat, A., Itai, A., Katz, M.: Geometry helps in bottleneck matching and related problems. Algorithmica 31, 1–28 (2001) · Zbl 0980.68101 · doi:10.1007/s00453-001-0016-8
[14] Frosini, P.: Connections between size functions and critical points. Math. Meth. Appl. Sci. 19, 555–596 (1996) · Zbl 0857.55005 · doi:10.1002/(SICI)1099-1476(19960510)19:7<555::AID-MMA787>3.0.CO;2-X
[15] Frosini, P., Landi, C.: New pseudodistances for the size function space. In: Melter, R.A., Wu, A.Y., Latecki, L.J. (eds.) Vision Geometry VI. Proc. SPIE, vol. 3168, pp. 52–60 (1997)
[16] Frosini, P., Landi, C.: Size functions and morphological transformations. Acta Appl. Math. 49, 85–104 (1997) · Zbl 0883.68133 · doi:10.1023/A:1005857402634
[17] Frosini, P., Landi, C.: Size theory as a topological tool for computer vision. Pattern Recogn. Image Anal. 9, 596–603 (1999)
[18] Frosini, P., Landi, C.: Size functions and formal series. Appl. Algebra Eng. Commun. Comput. 12, 327–349 (2001) · Zbl 0974.68229 · doi:10.1007/s002000100078
[19] Frosini, P., Landi, C.: Reparametrization invariant norms. Trans. Am. Math. Soc. 361, 407–452 (2009) · Zbl 1172.46012 · doi:10.1090/S0002-9947-08-04581-9
[20] Frosini, P., Mulazzani, M.: Size homotopy groups for computation of natural size distances. Bull. Belg. Math. Soc. 6, 455–464 (1999) · Zbl 0937.55010
[21] Frosini, P., Pittore, M.: New methods for reducing size graphs. Int. J. Comput. Math. 70, 505–517 (1999) · Zbl 0916.68111 · doi:10.1080/00207169908804771
[22] Garfinkel, R., Rao, M.: The bottleneck transportation problem. Nav. Res. Logist. Q. 18, 465–472 (1971) · Zbl 0262.90040 · doi:10.1002/nav.3800180404
[23] Handouyaya, M., Ziou, D., Wang, S.: Sign language recognition using moment-based size functions. In: Vision Interface 99, Trois-Rivières (1999)
[24] Hirsch, M.W.: Differential Topology. Springer, Berlin (1976) · Zbl 0356.57001
[25] Kuratowski, K., Mostowski, A.: Set Theory. North-Holland, Amsterdam (1968) · Zbl 0165.01701
[26] Latecki, L.J., Melter, R., Gross, A. (eds.): Special issue: shape representation and similarity for image databases. Pattern Recogn. 35, 1–297 (2002) · Zbl 0988.00035
[27] Veltkamp, R., Hagedoorn, M.: State-of-the-art in shape matching. In: Lew, M. (ed.) Principles of Visual Information Retrieval, pp. 87–119. Springer, Berlin (2001)
[28] Willard, S.: General Topology. Addison-Wesley, Reading (1970) · Zbl 0205.26601
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.