336 A Computational Introduction to Digital Image Processing, Second Edition
At Step 1, we only consider foreground pixels whose labels are 1. At Step 2, we only consider
foreground pixels whose labels are 2. We continue alternating between pixels labeled 1 and
pixels labeled 2 from step to step until no more deletions are possible. Here is the algorithm:
Flag a foreground pixel p as deletable if all of these conditions are met:
1. C(p) = 1,
2. B(p) > 1,
3. p is 4-adjacent to a background pixel
then delete all flagged pixels. This is done, in parallel, at alternate iterations for
each of the two subfields.
Continue until no deletions are possible in two successive iterations.
Consider our “L” example from above. We first superimpose a chessboard of 1’s and 2’s. In
Step 1 we just consider 1’s only. Step 1 shown in Figure 11.26 illustrates the first step: we
delete only those 1’s satisfying the Guo-Hall deletability conditions. These pixels are shown
in squares. Having deleted them, we now consider 2’s only; the deletable 2’s are shown in
Step 2.
. . . . . . . . . .
.
1 2 1 2 1
. . . .
.
2 1 2 1 2
. . . .
.
1 2 1 2 1
. . . .
.
2 1 2 1 2
. . . .
.
1 2 1 2 1
. . . .
.
2 1 2 1 2 1 2 1
.
.
1 2 1 2 1 2 1 2
.
.
2 1 2 1 2 1 2 1
.
.
1 2 1 2 1 2 1 2
.
.
2 1 2 1 2 1 2 1
.
. . . . . . . . . .
. . . . . . . . . .
. .
2
.
2
. . . . .
.
2 1 2 1 2
. . . .
. .
2 1 2
. . . . .
.
2 1 2 1 2
. . . .
. .
2 1 2
. . . . .
.
2 1 2 1 2
.
2
. .
. .
2 1 2 1 2 1 2
.
.
2 1 2 1 2 1 2
. .
. .
2 1 2 1 2 1 2
.
.
2
.
2
.
2
.
2
. .
. . . . . . . . . .
FIGURE 11.26: Steps 1 and 2 of a Guo-Hall skeletonization
Steps 3 and 4 as shown in Figure 11.27 continue the work; by Step 4 there are no more
deletions to be done, and we stop. We notice two aspects of the Guo-Hall algorithm as
compared with Zhang-Suen:
1. More pixels may be deleted at each step, so we would expect the algorithm to work
faster.
2. The final result includes more corner information than the Zhang-Suen algorithm.
We can implement this in using very similar means to our implementation of Zhang-Suen.