Optimization on euclidean distance transformation using grayscale morphology

Frank Y. Shih, Hong Wu

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


A distance transformation converts a digital binary image that consists of object (foreground) and nonobject (background) pixels into a gray-level image in which all object pixels have a value corresponding to the minimum distance from the background. Computing the distance from a pixel to a set of background pixels is in principle a global operation that is often prohibitively costly. The Euclidean distance measurement is very useful in object recognition and inspection because of the metric accuracy and rotation invariance. However, its global operation is difficult to decompose into small neighborhood operations because of the nonlinearity of Euclidean distance computation. This paper presents three algorithms for Euclidean distance transformation in digital images by the use of the grayscale morphological erosion with the squared Euclidean distance structuring element. The optimal algorithm requires only four erosions by small structuring components and is independent of the object size. It can be implemented in parallel and is very efficient in computation because only the integer is used until the last step of a square-root operation.

Original languageEnglish (US)
Pages (from-to)104-114
Number of pages11
JournalJournal of Visual Communication and Image Representation
Issue number2
StatePublished - Jun 1992

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Media Technology
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering


Dive into the research topics of 'Optimization on euclidean distance transformation using grayscale morphology'. Together they form a unique fingerprint.

Cite this