Efficient 2D and 3D watershed on graphics processing unit: block-asynchronous approaches based on cellular automata

• We present a cellular automata based watershed that exploits the GPU architecture.
• We propose a block-asynchronous strategy that maps the cellular automata on the GPU.
• The artifacts produced by the asynchronous updating scheme are corrected.
• The block-asynchronous method is tuned to be applied to 2D and 3D images.
• The block-asynchronous strategy is also adequate for multicore architectures.

The watershed transform is a method for non-supervised image segmentation. In this paper we show that a watershed algorithm based on a cellular automaton is a good choice for the recent GPU architectures, especially when the synchronization rules are relaxed. In particular, we propose a block-asynchronous computation strategy that maps the cellular automaton on the thread blocks of the GPU. This method reduces the number of points of global synchronization allowing efficient exploitation of the memory hierarchy of the GPU. We also avoid the artifacts produced in the watershed lines by the block-asynchronous updating scheme by correcting the data propagation speed among the blocks. The proposals are compared to an OpenMP multithreaded code. The high speedups indicate the potential of this kind of algorithm for new architectures based on hundreds of cores. The method is tuned to be applied to 3D volumes obtaining similar results.

Figure optionsDownload as PowerPoint slide