On solving exact Euclidean distance transformation with invariance to object size

Frank Y. Shih, Chyuan Huei T. Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

A distance transformation is to convert a digital binary image that consists of object (foreground) and nonobject (background) pixels into a gray-scale image in which each object pixel has a value corresponding to the minimum distance from the background by a distance function. Since the Euclidean distance measurement has metric accuracy as in the continuous case and possesses rotation invariance, it is very useful in image analysis and object inspection. Unfortunately, due to its nonlinearity, the global operation of Euclidean distance transformation (EDT) is difficult to decompose into small neighborhood operations. This paper presents two novel efficient algorithms on EDT using integers of squared Euclidean distances in which the global computations can be equivalent to local 3 × 3 neighborhood operations. The first algorithm requires only a limited number of iterations on the chain propagation; however, the second algorithm can avoid iterations and simply requires two scans of the image. The complexity of both algorithms is achieved to be only linearly proportional to image size.

Original languageEnglish (US)
Title of host publicationIEEE Computer Vision and Pattern Recognition
Editors Anon
PublisherPubl by IEEE
Pages607-608
Number of pages2
ISBN (Print)0818638826
StatePublished - Dec 1 1993
EventProceedings of the 1993 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - New York, NY, USA
Duration: Jun 15 1993Jun 18 1993

Publication series

NameIEEE Computer Vision and Pattern Recognition

Other

OtherProceedings of the 1993 IEEE Computer Society Conference on Computer Vision and Pattern Recognition
CityNew York, NY, USA
Period6/15/936/18/93

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint

Dive into the research topics of 'On solving exact Euclidean distance transformation with invariance to object size'. Together they form a unique fingerprint.

Cite this