N

This equation forms the core of the chamfer matching algorithm. It is possible, but not common, to apply this equation directly using a gray-values image for F. In general, for FIGURE 1 Illustration of the process of chamfer matching in two dimensions. From one image, a distance transform is made. A surface plot of the distance transform image looks like a groove or "chamfer." The bottom of the groove corresponds with the feature to be matched. The process of chamfer matching is like letting a wire (which represents a drawing from another image) fall into the groove. This corresponds to minimizing the distance between both features. Note that to improve the visualization in this figure, the distance transform has been clipped at a certain level.

FIGURE 1 Illustration of the process of chamfer matching in two dimensions. From one image, a distance transform is made. A surface plot of the distance transform image looks like a groove or "chamfer." The bottom of the groove corresponds with the feature to be matched. The process of chamfer matching is like letting a wire (which represents a drawing from another image) fall into the groove. This corresponds to minimizing the distance between both features. Note that to improve the visualization in this figure, the distance transform has been clipped at a certain level.

chamfer matching, the image F is obtained by segmenting the input image and applying a distance transform to the result. In a distance transform, the pixel value gives the shortest distance to the segmented feature , so that cost function CMEAN is an accurate estimate of the average distance between the segmented image features in both images. This function must be minimized to achieve image registration. In practice it is useful to express r and T in world coordinates, i.e., using centimeters instead of pixels, since this reduces the required number of coordinate transformations to interpret the matching result and allows easy matching of calibrated images without including scaling in the optimization procedure. Note that (when using a distance transform for F) Eq. (2) is equivalent to average absolute distance between the drawing and the feature in image F. For that reason, we call Eq. (2) the MEAN cost function. An alternative cost function is RMS:

global shape distortions. However, these cost functions are highly sensitive to outliers.

Equations (2) and (3) illustrate a few key features of the chamfer matching algorithm. First of all, the cost function is computed in only N steps, where N is the number of points in drawing r. For practical applications, Nmaybe on the order of a few hundred points for 2D to a few thousand points for 3D image registration. Second, the algorithm can be easily extended to subpixel accuracy by interpolating image F, e.g., using bilinear or trilinear interpolation. Our practical experience is that (linear) interpolation also drastically improves the performance of chamfer matching, since it causes the cost function to vary more smoothly as a function of T. Finally, the algorithm can easily be extended to handle the situation where the images to be matched do not overlap completely. This means that some of the transformed contour points are invalid, e.g., they fall outside the area/volume covered by image F. The solution is to ignore these points, i.e., assign them a value of zero in the sum and reduce the value of N. To avoid the situation in which zero points are valid, the cost function is set to an arbitrary high value when this occurs.

An essential component of the chamfer matching algorithm is the distance transform. The type of distance transform determines the accuracy with which the cost function describes the distance between the features in both images. In practice, good results have been obtained both with a city-block and with chamfer distance transforms, which are more simple to compute than the "true," Euclidean, distance. The city block distance is the shortest distance between two points using only horizontal and vertical movements. The chamfer distance is the shortest distance allowing movements along diagonal lines as well. The distance transform need only be computed once, and high-speed recursive algorithms exist for this purpose. For example, a simple city block distance transform of an arbitrary complex binary image in two dimensions may be computed with only eight operations per pixel, as illustrated next. Setting the segmented pixels to zero and all others to a high value, we can apply the following basic recursive series for a distance transform in one dimension (e.g., ):

This cost function is equivalent to the RMS distance between the drawing and the feature in image F. Similarly, one can define the MAX cost function, which correspond with the maximum distance. The usefulness of these cost functions depends on the problem. The MEAN cost function performs very well in the absence of global shape distortions (it is highly insensitive to outliers in the point list), whereas the RMS and MAX cost functions are more suitable in the presence of small where a defines the size of the pixel in world coordinates (a> 0), f is the input data, g is the output data, x is a counter, and M is the number of data points. To complete the distance transform, the same recursive operation must be performed backwards through the result of Eq. (4), i.e.,

To perform a city-block distance transform in two dimensions, first set all segmented pixels in image F to zero (their distance will be zero) and all other pixels to a high positive value. Then Eqs (4) and (5) must be applied, first to each row and then to each column of the image, writing the result back into the image. To obtain a chamfer distance transform (an eight-connected distance), Eqs. (4) and (5) must next be run over all diagonals of the image in both directions. Extension to three dimensions and nonequidistant image slices is trivial . Borgefors gives an extensive description of recursive distance transforms . More recently, several groups have also developed true Euclidean distance transforms that have a reasonable speed [11,19,38]. The performance gain obtained by using a Euclidean distance transforms in the chamfer matching algorithm is, however, limited because close to a perfect match all distances are zero irrespective of the type of distance transform.

An alternative for the use of a distance transform would be search the closest point of the segmented features of F for each of the points in drawing r (the iterative closest-point algorithm) [3,13,27,39]. In such an implementation, the speed is limited by the geometrical searching: For each feature point in one image, the algorithm would inspect all or many points of the feature of the other image. Often, the searching algorithm also poses constraints on the shape of the applied features. So, in essence, the chamfer matching algorithm is an efficient and flexible implementation of the iterative closest-point matching algorithm.