Parallel implementation of a watershed algorithm on shared memory multicore architecture

摘要

Watershed transform is widely used in image segmentation. In literature, this transform is computed by various algorithms among which the M-border kernel algorithm [1]. This algorithm computes the watershed transform in the framework of edge weighted graphs. It is based on a local property that makes it adapted to parallelization. In this paper we propose a parallel implementation of this algorithm. We start by studying the data dependencies problematic that it raises. We give then an approach that allows overcoming this problematic based on an alternated edges processing strategy. The implementation of this strategy on a shared memory multicore architecture using a Single Program Multiple Data (SPMD) approach proves its effectiveness. In fact, experimental results show that our implementation achieves a relative speedup factor of 2.8 using 4 processors over the performance of the sequential algorithm using a single processor on the same system.