Project Persistent skeletons based on papers in CGF 2015 CAIP 2015
Paper: A one-dimensional Homologically Persistent Skeleton of an unstructured point cloud in any metric space.
 |
|
@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
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 = {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