An efficient uniform cost algorithm applied to distance transforms

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

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on pattern analysis and machine intelligence 1989-04, Vol.11 (4), p.425-429
Main Authors: Verwer, B.J.H., Verbeek, P.W., Dekker, S.T.
Format: Article
Language:English
Subjects:
Applied sciences
Artificial intelligence
Assembly
Computer science
control theory
systems
Cost function
Exact sciences and technology
Game theory
Heuristic algorithms
Pattern recognition
Pattern recognition. Digital image processing. Computational geometry
Physics
Pixel
Problem-solving
Sorting
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.< >
ISSN:0162-8828
1939-3539
DOI:10.1109/34.19041