Parallel Algorithms for Higher-Dimensional Euclidean Distance Transforms with Applications

Yuh-Rau WANG; Shi-Jinn HORNG; Yu-Hua LEE; Pei-Zong LEE

Parallel Algorithms for Higher-Dimensional Euclidean Distance Transforms with Applications

Yuh-Rau WANG, Shi-Jinn HORNG, Yu-Hua LEE, Pei-Zong LEE

Full Text Views

0

Cite this

Summary :

Based on the dimensionality reduction technique and the solution for proximate points problem, we achieve the optimality of the three-dimensional Euclidean distance transform (3D_EDT) computation. For an N N N binary image, our algorithms for both 3D_EDT and its applications can be performed in O (log log N) time using CRCW processors or in O (log N) time using EREW processors. To the best of our knowledge, all results described above are the best known. As for the n-dimensional Euclidean distance transform (nD_EDT) and its applications of a binary image of size Nⁿ, all of them can be computed in O (nlog log N) time using CRCW processors or in O (nlog N) time using EREW processors.

Publication: IEICE TRANSACTIONS on Information Vol.E86-D No.9 pp.1586-1593

Publication Date: 2003/09/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section INVITED PAPER (Special Issue on Parallel and Distributed Computing, Applications and Technologies)

Category: Algorithms and Applications

Cite this

Copy

Yuh-Rau WANG, Shi-Jinn HORNG, Yu-Hua LEE, Pei-Zong LEE, "Parallel Algorithms for Higher-Dimensional Euclidean Distance Transforms with Applications" in IEICE TRANSACTIONS on Information, vol. E86-D, no. 9, pp. 1586-1593, September 2003, doi: .
Abstract: Based on the dimensionality reduction technique and the solution for proximate points problem, we achieve the optimality of the three-dimensional Euclidean distance transform (3D_EDT) computation. For an N N N binary image, our algorithms for both 3D_EDT and its applications can be performed in O (log log N) time using CRCW processors or in O (log N) time using EREW processors. To the best of our knowledge, all results described above are the best known. As for the n-dimensional Euclidean distance transform (nD_EDT) and its applications of a binary image of size Nⁿ, all of them can be computed in O (nlog log N) time using CRCW processors or in O (nlog N) time using EREW processors.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_9_1586/_p

Copy

@ARTICLE{e86-d_9_1586,
author={Yuh-Rau WANG, Shi-Jinn HORNG, Yu-Hua LEE, Pei-Zong LEE, },
journal={IEICE TRANSACTIONS on Information},
title={Parallel Algorithms for Higher-Dimensional Euclidean Distance Transforms with Applications},
year={2003},
volume={E86-D},
number={9},
pages={1586-1593},
abstract={Based on the dimensionality reduction technique and the solution for proximate points problem, we achieve the optimality of the three-dimensional Euclidean distance transform (3D_EDT) computation. For an N N N binary image, our algorithms for both 3D_EDT and its applications can be performed in O (log log N) time using CRCW processors or in O (log N) time using EREW processors. To the best of our knowledge, all results described above are the best known. As for the n-dimensional Euclidean distance transform (nD_EDT) and its applications of a binary image of size Nⁿ, all of them can be computed in O (nlog log N) time using CRCW processors or in O (nlog N) time using EREW processors.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - Parallel Algorithms for Higher-Dimensional Euclidean Distance Transforms with Applications
T2 - IEICE TRANSACTIONS on Information
SP - 1586
EP - 1593
AU - Yuh-Rau WANG
AU - Shi-Jinn HORNG
AU - Yu-Hua LEE
AU - Pei-Zong LEE
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2003
AB - Based on the dimensionality reduction technique and the solution for proximate points problem, we achieve the optimality of the three-dimensional Euclidean distance transform (3D_EDT) computation. For an N N N binary image, our algorithms for both 3D_EDT and its applications can be performed in O (log log N) time using CRCW processors or in O (log N) time using EREW processors. To the best of our knowledge, all results described above are the best known. As for the n-dimensional Euclidean distance transform (nD_EDT) and its applications of a binary image of size Nⁿ, all of them can be computed in O (nlog log N) time using CRCW processors or in O (nlog N) time using EREW processors.
ER -