Watershed is a widely used image segmentation algorithm. A grayscale image is considered as topographic relief, which is flooded from initial basins. However, frequently they are not aware of the options of the algorithm and the peculiarities of its realizations. There are many watershed implementations in software packages and products. Even if these packages are based on the identical algorithm–watershed by flooding, their outcomes, processing speed, and consumed memory, vary greatly.
|Algorithm 1 The marker-controlled watershed by Beucher and Meyer .|
One can see that the algorithm by Beucher and Meyer does not form WL. Frequently, watershed lines are valuable segmentation outputs. Meyer  described the algorithm with WL construction. Pseudocode of this method is presented in Algorithm 2.
|Algorithm 2 The marker-controlled watershed with WL construction by Meyer .|
The variables and steps of the algorithm by Meyer are the following:
M1 Image elements corresponding to markers are flagged as visited ; see line 5 in Algorithm 2.
M2 Image elements having marked neighbors are added to the priority queue and flagged as visited; see lines 6–11.
M3 The element with the highest priority is extracted from the queue; if the priority queue is empty, then the algorithm terminates; see lines 12–13.
M4 If all marked neighbors of the extracted element have the same marker, then the image element is labeled by that marker; if marked neighbors of the extracted element have different markers, then the elements are flagged as WL-belonged with marker wl; see lines 14–23.
M5 Nonflagged as visited neighbors of the extracted element are added to a priority queue (with same or lower priority) and flagged as visited if the extracted element is not WL-belonged; then, go to step M3; see lines 17–20.
Paper  presents source codes of Algorithms 1 and 2 for processing 3D images with 26-connectivity in the Python programming language.
Scholars consider how to operate the above described marked-controlled algorithms with WL  and without WL  construction. Figure 2a shows a binary image containing two overlapping discs. Scholars generated this image by a simple code in Python. Then, scholars create a relief by subtracting a constant from a rectangular area in the center part of the inverted Euclidean distance transform (EDT) result for image containing two overlapping disks (see Figure 2b). The image containing initial markers (red and blue) is generated by placing the red and blue squares in the centers of the discs (Figure 2c); correspondingly, the markers are located in local minima of the relief. Segmentation results obtained by algorithms with (Figure 2e) and without WL (Figure 2d) construction are different. This example refutes the common misconception that differences in outcomes of watershed with and without WL result only from image elements of WL. The example clearly shows that segmentation results can vary.
Figure 2. (a) Two overlapping binary discs; (b) relief; (c) initial markers; (d) segmentation result without watershed lines (WL) construction; (e) segmentation result with WL construction.
Although all flooding-based implementations have estimation of computational complexity as O(N), where N is the number of image elements, its processing speed strongly depends on the used data structures, applied programming language, software optimizations, asymptotic constant, and other parameters . Hendriks  performed research on various priority queues in terms of performance and demonstrated the importance of selecting the appropriate priority queue realization. For digital elevation models (DEM) used in geographic information systems (GIS), Barnes et al.  showed how the choice of different queues affects a performance of flooding-based watershed algorithms.
Over the 30-year history of the watershed, many algorithms have been developed: by topographic distance , via image foresting transform , rain falling ,
toboggan-based , via minimum spanning forest , hierarchical watersheds , etc. Surveys  compare various approaches for a watershed calculation. However, despite the enormous efforts to formulate the various mathematical concepts of watershed, only flooding-based algorithms are implemented in well-known software libraries.
Even if these packages are based on the identical algorithm, their outcomes, processing speed, and consumed memory, vary greatly. Papers  contain comprehensive benchmarking of various marker-controlled watershed implementations in software libraries and products.