Size-invariant four-scan Euclidean distance transformation

Frank Y. Shih, Jenny J. Liu

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


Distance transform (DT)(1) is used to convert a binary image that consists of object (foreground) and nonobject (background) pixels into another image in which each object pixel has a value corresponding to the minimum distance from the background by a predefined distance function. The Euclidean distance is more accurate than the others, such as city-block, chessboard and chamfer, but it takes more computational time due to its nonlinearity. By using the relative X and Y coordinates computed from the object pixel to the source mapping pixel of its neighbors as well as correction of particular cases, the Euclidean distance transformation (EDT) can be correctly obtained in just four scans of an image. In other words, the new algorithm achieves the computational complexity of EDT to be linear to the size of an image.

Original languageEnglish (US)
Pages (from-to)1761-1766
Number of pages6
JournalPattern Recognition
Issue number11
StatePublished - Nov 1998

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


  • Distance transform
  • Euclidean distance
  • Image processing
  • Recursive algorithm
  • Sequential algorithm
  • Skeletonization


Dive into the research topics of 'Size-invariant four-scan Euclidean distance transformation'. Together they form a unique fingerprint.

Cite this