Top

Published in:

2016 | OriginalPaper | Chapter

9. Homological Shape Analysis Through Discrete Morse Theory

Authors : Leila De Floriani, Ulderico Fugacci, Federico Iuricich

Published in: Perspectives in Shape Analysis

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Homology and persistent homology are fundamental tools for shape analysis and understanding that recently gathered a lot of interest, in particular for analyzing multidimensional data. In this context, discrete Morse theory, a combinatorial counterpart of smooth Morse theory, provides an excellent basis for reducing computational complexity in homology detection. A discrete Morse complex, computed over a given complex discretizing a shape, drastically reduces the number of cells of the latter while maintaining the same homology. Here, we consider the problem of shape analysis through discrete Morse theory, and we review and analyze algorithms for computing homology and persistent homology based on such theory.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Shape Compaction

next chapter Sparse Models for Intrinsic Shape Correspondence

Agoston, M.K.: Computer Graphics and Geometric Modeling: Mathematics. Springer, London (2005)MATH

Alexandroff, P., Hopf, H.: Topologie i, vol. 1035. Springer, Berlin (1935)MATHCrossRef

Artin, M.: Algebra. Prentice Hall, Englewood Cliffs (1991)MATH

Bendich, P., Edelsbrunner, H., Kerber, M.: Computing robustness and persistence for images. IEEE Trans. Vis. Comput. Graph. 16 (6), 1251–1260 (2010)CrossRef

Benedetti, B., Lutz, F.H.: Random discrete Morse theory and a new library of triangulations. Exp. Math. 23 (1), 66–94 (2014)MathSciNetMATHCrossRef

Boissonnat, J.D., Dey, T.K., Maria, C.: The compressed annotation matrix: an efficient data structure for computing persistent cohomology. In: Algorithms–ESA 2013, Sophia Antipolis, pp. 695–706. Springer (2013)

Boltcheva, D., Canino, D., Merino Aceituno, S., Léon, J.C., De Floriani, L., Hétroy, F.: An iterative algorithm for homology computation on simplicial shapes. Comput. Aided Des. 43 (11), 1457–1467 (2011)CrossRef

Bremer, P.T., Hamann, B., Edelsbrunner, H., Pascucci, V.: A topological hierarchy for functions on triangulated surfaces. IEEE Trans. Vis. Comput. Graph. 10 (4), 385–396 (2004)CrossRef

Canino, D., De Floriani, L., Weiss, K.: IA*: an adjacency-based representation for non-manifold simplicial shapes in arbitrary dimensions. Comput. Graph. 35 (3), 747–753 (2011)CrossRef

10.

Carlsson, G., Ishkhanov, T., De Silva, V., Zomorodian, A.J.: On the local behavior of spaces of natural images. Int. J. Comput. Vis. 76 (1), 1–12 (2008)CrossRef

11.

Cazals, F., Chazal, F., Lewiner, T.: Molecular shape analysis based upon the Morse-Smale complex and the Connolly function. In: Proceedings of 9th Annual Symposium on Computational Geometry, pp. 351–360. ACM Press, New York (2003)

12.

Cerri, A., Ferri, M., Giorgi, D.: Retrieval of trademark images by means of size functions. Graph. Models 68 (5), 451–471 (2006)CrossRef

13.

Chung, M.K., Bubenik, P., Kim, P.T.: Persistence diagrams of cortical surface data. In: Information Processing in Medical Imaging, pp. 386–397. Springer, Berlin/New York (2009)

14.

Čomić, L., De Floriani, L., Iuricich, F.: Simplification operators on a dimension-independent graph-based representation of Morse complexes. In: Hendriks, C.L.L., Borgefors, G., Strand R. (eds.) ISMM. Lecture Notes in Computer Science, vol. 7883, pp. 13–24. Springer, Berlin/New York (2013)

15.

Čomić, L., De Floriani, L., Iuricich, F., Fugacci, U.: Topological modifications and hierarchical representation of cell complexes in arbitrary dimensions. Comput. Vis. Image Underst. 121, 2–12 (2014)CrossRef

16.

Connolly, M.L.: Measurement of protein surface shape by solid angles. J. Mol. Graph. 4 (1), 3–6 (1986)MathSciNetCrossRef

17.

De Floriani, L., Hui, A.: Data structures for simplicial complexes: an analysis and a comparison. In: Desbrun, M., Pottmann, H. (eds.) Proceedings of 3rd Eurographics Symposium on Geometry Processing. ACM International Conference on Proceeding Series, vol. 255, pp. 119–128. Eurographics Association, Aire-la-Ville (2005)

18.

Dequeant, M.L., Ahnert, S., Edelsbrunner, H., Fink, T.M., Glynn, E.F., Hattem, G., Kudlicki, A., Mileyko, Y., Morton, J., Mushegian, A.R., et al.: Comparison of pattern detection methods in microarray time series of the segmentation clock. PLoS One 3 (8), e2856 (2008)CrossRef

