Fast Euclidean distance transformation in two scans using a 3 × 3 neighborhood

Cuisenaire and Macq [Comp. Vis. Image Understand., 76(2) (1999) 163] proposed a fast Euclidean distance transformation (EDT) by propagation using multiple neighborhoods and bucket sorting. To save the time for bucket sorting and to reduce the complexity of multiple neighborhoods, we propose a new, simple and fast EDT in two scans using a 3 × 3 neighborhood. By recording the relative x- and y-coordinates, an optimal two-scan algorithm can be developed to achieve the EDT correctly and efficiently in a constant time without iterations.