Approximate distance transformations.

As defined in equation , distance transformations are global transformations. Indeed, a direct application of this definition requires to consider all object pixels in order to compute the value of the DT for any non-object pixel. The computational complexity is proportional to the product of the numbers of pixels in O and O'.

In image processing, one usually tries to consider local transformations, i.e. transformations for which the value of a pixel depends only on the pixels belonging to its neighborhood. The simplest method to localize the definition of eq. is to assume that the DT at a pixel can be deduced from the values at its neighbors. This is strictly true for the city-block, chess-board and chamfer metrics, but not for the Euclidean one. It leads to a class of algorithms that Borgefors [10] called chamfering. Unfortunately, chamfer metrics are only coarse approximations of the Euclidean distance. Chamfer DTs produce systematic errors in the directions not covered by the chamfer masks. This is studied in section .

In order to define a local Euclidean DT algorithm, Danielsson [37] proposes to assume that the nearest object pixel (NOP) is a local property. The NOP of a background pixel is the same as that of one its neighbors. With the Euclidean metric, this assumption is true on a continuous plane, but sometimes incorrect on a discrete grid, with particular object pixels configurations. This leads to a quasi Euclidean DT where non-systematic errors occur on some locations of the image only. This is studied in section .