Oriented neighborhoods

A final improvement to the algorithm is possible using the the following observation.

For a pixel p, whose relative location from the nearest object pixel is (dp_x,dp_y), the only neighbors (n_x,n_y) that need to be considered are those "in the same direction" as (dp_x,dp_y ). More precisely, if we consider dp_x and dp_y positive without loss of generality, the neighbors (n_x,n_y) to consider are such that

$$(n_x-1).\frac{dp_y}{dp_x} < n_y < 1+n_x.\frac{dp_y}{dp_x}$$ (3.9)

To prove this, let us consider figure . We wish to determine which neighbors (n_x,n_y) should be considered when propagating pixel p, whose location relative to the nearest object pixel q is (dp_x,dp_y). Let us first consider the upper bound. If q is also the nearest object pixel for p₁=p+(0,1), the upper bound for neighbors of p₁ is higher than for those of p, which guarantees no neighbor will be missed.

  

Figure 3.6: pixel p only needs to be propagated to neighbors within the grey area

On the other hand, we consider that $q_1 \neq q$ is the nearest object pixel of p₁. The limit between the tiles VP(q) and VP(q₁) is on the mid-perpendicular of q₁q. This mid-perpendicular would be a good upper bound for neighbors of p, since the information from q only needs to be propagated to pixels belonging to VP(q). This mid-perpendicular itself is bounded by the second inequality of (). Indeed, it intersects pp₁ between p and p₁, thus below p₁. Also, its angle must be lower than dp_y/dp_x. Otherwise, it would cross q₁q between q and q₁, which is impossible for the mid-perpendicular of q₁q with q₁ on an integer location. The proof for the lower bound is similar.

Applying this property reduces the computational cost of applying a $n \times n$ neighborhood from O(n²) to O(n). The " Euclidean Distance Transformation by Propagation using Multiple Oriented Neighborhoods", or EDT-PMON uses the same initialization and first propagation as algorithm . The second propagation works as follows:

Algorithm 4   EDT by Propagation with Multiple Oriented Neighborhoods  

One should notice that dp_y/(dp_x+1) is added to end instead of adding dp_y/dp_x as suggested by the upper bound of (). Indeed, in algorithm , the information from object pixel q may propagate one step out of VP(q) before it stops propagating. Using dp_y/(dp_x+1) relaxes the upper bound on n_y and addresses this problem.