334 A Computational Introduction to Digital Image Processing, Second Edition
Python
In : def zs
_
fun(x,parity):
...: n = np.reshape(x,[3,3])
...: n[1,1] = 0
...: B = n.sum()
...: X = sk.measure.label(n,background=0).max()+1
...: out = (B>=2) and (B<=6) and (X==1)
...: if parity==0:
...: out = out & (x[1]==0 or x[3]==0 or (x[5]==0 and x[7]==0))
...: elif parity==1:
...: out = out & (x[5]==0 or x[7] ==0 or (x[1]==0 and x[3]==0))
...: return out
The functions will be applied using the ndimage.generic
_
filter method:
Python
In : from scipy.ndimage import generic
_
filter as gfilt
In : L = zeros((12,10)); L[1:11,1:6]=1; L[6:11,6:9]=1;
In : prev = np.copy(L)
In : curr = prev
*
(1-gfilt(prev,zs
_
fun,size=(3,3),extra
_
arguments=(1,)))
Then as with MATLAB or Octave we apply the even and odd iterations until there is no
more change:
Python
In : while True:
...: curr = curr
*
(1-gfilt(curr,zs
_
fun,size=(3,3),extra
_
arguments=(0,))
)
...: curr = curr
*
(1-gfilt(curr,zs
_
fun,size=(3,3),extra
_
arguments=(1,))
)
...: if np.array
_
equal(prev,curr):
...: break
...: else:
...: prev = np.copy(curr)
...:
Two more examples; the circles image and the “nice work” image. Both the images and
their skeletonizations are shown in Figure 11.25.
The Guo-Hall Skeletonization Algorithm
There are in fact a number of Guo-Hall algorithms; we will investigate one that has
the advantages of being simple to describe, easy to implement, fast to run, and gives good
results. What could be better?
The Guo-Hall algorithm is an example of a subfield algorithm. We imagine the image
grid being labeled with 1’s and 2’s in a chessboard configuration:
1 2 1 2 ···
2 1 2 1 ···
1 2 1 2 ···
2 1 2 1 ···
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Image Topology 335
FIGURE 11.25: Examples of the Zhang-Suen skeletonization
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.
Image Topology 337
. . . . . . . . . .
. . . . . . . . . .
. .
1
.
1
. . . . .
. . .
1
. . . . . .
. .
1 2 1
. . . . .
. . .
1
. . . . . .
. .
1 2 1
. . .
. .
. . .
1 2 1
.
1
. .
. .
1 2 1 2 1
. . .
. .
2 1
.
1
.
1
. .
.
2
. . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. .
1
.
1
. . . . .
. . .
1
. . . . . .
. . .
2
. . . . . .
. . .
1
. . . . . .
. . .
2
. . . .
. .
. . . .
2
. .
1
. .
. . .
2
.
2 1
. . .
. .
2
. . . .
1
. .
.
2
. . . . . . . .
. . . . . . . . . .
FIGURE 11.27: Steps 3 and 4 of a Guo-Hall skeletonization
Implementation in Python. Start by creating a version of the image tiled with ones
and twos. Using the “nice work” image stored as binary array n:
Python
In : r,c = n.shape
In : n2 = np.tile(np.array([[1,2],[2,1]]),[r/2,c/2])
*
n
As with the Zhang-Suen algorithm, create a function to flag deletable pixels:
Python
In : def gh
_
fun(x,parity):
...: n = (np.reshape(x,[3,3])>0)
*
1
...: n[1,1] = 0
...: B = n.sum()
...: X = sk.measure.label(n,8,background=0).max()+1
...: return ((B>=2) and (X==1) and (x[1]
*
x[3]
*
x[5]
*
x[7]==0) and (x
[4]==parity))
Then we can create the current and previous images:
Python
In : prev = np.copy(n2)
In : curr = prev
*
(1-gfilt(prev,gh
_
fun,size=(3,3),extra
_
arguments=(1,)))
Now apply the algorithm until there are no further changes:
338 A Computational Introduction to Digital Image Processing, Second Edition
Python
In : while True:
...: curr = curr
*
(1-gfilt(curr,gh
_
fun,size=(3,3),extra
_
arguments=(2,))
)
...: curr = curr
*
(1-gfilt(curr,gh
_
fun,size=(3,3),extra
_
arguments=(1,))
)
...: if np.array
_
equal(prev,curr):
...: break
...: else:
...: prev = np.copy(curr)
...:
Implementation in MATLAB and Octave. Start as before by defining the function
to apply to the subfields:
MATLAB/Octave
>> function out = gh(x)
> n = x; n(5) = 0;
> B = sum(n(:)); X = max(max(bwlabel(n,8)));
> S = n(2)
*
n(4)
*
n(6)
*
n(8);
> out = (B>=2 & X==1 & S==0);
> end
>> gh
_
lut = makelut(@gh,3);
Next, create a chessboard version of the image:
MATLAB/Octave
>> [r,c] = size(n);
>> n2 = repmat([1 2;2 1],r/2,c/2).
*
n;
Now apply the lookup table to the ones and twos in turn, until there is no change:
MATLAB/Octave
>> prev = n2;
>> g = apply(n2>0, gh
_
lut);
>> curr = prev .
*
~((prev==1) & (g==1));
>> while true,
> g = apply(curr>0, gh
_
lut);
> curr = curr .
*
~((curr==2) & (g==1));
> g = applylut(curr>0,gh
_
lut);
> curr = curr .
*
~((curr==1) & (g==1));
> if isequal(prev,curr), break;end
> prev = curr;
> end
>> imshow(curr>0)
The result is shown in Figure 11.28(a).
Note the differences between these skeletons and those produced by the Zhang-Suen
algorithm as shown in Figure 11.25.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.