A fast parallel thinning algorithm for the binary image skeletonization

This paper investigates the skeletonization problem using parallel thinning techniques and proposes a new one-pass parallel asymmetric thinning algori thm (OPATA(8)). Wu and Tsai presented a one-pass parallel asymmetric thinni ng algorithm (OPATA(4)) 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, thi s new algorithm improves not only the quality of the resulting skeletons bu t also the efficiency of the computation. This algorithm uses 18 patterns. The algorithm has been implemented, and has been compared to both algorithm OPATA(4) and Zhang and Suen's two-pass parallel thinning algorithm. The re sults show that the proposed OPATA(8) has good noise resistance, perfectly 8-connected skeleton output, and a faster speed without serious erosion.