TY - GEN

T1 - On solving exact Euclidean distance transformation with invariance to object size

AU - Shih, Frank Y.

AU - Yang, Chyuan Huei T.

PY - 1993/12/1

Y1 - 1993/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027795296&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027795296&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027795296

SN - 0818638826

T3 - IEEE Computer Vision and Pattern Recognition

SP - 607

EP - 608

BT - IEEE Computer Vision and Pattern Recognition

A2 - Anon, null

PB - Publ by IEEE

T2 - Proceedings of the 1993 IEEE Computer Society Conference on Computer Vision and Pattern Recognition

Y2 - 15 June 1993 through 18 June 1993

ER -