Euclidean ordering via chamfer distance calculations

This paper studies the mapping between continuous and discrete distances. T he continuous distance considered is the widely used Euclidean distance, wh ereas we consider as the discrete distance the chamfer distance based on 3 x 3 masks. A theoretical characterization of topological errors which arise during the approximation of Euclidean distances by discrete ones is presen ted. Optimal chamfer distance coefficients are characterized with respect t o the topological ordering they induce, rather than the approximation of Eu clidean distance values. We conclude the theoretical part by presenting a g lobal upper bound for a topologically correct distance mapping, irrespectiv e of the chamfer distance coefficients, and we identify the smallest coeffi cients associated with this bound. We illustrate the practical significance of these results by presenting a framework for the solution of a well-know n problem, namely the Euclidean nearest-neighbor problem. This problem is f ormulated as a discrete optimization problem and solved accordingly using a lgorithmic graph theory and integer arithmetic. (C) 1999 Academic Press.