Implementation issues

Let us now consider how distance transformations can be computed. A direct application - for every point - of the definition of the distance between a point and an object is obviously not practical. On the other hand, we know that the distances vary smoothly in the distance map, so that it must be possible to deduce the value of the map in one pixel from the values of the map around it. That is the fundamental idea used in all DT algorithms.

The natural, human way to proceed would be the following: starting from the object, we first determine the distance for the points that are in its neighborhood, then to these neighbors' neighbors and so on, as illustrated at figure for the two first steps of the propagation. Several algorithms reviewed in the next chapter (sections , and ), as well as those of chapters 3, 6, 8 and 10 try to mimic this human approach.

  

Figure 1.5: DT by propagation. Original image - after first step - after second step

Generally speaking, computers are not gifted at mimicking humans. In particular, the above propagation process is not an easy thing to implement. Instead, several algorithms rely on the natural way for computers to scan the image: raster scanning. The image is processed row by row from the top-right pixel to the bottom-left pixel. Distance transformations by raster scanning require at least a forward scan (from top-right to bottom-left) and a backward scan (from bottom-left to top-right), as illustrated at figure . Algorithms of this type are reviewed in sections , and . Also, the algorithm of chapter 5 uses raster scanning.

  

Figure 1.6: DT by raster scanning. Original image - after forward scan - after backward scan

Finally, another computer-friendly method to scan the image is sometimes used. As seen at figure , the rows of the image are first considered independently from each other. Then, the image is considered column by column. Such algorithms are reviewed in sections and .

  

Figure 1.7: DT by independent scanning. Original image - after row-scan - after column-scan.

Beside the order in which the image is scanned, the other key issue in implementing a distance transformation is the type of information that is propagated. On a continuous plane, as suggested by our examples so far, the distance itself would be a sufficient information. Some of the algorithms, reviewed at section , apply this simple idea to the discrete image grid. It produces distance transformations with approximate (non-Euclidean) metrics, called chamfer metrics.

Alternatively, one can propagate the signed distance, as in section . This allows the generation of distance maps that are quasi Euclidean. Surprisingly, these maps are not guaranteed to be exact in all locations. While on a continuous plane, the nearest object pixel of a point can always be deduced from the nearest object pixels of the points in its immediate neighborhood, this is not always true on a discrete grid.

This is the key reason why producing distance transformation on digital images is a complex problem. As shown at section , many solutions have been proposed, but none is optimal.