IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 27, NO.

10, OCTOBER 2005 1671

An Improved Rotation-Invariant examining the pixels in a 4
3 (or 3
4) window and it is clear that
among other configurations, two-pixel wide sections which are only
Thinning Algorithm two pixels long (e.g., Fig. 1) are not properly handled.
In this paper, we propose a modification to the rotation-
Peter I. Rockett invariant thinning algorithm of Ahmed and Ward based on their
set of 20 rules to carry out most of the thinning, thus preserving the
property of invariance to rotation. To deal with the case of two-
Abstract—Ahmed and Ward [2] have recently presented an elegant, rule-based pixel wide lines, however, we use a different procedure, mindful of
rotation-invariant thinning algorithm to produce a single-pixel wide skeleton from a
the origin of the shortcoming of the A-W algorithm set out in the
binary image. We show examples where this algorithm fails on two-pixel wide lines
preceding paragraph. We adopt a two-stage thinning procedure
and propose a modified method which corrects this shortcoming based on graph
which uses the A-W rules to thin down to a skeleton which includes
connectivity.
2-pixel wide lines—we make no attempt to deal with this case in
the first stage. As a second stage, we examine the 2-pixel wide lines
Index Terms—Thinning, skeletonization, graph theory.
in the provisional skeleton produced by the first processing stage
æ to see which pixels, if any, can be deleted without compromising
the connectivity of the skeleton.
1 INTRODUCTION In the following section, we describe our modified algorithm
and present some results in Section 3. Finally, we offer some
THE thinning (or skeletonization) of segmented binary images is a remarks and conclusions in Section 4.
much-used and well-studied topic in image processing and related
fields. In a frequently cited review published in 1995, Lam and Suen
[1] reviewed around 100 thinning algorithms and significant 2 DESCRIPTION OF THE MODIFIED ALGORITHM
numbers of new algorithms have been proposed in the intervening
years. Of recent note is the rotation-invariant thinning algorithm of Our algorithm comprises two stages: First, we apply the 20 rules of
Ahmed and Ward [2] which used the particularly elegant device of Ahmed and Ward over the 8-neighbors of each pixel, in turn, to
deriving a set of predicates over the 8-neighbors of a given pixel to determine if that pixel is on the boundary of the shape to be thinned
determine if that pixel is on the boundary of a shape and can thus be and hence can be deleted. Like the A-W algorithm, this first stage is
deleted. As part of our present work, we have used the Ahmed-Ward applied iteratively where the pixels are marked for deletion if they
(A-W) thinning algorithm to extract the center lines of arteries are adjudged to be on the shape’s boundary and then all marked
segmented from X-ray angiograms as a prelude to further proces- pixels are deleted at the end of an iterative pass. Again, like the
sing. These vascular trees are significantly more complex than any of A-W algorithm, we skip pixels which are found to be at the extrema
the characters examined by Ahmed and Ward and, in the course of of diagonal lines. Most importantly, any pixels which are found to
our work, we have observed a number of cases where the be part of two-pixel wide vertical or horizontal lines, that is which fit
A-W algorithm fails to produce a center line of single pixel width. any of the rules: ½ 0 w 1 0 , ½ 0 1 w 0 , ½ 0 w 1 0 T , or
One such example is shown in the image fragment of Fig. 1, where the ½ 0 1 w 0 T are skipped—two-pixel wide lines are processed in
union of the black and white pixels represent the original shape and the second stage. Similar to the A-W algorithm, the first stage
the white pixels show the center line produced by the A-W algorithm. progressively removes pixels from the boundary of a shape until the
Notice that a portion of this center line is a two pixel wide vertical line
shape has been eroded to a skeleton of mostly single pixel width.
and seems to arise because the rules constructed by Ahmed and
The second processing stage takes the provisional skeleton from
Ward to deal with two-pixel wide sections do not cover this (and
the first processing stage—where we know all the pixels, by
some other) pixel configuration(s). We emphasize that the occur-
definition, boundary pixels—and examines every pixel which
rence of 2-pixel wide center lines is fairly rare—we typically observe
makes up part of a two-pixel wide line. If deletion of such a pixel
between 2 and 5 in an angiogram image—but they are nonetheless
does not disrupt the connectivity of the skeleton, we remove it
undesirable. The existence of even one pathological case, however,
immediately from the skeleton in a single pass. Thus, at the end of
constitutes a disproof of the A-W algorithm.
this single pass, the skeleton comprises only single-pixel wide
The A-W algorithm proceeds by deriving a set of rules over the
segments. If any two pixel wide blocks remain, these cannot be
8-neighbors of the pixel which is a candidate for deletion. In its
deleted without producing a disconnected skeleton.
initial form, however, the algorithm cannot handle lines of two pixel In order to efficiently determine if deletion of a pixel in a 2-pixel
width and, consequently, Ahmed and Ward added further rules to wide line will disrupt connectivity, we build an undirected graph
deal with two pixel wide lines which involved extending the of the local pixel connectivity over its eight neighbors. The process
window over which the deletion decision was computed to include is illustrated by the example in Fig. 3 and Table 2, where the pixel
the four blocks of three pixels immediately above, below, to the right labeling convention we have used is shown in Fig. 2.
and to the left of the original 3
3 region—20 pixels in all. (The four Fig. 3a shows an initial pixel configuration in the provisional
corner pixels of this 5
5 region are “don’t care” cases.) Although skeleton produced by the first thinning stage. Note that, for this
inducing a set of rules over the eight neighbors (256 possible example, we assume that the middle two pixels form part of a two-
configurations) has proven eminently tractable, producing a set of pixel wide vertical line as implied by the zero pixel shown dotted to
foolproof rules to handle two-pixel wide lines over the 20 pixel set the left. Fig. 3b shows the graph representation of the connectivity in
(220  1 million possible configurations) is a formidable task and a the 3
3 region for the nonzero pixels of Fig. 3a where arcs represent
few of the possible configurations, such the one in Fig. 1, are not physical adjacency of the (nonzero) pixels. For example, x1 can only
dealt with correctly. The A-W rules for 2-pixel wide lines involve connect to x2 ; x3 ; x7 , and x8 , assuming that the pixels at both ends of
an arc are “1.” In other words, an arc is only allowable if it is possible
to pass from one pixel to the other without passing through a third
. The author is with the Department of Electronic & Electrical Engineering, pixel. A full list of allowable arcs is shown in Table 1.
University of Sheffield, Mappin Street, Sheffield S1 3JD, UK. From Fig. 3b, it is readily apparent that the central pixel in Fig. 3a
E-mail: [Link]@[Link]. (vertex x0 ) can be safely deleted without breaking the connectivity of
Manuscript received 2 Nov. 2004; revised 28 Feb. 2005; accepted 2 Mar. 2005;
the skeleton since x0 can be removed from Fig. 3b leaving a subgraph
published online 11 Aug. 2005. where every vertex has at least one arc connected to it. In order to
Recommended for acceptance by P. Torr. implement this notion, we construct an adjacency matrix for the
For information on obtaining reprints of this article, please send e-mail to: connectivity graph and examine the scenario where the central pixel
tpami@[Link], and reference IEEECS Log Number TPAMI-0592-1104. is deleted. In fact, it is sufficient (and faster) to construct only the
0162-8828/05/$20.00 ß 2005 IEEE Published by the IEEE Computer Society
1672 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 27, NO. 10, OCTOBER 2005

