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

Frank Y. Shih, Yi Ta Wu

Research output: Contribution to journalArticlepeer-review

88 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)195-205
Number of pages11
JournalComputer Vision and Image Understanding
Issue number2
StatePublished - Feb 2004

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition


  • Distance transformation
  • Euclidean distance
  • Image processing
  • Object representation


Dive into the research topics of 'Fast Euclidean distance transformation in two scans using a 3 × 3 neighborhood'. Together they form a unique fingerprint.

Cite this