Fast multidimensional parallel Euclidean distance transform based on mathematical morphology

Abstract

The paper presents a novel Euclidean distance transform algorithm formulated under the mathematical morphology approach. The distance transform is an erosion by a structuring function dependent on the distance metric used. To achieve high speed performance, the squared Euclidean distance structuring function is decomposed into a family of four one-dimensional two-point structuring functions. The erosion algorithm is based on a propagation scheme which resulted in an overall Euclidean distance transform algorithm very simple to code and understand, yet with speed performance compared to the Chamfer 3-5-7 sequential raster and anti-raster algorithm.