Robust and Efficient Skeletal Graphs

Abstract

There has recently been significant interest in using representations based on abstractions of Blum's skeleton into a graph, for qualitative shape matching. The application of these techniques to large databases of shapes hinges on the availability of numerical algorithms for computing the medial axis. Unfortunately, this computation can be extremely subtle. Approaches based on Voronoi techniques preserve topology, but heuristic pruning measures are introduced to remove unwanted edges. Methods based on Euclidean distance functions can localize skeletal points accurately, but often at the cost of altering the object's topology. In this paper we introduce a new algorithm for computing subpixel skeletons which is robust and accurate, has low computational complexity, and preserves topology. The key idea is to measure the net outward flux of a vector field per unit area, and to detect locations where a conservation of energy principle is violated. This is done in conjunction with a thinning process applied in a rectangular lattice. We illustrate the approach with several examples of skeletal graphs for biological and man-made silhouettes.