Some Parallel Thinning Algorithms for Digital Pictures

Publisher Website
Google Scholar
Abstract
If a picture contains elongated objects of different thicknesses, one can make measurements on it which are thickness-invariant by first transforming it so that each object is thinned down to a "medial line" of constant thickness. Several algorithms are described which perform such a thinning transformation when applied to the picture in parallel. It is proved that these algorithms do not change the connectivity properties of the picture. 1. Introduetion It is well known that the general problem of pattern recognition is that of partition- ing the set of patterns to be recognized into a prescribed number of classes; the choice of the class to which a given pattern is to be assigned is made on the basis of the values assumed by certain measurements applied to the pattern. It is also well known that the effectiveness of a pattern recognition method largely depends on how significant the set of measurements is. If planar, two-tone pictures containing elongated or linelike objects are to be classified, for example alphanumeric printed or handprinted characters, chromo- somes, etc., the thickness of the strokes which constitute the objects generally do not contribute to the recognition. Several authors (1-4) have studied the problem of obtaining sets of thickness-invari ant measurements; unfortunately, these measure- ments are invariant only with respect to a uniform change of thickness in the entire picture. One method for obtaining invariance for nonuniform thickness variations involves determining a constant-thickne ss "medial line" of each object and considering, for recognition purposes, only the features of this line. In this paper some algorithms are described for the determination of such a medial line; this line can be used (5) to extract topological features of the object. The results obtained are similar to those obtained by applying algorithms for the determination of the "skeleton" of a figure (6-8). t