The efficient algorithms for achieving Euclidean distance transformation

Frank Y. Shih, Yi Ta Wu

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


Euclidean distance transformation (EDT) is used to convert a digital binary image consisting of object (foreground) and nonobject (background) pixels into another image where each pixel has a value of the minimum Euclidean distance from nonobject pixels. In this paper, the improved iterative erosion algorithm is proposed to avoid the redundant calculations in the iterative erosion algorithm. Furthermore, to avoid the iterative operations, the two-scan-based algorithm by a deriving approach is developed for achieving EDT correctly and efficiently in a constant time. Besides, we discover when obstacles appear in the image, many algorithms cannot achieve the correct EDT except our two-scan-based algorithm. Moreover, the two-scan-based algorithm does not require the additional cost of preprocessing or relative-coordinates recording.

Original languageEnglish (US)
Pages (from-to)1078-1091
Number of pages14
JournalIEEE Transactions on Image Processing
Issue number8
StatePublished - Aug 2004

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'The efficient algorithms for achieving Euclidean distance transformation'. Together they form a unique fingerprint.

Cite this