A linear-time algorithm for Euclidean feature transform sets

The Euclidean distance transform of a binary image is the function that assigns to every pixel the Euclidean distance to the background. The Euclidean feature transform is the function that assigns to every pixel the set of background pixels with this distance. We present an algorithm to compute the exact Euclidean feature transform sets in linear time. The algorithm is applicable in arbitrary dimensions.