Computation of watersheds based on parallel graph algorithms

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

274 Downloads (Pure)

Abstract

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.

Original languageEnglish
Title of host publicationMATHEMATICAL MORPHOLOGY AND ITS APPLICATIONS TO IMAGE AND SIGNAL PROCESSING
EditorsP Maragos, RW Schafer, MA Butt
Place of PublicationDORDRECHT
PublisherUniversity of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science
Pages305-312
Number of pages9
ISBN (Print)0-7923-9733-9
Publication statusPublished - 1996
Event3rd International Symposium on Mathematical Morphology and Its Applications to Image and Signal Processing (ISMM 96) - , Gabon
Duration: 1-May-1996 → …

Publication series

NameCOMPUTATIONAL IMAGING AND VISION
PublisherKLUWER ACADEMIC PUBL

Other

Other3rd International Symposium on Mathematical Morphology and Its Applications to Image and Signal Processing (ISMM 96)
Country/TerritoryGabon
Period01/05/1996 → …

Keywords

  • parallelism
  • shared memory
  • shortest path algorithms
  • segmentation
  • watersheds

Cite this