Efficient parallel algorithms for Euclidean distance transform

Ling Chen; Yi Pan; Yixin Chen; Xiao Hua Xu

doi:10.1093/comjnl/47.6.694

Efficient parallel algorithms for Euclidean distance transform

Ling Chen
, Yi Pan
, Yixin Chen
, Xiao Hua Xu

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

The Euclidean distance transform (EDT) converts a binary image into one where each pixel has a value equal to its distance to the nearest foreground pixel. Two parallel algorithms for EDT on linear array with reconfigurable pipeline bus system (LARPBS) are presented. For an image with n × n pixels, the first algorithm can complete EDT in O [(log n log log n)/(log log log n)] time using n² processors. The second algorithm can compute the EDT in O (log n log log n) time using n²/(log log n) processors.

Original language	English
Pages (from-to)	694-700
Number of pages	7
Journal	Computer Journal
Volume	47
Issue number	6
DOIs	https://doi.org/10.1093/comjnl/47.6.694
State	Published - 2004

Access to Document

10.1093/comjnl/47.6.694

Cite this

@article{6a9335625977439a93d986fbe74a0fb5,

title = "Efficient parallel algorithms for Euclidean distance transform",

abstract = "The Euclidean distance transform (EDT) converts a binary image into one where each pixel has a value equal to its distance to the nearest foreground pixel. Two parallel algorithms for EDT on linear array with reconfigurable pipeline bus system (LARPBS) are presented. For an image with n × n pixels, the first algorithm can complete EDT in O [(log n log log n)/(log log log n)] time using n2 processors. The second algorithm can compute the EDT in O (log n log log n) time using n2/(log log n) processors.",

author = "Ling Chen and Yi Pan and Yixin Chen and Xu, \{Xiao Hua\}",

year = "2004",

doi = "10.1093/comjnl/47.6.694",

language = "English",

volume = "47",

pages = "694--700",

journal = "Computer Journal",

issn = "0010-4620",

number = "6",

}

TY - JOUR

T1 - Efficient parallel algorithms for Euclidean distance transform

AU - Chen, Ling

AU - Pan, Yi

AU - Chen, Yixin

AU - Xu, Xiao Hua

PY - 2004

Y1 - 2004

N2 - The Euclidean distance transform (EDT) converts a binary image into one where each pixel has a value equal to its distance to the nearest foreground pixel. Two parallel algorithms for EDT on linear array with reconfigurable pipeline bus system (LARPBS) are presented. For an image with n × n pixels, the first algorithm can complete EDT in O [(log n log log n)/(log log log n)] time using n2 processors. The second algorithm can compute the EDT in O (log n log log n) time using n2/(log log n) processors.

AB - The Euclidean distance transform (EDT) converts a binary image into one where each pixel has a value equal to its distance to the nearest foreground pixel. Two parallel algorithms for EDT on linear array with reconfigurable pipeline bus system (LARPBS) are presented. For an image with n × n pixels, the first algorithm can complete EDT in O [(log n log log n)/(log log log n)] time using n2 processors. The second algorithm can compute the EDT in O (log n log log n) time using n2/(log log n) processors.

UR - https://www.scopus.com/pages/publications/8644254385

U2 - 10.1093/comjnl/47.6.694

DO - 10.1093/comjnl/47.6.694

M3 - Article

AN - SCOPUS:8644254385

SN - 0010-4620

VL - 47

SP - 694

EP - 700

JO - Computer Journal

JF - Computer Journal

IS - 6

ER -

Efficient parallel algorithms for Euclidean distance transform

Abstract

Access to Document

Other files and links

Fingerprint

Cite this