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.
All Science Journal Classification (ASJC) codes
- Signal Processing
- Computer Vision and Pattern Recognition
- Distance transformation
- Euclidean distance
- Image processing
- Object representation