A linear time algorithm for computing exact Euclidean distance transforms of binary images in arbitrary dimensions
Top Cited Papers
- 19 February 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 25 (2) , 265-270
- https://doi.org/10.1109/tpami.2003.1177156
Abstract
A sequential algorithm is presented for computing the exact Euclidean distance transform (DT) of a k-dimensional binary image in time linear in the total number of voxels N. The algorithm, which is based on dimensionality reduction and partial Voronoi diagram construction, can be used for computing the DT for a wide class of distance functions, including the L/sub p/ and chamfer metrics. At each dimension level, the DT is computed by constructing the intersection of the Voronoi diagram whose sites are the feature voxels with each row of the image. This construction is performed efficiently by using the DT in the next lower dimension. The correctness and linear time complexity are demonstrated analytically and verified experimentally. The algorithm may be of practical value since it is relatively simple and easy to implement and it is relatively fast (not only does it run in O(N) time but the time constant is small). A simple modification of the algorithm computes the weighted Euclidean DT, which is useful for images with anisotropic voxel dimensions. A parallel version of the algorithm runs in O(N/p) time with p processors.Keywords
This publication has 46 references indexed in Scilit:
- Distance transformations in digital imagesPublished by Elsevier ,2006
- Image Registration Using Chamfer MatchingPublished by Elsevier ,2000
- Fast ray-tracing of rectilinear volume data using distance transformsIEEE Transactions on Visualization and Computer Graphics, 2000
- Fast Euclidean Distance Transformation by Propagation Using Multiple NeighborhoodsComputer Vision and Image Understanding, 1999
- Fast and exact signed Euclidean distance transformation with linear complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999
- Linear time Euclidean distance transform algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1995
- New algorithms for euclidean distance transformation of an n-dimensional digitized picture with applicationsPattern Recognition, 1994
- Voronoi diagrams—a survey of a fundamental geometric data structureACM Computing Surveys, 1991
- Finding local maxima in a pseudo-Euclidian distance transformComputer Vision, Graphics, and Image Processing, 1988
- Euclidean distance mappingComputer Graphics and Image Processing, 1980