Extending the approximate EDT to 3D

In order to produce approximate 3D Euclidean DT, Danielsson [37] and Leymarie [95] propose a complex 6 scans algorithm. It includes a forward and a backward scan over the whole image, plus opposite scans at the plane and line level. In total, it requires 12 comparisons per pixel with direct neighbors and 36 for the $3 \times 3 \times 3$ neighborhood.
In [128], Ragnelmam proposes two algorithms with independent raster scans. The corner EDT can be extended to any dimension. It uses 2^D scans involving D direct neighbors in D dimensions. In 3D, it requires to perform 24 comparisons per pixel. Alternatively, he proposes a 4 scan algorithm with the neighborhoods of figure . It requires 48 comparisons per pixel.

  

Figure 6.1: Neighborhood used for the 3D ordered propagation algorithm. Left: D(p)=0 Right: $D(p) \geq 1$ for one eighth of the directions space.

Finally, it is possible to extend the PSN algorithm of chapter 3 to 3 dimensions. The only modification required is that 3D neighborhoods should be used. Instead of those of figure , we use those of figure . For object pixels, the complete $3 \times 3 \time 3$ neighborhood is checked ^6.1. For other pixels, only direct neighbors n such that in the same direction as dp are considered. This algorithm requires approximately 3 comparisons per pixel.