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

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

International Journal of Applied Mathematics and Computer Science (2010)

  • Volume: 20, Issue: 2, page 317-335
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Khalid Saeed, et al. "K3M: a universal algorithm for image skeletonization and a review of thinning techniques." International Journal of Applied Mathematics and Computer Science 20.2 (2010): 317-335. <http://eudml.org/doc/207990>.

@article{KhalidSaeed2010,
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.},
author = {Khalid Saeed, Marek Tabędzki, Mariusz Rybnik, Marcin Adamski},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {skeletonization; thinning; digital image processing; parallelization; iteration; thinning methodologies; sequential thinning; parallel thinning},
language = {eng},
number = {2},
pages = {317-335},
title = {K3M: a universal algorithm for image skeletonization and a review of thinning techniques},
url = {http://eudml.org/doc/207990},
volume = {20},
year = {2010},
}

TY - JOUR
AU - Khalid Saeed
AU - Marek Tabędzki
AU - Mariusz Rybnik
AU - Marcin Adamski
TI - K3M: a universal algorithm for image skeletonization and a review of thinning techniques
JO - International Journal of Applied Mathematics and Computer Science
PY - 2010
VL - 20
IS - 2
SP - 317
EP - 335
AB - 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.
LA - eng
KW - skeletonization; thinning; digital image processing; parallelization; iteration; thinning methodologies; sequential thinning; parallel thinning
UR - http://eudml.org/doc/207990
ER -

References

top
  1. Ahmed, M. and Ward, R. (2002). A rotation invariant rulebased 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. Zbl0800.68797
  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. 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. 
  20. 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. 
  21. 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. 
  22. 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. 
  23. Hilditch, C.J. (1969). Linear skeletons from square cupboards, Machine Intelligence 4: 403-420. 
  24. Hilditch, C.J. (1968). An application of graph theory in pattern recognition, Machine Intelligence 3: 325-347. Zbl0197.14701
  25. Guo, Z. and Hall, R.W. (1992). Fast fully parallel thinning algorithms, CVGIP: Image Understanding 55(3): 317-328. Zbl0780.68123
  26. Guo, Z. and Hall, R.W. (1989). Parallel thinning with twosubiteration algorithms, Communications of the ACM 32(3): 359-373. 
  27. Gonzalez, R.C. and Woods, R.E. (2007). Digital Image Processing, 3rd Edition, Prentice Hall, Upper Saddle River, NJ. 
  28. Favre, A. and Keller, H. (1983). Parallel syntactic thinning by recoding of binary pictures, Computer Vision, Graphics, and Image Processing 23(1): 99-112. 
  29. Dyer, C. and Rosenfeld, A. (1979). Thinning algorithms for gray-scale pictures, IEEE Transactions on Pattern Analysis and Machine Intelligence 1(1): 88-89. 
  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. Zbl1064.68090
  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. Zbl0709.94650
  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. Zbl0482.68087
  41. Pavlidis, T. (1982b). An asynchronous thinning algorithm, Computer Graphics Image Processing 20(2): 133-157. Zbl0532.68084
  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 Zbl0334.68054
  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. Zbl1005.68845
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.