 Open Access
 Total Downloads : 2474
 Authors : Jayanta Basak, Sourav Saha
 Paper ID : IJERTV3IS111060
 Volume & Issue : Volume 03, Issue 11 (November 2014)
 Published (First Online): 27112014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Analysis of Iterative Skeletonization Algorithm in Recognizing Medial Axis of a Binary Image
Jayanta Basak
Department of Computer Science & Engineering Institute of Engineering and Management Kolkata, West Bengal, INDIA
Sourav Saha
Department of Computer Science & Engineering Institute of Engineering and Management Kolkata, West Bengal, INDIA
Abstract One of the central concerns in many computer vision based recognition systems is to extract skeletons of binary image objects in order to analyse structural similarities among them. Skeletonization of a digital image primarily refers to a special shapetransformation for representing structural properties of the various distinguishable key constituent components of the original image. Thinning is one of the popular approaches to find the skeleton of an image. The output of thinning algorithms is a set of connected digital curves or arcs maintaining overall structural properties of the object. In this paper we have studied two popular iterative skeletonization algorithms, namely Stentiford Thinning Algorithm and ZhangSuen Thinning Algorithm to present a comparative analytical framework in relation with meaningful skeleton extraction capability.
Keywords Skeletonization, medial axis transformation, thinning.

INTRODUCTION
A skeleton is presumed to be the representative of structure of an object's shape with relatively very small number of pixels, all of which are constituents of basic structural elements. The skeleton conveys all the structural information found in the original and the position, orientation, and length of the line segments of the skeleton are representatives of structural relationships among distinct shapesubcomponents of the object. Thinning is one of the popular approaches to find the skeleton of an image. The output of thinning algorithms is set of connected digital curves or arcs holding overall structural properties of the object. Thinning can also be defined as the act of identifying pixels belonging to an object that are essential for communicating the objects internal structure for rendering the shape. In order to find the Skeleton of an image three basic things requirements are generally kept in mind:

Not all objects can be thinned for skeleton extraction. Thinning is useful for digital representation of objects having reasonable amount of area.

To find the skeleton, one technique may not work in all situations.

Thinning is not always an iterative process of stripping away the outer layers of pixels. Thinning is the act of identifying the skeleton.
Medial Axis Transform (MAT)
The medial axis transform (MAT) was first introduced by Blum [1,2] to describe biological shape. The MAT has been used in pattern analysis and image analysis [3,4]. It can be viewed as the locus of the centre of a maximal disc as it rolls inside an object. There is a onetoone relationship between the MAT and object boundary which means that for an object there will be a unique MAT. It is possible to reconstruct a broken object if its MAT is known. Using MAT a broken object can be reconstructed [5]. More importantly, dimensional reduction and topological equivalence make the MAT a simplified, abstract representation of the geometry. MAT also provides details with respect to the symmetry of the object, it can be applied to application areas where this property is considered important. An important characteristic of the MAT is that it can be used to simplify the original object and still retain the original objects information. MAT of an object is therefore also called the skeleton or symmetric axis transform of an object or a shape.
The MAT treats all boundary pixels as point sources of a wave front. Each of these pixels excites its neighbours with a delay time proportional to distance, so that they all are the part of the wave front. The wave passes through each point only once, and when two waves meet they cancel each other, producing a corner. The medial axis is the locus of the corners, and forms the skeleton (Blum says line of symmetry) of the object.
The MAT uses both time and space information, and can be inverted to give back the original picture. To implement this need to convert the continuous transform to a discrete one. This involves various approximations involving the distance function on a discrete grid. This allows the MAT to be applied to a raster image.


THINNING AND SKELETONIZATION
ALGORITHMS
Skeletonization was introduced to describe the global properties of objects and to reduce the original image into a more compact representation. The skeleton expresses the structural connectivity of the main components of an object and it has the width of one pixel in the discrete case. These kinds of techniques have a wide range of applications, for
example skeletonization has been applied successfully in solving character recognition problems.
A basic method for skeletonization is thinning. It is generally an iterative technique, which extracts the skeleton of an object as a result. In every iteration, the edge pixels having at least one adjacent background point are deleted. All those pixels can be eroded, only if its removal doesn't affect the topology of the object. The skeleton represents the shape of the object in a relatively small number of pixels.
Thinning works suitably for objects with definite shape. This method does not work well for objects having complex contours enclosing a large area. The performance of a skeletonization approach must be measured based on its efficacy on variety of shapes.
The MAT in its original implementation needs time and space and it turns out ineffective to implement directly on shape. For this reason sometimes it becomes necessary to transform input image into some other form prior to the application of MAT.
A good approximation of MAT on a sampled grid is easily obtained computing first the distance from each object pixel to the nearest boundary pixel, and then calculates the Laplacian of the distance image. Pixels having large values belong to the medial axis. The distance between the object pixels and the boundary can be measured in several ways and we need to explore each way as the distance metric has an influence on the final result. Figure 1 illustrates the thinning process using the Medial Axis Transform.
Figure 1. Skeletonization process using the medial axis transforms.
a) Sampled Image. b) Distance Map for 8distance. c) Skeleton for 8distance.

Distance Map for 4distance.

Skeleton for 4distance.


