Memory-Efficient Computation of Persistent Homology for 3D Images Using Discrete Morse Theory
Memory-Efficient Computation of Persistent Homology for 3D Images Using Discrete Morse Theory
复制标题
使用离散莫尔斯理论对 3D 图像持久同调进行内存高效计算
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
H. Wagner
中科院分区：
文献类型：
--
作者：
D. Günther;Jan Reininghaus;I. Hotz;H. Wagner
我们提出了一种计算三维灰度图像持久同源性的高效内存方法。其基本思想是计算诱导的莫尔斯-小复合体的持续时间。由于在实践中这个复合体比输入数据要小得多，因此后续计算所需的内存要少得多。基于离散莫尔斯理论，提出了一种有效提取莫尔斯-小复合体的新算法。因此，该算法是最优的，计算复杂度为O（n2）。然后，通过应用具有良好实际运行时间的现有算法，使用morse - small复合体计算持久性。我们证明了我们的方法允许在商品硬件上计算大数据的持久同源性。
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.