A modified K3M thinning algorithm

• Autorzy: Tabedzki M. , Saeed K. , Szczepański A.

Identyfikatory

DOI

10.1515/amcs-2016-0031

• 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 algorithm; K3M algorithm; digital image processing

PL

szkieletyzacja; pocienianie; algorytm K3M; cyfrowe przetwarzanie obrazu

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2016
• Tom: Vol. 26, no. 2
• Strony: 439--450
• Opis fizyczny: Bibliogr. 17 poz., rys., tab.

Twórcy

autor

Tabedzki M.

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

autor

Saeed K.

• 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

Szczepański A.

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

Bibliografia

• [1] 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.
• [2] 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.
• [3] 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.
• [4] 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.
• [5] 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.
• [6] 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.
• [7] 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.
• [8] 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.
• [9] 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.
• [10] 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.
• [11] 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.
• [12] 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.
• [13] Rutovitz, D. (1966). Pattern recognition, Journal of the Royal Statistical Society: Series A (General) 129(4): 504–530.
• [14] 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.
• [15] 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.
• [16] 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.
• [17] Zhang, T. and Suen, C. (1984). A fast parallel algorithm for thinning digital patterns, Communications of the ACM 27(3): 236–239.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.