K3M: A universal algorithm for image skeletonization and a review of thinning techniques

Saeed, K. ; Tabędzki, M. ; Rybnik, M. ; Adamski, M.

International Journal of Applied Mathematics and Computer Science, Tome 20 (2010) no. 2, pp. 317-335.

Résumé

This paper aims at three aspects closely related to each other: first, it presents the state of the art in the area of thinning methodologies, by giving descriptions of general ideas of the most significant algorithms with a comparison between them. Secondly, it proposes a new thinning algorithm that presents interesting properties in terms of processing quality and algorithm clarity, enriched with examples. Thirdly, the work considers parallelization issues for intrinsically sequential algorithms of thinning. The main advantage of the suggested algorithm is its universality, which makes it useful and versatile for a variety of applications.

Détail

Keywords: skeletonization, thinning, digital image processing, parallelization, iteration, thinning methodologies, sequential thinning, parallel thinning
Mots-clés : szkieletyzacja, obraz cyfrowy, przetwarzanie obrazu, przetwarzanie równoległe

Bibliographie

[1] Ahmed, M. and Ward, R. (2002). A rotation invariant rule based thinning algorithm for character recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence 24(12): 1672-1678.

[2] Altuwaijri, M.M. and Bayoumi, M.A. (1998). A thinning algorithm for arabic characters using art2 neural network, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 45(2): 260-264.

[3] Ammann, C.J. and Sartori-Angus, A.G. (1985). Fast thinning algorithm for binary images, Image Vision and Computing 3(2): 71-79.

[4] Andreadis, I., Vardavoulia, M., Louverdis, G. and Papamarkos, N. (2000). Colour image skeletonisation, Proceedings of the 10th European Signal Processing Conference, Tampere, Finland, Vol. 4, pp. 2389-2392.

[5] Arcelli, C. (1981). Pattern thinning by contour tracing, Computer Graphics Image Processing 17(2): 130-144.

[6] Arcelli, C. and di Baja, G.S. (1978). On the sequential approach to medial line transformation, IEEE Transactions on Systems, Man and Cybernetics 8(2): 139-144.

[7] Arcelli, C. and di Baja, G.S. (1981). A thinning algorithm based on prominence detection, Pattern Recognition 13(3): 225-235.

[8] Arcelli, C. and di Baja, G.S. (1987). A contour characterization for multiply connected figures, Pattern Recognition Letters 6(4): 245-249.

[9] Arcelli, C. and di Baja, G.S. (1989). A one-pass two-operation process to detect the skeletal pixels on the 4-distance transform, IEEE Transactions on Pattern Analysis and Machine Intelligence 11(4): 411-414.

[10] Baruch, O. (1988). Line thinning by line following, Pattern Recognition Letters 8(4): 271-276.

[11] Blum, H. (1967). A transformation for extracting new descriptors of shape, in W.W. Dunn (Ed.), Models for the Perception of Speech and Visual Form, MIT Press, Cambridge, MA, pp. 362-380.

[12] Chen, Y.-S. (1996). The use of hidden deletable pixel detection to obtain bias-reduced skeletons in parallel thinning, ICPR '96: Proceedings of the 13th International Conference on Pattern Recognition, Washington, DC, USA, pp. 91-95.

[13] Chen, Y.-S. and Hsu, W.-H. (1988). A modified fast parallel algorithm for thinning digital patterns, Pattern Recognition Letters 7(2): 99-106.

[14] Chen, Y.-S. and Hsu, W.-H. (1989a). A 1-subcycle parallel thinning algorithm for producing perfect 8-curves and obtaining isotropic skeleton of an l-shape pattern, Proceedings of the International Conference on Computer Vision and Pattern Recognition, San Diego, CA, USA, pp. 208-215.

[15] Chen, Y.-S. and Hsu, W.-H. (1989b). A systematic approach for designing 2-subcycle and pseudo 1-subcycle parallel thinning algorithms, Pattern Recognition 22(3): 267-282.

[16] Chen, Y.-S. and Hsu, W.-H. (1990). A comparison of some one-pass parallel thinnings, Pattern Recognition Letters 11(1): 35-41.

[17] Chin, R.T., Wan, H.-K., Stover, D.L. and Iverson, R. D. (1987). A one-pass thinning algorithm and its parallel implementation, Computer Vision, Graphics, and Image Processing 40(1): 30-40.

[18] Dinnen, G. (1955). Programming pattern recognition, Proceedings of the Western Joint Computer Conference, Los Angeles, CA, USA, pp. 94-100.

[19] Dyer, C. and Rosenfeld, A. (1979). Thinning algorithms for gray-scale pictures, IEEE Transactions on Pattern Analysis and Machine Intelligence 1(1): 88-89.

[20] Favre, A. and Keller, H. (1983). Parallel syntactic thinning by recoding of binary pictures, Computer Vision, Graphics, and Image Processing 23(1): 99-112.

[21] Gonzalez, R.C. and Woods, R.E. (2007). Digital Image Processing, 3rd Edition, Prentice Hall, Upper Saddle River, NJ.

[22] Guo, Z. and Hall, R.W. (1989). Parallel thinning with two subiteration algorithms, Communications of the ACM 32(3): 359-373.

[23] Guo, Z. and Hall, R.W. (1992). Fast fully parallel thinning algorithms, CVGIP: Image Understanding 55(3): 317-328.

[24] Hilditch, C.J. (1968). An application of graph theory in pattern recognition, Machine Intelligence 3: 325-347.

[25] Hilditch, C.J. (1969). Linear skeletons from square cupboards, Machine Intelligence 4: 403-420.

