Efficient euclidean distance transform using perpendicular bisector segmentation

Jun Wang, Ying Tan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Citations (Scopus)

Abstract

In this paper, we propose an efficient algorithm for computing the Euclidean distance transform of two-dimensional binary image, called PBEDT (Perpendicular Bisector Euclidean Distance Transform). PBEDT is a two-stage independent scan algorithm. In the first stage, PBEDT computes the distance from each point to its closest feature point in the same column using one time column-wise scan. In the second stage, PBEDT computes the distance transform for each point by row with intermediate results of the previous stage. By using the geometric properties of the perpendicular bisector, PBEDT directly computes the segmentation by feature points for each row and each segment corresponding to one feature point. Furthermore, by using integer arithmetic to avoid time consuming float operations, PBEDT still achieves exact results. All these methods reduce the computational complexity significantly. Consequently, an efficient and exact linear time Euclidean distance transform algorithm is implemented. Detailed comparison with state-of-the-art linear time Euclidean distance transform algorithms shows that PBEDT is the fastest on most cases, and also the most stable one with respect to image contents.

Original languageEnglish
Title of host publication2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011
PublisherIEEE Computer Society
Pages1625-1632
Number of pages8
ISBN (Print)9781457703942
DOIs
Publication statusPublished - 2011
Externally publishedYes

Publication series

NameProceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
ISSN (Print)1063-6919

Fingerprint

Dive into the research topics of 'Efficient euclidean distance transform using perpendicular bisector segmentation'. Together they form a unique fingerprint.

Cite this