Enhancing distance transform computation by leveraging the discrete nature of images.

This paper presents a major reformulation of a widely used solution for computing the exact Euclidean distance transform of n-dimensional discrete binary shapes. Initially proposed by Hirata, the original algorithm is linear in time, separable, and easy to implement. Furthermore, it accounts for the fastest existing solutions, leading to its widespread use in the state of the art, especially in real-time applications. In particular, we focus on the second step of this algorithm, where the lower envelope of a set of parabolas has to be computed. By leveraging the discrete nature of images, we show that some of those parabolas can be merged into line segments. It reduces the computational cost of the algorithm by about 20% in most practical cases, while maintaining its exactness. To evaluate the proposed improvement on different cases, two state-of-the art benchmarks are implemented and discussed. [ABSTRACT FROM AUTHOR]