Thinning is an important preprocessing step for many image analysis operations. The goal of this paper is to present and evaluate two parallel thinning algorithms.

The authors define these algorithms over binary-valued images digitized in a rectangular tessellation, as two-subiteration algorithms restricted to 3 × 3 thinning operators. These two algorithms are compared with other two-subiteration algorithms and with a fully parallel thinner considered in the literature. The comparison criteria are (1) the minimum number of iterations necessary to reach the skeleton, (2) the minimum percentage of redundant pixels left in the skeleton, and (3) the satisfiability of the specific goals of any thinning algorithms extended in this paper for parallel thinners.

The first algorithm modifies the algorithms of Zhang and Suen [1] and Lü and Wang [2] in order to produce thin results and to preserve all connectivity properties. The second algorithm is defined on an image that is divided into two subfields in a checkerboard pattern; it is an adaptation of the classical thinning algorithm of Rosenfeld and Kak. It achieves the best overall parallel speed and minimizes the number of redundant pixels. For both algorithms, the connectivity properties of the image are proved in two appendices.

The reader needs no special background. The clarity and the complete presentation of the algorithm and their performance define this paper. All included references are good and recent.