Image Topology 329
Returning again to Figure 11.20(b), since C(p) = 1 the central pixel p is 8-simple and so
can be deleted without affecting the 8-connectivity of the object. But since A(p) = 1, the
central pixel p is not 4-simple and so cannot be deleted without affecting the 4-connectivity
of the object. This is exemplified in Figure 11.3.
Note that A(p) and B(p) can be computed simply by using the various labeling functions
discussed earlier. For example, consider the neighborhood shown in Figure 11.20(b):
MATLAB/Octave
>> n = [1 1 0;1 1 1;0 0 1]
>> n(5) = 0;
>> max(max(bwlabel(n,4)))
ans =
2
>> max(max(bwlabel(n,8)))
ans =
1
Similarly:
Python
In : from skimage.measure import label
In : n = np.array([[1,1,0],[1,1,1],[0,0,1]])
In : n[1,1] = 0
In : label(n,4,background=0).max()+1
Out: 2
In : label(n,8,background=0).max()+1
Out: 1
How Not To Do Skeletonization
So now we know how to check if a pixel can be deleted without effecting the connectivity
of the object. In general, a skeletonization algorithm works by an iteration process: at each
step identifying deletable pixels and deleting them. The algorithm will continue until no
further deletions are possible.
One way to remove pixels is as follows:
At each step, find all foreground pixels that are 4-simple and delete them all.
Sounds good? Let’s try it on a small rectangle of size 2 × 4:
0 0 0 0 0 0
0 1 1 1 1 0
0 1 1 1 1 0
0 0 0 0 0 0
If we check the pixels in this object carefully, we will find that they are all 4-simple. Deleting
them all will thus remove the object completely: a very undesirable result. Clearly we need
to b e a bit more careful about which pixels we can delete and when. We need to add an
extra test for deletability, so that we do not delete too many pixels.
We have two options here:
1. We can provide a step-wise algorithm, and change the test for de letability at each
step.
330 A Computational Introduction to Digital Image Processing, Second Edition
2. We can apply a different test for deletability according to where the pixel lies on the
image grid.
Algorithms that work according to the first option are called subiteration algorithms; algo-
rithms that work according to the second option are called subfield algorithms.
The Zhang-Suen Skeletonization Algorithm
This algorithm has attained the status of a modern classic; it has some f aults (as we
shall see), but it works fairly fast, and most of the time produces acceptable results. It is an
example of a subiteration algorithm, in that we apply a slightly different deletability test
for different steps of the algorithm. In each step, the neighboring pixels are indexed as
p
1
p
4
p
7
p
2
p
5
p
8
p
3
p
6
p
9
where p
5
= p is the pixel being considered for deletion.
Step N
Flag a foreground pixel p = 1 to be deletable if
1. 2 ≤ B(p) ≤ 6,
2. X(p) = 1,
3. If N is odd, then
p
4
· p
8
· p
6
= 0
p
8
· p
6
· p
2
= 0.
If N is even, then
p
4
· p
8
· p
2
= 0
p
4
· p
6
· p
2
= 0.
Delete all flagged pixels.
Continue until there are no more deletable pixels in two successive iterations.
Item 3 can be written alternatively as:
3. If N is odd, then
p
6
= 0, or p
8
= 0, or p
2
= p
4
= 0
If N is even, then
p
2
= 0, or p
4
= 0, or p
6
= p
8
= 0.
If we check the diagram for the neighbors of a foreground pixel p, we see that we can
rephrase this item as:
For odd iterations, delete only pixels that are on the right hand side, or bottom of
an object, or on a northwest corner.
For even iterations, delete only pixels that are on the left hand side, or top of an
object, or on a southeast corner.
Image Topology 331
Odd iterations Even iterations
FIGURE 11.22: Deletion in the Zhang-Suen algorithm
Figure 11.22 shows pixels that may be considered for deletion at different iterations. Item 1
in the algorithm ensures that we do not delete pixels that have only one neighbor, or have
seven or more. If a pixel has only one neighbor, it would be at the end of a skeletal line,
and we would not want it to be deleted. If a pixel has seven neighbors, then deleting it
would start an unacceptable erosion into the object’s shape. This item thus ensures that
the basic shape of the object is kept by the skeleton. Item 2 is our standard connectivity
condition.
A major fault with this algorithm is that there are objects that will be deleted completely.
Consider a 2 × 2 square:
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
We can check carefully that every item is satisfied by every pixel, and hence every pixel will
be deleted.
An example. Consider the L shape shown in Figure 11.23, where for ease of viewing we
have replaced all the zeros (background pixels) with dots. The boxed pixels show those that
will be deleted by Steps 1 and 2 of the algorithm. Figure 11.24 shows Steps 3 and 4 of the
skeletonization. After Step 4 no more deletions are possible, and so the skeleton consists
of the unboxed foreground pixels in the right-hand diagram of Figure 11.24. Note that the
skeleton does not include the corners of the original object.
Implementation in MATLAB and Octave. We can implement this algorithm easily
in MATLAB or Octave; we use lookup tables: one for the odd iterations, and one for the
even. We then apply these lo okup tables alternately until there is no change in the image
for two successive iterations. We manage this by keeping three images at any given time:
the current image, the previous image, and the last (that is, before the previous) image.
If the current and last images are equal, we stop. Otherwise, “push” the images back: the
previous image becomes last, and the current image becomes the previous image. We then
apply whichever lookup table is appropriate to the current image to create the new current
image. That is:
last ← previous
previous ← current
current ← applylut(current, lut)
332 A Computational Introduction to Digital Image Processing, Second Edition
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1 1 1
FIGURE 11.23: Steps 1 and 2 of a Zhang-Suen skeletonization
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
FIGURE 11.24: Steps 3 and 4 of a Zhang-Suen skeletonization
Image Topology 333
The lookup table for the odd iterations can be created as:
MATLAB/Octave
>> function out = zs
_
odd(x)
> t = x;t(5)=0; B = sum(t(:));X=max(max(bwlabel(t,4)));
> out = (B>=2) & (B<=6) & (X==1);
> out = out&(t(6)==0 | t(8)==0 | (t(2)==0 & t(4)==0));
> end
>> lut
_
odd = makelut(@zs
_
odd,3);
and for the even iterations as:
MATLAB/Octave
>> function out = zs
_
even(x)
> t = x;t(5)=0; B = sum(t(:));X=max(max(bwlabel(t,4)));
> out = (B>=2) & (B<=6) & (X==1);
> out = out&(t(2)==0 | t(4)==0 | (t(6)==0 & t(8)==0));
> end
>> lut
_
even = makelut(@zs
_
even,3);
Applying these lookup tables to the L shape from the previous figures can be easily done,
but to simplify the work we shall perform two iterations at a time:
MATLAB/Octave
>> L = zeros(12,10); L(2:11,2:6)=1; L(7:11,7:9)=1;
>> previous = L;
>> current = L & ~applylut(L,lut
_
odd);
>> while true,
> current = current & ~applylut(current,lut
_
even);
> current = current & ~applylut(current,lut
_
odd);
> if isequal(previous,current), break;end
> previous = current;
> end
Note that the results of applying the lookup tables is an array A of zeros and ones, where
the ones give the positions of the deletable foreground pixels. To delete these pixels from
the current array X we need to perform a set difference XA, which can be implemented
with
X & ~A.
At this stage, the value of
current will be the skeleton shown in Figure 11.24.
Implementation in Python. In fact, the Zhang-Suen algorithm is implemented as the
skeletonize method in the skimage.morphology module. But as an example, we will
show how we can do it ourselves. Start with writing a function for both the odd and even
iterations, using a separate argument (here called
parity) to distinguish them:
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.