Efficient Euclidean distance transform algorithm of binary images in arbitrary dimensions

Jun Wang, Ying Tan

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)230-242
Number of pages13
JournalPattern Recognition
Volume46
Issue number1
DOIs
Publication statusPublished - Jan 2013
Externally publishedYes

Keywords

  • Arbitrary dimensions
  • Binary image
  • Euclidean distance transform
  • Independent scan
  • Linear time algorithm

Fingerprint

Dive into the research topics of 'Efficient Euclidean distance transform algorithm of binary images in arbitrary dimensions'. Together they form a unique fingerprint.

Cite this