Sequential processing by raster scanning.

In the above section, Ragnelmam's exact EDT was presented as an efficient implementation of Yamada's parallel algorithm. Alternatively, it could have been presented as an alteration of the approximate EDT by propagation from the same paper [127]. Similarly, Mullikin [112] and Shih [146] propose to produce exact Euclidean DT by modifying slightly Danielsson's raster scanning approximate algorithm.

Mullikin [112] proposes to process the image twice. First, he applies Danielsson's 4SED algorithm, which can leave a few errors. Typically, he finds about $2\%$ of errors for a $200 \times 200$ empty disk image. Secondly, he corrects those errors by applying a modified version of 4SED where the vectors are remembered and propagated if they are less than $\varepsilon$ longer than the distance at the current pixel. This requires to store, for each pixel p, the list of all object pixels at a distance between D(p) and $D(p)+\varepsilon$. He calls this algorithm $\varepsilon$VDT, where VDT stands for Vector Distance Transformation.

Mullikin shows that, with $\varepsilon = \sqrt{N}/N$ in N dimensions, $\varepsilon$VDT implements the exact Euclidean DT. Actually, he finds the following relations between $\varepsilon$ and the maximum error

 

$$( 1 - \frac{\sqrt{N}}{N} ) ( 1 - \varepsilon \sqrt{N})$$ E_max = (2.25)

$$\varepsilon \frac{N - \sqrt{N} - N . E_{max}}{\sqrt{N}.(N-\sqrt{N})}$$ = (2.26)

where N is the number of dimensions. From eq. , he finds the adequate $\varepsilon$ to ensure a given maximum acceptable error. This provides us with a number of trade-offs between $\varepsilon$VDT(0) where only exact ties are stored in the lists and the exact $\varepsilon$VDT(1), where all near ties up to $\varepsilon = \sqrt{N}/N$ are kept.

Of course, the increased accuracy has a computational cost. $\varepsilon$VDT(0) appears to be 10 times slower than 4SED. $\varepsilon$VDT(1) is itself approximately 10 times slower than $\varepsilon$VDT(0) for the test images Mullikin considers. Besides, it has a higher complexity. For $n \times n$ images, 4SED and $\varepsilon$VDT(0) are o(n²), but $\varepsilon$VDT(1) is between o(n²) and o(n³), depending on the image.

Shih and Liu [146] also propose to process the image twice, first with a variant of Danielsson's 8SED algorithm, then to detect and correct possible errors. They pre-compute the possible relative locations (p_x-q_x,p_y-q_y) for which an error could occur, and find out that those are extremely rare. For $100 \times 100$ images, errors can only occur for relative locations (12,5), (40,12), (48,10), (54,12), (60,13), (70,12), (72,12), (80,14) and (98,14) with $0 \leq p_y-q_y \leq p_x-q_x \leq 100$, and similar results for the other 8 angular sectors. This means 72 possible relative error locations out of $200 \times 200$, i.e. an error ratio of only $0.18\%$.

Thanks to this low error ratio, Shih suggests to detect possible errors by checking the distance values found by the approximate DT against a look-up table made from the above list. The very few possible error locations are then submitted to additional computations. The computational cost of the extra detection and correction step is negligible.

Unfortunately, this apparently optimal solution is flawed. In [26], we show that the possible relative locations for errors made by the 8SED algorithm are far more numerous than computed by Shih. Actually, the possible error ratio is close to $20\%$ for $100 \times 100$ images, and climbs to more than $50\%$ for images larger than $400 \times 400$. This makes the look-up table approach unpractical for error detection.

It should also be noted that the approximate Euclidean DT algorithm of section 2 of [146] does not work. Indeed, the 4-scan algorithm uses twice the same two scanning orders, while Ragnelmam [128] showed that any raster scanning algorithm for EDT should use at least 3 different scanning orders to support propagation in all directions.