Analysis of Iterative Skeletonization Algorithm in Recognizing Medial Axis of a Binary Image

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 shape-transformation 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 Zhang-Suen Thinning Algorithm to present a comparative analytical framework in relation with meaningful skeleton extraction capability.

Keywords Skeletonization, medial axis transformation, thinning.

1. 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 shape-sub-components 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:

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

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

   3. 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 one-to-one 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.

2. 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 8-distance. c) Skeleton for 8-distance.

   1. Distance Map for 4-distance.

   2. Skeleton for 4-distance.

3. 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 template-matching 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 Template-Based Mark-and-Delete 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:

   1. Find a pixel location (i,j) where the pixels in the image I

      match those in template T1

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

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

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

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

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

   1. Represents connectivity number = 0.

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

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

   4. Represents connectivity number = 3,

   5. Represents connectivity number = 4.

   Figure 4 shows one iteration (the first) of this thinning algorithm applied to the T-shaped 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)

   1. T-shaped object

   2. After applying template T1.

   3. After T2.

   4. After T3.

   5. After T4.

   In each case, the black pixels represent those to be deleted in this iteration.

   Figure 5. Skeletonization Process using Stentiford Algorithm.

   Zhang-Suen Algorithm:

   Another popular skeletonization algorithm was proposed by Zhang-Suen Thinning Algorithm [6, 7]. This skeletonization algorithm repeatedly fine-tunes 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 sub-iterations as described below.

   In the first one, a pixel I (i,j) is deleted if the following condition are satisfied:

   1. Its connectivity number is one.

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

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

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

   In the second sub-iteration the conditions in steps 3 and 4 change.

   1. Its connectivity number is one.

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

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

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

      At the end, pixels satisfying these conditions will be deleted. If at the end of either sub-iteration there are no pixels to be deleted, then the algorithm stops.

      Figure 6. Skeletonization Process using Zhang-Suen Algorithm.

4. CONCLUSION

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

5. REFERENCES

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

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

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

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

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

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

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