Project Persistent skeletons based on papers in CGF 2015 CAIP 2015
Paper: A onedimensional Homologically Persistent Skeleton of an unstructured point cloud in any metric space.

@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
Paper: A Homologically Persistent Skeleton is a fast and robust descriptor of interest points in 2D images.
@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