Skeletonisation algorithms with theoretical guarantees for unorganised point clouds with high levels of noise



Smith, P and Kurlin, V ORCID: 0000-0001-5328-5351
(2021) Skeletonisation algorithms with theoretical guarantees for unorganised point clouds with high levels of noise. PATTERN RECOGNITION, 115. p. 107902.

[img] Text
1901.03319v1.pdf - Submitted version

Download (4MB)
[img] Text
skeletonization_algorithms_final.pdf - Author Accepted Manuscript

Download (10MB) | Preview

Abstract

Data Science aims to extract meaningful knowledge from unorganised data. Real datasets usually come in the form of a cloud of points with only pairwise distances. Numerous applications require to visualise an overall shape of a noisy cloud of points sampled from a non-linear object that is more complicated than a union of disjoint clusters. The skeletonisation problem in its hardest form is to find a 1-dimensional skeleton that correctly represents a shape of the cloud. This paper compares several algorithms that solve the above skeletonisation problem for any point cloud and guarantee a successful reconstruction. For example, given a highly noisy point sample of an unknown underlying graph, a reconstructed skeleton should be geometrically close and homotopy equivalent to (has the same number of independent cycles as) the underlying graph. One of these algorithm produces a Homologically Persistent Skeleton (HoPeS) for any cloud without extra parameters. This universal skeleton contains sub-graphs that provably represent the 1-dimensional shape of the cloud at any scale. Other subgraphs of HoPeS reconstruct an unknown graph from its noisy point sample with a correct homotopy type and within a small offset of the sample. The extensive experiments on synthetic and real data reveal for the first time the maximum level of noise that allows successful graph reconstructions.

Item Type: Article
Additional Information: This paper has been published in the journal Pattern Recognition
Uncontrolled Keywords: Data skeletonisation, Noisy point sample, Persistent homology
Depositing User: Symplectic Admin
Date Deposited: 24 Jan 2019 10:08
Last Modified: 18 Jan 2024 11:34
DOI: 10.1016/j.patcog.2021.107902
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3031137