TY - JOUR

T1 - Efficient Euclidean distance transform algorithm of binary images in arbitrary dimensions

AU - Wang, Jun

AU - Tan, Ying

N1 - Funding Information:
This work was supported by the National Natural Science Foundation of China under grants No. 61170057 and 60875080 . This work is also in part supported by the National High Technology Research and Development Program of China (863 Program), with grant number 2007AA01Z453 .

PY - 2013/1

Y1 - 2013/1

N2 - 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 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 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 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.

AB - 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 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 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 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.

KW - Arbitrary dimensions

KW - Binary image

KW - Euclidean distance transform

KW - Independent scan

KW - Linear time algorithm

UR - http://www.scopus.com/inward/record.url?scp=84866013218&partnerID=8YFLogxK

U2 - 10.1016/j.patcog.2012.07.030

DO - 10.1016/j.patcog.2012.07.030

M3 - Article

AN - SCOPUS:84866013218

VL - 46

SP - 230

EP - 242

JO - Pattern Recognition

JF - Pattern Recognition

SN - 0031-3203

IS - 1

ER -