Computation of Watersheds Based on Parallel Graph Algorithms
A. Meijster and J.B.T.M. Roerdink. Computation of Watersheds Based on Parallel Graph Algorithms. In: Mathematical Morphology and its Applications to Image and Signal Processing, P. Maragos, R.W. Shafer, M.A. Butt (eds.), Kluwer, 1996, pp. 305-312.
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 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.
Download in gzipped postscript format© Kluwer. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the publisher.
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.