ITERATIVE MORPHOLOGICAL METHODS
Majority of thinning algorithms are based on a repeated stripping away of layers of pixels until no more layers can be removed. A set of rules defines which pixels can be removed, and some sort of templatematching scheme frequently is used to implement these rules. The algorithm stops when no change occurs after two consecutive passes through the image.
Stentiford Thinning Method:
The TemplateBased MarkandDelete Thinning Algorithms are very popular because of their reliability and effectiveness. This type of thinning process uses templates, where a match of the template in the image leads to deletion of the centre pixel. They are iterative in nature which repeately erodes the outer layers of pixel until no more layers can be removed. The Stentiford Thinning Method is an instance of such kinds of algorithms [6,7]. It uses a set of four 3 X 3 templates to scan the image. As shown in Fiure 2
Figure 2. Templates to identify pixels to be eroded in the Stentiford Method. Empty white boxes belong to places where the colour of the pixel does not need to be checked.
The basic algorithm outlined below:

Find a pixel location (i,j) where the pixels in the image I
match those in template T1

If the central pixel is not an endpoint, and has connectivity number = 1, then mark this pixel for later deletion.

Repeat steps 1 and 2 for all pixel locations matching the template T1.

Repeat steps 13 for the remaining templates in turn: T2, T3, and T4.

If any pixels have been marked for deletion, then delete them by setting them to white.

If any pixels were deleted in step 5, then repeat the entire process from step 1; otherwise, stop.
The concept of connectivity number is little bit complex. It is a measure of how many objects are connected with a particular pixel. The number can be evaluated using following formula.
Cn = Nk – (Nk . Nk+1 . Nk+2 )
kS
Where:
Nk is the colour of the eight neighbours of the pixel under consideration. N0 is the centre pixel. N1 is the colour value of the pixel to the right of the central pixel and the rest are numbered in counter clockwise order around the centre and S = {1, 3, 5, 7}. Figure 3 illustrates the connectivity number.
Figure 3. Connectivity numbers.

Represents connectivity number = 0.

Represents connectivity number = 1, the central pixel might be deleted without affecting the connectivity between left and right.

Represents connectivity number = 2, the deletion of the central pixel might disconnect both sides.

Represents connectivity number = 3,

Represents connectivity number = 4.
Figure 4 shows one iteration (the first) of this thinning algorithm applied to the Tshaped object. One iteration includes one pass for each of the four templates. The black pixels are those marked for deletion, and it is clear from the figure exactly what each template accomplishes. Each complete iteration effectively erodes a layer of pixels from the outside of the object, but unlike standard morphological erosion, the deletion of a pixel is contingent upon meeting the endpoint and connectedness constraints.
Figure 4. The four parts of each iteration of the Stentiford thinning method.
(a) (b) (c) (d) (e)

Tshaped object

After applying template T1.

After T2.

After T3.

After T4.
In each case, the black pixels represent those to be deleted in this iteration.
Figure 5. Skeletonization Process using Stentiford Algorithm.
ZhangSuen Algorithm:
Another popular skeletonization algorithm was proposed by ZhangSuen Thinning Algorithm [6, 7]. This skeletonization algorithm repeatedly finetunes an approximate skeleton based on the result obtained at previous iteration step. It is fast and simple. It can be implemented parallel, meaning that the new value for any pixel can be computed using only the values known from the previous iteration. Therefore, if a computer having one processor per pixel were available, it could determine the entire next iteration at one go. This algorithm is made by two subiterations as described below.
In the first one, a pixel I (i,j) is deleted if the following condition are satisfied:

Its connectivity number is one.

It has at least two black neighbours and not more than six.

At least one of I(i,j+1), I(i1,j), and I(i,j1) are white.

At least one of I(i1,j), I(i+1,j), and I(i,j1) are white.
In the second subiteration the conditions in steps 3 and 4 change.

Its connectivity number is one.

It has at least two black neighbours and not more than six.

At least one of I(i1,j), I(i,j+1), and I(i+1,j) are white.

At least one of I(i,j+1), I(i+1,j), and I(i,j1) are white.
At the end, pixels satisfying these conditions will be deleted. If at the end of either subiteration there are no pixels to be deleted, then the algorithm stops.
Figure 6. Skeletonization Process using ZhangSuen Algorithm.


CONCLUSION
The aim of the skeletonization is to extract a regionbased shape feature representing the general form of an object. In this paper we described two popular image skeletonization technique– Stentiford and ZhangSuen Thinning Algorithm. It has been empirically observed that Stentiford Thinning algorithm outperforms ZhangSuen Thinning Algorithm for finding medial axis of wide variety of shapes.

REFERENCES

Blum H. A transformation for extracting new descriptors of shape. In:Dunn W, editor. Models for the perception of speech and visual form.Cambridge: MIT Press, 1967. p 36280.

Blum H. Biological shape and visual science (Part I). J Theor Biol 1973;38:20587.

Baja GS, Thiel E. (34)Weighted skeleton decomposition for pattern representation and description. Pattern Recogn 1994;27(8):103949.

Montanari U. Continuous skeletons from digitized images. J Assoc Comput Machinery 1969;16(4):53449.

Gelston S, Dutta D. Boundary surface recovery from skeleton curves and surfaces. Comput Aided Geometr Des 1995;12:2751.

Parker, J., R., Practical Computer Vision using C, Wiley Computer Publishing, 1994.

Sonka, M., Hlavac, V., Boyle, R., Image Processing, Analysis, and Machine Vision, 2nd Edition, Pws. Pub. Co., 1998.