Fast Euclidean Distance Transform Based on Contour Tracking
Xiang Liu · Chinese Journal of Computers · 2006
A fast 2-D Euclidean distance transform algorithm based on contour tracking and stripping is presented in the paper. Begining with the outest layer, the algorithm tracks the contour of the object, from outer to inner and layer by layer. For every contour pixel being tracked, the Euclidean distance to the nearest background pixel is computed by the shortest distance information propagated from its neighbors. Moreover, a list is designed to store necessary information for updating the distance of the object pixels that have been transformed to solve the problem that the distance-propagating path may be changed. After every layer of contour is tracked and the distance is computed, the pixels on this contour are deleted from the object area and the next tracking starts. This course is processed repeatedly until the area of object is empty. In contrast with all fast algorithms previously published, this algorithm produces perfect Euclidean distance maps in a time linearly proportional to the number of pixels in the image. The computational cost is twice less than that of 3×3 chamfer distance transform, and tens and thousands of the Euclidean distance transform algorithms based on bucket-sorting.