Parallel Banding Algorithm

Parallel Banding Algorithm to Compute Exact Distance Transform with the GPU

Thanh-Tung Cao, Ke Tang, Anis Mohamed, and Tiow-Seng Tan

{ caothanh | tangke | tants } @ comp.nus.edu.sg, mohd.anis @ gmail.com

School of Computing

National University of Singapore


Original Image	Sampled Image	Result by CVD

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.

CR Categories: I.3.1 [Computer Graphics]: Hardware Architecture - Graphics Processors; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling - Geometric algorithms.

Keywords: Digital geometry, Interactive application, Programmable graphics hardware.

Paper in The Proceedings of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D 2010), Maryland, USA, 19--21 February, 2010, pp. 83--90.

Video: click here to download the video clip (58M).

See also: Presentation in i3d , PBA Software Download , CVD Software Download

Dated: 10 Jan 2010, 27 Jan 2010, 4 March 2010