返回
A Work Efficient Parallel Algorithm for Exact Euclidean Distance Transform
DOI:10.1109/TIP.2019.2916741.png)
摘要
En 中文
A fully-parallelized work-time optimal algorithm is presented for computing the exact Euclidean Distance Transform (EDT) of a 2D binary image with the size of n x n. Unlike existing PRAM (Parallel Random Access Machine) and other algorithms, this algorithm is suitable for implementation on modern SIMD (Single Instruction Multiple Data) architectures such as CPUs. As a fundamental operation of 2D EDT, ID EDT is efficiently parallelized first. Specifically, the GPU algorithm for the ID EDT, which uses CUDA (Compute Unified Device Architecture) binary functions, such as ballot(), ffs(), dz(), and shfl(), runs in O(log(32)n) time and performs O(n) work. Using the 1D EDT as a fundamental operation, the fully-parallelized work-time optimal 2D EDT algorithm is designed. This algorithm consists of three steps. Step 1 of the algorithm runs in O(log(32)n) time and performs O(N) (N=n(2)) of total work on GPU. Step 2 performs O(N) of total work and has an expected time complexity of O(logn) on GPU. Step 3 runs in O(log(32)n) time and performs O(N) of total work on CPU. As far as we know, this algorithm is the first fully-parallelized and realized work-time optimal algorithm for CPUs. The experimental results show that this algorithm outperforms the prior state-of-the-art CPU algorithms.
Keyword:
Work-time optimal parallel algorithm
SIMD architecture
1D EDT
2D EDT
binary operations on GPU
AI总结
对已上传原文的论文进行重点信息的提取,主要内容包括:简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
13.7
论文数:
1.1W
被引数:
10.8W

