A Fast Parallel Thinning Algorithm for the Binary Image Skeletonization

Abstract

This paper investigates the skeletonization problem using parallel thinning techniques and proposes a new one-pass parallel asymmetric thinning algorithm (OPATA₈). Wu and Tsai presented a one-pass parallel asymmetric thinning algorithm (OPATA₄) that implemented 4-distance, or city block distance, skeletonization. However, city block distance is not a good approximation of Euclidean distance. By applying 8-distance, or chessboard distance, this new algorithm improves not only the quality of the resulting skeletons but also the efficiency of the computation. This algorithm uses 18 patterns. The algorithm has been implemented, and has been compared to both algorithm OPATA₄ and Zhang and Suen’s two-pass parallel thinning algorithm. The results show that the proposed OPATA₈ has good noise resistance, perfectly 8-connected skeleton output, and a faster speed without serious erosion.