Segmentation by watersheds: definition and parallel implementation

The watershed algorithm is a method for image segmentation widely used in the area of mathematical morphology. In this paper we first address the problem of how to define watersheds. It is pointed out that various existing definitions are not equivalent. In particular we explain the differences between the recursive definition, a modification of this definition necessary to avoid relabelling of watershed pixels, and the definition based on shortest path with respect of certain grey-value distance function. The sequential implementation of both algorithms is discussed. Finally we sketch parallel implementations of the two watershed algorithms on a MIMD ring-architecture, and a Cray J932 shared memory computer, respectively.