OPTIMUM DESIGN OF CHAMFER DISTANCE TRANSFORMS

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.