The Watershed Transform: Definitions, Algorithms and Parallelization Strategies Jos B.T.M. Roerdink and Arnold Meijster Institute for Mathematics and Computing Science University of Groningen P.O. Box 800, 9700 AV Groningen, The Netherlands Email: roe@cs.rug.nl, a.meijster@rc.rug.nl Abstract. The watershed transform is the method of choice for image segmentation in the field of mathematical morphology. We present a critical review of several definitions of the watershed transform and the associated sequential algorithms, and discuss various issues which often cause confusion in the literature. The need to distinguish between definition, algorithm specification and algorithm implementation is pointed out. Various examples are given which illustrate differences between watershed transforms based on different definitions and/or implementations. The second part of the paper surveys approaches for parallel implementation of sequential watershed algorithms. Keywords: Mathematical morphology, watershed transform, watershed definition, sequential algorithms, parallel implementation. ### 1. Introduction In grey scale mathematical morphology the watershed transform, originally proposed by Digabel and Lantuéjoul $ [9,20] $ and later improved by Beucher and Lantuéjoul $ [4] $ , is the method of choice for image segmentation $ [5,46,52] $ . Generally spoken, image segmentation is the process of isolating objects in the image from the background, i.e., partitioning the image into disjoint regions, such that each region is homogeneous with respect to some property, such as grey value or texture $ [18] $ . The watershed transform can be classified as a region-based segmentation approach. The intuitive idea underlying this method comes from geography: it is that of a landscape or topographic relief which is flooded by water, watersheds being the divide lines of the domains of attraction of rain falling over the region $ [46] $ . An alternative approach is to imagine the landscape being immersed in a lake, with holes pierced in local minima. Basins (also called 'catchment(basins') will fill up with water starting at these local minima, and, at points where water coming from different basins would meet, dams are built. When the water level has reached the highest peak in the landscape, the process is stopped. As a result, the landscape is partitioned into regions or basins separated by dams, called watershed lines or simply watersheds. When simulating this process for image segmentation, two approaches may be used: either one first finds basins, then watersheds by taking a set complement; or one computes a complete partition of the image into basins, and subsequently finds the watersheds by boundary detection. To be more explicit, we will use the expression 'watershed transform' to denote a labelling of the image, such that all points of a given catchment basin have theThe Watershed Transform: Definitions, Algorithms and Parallelization Strategies Jos B.T.M. Roerdink and Arnold Meijster Institute for Mathematics and Computing Science University of Groningen P.O. Box 800, 9700 AV Groningen, The Netherlands Email: roe@cs.rug.nl, a.meijster@rc.rug.nl Abstract. The watershed transform is the method of choice for image segmentation in the field of mathematical morphology. We present a critical review of several definitions of the watershed transform and the associated sequential algorithms, and discuss various issues which often cause confusion in the literature. The need to distinguish between definition, algorithm specification and algorithm implementation is pointed out. Various examples are given which illustrate differences between watershed transforms based on different definitions and/or implementations. The second part of the paper surveys approaches for parallel implementation of sequential watershed algorithms. Keywords: Mathematical morphology, watershed transform, watershed definition, sequential algorithms, parallel implementation. ### 1. Introduction In grey scale mathematical morphology the watershed transform, originally proposed by Digabel and Lantuéjoul $ [9,20] $ and later improved by Beucher and Lantuéjoul $ [4] $ , is the method of choice for image segmentation $ [5,46,52] $ . Generally spoken, image segmentation is the process of isolating objects in the image from the background, i.e., partitioning the image into disjoint regions, such that each region is homogeneous with respect to some property, such as grey value or texture $ [18] $ . The watershed transform can be classified as a region-based segmentation approach. The intuitive idea underlying this method comes from geography: it is that of a landscape or topographic relief which is flooded by water, watersheds being the divide lines of the domains of attraction of rain falling over the region $ [46] $ . An alternative approach is to imagine the landscape being immersed in a lake, with holes pierced in local minima. Basins (also called 'catchment(basins') will fill up with water starting at these local minima, and, at points where water coming from different basins would meet, dams are built. When the water level has reached the highest peak in the landscape, the process is stopped. As a result, the landscape is partitioned into regions or basins separated by dams, called watershed lines or simply watersheds. When simulating this process for image segmentation, two approaches may be used: either one first finds basins, then watersheds by taking a set complement; or one computes a complete partition of the image into basins, and subsequently finds the watersheds by boundary detection. To be more explicit, we will use the expression 'watershed transform' to denote a labelling of the image, such that all points of a given catchment basin have the