Parallel Computation of Watershed Transform in Weighted Graphs on Shared Memory Machines

International audienceWatershed Transform is a widely used image segmentation technique that is known to be very data-intensive and time-consuming. The M-border Kernel Algorithm computes watersheds in the framework of Edge Weighted Graphs and allows to preserve the topology of the initial map. Par-allelization represents an effective solution to accelerate it. However, this task remains challenging due to the nature of this technique. In this paper, we address this problem. We start by analyzing the Data Dependency Issues that this algorithm raises when dealing with parallel execution. With respect to that, we propose a parallelization strategy that opts for vertices scanning instead of edges scanning of the graph while preserving the thinning paradigm on which the M-border Kernel Algorithm is based. We show that this strategy overcomes the problem of the simultaneous lowering of two adjacent M-border edges that may occur when edges scan is used. The implementation of the proposed algorithm on a shared memory multicore architecture proves its effectiveness in terms of speedup. In fact, the experimental results show that a 2 Yosra Braham et al. speedup factor of 5.55 is achieved using 8 processors for 2048 × 2048 images over the performance of the sequential algorithm using a single processor on the same architecture. Furthermore, the gain in terms of execution time and thus speedup is guaranteed whatever is the size of images on which the algorithm is applied. In fact, a speedup factor of 5.55 is obtained for 2048 × 2048 images, 5.11 for 1024 × 1024 images and 4.45 for 512 × 512 images using 8 cores