Abstract
We propose an efficient algorithm that computes the Morse–Smale complex for 3D gray-scale images. This complex allows for an efficient computation of persistent homology since it is, in general, much smaller than the input data but still contains all necessary information. Our method improves a recently proposed algorithm to extract the Morse–Smale complex in terms of memory consumption and running time. It also allows for a parallel computation of the complex. The computational complexity of the Morse–Smale complex extraction solely depends on the topological complexity of the input data. The persistence is then computed using the Morse–Smale complex by applying an existing algorithm with a good practical running time. We demonstrate that our method allows for the computation of persistent homology for large data on commodity hardware.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
The Institute of Computer Graphics and Algorithms. http://www.cg.tuwien.ac.at/research/vis/datasets/
Volvis: Voxel Data Repository (2010). http://www.volvis.org/
Bauer, U., Lange, C., Wardetzky, M.: Optimal topological simplification of discrete functions on surfaces. Discrete & Computational Geometry 47(2), 1–31
Bendich, P., Edelsbrunner, H., Kerber, M.: Computing robustness and persistence for images. Proc. - IEEE Conf. Inf. Vis. 16, 1251–1260 (2010)
Chari, M.K.: On discrete Morse functions and combinatorial decompositions. Discrete Math. 217(1–3), 101–113 (2000)
Chen, C., Kerber, M.: An output-sensitive algorithm for persistent homology. In: Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG ’11), pp. 207–216. ACM, New York (2011)
Chen, C., Kerber, M.: Persistent homology computation with a twist. In: 27th European Workshop on Comp. Geometry (EuroCG 2011) (2011)
Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discrete Comput. Geom. 37, 103–120 (2007)
Edelsbrunner, H., Harer, J.: Computational Topology. An Introduction. American Mathematical Society (2010)
Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28(4), 511–533 (2002)
Forman, R.: Morse theory for cell complexes. Adv. Math. 134, 90–145 (1998)
Forman, R.: A user’s guide to discrete Morse theory. In: Seminaire Lotharingien de Combinatoire, vol. B48c, pp. 1–35 (2002)
Günther, D., Reininghaus, J., Prohaska, S., Weinkauf, T., Hege, H.C.: Efficient computation of a hierarchy of discrete 3d gradient vector fields. In: Peikert, R., Hauser, H., Carr, H., Fuchs, R. (eds.) Topological Methods in Data Analysis and Visualization. II. Mathematics and Visualization (TopoInVis 2011), Zürich, Switzerland, April 4–6, pp. 15–30. Springer, Berlin (2012)
Günther, D., Reininghaus, J., Wagner, H., Hotz, I.: Memory efficient computation of persistent homology for 3D image data using discrete Morse theory. In: Lewiner, T., Torres, R. (eds.) Proceedings of Conference on Graphics, Patterns and Images (SIBGRAPI), Maceió, Los Alamitos, vol. 24, pp. 25–32. IEEE Press, New York (2011)
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, 1619–1626 (2008)
Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)
Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology. Applied Math. Sciences, vol. 157. Springer, Berlin (2004)
Lewiner, T.: Geometric discrete Morse complexes. Ph.D. thesis, Dept. of Mathematics, PUC-Rio (2005)
Lewiner, T., Lopes, H., Tavares, G.: Optimal discrete Morse functions for 2-manifolds. Comput. Geom. 26(3), 221–233 (2003)
Milnor, J.: Topology from the Differentiable Viewpoint. University of Virginia Press, Charlottesville (1965)
Milosavljević, N., Morozov, D., Skraba, P.: Zigzag persistent homology in matrix multiplication time. In: Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG ’11), pp. 216–225. ACM, New York (2011)
Morozov, D.: Persistence algorithm takes cubic time in the worst case. In: BioGeometry News. Duke Computer Science, Durhmam (2005)
Mrozek, M., Wanner, T.: Coreduction homology algorithm for inclusions and persistent homology. Comput. Math. Appl. 60, 2812–2833 (2010)
Reininghaus, J., Günther, D., Hotz, I., Prohaska, S., Hege, H.C., TADD: A computational framework for data analysis using discrete Morse theory. In: Mathematical Software (ICMS 2010), pp. 198–208. Springer, Berlin (2010)
Robins, V., Wood, P., Sheppard, A.: Theory and algorithms for constructing discrete Morse complexes from grayscale digital images. IEEE Trans. Pattern Anal. Mach. Intell. 33(8), 1646–1658 (2011)
Röttger, S.: http://www9.informatik.uni-erlangen.de/External/vollib/
Wagner, H., Chen, C., Vucini, E.: Efficient computation of persistent homology for cubical data. In: Peikert, R., Hauser, H., Carr, H., Fuchs, R. (eds.) Topological Methods in Data Analysis and Visualization. II. Mathematics and Visualization (TopoInVis 2011), Zürich, Switzerland, April 4–6, pp. 91–108. Springer, Berlin (2012)
Acknowledgements
This work was supported by the MPI of Biochemistry, the MPI for Informatics, the DFG Emmy-Noether research program, and Foundation for Polish Science Geometry and Topology in Physical Models program. We thank Daniel Baum for providing the molecule data set. We also thank Herbert Edelsbrunner and Chao Chen for many fruitful discussions.
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
Let Ω=[−2,2]3. The function g:Ω→ℝ is given by
Rights and permissions
About this article
Cite this article
Günther, D., Reininghaus, J., Wagner, H. et al. Efficient computation of 3D Morse–Smale complexes and persistent homology using discrete Morse theory. Vis Comput 28, 959–969 (2012). https://doi.org/10.1007/s00371-012-0726-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-012-0726-8