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.
@article{bwmeta1.element.bwnjournal-article-amcv26i2p439bwm,
author = {Marek Tabedzki and Khalid Saeed and Adam Szczepa\'nski},
title = {A modified K3M thinning algorithm},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {26},
year = {2016},
pages = {439-450},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv26i2p439bwm}
}
Marek Tabedzki; Khalid Saeed; Adam Szczepański. A modified K3M thinning algorithm. International Journal of Applied Mathematics and Computer Science, Tome 26 (2016) pp. 439-450. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv26i2p439bwm/
[000] 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.
[001] 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.
[002] 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.
[003] 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.
[004] 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.
[005] 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.
[006] 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.
[007] 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. | Zbl 1267.68289
[008] 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.
[009] 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.
[010] 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.
[011] 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.
[012] Rutovitz, D. (1966). Pattern recognition, Journal of the Royal Statistical Society: Series A (General) 129(4): 504-530.
[013] 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. | Zbl 1005.68845
[014] 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. | Zbl 1194.94040
[015] 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.
[016] Zhang, T. and Suen, C. (1984). A fast parallel algorithm for thinning digital patterns, Communications of the ACM 27(3): 236-239.