Discussion.

Today, distance transformation is a mature domain, in the sense that, for most problems, optimal algorithmic solutions are known. The theoretical optimal complexity of a DT is obviously the complexity of the distance image it generates. For an $n \times n$ image, that means O(n²) for usual DTs and O(k.n²) for the k-DT. The aims of this discussion are

• to review the algorithms of sections and in the light of the possible applications of section .
• to discuss which algorithms are optimal and which problems still require algorithmic improvements.
• to stress the strong and weak points in the existing solutions, in order to suggest how such improvements can be achieved.

The generation, in two raster scans, of the approximate chamfer DT obviously has an optimal O(n²) algorithmic complexity. The best values for the chamfer masks are known, as well as good integer approximations. Chamfer DT can also be adapted to anisotropic grids, although it requires to compute the optimal mask values for every new anisotropy factor. The relative error is less than 8% for chamfer (3:4) masks and 2% for chamfer (5:7:11) masks.

On the negative side, one cannot improve the precision of the chamfer DT unless one uses much larger masks, which requires an unacceptable additional computational cost. Several applications may suffer from this. For instance, when computing centers of maximal disks, it is important that the shape of the disks be as circular as possible, which is only coarsely approximated by chamfer DT, as illustrated at figure . Similarly, skeletons generated from a chamfer DT do not have a good rotational invariance.

Also, for pattern matching applications, faster convergence can usually be reached if one can use the gradient of the DT in the maximization of the correlation. As illustrated at figure , the possible directions for the gradient of the chamfer DT are restricted to the directions available in the mask, while the full range of directions would be possible with the Euclidean DT.

Finally, chamfer DT doesn't scale well to higher dimensions. While it can still be generated in two scans over the image, it requires to use masks that contain 3^D-1 neighbors in D dimensions. In conclusion, chamfer DT should only be used for applications in 2 or 3 dimensions, where the precision of the DT is not a crucial parameter.

  

Figure 2.21: Disks generated with the chamfer(3:4), chamfer(5:7:11) and Euclidean metric

  

Figure: Direction of the gradient of the distance in the images of Figure . Left: chamfer(3:4). Center: chamfer(5:7:11). Right: Euclidean.

The approximate Euclidean DT algorithms of section also have an optimal O(n²) algorithmic complexity, both for the raster scanning and for the ordered propagation implementations. Implemented carefully, their computational cost is actually nearly as low as that of chamfer DT, with a much better precision. Errors only occur in a few locations while most of the distances are computed exactly.

Also, because it can be computed using only direct neighbors and not the diagonal ones, it scales quite well to higher dimensions. In D dimensions, one only needs to consider 2.D neighbors. Unfortunately, the raster scanning algorithm then requires 2^D scans. Instead, one should use the ordered propagation algorithm as soon as D>2. This algorithm is optimal.

On the negative side, these algorithms still don't provide a perfect Euclidean DT. For some applications, the non-systematic nature of the errors can cause problems. For instance, when one implements the morphological dilation, using () and the 8SED algorithm, of object $O = \{ p_1 , p_2 , p_3 \}$ in figure by a ball B of size 13, pixel q is mistakenly not included in $O \oplus B$. If one then applies a morphological erosion with the same ball - i.e the dilation of $(O \oplus B)^c$, the complement of $O \oplus B$ - the error is not repeated because there is no unfortunate arrangement of object pixels in $(O \oplus B)^c$. Therefore, the closing $O \bullet B =(O \oplus B) \ominus B$ does not include pixel p₂. This contradicts a fundamental property of openings and closings in mathematical morphology, that $O \circ B \subseteq O \subseteq O \bullet B$. For similar reasons, the exact reconstruction of the original object is not guaranteed from skeletons generated using an approximate Euclidean DT.

The precision of the exact Euclidean DT is of course perfect. Unfortunately, there is still no optimal (in terms of computation time) algorithm to produce it, which restricts its use in practical applications. Let us consider the five families of algorithms described in section .

First, the parallel EDT is obviously unpractical on general purpose computers. It requires as many scans over the image as the largest distance in the image, i.e. has a O(n³) complexity.

Among the exact EDT by propagation, Eggers' [42] algorithm is the most efficient. Unfortunately, in order to be exact, it can not use the optimal ordered propagation, but instead the natural propagation order of $3 \times 3$ neighborhoods. That can lead to multiple updates by successive propagation fronts. In the worst case - an oblique line with a 22,5^o inclination - it has a O(n³) complexity too. Practically, the computational cost is highly image-dependent, sometimes as low as that of approximate EDT, sometimes orders of magnitude slower.

The only raster-scan exact EDT - Mullikin's [112] $\epsilon$VDT(1) - has a complexity between O(n²) and O(n³) and is several orders of magnitude slower than the approximate EDTs.

Among the independent scans algorithms, Saito's [140] algorithm is the most efficient. The exact computational complexity of the method isn't assessed, but experiments show that it is more than O(n²).

Finally, the algorithms explicitly based on the computation of the Voronoi diagram of the object pixels do have an optimal O(n²) complexity. Unfortunately, the computations involved are so complex that the practical computational cost ends up being much larger than the cost of approximate EDT, Eggers' or Saito's algorithms.

In conclusion, none of these approaches leads to an algorithm that is both fast and asymptotically optimal. Fast algorithms, such as the approximate ones, Eggers' or Saito's, require that only a few simple operations be performed on each pixel. On the other hand, asymptotically optimal algorithms require to explicitly take into account the continuous nature of the Voronoi diagram. In chapters 3, 5 and 6, we show how both approaches can be combined efficiently.

The optimal algorithm to compute a Geodesic DT, constrained by a non-convex domain, was presented by Verwer [167]. The ordered propagation by bucket sorting has a O(n²) complexity, and the cost of the dynamic data structure it requires can be minimized with a careful implementation.

  

Figure 2.23: Shortest path through a maze. Left: computed with a chamfer geodesic DT Right: on a continuous plane.

On the other hand, the discrete geodesic DT is only a poor approximation of its continuous equivalent. In particular, the shortest paths it generates are restricted to steps along the directions available in the mask used during the propagation. For instance, for the commonly used chamfer(3:4) geodesic DT, paths are restricted to horizontal, vertical and 45^o diagonal steps, as illustrated at figure .

In chapter 8, we show how a quasi-Euclidean geodesic DT can be generated, using balls of any chosen size in the propagation process, while keeping the optimal computational cost of the propagation algorithm.

Finally, the k-DT algorithm proposed by Warfield [175] is obviously non optimal, it requires O (2^Dn^D(D+1)k) distance computations and O $(2^Dn^D(D+1)k.\log((D+1)k))$ comparisons on a $n \times n \times ... \times n$ (D times) image. It is also not an exact DT, since it is based on Ragnelmam's approximate EDT [128], but this does not matter much in the k-NN classification application.

In chapter 10, we show that k-DT can be implemented optimally, i.e with O(n^D.k) distance computations and O(n^D.D.k) comparisons.