Efficient Computation of the Euclidean Distance Transform

We present a simple algorithm for the Euclidean distance transform of a binary image that runs more efficiently than other algorithms in the literature. We show that our algorithm runs in optimal time for many architectures and has optimal cost for the RAM and EREW PRAM.