An Alternative Algorithm for Computing Watersheds on Shared Memory Parallel Computers

In this paper a parallel implementation of a watershed algorithm is proposed. The algorithm can easily be implemented on shared memory parallel computers. The watershed transform is generally considered to be inherently sequential since the discrete watershed of an image is defined using recursion. However, recently a few research groups, have designed parallel algorithms for computing watersheds. Most of these parallel algorithms are based on splitting the source image in blocks, computing the watershed 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. In this paper we show that it is possible to transform the computation of the discrete watershed into a sequence of three simple steps which are easier to execute in parallel than the original algorithm. In the first step the input image is transformed into a graph representation of the image. In the second step we compute the watershed of this graph and finally we transform the resulting graph back into the image domain.