Project Persistent skeletons based on papers in AAM 2019  CGF 2015  CAIP 2015

@article{KKL19AAM, author = {Kalisnik, S. and Kurlin,V. and Lesnik,D.}, title = {A highdimensional 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

@article{Kur15CGF, 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

@inproceedings{Kur15CAIP, 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