Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

One of the main topics in the field of topography are watersheds [90]. Knowing the right watersheds and their corresponding catchment basins is essential in countless applications in areas such as Civil Engineering, Hydrology, Environmental Science, Ecology, Limnology, Urban Planning, Agriculture and so on [2, 52, 66, 86]. For instance, determining areas where a flood risk exists can help experts to make a decision to forbid the urban construction in such areas [35]; studying the movement of water within the hydrological cycle need the use of catchment basins as units [59]; analyzing water quality inside lakes or reservoirs depends on several factors included at catchment basin scale [71]; determining territorial boundaries (e.g., such as in the case of Hudson Bay basin) require the use of watersheds [80], etc.

In the late ’60 and ’70s mathematicians and engineers started to work in the first algorithmic solutions for determining catchment basin’s boundaries and watersheds [38, 43, 72]. Later on, researchers implemented a standardized version which they called the watershed algorithm [22]. The watershed algorithm has proved to be a very useful and powerful tool in many different application fields such as cartography [7, 32, 50, 65, 94], general image segmentation [61, 73, 87, 92, 97], video related issues [17, 19, 34, 95, 98], etc. There are several publications on biological and/or medical applications such as analysis of MRI images [3, 28, 46, 56, 77], cell images [4, 12, 14, 24, 85], ultrasound images [16, 33, 41, 45, 76], mammogram images [13, 23, 40, 79, 89], microscopy images [1, 6, 37, 42], among others.

Although there are a few publications reviewing the state-of-the-art of watershed algorithms [43, 60] and applications [18, 29, 49, 75], they are now outdated. In the last few years there has been an increasing number of publications in journals and conferences (Figs. 1 and 2).

Fig. 1
figure 1

Number of publications per year. Data obtained from Scopus © and CiteseerX © in October 13th, 2015

Full size image
Fig. 2
figure 2

Number of publications by document type

Full size image

Nowadays, most of the research in watershed algorithms are specifically devoted to image segmentation, but there are still some applications to real topographical watersheds, as shown in the world map of Fig. 3.

Fig. 3
figure 3

Publications apply to topographic watersheds by country. The number of publications is color-coded from white to green, where darker green represent a higher number of publications in the given country

Full size image

The rest of this survey is organized as follows. Section 2 introduces the basic common definitions used in the reviewed papers. Section 3 shows the main algorithms and strategies used for watershed determination. Section 4 is devoted to one of the main problems in watershed algorithms: over-segmentation. Section 5 reviews parallel approaches. Finally, Sect. 6 is reserved for conclusions and discussion.

2 Definitions

Each reviewed paper in this work uses different notation and terminology. Thus, we here propose a unified notation that will be used throughout this work in order to be able to study and compare the main algorithms and strategies cited in the bibliography.

Let us first consider a drop of water on a topographic surface. The water streams down, reaches a minimum of height and stops there. The set of all points of the surface, which the drops of water reaching this minimum can come from, can be associated with each minimum. Such a set of points is a catchment basin of the surface. The lines, which separate different catchment basins, are called watersheds or watershed lines.

Definition 1

We consider a topographic surface represented by a grid structure called Digital Elevation Model (DEM), composed of cells, analogous to a digital image (IMG), composed of pixels. Every cell/pixel has a natural number as value representing heights on DEM or intensity on IMG of size \(n\times m\).

$$\begin{aligned} DEM = \{x_{ij}\in \mathbb {R}|i\in \mathbb {N},j\in \mathbb {N},i\in (0,\ldots ,n),j\in (0,\ldots ,m)\}\end{aligned}$$
(1)
$$\begin{aligned} IMG = \{x_{ij}\in \mathbb {N}|i\in \mathbb {N},j\in \mathbb {N},i\in (0,\ldots ,n),j\in (0,\ldots ,m)\} \end{aligned}$$
(2)

For the sake of simplicity, from now on we will use the notation for topographic surface instead of the image’s version in the rest of this manuscript.

Definition 2

Given a cell p defined as its position (i, j) in DEM, we define function I as \(I(p)=x_{ij}\).

Definition 3

