|
Vol: 57(71) No: 3 / September 2012 An Improved Parallel Algorithm for Thinning Binary Images Peter Tarabek Department of Transportation Networks, University of Zilina, Univerzitná 8215/1, 010 26 Zilina, Slovakia, e-mail: peter.tarabek@fri.uniza.sk Keywords: thinning, skeleton, Zhang and Suen algorithm, one pixel thick skeleton, excessive erosion, shape analysis Abstract In this paper an improved algorithm for thinning binary images based on the popular Zhang and Suen (ZS) method is presented. The ZS algorithm becomes one of the most used thinning algorithms mainly because of its fast computational speed and its robustness in terms of connectivity and insensitivity to boundary noise. We proposed additional conditions and post-processing step to deal with three main problems of the ZS algorithm i.e. excessive erosion of diagonal line segments, deletion of 2x2 square patterns and production of redundant pixels in skeleton. These drawbacks can have huge impact on the quality of skeleton making the further tracking and feature extraction processes less efficient. The proposed conditions use information from 4x4 neighborhood to recognize and preserve the crucial patterns in skeleton. To evaluate the performance of the proposed method we use two measurement criteria: the thinning rate and the number of junction points. Experimental results show that our method preserves good properties of the ZS algorithm, overcomes the mentioned weaknesses and in some cases requires even less computational time than original ZS algorithm. We believe that because of these properties the method is suitable for applications such as character and handwriting recognition, vectorization of transport infrastructure, fingerprint analysis and medical image processing. References [1] J. Sadri, C.Y. Suen, and T.D. Bui, “Automatic segmentation of unconstrained handwritten numeral strings,” Proceedings of the Ninth International Workshop on Frontiers in Handwriting Recognition (IWFHR 2004), 2004, pp. 317–322. [2] M.S. Khorsheed, “Recognising Handwritten Arabic Manuscripts Using a Single Hidden Markov Model,” Pattern Recognition Letters, vol. 24, pp. 2235-2242, 2003. [3] J.-Y. Cheng, and Y.-H. Liu, “Human body image segmentation based on wavelet analysis and active contour models,” Proceedings of International Conference on Wavelet Analysis and Pattern Recognition (ICWAPR \'07), 2007, pp. 265 – 269. [4] R. Xia, P. Wang, and Q. Zhao, “An Image Segmentation Method for Quasi-circular Immune Cells,” Proceedings of International Symposium on Intelligence Information Processing and Trusted Computing (IPTC), 2010, pp. 353 – 356. [5] P. Cenek, and P. Tarabek, “Acquisition of Input Data for Transportation Models,” Proceedings of 7th EUROSIM Congress on Modelling and Simulation, 2010. [6] H. Xu, Y. Qu, and F. Zhao, “FPGA Based Parallel Thinning for Binary Fingerprint Image,” Proceedings of IEEE Chinese Conference on Pattern Recognition, 2009, pp. 1–4. [7] A. Hafiz, Md.F. Amin and K. Murase, “Real-Time Hand Gesture Recognition Using Complex-Valued Neural Network (CVNN),“ Proceedings of International Conference on Neural Information Processing (ICONIP 2011), 2011. [8] L. Lam, S. Lee, and C. Suen, “Thinning Methodologies—A Comprehensive Survey,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14, no. 9, pp. 869-885, 1992. [9] L. Lam, and C. Suen, “An Evaluation of Parallel Thinning Algorithms for Character Recognition,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no. 9, pp. 914-919, 1995. [10] T.Y. Zhang, and C.Y. Suen, “A Fast Parallel Algorithm for Thinning Digital Patterns,” Communications of ACM, vol. 27, pp. 236-239, 1984. [11] L.E. Lu, and P.S.P. Wang, “A Comment on ‘A Fast Parallel Algorithm for Thinning Digital Patterns’,” Communications of ACM, vol. 29, pp. 239-242, 1986. [12] P. S. P. Wang, L. Hui, and Jr. T. Fleming, \"Further improved fast parallel thinning algorithm for digital Patterns,\" Proceedings of Computer Vision, Image Processing and Communication Systems and Applications, pp. 37-40, 1986. [13] J.S. Kwon, J.W. Gi, and E.K. Kang, “An enhanced thinning algorithm using parallel processing,” Proceedings of International Conference on Image Processing, 2001, pp. 752 -755. [14] X. D. Gu, D. H. Yu, and L. M. Zhang, “Image thinning using pulse coupled neural network,” Pattern Recognition Letters, vol. 25, no. 9, pp. 1075–1084, Jul. 2004. [15] A. Datta, S.K. Parui, and B.B. Chaudhuri, “Skeletonization by a Topology-Adaptive Self-Organizing Neural Network,” Pattern Recognition, vol. 34, pp. 617-629, 2001. [16] P. Tarabek, “A robust parallel thinning algorithm for pattern recognition,“ Proceedings of 7th IEEE International Symposium on Applied Computational Intelligence and Informatics (SACI), 2012, pp. 75-79. [17] P. Tarabek, “Performance measurements of thinning algorithms,” Journal of Information, Control and Management Systems, vol. 6, pp. 125-132, 2008. |