Bucket sorting algorithm

In order to define an efficient implementation of the B_d-geodesic DT, we restrict the class of paths under consideration to the paths $\{p_1,p_2,...,p_m\}$ such that

 

$$\forall \; 1 \leq i < m-1 \; , d_N(p_i,p_{i+1}) \leq d$$

$$\; \; \exists n \in N_4 \; \vert \; d_N(p_i,p_i+n) > d$$

$$\mathrm{for} \; i = m \; , 1 \leq d_N(p_{i-1},p_i) \leq d$$ (8.6)

That is, all steps but the last one are approximately of length d. This slightly reduces the accuracy of the EDT approximation by restricting the path directions to those of the edge of B_d, instead of the complete ball. The accuracy of the EDT approximation is studied in section .
On the other hand, it makes the implementation of the DT much easier. For all p such that $D(p) \leq d$, the DT can be computed similarly to the PSN algorithm in chapter 3. For $d < D(p) \leq 2.d$, the distances can be computed by propagating from the edge of $O \oplus B_d$, i.e. $\delta(O \oplus B_d)$. For those pixels, D(p) is defined as

$$D(p) = \min_{p' \in \delta(O \oplus B_d)} \{ D(p') + dist_e(p,p') \}$$ (8.7)

Similarly, for $2.d < D(p) \leq 3.d$, we propagate from the edge of $O \oplus B_d \oplus B_d$, and so on. More generally, the value of D(p) for a pixel p can be split into two terms:

 

$$\sum_{i=1}^{m-1}d_N(p_i,p_{i+1}) \; \; \; \mathrm{with} \; \; p_m=p$$ D(p) =

$$\sum_{i=1}^{m-2}d_N(p_i,p_{i+1}) + d_N(p_m-1,p_m)$$ =

= D(p_m-1) + d_N(p_m-1,p_m) (8.8)

where $p_{m-1} \; \in \; \delta(O \oplus B_d \oplus ... \oplus B_d)$ (m-1 times) and $p \; \in \; O \oplus B_d \oplus ... \oplus B_d$ (m times).
In the following algorithm, we remember two values for each pixel in the propagation front. d_path corresponds to the first term of () and is the length of the path from p₁ to p_m-1. The vector dp is the relative location of p from p_m-1. It corresponds to the second term of ().
The algorithm proceeds step by step, first computing D(p) in $O \oplus B$, then in $(O \oplus B) \oplus B$, ... Within each step, the propagation is ordered by bucket sorting on dist_E(dp). When dist_e(dp) > d, the pixel is saved in a temporary buffer to be used in the following step.

Algorithm 8   B_d-geodesic DT by bucket sorting.