The chain code of a shape outline is the sequence of directions from one discretized boundary point to the next. In an example, starting at an arbitrary boundary point, the nearest boundary point in counterclockwise direction could lie to the right (east), followed by the next point northeast and the next point north, followed by another point to the north, and so on. The chain code would be E-NE-N-N. By replacing the compass directions by numbers as shown in Figure 9.6, the sequence of directions becomes 6-7-0-0. To generate the chain code of a shape, the grid on which the boundary points are discretized does not necessarily coincide with the image pixels.
The normalized central moments are then defined through
FIGURE 9.6 Enumeration of the possible directions from one grid point to its neighbor.
Rather, a coarser grid is generally desirable to avoid encoding small irregularities of the shape boundary that may be a consequence of image noise or the segmentation process. The example in Figure 9.7 shows the microscopic image of a fluorescently stained chromatid. An 8 x 8 pixel grid is superimposed (indicated by + signs), and part of the outline is indicated (thick white line starting at S). In this example, the chain code would start with 6-7-6-7-7-0-0-7-0-0-0 •••.
Chain codes can be computed on an 8-neighborhood (as in the example of Figures 9.6 and 9.7) or on a 4-neighborhood. In that case, only the directions 0, 1,2, and 3 would exist. The shape needs to be thick enough that its boundary can be circled unambiguously. If two parts of one feature are linked by a single diagonally connected pixel, this pixel could be traversed diagonally or at a 90° angle.
FIGURE 9.7 Generation of the chain code in an example image, a fluorescent microscope image of a chromatid. The chain starts at the lowermost point (labeled "S") and proceeds in a counterclockwise direction. The discrete grid is 8 x 8 pixels.
The resulting chain code depends on this decision. Furthermore, the chain code depends on the starting pixel. A suitable choice of a starting pixel, for example, the boundary point with the largest distance to the centroid, is necessary (but not sufficient) to provide a rotation-invariant shape description. In an 8-neighborhood, the chain code varies with the rotational angle of the shape because the diagonal links are longer than the horizontal and vertical links. Russ proposes to subdivide each link into a sequence of smaller links, five for the horizontal and vertical links, and seven for the diagonal links.34 The rationale is that 7/5 is a good approximation of \fl with the consequence that each link, whether diagonal or horizontal/vertical, would have approximately the same length. Under this definition, the first two links in Figure 9.7 would be represented by the sequence 6-6-6-6-6-7-7-7-7-7-7-7. Dhawan describes an adaptive scheme to subdivide the shape boundary.10 Two vertices are defined on the boundary. Although the initial vertices may be selected arbitrarily, the initial vertices are often placed at the end of the long axis or at points with high curvature. The maximum deviation of the line connecting the two vertices from the shape boundary is now determined (Figure 9.8A). If the line deviates from the curve more than a predetermined threshold distance e, a new vertex is created at the maximum distance of the curve from the line, and the line is subdivided to touch the new vertex (Figure 9.8B). This divide-and-conquer approach is repeated until the approximation of the curve is satisfactory (i.e., each segment deviates less than € from the curve). The original line can now be used in the opposite direction to approximate the other half of the shape. At the end of this process, the shape is approximated by a polygon with sides that are not necessarily at 0° and 45°. In a last step, the sides are subdivided into links of the chain with a horizontal, vertical, or diagonal direction and of equal length by means of a suitable algorithm, such as the Bresenham algorithm.5
FIGURE 9.8 Approximation of a shape outline by line segments. The maximum distance of a line segment from the curve is determined (A), and if it exceeds a threshold distance, a new vertex is created and the line is split to touch the new vertex (B).
The idea of chain codes can now be improved further by considering the orientation differences between successive segments in a counterclockwise direction, that is, the angle between two consecutive chain segments in increments of 45°. If the difference is positive in counterclockwise direction, positive differences indicate a convex section, and negative differences indicate a concave section of the shape boundary. Furthermore, symmetries of the shape are represented by symmetric sections of the differential chain code.
To extract quantitative metrics that describe the shape, the histogram of the differential chain code can be considered. In the differential chain code histogram, a strongly elongated shape would be dominated by the value zero. Irregular shapes would have higher histogram values for larger angular changes. A method that provides even more information about the shape was presented by Iivarinen et al.19 Starting with the polygonal approximation of the shape, each segment of the polygon is in turn used as a reference line. For all segments except the one used as a reference, the angle 0 to the reference line, its minimum and maximum distances, dmin and dmax, respectively, are computed. A two-dimensional histogram of the distance and the angle, termed a piecewise geometric histogram, is filled by incrementing all histogram bins with angle 0 from the smallest to the largest distance, as demonstrated in Figure 9.9. Like all multidimensional histograms, it requires a large number of data to be meaningful. Iivarinen et al.19 chose a large bin size to limit the size of the histogram to 8 x 8 bins, and a 16-element feature vector was extracted from the conditional probabilities over each row and column.
FIGURE 9.9 Construction of a pairwise geometric histogram. One line of the polygon that approximates the shape is selected as reference line (thick line). For each of the remaining sides of the polygon, the angle 0 to the reference line (dashed line) and the minimum and maximum distances (dotted lines) are computed. In the pairwise geometric histogram, all bins for angle 0 and for all distance values between dmin and dmax are incremented.
