On solving exact Euclidean distance transformation with invariance to object size

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.