Analysis of a Step-Based Watershed Algorithm Using CUDA

Analysis of a Step-Based Watershed Algorithm Using CUDA

Giovani Bernardes Vitor (Universidade Estadual de Campinas, Brazil), André Körbes (Universidade Estadual de Campinas, Brazil), Roberto de Alencar Lotufo (Universidade Estadual de Campinas, Brazil) and Janito Vaqueiro Ferreira (Universidade Estadual de Campinas, Brazil)
Copyright: © 2012 |Pages: 15
DOI: 10.4018/978-1-4666-1574-8.ch018
OnDemand PDF Download:
No Current Special Offers


This paper proposes and develops a parallel algorithm for the watershed transform, with application on graphics hardware. The existing proposals are discussed and its aspects briefly analysed. The algorithm is proposed as a procedure of four steps, where each step performs a task using different approaches inspired by existing techniques. The algorithm is implemented using the CUDA libraries and its performance is measured on the GPU and compared to a sequential algorithm running on the CPU, achieving an average speed of twice the execution time of the sequential approach. This work improves on previous results of hybrid approaches and parallel algorithms with many steps of synchronisation and iterations between CPU and GPU.
Chapter Preview

2. Watershed Transform

Taking different approaches, the watershed transform is defined diversely on the literature, each of which producing a different set of solutions (Vincent & Soille, 1991; Meyer, 1994; Lotufo & Falcão, 2000; Bieniek & Moga, 1998; Cousty et al., 2009). The definitions are based on regional or global elements, such as influence zones and shortest-path forests with max or sum of weights of edges, or on local elements, such as the steepest descent paths, where the neighbour’s information is used to create a path to the corresponding minimum. These definitions are thoroughly revised on the literature (Audigier & Lotufo, 2007; Roerdink & Meijster, 2000; Cousty et al., 2009). In this work the local condition definition is used, henceforth named LC-WT (Local Condition Watershed Transform).

The LC-WT definition was introduced by Bieniek et al. (1997) with the purpose of achieving speedups on the parallel watershed transform, once it mimics the behaviour of a drop of water on a surface, requiring less steps of global processing, and thus requiring less communication and synchronisation. Next, we discuss the algorithms that implement this definition on their sequential and parallel versions.

Complete Chapter List

Search this Book: