The parallel watershed transformation used in gray scale image segmentation is reconsidered on the basis of the component labeling problem. The main idea is to break the sequentiality of the watershed transformation and to correctly delimit the extent of all connected components locally, on each processor, simultaneously. The internal fragmentation of the catchment basins, due to domain decomposition, into smaller subcomponents is finally solved by employing a global connected components operator. Therefore, in a pyramidal structure of master-slave processors, internal contours of adjacent subcomponents within the same component are hierarchically removed. Global final connected areas are efficiently obtained in log/sub 2/ N steps on a logical grid of N processors. Timings and segmentation results of the algorithm built on top of the message passing interface and tested on the Gray T3D are brought forward to justify the superiority of the novel design solution compared against previous implementations.

The parallel watershed transformation used in grayscale image segmentation is reconsidered on the basis of markers. The goal is to reduce the typical over segmentation by decreasing the number of catchment basins produced by flooding. Assimilating the set of basins with a weighted neighborhood graph and computing the minimum spanning forest in which every tree is rooted at a marked vertex, all non-marked regions in each tree are incorporated in the root region of the tree. A log/sub 2/N distributed message passing algorithm performing the above stated goal on N processors is presented. Two merits of the parallel algorithm are worth of mentioning: first, the local detection of the catchment basins conforming to the watershed principle (which strongly depends on the history of the region growth), with an extremely low communication traffic; and second, the parallel computation of the Boruvka like minimum spanning forest with the constraint that any tree contains exactly one marker. Evaluation of a Cray T3D implementation under the message passing interface (MPI) is included.

An important aspect of designing a parallel algorithm is exploitation of the data locality for minimization of the communication overhead. We propose a reformulation of a global image operation called the watershed transformation. The method is one of the various approaches for image segmentation and works by labeling connected components. Both serial and parallel programming models are presented and evaluated when running on SUN and DEC Alpha AXP workstations, and a Cray T3D, respectively.