Skeletonization via the realization of the fire front's propagation and extinction in digital binary shapes

Abstract

A sequential method of skeletonization for digital binary images is proposed. The method realizes in a discrete plane prairie-fire propagation model. The techniques of contour following is adopted to simulate the simultaneous fire spreading off of the grass perimeter. The algorithm contains two steps: (1) find and mark all of the contours of the input image during a conventional scan. Then, after the borders a 'lighted', (2) repeatedly examine the borders and strip deletable edge points until no more can be removed. In this way only the successive contours, but not the whole image, will be processed. The second step is subdivided as follows: first, the contours representing the current fire fronts are traced, all the edge points are memorized, and the next fire fronts are marked. Second, the algorithm verifies the memorized edge points and those marked only once are removed. Although no neighborhood's test is needed during this stage of peeling, the connectedness of objects to thinning is conserved. Insignificant spurs can, optionally, be removed during thinning.