Project Persistent skeletons based on papers in
PR 2021 
TopoInVis 2019 
AAM 2019 
CGF 2015 
CAIP 2015
HoPeS : a Homologically Persistent Skeleton outperforms other algorithms on noisy data

@inproceedings{smith2021skeletonisation, author = {Smith, Philip and Kurlin, Vitaliy}, title = {Skeletonisation algorithms with theoretical guarantees for unorganised point clouds with high levels of noise}, journal = {Pattern Recognition}, volume = {115}, year = {2021} }
 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 nonlinear object that is more complicated than a union of disjoint clusters. The skeletonisation problem in its hardest form is to find a 1dimensional 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 subgraphs that provably represent the 1dimensional 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.
Back to Top of this page  Back to Research & papers  Back to Home page
ASk : Approximate Skeleton of a point cloud
@inproceedings{elkin2019fast, author = {Elkin, Y. and Liu, D. and Kurlin,V}, title = {A fast approximate skeleton with guarantees for any cloud of points in a Euclidean space}, booktitle = {Proceedings of TopoInVis 2019 (Topologybased methods in Visualization)}, year = {2019} }
 Input : a finite cloud C of n points in any Euclidean space.
 Output : an embedded straightline Approximate Skeleton (ASk) approximating C with theoretical guarantees.
 Abstract. The tree reconstruction problem is to find an embedded straightline tree that approximates a given cloud of unorganized points in Rm up to a certain error. A practical solution to this problem will accelerate a discovery of new colloidal products with desired physical properties such as viscosity. We define the Approximate Skeleton of any finite point cloud C in a Euclidean space with theoretical guarantees. The Approximate Skeleton ASk(C) always belongs to a given offset of C, i.e. the maximum distance from C to ASk(C) can be a given maximum error. The number of vertices in the Approximate Skeleton is close to the minimum number in an optimal tree by factor 2. The new Approximate Skeleton of any unorganized point cloud C is computed in a near linear time in the number of points in C. Finally, the Approximate Skeleton outperforms past skeletonization algorithms on the size and accuracy of reconstruction for a large dataset of real micelles and random clouds.
Back to Top of this page  Back to Research & papers  Back to Home page
Higherdimensional skeleton HoPeS

@article{kalisnik2019higher, author = {Kalisnik, S. and Kurlin,V. and Lesnik,D.}, title = {A higherdimensional Homologically Persistent Skeleton}, journal = {Advances in Applied Mathematics}, volume = {102}, pages = {113142}, year = {2019} }
 DOI : 10.1016/j.aam.2018.07.004 ISSN : 01968858
 Input : a finite cloud C of n points (or a filtration of complexes on C) in any metric space.
 Output : a kdimensional skeleton HoPeS(C) with all persistent kdimensional cycles hidden in C.
 Abstract. Real data is often given as a point cloud, i.e. a finite set of points with pairwise distances between them. An important problem is to detect the topological shape of data — for example, to approximate a point cloud by a lowdimensional nonlinear subspace such as an em bedded graph or a simplicial complex. Classical clustering methods and principal component analysis work well when given data points split into wellseparated clusters or lie near linear subspaces of a Euclidean space.
 Methods from Topological Data Analysis in general metric spaces detect more complicated patterns such as holes and voids that persist for a large interval in a 1parameter family of shapes associated to a cloud. These features can be visualized in the form of a 1dimensional homologically persistent skeleton, which optimally extends a minimum spanning tree of a point cloud to a graph with cycles. We generalize this skeleton to higher dimensions and prove its optimality among all complexes that preserve topological features of data at any scale.
Back to Top of this page  Back to Research & papers  Back to Home page
HoPeS : a Homologically Persistent Skeleton

@article{kurlin2015one, author = {Kurlin,V.}, title = {A onedimensional Homologically Persistent Skeleton of an unstructured point cloud in any metric space}, journal = {Computer Graphics Forum}, volume = {34}, number = {5}, pages = {253262}, year = {2015} }
 DOI : 10.1111/cgf.12713 Online ISSN : 14678659
 Input : a finite cloud C of n points (or a filtration of complexes on C) in any metric space.
 Output : the skeleton HoPeS(C) with all persistent cycles that were hidden in the cloud C.
 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 1dimensional 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 1dimensional 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).
 C++ code : persistentskeletons.cpp (a betaversion, please email vitaliy.kurlin(at)gmail.com for support).
Back to Top of this page  Back to Research & papers  Back to Home page
HePeS applications to image skeletonisation

@inproceedings{kurlin2015homologically, author = {Kurlin,V.}, title = {A Homologically Persistent Skeleton is a fast and robust descriptor of interest points in 2D images}, booktitle = {Lecture Notes in Computer Science (Proceedings of CAIP 2015)}, volume = {9256}, pages = {606617}, year = {2015} }
 DOI : 10.1007/9783319231921_51 Online ISBN : 9783319231921
 Input : a finite cloud C of n points in the plane, say Canny edge points of a 2D image.
 Output : the skeleton HoPeS(C) whose cycles correspond to all dots in 1D persistence of C.
 Running time : O(n log n) for a cloud C of n points with any real coordinates in the plane.
 Abstract. 2D images often contain irregular salient features and interest points with noninteger coordinates. Our skeletonization problem for such a noisy sparse cloud is to summarize the topology of a given 2D cloud across all scales in the form of a graph, which can be used for combining local features into a more powerful objectwide descriptor.
 We extend a classical Minimum Spanning Tree of a cloud to a Homologically Persistent Skeleton, which
 (1) is scaleandrotation invariant and depends only on the cloud C without any extra input parameters;
 (2) contains reduced skeleton (at every scale), shortest among all graphs that have the homology of the thickened cloud;
 (3) contains the derived skeleton giving a close approximation to a good unknown planar graph given by a noisy sample;
 (4) is geometrically stable for a noisy sample C around planar graphs (remains in a small neighborhood after perturbing C);
 (5) is computable in time O(n log n) for any n points in the plane (based on αcomplexes filtering a Delaunay triangulation).
 C++ code : persistentskeletons.cpp (a betaversion, please email vitaliy.kurlin(at)gmail.com for support).
Back to Top of this page  Back to Research & papers  Back to Home page