| 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. |