TABLE 2
Adjacency Matrix for the Graph Shown in Fig. 3b

Fig. 1. A fragment of a segmented X-ray angiogram illustrating the breakdown of

the Ahmed and Ward [2] thinning algorithm. The union of the black and white
pixels is the original shape to be thinned and the white pixels show the final center
line produced by the Ahmed-Ward algorithm. Note the 2
2 block in the center of
the image.

Fig. 4. Counterexample of a pixel configuration where the central pixel cannot be

deleted without causing disconnection of the skeleton.
Fig. 2. The pixel numbering convention used here. (This is identical to Ahmed and
Ward [2] except that we extend their notation to label the central pixel as x0 .)
matrix must contain at least one nonzero entry. The speed of
searching the adjacency matrix can be improved by an “early jump-
out” approach: When searching a row, as soon as the first nonzero
entry is encountered, we can move on to searching the next row
since the presence of a single “1” is enough to guarantee connectivity
(for that row). Similarly, as soon as we find the first row that contains
only zero entries, we can terminate the search since a single empty
row tells us we cannot delete the central pixel under consideration.
By way of counterexample, Fig. 4 shows a pixel configuration in
the first-stage skeleton where the central pixel cannot be removed
as evidenced by the fact that vertex x2 will become disconnected if
vertex x0 is deleted. Deducing this conclusion from the corre-
sponding adjacency matrix is trivial.
Fig. 3. Example of construction of an undirected connectivity graph. (a) Shows the In practice, constructing and searching the adjacency matrix is
original pixel configuration and (b) the resulting graph. fast and efficient. Since we treat a 3
3 image patch and the central
TABLE 1 pixel and at least one other pixel are set (in order to constitute a two
Allowable Arcs pixel wide line), the adjacency matrix has to consider the connectivity
of only the remaining seven pixels in the 3
3 patch. Since, at this
stage of the algorithm, we are dealing with exterior pixels, strictly less
than seven pixels can ever be set. As a consequence, the adjacency
matrix is strictly smaller than 7
7 and, typically, much smaller than
even this. (In fact, we show below that the algorithm described here
can be faster than the A-W algorithm.)

