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.


    Access

    Download


    Export, share and cite



    Title :

    An Alternative Algorithm for Computing Watersheds on Shared Memory Parallel Computers


    Contributors:

    Publication date :

    1995-01-01


    Remarks:

    Meijster , A & Roerdink , J B T M 1995 , An Alternative Algorithm for Computing Watersheds on Shared Memory Parallel Computers . in EPRINTS-BOOK-TITLE . University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science .


    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629 / 006