The Stepping Distance Transformation

An algorithm Mscan is proposed for the computation of the distance transform of a feature in an image with respect to a chamfer distance. The algorithm is naively simple and can therefore be easily parallellized. It seems to be new, even for special cases. It is not correct for arbitrary chamfer distances but, by a general analysis of masks and their weights, sufficient conditions for its correctness are obtained. If the image is rectangular with edges parallel to the coordinate axes, all chamfer distances used to approximate the Euclidean distance satisfy these conditions. Keywords: distance transform, chamfer distance, parallel algorithm 1 Introduction For more than thirty years, distance transforms of binary images have played a basic role in computational geometry, with applications in many areas including image processing, graphics and pattern recognition, e.g., cf. [RoP66, RoP68, Pag92]. Since the exact Euclidean distance transform is not always relevant, and is often regarded a..