Graph skeletonization of high-dimensional point cloud data via topological method
Graph skeletonization of high-dimensional point cloud data via topological method
复制标题
DOI：
--
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Lucas Magee;Yusu Wang
中科院分区：
文献类型：
--
作者：
Lucas Magee;Yusu Wang
几何图形构成了数据背后隐藏结构的一个重要家族。本文提出了一种高效鲁棒的算法来推断高维点云数据集（PCD）的图骨架。以前，有很多工作是从低维密度场或相对干净的高维PCD中恢复隐藏图。我们提出的方法建立在最近的工作线上，即使用基于持久性引导的离散莫尔斯（DM）理论的方法从低维三角测量上定义的密度场重建几何图形。特别是，我们首先从密度函数的角度对这种基于dm的算法进行了非常简单的推广，并将其推广到一般过滤的角度。在理论方面，我们表明广义算法的输出包含一个所谓的字典最优持久循环基，而不是输入过滤，证明输出确实是有意义的。在算法方面，这种泛化使我们能够结合稀疏加权Rips过滤来开发一种新的针对噪声点云数据的图重构算法。该算法对背景噪声和输入点的非均匀分布具有较强的鲁棒性，并提供了各种实验结果来证明该算法的有效性。
Geometric graphs form an important family of hidden structures behind data. In this paper, we develop an efficient and robust algorithm to infer a graph skeleton of a high-dimensional point cloud dataset (PCD). Previously, there has been much work to recover a hidden graph from a low-dimensional density field, or from a relatively clean high-dimensional PCD. Our proposed approach builds upon the recent line of work on using a persistence-guided discrete Morse (DM) theory based approach to reconstruct a geometric graph from a density field defined over a low-dimensional triangulation. In particular, we first give a very simple generalization of this DM-based algorithm from a density-function perspective to a general filtration perspective. On the theoretical front, we show that the output of the generalized algorithm contains a so-called lexicographic-optimal persistent cycle basis w.r.t the input filtration, justifying that the output is indeed meaningful. On the algorithmic front, the generalization allows us to combine sparsified weighted Rips filtration to develop a new graph reconstruction algorithm for noisy point cloud data. The new algorithm is robust to background noise and non-uniform distribution of input points, and we provide various experimental results to show its effectiveness.