Propagation with a single neighborhood

In a propagation algorithm, the pixels should ideally be updated only once, when they receive their final value. In other words, the propagation from one object pixel should be restricted to the pixels of its tile in the Voronoi diagram. In order to achieve this, the propagation order should be the same as the metric order. In other words, the pixels in the propagation front should be sorted by increasing distance value before being propagated. As shown by Verwer [167] for constrained chamfer DT and Ragnelmam [127] for Euclidean DT, this can be accomplished by bucket sorting of the pixels in the propagation front.

Instead of using a single list, pixels to be propagated are stored in a number of buckets, one for each possible dist_E(p,q) value. Indeed, dist_E(p,q) is an integer if p and q are located on an integer grid. Thus, it is an appropriate choice for the index d for the buckets, that are processed by increasing index values. For each pixel p in the propagation front, we store its coordinates (p_x,p_y) and its coordinates (dp_x,dp_y)=(p_x-q_x,p_y-q_y) relatively to the nearest pixel q of the object O. This gives the following algorithm, which we call "Euclidean Distance Transformation by Propagation using a Single Neighborhood", or EDT-PSN.

Algorithm 1   EDT by Propagation with a Single Neighborhood  

If N is the 4-direct neighborhood, we have $dist_E(dp+n) \leq (\sqrt{d}+1)^2 = d + 2.\sqrt{d} + 1$. Thus, the termination condition - that all buckets are empty - is true when the last $(2\sqrt{d}+1)$ buckets are empty. With the 8-direct neighborhood, the whole bucket structure is empty as soon as the last $2\sqrt{2d}+2$ buckets are empty.

As pointed our earlier [167], an efficient implementation of the buckets' data structure requires a memory allocation in chunks for the dynamic lists. In what follows, we use chunks of 16 elements, but a large range of values is acceptable, as discussed at section .

Also, special care should be given to the efficient computation of dist_E( dp + n ). Leymarie [95] recommends to use eq. (), which only requires to use additions, one shift and one increment. Instead, we routinely use lookup tables for $sq[\pm i]=i^2$, so that dist_E(dp+n)=sq[dp_x+n_x]+sq[dp_y+n_y]. This has a similar computational cost and is more general when n belongs to a large neighborhood, as we use later.

  

Figure 3.1: Directed neighbors to consider when using 4-direct neighborhoods

Finally, as shown by Ragnelmam [127], at most 2 neighbors need to be considered in the propagation phase, as soon as d>1. For the 8-direct connectivity, this means the neighbors of figure . The neighbors for the 4-direct connectivity are found in figure .