arrow
返回

A Work Efficient Parallel Algorithm for Exact Euclidean Distance Transform

delete2019-11-01
delete13
delete
OA
AI
M
Manduhu Manduhu *
M
Mark W. Jones
DOI:10.1109/TIP.2019.2916741delete
delete原文链接
delete分享
delete收藏
查看原文
摘要

摘要

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总结

AI总结

对已上传原文的论文进行重点信息的提取,主要内容包括:简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

IEEE Transactions on Image Processing 封面图
IEEE Transactions on Image Processing
IF:
13.7
论文数:
1.1W
被引数:
10.8W

机构

S
Swansea University
学者数:
319
论文数: 191
被引数: 6.5K
引用论文

引用论文

Marek’s disease virus in vaccinated poultry flocks in Turkey: its first isolation with molecular characterization
err2021-01-06
err0
PREAI
errEmre Ozan; Bahadir Muftuoglu; Ismail Sahindokuyucu; Hanne Nur Kurucay; Sinem Inal; Nilufer Kuruca; Ahmed Eisa Elhag; Efe Karaca; Cuneyt Tamer; Semra Gumusova; Harun Albayrak; Gerald Barry; Mustafa Yavuz Gulbahar; Zafer Yazici
err分享
err收藏
2D Euclidean distance transform algorithms: A comparative survey二维欧几里得距离变换算法的比较研究
err2008-02-22
err389
PREAI
errFabbri, Ricardo; Costa, Luciano Da F.; Torelli, Julio C.; Bruno, Odemir M.
err分享
err收藏
Rodents and Risk in the Mekong Delta of Vietnam: Seroprevalence of Selected Zoonotic Viruses in Rodents and Humans
err2015-01-01
err0
errOAAI
errNguyen Van Cuong; Juan Carrique-Mas; Hien Vo Be; Nguyen Ngoc An; Ngo Tri Tue; Nguyet Lam Anh; Pham Hong Anh; Nguyen The Phuc; Stephen Baker; Liina Voutilainen; Anne Jääskeläinen; Eili Huhtamo; Mira Utriainen; Tarja Sironen; Antti Vaheri; Heikki Henttonen; Olli Vapalahti; Yannick Chaval; Serge Morand; Juliet E. Bryant
err分享
err收藏
Dashboard Design Patterns
err2022-01-01
err0
errOAAI
errBenjamin Bach; Euan Freeman; Alfie Abdul-Rahman; Cagatay Turkay; Saiful Khan; Yulei Fan; Min Chen
err分享
err收藏
Retraction: The “Other Face” of Research Collaboration?
err2020-03-25
err0
PREAI
errLi Tang; Guangyuan Hu; Yang Sui; Yuhan Yang; Cong Cao
err分享
err收藏
学者 查看更多内容