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

Khalid Saeed; Marek Tabędzki; Mariusz Rybnik; Marcin Adamski

doi:10.2478/v10006-010-0024-4

Abstract

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.

References

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.10.1109/TPAMI.2002.1114862
Search in Google Scholar
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.10.1109/82.661669
Search in Google Scholar
Ammann, C. J. and Sartori-Angus, A. G. (1985). Fast thinning algorithm for binary images, Image Vision and Computing 3(2): 71-79.10.1016/0262-8856(85)90015-0
Search in Google Scholar
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.
Search in Google Scholar
Arcelli, C. (1981). Pattern thinning by contour tracing, Computer Graphics Image Processing 17(2): 130-144.10.1016/0146-664X(81)90021-6
Search in Google Scholar
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.10.1109/TSMC.1978.4309914
Search in Google Scholar
Arcelli, C. and di Baja, G. S. (1981). A thinning algorithm based on prominence detection, Pattern Recognition 13(3): 225-235.10.1016/0031-3203(81)90099-6
Search in Google Scholar
Arcelli, C. and di Baja, G. S. (1987). A contour characterization for multiply connected figures, Pattern Recognition Letters 6(4): 245-249.10.1016/0167-8655(87)90084-5
Search in Google Scholar
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.1109/34.19037
Search in Google Scholar
Baruch, O. (1988). Line thinning by line following, Pattern Recognition Letters 8(4): 271-276.10.1016/0167-8655(88)90034-7
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
Chen, Y.-S. and Hsu, W.-H. (1988). A modified fast parallel algorithm for thinning digital patterns, Pattern Recognition Letters 7(2): 99-106.10.1016/0167-8655(88)90124-9
Search in Google Scholar
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 1-shape pattern, Proceedings of the International Conference on Computer Vision and Pattern Recognition, San Diego, CA, USA, pp. 208-215.
Search in Google Scholar
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.10.1016/0031-3203(89)90075-7
Search in Google Scholar
Chen, Y.-S. and Hsu, W.-H. (1990). A comparison of some one-pass parallel thinnings, Pattern Recognition Letters 11(1): 35-41.10.1016/0167-8655(90)90053-5
Search in Google Scholar
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.10.1016/0734-189X(87)90054-5
Search in Google Scholar
Dinnen, G. (1955). Programming pattern recognition, Proceedings of the Western Joint Computer Conference, Los Angeles, CA, USA, pp. 94-100.
Search in Google Scholar
Dyer, C. and Rosenfeld, A. (1979). Thinning algorithms for gray-scale pictures, IEEE Transactions on Pattern Analysis and Machine Intelligence 1(1): 88-89.10.1109/TPAMI.1979.4766880
Search in Google Scholar
Favre, A. and Keller, H. (1983). Parallel syntactic thinning by recoding of binary pictures, Computer Vision, Graphics, and Image Processing 23(1): 99-112.10.1016/0734-189X(83)90056-7
Search in Google Scholar
Gonzalez, R. C. and Woods, R. E. (2007). Digital Image Processing, 3rd Edition, Prentice Hall, Upper Saddle River, NJ.
Search in Google Scholar
Guo, Z. and Hall, R. W. (1989). Parallel thinning with two-subiteration algorithms, Communications of the ACM 32(3): 359-373.10.1145/62065.62074
Search in Google Scholar
Guo, Z. and Hall, R. W. (1992). Fast fully parallel thinning algorithms, CVGIP: Image Understanding 55(3): 317-328.10.1016/1049-9660(92)90029-3
Search in Google Scholar
Hilditch, C. J. (1968). An application of graph theory in pattern recognition, Machine Intelligence 3: 325-347.
Search in Google Scholar
Hilditch, C. J. (1969). Linear skeletons from square cupboards, Machine Intelligence 4: 403-420.
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
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.10.1109/34.166630
Search in Google Scholar
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.
Search in Google Scholar
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.10.1016/j.cad.2007.02.006208435218449328
Search in Google Scholar
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.
Search in Google Scholar
Klette, R. and Rosenfeld, A. (2004). Digital Geometry: Geometric Methods for Digital Image Analysis, Morgan Kaufmann, San Francisco, CA.10.1016/B978-155860861-0/50005-5
Search in Google Scholar
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.10.1109/34.161346
Search in Google Scholar
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.
Search in Google Scholar
Malina, W., Ablemeyko, S. and Pawlak, W. (2002). Fundamentals of Digital Image Processing, Akademicka Oficyna Wydawnicza EXIT, Warsaw, (in Polish).
Search in Google Scholar
Mallat, S. (1989). A theory for multiresolution signal decomposition: The wavelet representation, IEEE Transactions on Pattern Analysis and Machine Intelligence 11(7): 674-693.10.1109/34.192463
Search in Google Scholar
Parker, J., Jennings, C. and Molaro, D. (1994). A force-based thinning strategy with sub-pixel precision, Vision Interface Conference, Banff, Alberta, Canada.10.1142/9789812812483_0008
Search in Google Scholar
Pavlidis, T. (1980). A thinning algorithm for discrete binary images, Computer Graphics Image Processing 13(2): 142-157.10.1016/S0146-664X(80)80037-2
Search in Google Scholar
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.
Search in Google Scholar
Pavlidis, T. (1982a). Algorithms for Graphics and Image Processing, Springer, Computer Science Press, Rockville, MD.10.1007/978-3-642-93208-3
Search in Google Scholar
Pavlidis, T. (1982b). An asynchronous thinning algorithm, Computer Graphics Image Processing 20(2): 133-157.10.1016/0146-664X(82)90041-7
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
Rockett, P. I. (2005). An improved rotation-invariant thinning algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence 27(10): 1671-1674.10.1109/TPAMI.2005.19116238001
Search in Google Scholar
Rosenfeld, A. (1975). A characterization of parallel thinning algorithms, Information and Control 29(3): 286-291, http://theory.lcs.mit.edu/~iandc/ic75.html http://theory.lcs.mit.edu/~iandc/ic75.html
Search in Google Scholar
Rutovitz, D. (1966). Pattern recognition, Journal of Royal Statistical Society 129(4): 504-530.10.2307/2982255
Search in Google Scholar
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.
Search in Google Scholar
Saeed, K. (2004). Image Analysis for Object Recognition, Białystok Technical University Press, Białystok.
Search in Google Scholar
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.
Search in Google Scholar
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.10.1007/3-540-44692-3_72
Search in Google Scholar
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.
Search in Google Scholar
You, X. and Tang, Y. Y. (2007). Wavelet-based approach to character skeleton, IEEE Transactions on Image Processing 16(5): 1220-1231.10.1109/TIP.2007.89180017491454
Search in Google Scholar
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.
Search in Google Scholar

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

Abstract

Paradigm

My account