Parallel processing.

Yamada [185] combines Danielsson's 8SED masks (Fig. ) into the single $3 \times 3$ mask of Figure . This masks is applied iteratively over the whole image. The |dp_x|^t,|dp_y|^t descriptor of a pixel at iteration t is computed from iteration t-1 by adding the mask values to the descriptors of the 9 pixels covered by the mask and choosing the one that gives the minimum Euclidean distance. This process is iterated until no pixels change anymore.

  

Figure 2.9: Yamada's EDT. Left: the 3x3 mask. Center: result after 1 step. Right: result after two steps.

Yamada proves that this algorithm is an exact Euclidean DT. Indeed, the information is propagated with 8-direct neighborhoods, and respects the order defined by the dist_chess metric. Thus, in Figure , pixel r₁ is reached by the propagation front from p₂ at least one step earlier than by the propagation front from p₁. More generally, one can prove that the propagation, from an object pixel p to any of the pixels q in its zone of influence, is always possible along the shortest path made of diagonal steps only, followed by vertical or horizontal steps only.

In [147], Shih and Mitchell consider distance transformations as a gray-scale mathematical morphology operation. From a binary image f where object pixels have the value 0 and non-object pixels the value $+\infty$, they compute the gray-scale distance map $g = f \ominus k$, by eroding f with a structuring element k at least as large as the maximum distance in the image. The weights of this structuring element are the negative of their distance to the center.

Handling such a large structuring element is of course inefficient. Thus, they decompose it into smaller $3 \times 3$ elements as follows:

  

$$k_{(2n+1 \times 2n+1)} \max \{ k_{1(3 \times 3)}, k_{2(5 \times 5)}, ... , k_{n(2n+1 \times 2n+1)} \}$$ = (2.19)

$$k_{i(2i+1 \times 2i+1)} k_{i1(3 \times 3)} \oplus k_{i2(3 \times 3)} \oplus ... \oplus k_{ii(3 \times 3)}$$ = (2.20)

For instance, with n=2,

$$\begin{tabular}{ccccccccccccc} & & & & & & & $b_2$\space &... ...0$\space & $b_1$\space & $b_2$\space & \\ \end{tabular}$$ (2.21)

$$\begin{tabular}{ccccccccccccc} $b_2$\space & $b_1$\space &... ...b_1$\space & $b_2$\space & & & & & & & & \\ \end{tabular}$$ (2.22)

where the value of x does not matter, a₀=-1, $a_1=-\sqrt{2}$, b₀=-2, $b_1=-\sqrt{5}$ and $b_2=-\sqrt{8}$. In all $k_{i(2i+1 \times 2i+1)}$ structuring elements, only the outer weights matter. In all $k_{ij(3 \times 3)}$ structuring elements, the diagonal weights are zero.

With this method, the implementation of a $k_{(2n+1 \times 2n+1)}$ elements requires n(n+1)/2 gray scale erosions. Therefore, it can only be reasonably efficiently implemented on specialized parallel pipelined VLSI circuits such as in [1].

With Huang [77], Mitchell adapts his above method to the dist_E squared Euclidean metric. The decomposition of the structuring element becomes much simpler.

$$k_{(2n+1 \times 2n+1)} = k_{1(3 \times 3)} \oplus k_{2(3 \times 3)} \oplus ... \oplus k_{n(3 \times 3)}$$ (2.23)

 

-4i+2 -2i+1 -4i+2 (2.24)

$$k_{i(3 \times 3)} = -2i+1$$ 0 -2i+1

-4i+2 -2i+1 -4i+2

This only requires n erosions to implement a Euclidean distance transformation that is exact up to distance n. The computational cost is similar to Yamada's method.

Finally, in [41], Eggers proves that both Huang's and Yamada's parallel DTs can successfully be extended to anisotropic grids and to higher dimensions.