Computation of watersheds based on parallel graph algorithms

OnderzoeksoutputAcademicpeer review

277 Downloads (Pure)

Samenvatting

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.

Originele taal-2English
TitelMATHEMATICAL MORPHOLOGY AND ITS APPLICATIONS TO IMAGE AND SIGNAL PROCESSING
RedacteurenP Maragos, RW Schafer, MA Butt
Plaats van productieDORDRECHT
UitgeverijUniversity of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science
Pagina's305-312
Aantal pagina's9
ISBN van geprinte versie0-7923-9733-9
StatusPublished - 1996
Evenement3rd International Symposium on Mathematical Morphology and Its Applications to Image and Signal Processing (ISMM 96) - , Gabon
Duur: 1-mei-1996 → …

Publicatie series

NaamCOMPUTATIONAL IMAGING AND VISION
UitgeverijKLUWER ACADEMIC PUBL

Other

Other3rd International Symposium on Mathematical Morphology and Its Applications to Image and Signal Processing (ISMM 96)
Land/RegioGabon
Periode01/05/1996 → …

Citeer dit