Pattern Recognition and
Image Processing Group
Institute of Computer Graphics and Algorithms
PRIP Fakultät für Informatik, TU Wien Technische Universität Wien Fakultät für Informatik

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 (15 pages, 2.8M).

Contact: Mail: webmaster(at) | Tel: +43.1.58801.18661 | Fax : +43.1.58801.18697
2014 PRIP, Impressum
This page is maintained by Webmaster ( webmaster(at) ) and was last modified on 12. March 2015 18:10