Exact Euclidean distance transformations.

Many different approaches are possible to compute exact Euclidean DT, i.e. without the errors made by the 4SSED and 8SSED algorithms. Historically, the first idea was to consider distance transformations as the result of a filtering process [185,147,77,41] (sec. ). A $3 \times 3$ mask is applied repeatedly on all image pixels until a stable solution is reached. Unfortunately, this can only be implemented efficiently on a parallel processing array.

A second approach modifies the approximate algorithms in order to incorporate the useful mechanisms of the parallel processing methods above, while keeping a reasonable computational cost. This leads to region-growing [168,127,42] (sec. ) and raster scanning [112,146] (sec. ) algorithms.

A third approach extends an algorithm originally proposed by Rosenfeld [132] for coarser metrics, where columns and rows are scanned independently [118,140] (sec. ). Finally, a last approach is based on the explicit computation of the Voronoi diagram of the object pixels in the continuous plane [17,69,44] (sec. ).