A modified K3M thinning algorithm

• Autorzy: Marek Tabedzki , Khalid Saeed , Adam Szczepański
• Języki publikacji: EN

Abstrakty

EN

The K3M thinning algorithm is a general method for image data reduction by skeletonization. It had proved its feasibility in most cases as a reliable and robust solution in typical applications of thinning, particularly in preprocessing for optical character recognition. However, the algorithm had still some weak points. Since then K3M has been revised, addressing the best known drawbacks. This paper presents a modified version of the algorithm. A comparison is made with the original one and two other thinning approaches. The proposed modification, among other things, solves the main drawback of K3M, namely, the results of thinning an image after rotation with various angles.

Słowa kluczowe

EN

skeletonization; thinning; K3M algorithm; digital image processing

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2016
• Tom: 26
• Numer: 2
• Strony: 439-450

Daty

wydano

2016

otrzymano

2015-04-04

poprawiono

2015-08-27

poprawiono

2015-10-28

zaakceptowano

2015-12-02

Twórcy

autor

Marek Tabedzki

• Faculty of Computer Science, Białystok University of Technology, ul. Wiejska 45 A, 15-351 Białystok, Poland

autor

Khalid Saeed

• Faculty of Computer Science, Białystok University of Technology, ul. Wiejska 45 A, 15-351 Białystok, Poland
• Faculty of Mathematics and Information Sciences, Warsaw University of Technology, ul. Koszykowa 75, 00-662 Warsaw, Poland

autor

Adam Szczepański

• Faculty of Computer Science, Białystok University of Technology, ul. Wiejska 45 A, 15-351 Białystok, Poland

Bibliografia

• Abu-Ain, W., Abdullah, S.N.H.S., Bataineh, B., Abu-Ain, T. and Omar, K. (2013). Skeletonization algorithm for binary images, Procedia Technology 11(0): 704-709.
• Arcelli, C. (1981). Pattern thinning by contour tracing, Computer Graphics and Image Processing 17(2): 130-144, DOI: 10.1016/0146-664X(81)90021-6.
• Arcelli, C. and Sanniti di Baja, G. (1978). On the sequential approach to medial line transformation, IEEE Transactions on Systems, Man and Cybernetics 8(2): 139-144, DOI: 10.1109/TSMC.1978.4309914.
• Chen, Y. and W.H., H. (1993). Parallel thinning algorithm for binary digital patterns, in C. Chen et al. (Eds.), Handbook of Pattern Recognition; Computer Vision, World Scientific Publishing, River Edge, NJ, pp. 457-490, DOI: 10.1007/978-3-642-33564-8_78.
• Deng, W., Iyengar, S.S. and Brener, N.E. (2000). A fast parallel thinning algorithm for the binary image skeletonization, International Journal of High Performance Computing Applications 14(1): 65-81.
• Dinneen, G. (1955). Programming pattern recognition, Proceedings of the 1955, Western Joint Computer Conference, New York, NY, USA, pp. 94-100, DOI: 10.1145/1455292.1455311.
• Guo, Z. and Hall, R. (1989). Parallel thinning with two-subiteration algorithms, Communications of the ACM 32(3): 359-373, DOI: 10.1145/62065.62074.
• Kardos, P., Nemeth, G. and Palagyi, K. (2009). An order independent sequential thinning algorithm, in P. Wiederhold and R. Barneva (Eds.), Combinatorial Image Analysis, Lecture Notes in Computer Science, Vol. 5852, Springer, Berlin/Heidelberg, pp. 162-175, DOI: 10.1007/978-3-642-10210-3_13.
• Kong, T.Y. and Rosenfeld, A. (1989). Digital topology: Introduction and survey, Computer Vision, Graphics, and Image Processing 48(3): 357-393, DOI: 10.1016/0734-189X(89)90147-3.
• Lam, L., Lee, S. and Sueni, C. (1991). Thinning methodologies-a comprehensive survey, IEEE Transactions on Pattern Analysis and Machine Intelligence 14(9): 869-885, DOI: 10.1109/34.161346.
• Misztal, K., Szczepański, A., Kocjan, P., Saeed, K. and Tabor, J. (2013). Distribution estimation applied to face recognition as a simple and robust solution, 2013 International Conference on Biometrics and Kansei Engineering (ICBAKE), Tokyo, Japan, DOI: 10.1109/ICBAKE.2013.19.
• Prakash, R., Prakash, K.S. and Binu, V. (2015). Thinning algorithm using hypergraph based morphological operators, 2015 IEEE International Advance Computing Conference (IACC), Benglore, India, pp. 1026-1029.
• Rutovitz, D. (1966). Pattern recognition, Journal of the Royal Statistical Society: Series A (General) 129(4): 504-530.
• Saeed, K., Rybnik, M. and Tabedzki, M. (2001). Implementation and advanced results on the non-interrupted skeletonization algorithm, in W. Skarbek (Ed.), Computer Analysis of Images and Patterns, Lecture Notes in Computer Science, Vol. 2124, Springer, Berlin/Heidelberg, pp. 601-609.
• Saeed, K., Tabędzki, M., Rybnik, M. and Adamski, M. (2010). K3M: A universal algorithm for image skeletonization and a review of thinning techniques, International Journal of Applied Mathematics and Computer Science 20(2): 317-335, DOI: 10.2478/v10006-010-0024-4.
• Xie, F., Xu, G., Cheng, Y. and Tian, Y. (2011). Human body and posture recognition system based on an improved thinning algorithm, IET Image Processing 5(5): 420-428, DOI: 10.1049/iet-ipr.2009.0303.
• Zhang, T. and Suen, C. (1984). A fast parallel algorithm for thinning digital patterns, Communications of the ACM 27(3): 236-239.

Identyfikatory

DOI

10.1515/amcs-2016-0031