FAST HOMOTOPY - PRESERVING SKELETONS USING MATHEMATICAL MORPHOLOGY

This paper describes two algorithms for skeletonization of 2-D binary images, each of which explicitly separates the two major aspects of skeletonization: 1) the identification of points critical to shape representation and 2) the identification of further points necessary to preserve homotopy. Sets of points critical to shape representation are found by eroding the original image I with a nested sequence of structuring elements E(i), where E0 = {O} and E(i) subset-of E(i+1), corresponding to a generalized distance transform. In a generalization of the "morphological skeleton," at each iteration, the set of shape-related points M(i) is defined to be I - E(i-1) \ (I - E(i)) + D, where D is a suitable small structuring element. Points needed in addition to those of M(i), in order to preserve homotopy, may be found at each iteration by a search restricted to the "shell" I - E(i-1), \ I - E(i). By choosing appropriate {E(i)} and D, either algorithm is capable of producing a variety of skeletons corresponding to different distance functions. It is proved that if E(i) + D subset-or-equal-to E(i+1), then the original image can be reconstructed from the skeleton. In the case of the first algorithm, there are few restrictions on the set of structuring elements. It uses a simple search strategy to find points whose removal would alter homotopy. Examples of its application illustrate shape, connectivity, thinness, and image reconstruction aspects of skeletonization. The second, faster, algorithm has a more constructional approach to finding points necessary for preserving homotopy, which limits it to a more restricted set of structuring elements than the first algorithm. However, it may still be used with a variety of distance functions including "city block," "chessboard," and "octagon" distances and a set of approximations to Euclidean distance where precision may be traded against computational cost. "Interval coding" of the binary images is used, resulting in computationally efficient implementations of mathematical morphology and Boolean functions, and performance data confirm that the second algorithm is amongst the fastest serial computer skeletonization algorithms.