Skeleton of Image Region

The structural shape of an image region can be represented by a graph. It is achieved by using a thinning algorithm. The resulting graph is called the skeleton of the region. It can be a useful preprocessing step for some applications such as optical character recognition. The following figures shows an original structural shape and its skeleton.

The skeleton of a region is obtained using various methods. Two popular methods among them are Medial Axis Transformation (MAT) , and Two Step Thinning. In Medial Axis Transformation, each point in the region finds its closest neighbour on the boundary of the region. If it finds more than one such neighbour, it belongs to the skeleton of the region. Although MAT is easy to understand, it needs a lot of calculation. We find the distance transform of the region first. The distance transform replaces each pixel value in the region with the distance of the pixel from the nearest neighbour on the boundary of the region. The nearer pixels from the boundary have the lower distance values (lower intensity) and the farther pixels from the boundary have the larger distance values (higher intensity). From the distance values, the local maximums along row or column are searched and defined as pixels in the skeleton. The example MATLAB code for MAT can be seen here (MATeg.m). The original image, the distance transformed image, and the skeleton using MAT are shown in the following figures.

Two Step Thinning algorithm is more efficient and faster than MAT. Two step thinning algorithm iterately delete edge points of a region subject to the constraints that deletion of these points does not remove end points, does not break connectivity, and does not cause excessive erosion of the region. The region points are assumed to have value 1 and background points to have value 0. The method consists of successive passes of two basic steps applied to the given region.

With reference to the 8 neighborhood notation shown in the figure, step 1 flags a contour point p1 for deletion if the following conditions are satisfied: (a) 2 ≤ N(p1) ≤ 6 (b) T(p1) = 1 (c) p2.p4.p6 = 0 (d) p4.p6.p8 = 0 where N(p1) is the number of nonzero neighbors of p1, and T(p1) is the number of 0 to 1 transitions in the ordered sequence p2, p3, ... , p8, p9, p2. In step 2, conditions (a) and (b) remain the same, but conditions (c) and (d) are changed to (c') p2.p4.p8= 0 (d') p2.p6.p8= 0 Step 1 is applied to every border pixel in the binary region under consideration. If one or more of conditions (a)-(d) are violated, the value of the point in question is not changed. If all conditions are satisfied the point is flagged for deletion. However, the point is not deleted until all border points have been processed. This delay prevents changing the structure of the data during execution of the algorithm. After step 1 has been applied to all border points, those that were flagged are deleted (changed to 0). Then step 2 is applied to the resulting data in exactly the same manner as step 1. Thus one iteration of the thinning algorithm consists of (1) applying step 1 to flag border points for deletion; (2) deleting the flagged points; (3) applying step 2 to flag the remaining border points for deletion; and (4) deleting the flagged points. This basic procedure is applied iteratively until no further points are deleted, at which time the algorithm terminates, yielding the skeleton of the region. Condition (c) p2.p4.p6 = 0 and (d) p4.p6.p8 = 0 are satisfied simultaneously by the minimum set of values; (p4 = 0 or p6= 0) or (p2=0 and p8=0). Similarly, conditions (c') and (d') are satisfied simultaneously by the following minimum set of values: (p2=0 or p8=0) or (p4=0 and p6=0). The example MATLAB code for Two Step Thinning algorithm can be seen here (TSTeg.m).

The above codes may be useful to understand the methods and to implement them in other programming languages. In MATLAB, the skeleton of all regions in a binary image is generated via function bwmorph. sk=bwmorph(bwImg,'skel',Inf); The result of the above operation is shown below.

Reference: Rafael C. Gonzalez, Richard E. Woods, Steven L. Eddins, "Digital Image Processing Using MATLAB", Second Edition, Mc Graw Hill (Asia), 2011.