19.

Dey, T.K., Fan, F., Wang, Y.: Computing topological persistence for simplicial maps. arXiv preprint arXiv:1208.5018 (2012)

20.

Dey, T.K., Hirani, A.N., Krishnamoorthy, B., Smith, G.: Edge contractions and simplicial homology. arXiv preprint arXiv:1304.0664 (2013)

21.

Dłotko, P., Kaczynski, T., Mrozek, M., Wanner, T.: Coreduction homology algorithm for regular cw-complexes. Discret. Comput. Geom. 46 (2), 361–388 (2011)MathSciNetMATHCrossRef

22.

Dłotko, P., Wagner, H.: Simplification of complexes of persistent homology computations. Homol. Homotopy Appl. 16 (1), 49–63 (2014)MathSciNetMATHCrossRef

23.

Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer, Berlin (1987)MATHCrossRef

24.

Edelsbrunner, H., Harer, J.: Persistent homology-a survey. Contemp. Math. 453, 257–282 (2008)MathSciNetMATHCrossRef

25.

Edelsbrunner, H., Letscher, D., Zomorodian, A.J.: Topological persistence and simplification. Discret. Comput. Geom. 28 (4), 511–533 (2002)MathSciNetMATHCrossRef

26.

Fellegara, R., Iuricich, F., De Floriani, L., Weiss, K.: Efficient computation and simplification of discrete Morse decompositions on triangulated terrains. In: 22th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2014, Dallas, 4–7 Nov 2014 (2014)

27.

Forman, R.: Combinatorial vector fields and dynamical systems. Mathematische Zeitschrift 228, 629–681 (1998)MathSciNetMATHCrossRef

28.

Forman, R.: Morse theory for cell complexes. Adv. Math. 134, 90–145 (1998)MathSciNetMATHCrossRef

29.

Fugacci, U., Iuricich, F., De Floriani, L.: Efficient computation of simplicial homology through acyclic matching. In: Proceedings of 5th International Workshop on Computational Topology in Image Context (CTIC 2014), Timisoara (2014)

30.

Ghrist, R.: Barcodes: the persistent topology of data. Bull. Am. Math. Soc. 45 (1), 61–75 (2008)MathSciNetMATHCrossRef

31.

Günther, D., Reininghaus, J., Wagner, H., Hotz, I.: Efficient computation of 3D Morse-Smale complexes and persistent homology using discrete Morse theory. Vis. Comput. 28 (10), 959–969 (2012)CrossRef

32.

Gyulassy, A., Bremer, P.T., Pascucci, V.: Computing Morse-Smale complexes with accurate geometry. IEEE Trans. Vis. Comput. Graph. 18 (12), 2014–2022 (2012). doi:10.1109/TVCG.2012.209CrossRef

33.

Gyulassy, A., Bremer, P.T., Hamann, B., Pascucci, V.: A practical approach to Morse-Smale complex computation: scalability and generality. IEEE Trans. Vis. Comput. Graph. 14 (6), 1619–1626 (2008)CrossRef

34.

Gyulassy, A., Bremer, P.T., Hamann, B., Pascucci, V.: Practical considerations in Morse-Smale complex computation. In: Pascucci, V., Tricoche, X., Hagen, H., Tierny, J. (eds.) Topological Methods in Data Analysis and Visualization: Theory, Algorithms, and Applications, Mathematics and Visualization, pp. 67–78. Springer, Heidelberg (2011)CrossRef

35.

Gyulassy, A., Kotava, N., Kim, M., Hansen, C., Hagen, H., Pascucci, V.: Direct feature visualization using Morse-Smale complexes. IEEE Trans. Vis. Comput. Graph. 18 (9), 1549–1562 (2012)CrossRef

36.

Harker, S., Mischaikow, K., Mrozek, M., Nanda, V.: Discrete Morse theoretic algorithms for computing homology of complexes and maps. Found. Comput. Math. 14 (1), 151–184 (2014)MathSciNetMATHCrossRef

37.

Harker, S., Mischaikow, K., Mrozek, M., Nanda, V., Wagner, H., Juda, M., Dłotko, P.: The efficiency of a homology algorithm based on discrete Morse theory and coreductions. In: Proceedings of 3rd International Workshop on Computational Topology in Image Context (CTIC 2010), Cádiz. Image A, vol. 1, pp. 41–47 (2010)

38.

Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge/New York (2002)MATH

39.

King, H., Knudson, K., Mramor, N.: Generating discrete Morse functions from point data. Exp. Math. 14 (4), 435–444 (2005)MathSciNetMATHCrossRef

40.

Lewiner, T., Lopes, H., Tavares, G.: Optimal discrete Morse functions for 2-manifolds. Comput. Geom. 26 (3), 221–233 (2003)MathSciNetMATHCrossRef

