Skeletonisation algorithms with theoretical guarantees for unorganised point clouds with high levels of noise. (July 2021)

• Record Type: Journal Article
• Authors: Smith, P.; Kurlin, V.
• Is Part Of: Pattern recognition. Volume 115(2021)
• Publication Date: 2021-07
• Subjects: Data skeletonisation -- Noisy point sample -- Persistent homology; 97P99; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2021.107902
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: The paper evaluates algorithms that approximate unorganised point clouds by skeletons. A Homologically Persistent Skeleton (HoPeS) has guarantees proved for the first time. The optimality guarantee means that subgraphs of HoPeS show cycles hidden in a cloud. Other guarantees give conditions when a graph can be reconstructed from a noisy sample. Evaluations on large data show highest levels of noise for correct reconstructions. Abstract: Data Science aims to extract meaningful knowledge from unorganised data. Real datasets usually come in the form of a cloud of points. It is a requirement of numerous applications 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 the shape of the cloud. This paper compares different 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 algorithms produces a Homologically Persistent Skeleton (HoPeS) for any cloud without extra parameters. This universal skeleton contains subgraphs 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.