A Fast Parallel Algorithm for Thinning Digital Patterns

Author: T. Y. Zhang and C. Y. Suen
Source: http://www.cr-online.ru/data/articles/p236-zhang.zip

      A fast parallel thinning algorithm is proposed in this paper. It consists of two subiterations: one aimed at deleting the south-east boundary points and the north-west corner points while the other one is aimed at deleting the north-west boundary points and the south-east corner points. End points and pixel connectivity are preserved. Each pattern is thinned down to a "skeleton" of unitary thickness. Experimental results show that this method is very effective.
      It is well known that the general problem of pattern recognition lies in the effectiveness and efficiency of extracting the distinctive features from the patterns. The stroke analysis method is a powerful approach to recognizing certain types of digital patterns such as alphanumeric characters and ideographs. It should be noted that the strokes thinned by hardware or software are accompanied by different kinds of distortion. Different thinning algorithms produce different degrees of distortion [1-5, 7-12].
      There is no general agreement in the literature on an exact definition of thinness. Pavlidis [6] describes a thinning algorithm that determines skeletal pixels by local operations. At the same time, the pixels are labeled so that the original image can be reconstructed from its skeleton. The goal of this paper is to find a faster and more efficient parallel thinning algorithm. The distortion should be as little as possible. Experimental results indicate that this method can be used to thin a variety of digital patterns.
      A binary digitized picture is defined by a matrix IT where each pixel IT(i, j) is either 1 or 0. The pattern consists of those pixels that have value 1. Each stroke in the pattern is more than one element thick. Iterative transformations are applied to matrix IT point by point according to the values of a small set of neighboring points. It is assumed that the neighbors of the point (i, j) are (i - 1, j), (i - 1, j + 1), (i, j + 1), (i + 1, j + 1), (i + 1, j), (i + 1, j - 1), (i, j - 1), and (i - 1, j - 1), as is shown in Figure 1. In parallel picture processing, the new value given to a point at the nth iteration depends on its own value as well as those of its eight neighbors at the (n - 1)th iteration, so that all picture points can be processed simultaneously. It is assumed that a 3 x 3 window is used, and that each element is connected with its eight neighboring elements. The algorithm presented in this paper requires only simple computations.
      Our method for extracting the skeleton of a picture consists of removing all the contour points of the picture except those points that belong to the skeleton. In order to preserve the connectivity of the skeleton, we divide each iteration into two subiterations.
      In the first subiteration, the contour point P1 is deleted from the digital pattern if it satisfies the following conditions:
(a) 2 <= B(P1) <= 6
(b) A(P1)= 1
(C) P2*P4*P6 = 0
(d) P4*P6*P8 = 0
where A(P1) is the number of 01 patterns in the ordered set P2, P3, P4, ... ,P8, P9 that are the eight neighbors of P1 (Figure 1), and B(Pi) is the number of nonzero neighbors of P1, that is, B(P1) = P2 + P3 + P4 + ... + P8 + P9.
      If any condition is not satisfied, e.g., the values of P2, P3, P4, ..., P9 as shown in Figure 2, then A(Pi) = 2
      Therefore, P1 is not deleted from the picture.
      A parallel algorithm for thinning different types of digital patterns is presented in this paper. Each iteration is divided into two subiterations that remove the boundary and corner points of the digital patterns. After several iterations, only a skeleton of the pattern remains.
      The proposed algorithm appears to be very efficient in the thinning of digital patterns and it compares favorably with those described in [11]. The results in Table I indicate that our method is 1.5 to 2.3 times faster than the four-step and two-step methods described in [11] while the resulting skeletons look very much the same. 1. Arcelli, C., Cordelia, L.P. and Levialdi, S. From local maxima to connected skeletons. IEEE Trans. Pattern Analysis and Machine Intell. PAMI-3 (March 1981), 134-143.
2. Arcelli, C. A condition for digital points removal. Signal Processing 1,4 (1979), 283-285.
3. Deutsch, E.S. Thinning algorithms on rectangular, hexagonal, and triangular arrays. Commun. ACM 15, 9 (Sept. 1972), 827-837.
4. Hilditch, C.J. Linear skeletons from square cupboards. In: Machine Intelligence IV, B. Mertzer and D. Michie, Eds., University Press, Edinburgh, 1969, pp. 403-420.
5. Ogawa, H. and Tanguchi, K. Thinning and stroke segmentation for handwritten Chinese character recognition. Pattern Recognition 15, 4 (1982), 299-308.
6. Pavlidis, T. A Flexible Parallel Thinning Algorithm. Proc. IEEE Comput. Soc. Conf. on Pattern Recognition and Image Processing. Aug. 1981, pp. 162-167.
7. Rosenfeld, A. Connectivity in digital picture. J. ACM 17, 1 (Jan. 1971), 146-160.
8. Rosenfeld, A. A characterization of parallel thinning algorithm. Info. Control 29 (Nov. 1975}, 286-291.
9. Rosenfeld, A. and Davis, L.S. A note on thinning• IEEE Trans. Syst. Man Cybern. SMC-6, 3 (March 1976), 226-228.
10. Rutovitz, D. Pattern Recognition. Proc. Royal Statists. Soc. 129, Series A (1966), 504-530.
11. Stefanelli, S. and Rosenfeld, A. Some parallel thinning algorithms for digital picture• J. ACM 18 (April 1971), 255-264.
12. Tamura, H. A comparison of line thinning algorithms from digital geometry viewpoint. Proc. 4th Int. Conf. Pattern Recognition, 1978, pp. 715-719.