41.

Lewis, R.H., Zomorodian, A.J.: Multicore homology via Mayer Vietoris. arXiv preprint arXiv:1407.2275 (2014)

42.

Lundell, A.T., Weingram, S.: The topology of CW complexes. Van Nostrand Reinhold Company, New York (1969)MATHCrossRef

43.

Martin, S., Thompson, A., Coutsias, E.A., Watson, J.P.: Topology of cyclo-octane energy landscape. J. Chem. Phys. 132 (23), 234115 (2010). doi:10.1063/1.3445267CrossRef

44.

Milnor, J.: Morse Theory. Princeton University Press, Princeton (1963)MATHCrossRef

45.

Mischaikow, K., Nanda, V.: Morse theory for filtrations and efficient computation of persistent homology. Discret. Comput. Geom. 50 (2), 330–353 (2013)MathSciNetMATHCrossRef

46.

Mrozek, M., Batko, B.: Coreduction homology algorithm. Discret. Comput. Geom. 41 (1), 96–118 (2009)MathSciNetMATHCrossRef

47.

Mrozek, M., Wanner, T.: Coreduction homology algorithm for inclusions and persistent homology. Comput. Math. Appl. 60 (10), 2812–2833 (2010)MathSciNetMATHCrossRef

48.

Munkres, J.: Elements of Algebraic Topology. Advanced Book Classics. Perseus Books, New York (1984)MATH

49.

Nanda, V.: The Perseus software project for rapid computation of persistent homology. http://www.math.rutgers.edu/~vidit/perseus/index.html

50.

Rieck, B., Leitte, H.: Structural analysis of multivariate point clouds using simplicial chains. Comput. Graph. Forum 33 (8), 28–37 (2014). doi:10.1111/cgf.12398CrossRef

51.

Rieck, B., Mara, H., Leitte, H.: Multivariate data analysis using persistence-based filtering and topological signatures. IEEE Trans. Vis. Comput. Graph. 18 (12), 2382–2391 (2012). doi:10.1109/TVCG.2012.248CrossRef

52.

Robins, V., Wood, P.J., Sheppard, A.P.: Theory and algorithms for constructing discrete Morse complexes from grayscale digital images. IEEE Trans. Pattern Anal. Mach. Intell. 33 (8), 1646–1658 (2011)CrossRef

53.

Rosenfeld, A., Kak, A.C.: Digital Picture Processing. Academic Press, London (1982)MATH

54.

Shivashankar, N., Maadasamy, S., Natarajan, V.: Parallel computation of 2D Morse-Smale complexes. IEEE Trans. Vis. Comput. Graph. 18 (10), 1757–1770 (2012)CrossRef

55.

Shivashankar, N., Natarajan, V.: Parallel computation of 3D Morse-Smale complexes. Comput. Graph. Forum 31 (3), 965–974 (2012)CrossRef

56.

de Silva, V., Ghrist, R.: Coverage in sensor networks via persistent homology. Algebr. Geom. Topol. 7, 339–358 (2007). doi:10.2140/agt.2007.7.339MathSciNetMATHCrossRef

57.

Wang, Y., Agarwal, P.K., Brown, P.H.E., Rudolph, J.: Coarse and reliable geometric alignment for protein docking. In: Proceedings of Pacific Symposium on Biocomputing, Hawaii, vol. 10, pp. 65–75 (2005)

58.

Weiss, K., De Floriani, L., Fellegara, R., Velloso, M.: The PR-star octree: a spatio-topological data structure for tetrahedral meshes. In: GIS, Chicago, pp. 92–101 (2011)

59.

Weiss, K., Iuricich, F., Fellegara, R., De Floriani, L.: A primal/dual representation for discrete Morse complexes on tetrahedral meshes. Comput. Graph. Forum 32 (3), 361–370 (2013)CrossRef

60.

Van de Weygaert, R., Vegter, G., Edelsbrunner, H., Jones, B.J., Pranav, P., Park, C., Hellwing, W.A., Eldering, B., Kruithof, N., Bos, E., et al.: Alpha, Betti and the megaparsec universe: on the topology of the cosmic web. In: Transactions on Computational Science XIV, pp. 60–101. Springer, Berlin/New York (2011). http://arxiv.org/abs/1306.3640

61.

Zomorodian, A.J.: Topology for Computing, vol. 16. Cambridge University Press, Cambridge/New York (2005)MATHCrossRef

Title: Homological Shape Analysis Through Discrete Morse Theory
Authors: Leila De Floriani
Ulderico Fugacci
Federico Iuricich
Publisher: Springer International Publishing
Book: Perspectives in Shape Analysis
Print ISBN: 978-3-319-24724-3

Electronic ISBN: 978-3-319-24726-7

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-24726-7_9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner