Efficient Euclidean distance transform algorithm of binary images in arbitrary dimensions

In this paper, we propose an efficient algorithm, i.e., PBEDT, for short, to compute the exact Euclidean distance transform (EDT) of a binary image in arbitrary dimensions. The PBEDT is based on independent scan and implemented in a recursive way, i.e., the EDT of a d  -dimensional image is able to be computed from the EDTs of its (d−1)-dimensional(d−1)-dimensional sub-images. In each recursion, all of the rows in the current dimensional direction are processed one by one. The points in the current processing row and their closest feature points in (d−1)-dimensional(d−1)-dimensional sub-images can be shown in a Euclidean plane. By using the geometric properties of the perpendicular bisector, the closest feature points of (d−1)-dimensional(d−1)-dimensional sub-images are easily verified so as to lead to the EDT of a d-dimensional image after eliminating the invalid points. The time complexity of the PBEDT algorithm is linear in the amount of both image points and dimensions with a small coefficient. Compared with the state-of-the-art EDT algorithms, the PBEDT algorithm is much faster and more stable in most cases.

► We propose an algorithm to compute the EDT of binary image in arbitrary dimensions.
► A thoroughly theoretical treatment by means of independent scan is provided.
► By using the perpendicular bisector, the EDT of each dimension is computed.
► The time complexity of this algorithm is linear with the image size and dimensions.
► This algorithm is faster than state-of-the-art algorithms tested by various contents.