Optimization on euclidean distance transformation using grayscale morphology

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.