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: