Search

An algorithm to compute the curve skeleton of 3D objects in voxel images is presented. The skeleton is stable under isometric transformations of the object, since the algorithm is based on the use of the (3, 4, 5) weighted distance transform, which is a good approximation of the Euclidean distance transform. The (3, 4, 5) weighted distance transform is used both to identify suitable anchor points, and to efficiently check object voxels according to their distance to the background. The curve skeleton is symmetrically placed within the object, is topologically equivalent to the object, is unit-wide and provides a satisfactory representation of the object. Though the size of the object reconstructed from the curve skeleton via the reverse distance transformation is not as thick as that of the input, shape information is mostly retained by the skeleton, since all regions perceived as significant in the input can still be found in the reconstructed object.

The characterization of a digital figure in terms of the multiple pixels, i.e., the pixels placed where the contour selfinteracts, can provide useful shape cues. These pixels can satisfactorily be detected if a suitable definition of contour simplicity is available. Such a definition is given in this paper, for the case of multiply connected figures. The multiple pixels are those where the contour fails to be simple, and they can be identified by using 3 × 3 local operations.

The 4-metric is adopted to construct the Voronoi diagram of a binary digital picture, whose foreground consists of arbitrarily shaped components. The 4-distance transform of the background is employed to find the exoskeleton, from which the set of the Voronoi edges is succesivvely obtained after removal of certain pixels. As an ultimate step, the various tiles are identified by using a component labeling technique. The proposed algorithm can be convenietly implemented on standard sequential computers, as only five complete inspections of the picture are sufficient for the whole process. Moreover, all the computations are performed on the array where the picture is initially stored.