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 discrete distance the chamfer distance based on 3 X 3 masks. A theoretical characterisation of topological errors which arise during the approximation of Euclidean distances by discrete ones is presented. Optimal chamfer distance coefficients are characterised 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 identify the smallest coefficients associated with this bound. We use these results to solve a problem which is a representative of most of problems in image processing, namely the Euclidean-nearest neighbour problem. This problem is formulated as a
discrete optimisation problem and solved accordingly using algorithmic graph theory and integer
arithmetic.