A EUCLIDEAN DISTANCE TRANSFORM USING GRAYSCALE MORPHOLOGY DECOMPOSITION

A fast and exact Euclidean distance transformation using decomposed grayscale morphological operators is presented. Applied on a binary image, a distance transformation assigns each object pixel a value that corresponds to the shortest distance between the object pixel and the background pixels. Grayscale morphological erosion is known as an appropriate approach to this problem. However, these methods have been complex and time consuming. It is shown that the large structuring element required for the Euclidean distance transformation can be easily decomposed into 3 x 3 windows. This is possible because the square or the Euclidean distance matrix changes uniformly both in the vertical and horizontal directions. A simple extension for a 3-D Euclidean distance transformation is discussed. A rast distance transform for serial computers is also presented. Acting like thinning algorithms, the version for serial computers focuses operations only on the potential changing pixels and propagates from the boundary of objects, significantly reducing execution time. Nonsquare pixels can also be used in this algorithm. An example application, shape filtering using arbitrary sized circular dilation and erosion, is discussed. Rotation-invariant basic morphological operations can be done using this example application.