3 RESULTS
Fig. 5 shows the thinning results for the portion of X-ray
angiogram image shown in Fig. 1 with the algorithm presented
here and for which the A-W algorithm fails. Note that the
algorithm described here does indeed produce a single-pixel wide
skeleton although the overall skeletonization is (unsurprisingly)
slightly different.
Figs. 6 and 7 contain two more examples of pixel configurations
taken from X-ray angiograms for which the A-W algorithm fails to
Note that the vertices at both ends of an arc must be “1” ( or true).
produce a single-pixel wide skeleton. Both Figs. 6a and 7a show
the results of the A-W algorithms and in Figs. 6b and 7b, the results
adjacency matrix for the subgraph resulting from excluding the obtained here. Again, the skeleton obtained from the new
central pixel. The adjacency matrix for the corresponding subgraph algorithm is of the desired single-pixel width.
of the graph in Fig. 3b is shown in Table 2. From this table, it is clear In addition to the examples taken from the complex vascular
that in order for the deletion of the central pixel not to create a trees obtained from X-ray angiograms, Figs. 8 and 9 compare the
disconnected skeleton, every row (or column) of the adjacency A-W and present algorithms for the task of skeletonizing two
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 27, NO. 10, OCTOBER 2005 1673

Fig. 8. Skeletonization of a Chinese character using (a) the A-W algorithm and
Fig. 5. Result of thinning for the section of X-ray angiogram image shown in Fig. 1 (b) the present algorithm.
using the present algorithm. The final skeleton is shown with the white pixels.

Fig. 6. A second example of thinning for a section of an X-ray angiogram image.

(a) Shows the skeleton obtained with the A-W algorithm and (b) that obtained with Fig. 9. Skeletonization of a Chinese character using (a) the A-W algorithm and
the present algorithm. The final skeletons are shown with the white pixels. (b) the present algorithm.

TABLE 3
Comparison of the Numbers of Pixels
in the Skeletons of the Chinese Characters

The numbers of pixels comprising the final skeletons of the

Fig. 7. A third example of thinning for a section of an X-ray angiogram image.
Chinese characters for each algorithm are shown in Table 3. There
(a) Shows the skeleton obtained with the A-W algorithm and (b) that obtained with
the present algorithm. The final skeletons are shown with the white pixels. appears to be no great difference in the overall numbers although
the new algorithm tends to use fewer pixels in the interior of
Chinese characters taken from Lin and Chen [3] and which have also skeleton segments and rather more at the ends of strokes.
been used by Ahmed and Ward [2]. Although the both algorithms We have also examined the operation of our modified algorithm
on the sequence of rotated symbols used by Ahmed and Ward [2,
yield acceptable, single-pixel wide skeletons for these characters, the
Fig. 3b]. Since the basis of our modified algorithm is the A-W rule
skeletons obtained are slightly different in nature. Since there is no
set, the modified algorithm produce results which differ only in its
established method for objectively comparing thinning algorithms,
treatment of diagonal lines. These differences can be conveniently
we confine ourselves to subjective observations based on the
summarized by the results of thinning the triangular shape (from
examples of the angiogram images and the Chinese characters in
the third column in A-W’s Fig. 3b) and are shown in Fig. 10.
Figs. 8 and 9.
The original A-W algorithm thins diagonal segments down to the
First, whereas the A-W algorithm often tends to skeletonize
“staircase” structures described above whereas our algorithm makes
diagonal lines with a “staircase” structure comprising two hor-
greater use of diagonal connectivities to produce a smoother
izontal pixels followed by two vertical pixels, the modified
skeleton. The difference between Figs. 10a and 10b are shown in
algorithm presented here tends to produce diagonal runs of pixels
Fig. 11 where the pixels which are present in the A-W result (Fig. 10a)
connected NW-to-SE (or NE-to-SW). Thus, the new algorithm
but absent from the results of the modified algorithm (Fig. 10b) are
arguably achieves a greater degree of thinning in that the resulting
shown in white. This difference illustrates that the modified
skeletons are more generally made-up of single-pixels rather than
algorithm tends to use fewer pixels in generating a skeleton from a
“staircases” of two-pixel long “risers” and “treads.”
diagonal segment. Similarly, the two pixels which are present in
Second, the A-W method appears to be more aggressive in Fig. 10b, but absent from Fig. 10a are arrowed; the fact that these two
eroding the ends of lines than the new algorithm; this is pixels are both next to pixels used by the A-W algorithm indicates
particularly evident from the Chinese character results. Whether that the modified algorithm is simply making an alternative choice of
this is an advantage or not probably depends on the end- skeleton pixel in these cases.
application for the skeleton. Certainly, for our work on X-ray As to the relative execution times, we have compared the average
angiograms, the present thinning algorithm is preferable since we run times over 10 executions for a 928
342 X-ray angiogram image
are interested, among other things, in identifying the end points of and the new algorithm runs ~ 6 percent faster (234mS versus 219mS)
terminal capillaries in arterial networks. since there are fewer rules to be evaluated in the iterative phase of the
1674 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 27, NO. 10, OCTOBER 2005

