A Homologically Persistent Skeleton is a fast and robust descriptor of interest points in 2D images

Kurlin, Vitaliy

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 is scale-and-rotation invariant and depends only on the cloud without extra parameters. This graph (1) is computable in time O(nlogn) 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.

Citation

Kurlin, V. (1999). A Homologically Persistent Skeleton is a fast and robust descriptor of interest points in 2D images. In G. Azzopardi, & N. Petkov (Eds.), Computer analysis of images and patterns : 16th International Conference, CAIP 2015, Valletta, Malta, September 2-4, 2015. Proceedings. Part I (606-617). Springer Verlag. https://doi.org/10.1007/978-3-319-23192-1_51

• Acceptance Date: Jun 19, 2015
• Publication Date: Aug 25, 1999
• Deposit Date: Sep 18, 2015
• Publicly Available Date: Aug 25, 2016
• Publisher: Springer Verlag
• Pages: 606-617
• Series Title: Lecture notes in computer science
• Book Title: Computer analysis of images and patterns : 16th International Conference, CAIP 2015, Valletta, Malta, September 2-4, 2015. Proceedings. Part I.
• ISBN: 9783319231914
• DOI: https://doi.org/10.1007/978-3-319-23192-1_51
• Keywords: Skeleton, Delaunay triangulation, Persistent homology.
• Additional Information: Volume 9256 of the series Lecture Notes in Computer Science