Topology is a branch of mathematics that deals with the connectivity of shapes under certain transformations. A shape is said to be topologically invariant even if it is stretched and bent in rubber band fashion. A shape can be thought to be drawn on a sheet of rubber, and the shape would remain the same in terms of topology if the rubber sheet is stretched and distorted but not torn. A trail around a lake is the topological equivalent of the letter O, but if a bridge crosses the lake in the middle, thus connecting two sides of the trail, it becomes a topologically different shape, now the equivalent of the letter B. For shape analysis, the description in terms of topology is a description of connectivity. This notion leads to graph theory, where a graph is defined as a set of nodes (or vertices) that are connected by edges. In two dimensions, edges cannot cross each other, or they would create a new vertex (and with it, a topologically different structure).
FIGURE 9.12 The seven bridges of Konigsberg (only five of them exist today) and the associated graph, where each island is a vertex and each bridge is an edge connecting two vertices. The notion of island includes the right and left banks as idealized infinite islands.
The mathematician L. Euler proved in 1735 that there is no walk that crosses the seven bridges of Konigsberg once and only once (Figure 9.12). This proof initiated the field of topology. For the purpose of the topological description of a shape, the shape and length of the edges (here, the bridges) are not relevant. The graph in Figure 9.12 has four vertices (the two islands and the right and left banks) and seven edges (the bridges). Furthermore, the graph has four holes or loops. The Euler number e, also known as the Euler characteristic, is defined as
where v is the number of vertices, n the number of edges, and l the number of loops. For the graph in Figure 9.12, e = 1. In any graphlike structure, the values of v, n, l, and e are invariant with respect to rotation, scaling, and translation. Furthermore, they are also invariant under affine transformations. These values are therefore particularly suited to describe a meshlike structure.
For long branched or intertwined shapes, the underlying graph of vertices and connections can be extracted through skeletonization, a thinning process that reduces shapes to their medial axis. Mathematically, the medial axis can be defined as the set of centers of inscribed disks of maximum diameter that touch the shape boundary and are tangential to the boundary without intersecting it.9 A different but related definition uses the Euclidean distance from a pixel to the nearest background pixel: For each feature pixel, the distance to all background pixels is computed, and the background pixel with the minimum distance is determined. If two background pixels with the same minimum distance exist, the corresponding feature pixel belongs to the medial axis.4 Probably the most widely used algorithm to compute a skeleton is the iterative algorithm of Zhang and Suen,43 which, however, has the disadvantage of being very noise-sensitive. The skeletonization process is shown in Figure 9.13, where a fingerprint is thresholded to provide the binary image required for skeletonization and then thinned using the Zhang-Suen algorithm. A magnified section is shown in Figure 9.14. A vertex is any pixel where three or more edges are joined. Any edge that connects two vertices is called a link, any edge that is connected to only one vertex is called a branch, and the other end of the branch is termed an endpoint.
FIGURE 9.13 Example of a skeletonization process. A fingerprint (A, ridges are lighter than valleys) is thresholded (B), and the features—white ridges—are thinned by skeletonization.
A closed sequence of links and vertices is called a loop. The numbers of vertices, links, branches, and loops are the topological invariants. They describe the connectivity of the network independent of its position, scale, or rotation, and the metrics are theoretically invariant under affine transformations. However, in practice, even minor changes of the binary images can cause major changes in the network. An example is given in Figure 9.15. The skeleton of a rectangle is a line (although under alternative definitions the medial axis transform would contain four diagonal branches). If the rectangle contains single black pixels, the skeleton loops around those pixels. In addition, even the slightest irregularity in the outline of the rectangle would create additional links. Although this behavior is topologically correct (the second rectangle in Figure 9.15 contains three holes, albeit small ones, so the graph contains three loops), it implies that even small changes in the preprocessing or segmentation step may cause large changes in the topological invariants. This sensitivity needs to be taken into account when a skeleton is being used for shape characterization.
FIGURE 9.14 Magnified section of the fingerprint skeleton in Figure 9.13.
FIGURE 9.15 Skeletonization of a solid rectangle and a rectangle with some random pixels in it.
The skeletonization algorithm by Zhang and Suen produces a skeleton by iterative conditional erosion of the feature. A pixel may not be deleted in the erosion process if it is an endpoint (i.e., it has fewer than two 8-connected neighbors) or if deleting this pixel would split an 8-connected feature into two. Zhang and Suen listed a number of neighborhood patterns that define a boundary pixel that may be eroded. The most efficient implementation is to use fate tables, encoded neighborhood pixel patterns that determine whether or not a pixel may be deleted. This is particularly convenient, as each neighbor may be encoded with 1 bit of a byte, and eight neighbors allow for 28 = 256 possible neighborhood patterns (combinations). The neighborhood and its associated code values are explained in Figure 9.16. The code values are powers of 2,and adding them together produces any value from zero to 255, depending on the bit pattern.
FIGURE 9.16 Definition of the neighborhood indices from 1 to 8, clockwise, and the associated code values (in italics).
If the top and both horizontal neighbors, for example, are set (i.e., neighbors numbered 1, 3, and 7), the resulting code would be 1 + 4 + 64 = 69. This index can be used to look up instructions on how to handle the central pixel (the fate of the pixel) in a table. The actual skeletonization is iterative; that is, any boundary points get eroded, if permitted by the fate table, until no more points have been eroded. The permissions are slightly different in alternating iterations, and the fate table reflects this difference. If the fate table holds a zero for a specific bit pattern, the pixel cannot be removed. If it holds a 1, the pixel may be removed in odd-numbered iterations; if it holds a 2, the pixel may be removed in even-numbered iterations; if it holds a 3, the pixel may be removed in any iteration. The sixty-ninth fate table entry, to stay with the example above, is zero. If such a bit pattern occurs, the central pixel may not be removed. The iterative skeletonization process that builds on this scheme is shown in Algorithm 9.4. This algorithm was used to generate Figure 9.13C from Figure 9.13B.
From the skeleton, the connectivity metrics (i.e., the topological invariants) can be determined, such as the number of nodes, links, branches, and loops. For this purpose the skeleton needs to be analyzed, and the following steps can be applied to obtain these metrics. In the first pass, the neighborhood connectivity of each pixel can be analyzed. Any pixel with exactly one neighbor is an endpoint and marks the start of a branch. A vertex is any pixel with more than two neighbors that do not touch other neighbors. Isolated dots (pixels with no neighbors) are also possible, but these are generally the consequence of noise. In the next pass over the image, the endpoints can be iteratively eroded until a vertex or another endpoint is reached. As a result, all branches are now marked. If, in this process, a pixel is eroded from two sides, it indicates the presence of a loop. Alternatively, the number of loops l can be found by subtracting the number of vertices from the number of links plus one. Finally, the Euler number can be computed through Equation (9.28). After this pass, the only structures remaining are isolated loops that have no vertices and one branch. If these were to be counted as loops, they would also contribute one branch each. In addition to these topological metrics, noninvariant metrics, such as the average length of links, branches, and loops, can be computed. Any of these metrics can be combined to provide a feature vector for shape description. In addition, it is possible to further process the skeleton to gain additional descriptors. The skeleton can also be examined for self-similar properties by estimating its box-counting or Minkowsky dimension (see Section 10.2). If a skeleton is characterized by few dominant links, their length and curvature may be examined.
The skeletonization algorithm of Zhang and Suen does not remove all four-connected pixels, as demonstrated in Figure 9.17. If a strictly 8-connected skeleton is required, an additional processing step needs to be added where 4-connected pixels are identified and removed, as in Figure 9.17B. The sensitivity of the skeletonization process toward noise and irregular shape outlines usually leads to numerous small branches, such as the 2-pixel branch coming off the downward link at the right side of Figure 9.17. The skeleton can be pruned to remove those branches. A simple pruning step would involve iterative erosion of endpoints with a limited number of iterations and under the constraint that erosion is strictly limited to branches (i.e., vertices and links cannot be eroded). At the end of this step, any branch that has fewer pixels than the number of iterations is removed completely. To restore the original, but pruned, skeleton, the erosion step is followed by iterative dilation of the endpoints under the constraint that only pixels that belonged to the original skeleton can be added by dilation. After this step, all branches that have not been pruned are restored to their original lengths.
Algorithm 9.4 Skeletonization of a binary image. The input image is IM(x,y) with size xmax and ymax and is assumed to be binary (a background pixel is zero, any nonzero pixels are foreground pixels). The algorithm applies the rules in the fate table repeatedly until no more pixels have been removed. Note that the AND operator represents a bit-wise logical operation.
FIGURE 9.17 The skeletonization process by Zhang and Suen leaves several 4-connected pixels in the network (A). Those pixels need to be identified and removed in a separate step if a strictly 8-connected skeleton is desired (B).