Fig. 10. Results of thinning a representative triangle form Fig. 3b of Ahmed and Ward. (a) Shows the result from the A-W algorithm whereas (b) shows the result from the
present algorithm.

new algorithm. By contrast, when comparing the execution times of algorithm appears to effect far less aggressive erosion of the ends
both algorithms on Ahmed and Ward’s Fig. 3, the algorithm of lines. Since the new algorithm utilizes the rotation-invariant
presented here ran ~18 percent slower than the A-W algorithm thinning rules of Ahmed and Ward, the skeletons it produces will
due to the large number of diagonal segments present in this image possess the same rotation invariant properties as skeletons
and, hence, the extensive application of the graph-based thinning produced by the Ahmed-Ward algorithm although the claim of
stage. For yet other images, the execution times of the two algorithms rotation invariance needs to treated somewhat carefully. For a two-
were indistinguishable. In general, therefore, it appears that the pixel wide line, the skeleton is considered as running between the
comparative execution times are similar but detailed differences two pixels and which of the two is deleted to yield a single-pixel
depend on the particular image under consideration. Both algo- wide center line is completely arbitrary. Ahmed and Ward chose the
rithms required the same number of iterations of applying the bottom-most pixel in a horizontal 2-pixel line and the right-most in a
thinning rule set. 2-pixel vertical line. Here, we tend to delete the top-most and left-
most pixels although this choice is implementation-dependent and
determined by the scan order (from top-left) in the second stage of
4 DISCUSSIONS AND CONCLUSIONS the algorithm; this could trivially be reversed to follow the same
The principal contribution of this work is to remedy a deficiency in choice as Ahmed and Ward by scanning from the bottom-right.
the thinning algorithm of Ahmed and Ward [2] by modifying the Nonetheless, since the choice of which pixel to delete from a 2-pixel
way in which lines of two-pixels width are handled. We have shown wide line is arbitrary and implementation-dependent, no thinning
that a few pathological configurations exist for which the algorithm can be truly rotation invariant. To select a consistent pixel
A-W algorithm does not produce single-pixel wide lines. Rather to delete, independent of rotation would require recognition of the
than attempting to thin two-pixel wide lines using an extension of shape’s pose and, therefore, recognition of the shape. But as one of
the rule-based methodology of Ahmed and Ward which requires the main uses of skeletonization is recognition, using knowledge of
characterization of a window encompassing more than the the shape’s pose to guide the thinning process is, in most cases, a
eight neighbors of the pixel under consideration, we have used a paradox.
two-stage process whereby we utilize Ahmed and Ward’s thinning
rules to produce a provisional skeleton containing two-pixel wide ACKNOWLEDGMENTS
segments which are then subsequently thinned where possible in a
single pass of a second stage. This second stage uses a graph-based This work was supported by the UK Joint BBSRC/EPSRC/MRC
method of determining whether a pixel in a two-pixel wide line can Discipline Hopping Programme under Grant No. GR0300594. The
be deleted without disrupting the connectivity of the skeleton. The author is also grateful to Maher Ahmed and Rabab Ward for
new algorithm produces results which are qualitatively different kindly providing copies of the images used in their paper for
from the A-W algorithm despite both sharing a common set of comparison purposes.
thinning rules. In addition to arguably achieving what seems to be a
greater degree of thinning than the A-W algorithm, the new
REFERENCES
[1] L. Lam and C.Y. Suen, “An Evaluation of Parallel Thinning Algorithms for
Character-Recognition,” IEEE Trans. Pattern Analysis and Machine Intelli-
gence, vol. 17, no. 9, pp. 914-919, Sept. 1995.
[2] M. Ahmed and R. Ward, “A Rotation Invariant Rule-Based Thinning
Algorithm for Character Recognition,” IEEE Trans. Pattern Analysis and
Machine Intelligence, vol. 24, no. 12, pp. 1672-1678, Dec. 2002.
[3] J.Y. Lin and Z.A. Chen, “Chinese Character Thinning Algorithm-Based on
Global Features and Contour Information,” Pattern Recognition, vol. 28,
no. 4, pp. 493-512, Apr. 1995.

. For more information on this or any other computing topic, please visit our
Digital Library at [Link]/publications/dlib.

Fig. 11. Difference between the skeleton pixels produced by the A-W and modified
algorithms shown in Fig. 10. The white pixels are pixels present in the A-W result
but absent from the modified algorithm result. The two (arrowed) gray pixels are
present in the modified algorithm result but absent from the A-W result.