Parallel thinning and skeletonization algorithm based on cellular automaton
- PDF / 3,429,364 Bytes
- 18 Pages / 439.642 x 666.49 pts Page_size
- 74 Downloads / 189 Views
Parallel thinning and skeletonization algorithm based on cellular automaton Fan Zhang1,2 · Xiaopan Chen1 · Xinhong Zhang3 Received: 1 June 2019 / Revised: 23 June 2020 / Accepted: 18 August 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper proposes a parallel image thinning algorithm and a skeletonization algorithm based on cellular automaton (CA). Cellular automaton is a parallel computation model and a non-linear dynamical system. In this paper, each image pixel is identified as a cell of CA and the change of cell depends on the current state of itself and the state of its neighbors. In a binary image, this paper assumes that the objects (white pixel) are preys which are surrounded by many ants (every black pixels). The movement of ants is controlled by cellular automation. The ants gnaw preys until the preys (objects) become skeleton. The proposed parallel skeletonization algorithm can produce a traditional skeleton with a thin line located in the center of object, and the proposed thinning algorithm can produce a new kind of skeleton which is named as the ants-gnawing skeleton. The computation of ants-gnawing skeleton is faster than the traditional skeleton while it contains more the structural features of image. Benefiting from the properties of cellular automation, the proposed thinning algorithm does not change the basic geometry structure of image, and it is invariant for image rotation. Keywords Thinning algorithm · Skeletonization algorithm · Cellular automation · Parallel computation
Xiaopan Chen
[email protected] Xinhong Zhang
[email protected] Fan Zhang [email protected] 1
School of Computer and Information Engineering, Henan University, Kaifeng, 475004, China
2
Henan Key Laboratory of Big Data Analysis and Processing, Henan University, Kaifeng, 475004, China
3
School of Software, Henan University, Kaifeng, 475004, China
Multimedia Tools and Applications
1 Introduction The image thinning and skeletonization algorithms are methods that convert an image into a more compact representation in the mean while keeping the meaningful features of image. In the image, an object is reduced to a curve skeleton consisting of one-dimensional structures. The object’s skeleton contains not only the shape features but also the topological structures, therefore it is a useful and essential descriptor for the object recognition and other related applications, such as the object description, image retrieval, image manipulation, image matching, image registration, object tracking, image recognition, and image compression [11–13, 42]. The concept of skeleton is firstly introduced by Blum as a result of the Medial Axis Transform (MAT) or Symmetry Axis Transform (SAT) [15]. Blum’s skeleton is defined by a grass-fire transform process in which the object is assumed to be a field of dry grass and a fire is simultaneously lit at all the boundary points. The fire propagates inside the object at a uniform velocity. The final skeleton is the set that the fire fro
Data Loading...
