No Cover Image

Journal article 59 views 12 downloads

A work efficient parallel algorithm for exact Euclidean Distance Transform / Manduhu; Mark W. Jones

IEEE Transactions on Image Processing, Pages: 1 - 1

Swansea University Author: Jones, Mark

  • 2019_ParallelEDT.pdf

    PDF | Accepted Manuscript

    Download (2.96MB)
  • Author's Original under embargo until: 19th April 2020

Abstract

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 and other algorithms, this algorithm is suitable for implementation on modern SIMD architectures such as GPUs. As...

Full description

Published in: IEEE Transactions on Image Processing
ISSN: 1057-7149 1941-0042
Published: 2019
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa50104
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: 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 and other algorithms, this algorithm is suitable for implementation on modern SIMD architectures such as GPUs. As a fundamental operation of 2D EDT, 1D EDT is efficiently parallelized first. Specifically, the GPU algorithm for the 1D EDT, which uses CUDA binary functions such as ballot(), ffs(), clz() and shfl(), runs in O(log_32n) 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_32n) 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_32n) time and performs O(N) of total work on GPU. As far as we know, this algorithm is the first fully-parallelized and realized work-time optimal algorithm for GPUs. Experimental results show that this algorithm outperforms prior state-of-the-art GPU algorithms.
College: College of Science
Start Page: 1
End Page: 1