A Fast and Efficient Thinning Algorithm for Binary Images

Tarik Abu-Ain, Siti Norul Huda Sheikh Abdullah, Bilal Bataineh, Khairuddin Omar

Abstract


Skeletonization “also known as thinning” is an important step in the pre-processing phase in many of pattern recognition techniques. The output of Skeletonization process is the skeleton of the pattern in the images. Skeletonization is a crucial process for many applications such as OCR and writer identification. However, the improvements in this area are only a recent phenomenon and still require more researches. In this paper, a new skeletonization algorithm is proposed. This algorithm combines between parallel and sequential, which is categorized under an iterative approach. The suggested method is conducted by experiments of benchmark dataset for evaluation. The outcome is to obtain much better results compared to other thinning methods that are discussed in comparison part.

Full Text:

PDF

References


Kasturi, R., O’Gorman L. & Govindaraju, V., Document Image Analysis: A Primer, SADHANA-Academy Proceedings in Engineering Sciences, 27(1), pp. 3-22, 2002.

Marinai,S.,Introduction to Document Analysis and Recognition,Studies in Computational Intelligence,Ed.: Kacprzyk, Janusz, 90, pp.1-20,2008.

Wei, C., Lichun, S., Xu, Z. & Lang, Y., Improved Zhang-Suen Thinning Algorithm in Binary Line Drawing Applications, International Conference on Systems and Informatics (ICSAI 2012), Yantai, China, pp. 1947-1950, 2012.

Abu-Ain, T.A.H., Abu-Ain, W.A.H., Abdullah, S.N.H.S. & Omar, K., Off-line Arabic Character-Based Writer Identification-a Survey, in Proceeding of the International Conference on Advanced Science, Engineering and Information Technology (ICASEIT 2011), UKM, Bangi, Malaysia, pp. 161-166, 2011.

Bataineh, B., Abdullah, S.N.H.S. & Omar, K., An Adaptive Local Binarization Method for Document Images based on a Novel Thresholding Method and Dynamic Windows, Pattern Recognition Letters, 32(14), pp. 1805-1813, 2011.

Abu-Ain, T., Sheikh Abdullah, S.N., Bataineh, B., Omar, K. & Abu-Ein, A., A Novel Baseline Detection Method of Handwritten Arabic-Script Documents Based on Sub-Words, Soft Computing Applications and Intelligent Systems, Communications in Computer and Information Science, Springer Berlin Heidelberg, 378, pp. 67-77, 2013.

Gopakumar, R., Subbareddy, N.V., Makkithaya,K. & Acharya, U.D., Script Identification from Multilingual Indian Documents using Structural Features, Journal of Computing,2(7), pp. 106-111,2010.

Ali, M.A., An Efficient Thinning Algorithm for Arabic OCR Systems, Signal & Image Processing: An International Journal (SIPIJ), 3(3), pp. 31-38, 2012.

Nemeth, G. & Palagyi,K.,Topology Preserving Parallel Thinning Algorithm, International Journal of Imaging System and Technology, 21(1), pp. 37-44, 2011.

Saeed, K., Tabedzki, M., Rybnik, M.& Adamski, M., K3M: A Universal Algorithm for Image Skeletonization and a Review of Thinning Techniques, International Journal of Applied Mathematics and Computer Science, 20(2), pp. 317-335, 2010.

Quadros, W.R., Shimada, K.& Owen, S.J., Skeleton-Based Computa-tional Method for the Generation of a 3D Finite Element Mesh Sizing Function, Engineering with Computers, 20(3), pp. 249-264, 2004.

Guo, Z. & Hall, R.W., Fast Fully Parallel Thinning Algorithms, CVGIP: Image Understanding, 55(3), pp. 317-328,1992.

Ahmed, M. & Ward, R., A Rotation Invariant Rulebased Thinning Algorithm for Character Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(12), pp. 1672-1678,2002

Zhang, Y.Y. & Wang, P.S.P., A Parallel Thinning Algorithm with Two-Subiteration that Generates One-Pixel-Wide Skeletons, Proceedings of the 13th International Conference on Pattern Recognition (ICPR), Vienna, pp. 457-461,1996.

Lam, L., Lee, S. & Suen, C.Y., Thinning Methodologies-A Comprehen-sive Survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(9), pp. 869-885, 1992.

Naccache, N.& Shinghal, R., SPTA: A Proposed Algorithm for Thinning Binary Patterns, IEEE Transactions on Systems, Man and Cybernetics, 14(3), pp. 409-418, 1984.

Pavlidis, T., A Thinning Algorithm for Discrete Binary Images, Computer Graphics and Image Processing, 13(2), pp. 142-157, 1980.

Pavlidis, T., An Asynchronous Thinning Algorithm, Computer Graphics and Image Processing, 20(2), pp. 133-157, 1982.

Zhang, T.Y. & Suen, C.Y., A Fast Parallel Algorithm for Thinning Digital Patterns, Communications of the ACM, 27(3), pp. 236-239, 1984.

Xie, F., Xu, G., Cheng, Y. & Tian, Y., Human Body and Posture Recognition System Based on an Improved Thinning Algorithm, Image Processing, IET, 5(5), pp. 420-428, 2011.

Chen, Y.& Hsu, W., Systematic Approach for Designing 2-Subcycle and Pseudo 1-Subcycle Parallel Thinning Algorithms, Pattern Recognition, 22(3), pp. 267-282,1989.

Bag, S. & Harit, G., An Improved Contour-based Thinning Method for Character Images, Pattern Recognition Letters, 32(14), pp. 1836-1842,2011.

Ahmed, P., A Neural Network Based Dedicated Thinning Method, Pattern Recognition Letters, 16(6), pp. 585-590, 1995.

Mady, A.M.M. & Omar, K., A Comparative Study of Voronoi Algorithm Construction in Thinning, International Conference on Electrical Engineering and Informatics, Bandung, Indonesia, pp. 17-19, 2011.

You, X. & Tang Y., Wavelet-Based Approach to Character Skeleton, IEEE Transactions on Image Processing, 16(5), pp. 1220-1231, 2007.

Rockett, P.I., An Improved Rotation-Invariant Thinning Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(10), pp. 1671-1674, 2005.

Huang, L., Wan, G.& Liu, C., An Improved Parallel Thinning Algorithm, Proceedings of the Seventh International Conference on Document Analysis and Recognition (ICDAR 2003), Edinburgh, Scotland, UK, pp. 780-783, 2003.

Jeannin, S. & Bober, M., Description of Core Experiments for Mpeg-7 Motion/Shape, Technical Report ISO/IEC JTC 1/SC 29/WG 11 MPEG99/N2690, Seoul, March 1999.




DOI: http://dx.doi.org/10.5614%2Fitbj.ict.res.appl.2013.7.3.3

Refbacks

  • There are currently no refbacks.


Contact Information:

ITB Journal Publisher, LPPM – ITB, 

Center for Research and Community Services (CRCS) Building Floor 7th, 
Jl. Ganesha No. 10 Bandung 40132, Indonesia,

Tel. +62-22-86010080,

Fax.: +62-22-86010051;

e-mail: jictra@lppm.itb.ac.id.