The Euclidean k-distance transformation in arbitrary dimensions: a separable implementation

The signed k-distance transformation (k-DT) computes the k nearest prototypes from each location on a discrete regular grid within a given D dimensional volume. We propose a new k-DT algorithm that divides the problem into D 1-dimensional problems and compare its accuracy and computational complexity to the existing raster-scanning and propagation approaches.