Vector propagation.

In order to better approximate the Euclidean distance transformation, Danielsson [37] proposes to propagate more information than just the distance. Instead, he uses a two-component descriptor: |p_x-q_x|,|p_y-q_y| (also written |dp_x|,|dp_y|), the absolute values of the relative coordinates of the nearest object pixel. The Euclidean distance can of course be deduced from this information using ().

The algorithm is similar to the chamfer DT algorithm described in section , with one major change. During the process, the descriptors need to propagate in all directions. Unfortunately, raster scanning with masks such as those of Figure only provides a 135^o propagation angle. Danielsson opens this angle up to 180^o by modifying the raster scanning procedure. At each step in the vertical direction, the row is scanned both from left to right and from right to left. The masks considered are then those of Figure .

  

Figure 2.4: Masks used in Danielsson's 4SED (left) and 8SED (right) algorithms

On the negative side, this back and forth scanning requires more computations. This adds up to the extra computational cost of comparing descriptors - which requires the evaluation of () - instead of scalar distance values in the chamfer DT. On the positive side, it allows us to chose the smaller 4-direct neighborhood instead of the 8-direct one. Danielsson names the respective algorithms "FOUR-point Sequential Euclidean Distance mapping" or 4SED, and "EIGHT-point Sequential Euclidean Distance mapping" or 8SED.

Unfortunately, these algorithms do not always provide the exact Euclidean DT. At Figure (left), pixel q gets $dist_e=\sqrt{3^2+0^2}=3$ instead of $dist_e=\sqrt{2^2+2^2}=\sqrt{8}$. Indeed, 4SED only allows propagation from a pixel to its 4-direct neighbors. In this case, none of the 4-direct neighbors of the erroneous pixel had the same nearest object pixel. This particular error would have been avoided by using the 8SED algorithm instead. But even 8SED isn't completely error-free, as illustrated at Figure (right), pixel q gets $dist_e=\sqrt{170}$ while it should have received $\sqrt{169}$ instead. Actually, whatever the size of the neighborhood considered, it will be possible to find object pixel configurations where errors do occur. This is analyzed thoroughly at section .

  

Figure 2.5: Errors made by Danielsson's 4SED (left) and 8SED (right) algorithms. Object pixel p₂ is hidden from pixel q by object pixels p₁ and p₃, that are closer to r₁ and r₂, respectively. Left: q-p₁=(3,0), q-p₂=(2,2), q-p₃=(0,3). Right: q-p₁=(13,1), q-p₂=(12,5), q-p₃=(11,7)

Nonetheless, the 4SED and 8SED are very good approximations of the Euclidean DT. First, they provide exact results for most pixels. Secondly, Danielsson proves that, for 4SED, the maximum absolute error is at most 0.29 pixel units. The maximum relative error is that illustrated at Figure , i.e. $(3-\sqrt{8})/\sqrt{8} = 6.1\%$. With 8SED, the absolute error is bounded by 0.09 pixel units and the maximum relative error is that of Figure , i.e. $(\sqrt{170}-13)/13 = 0.3\%$. ^2.1.

Ye [186] introduces 4SSED and 8SSED, similar algorithms producing the signed Euclidean distance transformations. This is done by propagating (p_x-q_x,p_y-q_y) instead of their absolute values. This is achieved by replacing the masks of Figure by signed masks, i.e. masks where the x-coordinate is negative on the left column, and y-coordinate is negative on the upper row.

Leymarie [95] shows that Danielsson's algorithm, with some minor changes, can be implemented as efficiently as chamfer DT algorithms. First, he uses the dist_E metric for all comparisons made in the algorithm, so that only integer operations are needed. Secondly, he stores explicitly 3 values for each pixel, i.e. the 2 relative coordinates (dp_x,dp_y) of the nearest object pixels and the value of the dist_E distance. With this information, the distance computations are simplified. Knowing the value of dist_E(dp), we have

 

$$dist_E(dp+(\pm 1,0)) (dp_x\pm 1)^2 + dp_y^2$$ =

$$dist_E(dp) \pm 2.dp_x + 1$$ =

