A Fast Parallel Algorithm for Thinning Digital Patterns

A Fast Parallel Algorithm for Thinning Digital Patterns

March 1984 | T. Y. ZHANG and C. Y. SUEN
A fast parallel algorithm for thinning digital patterns is proposed. The algorithm consists of two subiterations: one to remove south-east boundary points and north-west corner points, and the other to remove north-west boundary points and south-east corner points. Endpoints and pixel connectivity are preserved, and each pattern is thinned to a skeleton of unitary thickness. Experimental results show the method is effective. The paper discusses the problem of pattern recognition, emphasizing the importance of extracting distinctive features. Thinning algorithms can introduce distortion, and there is no consensus on the definition of thinness. Pavlidis describes a thinning algorithm that determines skeletal pixels through local operations and allows reconstruction of the original image from its skeleton. The goal is to find a faster and more efficient parallel thinning algorithm with minimal distortion. The algorithm processes a binary matrix, where each pixel is either 1 or 0. Iterative transformations are applied to the matrix based on neighboring points. The algorithm uses a 3x3 window and processes all points simultaneously. Each iteration is divided into two subiterations to preserve connectivity. In the first subiteration, points are deleted based on specific conditions related to their neighbors. In the second subiteration, similar conditions are applied but with different criteria. The algorithm is tested on various patterns, including the character "H," a Chinese character, and a letter "B." The results show that the algorithm preserves endpoints and maintains good connectivity and noise immunity. The algorithm is compared with another method, showing it is 1.5 to 2.3 times faster. The algorithm uses two matrices, IT and M, to save memory. The results indicate that the algorithm is efficient and effective for thinning digital patterns.A fast parallel algorithm for thinning digital patterns is proposed. The algorithm consists of two subiterations: one to remove south-east boundary points and north-west corner points, and the other to remove north-west boundary points and south-east corner points. Endpoints and pixel connectivity are preserved, and each pattern is thinned to a skeleton of unitary thickness. Experimental results show the method is effective. The paper discusses the problem of pattern recognition, emphasizing the importance of extracting distinctive features. Thinning algorithms can introduce distortion, and there is no consensus on the definition of thinness. Pavlidis describes a thinning algorithm that determines skeletal pixels through local operations and allows reconstruction of the original image from its skeleton. The goal is to find a faster and more efficient parallel thinning algorithm with minimal distortion. The algorithm processes a binary matrix, where each pixel is either 1 or 0. Iterative transformations are applied to the matrix based on neighboring points. The algorithm uses a 3x3 window and processes all points simultaneously. Each iteration is divided into two subiterations to preserve connectivity. In the first subiteration, points are deleted based on specific conditions related to their neighbors. In the second subiteration, similar conditions are applied but with different criteria. The algorithm is tested on various patterns, including the character "H," a Chinese character, and a letter "B." The results show that the algorithm preserves endpoints and maintains good connectivity and noise immunity. The algorithm is compared with another method, showing it is 1.5 to 2.3 times faster. The algorithm uses two matrices, IT and M, to save memory. The results indicate that the algorithm is efficient and effective for thinning digital patterns.
Reach us at info@study.space