The set of neighborhood cells of p in the DEM is called \(N_G(p)\) and collect all cells adjacent (adj) to p.

$$\begin{aligned} N_G(p) = \{p'\in I|adj(p,p')\} \end{aligned}$$
(3)

Definition 4

A path P of length l between two cells p and \(p'\) in DEM is a \((l+1)\)-tuple of adjacent cells \((p_0, p_1, \ldots , p_{l-1}, p_l)\) such that \(p_0=p\), \(p_l=p'\).

Definition 5

Cells belonging to the same connected plateau CP must satisfy the following condition

$$\begin{aligned} \forall p,p'\in CP,\exists P=(p0,p_1,\ldots ,p_l)|p_0=p \wedge p_l=p' \wedge \forall p_i \in P, I(p_i) = I(p) = I(p') \end{aligned}$$
(4)

Definition 6

A minimum area M of DEM is a connected plateau of cells from which it is impossible to reach a cell of lower altitude without having to climb (Fig. 4).

$$\begin{aligned} \begin{array}{l} M=\{p|\forall p' \notin CP(p) \wedge I(p')\le I(p) \rightarrow \forall P=(p0,p_1,\ldots ,p_l)|p_0=p\wedge p_l=p',\\ \exists i\in [1,l]|I(p_i)\ge I(p_0)\} \end{array} \end{aligned}$$
(5)
Fig. 4
figure 4

Connected plateau

Full size image

For a particular altitude h we denote the minimum area as \(M_h\).

Definition 7

\(T_h(I)\) stands for the threshold of I at level h where h is the value taken by I and \(h \in [h_{min},h_{max}]\).

$$\begin{aligned} T_h(I)=\{p|I(p)\le h\} \end{aligned}$$
(6)

Definition 8

The geodesic distance \(d_A(p,p')\) between two cells p and \(p'\) in A is the minimun of the length of the paths which join p and \(p'\) and are totally included in area A (Fig. 5).

$$\begin{aligned} d_A(p,p')=min(\{length(P),P=(p,\ldots ,p') \text { which is totally included in}\,A\}) \end{aligned}$$
(7)
Fig. 5
figure 5

Geodesic distance

Full size image

Definition 9

Let A and B be two sets of cells of a given DEM (Fig. 6), where \(B \subset A\). B is composed by k areas not adjacent: \(B_1, B_2,\ldots , B_k\) (black areas in Fig. 6) but connected through A. The geodesic influence zone \(IZ_A(B_i)\) of a component of B in A is the locus of the cells of A whose geodesic distance to \(B_i\) is smaller than their geodesic distance to any other component of B (blue color in Fig. 6 is the \(IZ_A(B_1)\)).

$$\begin{aligned} IZ_A(B_i)=\{p\in A,\forall j\in [1,k]\wedge j \ne i|d_A(p,B_i)<d_A(p,B_j)\} \end{aligned}$$
(8)
Fig. 6
figure 6

Geodesic influence zone. A small example with \(k=3\)

Full size image

Definition 10

The cells of A which do not belong to any geodesic influence zone constitute the skeleton by influence zones (SKIZ) of B inside A, denoted \(SKIZ_A(B)\)

$$\begin{aligned} SKIZ_A(B)=A \setminus IZ_A(B)\text { with }IZ_A(B)=\bigcup _{i\in [1,k]}{IZ_A(B_i)} \end{aligned}$$
(9)

Definition 11

The set of catchment basins of DEM is equal to the set \(X_{h_{max}}\) composed of not adjacent areas and obtained after the following recursion

$$\begin{aligned} \left\{ \begin{array}{rcl} X_h=T_h(I) &{},&{} h=h_{min}\\ X_{h+1}=M_{h+1}\cup IZ_{T_{h+1}(I)}(X_h) &{},&{} h\in (h_{min},h_{max}-1] \end{array} \right. \end{aligned}$$
(10)

Definition 12

The watersheds are \(X^C_{h_{max}}\), i.e. the complement set of \(X_{h_{max}}\).

3 Algorithms

Naturally, the first algorithms for computing watersheds are found in the field of topography. Lets recall that topographic surfaces are numerically handled through DEMs, these are arrays of numbers that represent the spatial distribution of terrain altitudes [90]. In image segmentation, its main application, the idea of the watershed construction is quite simple: a gray scale image can be considered as a topographic relief, the gray scale value of a pixel being the altitude at that particular point [69]. Using this analogy we can now review all papers regardless of its application.

There are a few reviews devoted to watershed algorithms in the bibliography. The first one appeared in the early 90s, when Beucher and Meyer publish a book chapter introducing what they have called the “watershed transformation” (basically the flooding process explained below) along with the principles of morphological segmentation and morphological tools [9]. This transformation was rapidly adopted by many other researchers for their own particular applications [30, 96].

Later on in 2003, Najman and Couprie study the behavior of watershed algorithms. Through the introduction of the concept of “pass value” they show that most classical watershed algorithms do not allow the retrieval of some important topological features of the image [60]. An important consequence of this result is that it is not possible to compute sound measures such as depth area or volume of basins using most classical watershed algorithms.

Finally and more than 5 years later, Körbes and Lotufo present a communication in a symposium reviewing fifteen watershed algorithms in a comprehensive way [43]. Afterwards several novel algorithms were developed and thus needed an updated review.

But let us first introduce the two main strategies for determining watersheds, we will study each of them separately in the next subsections.

Fig. 7
figure 7

Immersion-based watersheds

Full size image

3.1 By Immersion

The first strategy that we will analyze is called immersion (also called flooding). It was first developed for contour detection in images and introduced by Beucher and Lantuejoul in 1979 [8].

Later, an algorithmic-based definition for the identification of watersheds by immersion was introduced by Vincent and Soille in 1991 [90]. By analogy to the idea of immersion, we can figure that we have pierced holes in each regional minimum of our topographic surface. We then slowly immerse our surface into a lake. Starting from the minima of lowest altitude, the water will progressively fill up the different catchment basins. Now, at each position where the water coming from two different minima would merge, we build a “dam”. At the end of this immersion procedure, each minimum is completely surrounded by dams, which delimit its associated catchment basin. The whole set of dams which has been built provides a division of the surface in its different catchment basins. These dams correspond to the watersheds of our surface [90] (Fig. 7). Vincent and Soille algorithm was developed for image segmentation and involves two major steps: (1) sorting of pixels in increasing order of gray value (the gray value of a pixel being the altitude at a particular point), and (2) fast computation of geodesic influence zones by breadth-first scanning of each threshold level using a first-in-first-out (FIFO) data structure (Algorithm 1).

figure a
figure b

Meijster and Roerdink propose in 1998 [51] an algorithm with two stages: (1) transform a lower complete image using a FIFO-queue algorithm, and (2) calculate the watershed using graph theory and removing the old FIFO-queue (Algorithm 4).

figure c
figure d
figure e

Lotufo and Falcao, in 2000, reviews the watershed in the graph framework of a shortest-path forest problem using a lexicographic path cost formulation. This formulation reflects the behavior of the ordered queue-based watershed algorithm [47].

In 2001, Chen and Shi [15] modify the original Vincent and Soille immersion-based watershed algorithm to correct some issues: (1) incorrect labeling when a point p is at the same distance from three or more adjacent catchment basins (i.e., it will be labeled as catchment basin instead as watershed), (2) unnecessary computation of geodesic distance between points which belong to the labeled, (3) memory consumption, and (4) incapacity to obtain information about catchment basins during the processing. The modified algorithm proposed introduces a third step call “gushing step”, that together with the immersion step, produces a fast recognition of pixels of labeled and gets the flood level of the catchment basin.

Later on, Rambabu et al. first, in 2003, propose a new algorithm based on hill climbing simulation, that avoided multiple scanning of the original matrix by using different queues to store pixels [69]. Then, in 2008, Rambabu and Chakrabarti gives an updated and corrected version of this same algorithm [70].

In 2005, Shen and Chang [74] present a nearest-neighbor graph (NNG) based watershed algorithm. The main idea behind this work is to transform the image into a NNG and then partitioned by discovering the defined geographic features in the first step. The initial population result is also transformed into the NNG again and the recursively distilled by the proposed algorithm.

Fig. 8
figure 8

Rainfall-based watersheds

Full size image

3.2 By Rainfall

The second strategy is called rainfall and has two main steps: (1) the weakest edges are removed by “drowning” the image, creating a number of “lakes” grouping all the pixels that lie below a certain threshold (this is useful to reduce the influence of noise, and reduces the over-segmentation), and (2) the direction of a raindrop from each pixel would flow if it would fall on the topographic activity surface. This steepest descent neighbor and the pixel under consideration are then merged, finally enabling the localization of the remaining edges and segments [21] (Fig. 8).

Mortensen and Barret in 1999 introduces an optimization variation for the rainfall-based watershed algorithm using a tobogganing technique, which makes a much more computationally efficient algorithm [57]. In this version, tobogganing over-segments an image into small regions by sliding in the derivative terrain. The basic idea is that given the gradient magnitude of an image, each pixel determines a slide direction by finding the pixel in a neighborhood with the lowest gradient magnitude. Pixels that “slide” to the same local minimum are grouped together, thus segmenting the image into a collection of small regions.

A year later, Bieniek and Moga [11] propose an efficient algorithm based on connected components that generates the same results as the original Meyer’s algorithm [53] but with a simpler algorithmic construction and, hence, a lower complexity (it can label all catchment basins by only scanning the image four times).

Later on, in 2007, Osma-Ruiz et al. implement a more efficient algorithm by computation of shortest paths [63] (Algorithm 5). This algorithm produces the same result as the previous works using only two scans (plus another to initialize the data structures), thus decreasing the running time obtained in [11, 81].

figure f
figure g
figure h

One of the latest work in the area was developed by Świercz and Iwanowski in 2010 [82]. In their work, a mechanism called directional code is used to code descent paths, where each visited pixel receives a temporary marking in the output label array. The value of this temporary marking represents the position of pixel in the image. A path can be therefore viewed as a series of pointers to pixels stored in the output array.

3.3 Mixed Approaches

In 2005 Sun et al. modifies Bieniek and Moga’s work simulating raining to generate the connected components using chain code instead of pixel address. Afterwards, they simulate flooding to label catchment basins by tracing chain codes [81]. This algorithm not only can label catchment basins by scanning the image only four times, but also is more helpful to the following image processing.

Cousty et al. in 2009 introduces the first work that mathematically prove equivalence to both immersion-based and rainfall-based watersheds [20]. For this purpose, the authors propose a new definition of watershed, called watershed cut and give a liner-time algorithm to compute the watershed cuts of an edge-weighted graph (pre-processed image). The proposed algorithm does not require any sorting step or the use of any sophisticated data structure such as a hierarchical queue or a representation to maintain unions of disjoint sets.

4 Over-Segmentation

Researcher noticed that it was hard to apply watershed transformations since they are very sensitive to noise. One of the main drawbacks of the classical watershed algorithm is a phenomenon known as over-segmentation. There are several approaches to reduce the impact of this issue, which can be categorized into two approaches: pre-processing and post-processing. Several pre-processing and post-processing methods were reviewed by Bieniecki in 2004 applied to color images. Between the studied pre-processing methods, the author analyze noise removal by using a median filter, color morphology and other smoothing filters. Between the post-processing methods, the author research merging basins by gradient watersheds on graphs, basin dynamics, inclusionary and exclusionary cues, image component labeling and multi-scale gradient analysis [10].

4.1 Pre-processing

The most efficient pre-processing techniques are based on markers. In a marker-based algorithm, the gradient image is first modified by a marker image, which is a binary image with the object interiors (markers) being set to 0 and the uncertainty areas being set to 255 (Fig. 9). Each marker indicates the presence of an object [25].

Fig. 9
figure 9

Modification process of the gradient image by the marker image

Full size image

In Moga and Gabbouj watershed transformation is augmented to perform with the aid of a priori supplied image markers. In this method pixels are first clustered based on spatial proximity and gray level homogeneity with the watershed transformation. Boundary-based region merging is the effected to condense non-marked regions into marked catchment basins The agglomeration strategy works with a weighted neighborhood graph representation of the over-segmented image [55].

Some years later Gao et al. propose a marker-based algorithm using a disjoint set data structure with a linear complexity [25]. Later on they present an updated algorithm to extract the regional minima from the low frequency components in the gradient map. The extracted minima constitute the binary marker image. Then the original gradient map is modified by suppressing its all-intrinsic minima around these extracted markers. Thus, compared with traditional approaches, both the spurious minima are more effectively removed and meanwhile the boundaries of objects are more effectively protected [26].

In 2009, Zhu et al. apply a multi-scale alternating sequential filtering by reconstruction to simplify the input image in order to remove local minima which are caused by irregular gray disturbance and noise, and preserve important contour information [99]. After this procedure is done, there still exists some local minima problem which is reduced by a marker-extracted method that uses minima imposition to make a marked image before watershed transformation. Markers are a set of components marking flat regions of an image. The mark extraction can suppress all of is intrinsic minima. Finally, the watershed algorithm is applied to the modified gradients by the markers.

A stochastic version of the watershed algorithm is obtained by choosing randomly in the image the seeds from which the watershed regions are grown. In the 2009’s work Tolosa et al. explore two seed-generation processes to avoid over-segmentation. The first is a non-uniform Poisson process, the density of which is optimized on the basis of the opening granulometry. The second process positions the seed randomly within disks centered on the maxima of a distance map [84].

Procházka et al. proposes in 2010 a smoothing procedure to reduce noise and over-segmentation. This procedure first applies wavelet image de-noising, and afterwards a smoothing phase. The main idea in this phase is to remove image elements smaller than the size of structuring element and to fill gaps between pixels and smoothes their outer edges [68].

Also in 2010, Moumoun et al. introduces a filtering step to eliminate insignificant minima that take into account not only the depth of the pixel but also the change in concavity [58]. This is done by defining a hierarchy between minima using a generic graph. In this graph each region is represented by a node. The minimum curvature of a region is associated with the corresponding node. The arcs express the adjacencies relations between regions and two regions are called adjacent if they have adjacent faces. The weight of each arc is defined by the depth measurement already mentioned.

4.2 Post-processing

Gies and Bernard propose in 2004 a merging phase of basin using statistical information. With regions of an unspecified size, the merging criterion must follow statistical rules accounting for the region size. The authors consider the regions as the outcome of stochastic processes. The merging criterion is based on the knowledge of region area and statistical regional measures, determining the statistical reliability of the merging [27].

Patino publishes in 2005 an approach that characterizes each of the segmented regions and then employs the composition of fuzzy relations to group together similar regions. A fuzzy c-means algorithm along with fuzzy relations can group together similar gray-level values, but only between adjacent regions [64].

Jianhua et al. propose a more complex strategy for basin merging in 2005. Their method pre-segments the image by watersheds and then merges it by Immune Clonal Algorithm (ICA). To implement the task, several operators are proposed such as the DC operator, the Proportional Creation of the First generation operator, and fitness function based on JND and average gray value [36].

Moumoun et al. also propose a post-processing technique based on region merging by the depth of the watershed segmentation. This depth is defined by the difference between the height of the saddle point and the minimum of adjacent regions [58].

4.3 Other Approaches

There are very few approach to reduce over-segmentation that do not use pre-processing or post-processing. Swiercz and Iwanowsky propose in 2011 a “water-ball method designed to counter over-segmentation during the actual calculation of watersheds. This proposal can be perceived as a composite method for object extraction, combining several techniques and mechanisms to produce satisfactory macro-scale results [83]. The “water-ball method uses two distinct mechanisms. The first one consists of a “rolling ball” based on the simulation of a larger object rolling down the slope (contrary to classic rainfall methods where a single drop of water is used). This ball has the ability to cross small ridges and ignore small, insignificant local minima. The second mechanism, weakening with edge enhancement, makes it possible to eliminate low, insignificant interior boundaries.

5 Parallel Approaches

When watershed algorithms are applied in large images or big DEMs, serial versions can take many hours to return the solution. therefore, researchers dedicated their effort to implement parallelized versions, but do to the recursive nature of the watershed transformation, its parallelization is not a trivial task [54] and cannot suit real-time operations in most cases [62].

5.1 Parallelization Using Distributed Memory

Most of the existing papers on parallel watershed algorithms are based on a divide-and-conquer approach [54, 55, 67, 72, 93] with regular domain decomposition into blocks of data. Each block is then processed by a different processor independently, thus using distributed memory. Afterwards all blocks are merged together. In 2010 Šwiercz and Iwanowski [82] present an interesting approach to reduce the merging process by pre-calculating the adjacent sections between the different blocks. Thus, the merging process reduces to a bulk memory copy of each processed block.

5.2 Parallelization Using Shared Memory

There are a few publications that uses a shared memory approach where there is a need of constant synchronization between the processors that process adjacent blocks. In Wagner et al. [91] the authors propose a chromatic ordering that allows to gain a correct segmentation without an examination of adjacent domains or a final relabeling. Later, VanNeerbos et al. [88] parallelize topological watersheds in such a way that border pixels between threads are not calculated at the same time. To do this, each thread process its tile in different stages and synchronizing between all threads is performed after each stage. Also in 2011 Mahmoudi et al. [48] introduce an adapted parallelization strategy called split, distribute and merge strategy which allows efficient parallelization of a large class of topological operators including, mainly, smoothing, skeletonization, and watershed algorithms. To achieve a good speedup they focus on task scheduling.

5.3 Parallelization Using Graphics Processor Units

There is a rising tendency in research in parallelization using Graphics Processor Units (GPUs) and watershed algorithms are not an exception. Kauffmann and Piche [39] describe a cellular automaton (CA) to perform the watershed transform in N-D images. Due to the local nature of CA algorithms they show that they are designed to run on massively parallel processors and therefore, be efficiently implemented on low cost consumer GPUs. A few years later Körbes et al. review the advances in watershed processing on GPU architecture [44] on two algorithms: one inspired by the drop of water paradigm and depth-search approaches; and one based on cellular automata to process a shortest-path forest with sum cost function. In 2012 Hucko and Srámek [31] present the first GPU watershed algorithm able to process data larger than the available memory, as the whole data has to be present in the memory of the device. In their manuscript they present two versions of a streamed multi-pass algorithm for watershed computation on a GPU. As the slice-based streaming approach is used both variants are capable of processing data exceeding the size of the available graphics accelerator memory. Another interesting approach is shown by Quedada-Barriuso et al. [5] where the watershed transform based on a cellular automaton, especially when the synchronization rules are relaxed. In particular, they compare a synchronous and an asynchronous implementation of the algorithm. One of the main applications for watersheds are medical related issues, therefore Smistad et al. recently published a comprehensive survey on medical image segmentation on GPUs [78].

6 Conclusions

Recent advances in watershed algorithms focus on the use of different data structures to improve the efficiency of the proposed algorithms. Most of the work done has been developed for image segmentation purposes, specially on medical and biological images. Also, parallel approaches seem to be an area of constant development. Curiously, many of the most interesting proposals were published in conferences instead of in journals. This tendency seems to change in the latest years of research.

Although there are many different watershed algorithmic solutions, there are still many problems to solve. Thus, there is an increasing amount of publications over the last few years. That is, watershed algorithms are still an open problem and there are more and more new fields starting to use and develop this kind of techniques from different points of view.

Another open issue is the oversegmentation watershed algortihms produce. Although there are several approches to minimize this problem, there is still no perfect solution available yet. Oversegmentation can be an important issue when determining countours on images that will be used for counting purposes (such as blood cells).

Many applications that use watershed algorithms work with a small dataset or datasets. For real-world applications in topography that includes large regions of terrain, watershed algorithms became slow and inefficient. Sometimes they are not capable to work since memory becomes a crucial issue. For this kind of big data processes the only available solution is the partition of the dataset into smaller sets and the posterior merge of each partial solution.

We believe there is still a lot of improvement to be developed in this field. For instance, there is a lack of techniques for real-time and streaming applications. Also, we could not retrieve many studies on real watersheds in many countries, thus indicating that many catchment basins worldwide have not been studied yet.