PARALLEL THINNING
The most "natural" way to thin an object consists of removing some of its border points in parallel, in a symmetrical manner. However, parallel deletion of simple points does not, in general, guarantee topology preservation: see for example Fig. 1a, where removing all simple points would split the object and merge two components of the background, and Fig. 1b,c,d where all the points are simple.
In fact, such a guarantee is not obvious to obtain, even for the 2D case (see [Cou06], where fifteen published parallel thinning algorithms are analyzed, and counter-examples are shown for five of them).
In the 2D case, a popular method due to A. Rosenfeld consists of dividing each thinning step into substeps. In each substep, only simple points that have no neighbor belonging to the object in one of the four main directions (north, south, east, west) are candidate for deletion. In addition, two special configurations made of two adjacent pixels (see Fig. 1c,d) must be preserved, as well as their 90 degrees rotations. This stategy prevents a whole object to vanish like in Fig. 1b, or to break like in Fig. 1a.
However, it cannot be straightforwardly extended to 3D. In this case, the six main directions are north, south, east, west, up and down. In Fig. 2, the voxels x,y are simple voxels that have no neighbor belonging to the object in the direction "up", but if we remove them in parallel, the object splits.
|
|
|
Figure 1. (a): The object is the set of all black and gray pixels. The pixels in gray are simple, but pixels x,y for example cannot be removed in parallel while preserving topology. North pixels are marked with the letter "n". (b,c,d): All pixels are simple.
Figure 2. All voxels are simple, the voxels x and y are both "up" voxels.
Site info
© 2006-2007 A2SI Lab.