Efficient Euclidean distance transform algorithm of binary images in arbitrary dimensions

Jun Wang, Ying Tan

Результат исследований: Вклад в журналСтатьярецензирование

24 Цитирования (Scopus)


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.

Язык оригиналаАнглийский
Страницы (с-по)230-242
Число страниц13
ЖурналPattern Recognition
Номер выпуска1
СостояниеОпубликовано - янв. 2013
Опубликовано для внешнего пользованияДа


Подробные сведения о темах исследования «Efficient Euclidean distance transform algorithm of binary images in arbitrary dimensions». Вместе они формируют уникальный семантический отпечаток (fingerprint).