The skeleton is significant to the object representation and recognition. It can be applied in various areas, such as content-based image retrieval, computer graphics, character recognition and analysis of biomedical images [1]. The skeleton is an abstract of an object, which contains both an object's shape features and topological structure. Because of skeleton's importance for shape description, many algorithms have been developed to recognize objects' shapes by matching skeleton structures represented by graph or trees [2]-[5]. However, Current skeleton extraction algorithms are only adapted to simple shapes, which can not be applied to complex shapes like shapes in MPEG-7 data set [6]. The most significant limitation constraining the matching of skeletons is skeleton's sensitivity to an object's boundary deformation. The sensitivity means that the little noise and the disturbance of contour are possible to generate redundant skeleton protrusions, which may seriously disturb the topological structure of the object (see Fig. 1(a)).
In order to overcome the instability of the skeleton caused by boundary noise, a variety of techniques have been suggested for matching and recognizing shapes. Zhu and Yule [7]extract more than one skeleton to solve the problem. A similar shape descriptors based on self-similarity of a smooth outline is presented in [8]. Aslan and Tari [4]have proposed an unconventional method to shape recognition using disconnected skeletons. These methods have great stability to boundary deformation, but the obtained skeletons cannot represent the shape details. Presently, the most common approaches to overcome instability are based on skeleton pruning. Shaked and Buckstein [9] give a complete analysis and compare such pruning methods. Propagation velocity, maximal thickness, radius function, axis arc length, and the length of the boundary unfolded belong to the common significance measures of skeleton points. Multiscale pruning strategies such as the iteratively pruned trees of Voronoi edges have also been proposed in [10]. Siddiqi et al [11] combine a flux measurement with the thinning process to extract a robust and accurate connected skeleton. Skeleton pruning based on discrete curve evolution have been proposed in [12]. As an essential part of skeleton extraction algorithms, skeleton pruning algorithms usually appear in a variety of application-dependent formulations [9], [12]. Even in such cases, all presented methods have several drawbacks. They do not preserve the topological information of the original object [13], and they are not invariant under Euclidean transformations such as rotations and translations. Also, in many cases, such as objects with holes, they do not represent significant visual parts of objects.
Fig. 1: (a) sensitivity of a skeleton to boundary noise (b) The proposed method.
In this paper, we propose an approach that can completely remove redundant protrusions and obtain accurate skeleton and preserve the original topological property of a shape (see (b)). First of all, this paper proposes an effective and precise criterion for the extraction of connected skeleton based on signed sequential Euclidean distance map. This criterion is able to determine whether a given point is a skeleton point or not and calculate the skeleton point's discrete bisector angle. Then the discrete bisector angle based pruning algorithm can be used to effectively remove skeleton protrusions caused by boundary noise.
The rest of this paper is organized as follows: some basic concepts are explained in Section 2. In Section 3, we describe the skeleton extraction algorithm based on criterion. Then, In Section 4, we present the pruning algorithm based on bisector angle. Experimental results are stated in Section 5 and Section 6 is the conclusions.
Preliminaries
Suppose is continuum boundary of the object in an image and the planar shapedenotes the object's content inside the boundary . According to the definition of medial axis from Blum[1], planar shape 's skeleton is the set of maximal disks' center point. Medial axis transformation is defined as:
Medial axis transformation: Medial axis transformation is the set of maximal disks' center point of .
Where is the set of maximal disks; denotes the disk with a center point, and a radius of .
's maximal disk is included in , not in other disks and tangent with . It's easily to know that maximal disk is tangent with boundary including at least two tangent points and the distance between tangent point and skeleton point is shortest. If is a skeleton point and , are the tangent points. Bisector angle is defined as:
Bisector angle: is the bisector angle, and the range of the angle is from 0 to. If the maximal disk touches the boundary at more than two points, then the bisector angle is the largest angle. Indeed, the angle between any two tangent points is either close to 0 or close to the bisector angle [14].
Property of a skeleton point: The perpendicular bisector of chord of maximal disk definitely goes through skeleton point.
Skeleton extraction based on criterion
The criterion for a skeleton point
The width of the ideal skeleton should have been zero. The continuous boundary would generate connected skeleton. For a digital image, skeleton points must be located at the corresponding pixel points. However, there is the possibility that the skeleton does not go through the pixel points exactly because of the quantization noise of a digital image. Therefore, the width of the ideal skeleton should not be zero and the pixel points that the ideal skeleton go through should be considered as the skeleton points.
As shown in Fig. 2, the maximal disk of skeleton point p touches the boundary at and. Points and are the two nearest boundary points with respect to point. Pointsand pointare neighbor pixel points and the skeleton point is located at the line segment. Line segmentis parallel to line segmentand perpendicular to the direction of skeleton. is pixel's Euclidean distance and is pixel's Euclidean distance. Suppose that the coordinates of are respectively, and then the coordinates of point, which is the middle point of line segment, are. The slope for the perpendicular bisector of line segmentis equal to:
Fig. 2: the definition of skeleton.
According to the property of a skeleton point, the perpendicular bisector of line segmentdefinitely goes through point. Because of the quantization noise of a discrete image, the skeleton point would deviate possibly. Suppose that the perpendicular bisector of intersects the line segmentat and the coordinates of are. We assume that the width of the skeleton is one pixel unit. For the point, if is in the range of and middle point of, thenis considered as the skeleton point. That is:
If and, thenis considered as the skeleton point. Pointis the actual skeleton point in the image.
For the pixel points and , isn't equal to; however, for the skeleton point, is equal to. In this way, the width of the ideal skeleton is zero, and under the inequality condition, pointis the pixel point corresponding to the actual skeleton point. The maximalis the bisector angle.
The skeleton algorithm
To determine whether a point is a skeleton point or not, we need to know the given point's eight-neighborhood pixel points and it's corresponding nearest contour points. And then we can determine whether the given point is a skeleton point according to the criterion. If one point in the eight-neighborhood and the current point satisfy the criterion, then the current point is a skeleton point. Otherwise, if all the points in the eight-neighborhood and the current point don't satisfy the criterion, then the current point is not a skeleton point. The main steps of the skeleton algorithm are described as follows:
The point which has the maximal Euclidean distance in F is the first skeleton point, that is, the seed point. A seed-point queue needs to be maintained.
Take out the seed point from the head of the queue and determine whether the seed point's eight-neighborhood pixels satisfy the criterion of a skeleton point. If the pixel satisfies the criterion, it would be put in the tail of the queue and its bisector angle would be calculated.
The connected skeleton will be obtained until the seed-point queue is empty, and the skeleton algorithm is finished.
Skeleton pruning based on bisector angle
There would be many redundant protrusions according to the criterion of a skeleton point. In fact, quantization noise (sampling error) results in redundant protrusions, because not every sampling point is exactly located in the connected boundary. Therefore it's quite important and necessary to prune the redundant skeleton. This paper proposes a method in order to make sure that the pruned skeleton preserves its topological structure. At first, the critical points of the skeleton are determined based on the bisector angles. Then, on the basis of redundant skeleton, the critical points would be connected to obtain the pruned skeleton which can preserve the visual features of the original object
(a)
(b)
(c)
(d)
(e)
(f)
Fig. 3: bisector angle of the skeleton points.
In order to visualize the effect of noise, we take the distance of a skeleton point d（s）as the y-coordinate and take the bisector angle of a skeleton point b(s) as the x-coordinate. Therefore, any skeleton pint s (including the skeleton points on redundant protrusions) has the coordinates（b（s），d（s））in the Cartesian coordinate system, called a parameter graph .
In the continuous space, the bisector angle of the skeleton except at the multiple points is continuous [14] in a parameter graph as shown in Fig. 3(b). For the digital image, the parameter graph of skeleton points is complicated because of the existence of quantization noise. However, as shown in Fig. 3(d), the skeleton points in the right side of the red line are still close to the continuous curves. As shown in Fig. 3(e) and Fig. 3(f), most of the redundant skeleton points are located in the left side of the red line. Hence, most of the points whose bisector angles are too small are noise points. But setting a threshold for bisector angle can't make sure to get the connected skeleton. As shown in Fig. 4, the points in the right side of the red line in Fig. 4(b) are the red skeleton points in Fig. 4(a). Obviously, the skeleton points may be not continuous.
Critical point: The skeleton point whose bisector angle is larger than the threshold is the critical point.
Area of critical points: The number of the continuous key points is taken as the area of critical points, denoted as .
(a)
(b)
Fig. 4: skeleton point whose bisector angle is bigger than threshold.
In fact, there are still some noisy critical points because their bisector angles are large, but these points need to be removed, as shown in (the red point in the green circle). Therefore, we set the area of critical points as another threshold. The new set of critical points is obtained by deleting some critical points whose areas are too small. On the basis of the skeleton obtained from the criterion of a skeleton point, using Dijkstra's shortest path algorithm[15] connects all the critical points to get the pruned skeleton.
Fig. 5: noisy skeleton points.
For the objects with holes (the object with several boundaries), the skeleton points whose tangent points are located in different boundaries sequences are put in the critical set. In this way, we could handle the topology preservation problem for the object with holes as shown in Fig. 6.
Fig. 6: the skeleton of hole-object.
Experimental results
In this section, we discuss the performance of the proposed algorithm from two aspects: 1) the stability to noise and rigid transform, 2) the comparative analysis between the proposed algorithm and another skeleton extraction algorithm.
The stability of the skeleton algorithm
For the images of different rats, teddies and apples, we obtain similar skeletons under the same threshold condition ( and ) and the skeletons are able to perfectly indicate the topological structures of the images (see Fig. 7).
In most applications, it is possible to conduct rigid transform (rotations, scaling, interpolation, etc.) which generates noise on the image. But the skeleton extraction should have invariant property to the rigid transform. Fig. 8 shows robustness of the algorithm proposed in this paper against rotary transform and scale transform.
In addition, we added (0, 1) and (0, 1.5) Gauss noises on the boundary in Fig. 9 The experimental results show that the proposed algorithm can ignore the influence of boundary noise and extract stable skeletons.
Fig. 7: Skeleton production by the proposed algorithm.
Fig. 8: skeleton production by the proposed algorithm on noisy images by rigid transform.
Fig. 9: skeleton production by the proposed algorithm on Gauss noisy image.
(a)
(b)
(c)
(d)
Fig. 10: skeleton obtained by method described (a),(b) in [12] with threshold 15,(c)(d)by the proposed method with threshold(and ).
Analysis and comparison
Part B compares the skeleton extraction algorithm proposed in this paper with the algorithm proposed in [12]. Almost all the skeleton extraction algorithms generate redundant skeleton protrusions. The algorithm in [12] can get ideal skeleton, but it's hard to determine the number of the vertex of the polygon during the discrete boundary curve evolvement. Therefore, it is difficult to find an appropriate parameter to make the algorithm in [12] adaptive in all kinds of shapes as shown in Fig. 10(a), (b). The minimum of the parameter of boundary curve evolvement is three, so the skeleton has at least three branches. This is not adaptive to some standard shapes such as circle and ellipse, as shown in Fig. 11(a). However, the algorithm proposed in this paper can use the same threshold to adapt different shapes as shown in Fig. 10 (c), (d), Fig. 11 (b).
(a)
(b)
Fig. 11: standard shape's skeleton obtained by method described (a) in [12] with minimum threshold 3, (b) by the proposed method with threshold (and).
Time complexity of the skeleton extraction algorithm and the pruning algorithm proposed in this paper is, respectively, so the total time complexity is.
Conclusion and future work
In this paper, we propose a precise, stable and connected skeleton extraction and pruning algorithm that overcomes the influence of boundary noise on skeleton. We extract the skeleton with the criterion, prune the skeleton by bisector angle and preserve the visual important skeleton. The algorithm in this paper can be extended to high-dimension space easily, but the criterion of a skeleton point and the bisector angle need redefinition.
Acknowledgments This work was supported in part by grants from the Grant-in-Aid for Scientific Research (B) numbered 21300036 and the Grant-in-Aid for Exploratory Research numbered 20650143 from the Japan Society for the Promotion of Science
