Abstract
The skeletonization of an image consists of converting the initial image into a more compact representation. In general, the skeleton preserves the basic structure and, in some sense, keeps the meaning. The most important features concerning a shape are its topology (represented by connected components, holes, etc.) and its geometry (elongated parts, ramifications, etc.), thus they must be preserved. Skeletonization is usually considered as a pre-processing step in pattern recognition algorithms, but its study is also interesting by itself for the analysis of line-based images such as texts, line drawings, human fingerprints classification or cartography.
Since the introduction of the concept by Blum in 1962 under the name of medial axis transform, many algorithms have been published in this topic and there are many different approaches to the problem, among them the ones based on distance transform of the shape and skeleton pruning based on branch analysis. In this chapter, we focus on how the skeletonization of an image can be studied in the Cellular Automata framework and, as a case study, we consider in detail the Guo and Hall skeletonizing algorithm.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Acerbi, L., Dennunzio, A., Formenti, E.: Conservation of some dynamical properties for operations on cellular automata. Theoretical Computer Science 410(38-40), 3685–3693 (2009)
Altuwaijri, M., Bayoumi, M.: A new thinning algorithm for Arabic characters using self-organizing neural network. In: 1995 IEEE International Symposium on Circuits and Systems, ISCAS 1995, vol. 3, pp. 1824–1827 (1995)
Ammann, C., Sartori Angus, A.: Fast thinning algorithm for binary images. Image Vision and Computing 3(2), 71–79 (1985)
Arcelli, C., di Baja, G.S.: Euclidean skeleton via centre-of-maximal-disc extraction. Image and Vision Computing 11(3), 163–173 (1993)
Attali, D., Boissonnat, J.D., Edelsbrunner, H.: Stability and Computation of Medial Axes - a State-of-the-Art Report. In: Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration, ch. 6, pp. 109–125. Springer, Heidelberg (2009)
di Baja, G.S., Thiel, E.: Skeletonization algorithm running on path-based distance maps. Image and Vision Computing 14(1), 47–57 (1996)
Baruch, O.: Line thinning by line following. Pattern Recognition Letters 8(4), 271–276 (1988)
Betel, H., Flocchini, P.: On the relationship between fuzzy and boolean cellular automata. Theoretical Computer Science 412(8-10), 703–713 (2011)
Biasotti, S., Attali, D., Boissonnat, J.D., Edelsbrunner, H., Elber, G., Mortara, M., Baja, G.S., Spagnuolo, M., Tanase, M., Veltkamp, R.: Skeletal structures. In: Floriani, L., Spagnuolo, M. (eds.) Shape Analysis and Structuring, Mathematics and Visualization, pp. 145–183. Springer, Heidelberg (2008)
Blum, H.: An associative machine for dealing with the visual field and some of its biological implications. In: Bernard, E.E., Kare, M.R. (eds.) Biological Prototypes and Synthetic Systems, vol. 1, pp. 244–260. Plenum Press, New York (1962), Proceedings of the 2nd Annual Bionics Symposium, held at Cornell University (1961)
Blum, H.: An associative machine for dealing with the visual field and some of its biological implications. In: Computer and Mathematical Sciences Laboratory, Electronics Research Directorate, Air Force Cambridge Research Laboratories, Office of Aerospace Research. United States Air Force (1962)
Cattaneo, G., Dennunzio, A., Margara, L.: Solution of some conjectures about topological properties of linear cellular automata. Theoretical Computer Science 325(2), 249–271 (2004), Theoretical Aspects of Cellular Automata
Chauhan, S.: Survey paper on training of cellular automata for image. International Journal of Engineering and Computer Science 2(4), 980–985 (2013)
Chen, Y.S.: The use of hidden deletable pixel detection to obtain bias-reduced skeletons in parallel thinning. In: Proceedings of the 13th International Conference on Pattern Recognition, vol. 2, pp. 91–95. IEEE Computer Society, Washington, DC (1996)
Chen, Y.S., Hsu, W.H.: Systematic approach for designing 2-subcycle and pseudo 1-subcycle parallel thinning algorithms. Pattern Recognition 22(3), 267–282 (1989)
Dinneen, G.P.: Programming pattern recognition. In: Proceedings of the Western Joint Computer Conference, AFIPS 1955 (Western), pp. 94–100. ACM, New York (1955)
Dufresne, T.E., Sarwal, A., Dhawan, A.P.: A gray-level thinning method for delineation and representation of arteries. Computerized Medical Imaging and Graphics 18(5), 343–355 (1994)
Favre, A., Keller, H.: Parallel syntactic thinning by recoding of binary pictures. Computer Vision, Graphics, and Image Processing 23(1), 99–112 (1983)
Gil Montoya, M., Garcia, I.: Implementation of parallel thinning algorithms on multicomputers: analysis of the work load balance. In: Proceedings of the Sixth Euromicro Workshop on Parallel and Distributed Processing, PDP 1998, pp. 257–263 (1998)
González, R.C., Woods, R.E.: Digital image processing. Pearson/Prentice Hall (2008)
Guo, Z., Hall, R.W.: Parallel thinning with two-subiteration algorithms. Communications of the ACM 32, 359–373 (1989)
Guo, Z., Hall, R.W.: Fast fully parallel thinning algorithms. CVGIP: Image Understanding 55, 317–328 (1992)
Hernandez, G., Herrmann, H.: Cellular-automata for elementary image-enhancement. Graphical Models and Image Processing 58(1), 82–89 (1996)
Heydorn, S., Weidner, P.: Optimization and performance analysis of thinning algorithms on parallel computers. Parallel Computing 17(1), 17–27 (1991)
Hilditch, C.: An application of graph theory in pattern recognition. Machine Intelligence 3, 325–347 (1968)
Holt, C., Stewart, A.: A parallel thinning algorithm with fine grain subtasking. Parallel Computing 10(3), 329–334 (1989)
Hongbin, P., Junali, C., Yashe, Z.: Fingerprint thinning algorithm based on mathematical morphology. In: 8th International Conference on Electronic Measurement and Instruments, ICEMI 2007, pp. 2–618–2–621 (2007)
Kirsch, R.A., Cahn, L., Ray, C., Urban, G.H.: Experiments in processing pictorial information with a digital computer. In: Papers and Discussions Presented at the December 9-13, Eastern Joint Computer Conference: Computers with Deadlines to Meet, IRE-ACM-AIEE 1957 (Eastern), pp. 221–229. ACM, New York (1958)
Lee, K.H., Cho, S.B., Choy, Y.C.: Automated vectorization of cartographic maps by a knowledge-based system. Engineering Applications of Artificial Intelligence 13(2), 165–178 (2000)
Liu, L.: 3D thinning on cell complexes for computing curve and surface skeletons. Washington University (2009)
Liu, L., Chambers, E.W., Letscher, D., Ju, T.: A simple and robust thinning algorithm on cell complexes. Computer Graphics Forum 29(7), 2253–2260 (2010)
Lü, H.E., Wang, P.S.P.: A comment on a fast parallel algorithm for thinning digital patterns. Communications of the ACM 29(3), 239–242 (1986)
Nedzved, A., Ilyich, Y., Ablameyko, S., Kamata, S.: Color thinning with applications to biomedical images. In: Skarbek, W. (ed.) CAIP 2001. LNCS, vol. 2124, pp. 256–263. Springer, Heidelberg (2001)
Pavlidis, T.: Algorithms for Graphics and Image Processing. Digital system design series. Computer Science Press (1982)
Peña-Cantillana, F., Berciano, A., Díaz-Pernil, D., Gutiérrez-Naranjo, M.A.: Parallel skeletonizing of digital images by using cellular automata. In: Ferri, M., Frosini, P., Landi, C., Cerri, A., Di Fabio, B. (eds.) CTIC 2012. LNCS, vol. 7309, pp. 39–48. Springer, Heidelberg (2012)
Rosenfeld, A.: A characterization of parallel thinning algorithms. Information and Control 29(3), 286–291 (1975)
Rosin, P.L.: Training cellular automata for image processing. IEEE Transactions on Image Processing 15(7), 2076–2087 (2006)
Rutovitz, D.: Pattern recognition. Journal of the Royal Statistical Society 129, 504–530 (1966)
Saeed, K., Tabedzki, M., Rybnik, M., Adamski, M.: K3M: A universal algorithm for image skeletonization and a review of thinning techniques. Applied Mathematics and Computer Science 20(2), 317–335 (2010)
de Saint Pierre, T., Milgram, M.: New and efficient cellular algorithms for image processing. CVGIP: Image Understanding 55(3), 261–274 (1992)
Siddiqi, K., Pizer, S.: Medial representations: mathematics, algorithms and applications. Computational imaging and vision. Springer (2008)
Smith, S.J., Bourgoin, M.O., Sims, K., Voorhees, H.L.: Handwritten character classification using nearest neighbor in large databases. IEEE Transactions on Pattern Analysis and Machine Intelligence 16(9), 915–919 (1994)
Suzuki, S., Abe, K.: Binary picture thinning by an iterative parallel two-subcycle operation. Pattern Recognition 20(3), 297–307 (1987)
Ye, Q.Z., Danielsson, P.E.: Inspection of printed circuit boards by connectivity preserving shrinking. IEEE Transactions on Pattern Analysis and Machine Intelligence 10(5), 737–742 (1988)
Zhang, T.Y., Suen, C.Y.: A fast parallel algorithm for thinning digital patterns. Communications of the ACM 27(3), 236–239 (1984)
Zhang, Y.Y., Wang, P.S.P.: A parallel thinning algorithm with two-subiteration that generates one-pixel-wide skeletons. In: Proceedings of the 13th International Conference on Pattern Recognition, vol. 4, pp. 457–461 (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Díaz-Pernil, D., Peña-Cantillana, F., Gutiérrez-Naranjo, M.A. (2014). Skeletonizing Digital Images with Cellular Automata. In: Rosin, P., Adamatzky, A., Sun, X. (eds) Cellular Automata in Image Processing and Geometry. Emergence, Complexity and Computation, vol 10. Springer, Cham. https://doi.org/10.1007/978-3-319-06431-4_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-06431-4_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06430-7
Online ISBN: 978-3-319-06431-4
eBook Packages: EngineeringEngineering (R0)