Vitaliy Kurlin
A one-dimensional Homologically Persistent Skeleton of an unstructured point cloud in any metric space
Kurlin, Vitaliy
Authors
Abstract
Real data are often given as a noisy unstructured point cloud, which is hard to visualize. The important problem is to represent topological structures hidden in a cloud by using skeletons with cycles. All past skeletonization methods require extra parameters such as a scale or a noise bound. We define a homologically persistent skeleton, which depends only on a cloud of points and contains optimal subgraphs representing 1-dimensional cycles in the cloud across all scales. The full skeleton is a universal structure encoding topological persistence of cycles directly on the cloud. Hence a 1-dimensional shape of a cloud can be now easily predicted by visualizing our skeleton instead of guessing a scale for the original unstructured cloud. We derive more subgraphs to reconstruct provably close approximations to an unknown graph given only by a noisy sample in any metric space. For a cloud of n points in the plane, the full skeleton and all its important subgraphs can be computed in time O(n log n).
Citation
Kurlin, V. (2015). A one-dimensional Homologically Persistent Skeleton of an unstructured point cloud in any metric space. Computer Graphics Forum, 34(5), 253-262. https://doi.org/10.1111/cgf.12713
Journal Article Type | Article |
---|---|
Publication Date | Aug 10, 2015 |
Deposit Date | Sep 18, 2015 |
Publicly Available Date | Aug 10, 2016 |
Journal | Computer Graphics Forum |
Print ISSN | 0167-7055 |
Electronic ISSN | 1467-8659 |
Publisher | Wiley |
Peer Reviewed | Peer Reviewed |
Volume | 34 |
Issue | 5 |
Pages | 253-262 |
DOI | https://doi.org/10.1111/cgf.12713 |
Keywords | Categories and Subject Descriptors (according to ACM CCS), I.5.1 [Pattern Recognition]: Models—Structural. |
Public URL | https://durham-repository.worktribe.com/output/1399753 |
Files
Accepted Journal Article
(3.6 Mb)
PDF
Copyright Statement
This is the accepted version of the following article: Kurlin, V. (2015), A one-dimensional homologically persistent skeleton of an unstructured point cloud in any metric space. Computer Graphics Forum, 34(5): 253-262, which has been published in final form at http://dx.doi.org/10.1111/cgf.12713. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.
You might also like
A fast persistence-based segmentation of noisy 2D clouds with provable guarantees
(2015)
Journal Article
Reconstructing persistent graph structures from noisy images
(2013)
Journal Article
Computing braid groups of graphs with applications to robot motion planning
(2012)
Journal Article
Recognizing trace graphs of closed braids
(2010)
Journal Article