Euclidean distance transformation by propagation

In this chapter, we explore a first approach to the improvement of exact Euclidean distance transformation algorithms: improving the EDT by propagation. In order to keep the computational cost low, one has to order the propagation according to the metric order. This potentially produces errors in the resulting EDT. The properties of those errors are analyzed, in particular their dependence on the size of the neighborhood used during the propagation. Thanks to these properties, we show how an exact EDT can be produced by using neighborhoods of increasing size, applied on restricted sets of pixels. The computational cost and complexity of the algorithm is then evaluated. It shows a significant improvement over the methods proposed by Saito and Eggers. In order to illustrate potential applications, we show that it can be used to implement mathematical morphology operators on binary images.