A review of distance transformations

This chapter presents the framework of this thesis in more details. First, we define the main concepts and notations that will be used in this text. Secondly, we review most DT algorithms that were proposed in the literature. Those can be divided according to several criteria such as their accuracy, the order in which they scan the image, their computational complexity, etc. We choose to present them by order of increasing accuracy, from the coarser metrics introduced by Rosenfeld [132] to the exact Euclidean metric achieved by the latest algorithms. Thirdly we present extended DT concepts, such as the geodesic DT where the image domain is non-convex. Fourthly, we review the main applications of distance transformations, within and without the medical image processing framework. Finally, we discuss the main strong and weak points in the various algorithms and analyze which elements can be used to develop improved DT algorithms.