The distance transform has found many applications in image analysis.
Chamfer distance transforms are a class of discrete algorithms that of
fer a good approximation to the desired Euclidean distance transform a
t a lower computational cost. They can also give integer-valued distan
ces that are more suitable for several digital image processing tasks.
The local distances used to compute a chamfer distance transform are
selected to minimize an approximation error. In this paper, a new geom
etric approach is developed to find optimal local distances. This new
approach is easier to visualize than the approaches found in previous
work, and can be easily extended to chamfer metrics that use large nei
ghborhoods. A new concept of critical local distances is presented whi
ch reduces the computational complexity of the chamfer distance transf
orm without increasing the maximum approximation error.