Euclidean ordering via chamfer distance calculations

This paper studies the mapping between continuous and discrete distances. The continuous distance considered is the widely used Euclidean distance, whereas 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 presented. Optimal chamfer distance coefficients are characterized with respect to the topological ordering they induce, rather than the approximation of Euclidean distance values. We conclude the theoretical part by presenting a global upper bound for a topologically correct distance mapping, irrespective of the chamfer distance coefficients, and we identify the smallest coefficients associated with this bound. We illustrate the practical significance of these results by presenting a framework for the solution of a well-known problem, namely the Euclidean nearest-neighbor problem. This problem is formulated as a discrete optimization problem and solved accordingly using algorithmic graph theory and integer arithmetic. (C) 1999 Academic Press.