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 high-dimensional Homologically Persistent Skeleton}, journal = {Advances in Applied Mathematics}, volume = {102}, pages = {113-142}, year = {2019} }- DOI : 10.1016/j.aam.2018.07.004 ISSN : 0196-8858
- Input : a finite cloud C of n points (or a filtration of complexes on C) in any metric space.
- Output : a k-dimensional skeleton HoPeS(C) with all persistent k-dimensional 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 low-dimensional non-linear 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 well-separated 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 1-parameter family of shapes associated to a cloud. These features can be visualized in the form of a 1-dimensional 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 one-dimensional Homologically Persistent Skeleton of an unstructured point cloud in any metric space}, journal = {Computer Graphics Forum}, volume = {34}, number = {5}, pages = {253-262}, year = {2015} }- DOI : 10.1111/cgf.12713 Online ISSN : 1467-8659
- 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 1-dimensional 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 1-dimensional 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 : persistent-skeletons.cpp (a beta-version, please e-mail 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 = {606-617}, year = {2015} }- DOI : 10.1007/978-3-319-23192-1_51 Online ISBN : 978-3-319-23192-1
- 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 non-integer 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 object-wide descriptor.
- We extend a classical Minimum Spanning Tree of a cloud to a Homologically Persistent Skeleton, which
- (1) is scale-and-rotation 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 : persistent-skeletons.cpp (a beta-version, please e-mail vitaliy.kurlin(at)gmail.com for support).
Back to Top of this page | Back to Research & papers | Back to Home page