An efficient uniform cost algorithm applied to distance transforms
- 1 April 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 11 (4) , 425-429
- https://doi.org/10.1109/34.19041
Abstract
The uniform-cost algorithm is a special case of the A*-algorithm for finding the shortest paths in graphs. In the uniform-cost algorithm, nodes are expanded in order of increasing cost. An efficient version of this algorithm is developed for integer cost values. Nodes are sorted by storing them at predefined places (bucket sort), keeping the overhead low. The algorithm is applied to general distance transformation. A constrained distance transform is an operation which calculates at each pixel of an image the distance to the nearest pixel of a reference set, distance being defined as minimum path length. The uniform-cost algorithm, in the constrained case, proves to be the best solution for distance transformation. It is fast, the processing time is independent of the complexity of the image, and memory requirements are moderate.Keywords
This publication has 7 references indexed in Scilit:
- Distance transformations in digital imagesPublished by Elsevier ,2006
- Improved metrics in image processing applied to the Hilditch skeletonPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Computing distance transformations in convex and non-convex domainsPattern Recognition, 1987
- Distances defined by neighborhood sequencesPattern Recognition, 1986
- Distance transformations in arbitrary dimensionsComputer Vision, Graphics, and Image Processing, 1984
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968
- Distance functions on digital picturesPattern Recognition, 1968