A typical application

The best known application of distance transformations comes from pattern recognition. It consists of looking for a specific object in a binary image including objects of various shapes, positions, orientations, ... It is often referred to as ``chamfer matching'', because it was first used with the chamfer DT, an approximation of the Euclidean metric.

  

Figure 1.3: Chamfer matching: Top-left: original image. Top-right distance map. Bottom: distance map seen as a relief.

Let us consider the example of figure . In the binary image, we are looking for the letter T. First, we compute the distance transformation and produce the distance map in the upper right corner. The pattern we are looking for - the T shape - is then moved over the relief defined by the distance map. Under the action of gravity, the pattern slides over the relief until it reaches the lowest possible altitude. If this altitude is zero or close to zero, we have found a matching pattern in the image.

More formally, the matching criterion is the correlation of the searched pattern with the distance map. The pattern is located where this correlation reaches an absolute minimum.

Theoretically, a more simple matching criterion could be used: the correlation of the pattern with the original binary image. Indeed, this criterion also has an absolute minimum at the correct location. Nevertheless, the use of the distance transformation brings a major practical improvement, illustrated at figure . The distance-based criterion has smooth and wide minima, which allows the use of fast minimization algorithms. On the other hand, the simple criterion only has very abrupt and narrow minima, requiring the complete set of possible positions to be searched.

  

Figure 1.4: Matching criterion for the T shape. Left: convolution with the original image Right: Convolution with the distance map

There are many other types of applications of distance transformations. We review some in section , and present 4 medical imaging applications in chapters 4, 7, 9 and 11. The application of chapter 6 - the registration of medical images - is closely linked to chamfer matching.