Computation of watersheds based on parallel graph algorithms

In this paper the implementation of a parallel watershed algorithm is described. The algorithm has been implemented on a Cray J932, which is a shared memory architecture with 32 processors. The watershed transform has generally been considered to be inherently sequential, but recently a few research groups, see [5, 9, 10], have designed parallel algorithms for computing watersheds. Most of these parallel algorithms are based on splitting the source image in blocks, computing the watersheds of these blocks and merging the resulting images into the desired result. A disadvantage of this approach is that a lot of communication is necessary at the boundaries of the blocks. It is possible to formulate the computation of the watershed transform as a shortest path searching problem that is commonly found in algorithmic graph theory. In this paper we use a parallel adapted version of Dijkstra's algorithm for computing shortest paths in undirected graphs.