An Alternative Algorithm for Computing Watersheds on Shared Memory Parallel Computers

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

77 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationEPRINTS-BOOK-TITLE
PublisherUniversity of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science
Number of pages9
Publication statusPublished - 1995

Cite this