Please use this identifier to cite or link to this item: https://doi.org/10.1145/1730804.1730818
Title: Parallel Banding Algorithm to compute exact distance transform with the GPU
Authors: Cao, T.-T.
Tang, K.
Mohamed, A.
Tan, T.-S. 
Keywords: Computational geometry
Graphics hardware
Morphological operation
Stipple drawing
Voronoi diagram
Issue Date: 2010
Source: Cao, T.-T.,Tang, K.,Mohamed, A.,Tan, T.-S. (2010). Parallel Banding Algorithm to compute exact distance transform with the GPU. Proceedings of I3D 2010: The 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games : 83-90. ScholarBank@NUS Repository. https://doi.org/10.1145/1730804.1730818
Abstract: We propose a Parallel Banding Algorithm (PBA) on the GPU to compute the exact Euclidean Distance Transform (EDT) for a binary image in 2D and higher dimensions. Partitioning the image into small bands to process and then merging them concurrently, PBA computes the exact EDT with optimal linear total work, high level of parallelism and a good memory access pattern. This work is the first attempt to exploit the enormous power of the GPU in computing the exact EDT, while prior works are only on approximation. Compared to these other algorithms in our experiments, our exact algorithm is still a few times faster in 2D and 3D for most input sizes. We illustrate the use of our algorithm in applications such as computing the Euclidean skeleton using the integer medial axis transform, performing morphological operations of 3D volumetric data, and constructing 2D weighted centroidal Voronoi diagrams. Copyright © 2010 by the Association for Computing Machinery, Inc.
Source Title: Proceedings of I3D 2010: The 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games
URI: http://scholarbank.nus.edu.sg/handle/10635/40089
ISBN: 9781605589381
DOI: 10.1145/1730804.1730818
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

75
checked on Jan 17, 2018

Page view(s)

72
checked on Jan 15, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.