[26] Huang, L., Wan, G. and Liu, C. (2003). An improved parallel thinning algorithm, ICDAR '03: Proceedings of the Seventh International Conference on Document Analysis and Recognition, Washington, DC, USA, pp. 780-783.

[27] Jaisimha, M.Y., Haralick, R.M. and Dori, D. (1994). Quantitative performance evaluation of thinning algorithms under noisy conditions, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Seattle, WA, USA, pp. 678-683.

[28] Jang, B.K. and Chin, R.T. (1992). One-pass parallel thinning: Analysis, properties and quantitative evaluation, Transactions on Pattern Analysis and Machine Intelligence 14(11): 1129-1140.

[29] Ji, X. and Feng, J. (2004). A new approach to thinning based on time-reversed heat conduction model, International Conference on Image Processing (ICIP), Singapore, Vol. 1, pp. 653-656.

[30] Ju, T., Baker, M.L. and Chiu, W. (2007). Computing a family of skeletons of volumetric models for shape description, Computer-Aided Design 39(5): 352-360.

[31] Kirsch, R.A., Cahn, L., Ray, C. and Urban, G.H. (1958). Experiments in processing pictorial information with a digital computer, IRE-ACM-AIEE '57 (Eastern): Papers and Discussions Presented at the December 9-13, 1957, Eastern Joint Computer Conference: Computers with Deadlines to Meet, New York, NY, USA, pp. 221-229.

[32] Klette, R. and Rosenfeld, A. (2004). Digital Geometry: Geometric Methods for Digital Image Analysis, Morgan Kaufmann, San Francisco, CA.

[33] Lam, L., Lee, S.-W. and Suen, C.Y. (1992). Thinning methodologies-A comprehensive survey, IEEE Transactions on Pattern Analysis and Machine Intelligence 14(9): 869-885.

[34] Lee, S.-W., Lam, L. and Suen, C. Y. (1991). Performance evaluation of skeletonizing algorithms for document image processing, Proceedings of the First International Conference on Document Analysis and Recognition, Saint-Malo, France, pp. 260-271.

[35] Malina, W., Ablemeyko, S. and Pawlak, W. (2002). Fundamentals of Digital Image Processing, Akademicka Oficyna Wydawnicza EXIT, Warsaw, (in Polish).

[36] Mallat, S. (1989). A theory for multiresolution signal decomposition: The wavelet representation, IEEE Transactions on Pattern Analysis and Machine Intelligence 11(7): 674-693.

[37] Parker, J., Jennings, C. and Molaro, D. (1994). A force-based thinning strategy with sub-pixel precision, Vision Interface Conference, Banff, Alberta, Canada.

[38] Pavlidis, T. (1980). A thinning algorithm for discrete binary images, Computer Graphics Image Processing 13(2): 142-157.

[39] Pavlidis, T. (1981). A flexible parallel thinning algorithm, Proceedings of the International Conference on Pattern Recognition and Image Processing, Dallas, TX, USA, pp. 162-167.

[40] Pavlidis, T. (1982a). Algorithms for Graphics and Image Processing, Springer, Computer Science Press, Rockville, MD.

[41] Pavlidis, T. (1982b). An asynchronous thinning algorithm, Computer Graphics Image Processing 20(2): 133-157.

[42] Pervouchine, V. and Leedham, G. (2005). Document examiner feature extraction: Thinned vs. skeletonised handwriting images, Proceedings of the IEEE Region 10 Technical Conference (TENCON05), Melbourne, Australia, pp. 1-6.

[43] Quadros,W. R., Shimada, K. and Owen, S. J. (2004). 3d discrete skeleton generation by wave propagation on pr-octree for finite element mesh sizing, SM '04: Proceedings of the Ninth ACM Symposium on Solid Modeling and Applications, Aire-la-Ville, Switzerland, pp. 327-332.

[44] Rockett, P. I. (2005). An improved rotation-invariant thinning algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence 27(10): 1671-1674.

[45] Rosenfeld, A. (1975). A characterization of parallel thinning algorithms, Information and Control 29(3): 286-291, http://theory.lcs.mit.edu/~iandc/ic75.html

[46] Rutovitz, D. (1966). Pattern recognition, Journal of Royal Statistical Society 129(4): 504-530.

[47] Saeed, K. (2001). Text and image processing: Non-interrupted skeletonization, Proceedings of the 1st International IEEE Conference on Circuits, Systems, Comunications and Computers-IEEE-CSCC'01, Crete, Greece, Advances in Scientific Computing, Computational Intelligence and Applications, World Scientific Engineering Society Press, pp. 350-354.

[48] Saeed, K. (2004). Image Analysis for Object Recognition, Białystok Technical University Press, Białystok.

[49] Saeed, K. and Niedzielski, R. (1999). Experiments on thinning of cursive-style alphabets, International Conference on Information Technologies for Education, Science and Business ITESB'99, Minsk, Belarus, pp. 45-49.

[50] 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-Verlag, Heidelberg, pp. 601-609.

[51] Wan, Y., Yao, L., Xu, B. and Zeng, P. (2008). A distance map based skeletonization algorithm and its application in fiber recognition, International Conference on Audio, Language and Image Processing, Shanghai, China, pp. 1769-1774.

[52] You, X. and Tang, Y. Y. (2007). Wavelet-based approach to character skeleton, IEEE Transactions on Image Processing 16(5): 1220-1231.

[53] Zhang, Y. Y. and Wang, P. P. (1996). A parallel thinning algorithm with two-subiteration that generates one-pixel-wide skeletons, International Conference on Pattern Recognition, Vienna, Austria, Vol. 4, pp. 457-461.