The Edit Distance for Reeb Graphs of Surfaces

详细信息    查看全文

• 作者：Barbara Di Fabio ; Claudia Landi
• 关键词：Shape similarity ; Graph edit distance ; Morse function ; Natural stratification ; 05C10 ; 68T10 ; 54C30
• 刊名：Discrete and Computational Geometry
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：55
• 期：2
• 页码：423-461
• 全文大小：1,378 KB
• 参考文献：1.Barra, V., Biasotti, S.: 3D shape retrieval using kernels on extended Reeb graphs. Pattern Recogn. 46(11), 2985–2999 (2013)CrossRef
  2.Bauer, U., Ge, X., Wang, Y.: Measuring distance between Reeb graphs. In: Proceedings of the Thirtieth Annual Symposium on Computational Geometry (New York, NY), SOCG’14, pp. 464–473. ACM (2014)
  3.Bauer, U., Munch, E., Wang, Y.: Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs. In: L. Arge & J. Pach (eds.) 31st International Symposium on Computational Geometry (SoCG 2015) (Dagstuhl, Germany), Leibniz International Proceedings in Informatics (LIPIcs), vol. 34, pp. 461–475. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern (2015)
  4.Biasotti, S., Marini, S., Spagnuolo, M., Falcidieno, B.: Sub-part correspondence by structural descriptors of 3D shapes. Comput.-Aided Des. 38(9), 1002–1019 (2006)CrossRef
  5.Bolsinov, A.V., Fomenko, A.T.: Integrable Hamiltonian Systems: Geometry, Topology, Classification. CRC Press, Boca Raton (2004) (Translated from the 1999 Russian original)
  6.Cagliari, F., Di Fabio, B., Landi, C.: The natural pseudo-distance as a quotient pseudo-metric, and applications. Forum Math. 27(3), 1729–1742 (2015)CrossRef MathSciNet
  7.Cerf, J.: La stratification naturelle des espaces de fonctions différentiables réelles et le théorème de la pseudo-isotopie. Publ. Math. Inst. Hautes Étud. Sci. 39, 5–173 (1970)
  8.Cerri, A., Di Fabio, B., Ferri, M., Frosini, P., Landi, C.: Betti numbers in multidimensional persistent homology are stable functions. Math. Methods Appl. Sci. 36(12), 1543–1557 (2013)CrossRef MathSciNet MATH
  9.Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discrete Comput. Geom. 37(1), 103–120 (2007)CrossRef MathSciNet MATH
  10.Cole-McLaughlin, K., Edelsbrunner, H., Harer, J., Natarajan, V., Pascucci, V.: Loops in Reeb graphs of 2-manifolds. Discrete Comput. Geom. 32, 231–244 (2004)CrossRef MathSciNet MATH
  11.Cornea, N.D., Silver, D., Min, P.: Curve-skeleton properties, applications, and algorithms. IEEE Trans. Vis. Comput. Gr. 13(3), 530–548 (2007)CrossRef
  12.Di Fabio, B., Landi, C.: Reeb graphs of curves are stable under function perturbations. Math. Methods Appl. Sci. 35(12), 1456–1471 (2012)CrossRef MathSciNet MATH
  13.Donatini, P., Frosini, P.: Natural pseudodistances between closed manifolds. Forum Math. 16(5), 695–715 (2004)CrossRef MathSciNet MATH
  14.Gao, X., Xiao, B., Tao, D., Li, X.: A survey of graph edit distance. Pattern Anal. Appl. 13(1), 113–129 (2010)CrossRef MathSciNet
  15.Hilaga, M., Shinagawa, Y., Kohmura, T., Kunii, T.L.: Topology matching for fully automatic similarity estimation of 3D shapes. In: Proceedings of SIGGRAPH 2001, ACM Computer Graphics, pp. 203–212. ACM Press, Los Angeles (2001)
  16.Hirsch, M.: Differential Topology. Springer, New York (1976)CrossRef MATH
  17.Kudryavtseva, E.A.: Reduction of Morse functions on surfaces to canonical form by smooth deformation. Regul. Chaotic Dyn. 4(3), 53–60 (1999)CrossRef MathSciNet MATH
  18.Kulinich, E.V.: On topologically equivalent Morse functions on surfaces. Methods Funct. Anal. Topol. 4, 59–64 (1998)MathSciNet MATH
  19.Masumoto, Y., Saeki, O.: A smooth function on a manifold with given Reeb graph. Kyushu J. Math. 65(1), 75–84 (2011)CrossRef MathSciNet MATH
  20.Milnor, J.: Lectures on the \(h\) -Cobordism Theorem. Notes by L. Siebenmann and J. Sondow. Princeton University Press, Princeton (1965)
  21.Pascucci, V., Scorzelli, G., Bremer, P.-T., Mascarenhas, A.: Robust on-line computation of Reeb graphs: simplicity and speed. ACM Trans. Graph. (2007). doi:10.​1145/​1276377.​1276449
  22.Reeb, G.: Sur les points singuliers d’une forme de Pfaff complétement intégrable ou d’une fonction numérique. C. R. Acad. Sci. 222, 847–849 (1946)
  23.Sergeraert, F.: Un théorème de fonctions implicites sur certains espaces de Fréchet et quelques applications. Ann. de I’Éc. Norm. 5, 599–660 (1972)
  24.Sharko, V.V.: Smooth and topological equivalence of functions on surfaces. Ukr. Math. J. 55(5), 832–846 (2003)CrossRef MathSciNet
  25.Sharko, V.V.: About Kronrod-Reeb graph of a function on a manifold. Methods Funct. Anal. Topol. 12(4), 389–396 (2006)MathSciNet MATH
  26.Shinagawa, Y., Kunii, T.L.: Constructing a Reeb graph automatically from cross sections. IEEE Comput. Graph. Appl. 11(6), 44–51 (1991)CrossRef
  27.Shinagawa, Y., Kunii, T.L., Kergosien, Y.L.: Surface coding based on Morse theory. IEEE Comput. Graph. Appl. 11(5), 66–78 (1991)CrossRef
  28.Tangelder, J.W., Veltkamp, R.C.: A survey of content based 3D shape retrieval methods. Multimedia Tools Appl. 39(3), 441–471 (2008)CrossRef
  
• 作者单位：Barbara Di Fabio (1) (2)
  Claudia Landi (1) (2)
  
  1. Dipartimento di Scienze e Metodi dell’Ingegneria, Università di Modena e Reggio Emilia, Via Amendola 2, Pad, 42122, Morselli, Reggio Emilia, Italy
  2. ARCES, Università di Bologna, Via Toffano 2/2, 40125, Bologna, Italy
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1432-0444

文摘

Reeb graphs are structural descriptors that capture shape properties of a topological space from the perspective of a chosen function. In this work, we define a combinatorial distance for Reeb graphs of orientable surfaces in terms of the cost necessary to transform one graph into another by edit operations. The main contributions of this paper are the stability property and the optimality of this edit distance. More precisely, the stability result states that changes in the Reeb graphs, measured by the edit distance, are as small as changes in the functions, measured by the maximum norm. The optimality result states that the edit distance discriminates Reeb graphs better than any other distance for Reeb graphs of surfaces satisfying the stability property. Keywords Shape similarity Graph edit distance Morse function Natural stratification