Pattern Recognition and
Image Processing Group
Institute of Visual Computing and Human-Centered Technology
Title: A homologically persistent skeleton in computer vision
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 the new fundamental concept of a Homologically Persistent Skeleton, which is scale-and-rotation invariant and depends only on the given cloud without extra parameters. This graph
(1) is computable in time O(n log n) for any n points in the plane;
(2) has the minimum total length among all graphs that span a 2D cloud at any scale and also have most persistent 1-dimensional cycles;
(3) is geometrically stable for noisy samples around planar graphs.
The preprint is available at http://kurlin.org/projects/homologically-persistent-skeleton-dim2.pdf (15 pages, 2.8M).