A width-independent fast thinning algorithm.

The skeleton of a digital figure can often be regarded as a convenient alternative to the figure itself. It is useful both to diminish drastically the amount of data to be handled, and to simplify the computational procedures required for description and classification purposes. Thinning a digital figure down to its skeleton is a time-consuming process when conventional sequential computers are employed. The procedure we propose allows one to speed up the thinning transformation, and to get a well-shaped skeleton. After cleaning of the input picture has been performed, the pixels of the figure are labeled according to their distance from the background, and a set, whose pixels are symmetrically placed with respect to distinct contour parts of the figure, is found. This set is then given a linear structure by applying topology preserving removal operations. Finally, a pruning step, regarding branches not relevant in the framework of the problem domain, completes the process. The resulting skeleton is a labeled set of pixels which is shown to possess all the required properties, particularly those concerning connectedness, topology, and shape. Moreover, the original figure can almost completely be recovered by means of a reverse distance transformation. Only a fixed and small number of sequential passes through the picture is necessary to achieve the goal. The computational effort is rather modest, and the use of the proposed algorithm turns out to be more advantageous the greater the width of the figure to be thinned.

From local maxima to connected skeletons.

In picture processing it is often convenient to deal with a stick-like version (skeleton) of binary digital images. Although skeleton connectedness is not necessary for storage and retrieval purposes, this property is desirable when a structural description of images is of interest. In this paper a parallel procedure is described which, applied to a connected image, originates a connected skeleton made by the union of simple digital arcs. The procedure involves a step by step propagation of the background over the image. At every step, contour elements either belonging to the significant convex regions of the current image or being local maxima of the original image are selected as skeleton elements. Since the final set so obtained is not ensured to be connected, the configurations in correspondence of which disconnections appear are investigated and the procedures to avoid this shortcoming are given. The presence of the whole set of local maxima among the skeleton elements ensures the possibility of recovering the original image by means of a reverse distance transform. The details of the program implementing the proposed algorithm on a parallel processor are finally included.