Memory-Efficient Computation of Persistent Homology for 3D Images using Discrete Morse Theory
2011 (English)Conference paper (Refereed)
We propose a memory-efficient method that computes persistent homology for 3D gray-scale images. The basic idea is to compute the persistence of the induced Morse-Smale complex. Since in practice this complex is much smaller than the input data, significantly less memory is required for the subsequent computations. We propose a novel algorithm that efficiently extracts the Morse-Smale complex based on algorithms from discrete Morse theory. The proposed algorithm is thereby optimal with a computational complexity of O(n2). 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.
Place, publisher, year, edition, pages
2011. 25-32 p.
computational topology, algorithm
Computer Vision and Robotics (Autonomous Systems)
IdentifiersURN: urn:nbn:se:liu:diva-127677DOI: 10.1109/SIBGRAPI.2011.24ISBN: 978-1-4577-1674-4OAI: oai:DiVA.org:liu-127677DiVA: diva2:926368
2011 24th SIBGRAPI Conference on Graphics, Patterns and Images. 28-31 Aug. 2011 Maceio, Alagoas