$$dist_E(dp+(0,\pm 1)) dp_x^2 + (dp_y\pm 1)^2$$ =

$$dist_E(dp) \pm 2.dp_y + 1$$ =

$$dist_E(dp+(\pm 1,\pm 1)) (dp_x\pm 1)^2 + (dp_y\pm 1)^2$$ =

$$dist_E(dp) \pm 2.(dp_x + dp_y \pm 1)$$ =

$$dist_E(dp+(\pm 1,\mp 1)) (dp_x\pm 1)^2 + (dp_y\pm 1)^2$$ =

$$dist_E(dp) \pm 2.(dp_x - dp_y \pm 1)$$ = (2.18)

This reduces the computational cost of a distance to one addition, one shift ($\times 2$) and one increment, instead of two multiplications, one addition and one square root operation in (). Therefore, the computational complexity of the 4SED and 8SED algorithms becomes comparable to that of the chamfer approximations.

Ragnelmam [127,126] adapts the works of Piper [122] and Verwer [167] to the Euclidean DT. Instead of raster scanning, he uses ordered propagation (a.k.a. contour-processing) where the image pixels are considered by increasing distance values. In [126], this is done by bucket sorting with as many buckets as possible distance values. In [127], he uses ordered propagation by thresholding, where all pixels in the propagation front are stored in the same dynamic list, but are only propagated if their value is below the current distance.

In contrast with raster scanning algorithms, the propagation DT uses a ``write'' formalism instead of a ``read'' formalism. In the raster scanning method, the basic operation is the updating of the value one pixel based on the information coming from several neighbors. In the propagation method, the basic operation is the updating of all neighboring pixels based on the value of the one propagated pixel.

The additional computational cost of the dynamic data structure needed to implement ordered propagation is compensated by two factors. First, using Danielsson's back and forth raster scanning, many pixels are updated several times, up to 4 times. Ideally, pixels only need to be updated once, when they get their final value. Ordered propagation approaches this behaviour because pixels are only propagated once. Secondly, the information from a pixel only needs to be propagated in the direction of increasing distances and not backward, which reduces the size of the neighborhoods used. Adapting Montanari's theorem [109] (section ) to Euclidean metrics, Ragnelmam shows that, apart from the two first iterations, only one or two neighbors need to be considered for propagation, as illustrated at Figure .

  

Figure 2.6: Directional neighborhoods used by Ragnelmam's ordered propagation algorithm. Left: for D(p)=0. Center: for D(p)=1. Right: for D(p)>1.

In [128], Ragnelmam shows that the 8SSED algorithm can also be implemented with separable raster scans, i.e. without the back and forth scan at each line suggested by Danielsson. Each scan, with a specific scanning order and a given mask, can support the propagation of information within some part of the direction space. Any SSED algorithm should include enough scans to support propagation in all directions. In 2 dimensions, it is possible to produce the approximate EDT in 3 raster scans only, with the masks and scanning orders illustrated at Figure . In three dimensions, 4 scans are sufficient with the masks of Figure .

  

Figure 2.7: Ragnelmam's 3-scan 8SSED. Top: masks used. Bottom: supported propagation directions.

  

Figure 2.8: Masks for Ragnelmam's 4-scan 26SSED.

In n dimensions, algorithms with a minimal number of scans are harder to design. Instead, he recommends to use "corner" masks, i.e. masks including half of the 2n-direct neighbors, 1 out of 2 for each direction. He shows that the approximate (2n)SSED algorithm can always be generated in 2ⁿ raster scans over the image ^2.2.

Finally, Embrechts and Roose [44] show how the 4SSED algorithm can be implemented efficiently on multi-processor computers. Each processor applies the 4SSED on a sub-region of the image. Before that, communications between the processors determine the list of object pixels that influence the sub-region although they are located in another one. The parallelization procedure itself does not introduce any error in Euclidean DT. The only reason why Embrechts' algorithm is approximate is that the local algorithm used by each processor is the approximate 4SSED. Therefore, this parallelization procedure will be further studied in section together with other transformations based on the Voronoi diagram.