324 A Computational Introduction to Digital Image Processing, Second Edition
MATLAB/Octave
>> for i = 1:256,
> for j = 1:256,
> c2(i+1,j+1) =
min
(min(c2(i:i+2,j:j+2)+fmask));
> end
> end
>> for i = 256:-1:1,
> for j = 256:-1:1,
> c2(i+1,j+1) = min(min(c2(i:i+2,j:j+2)+bmask));
> end
> end
or in Python with
Python
In : for i in range(256):
...: for j in range(256):
...: c2[i+1,j+1] = (c2[i:i+3,j:j+3]+fmask).min()
...:
In : for i in range(256)[::-1]:
...: for j in range(256)[::-1]:
...: c2[i+1,j+1] = (c2[i:i+3,j:j+3]+bmask).min()
...:
The result can be shown as
MATLAB/Octave
>> imshow(mat2gray(2(2:257,2:257)))
or
Python
In : io.imshow(c2[1:257,1:257])
and is shown in Figure 11.13(a). Sometimes better information can be obtained by inverting
the image and finding the distance inside the objects, as shown in Figure 11.13(b)
11.8 Skeletonization
The skeleton of a binary object is a collection of lines and curves that encapsulate the
size and shape of the object. There are in fact many different methods of defining a skeleton,
and for a given object, many different possible skeletons. But to give a general idea, we
show a few examples in Figure 11.14.
A problem with skeletonization is that very small changes to an object can result in
large changes to the skeleton. Figure 11.15 shows what happens if we take away or add to
the central image of Figure 11.14.
Image Topology 325
(a) “External” distances (b) “Internal” distances
FIGURE 11.13: Examples of a distance transform
FIGURE 11.14: Examples of skeletonization
326 A Computational Introduction to Digital Image Processing, Second Edition
FIGURE 11.15: Skeletons after small changes to an object
One very popular way of defining a skeleton is by the medial axis of an object: a
pixel is on the medial axis if is equidistant from at least two pixels on the boundary of
the object. To implement this definition directly requires a quick and efficient method of
obtaining approximate distances; one way is to use the distance transf orm. Other ways of
approaching the medial axis are:
• Imagine the object to b e burning up by a fire that advances at a constant rate from
the boundary. The places where two “lines” of fire meet form the medial axis.
• Consider the set of all circles lying within the object, which touch at least two points
on the boundary. The centers of all such circles form the medial axis. Figure 11.16
shows this in action.
FIGURE 11.16: The medial axis of an object
A very good account of the medial axis (and of skeletonization in general) is given by
Parker [32].
Image Topology 327
Topological methods provide some powerful methods of skeletonization in that we can
directly define those pixels which are to be deleted to obtain the final skeleton. In general,
we want to delete pixels that can be deleted without changing the connectivity of an object,
which do not change the number of components, change the number of holes, or the relation-
ship of objects and holes. For example, Figure 11.17 shows a non-deletable pixel; deleting
the center (boxed) pixel introduces a hole into the object. In Figure 11.18, there is another
FIGURE 11.17: A non-deletable pixel: creates a hole
example of a non-deletable pixel; in this case, deletion removes a hole, in that the hole and
the exterior become joined. In Figure 11.19, there is a further example of a non-deletable
FIGURE 11.18: A non-deletable pixel: removes a hole
pixel; in this case, deletion breaks the object into two separate components. Sometimes we
FIGURE 11.19: A non-deletable pixel: disconnects an object
need to consider whether the object is 4-connected or 8-connected. In the previous examples
this was not a problem. However, look at the examples in Figure 11.20. In Figure 11.20(a),
the central point can not b e deleted without changing both the 4-connectivity and the 8-
connectivity. In Figure 11.20(b) deleting the central pixel will change the 4-connectivity,
but not the 8-connectivity. A pixel that can be deleted without changing the 4-connectivity
of the object is called 4-simple; similarly, a pixel that can be deleted without changing the
8-connectivity of the object is called 8-simple. Thus, the central pixel in Figure 11.20(a) is
neither 4-simple nor 8-simple, but the central pixel in Figure 11.20(b) is 8-simple but not
4-simple.
A pixel can be tested for deletability by checking its 3 ×3 neighborhood. Look again at
Figure 11.20(a). Suppose the central pixel is deleted. There are two options:
328 A Computational Introduction to Digital Image Processing, Second Edition
(a) (b)
FIGURE 11.20: Are the center points deletable?
1. The top two pixels and the bottom two pixels become separated; in effect breaking
up the object.
2. The top two pixels and the bottom two pixels are joined by a chain of pixels outside
the shown neighborhood. In this case, all pixels will encircle a hole, and removing the
central pixel will remove the hole, as in Figure 11.18.
To check whether a pixel is 4-simple or 8-simple, we introduce some numbers associated
with the neighborhood of a foreground pixel p. First define N
p
to be the 3×3 neighborhood
of p, and N
∗
p
to be the 3 ×3 neighborhood excluding p. Then:
A(p) = the number of 4-components in N
∗
p
C(p) = the number of 8-components in N
∗
p
B(p) = the number of foreground pixels in N
∗
p
For example, in Figure 11.20(a), we have
A(p) = 2
C(p) = 2
B(p) = 4
and in Figure 11.20(b) we have
A(p) = 2
C(p) = 1
B(p) = 5
We can see the last example by deleting the central pixel and enumerating the components
of the remaining foreground pixels. This is shown in Figure 11.21. Simple points can now
A(p) C(p)
FIGURE 11.21: Components of N
∗
p
be characterized entirely in terms of the values of A(p) and C(p):
A foreground pixel p is 4-simple if and only if A(p) = 1, and is 8-simple if and only
if C(p) = 1.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.