Hubbry Logo
Watershed (image processing)Watershed (image processing)Main
Open search
Watershed (image processing)
Community hub
Watershed (image processing)
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Watershed (image processing)
Watershed (image processing)
Watershed (image processing)
View on Wikipedia
from Wikipedia

In the study of image processing, a watershed is a transformation defined on a grayscale image. The name refers metaphorically to a geological watershed, or drainage divide, which separates adjacent drainage basins. The watershed transformation treats the image it operates upon like a topographic map, with the brightness of each point representing its height, and finds the lines that run along the tops of ridges.

There are different technical definitions of a watershed. In graphs, watershed lines may be defined on the nodes, on the edges, or hybrid lines on both nodes and edges. Watersheds may also be defined in the continuous domain.[1] There are also many different algorithms to compute watersheds. Watershed algorithms are used in image processing primarily for object segmentation purposes, that is, for separating different objects in an image. This allows for counting the objects or for further analysis of the separated objects.

  • Relief of the gradient magnitude
    Relief of the gradient magnitude
  • Gradient magnitude image
    Gradient magnitude image
  • Watershed of the gradient
    Watershed of the gradient
  • Watershed of the gradient (relief)
    Watershed of the gradient (relief)

Definitions

[edit]

In geology, a watershed is a divide that separates adjacent catchment basins.

Watershed by flooding

[edit]

The idea was introduced in 1979 by S. Beucher and C. Lantuéjoul.[2] The basic idea consisted of placing a water source in each regional minimum in the relief, to flood the entire relief from sources, and build barriers when different water sources meet. The resulting set of barriers constitutes a watershed by flooding. A number of improvements, collectively called Priority-Flood, have since been made to this algorithm.[3]

Watershed by topographic distance

[edit]

Intuitively, a drop of water falling on a topographic relief flows towards the "nearest" minimum. The "nearest" minimum is that minimum which lies at the end of the path of steepest descent. In terms of topography, this occurs if the point lies in the catchment basin of that minimum. The previous definition does not verify this condition.

Watershed by the drop of water principle

[edit]

Intuitively, the watershed is a separation of the regional minima from which a drop of water can flow down towards distinct minima. A formalization of this intuitive idea was provided in [4] for defining a watershed of an edge-weighted graph.

Inter-pixel watershed

[edit]

S. Beucher and F. Meyer introduced an algorithmic inter-pixel implementation of the watershed method,[5] given the following procedure:

  1. Label each minimum with a distinct label. Initialize a set S with the labeled nodes.
  2. Extract from S a node x of minimal altitude F, that is to say F(x) = min{F(y)|y ∈ S}. Attribute the label of x to each non-labeled node y adjacent to x, and insert y in S.
  3. Repeat Step 2 until S is empty.

Topological watershed

[edit]

Previous notions focus on catchment basins, but not to the produced separating line. The topological watershed was introduced by M. Couprie and G. Bertrand in 1997,[6] and beneficiate of the following fundamental property. A function W is a watershed of a function F if and only if W ≤ F and W preserves the contrast between the regional minima of F; where the contrast between two regional minima M1 and M2 is defined as the minimal altitude to which one must climb in order to go from M1 to M2.[7] An efficient algorithm is detailed in the paper.[8]

Watershed algorithm

Different approaches may be employed to use the watershed principle for image segmentation.

  • Local minima of the gradient of the image may be chosen as markers, in this case an over-segmentation is produced and a second step involves region merging.
  • Marker based watershed transformation make use of specific marker positions which have been either explicitly defined by the user or determined automatically with morphological operators or other ways.

Meyer's flooding algorithm

[edit]

One of the most common watershed algorithms was introduced by F. Meyer in the early 1990s, though a number of improvements, collectively called Priority-Flood, have since been made to this algorithm,[9] including variants suitable for datasets consisting of trillions of pixels.[10]

The algorithm works on a gray scale image. During the successive flooding of the grey value relief, watersheds with adjacent catchment basins are constructed. This flooding process is performed on the gradient image, i.e. the basins should emerge along the edges. Normally this will lead to an over-segmentation of the image, especially for noisy image material, e.g. medical CT data. Either the image must be pre-processed or the regions must be merged on the basis of a similarity criterion afterwards.

  1. A set of markers, pixels where the flooding shall start, are chosen. Each is given a different label.
  2. The neighboring pixels of each marked area are inserted into a priority queue with a priority level corresponding to the gradient magnitude of the pixel.
  3. The pixel with the lowest priority level is extracted from the priority queue. If the neighbors of the extracted pixel that have already been labeled all have the same label, then the pixel is labeled with their label. All non-marked neighbors that are not yet in the priority queue are put into the priority queue.
  4. Redo step 3 until the priority queue is empty.

The non-labeled pixels are the watershed lines.

Example of a marker-supported watershed transformation for a population of pharmaceutical pellets. Watershed lines are superimposed in black on the CT image stack.[11]

Optimal spanning forest algorithms (watershed cuts)

[edit]

Watersheds as optimal spanning forest have been introduced by Jean Cousty et al.[12] They establish the consistency of these watersheds: they can be equivalently defined by their “catchment basins” (through a steepest descent property) or by the “dividing lines” separating these catchment basins (through the drop of water principle). Then they prove, through an equivalence theorem, their optimality in terms of minimum spanning forests. Afterward, they introduce a linear-time algorithm to compute them. It is worthwhile to note that similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm, both in theory and practice.

  • An image with two markers (green), and a Minimum Spanning Forest computed on the gradient of the image.
    An image with two markers (green), and a Minimum Spanning Forest computed on the gradient of the image.
  • Result of the segmentation by Minimum Spanning Forest
    Result of the segmentation by Minimum Spanning Forest
[edit]

Graph cuts

[edit]

In 2007, C. Allène et al.[13] established links relating Graph Cuts to optimal spanning forests. More precisely, they show that when the power of the weights of the graph is above a certain number, the cut minimizing the graph cuts energy is a cut by maximum spanning forest.

Shortest-path forests

[edit]

The image foresting transform (IFT) of Falcao et al.[14] is a procedure for computing shortest path forests. It has been proved by J. Cousty et al.[15] that when the markers of the IFT corresponds to extrema of the weight function, the cut induced by the forest is a watershed cut.

Random walker

[edit]

The random walker algorithm is a segmentation algorithm solving the combinatorial Dirichlet problem, adapted to image segmentation by L. Grady in 2006.[16] In 2011, C. Couprie et al. proved that when the power of the weights of the graph converge toward infinity, the cut minimizing the random walker energy is a cut by maximum spanning forest.[17]

Hierarchies

[edit]

A hierarchical watershed transformation converts the result into a graph display (i.e. the neighbor relationships of the segmented regions are determined) and applies further watershed transformations recursively. See [18] for more details. A theory linking watershed to hierarchical segmentations has been developed in[19]

Notes

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Watershed (image processing)

View on Grokipedia
from Grokipedia
The watershed transform in image processing is a region-based segmentation technique that models a image as a topographic surface, with pixel intensities representing elevations, and simulates the flooding of water from local minima to delineate object boundaries along the lines where separate flood basins meet. Introduced by Serge Beucher and Christian Lantuéjoul in 1979 as part of , it provides an intuitive framework for partitioning images into meaningful regions, particularly effective for separating touching or overlapping objects without assuming prior shape knowledge. The core principle simulates flooding from minima to form catchment basins, with boundaries at watershed lines. To mitigate common issues like oversegmentation from noise-induced minima, marker-controlled variants—introduced by Fernand Meyer and Serge Beucher in 1990 and implemented efficiently by Luc Vincent and Pierre Soille in 1991—use foreground and background markers to guide the process, ensuring robust performance on complex images. Despite its computational demands, especially for 3D volumetric data, the method excels in producing topologically accurate results and has been optimized through parallel algorithms and libraries like ITK and scikit-image. Watershed segmentation finds widespread application in for tasks such as detection in or brain tissue extraction in MRI, as well as in for analyzing microstructures in CT scans of porous media. Its integration with preprocessing techniques, like computation or , further enhances accuracy in handling irregular shapes and low-contrast boundaries, making it a foundational tool in pipelines.

Fundamentals

Core Analogy and Principles

The watershed transform in processing draws its name from a topographic , where a is interpreted as a continuous surface in which intensities represent elevation or height. Local minima in this surface correspond to valleys or basins, and the segmentation process simulates the flooding of water rising uniformly from these minima. As the water level increases, it delineates boundaries akin to watershed lines that separate distinct drainage areas, effectively partitioning the into homogeneous regions based on intensity gradients. Central to this analogy is the principle of catchment basins, which are the connected regions of the topographic surface that drain toward the same local minimum intensity point under the influence of gravity. Each catchment basin encompasses all pixels whose "downhill" paths—following the steepest descent in intensity—lead to a particular minimum, forming a natural grouping of similar elements. This concept ensures that the resulting segments correspond to areas of coherent intensity, such as object interiors in an , by associating pixels with their dominant drainage point. To address the common issue of over-segmentation, where numerous shallow minima fragment the image excessively, the analogy incorporates the construction of dams or crests along the ridges between merging catchment basins. These barriers are erected at the precise points where floods from adjacent minima would otherwise coalesce, preserving separation until higher thresholds are reached. The dams ultimately form the watershed lines, which serve as the segmentation boundaries, preventing uncontrolled merging and allowing for a hierarchical control of region fusion. The intuitive flooding process can be conceptualized at a high level as follows: begin by identifying all regional minima in the image surface; then, progressively raise the water level from these points, assigning pixels to the nearest flooding minimum while building dams at convergence points to separate basins; continue until the entire surface is flooded, with the dams defining the final boundaries. This process is often refined using topographic distance metrics to better simulate realistic water flow paths, though the core relies on intensity-based immersion.

1. Identify regional minima M_i in the [grayscale](/page/Grayscale) image f. 2. Initialize catchment basins CB_i around each M_i. 3. For increasing water levels h from min(f) to max(f): a. Flood pixels at height h into the nearest active basin. b. If floods from different basins meet at h, erect a dam (watershed line) between them. 4. Output the labeled basins separated by watershed lines. ```[](https://www.researchgate.net/publication/2407235_The_Watershed_Transformation_Applied_To_Image_Segmentation) ### Image Representation as Topography In the watershed transform for [image](/page/Image) processing, a [grayscale](/page/Grayscale) [image](/page/Image) is conceptualized as a topographic [relief](/page/Relief), where the intensity value at each [pixel](/page/Pixel) serves as the elevation of that point on a continuous surface. This representation transforms the two-dimensional [pixel](/page/Pixel) grid into a [height map](/page/Map), with brighter [pixels](/page/Pixel) corresponding to higher elevations and darker ones to lower valleys, enabling the [analogy](/page/Analogy) of water flow and flooding to model segmentation boundaries. The original formulation by Beucher and Lantuéjoul established this mapping to detect [contours](/page/The_Contours) in binary [images](/page/Image), later extended to [grayscale](/page/Grayscale) for broader segmentation tasks.[](https://people.cmm.minesparis.psl.eu/users/beucher/publi/watershed.pdf) For multidimensional images, such as color or multispectral data, the topographic representation is adapted by deriving a scalar [height function](/page/Height_function) from vector-valued pixels. A common approach computes the [gradient](/page/Gradient) magnitude across channels, where the Euclidean norm of the vector [gradient](/page/Gradient) yields a single elevation value per [pixel](/page/Pixel), emphasizing edges and discontinuities while reducing the problem to a [grayscale](/page/Grayscale) equivalent. This extension preserves the topographic analogy but requires careful vector ordering or norm selection to handle the increased dimensionality effectively.[](https://ieeexplore.ieee.org/document/4106730) Preprocessing is essential to prepare the [image](/page/Image) for this topographic interpretation, as [raw data](/page/Raw_data) often contains [noise](/page/Noise) that can introduce spurious minima and over-segmentation. [Smoothing](/page/Smoothing) techniques, such as Gaussian filtering, are applied to attenuate high-frequency [noise](/page/Noise) while maintaining structural integrity, typically using a kernel with standard deviation tuned to the [image](/page/Image)'s scale. Concurrently, the [gradient](/page/Gradient) [image](/page/Image) is computed—often via morphological or finite-difference operators—to amplify edges and create a [relief](/page/Relief) where watersheds align with object boundaries rather than intensity plateaus. Vincent and Soille recommend applying the transform to this [gradient](/page/Gradient) to focus on transitions.[](https://cse.msu.edu/~cse902/S03/watershed.pdf) Within the resulting topographic landscape, critical points define the structure: local minima are pixels or connected regions of lowest elevation from which all paths lead uphill, analogous to basin floors; local maxima are peaks where gradients point outward in all directions, serving as sources of flow; and saddle points are hybrid locations where the surface curves up in some directions and down in others, marking potential divide crests between adjacent basins. These points are identified through neighborhood analysis of the [height function](/page/Height_function), with minima initiating catchment basins in the segmentation outcome.[](https://www.sciencedirect.com/science/article/pii/0165168494900604) The topographic distance underpins path-based interpretations of this relief, quantifying connectivity over the surface. It is formally defined for points $ p $ and $ q $ in the image domain as $$ d_t(p, q) = \min_{\gamma \in \Gamma(p,q)} \left\{ \max_{r \in \gamma} f(r) \right\}, $$ where $ \Gamma(p,q) $ denotes the set of all paths from $ p $ to $ q $, $ f $ is the elevation function, and the inner maximum captures the highest barrier along each path, minimized across alternatives. This metric, introduced by Fernand Meyer, differs from [Euclidean distance](/page/Euclidean_distance) by prioritizing elevation barriers, thus guiding the delineation of influence zones in the watershed process.[](https://www.sciencedirect.com/science/article/pii/0165168494900604) ## Algorithmic Variants ### Flooding-Based Approaches Flooding-based approaches to the watershed transform in image processing simulate the gradual flooding of the image's topographic relief, starting from local minima and propagating upward until adjacent basins meet. This process iteratively assigns [pixels](/page/Pixel) to catchment basins associated with specific minima, with boundaries forming at saddle points where flooding from different basins collides, effectively delineating regions in the image. The core idea relies on ordered processing of pixel gray levels to mimic [water level](/page/Water_level) rise, ensuring efficient computation through data structures like priority queues or sorted lists.[](https://ieeexplore.ieee.org/document/87344) A foundational implementation of this flooding is the immersion simulation algorithm, which uses a first-in-first-out (FIFO) queue to flood from identified minima in increasing order of gray values, labeling connected components and detecting merges at higher thresholds. This method achieves linear [time complexity](/page/Time_complexity) O(N) for an N-pixel [image](/page/Image) by preprocessing pixels via a [bucket sort](/page/Bucket_sort). Distinct from topological variants that preserve specific connectivity properties, flooding-based methods emphasize the dynamic simulation of [water](/page/Water) propagation.[](https://ieeexplore.ieee.org/document/87344)[](https://arxiv.org/pdf/1202.0216) The drop of [water](/page/Water) principle provides the intuitive basis for basin assignment in these approaches: for any point on the topographic surface, an [infinitesimal](/page/Infinitesimal) drop of [water](/page/Water) placed there would descend along a steepest path to a regional minimum, thereby belonging to that minimum's catchment basin; watershed lines separate points whose drops flow to different minima. This principle resolves ambiguities in flat regions by considering minimal perturbations, ensuring a complete partitioning of the image into basins. In inter-pixel formulations of flooding-based watersheds, segmentation boundaries are placed on the edges between adjacent [pixels](/page/Pixel) rather than assigning entire [pixels](/page/Pixel) to basins, yielding thinner and more accurate [contours](/page/The_Contours) by treating the image as a graph where dual sites represent interfaces. This variant, which simulates flooding across pixel separations, avoids the thicker lines typical of pixel-based methods and is particularly useful for precise [edge detection](/page/Edge_detection) in continuous domains.[](https://arxiv.org/pdf/1202.0216) A key challenge in pure flooding-based watersheds is over-segmentation, arising from numerous noise-induced local minima that create extraneous basins, leading to fragmented regions in the output. To mitigate this, basic marker-controlled strategies impose internal markers on foreground objects of interest and external markers on the background, restricting flooding to start only from these predefined seeds and preventing noise-driven basins from forming.[](https://ieeexplore.ieee.org/document/87344) The following [pseudocode](/page/Pseudocode) outlines a simple queue-based flooding process for a [grayscale](/page/Grayscale) [image](/page/Image) $I$, assuming minima have been pre-identified and labeled; it processes [pixels](/page/Pixel) level by level, propagating labels from basins.

1. Identify regional minima M_i in the [grayscale](/page/Grayscale) image f. 2. Initialize catchment basins CB_i around each M_i. 3. For increasing water levels h from min(f) to max(f): a. Flood pixels at height h into the nearest active basin. b. If floods from different basins meet at h, erect a dam (watershed line) between them. 4. Output the labeled basins separated by watershed lines. ```[](https://www.researchgate.net/publication/2407235_The_Watershed_Transformation_Applied_To_Image_Segmentation) ### Image Representation as Topography In the watershed transform for [image](/page/Image) processing, a [grayscale](/page/Grayscale) [image](/page/Image) is conceptualized as a topographic [relief](/page/Relief), where the intensity value at each [pixel](/page/Pixel) serves as the elevation of that point on a continuous surface. This representation transforms the two-dimensional [pixel](/page/Pixel) grid into a [height map](/page/Map), with brighter [pixels](/page/Pixel) corresponding to higher elevations and darker ones to lower valleys, enabling the [analogy](/page/Analogy) of water flow and flooding to model segmentation boundaries. The original formulation by Beucher and Lantuéjoul established this mapping to detect [contours](/page/The_Contours) in binary [images](/page/Image), later extended to [grayscale](/page/Grayscale) for broader segmentation tasks.[](https://people.cmm.minesparis.psl.eu/users/beucher/publi/watershed.pdf) For multidimensional images, such as color or multispectral data, the topographic representation is adapted by deriving a scalar [height function](/page/Height_function) from vector-valued pixels. A common approach computes the [gradient](/page/Gradient) magnitude across channels, where the Euclidean norm of the vector [gradient](/page/Gradient) yields a single elevation value per [pixel](/page/Pixel), emphasizing edges and discontinuities while reducing the problem to a [grayscale](/page/Grayscale) equivalent. This extension preserves the topographic analogy but requires careful vector ordering or norm selection to handle the increased dimensionality effectively.[](https://ieeexplore.ieee.org/document/4106730) Preprocessing is essential to prepare the [image](/page/Image) for this topographic interpretation, as [raw data](/page/Raw_data) often contains [noise](/page/Noise) that can introduce spurious minima and over-segmentation. [Smoothing](/page/Smoothing) techniques, such as Gaussian filtering, are applied to attenuate high-frequency [noise](/page/Noise) while maintaining structural integrity, typically using a kernel with standard deviation tuned to the [image](/page/Image)'s scale. Concurrently, the [gradient](/page/Gradient) [image](/page/Image) is computed—often via morphological or finite-difference operators—to amplify edges and create a [relief](/page/Relief) where watersheds align with object boundaries rather than intensity plateaus. Vincent and Soille recommend applying the transform to this [gradient](/page/Gradient) to focus on transitions.[](https://cse.msu.edu/~cse902/S03/watershed.pdf) Within the resulting topographic landscape, critical points define the structure: local minima are pixels or connected regions of lowest elevation from which all paths lead uphill, analogous to basin floors; local maxima are peaks where gradients point outward in all directions, serving as sources of flow; and saddle points are hybrid locations where the surface curves up in some directions and down in others, marking potential divide crests between adjacent basins. These points are identified through neighborhood analysis of the [height function](/page/Height_function), with minima initiating catchment basins in the segmentation outcome.[](https://www.sciencedirect.com/science/article/pii/0165168494900604) The topographic distance underpins path-based interpretations of this relief, quantifying connectivity over the surface. It is formally defined for points $ p $ and $ q $ in the image domain as $$ d_t(p, q) = \min_{\gamma \in \Gamma(p,q)} \left\{ \max_{r \in \gamma} f(r) \right\}, $$ where $ \Gamma(p,q) $ denotes the set of all paths from $ p $ to $ q $, $ f $ is the elevation function, and the inner maximum captures the highest barrier along each path, minimized across alternatives. This metric, introduced by Fernand Meyer, differs from [Euclidean distance](/page/Euclidean_distance) by prioritizing elevation barriers, thus guiding the delineation of influence zones in the watershed process.[](https://www.sciencedirect.com/science/article/pii/0165168494900604) ## Algorithmic Variants ### Flooding-Based Approaches Flooding-based approaches to the watershed transform in image processing simulate the gradual flooding of the image's topographic relief, starting from local minima and propagating upward until adjacent basins meet. This process iteratively assigns [pixels](/page/Pixel) to catchment basins associated with specific minima, with boundaries forming at saddle points where flooding from different basins collides, effectively delineating regions in the image. The core idea relies on ordered processing of pixel gray levels to mimic [water level](/page/Water_level) rise, ensuring efficient computation through data structures like priority queues or sorted lists.[](https://ieeexplore.ieee.org/document/87344) A foundational implementation of this flooding is the immersion simulation algorithm, which uses a first-in-first-out (FIFO) queue to flood from identified minima in increasing order of gray values, labeling connected components and detecting merges at higher thresholds. This method achieves linear [time complexity](/page/Time_complexity) O(N) for an N-pixel [image](/page/Image) by preprocessing pixels via a [bucket sort](/page/Bucket_sort). Distinct from topological variants that preserve specific connectivity properties, flooding-based methods emphasize the dynamic simulation of [water](/page/Water) propagation.[](https://ieeexplore.ieee.org/document/87344)[](https://arxiv.org/pdf/1202.0216) The drop of [water](/page/Water) principle provides the intuitive basis for basin assignment in these approaches: for any point on the topographic surface, an [infinitesimal](/page/Infinitesimal) drop of [water](/page/Water) placed there would descend along a steepest path to a regional minimum, thereby belonging to that minimum's catchment basin; watershed lines separate points whose drops flow to different minima. This principle resolves ambiguities in flat regions by considering minimal perturbations, ensuring a complete partitioning of the image into basins. In inter-pixel formulations of flooding-based watersheds, segmentation boundaries are placed on the edges between adjacent [pixels](/page/Pixel) rather than assigning entire [pixels](/page/Pixel) to basins, yielding thinner and more accurate [contours](/page/The_Contours) by treating the image as a graph where dual sites represent interfaces. This variant, which simulates flooding across pixel separations, avoids the thicker lines typical of pixel-based methods and is particularly useful for precise [edge detection](/page/Edge_detection) in continuous domains.[](https://arxiv.org/pdf/1202.0216) A key challenge in pure flooding-based watersheds is over-segmentation, arising from numerous noise-induced local minima that create extraneous basins, leading to fragmented regions in the output. To mitigate this, basic marker-controlled strategies impose internal markers on foreground objects of interest and external markers on the background, restricting flooding to start only from these predefined seeds and preventing noise-driven basins from forming.[](https://ieeexplore.ieee.org/document/87344) The following [pseudocode](/page/Pseudocode) outlines a simple queue-based flooding process for a [grayscale](/page/Grayscale) [image](/page/Image) $I$, assuming minima have been pre-identified and labeled; it processes [pixels](/page/Pixel) level by level, propagating labels from basins.

Initialize a queue Q with all minimum , labeled with their basin ID Set all other as unlabelled While Q is not empty: Dequeue p For each unlabelled neighbor n of p: If gray(I[n]) <= current flood level: Label n with basin ID of p Enqueue n Else if n is at a (meets multiple basins): Mark n as watershed boundary Increase flood level to next gray value threshold Merge adjacent basins if they connect at the same level

This FIFO-based propagation ensures basins expand uniformly, with merges handled by union operations on labels.[](https://ieeexplore.ieee.org/document/87344) ### Distance-Based Approaches Distance-based approaches to the watershed transform in [image](/page/Image) processing emphasize the [computation](/page/Computation) of [distance](/page/Distance) metrics within the topographic representation of the [image](/page/Image), enabling segmentation through path-based delineation of catchment basins rather than iterative flooding simulations. These methods model the [image](/page/Image) as a height map where pixel intensities define [elevation](/page/Elevation), and segmentation boundaries emerge from the loci of [equidistant](/page/Equidistant) points relative to [seed](/page/Seed) minima. By prioritizing metric-driven assignment, such variants offer computational efficiency and precise control over boundary formation in complex terrains.[](https://doi.org/10.3233/FI-2000-411207) Central to these approaches is the topographic distance, which quantifies the "[cost](/page/Cost)" of connecting two pixels by considering the image's [relief](/page/Relief). Defined for an image function $f$, the topographic distance $T_f(p, q)$ between pixels $p$ and $q$ is given by $$ T_f(p, q) = \inf_{\gamma} \max_{r \in \gamma} f(r), $$ where the infimum is taken over all paths $\gamma$ from $p$ to $q$. This minimax formulation captures the lowest possible maximum height along any connecting path, effectively measuring the highest barrier to traversal.[](https://doi.org/10.1016/0165-1684(94)90060-4) Geodesic distance integration refines this metric by fusing Euclidean spatial separation with intensity-derived costs, yielding a path length that balances [geometry](/page/Geometry) and content. In a [geodesic](/page/Geodesic) framework, distances are computed within a mask image, where the path integral incorporates both positional increments and local [gradient](/page/Gradient) magnitudes, such as $d(p, q) = \int_{\gamma} \sqrt{ds^2 + g(f(s))^2} ds$, with $g$ modulating intensity influence. This combination allows segmentation to respect object shapes while adapting to varying contrast, particularly useful for delineating regions in gradient-weighted spaces.[](https://doi.org/10.3233/FI-2000-411207) The algorithmic steps typically begin with marker selection to identify basin minima, often via thresholding or morphological operations on the [image](/page/Image). A topographic distance transform is then constructed from these seeds, assigning to each [pixel](/page/Pixel) the minimum distance to the nearest marker using graph search techniques, such as the iterative [forest](/page/Forest) transform, which builds a shortest-path [forest](/page/Forest) in $O(m + n \log n)$ time for an [image](/page/Image) of $n$ pixels and $m$ edges. Pixels are labeled to their closest basin based on these distances, with watershed ridges forming where distances to multiple basins are equal, resolved by tie-breaking rules like priority queues. In comparison, [Euclidean distance](/page/Euclidean_distance) partitions pixels solely by straight-line proximity to seeds, forming Voronoi diagrams that ignore intensity variations and thus prone to leaks across adjacent but separated objects. Topographic distances mitigate this by constraining paths to low-maximum routes, blocking merges over even weak edges if they represent relative height differences, thereby enhancing boundary [fidelity](/page/Fidelity) in low-contrast scenarios without excessive over-segmentation.[](https://doi.org/10.3233/FI-2000-411207) A practical example arises in binary images for isolating touching foreground objects, where the [Euclidean distance](/page/Euclidean_distance) transform first generates a continuous height map from object boundaries, with minima at object centers. Watershed application on this transform assigns influence zones via topographic distances from these minima, producing clean separations equivalent to the skeleton by zones of influence and avoiding artifacts from direct binary processing.[](https://doi.org/10.3233/FI-2000-411207) ### Topological and Inter-Pixel Variants Topological watershed variants address limitations in traditional flooding methods by ensuring that the segmentation process preserves the intrinsic [topology](/page/Topology) of the [image](/page/Image), particularly its connectivity and [Euler characteristic](/page/Euler_characteristic). Introduced by Couprie and Bertrand in 1997, this approach defines a [grayscale](/page/Grayscale) [topology](/page/Topology) based on the immersion of level sets, where the [image](/page/Image) is treated as a stack of binary slices ordered by gray-level thresholds.[](https://www.spiedigitallibrary.org/conference-proceedings-of-spie/3168/0000/Topological-gray-scale-watershed-transformation/10.1117/12.292778.full) The transformation modifies the image function without creating spurious components or altering the genus of objects, achieved by selectively lowering minima while maintaining the number of connected components across sublevel sets. This preservation is quantified through the [Euler characteristic](/page/Euler_characteristic), a topological invariant that counts the alternating sum of connected components, holes, and voids in the [image](/page/Image) structure. Inter-pixel watershed methods, developed concurrently in the early [1990s](/page/1990s), shift the focus from assigning entire pixels to basins to delineating boundaries along the edges between pixels, enabling more precise contour extraction. Beucher and Meyer formalized this variant as an algorithmic flooding process on the [dual graph](/page/Dual_graph) of the image lattice, where watershed lines form along crack edges derived from morphological gradients.[](http://cmm.ensmp.fr/~beucher/publi/watershed.pdf) This inter-pixel assignment avoids the over-segmentation issues of pixel-based approaches by directly computing divide lines, which are thin and adhere closely to intensity discontinuities, thus improving boundary accuracy in applications like object contouring.[](https://link.springer.com/chapter/10.1007/978-3-540-30125-7_104) Topological distance measures in these variants extend the immersion framework to define "distance" not via Euclidean or [geodesic](/page/Geodesic) metrics, but through levels of topological immersion that respect connectivity without introducing distortions. Couprie et al. later proposed quasi-linear algorithms for computing such watersheds, ensuring computational efficiency while upholding topological invariance, with [time complexity](/page/Time_complexity) approaching that of standard methods.[](https://hal.science/hal-00622399v1/document) These measures are particularly valuable in preserving object [topology](/page/Topology) during segmentation, such as preventing the artificial creation of holes in uniform regions or unwanted merging of topologically distinct components, which is critical in [medical imaging](/page/Medical_imaging) for accurate organ delineation.[](https://www.lrde.epita.fr/dload/20080625-Seminar/abraham-watershed.pdf) Developed in the [1990s](/page/1990s) to mitigate topological distortions inherent in earlier simulation-based techniques, these variants build on the drop-of-water principle by incorporating rigorous topological constraints, fostering applications in topology-sensitive domains like biological structure analysis. ## Specific Algorithms ### Meyer's Flooding Algorithm Meyer's [flooding algorithm](/page/Flooding_algorithm), as efficiently realized in the immersion-based implementation by Vincent and Soille, simulates the progressive flooding of topographic basins in a [grayscale](/page/Grayscale) [image](/page/Image) using a first-in-first-out (FIFO) queue to manage level-by-level progression from local minima. This approach treats the [image](/page/Image) as a [landscape](/page/Landscape) where [pixel](/page/Pixel) intensities represent altitudes, with water rising uniformly from punctured minima until basins merge along watershed lines. The method ensures efficient computation by processing pixels in a single pass after initial sorting, avoiding the need for recursive flooding or complex distance transforms in basic cases.[](https://ieeexplore.ieee.org/document/87344) The algorithm proceeds in two main phases: sorting and flooding. First, all [pixel](/page/Pixel)s are sorted in ascending order of their gray-level values, enabling [sequential access](/page/Sequential_access) during immersion; this step requires O(N time for N pixels using a bucket-sort [variant](/page/The_Variant) adapted for discrete gray levels. Second, the flooding phase initializes by identifying regional minima—connected components of pixels where each has no lower-valued neighbors—and assigns unique labels to them while marking surrounding pixels as masked. A FIFO queue is then populated with the neighbors of these minima at the next intensity level (h+1). As processing continues, the queue drives breadth-first propagation: for each dequeued pixel, if it has no labeled neighbors, it becomes a new minimum with a fresh label; if adjacent to one label, it inherits that label; if adjacent to multiple identical labels, it propagates that label; and if adjacent to differing labels, it is marked as a watershed pixel to delineate the boundary. This labeling extends catchment basins via their [geodesic](/page/Geodesic) influence zones, simulating [water](/page/Water) overflow.[](https://ieeexplore.ieee.org/document/87344)[](https://cse.msu.edu/~cse902/S03/watershed.pdf) Flat regions, or plateaus, pose challenges by potentially causing premature or incorrect basin merging due to uniform intensities. The algorithm addresses this through specialized rules during flooding: a auxiliary [distance](/page/Distance) [image](/page/Image) tracks [geodesic](/page/Geodesic) distances from labeled basins into the plateau, ensuring labels propagate from the closest or lowest-connected minima rather than arbitrarily. Specifically, unlabeled pixels in a plateau are initially masked, and upon encountering labeled neighbors, they are assigned based on connectivity rules that prioritize [propagation](/page/Propagation) without crossing boundaries. This prevents thick watershed lines or deviations, maintaining topological accuracy. Pixels adjacent to basins with different labels are designated as watershed points, preserving separation.[](https://ieeexplore.ieee.org/document/87344)[](https://cse.msu.edu/~cse902/S03/watershed.pdf) Basin merging occurs dynamically when floods from distinct minima converge at a pixel during propagation. Merging of entire basins is not performed post hoc but emerges from the labeling process, with final unions possible via subsequent graph-based analysis if needed.[](https://ieeexplore.ieee.org/document/87344)[](https://www.researchgate.net/publication/2879434_The_Watershed_Transform_Definitions_Algorithms_and_Parallelization_Strategies) The [time complexity](/page/Time_complexity) of the algorithm is linear, O(N, achieved through the single sorting pass (approximately 2N operations) and flooding, where each [pixel](/page/Pixel) and its neighbors are examined a constant number of times on average (around three scans per pixel in 2D). This efficiency made it a cornerstone for practical [image segmentation](/page/Image_segmentation), with reported execution times of about 2.5 seconds for a 256×256 [image](/page/Image) on early 1990s hardware. The original publication detailing this implementation is Vincent and Soille's [1991](/page/1991) paper, which provided the key framework for efficient watershed computation in digital spaces.[](https://ieeexplore.ieee.org/document/87344) ### Optimal Spanning Forest Methods Optimal spanning forest methods in watershed image processing formulate segmentation boundaries as minimum cuts within region adjacency graphs (RAGs), where pixels or regions are nodes and edges represent adjacencies weighted by topographic distances or gradient magnitudes.[](https://www.researchgate.net/publication/229014695_Some_links_between_min-cuts_optimal_spanning_forests_and_watersheds) These cuts delineate catchment basins by separating pixels that flow toward different marker seeds under the drop-of-water principle, ensuring consistent partitioning without over-segmentation in flat regions. The capacity of such a cut $C$, defined as the boundary between basins, is given by the sum of the weights of edges crossing it: $$ P(C) = \sum_{e \in E(C)} w(e), $$ where $E(C)$ denotes the set of boundary edges and $w(e)$ is the weight of edge $e$.[](https://www.researchgate.net/publication/229014695_Some_links_between_min-cuts_optimal_spanning_forests_and_watersheds) This formulation guarantees optimality by minimizing the total boundary strength, directly linking to global graph optimization rather than local flooding simulations. Optimal spanning forest algorithms construct these cuts by computing a maximum spanning forest (MSF) rooted at the marker seeds, where each tree in the forest connects unlabeled pixels to a unique seed, representing intra-basin connections via paths that maximize the minimum edge weight along the path.[](https://www.researchgate.net/publication/221110646_Power_watersheds_A_new_image_segmentation_framework_extending_graph_cuts_random_walker_and_optimal_spanning_forest) In a RAG derived from an image's gradient, edge weights reflect topographic distances, ensuring that forest edges prioritize low-gradient paths within basins while excluding high-gradient boundaries.[](https://www.researchgate.net/publication/221110646_Power_watersheds_A_new_image_segmentation_framework_extending_graph_cuts_random_walker_and_optimal_spanning_forest) The resulting forest induces watershed cuts at the absent edges, providing a globally optimal partitioning that aligns with the topographic analogy. A key implementation, as detailed by Couprie et al., employs [Kruskal's algorithm](/page/Kruskal's_algorithm) variant for efficient MSF construction, processing edges in decreasing weight order and using a union-find [data structure](/page/Data_structure) to merge components only if they connect to the same seed root, achieving quasi-linear [time complexity](/page/Time_complexity) $O(m \alpha(n))$ where $m$ is the number of edges, $n$ the nodes, and $\alpha$ the inverse [Ackermann function](/page/Ackermann_function).[](https://www.researchgate.net/publication/221110646_Power_watersheds_A_new_image_segmentation_framework_extending_graph_cuts_random_walker_and_optimal_spanning_forest) This avoids explicit path searches, directly building disjoint trees from multiple seeds. These methods relate closely to minimum spanning trees (MSTs), extending them to forests of disjoint trees that collectively maximize (or minimize, depending on weighting convention) the total edge weights while respecting seed constraints; in watershed contexts, the MSF maximizes connectivity strength within basins, analogous to an MST but partitioned by seeds.[](https://www.researchgate.net/publication/229014695_Some_links_between_min-cuts_optimal_spanning_forests_and_watersheds) Unlike MSTs on the full graph, the forest ensures no inter-seed connections, enforcing separate basins. A primary advantage lies in handling multiple seeds through direct, non-iterative computation, enabling precise control over basin delineation without the sequential merging artifacts of flooding-based approaches, and yielding robust segmentations even with imperfect seed placement.[](https://www.researchgate.net/publication/221110646_Power_watersheds_A_new_image_segmentation_framework_extending_graph_cuts_random_walker_and_optimal_spanning_forest) This global optimization reduces sensitivity to noise and plateaus, improving accuracy in applications like [medical imaging](/page/Medical_imaging) where markers guide tumor boundary detection. ## Connections to Other Techniques ### Graph-Based Methods Graph-based methods establish a conceptual link between watershed segmentation and graph cut techniques by interpreting the image as a graph where pixels serve as nodes and edges are weighted according to intensity differences, such as $ w_{ij} = \exp(-\beta (I_i - I_j)^2) $, to model pixel affinities. In this framework, the watershed "dams" that separate basins of attraction correspond to min-cuts in the graph, partitioning the image into regions by minimizing the total edge weight across the cut, analogous to erecting barriers in a topographic landscape to prevent flooding between minima. This analogy highlights shared principles in energy minimization for segmentation, where both approaches seek optimal boundaries based on gradient or similarity metrics.[](https://perso.esiee.fr/~coupriec/945paper.pdf) Integration of watershed with graph cuts often leverages watershed oversegmentation as an initialization step to reduce computational cost, transforming the pixel-level graph into a region adjacency graph of watershed segments before applying min-cut optimization.[](https://bmva-archive.org.uk/bmvc/2006/papers/259.pdf) This hierarchical preprocessing confines the search space, enabling faster convergence in large images while preserving fine details through subsequent boundary refinement. Adaptations of the Boykov-Kolmogorov max-flow algorithm, known for its efficiency in computing min-cuts, have been used to refine boundaries starting from watershed lines, incorporating search strategies that propagate from initial crests to adjust cuts based on regional energies. Mid-2000s works demonstrated equivalence between watersheds and graph cuts under specific metrics, such as when watershed dams align with minimum spanning trees in the dual graph, laying the foundation for unified frameworks.[](http://imagine.enpc.fr/~audibert/Mes%20articles/ISMM2007-optimal%20structures.pdf)[](https://perso.esiee.fr/~coupriec/945paper.pdf) Key differences arise in formulation: traditional watersheds produce hierarchical segmentations via progressive flooding, yielding multi-level partitions, whereas graph cuts typically yield binary or multi-label results through [global optimization](/page/Global_optimization) of a discrete [energy](/page/Energy) function. Optimal spanning forests represent a watershed-specific graph method that aligns closely with this [analogy](/page/Analogy) by constructing trees from minima without cycles, complementing min-cut approaches. In practice, combining these for interactive segmentation in [medical imaging](/page/Medical_imaging), such as tumor boundary extraction in mammograms or liver CT scans, allows users to guide the process with seeds, where watershed provides initial regions and graph cuts enforce user-specified constraints for precise delineation.[](https://perso.esiee.fr/~coupriec/945paper.pdf) ### Path and Random Walk Algorithms Path-based algorithms for watershed segmentation model the image as a [directed acyclic graph](/page/Directed_acyclic_graph) (DAG), where marker [seed](/page/Seed)s serve as roots, and each [pixel](/page/Pixel) is assigned to a basin based on the minimum-[cost](/page/Cost) path [connecting](/page/Connecting) it to a [seed](/page/Seed). The [cost](/page/Cost) of a path is typically defined using topographic distances, such as the maximum intensity difference along the path, ensuring that paths follow low-gradient regions analogous to water flow in a topographic [landscape](/page/Landscape). This construction yields a shortest-path forest, where the forest's spanning trees partition the [image](/page/Image) into connected components representing catchment basins.[](https://doi.org/10.1111/1467-8659.00495) The shortest-path forest approach is theoretically equivalent to classical watershed segmentation when the path cost corresponds to the topographic distance, as both methods delineate basins by propagating from minima along optimal paths without crossing higher barriers. In the Image Foresting Transform (IFT), this is achieved by computing the forest using a dynamic programming [strategy](/page/Strategy) on the image graph, with seeds initiating the [propagation](/page/Propagation) and unresolved pixels (e.g., plateaus) handled via tie-breaking rules to avoid over-segmentation. This equivalence has been formally established through analyses linking shortest-path forests to watershed cuts, highlighting their shared optimality under the drop-of-water principle.[](https://ieeexplore.ieee.org/document/4815259)[](https://doi.org/10.1111/1467-8659.00495) The random walker algorithm provides a probabilistic extension of path-based watershed methods, assigning each unlabeled pixel to a seed based on the probability that a random walk originating from the pixel first reaches that seed's boundary. Formulated by Grady in 2006, this involves solving the discrete Laplace equation $\Delta u = 0$ on the image graph, subject to Dirichlet boundary conditions where seed pixels are fixed to indicator functions for each label, yielding a harmonic function $u$ whose values represent segmentation probabilities. This soft assignment contrasts with hard basin membership in traditional watersheds, enabling multi-label segmentations that capture uncertainty.[](https://ieeexplore.ieee.org/document/1704833) Random walker methods excel in handling noisy images by producing probability maps that smooth out local perturbations, as the expected segmentation under pure [noise](/page/Noise) aligns with uniform probabilities across labels, reducing sensitivity to outliers compared to deterministic path assignments. Computationally, shortest-path forests are efficiently derived using multisource [Dijkstra's algorithm](/page/Dijkstra's_algorithm) with a [priority queue](/page/Priority_queue), achieving linear [time complexity](/page/Time_complexity) in the number of pixels for sparse graphs. For random walks, the Laplace system is solved via iterative methods like conjugate gradients on the sparse [Laplacian matrix](/page/Laplacian_matrix), scaling well for large images through parallelizable sparse linear algebra.[](https://ieeexplore.ieee.org/document/1704833)[](https://doi.org/10.1111/1467-8659.00495) ## Advanced Topics ### Hierarchical Watersheds Hierarchical watersheds extend single-level watershed methods by constructing multi-scale segmentations through the progressive merging of basins at increasing intensity thresholds, thereby capturing [image](/page/Image) structures across varying levels of detail. This approach stacks watershed partitions, starting from a fine-grained oversegmentation and coarsening it by flooding adjacent basins when the threshold exceeds the height of separating crests, resulting in a nested sequence of partitions that represent the image's hierarchical organization. The [hierarchy](/page/Hierarchy) is typically represented as a [tree](/page/Tree) of partitions, such as a [dendrogram](/page/Dendrogram) or an ultrametric distance [tree](/page/Tree), where leaves correspond to individual pixels or initial basins, and internal nodes denote merged regions, with [branch](/page/Branch) heights indicating the threshold at which merges occur. This [tree structure](/page/Tree_structure) encodes all possible segmentations obtainable by thresholding, allowing flexible extraction of partitions at desired scales. Key algorithms for [hierarchy](/page/Hierarchy) construction include h-minima transforms, which iteratively suppress minima shallower than a [parameter](/page/Parameter) $ h $ to eliminate insignificant basins and build levels of increasing coarseness,[](https://www.isprs.org/proceedings/xxxvi/3-w52/final_papers/zhao_2007.pdf) and [persistent homology](/page/Persistent_homology) techniques, which compute the persistence of topological features (like connected components) across filtration scales to form a hierarchical representation akin to a merge [tree](/page/Tree).[](https://hal.science/hal-03676854/file/article.pdf) A foundational contribution is the 1996 method by Najman and Schmitt, which introduces hierarchical flooding on topographic graphs by assigning geodesic saliency to watershed contours based on their dynamics—the minimal path length in the graph connecting contour points—prioritizing merges of low-saliency (less significant) boundaries to create a balanced [hierarchy](/page/Hierarchy).[](https://ieeexplore.ieee.org/document/546254) In this context, the ultrametric distance $ d_h(p, q) $ between pixels $ p $ and $ q $ quantifies their hierarchical linkage as the lowest threshold height at which they join the same basin: $$ d_h(p, q) = \inf \{ h \mid p, q \in \text{same basin at height } h \} $$ This distance satisfies the ultrametric property ($ d_h(p, q) \leq \max(d_h(p, r), d_h(r, q)) $), ensuring the tree-like hierarchy without cycles.[](https://ieeexplore.ieee.org/document/546254) Recent advances include GPU-based parallel partitioning algorithms for efficient hierarchical segmentation (as of 2024) and supervised deep learning methods for predicting hierarchical structures (as of 2023), enhancing scalability for large-scale image analysis.[](https://arxiv.org/abs/2410.08946)[](https://doi.org/10.1007/978-3-031-49018-7_15) Hierarchical watersheds offer benefits such as user-controlled scale selection via saliency maps that visualize merge priorities, enabling the retention of salient features while reducing over-segmentation by discarding transient basins.[](https://ieeexplore.ieee.org/document/546254)[](https://hal.science/hal-03676854/file/article.pdf) ### Extensions and Improvements Marker-controlled watersheds address the over-segmentation issue inherent in traditional watershed methods by incorporating user-defined or automatically generated markers to constrain the flooding process. Internal markers represent foreground objects of interest, while external markers delineate the background, guiding the segmentation to produce more accurate and fewer regions. This approach, introduced in the morphological framework, allows precise control over basin formation and has become a standard technique for robust image partitioning.[](https://www.researchgate.net/publication/230837870_The_Morphological_Approach_to_Segmentation_The_Watershed_Transformation) Extensions to three-dimensional (3D) and video data adapt the watershed principle to volumetric images and temporal sequences. In 3D segmentation, volumetric flooding algorithms process image stacks, such as those from [confocal microscopy](/page/Confocal_microscopy), by extending distance transforms and gradient computations to higher dimensions, enabling the delineation of complex structures like cell nuclei.[](https://doi.org/10.1364/BOE.502228) For video, spatio-temporal watersheds incorporate motion cues and temporal consistency constraints to maintain stable segmentations across frames, reducing flickering and improving object tracking in dynamic scenes.[](https://ieeexplore.ieee.org/document/1246970) Hybrid methods combine watersheds with other segmentation paradigms to refine boundaries and enhance accuracy. Integration with active contours uses watershed results as initializations for deformable models, allowing iterative adjustment of contours to better fit object edges while leveraging the global partitioning of watersheds.[](https://link.springer.com/chapter/10.1007/3-540-45786-0_74) Hybrids with [machine learning](/page/Machine_learning) have advanced further; for example, deep learning-enhanced watersheds integrate convolutional neural networks to predict energy maps or markers, treating segmentation as an end-to-end process, as demonstrated in microstructural analysis applications (as of 2023).[](https://doi.org/10.1007/s10853-023-08901-w) Handling color images requires adaptations beyond scalar gradients, employing vector-valued distances and multivariate gradients to account for inter-channel correlations. These methods compute gradients in color spaces like RGB or Lab, using morphological operations on vector fields to define catchment basins that respect chromatic boundaries, thus avoiding artifacts in multispectral segmentation.[](https://www.sciencedirect.com/science/article/abs/pii/S0167865502003938) The sensitivity of watershed algorithms to noise, which can introduce spurious minima and lead to fragmented regions, is mitigated through preprocessing techniques like [anisotropic diffusion](/page/Anisotropic_diffusion). This nonlinear filtering smooths homogeneous areas while preserving edges, producing cleaner gradient maps for subsequent watershed application and improving overall segmentation reliability.[](http://users.ntua.gr/karank/img/Karantzalos_IJRS_2006.pdf) ## Practical Considerations ### Advantages and Limitations The watershed algorithm in [image](/page/Image) processing offers several key advantages that make it a valuable tool for segmentation tasks. Its flooding analogy provides an intuitive conceptualization, simulating water rising from image minima to delineate boundaries, which facilitates understanding and application in complex scenarios.[](https://www.researchgate.net/publication/2407235_The_Watershed_Transformation_Applied_To_Image_Segmentation) Efficient implementations, such as the immersion-based approach, achieve linear [time complexity](/page/Time_complexity) relative to the number of pixels, enabling rapid processing even for large images. Additionally, the method consistently produces closed contours that fully partition the image domain, ensuring complete and connected boundaries without gaps.[](https://digitalcommons.usu.edu/microscopy/vol1992/iss6/28/) This property is particularly beneficial for separating overlapping or touching objects, as demonstrated in [electron microscopy](/page/Microscopy) applications where it effectively isolates cellular structures.[](https://www.researchgate.net/publication/2407235_The_Watershed_Transformation_Applied_To_Image_Segmentation) Despite these strengths, watershed methods have notable limitations that can compromise segmentation quality. The algorithm is prone to over-segmentation, especially in noisy images, where spurious local minima lead to excessive region fragmentation.[](https://pubmed.ncbi.nlm.nih.gov/15084070/) It exhibits high sensitivity to such local minima in the [gradient](/page/Gradient) landscape, resulting in fragmented outputs that require post-processing to merge regions.[](https://www.sciencedirect.com/topics/computer-science/watershed-segmentation) Without markers to constrain the flooding process, boundaries can "leak" across weak edges, failing to accurately separate adjacent objects with subtle intensity differences.[](https://pubmed.ncbi.nlm.nih.gov/15084070%) In comparison to simple thresholding techniques, watersheds generally handle uneven illumination more robustly by operating on the [image gradient](/page/Image_gradient) rather than raw intensity, which mitigates the impact of lighting variations that often cause thresholding to produce inconsistent regions.[](https://www.researchgate.net/publication/260018901_An_Image_Binarization_Algorithm_Using_Watershed-Based_Local_Thresholding) However, this comes at the cost of higher computational demands, as watershed requires [gradient](/page/Gradient) computation and flooding simulation, whereas thresholding is typically faster but less adaptable to complex scenes.[](https://www.researchgate.net/publication/260018901_An_Image_Binarization_Algorithm_Using_Watershed-Based_Local_Thresholding) Quantitative evaluations highlight these trade-offs, particularly the role of markers in enhancing performance. Marker-controlled watersheds have shown Dice coefficients of 0.964 ± 0.069 in X-ray segmentation tasks, outperforming manual thresholding's 0.937 ± 0.119 by reducing boundary errors in challenging datasets.[](https://www.sciencedirect.com/science/article/abs/pii/S016926071300415X) Benchmarks often report significant over-segmentation in noisy images without markers, underscoring the need for preprocessing to achieve reliable results.[](https://www.sciencedirect.com/science/article/abs/pii/S016926071300415X) Historically, early watershed implementations in the 1980s, such as those by Beucher and Lantuejoul, largely overlooked over-segmentation issues, treating all minima equally and leading to impractical fragmentations in real images.[](https://www.researchgate.net/publication/221661175_The_watershed_concept_and_its_use_in_segmentation_a_brief_history) This prompted innovations in the [1990s](/page/1990s), including Beucher's marker-based refinements and the Vincent-Soille algorithm, which constrained flooding to user-defined or automatic markers to mitigate these flaws and enable practical adoption.[](https://www.researchgate.net/publication/221661175_The_watershed_concept_and_its_use_in_segmentation_a_brief_history) ### Implementation Challenges One of the primary implementation challenges in watershed algorithms is parameter selection, particularly the choice of markers that define initial catchment basins to guide the flooding process and mitigate over-segmentation. Markers can be selected manually for precise control or automated using techniques such as [distance](/page/Distance) transforms from object boundaries or saliency detection to identify foreground and background regions. In marker-controlled variants, improper marker placement—such as insufficient separation between adjacent objects—can lead to merged segments, necessitating iterative refinement or preprocessing steps like morphological operations to generate reliable markers.[](https://docs.opencv.org/4.x/d3/db4/tutorial_py_watershed.html)[](https://scikit-image.org/docs/stable/auto_examples/segmentation/plot_watershed.html) Memory efficiency poses significant hurdles, especially for high-resolution or volumetric [images](/page/Image), where the algorithm's queue-based flooding can require storing extensive topographic maps or [label](/page/Label) arrays. For instance, [processing](/page/Processing) a 1024³ [image](/page/Image) may demand up to 2 TiB of [memory](/page/Memory) in certain implementations due to the need to track [pixel](/page/Pixel) elevations and basin assignments simultaneously. To address this, strategies include hierarchical priority queues that [process](/page/Process) levels incrementally or graph-based reductions that [prune](/page/Prune) redundant nodes before flooding, thereby reducing peak [memory](/page/Memory) usage by 10-20% in optimized libraries.[](https://www.mdpi.com/2313-433X/4/10/123) Parallelization efforts face difficulties in preserving the sequential flooding order inherent to the immersion [simulation](/page/Simulation) model, as concurrent updates to shared basins can introduce race conditions or incorrect merges. GPU adaptations, such as path-reducing watershed variants, mitigate this by decomposing the [image](/page/Image) into independent subgraphs and synchronizing only at boundary pixels, enabling speedups of 10-50x on large datasets while maintaining topological accuracy. However, these require careful load balancing to avoid bottlenecks in plateau regions where multiple paths converge.[](https://arxiv.org/abs/2410.08946)[](https://www.sciencedirect.com/science/article/pii/S0743731525001078) Software tools for watershed implementation are widely available in open-source libraries, facilitating deployment without custom coding from scratch. [OpenCV](/page/OpenCV) provides a marker-based `cv.watershed` function that integrates seamlessly with preprocessing pipelines like distance transforms, supporting both CPU and GPU backends for 2D/3D images. Similarly, scikit-image's `skimage.segmentation.watershed` offers flexibility with masking and compactness parameters, ideal for Python-based workflows, while libraries like ITK and Mahotas extend support for [medical imaging](/page/Medical_imaging) with built-in marker extraction. For custom needs, [pseudocode](/page/Pseudocode) for Meyer's flooding can be adapted as follows:

This FIFO-based propagation ensures basins expand uniformly, with merges handled by union operations on labels.[](https://ieeexplore.ieee.org/document/87344) ### Distance-Based Approaches Distance-based approaches to the watershed transform in [image](/page/Image) processing emphasize the [computation](/page/Computation) of [distance](/page/Distance) metrics within the topographic representation of the [image](/page/Image), enabling segmentation through path-based delineation of catchment basins rather than iterative flooding simulations. These methods model the [image](/page/Image) as a height map where pixel intensities define [elevation](/page/Elevation), and segmentation boundaries emerge from the loci of [equidistant](/page/Equidistant) points relative to [seed](/page/Seed) minima. By prioritizing metric-driven assignment, such variants offer computational efficiency and precise control over boundary formation in complex terrains.[](https://doi.org/10.3233/FI-2000-411207) Central to these approaches is the topographic distance, which quantifies the "[cost](/page/Cost)" of connecting two pixels by considering the image's [relief](/page/Relief). Defined for an image function $f$, the topographic distance $T_f(p, q)$ between pixels $p$ and $q$ is given by $$ T_f(p, q) = \inf_{\gamma} \max_{r \in \gamma} f(r), $$ where the infimum is taken over all paths $\gamma$ from $p$ to $q$. This minimax formulation captures the lowest possible maximum height along any connecting path, effectively measuring the highest barrier to traversal.[](https://doi.org/10.1016/0165-1684(94)90060-4) Geodesic distance integration refines this metric by fusing Euclidean spatial separation with intensity-derived costs, yielding a path length that balances [geometry](/page/Geometry) and content. In a [geodesic](/page/Geodesic) framework, distances are computed within a mask image, where the path integral incorporates both positional increments and local [gradient](/page/Gradient) magnitudes, such as $d(p, q) = \int_{\gamma} \sqrt{ds^2 + g(f(s))^2} ds$, with $g$ modulating intensity influence. This combination allows segmentation to respect object shapes while adapting to varying contrast, particularly useful for delineating regions in gradient-weighted spaces.[](https://doi.org/10.3233/FI-2000-411207) The algorithmic steps typically begin with marker selection to identify basin minima, often via thresholding or morphological operations on the [image](/page/Image). A topographic distance transform is then constructed from these seeds, assigning to each [pixel](/page/Pixel) the minimum distance to the nearest marker using graph search techniques, such as the iterative [forest](/page/Forest) transform, which builds a shortest-path [forest](/page/Forest) in $O(m + n \log n)$ time for an [image](/page/Image) of $n$ pixels and $m$ edges. Pixels are labeled to their closest basin based on these distances, with watershed ridges forming where distances to multiple basins are equal, resolved by tie-breaking rules like priority queues. In comparison, [Euclidean distance](/page/Euclidean_distance) partitions pixels solely by straight-line proximity to seeds, forming Voronoi diagrams that ignore intensity variations and thus prone to leaks across adjacent but separated objects. Topographic distances mitigate this by constraining paths to low-maximum routes, blocking merges over even weak edges if they represent relative height differences, thereby enhancing boundary [fidelity](/page/Fidelity) in low-contrast scenarios without excessive over-segmentation.[](https://doi.org/10.3233/FI-2000-411207) A practical example arises in binary images for isolating touching foreground objects, where the [Euclidean distance](/page/Euclidean_distance) transform first generates a continuous height map from object boundaries, with minima at object centers. Watershed application on this transform assigns influence zones via topographic distances from these minima, producing clean separations equivalent to the skeleton by zones of influence and avoiding artifacts from direct binary processing.[](https://doi.org/10.3233/FI-2000-411207) ### Topological and Inter-Pixel Variants Topological watershed variants address limitations in traditional flooding methods by ensuring that the segmentation process preserves the intrinsic [topology](/page/Topology) of the [image](/page/Image), particularly its connectivity and [Euler characteristic](/page/Euler_characteristic). Introduced by Couprie and Bertrand in 1997, this approach defines a [grayscale](/page/Grayscale) [topology](/page/Topology) based on the immersion of level sets, where the [image](/page/Image) is treated as a stack of binary slices ordered by gray-level thresholds.[](https://www.spiedigitallibrary.org/conference-proceedings-of-spie/3168/0000/Topological-gray-scale-watershed-transformation/10.1117/12.292778.full) The transformation modifies the image function without creating spurious components or altering the genus of objects, achieved by selectively lowering minima while maintaining the number of connected components across sublevel sets. This preservation is quantified through the [Euler characteristic](/page/Euler_characteristic), a topological invariant that counts the alternating sum of connected components, holes, and voids in the [image](/page/Image) structure. Inter-pixel watershed methods, developed concurrently in the early [1990s](/page/1990s), shift the focus from assigning entire pixels to basins to delineating boundaries along the edges between pixels, enabling more precise contour extraction. Beucher and Meyer formalized this variant as an algorithmic flooding process on the [dual graph](/page/Dual_graph) of the image lattice, where watershed lines form along crack edges derived from morphological gradients.[](http://cmm.ensmp.fr/~beucher/publi/watershed.pdf) This inter-pixel assignment avoids the over-segmentation issues of pixel-based approaches by directly computing divide lines, which are thin and adhere closely to intensity discontinuities, thus improving boundary accuracy in applications like object contouring.[](https://link.springer.com/chapter/10.1007/978-3-540-30125-7_104) Topological distance measures in these variants extend the immersion framework to define "distance" not via Euclidean or [geodesic](/page/Geodesic) metrics, but through levels of topological immersion that respect connectivity without introducing distortions. Couprie et al. later proposed quasi-linear algorithms for computing such watersheds, ensuring computational efficiency while upholding topological invariance, with [time complexity](/page/Time_complexity) approaching that of standard methods.[](https://hal.science/hal-00622399v1/document) These measures are particularly valuable in preserving object [topology](/page/Topology) during segmentation, such as preventing the artificial creation of holes in uniform regions or unwanted merging of topologically distinct components, which is critical in [medical imaging](/page/Medical_imaging) for accurate organ delineation.[](https://www.lrde.epita.fr/dload/20080625-Seminar/abraham-watershed.pdf) Developed in the [1990s](/page/1990s) to mitigate topological distortions inherent in earlier simulation-based techniques, these variants build on the drop-of-water principle by incorporating rigorous topological constraints, fostering applications in topology-sensitive domains like biological structure analysis. ## Specific Algorithms ### Meyer's Flooding Algorithm Meyer's [flooding algorithm](/page/Flooding_algorithm), as efficiently realized in the immersion-based implementation by Vincent and Soille, simulates the progressive flooding of topographic basins in a [grayscale](/page/Grayscale) [image](/page/Image) using a first-in-first-out (FIFO) queue to manage level-by-level progression from local minima. This approach treats the [image](/page/Image) as a [landscape](/page/Landscape) where [pixel](/page/Pixel) intensities represent altitudes, with water rising uniformly from punctured minima until basins merge along watershed lines. The method ensures efficient computation by processing pixels in a single pass after initial sorting, avoiding the need for recursive flooding or complex distance transforms in basic cases.[](https://ieeexplore.ieee.org/document/87344) The algorithm proceeds in two main phases: sorting and flooding. First, all [pixel](/page/Pixel)s are sorted in ascending order of their gray-level values, enabling [sequential access](/page/Sequential_access) during immersion; this step requires O(N time for N pixels using a bucket-sort [variant](/page/The_Variant) adapted for discrete gray levels. Second, the flooding phase initializes by identifying regional minima—connected components of pixels where each has no lower-valued neighbors—and assigns unique labels to them while marking surrounding pixels as masked. A FIFO queue is then populated with the neighbors of these minima at the next intensity level (h+1). As processing continues, the queue drives breadth-first propagation: for each dequeued pixel, if it has no labeled neighbors, it becomes a new minimum with a fresh label; if adjacent to one label, it inherits that label; if adjacent to multiple identical labels, it propagates that label; and if adjacent to differing labels, it is marked as a watershed pixel to delineate the boundary. This labeling extends catchment basins via their [geodesic](/page/Geodesic) influence zones, simulating [water](/page/Water) overflow.[](https://ieeexplore.ieee.org/document/87344)[](https://cse.msu.edu/~cse902/S03/watershed.pdf) Flat regions, or plateaus, pose challenges by potentially causing premature or incorrect basin merging due to uniform intensities. The algorithm addresses this through specialized rules during flooding: a auxiliary [distance](/page/Distance) [image](/page/Image) tracks [geodesic](/page/Geodesic) distances from labeled basins into the plateau, ensuring labels propagate from the closest or lowest-connected minima rather than arbitrarily. Specifically, unlabeled pixels in a plateau are initially masked, and upon encountering labeled neighbors, they are assigned based on connectivity rules that prioritize [propagation](/page/Propagation) without crossing boundaries. This prevents thick watershed lines or deviations, maintaining topological accuracy. Pixels adjacent to basins with different labels are designated as watershed points, preserving separation.[](https://ieeexplore.ieee.org/document/87344)[](https://cse.msu.edu/~cse902/S03/watershed.pdf) Basin merging occurs dynamically when floods from distinct minima converge at a pixel during propagation. Merging of entire basins is not performed post hoc but emerges from the labeling process, with final unions possible via subsequent graph-based analysis if needed.[](https://ieeexplore.ieee.org/document/87344)[](https://www.researchgate.net/publication/2879434_The_Watershed_Transform_Definitions_Algorithms_and_Parallelization_Strategies) The [time complexity](/page/Time_complexity) of the algorithm is linear, O(N, achieved through the single sorting pass (approximately 2N operations) and flooding, where each [pixel](/page/Pixel) and its neighbors are examined a constant number of times on average (around three scans per pixel in 2D). This efficiency made it a cornerstone for practical [image segmentation](/page/Image_segmentation), with reported execution times of about 2.5 seconds for a 256×256 [image](/page/Image) on early 1990s hardware. The original publication detailing this implementation is Vincent and Soille's [1991](/page/1991) paper, which provided the key framework for efficient watershed computation in digital spaces.[](https://ieeexplore.ieee.org/document/87344) ### Optimal Spanning Forest Methods Optimal spanning forest methods in watershed image processing formulate segmentation boundaries as minimum cuts within region adjacency graphs (RAGs), where pixels or regions are nodes and edges represent adjacencies weighted by topographic distances or gradient magnitudes.[](https://www.researchgate.net/publication/229014695_Some_links_between_min-cuts_optimal_spanning_forests_and_watersheds) These cuts delineate catchment basins by separating pixels that flow toward different marker seeds under the drop-of-water principle, ensuring consistent partitioning without over-segmentation in flat regions. The capacity of such a cut $C$, defined as the boundary between basins, is given by the sum of the weights of edges crossing it: $$ P(C) = \sum_{e \in E(C)} w(e), $$ where $E(C)$ denotes the set of boundary edges and $w(e)$ is the weight of edge $e$.[](https://www.researchgate.net/publication/229014695_Some_links_between_min-cuts_optimal_spanning_forests_and_watersheds) This formulation guarantees optimality by minimizing the total boundary strength, directly linking to global graph optimization rather than local flooding simulations. Optimal spanning forest algorithms construct these cuts by computing a maximum spanning forest (MSF) rooted at the marker seeds, where each tree in the forest connects unlabeled pixels to a unique seed, representing intra-basin connections via paths that maximize the minimum edge weight along the path.[](https://www.researchgate.net/publication/221110646_Power_watersheds_A_new_image_segmentation_framework_extending_graph_cuts_random_walker_and_optimal_spanning_forest) In a RAG derived from an image's gradient, edge weights reflect topographic distances, ensuring that forest edges prioritize low-gradient paths within basins while excluding high-gradient boundaries.[](https://www.researchgate.net/publication/221110646_Power_watersheds_A_new_image_segmentation_framework_extending_graph_cuts_random_walker_and_optimal_spanning_forest) The resulting forest induces watershed cuts at the absent edges, providing a globally optimal partitioning that aligns with the topographic analogy. A key implementation, as detailed by Couprie et al., employs [Kruskal's algorithm](/page/Kruskal's_algorithm) variant for efficient MSF construction, processing edges in decreasing weight order and using a union-find [data structure](/page/Data_structure) to merge components only if they connect to the same seed root, achieving quasi-linear [time complexity](/page/Time_complexity) $O(m \alpha(n))$ where $m$ is the number of edges, $n$ the nodes, and $\alpha$ the inverse [Ackermann function](/page/Ackermann_function).[](https://www.researchgate.net/publication/221110646_Power_watersheds_A_new_image_segmentation_framework_extending_graph_cuts_random_walker_and_optimal_spanning_forest) This avoids explicit path searches, directly building disjoint trees from multiple seeds. These methods relate closely to minimum spanning trees (MSTs), extending them to forests of disjoint trees that collectively maximize (or minimize, depending on weighting convention) the total edge weights while respecting seed constraints; in watershed contexts, the MSF maximizes connectivity strength within basins, analogous to an MST but partitioned by seeds.[](https://www.researchgate.net/publication/229014695_Some_links_between_min-cuts_optimal_spanning_forests_and_watersheds) Unlike MSTs on the full graph, the forest ensures no inter-seed connections, enforcing separate basins. A primary advantage lies in handling multiple seeds through direct, non-iterative computation, enabling precise control over basin delineation without the sequential merging artifacts of flooding-based approaches, and yielding robust segmentations even with imperfect seed placement.[](https://www.researchgate.net/publication/221110646_Power_watersheds_A_new_image_segmentation_framework_extending_graph_cuts_random_walker_and_optimal_spanning_forest) This global optimization reduces sensitivity to noise and plateaus, improving accuracy in applications like [medical imaging](/page/Medical_imaging) where markers guide tumor boundary detection. ## Connections to Other Techniques ### Graph-Based Methods Graph-based methods establish a conceptual link between watershed segmentation and graph cut techniques by interpreting the image as a graph where pixels serve as nodes and edges are weighted according to intensity differences, such as $ w_{ij} = \exp(-\beta (I_i - I_j)^2) $, to model pixel affinities. In this framework, the watershed "dams" that separate basins of attraction correspond to min-cuts in the graph, partitioning the image into regions by minimizing the total edge weight across the cut, analogous to erecting barriers in a topographic landscape to prevent flooding between minima. This analogy highlights shared principles in energy minimization for segmentation, where both approaches seek optimal boundaries based on gradient or similarity metrics.[](https://perso.esiee.fr/~coupriec/945paper.pdf) Integration of watershed with graph cuts often leverages watershed oversegmentation as an initialization step to reduce computational cost, transforming the pixel-level graph into a region adjacency graph of watershed segments before applying min-cut optimization.[](https://bmva-archive.org.uk/bmvc/2006/papers/259.pdf) This hierarchical preprocessing confines the search space, enabling faster convergence in large images while preserving fine details through subsequent boundary refinement. Adaptations of the Boykov-Kolmogorov max-flow algorithm, known for its efficiency in computing min-cuts, have been used to refine boundaries starting from watershed lines, incorporating search strategies that propagate from initial crests to adjust cuts based on regional energies. Mid-2000s works demonstrated equivalence between watersheds and graph cuts under specific metrics, such as when watershed dams align with minimum spanning trees in the dual graph, laying the foundation for unified frameworks.[](http://imagine.enpc.fr/~audibert/Mes%20articles/ISMM2007-optimal%20structures.pdf)[](https://perso.esiee.fr/~coupriec/945paper.pdf) Key differences arise in formulation: traditional watersheds produce hierarchical segmentations via progressive flooding, yielding multi-level partitions, whereas graph cuts typically yield binary or multi-label results through [global optimization](/page/Global_optimization) of a discrete [energy](/page/Energy) function. Optimal spanning forests represent a watershed-specific graph method that aligns closely with this [analogy](/page/Analogy) by constructing trees from minima without cycles, complementing min-cut approaches. In practice, combining these for interactive segmentation in [medical imaging](/page/Medical_imaging), such as tumor boundary extraction in mammograms or liver CT scans, allows users to guide the process with seeds, where watershed provides initial regions and graph cuts enforce user-specified constraints for precise delineation.[](https://perso.esiee.fr/~coupriec/945paper.pdf) ### Path and Random Walk Algorithms Path-based algorithms for watershed segmentation model the image as a [directed acyclic graph](/page/Directed_acyclic_graph) (DAG), where marker [seed](/page/Seed)s serve as roots, and each [pixel](/page/Pixel) is assigned to a basin based on the minimum-[cost](/page/Cost) path [connecting](/page/Connecting) it to a [seed](/page/Seed). The [cost](/page/Cost) of a path is typically defined using topographic distances, such as the maximum intensity difference along the path, ensuring that paths follow low-gradient regions analogous to water flow in a topographic [landscape](/page/Landscape). This construction yields a shortest-path forest, where the forest's spanning trees partition the [image](/page/Image) into connected components representing catchment basins.[](https://doi.org/10.1111/1467-8659.00495) The shortest-path forest approach is theoretically equivalent to classical watershed segmentation when the path cost corresponds to the topographic distance, as both methods delineate basins by propagating from minima along optimal paths without crossing higher barriers. In the Image Foresting Transform (IFT), this is achieved by computing the forest using a dynamic programming [strategy](/page/Strategy) on the image graph, with seeds initiating the [propagation](/page/Propagation) and unresolved pixels (e.g., plateaus) handled via tie-breaking rules to avoid over-segmentation. This equivalence has been formally established through analyses linking shortest-path forests to watershed cuts, highlighting their shared optimality under the drop-of-water principle.[](https://ieeexplore.ieee.org/document/4815259)[](https://doi.org/10.1111/1467-8659.00495) The random walker algorithm provides a probabilistic extension of path-based watershed methods, assigning each unlabeled pixel to a seed based on the probability that a random walk originating from the pixel first reaches that seed's boundary. Formulated by Grady in 2006, this involves solving the discrete Laplace equation $\Delta u = 0$ on the image graph, subject to Dirichlet boundary conditions where seed pixels are fixed to indicator functions for each label, yielding a harmonic function $u$ whose values represent segmentation probabilities. This soft assignment contrasts with hard basin membership in traditional watersheds, enabling multi-label segmentations that capture uncertainty.[](https://ieeexplore.ieee.org/document/1704833) Random walker methods excel in handling noisy images by producing probability maps that smooth out local perturbations, as the expected segmentation under pure [noise](/page/Noise) aligns with uniform probabilities across labels, reducing sensitivity to outliers compared to deterministic path assignments. Computationally, shortest-path forests are efficiently derived using multisource [Dijkstra's algorithm](/page/Dijkstra's_algorithm) with a [priority queue](/page/Priority_queue), achieving linear [time complexity](/page/Time_complexity) in the number of pixels for sparse graphs. For random walks, the Laplace system is solved via iterative methods like conjugate gradients on the sparse [Laplacian matrix](/page/Laplacian_matrix), scaling well for large images through parallelizable sparse linear algebra.[](https://ieeexplore.ieee.org/document/1704833)[](https://doi.org/10.1111/1467-8659.00495) ## Advanced Topics ### Hierarchical Watersheds Hierarchical watersheds extend single-level watershed methods by constructing multi-scale segmentations through the progressive merging of basins at increasing intensity thresholds, thereby capturing [image](/page/Image) structures across varying levels of detail. This approach stacks watershed partitions, starting from a fine-grained oversegmentation and coarsening it by flooding adjacent basins when the threshold exceeds the height of separating crests, resulting in a nested sequence of partitions that represent the image's hierarchical organization. The [hierarchy](/page/Hierarchy) is typically represented as a [tree](/page/Tree) of partitions, such as a [dendrogram](/page/Dendrogram) or an ultrametric distance [tree](/page/Tree), where leaves correspond to individual pixels or initial basins, and internal nodes denote merged regions, with [branch](/page/Branch) heights indicating the threshold at which merges occur. This [tree structure](/page/Tree_structure) encodes all possible segmentations obtainable by thresholding, allowing flexible extraction of partitions at desired scales. Key algorithms for [hierarchy](/page/Hierarchy) construction include h-minima transforms, which iteratively suppress minima shallower than a [parameter](/page/Parameter) $ h $ to eliminate insignificant basins and build levels of increasing coarseness,[](https://www.isprs.org/proceedings/xxxvi/3-w52/final_papers/zhao_2007.pdf) and [persistent homology](/page/Persistent_homology) techniques, which compute the persistence of topological features (like connected components) across filtration scales to form a hierarchical representation akin to a merge [tree](/page/Tree).[](https://hal.science/hal-03676854/file/article.pdf) A foundational contribution is the 1996 method by Najman and Schmitt, which introduces hierarchical flooding on topographic graphs by assigning geodesic saliency to watershed contours based on their dynamics—the minimal path length in the graph connecting contour points—prioritizing merges of low-saliency (less significant) boundaries to create a balanced [hierarchy](/page/Hierarchy).[](https://ieeexplore.ieee.org/document/546254) In this context, the ultrametric distance $ d_h(p, q) $ between pixels $ p $ and $ q $ quantifies their hierarchical linkage as the lowest threshold height at which they join the same basin: $$ d_h(p, q) = \inf \{ h \mid p, q \in \text{same basin at height } h \} $$ This distance satisfies the ultrametric property ($ d_h(p, q) \leq \max(d_h(p, r), d_h(r, q)) $), ensuring the tree-like hierarchy without cycles.[](https://ieeexplore.ieee.org/document/546254) Recent advances include GPU-based parallel partitioning algorithms for efficient hierarchical segmentation (as of 2024) and supervised deep learning methods for predicting hierarchical structures (as of 2023), enhancing scalability for large-scale image analysis.[](https://arxiv.org/abs/2410.08946)[](https://doi.org/10.1007/978-3-031-49018-7_15) Hierarchical watersheds offer benefits such as user-controlled scale selection via saliency maps that visualize merge priorities, enabling the retention of salient features while reducing over-segmentation by discarding transient basins.[](https://ieeexplore.ieee.org/document/546254)[](https://hal.science/hal-03676854/file/article.pdf) ### Extensions and Improvements Marker-controlled watersheds address the over-segmentation issue inherent in traditional watershed methods by incorporating user-defined or automatically generated markers to constrain the flooding process. Internal markers represent foreground objects of interest, while external markers delineate the background, guiding the segmentation to produce more accurate and fewer regions. This approach, introduced in the morphological framework, allows precise control over basin formation and has become a standard technique for robust image partitioning.[](https://www.researchgate.net/publication/230837870_The_Morphological_Approach_to_Segmentation_The_Watershed_Transformation) Extensions to three-dimensional (3D) and video data adapt the watershed principle to volumetric images and temporal sequences. In 3D segmentation, volumetric flooding algorithms process image stacks, such as those from [confocal microscopy](/page/Confocal_microscopy), by extending distance transforms and gradient computations to higher dimensions, enabling the delineation of complex structures like cell nuclei.[](https://doi.org/10.1364/BOE.502228) For video, spatio-temporal watersheds incorporate motion cues and temporal consistency constraints to maintain stable segmentations across frames, reducing flickering and improving object tracking in dynamic scenes.[](https://ieeexplore.ieee.org/document/1246970) Hybrid methods combine watersheds with other segmentation paradigms to refine boundaries and enhance accuracy. Integration with active contours uses watershed results as initializations for deformable models, allowing iterative adjustment of contours to better fit object edges while leveraging the global partitioning of watersheds.[](https://link.springer.com/chapter/10.1007/3-540-45786-0_74) Hybrids with [machine learning](/page/Machine_learning) have advanced further; for example, deep learning-enhanced watersheds integrate convolutional neural networks to predict energy maps or markers, treating segmentation as an end-to-end process, as demonstrated in microstructural analysis applications (as of 2023).[](https://doi.org/10.1007/s10853-023-08901-w) Handling color images requires adaptations beyond scalar gradients, employing vector-valued distances and multivariate gradients to account for inter-channel correlations. These methods compute gradients in color spaces like RGB or Lab, using morphological operations on vector fields to define catchment basins that respect chromatic boundaries, thus avoiding artifacts in multispectral segmentation.[](https://www.sciencedirect.com/science/article/abs/pii/S0167865502003938) The sensitivity of watershed algorithms to noise, which can introduce spurious minima and lead to fragmented regions, is mitigated through preprocessing techniques like [anisotropic diffusion](/page/Anisotropic_diffusion). This nonlinear filtering smooths homogeneous areas while preserving edges, producing cleaner gradient maps for subsequent watershed application and improving overall segmentation reliability.[](http://users.ntua.gr/karank/img/Karantzalos_IJRS_2006.pdf) ## Practical Considerations ### Advantages and Limitations The watershed algorithm in [image](/page/Image) processing offers several key advantages that make it a valuable tool for segmentation tasks. Its flooding analogy provides an intuitive conceptualization, simulating water rising from image minima to delineate boundaries, which facilitates understanding and application in complex scenarios.[](https://www.researchgate.net/publication/2407235_The_Watershed_Transformation_Applied_To_Image_Segmentation) Efficient implementations, such as the immersion-based approach, achieve linear [time complexity](/page/Time_complexity) relative to the number of pixels, enabling rapid processing even for large images. Additionally, the method consistently produces closed contours that fully partition the image domain, ensuring complete and connected boundaries without gaps.[](https://digitalcommons.usu.edu/microscopy/vol1992/iss6/28/) This property is particularly beneficial for separating overlapping or touching objects, as demonstrated in [electron microscopy](/page/Microscopy) applications where it effectively isolates cellular structures.[](https://www.researchgate.net/publication/2407235_The_Watershed_Transformation_Applied_To_Image_Segmentation) Despite these strengths, watershed methods have notable limitations that can compromise segmentation quality. The algorithm is prone to over-segmentation, especially in noisy images, where spurious local minima lead to excessive region fragmentation.[](https://pubmed.ncbi.nlm.nih.gov/15084070/) It exhibits high sensitivity to such local minima in the [gradient](/page/Gradient) landscape, resulting in fragmented outputs that require post-processing to merge regions.[](https://www.sciencedirect.com/topics/computer-science/watershed-segmentation) Without markers to constrain the flooding process, boundaries can "leak" across weak edges, failing to accurately separate adjacent objects with subtle intensity differences.[](https://pubmed.ncbi.nlm.nih.gov/15084070%) In comparison to simple thresholding techniques, watersheds generally handle uneven illumination more robustly by operating on the [image gradient](/page/Image_gradient) rather than raw intensity, which mitigates the impact of lighting variations that often cause thresholding to produce inconsistent regions.[](https://www.researchgate.net/publication/260018901_An_Image_Binarization_Algorithm_Using_Watershed-Based_Local_Thresholding) However, this comes at the cost of higher computational demands, as watershed requires [gradient](/page/Gradient) computation and flooding simulation, whereas thresholding is typically faster but less adaptable to complex scenes.[](https://www.researchgate.net/publication/260018901_An_Image_Binarization_Algorithm_Using_Watershed-Based_Local_Thresholding) Quantitative evaluations highlight these trade-offs, particularly the role of markers in enhancing performance. Marker-controlled watersheds have shown Dice coefficients of 0.964 ± 0.069 in X-ray segmentation tasks, outperforming manual thresholding's 0.937 ± 0.119 by reducing boundary errors in challenging datasets.[](https://www.sciencedirect.com/science/article/abs/pii/S016926071300415X) Benchmarks often report significant over-segmentation in noisy images without markers, underscoring the need for preprocessing to achieve reliable results.[](https://www.sciencedirect.com/science/article/abs/pii/S016926071300415X) Historically, early watershed implementations in the 1980s, such as those by Beucher and Lantuejoul, largely overlooked over-segmentation issues, treating all minima equally and leading to impractical fragmentations in real images.[](https://www.researchgate.net/publication/221661175_The_watershed_concept_and_its_use_in_segmentation_a_brief_history) This prompted innovations in the [1990s](/page/1990s), including Beucher's marker-based refinements and the Vincent-Soille algorithm, which constrained flooding to user-defined or automatic markers to mitigate these flaws and enable practical adoption.[](https://www.researchgate.net/publication/221661175_The_watershed_concept_and_its_use_in_segmentation_a_brief_history) ### Implementation Challenges One of the primary implementation challenges in watershed algorithms is parameter selection, particularly the choice of markers that define initial catchment basins to guide the flooding process and mitigate over-segmentation. Markers can be selected manually for precise control or automated using techniques such as [distance](/page/Distance) transforms from object boundaries or saliency detection to identify foreground and background regions. In marker-controlled variants, improper marker placement—such as insufficient separation between adjacent objects—can lead to merged segments, necessitating iterative refinement or preprocessing steps like morphological operations to generate reliable markers.[](https://docs.opencv.org/4.x/d3/db4/tutorial_py_watershed.html)[](https://scikit-image.org/docs/stable/auto_examples/segmentation/plot_watershed.html) Memory efficiency poses significant hurdles, especially for high-resolution or volumetric [images](/page/Image), where the algorithm's queue-based flooding can require storing extensive topographic maps or [label](/page/Label) arrays. For instance, [processing](/page/Processing) a 1024³ [image](/page/Image) may demand up to 2 TiB of [memory](/page/Memory) in certain implementations due to the need to track [pixel](/page/Pixel) elevations and basin assignments simultaneously. To address this, strategies include hierarchical priority queues that [process](/page/Process) levels incrementally or graph-based reductions that [prune](/page/Prune) redundant nodes before flooding, thereby reducing peak [memory](/page/Memory) usage by 10-20% in optimized libraries.[](https://www.mdpi.com/2313-433X/4/10/123) Parallelization efforts face difficulties in preserving the sequential flooding order inherent to the immersion [simulation](/page/Simulation) model, as concurrent updates to shared basins can introduce race conditions or incorrect merges. GPU adaptations, such as path-reducing watershed variants, mitigate this by decomposing the [image](/page/Image) into independent subgraphs and synchronizing only at boundary pixels, enabling speedups of 10-50x on large datasets while maintaining topological accuracy. However, these require careful load balancing to avoid bottlenecks in plateau regions where multiple paths converge.[](https://arxiv.org/abs/2410.08946)[](https://www.sciencedirect.com/science/article/pii/S0743731525001078) Software tools for watershed implementation are widely available in open-source libraries, facilitating deployment without custom coding from scratch. [OpenCV](/page/OpenCV) provides a marker-based `cv.watershed` function that integrates seamlessly with preprocessing pipelines like distance transforms, supporting both CPU and GPU backends for 2D/3D images. Similarly, scikit-image's `skimage.segmentation.watershed` offers flexibility with masking and compactness parameters, ideal for Python-based workflows, while libraries like ITK and Mahotas extend support for [medical imaging](/page/Medical_imaging) with built-in marker extraction. For custom needs, [pseudocode](/page/Pseudocode) for Meyer's flooding can be adapted as follows:

Initialize with marker pixels sorted by While queue is not empty: Pop pixel with lowest Assign to basin if unlabelled For each unlabelled neighbor: If <= current + threshold, enqueue with updated Else, mark as boundary

This outline highlights the need for robust queue management in code.[](https://docs.opencv.org/4.x/d3/db4/tutorial_py_watershed.html)[](https://scikit-image.org/docs/stable/auto_examples/segmentation/plot_watershed.html)[](https://www.mdpi.com/2313-433X/4/10/123) Debugging common issues requires attention to plateau handling, where flat regions can cause ambiguous flooding paths leading to leaks between basins or, in naive implementations, infinite loops from repeated neighbor enqueuing without progress checks. To resolve, incorporate geodesic distance computations within plateaus to enforce consistent labeling, or use union-find structures to merge adjacent pixels efficiently during [simulation](/page/Simulation). Testing on synthetic images with controlled plateaus helps isolate these, ensuring the algorithm terminates in O(n log n) time.[](https://www.mdpi.com/2313-433X/4/10/123) Performance benchmarks reveal runtime variations across variants and libraries; for example, OpenCV's watershed implementation processes 2D images at 36 ns per element using boundary lines, outperforming scikit-image's 150 ns per element on similar hardware, while optimal spanning forest methods in Mahotas achieve approximately 300 ns per element for large-scale 3D data. These differences stem from language choices (C++ vs. Python) and optimization levels, with GPU-accelerated versions reducing times to under 1.4 seconds for 800-megavoxel volumes.[](https://www.mdpi.com/2313-433X/4/10/123)[](https://www.sciencedirect.com/science/article/pii/S0743731525001078) ### Applications in Image Analysis The watershed algorithm finds extensive application in biomedical imaging, particularly for segmenting cell nuclei in [microscopy](/page/Microscopy) images where objects overlap or touch. Marker-controlled watershed variants are commonly employed to delineate individual nuclei from clustered formations in fluorescence [microscopy](/page/Microscopy), improving accuracy in quantitative analysis of cell populations. For instance, in cervical cytology, multi-pass fast watershed methods have achieved precise segmentation of overlapping cells, enabling automated [diagnosis](/page/Diagnosis).[](https://pubmed.ncbi.nlm.nih.gov/29993863/) Similarly, in vessel extraction from [angiography](/page/Angiography) images, watershed segmentation integrated with multimodal data, such as [magnetic resonance angiography](/page/Magnetic_resonance_angiography) volumes, facilitates the identification of cerebral vascular trees by treating intensity gradients as topographic surfaces, resulting in robust delineation of fine vessel structures with minimal false positives.[](https://www.sciencedirect.com/science/article/abs/pii/S0262885606001764)[](https://www.spiedigitallibrary.org/conference-proceedings-of-spie/3661/0000/Automatic-segmentation-of-blood-vessels-from-MR-angiography-volume-data/10.1117/12.348489.pdf) In [remote sensing](/page/Remote_sensing), watershed segmentation supports [land cover](/page/Land_cover) classification from high-resolution [satellite imagery](/page/Satellite_imagery) by partitioning scenes into homogeneous regions based on spectral and textural features. For urban land-use mapping, watershed applied in vegetation-impervious-soil (V-I-S) feature space effectively separates built-up areas, [vegetation](/page/Vegetation), and bare [soil](/page/Soil), achieving improved classification accuracies over traditional methods on multispectral [data](/page/Data) from sensors like WorldView-2.[](https://www.tandfonline.com/doi/full/10.1080/01431161.2012.665193) Additionally, in geographic information systems (GIS), watershed principles adapted for hydrological modeling delineate catchment boundaries from digital elevation models derived via [remote sensing](/page/Remote_sensing), aiding in flood risk assessment and water resource management distinct from pure [image segmentation](/page/Image_segmentation) tasks. Improved watershed algorithms further extract cultivated land parcels from optical imagery, enhancing [precision agriculture](/page/Precision_agriculture) by isolating field boundaries with reduced oversegmentation.[](https://ieeexplore.ieee.org/document/6048920/)[](https://www.mdpi.com/2072-4292/13/5/939)[](https://agriculture.institute/watershed-mgt-fundamental/remote-sensing-gis-watershed-management/) Industrial inspection leverages watershed for defect detection in material surfaces and particle analysis in manufacturing processes. In surface defect identification, enhanced watershed algorithms segment irregularities on non-flat industrial products, such as cracks or scratches in metals, by combining morphological gradients with marker selection to isolate anomalies with detection rates over 95% on textured backgrounds.[](https://onlinelibrary.wiley.com/doi/10.1155/2021/6630802) For particle analysis, watershed segmentation separates contacting granules in X-ray computed tomography scans of powders used in additive manufacturing, enabling size distribution measurements and quality control with segmentation errors below 5% for overlapping particles. These applications extend to bridge infrastructure monitoring, where watershed delineates defects like corrosion from processed images, supporting non-destructive evaluation.[](https://www.spiedigitallibrary.org/conference-proceedings-of-spie/12779/127791W/Research-on-bridge-defect-detection-technology-based-on-image-processing/10.1117/12.2689360.full)[](https://www.sciencedirect.com/science/article/abs/pii/S003259101930628X) In [video processing](/page/Video_processing), watershed facilitates motion-based segmentation by applying the transform to temporal gradients or [optical flow](/page/Optical_flow) fields across frames. This approach segments moving objects from static backgrounds in MPEG-compressed streams, utilizing watershed on difference images to track regions with coherent motion, achieving real-time performance suitable for [surveillance](/page/Surveillance) with segmentation overlap metrics above 80%. [Optical flow](/page/Optical_flow) integration further refines boundaries in dynamic scenes, enabling robust partitioning of foreground elements in sequences with varying illumination.[](https://link.springer.com/chapter/10.1007/11595755_93)[](https://www.spiedigitallibrary.org/conference-proceedings-of-spie/3846/0000/Video-segmentation-based-on-watershed-algorithm-and-optical-flow-motion/10.1117/12.360455.full) Case studies highlight watershed's practical impact, such as in the International Symposium on Biomedical Imaging (ISBI) cell tracking challenges, where marker-based watershed variants have been pivotal in segmenting dense cell populations, contributing to top-performing entries with [Dice](/page/D.I.C.E.) coefficients of 0.85-0.92 for nucleus detection in [phase-contrast microscopy](/page/Phase-contrast_microscopy). In commercial photo editing, watershed principles underpin selective segmentation tools in software like [Adobe Photoshop](/page/Adobe_Photoshop) for isolating objects in complex scenes, facilitating non-destructive edits in professional workflows.[](https://pubmed.ncbi.nlm.nih.gov/29993863/)[](https://www.nature.com/articles/s41592-023-01879-y)[](https://www.tandfonline.com/doi/abs/10.1080/02533839.2009.9671524) Future trends emphasize integrating watershed with [artificial intelligence](/page/Artificial_intelligence) for end-to-end segmentation pipelines, where [deep learning](/page/Deep_learning) models preprocess images to generate adaptive markers, enhancing watershed's handling of noisy or low-contrast data in biomedical and [remote sensing](/page/Remote_sensing) applications. This hybrid approach, as seen in convolutional neural network-guided watersheds for cellular analysis, boosts overall accuracy by 10-20% in challenging datasets while maintaining computational efficiency. Recent advances as of 2025 include GPU-based parallel partitioning for faster hierarchical segmentation and automatic methods for cancerous lesion detection in histology images.[](https://pmc.ncbi.nlm.nih.gov/articles/PMC8759575/)[](https://link.springer.com/article/10.1007/s10853-023-08901-w)[](https://arxiv.org/abs/2410.08946)[](https://www.mdpi.com/2076-3417/14/22/10394)

This outline highlights the need for robust queue management in code.[](https://docs.opencv.org/4.x/d3/db4/tutorial_py_watershed.html)[](https://scikit-image.org/docs/stable/auto_examples/segmentation/plot_watershed.html)[](https://www.mdpi.com/2313-433X/4/10/123) Debugging common issues requires attention to plateau handling, where flat regions can cause ambiguous flooding paths leading to leaks between basins or, in naive implementations, infinite loops from repeated neighbor enqueuing without progress checks. To resolve, incorporate geodesic distance computations within plateaus to enforce consistent labeling, or use union-find structures to merge adjacent pixels efficiently during [simulation](/page/Simulation). Testing on synthetic images with controlled plateaus helps isolate these, ensuring the algorithm terminates in O(n log n) time.[](https://www.mdpi.com/2313-433X/4/10/123) Performance benchmarks reveal runtime variations across variants and libraries; for example, OpenCV's watershed implementation processes 2D images at 36 ns per element using boundary lines, outperforming scikit-image's 150 ns per element on similar hardware, while optimal spanning forest methods in Mahotas achieve approximately 300 ns per element for large-scale 3D data. These differences stem from language choices (C++ vs. Python) and optimization levels, with GPU-accelerated versions reducing times to under 1.4 seconds for 800-megavoxel volumes.[](https://www.mdpi.com/2313-433X/4/10/123)[](https://www.sciencedirect.com/science/article/pii/S0743731525001078) ### Applications in Image Analysis The watershed algorithm finds extensive application in biomedical imaging, particularly for segmenting cell nuclei in [microscopy](/page/Microscopy) images where objects overlap or touch. Marker-controlled watershed variants are commonly employed to delineate individual nuclei from clustered formations in fluorescence [microscopy](/page/Microscopy), improving accuracy in quantitative analysis of cell populations. For instance, in cervical cytology, multi-pass fast watershed methods have achieved precise segmentation of overlapping cells, enabling automated [diagnosis](/page/Diagnosis).[](https://pubmed.ncbi.nlm.nih.gov/29993863/) Similarly, in vessel extraction from [angiography](/page/Angiography) images, watershed segmentation integrated with multimodal data, such as [magnetic resonance angiography](/page/Magnetic_resonance_angiography) volumes, facilitates the identification of cerebral vascular trees by treating intensity gradients as topographic surfaces, resulting in robust delineation of fine vessel structures with minimal false positives.[](https://www.sciencedirect.com/science/article/abs/pii/S0262885606001764)[](https://www.spiedigitallibrary.org/conference-proceedings-of-spie/3661/0000/Automatic-segmentation-of-blood-vessels-from-MR-angiography-volume-data/10.1117/12.348489.pdf) In [remote sensing](/page/Remote_sensing), watershed segmentation supports [land cover](/page/Land_cover) classification from high-resolution [satellite imagery](/page/Satellite_imagery) by partitioning scenes into homogeneous regions based on spectral and textural features. For urban land-use mapping, watershed applied in vegetation-impervious-soil (V-I-S) feature space effectively separates built-up areas, [vegetation](/page/Vegetation), and bare [soil](/page/Soil), achieving improved classification accuracies over traditional methods on multispectral [data](/page/Data) from sensors like WorldView-2.[](https://www.tandfonline.com/doi/full/10.1080/01431161.2012.665193) Additionally, in geographic information systems (GIS), watershed principles adapted for hydrological modeling delineate catchment boundaries from digital elevation models derived via [remote sensing](/page/Remote_sensing), aiding in flood risk assessment and water resource management distinct from pure [image segmentation](/page/Image_segmentation) tasks. Improved watershed algorithms further extract cultivated land parcels from optical imagery, enhancing [precision agriculture](/page/Precision_agriculture) by isolating field boundaries with reduced oversegmentation.[](https://ieeexplore.ieee.org/document/6048920/)[](https://www.mdpi.com/2072-4292/13/5/939)[](https://agriculture.institute/watershed-mgt-fundamental/remote-sensing-gis-watershed-management/) Industrial inspection leverages watershed for defect detection in material surfaces and particle analysis in manufacturing processes. In surface defect identification, enhanced watershed algorithms segment irregularities on non-flat industrial products, such as cracks or scratches in metals, by combining morphological gradients with marker selection to isolate anomalies with detection rates over 95% on textured backgrounds.[](https://onlinelibrary.wiley.com/doi/10.1155/2021/6630802) For particle analysis, watershed segmentation separates contacting granules in X-ray computed tomography scans of powders used in additive manufacturing, enabling size distribution measurements and quality control with segmentation errors below 5% for overlapping particles. These applications extend to bridge infrastructure monitoring, where watershed delineates defects like corrosion from processed images, supporting non-destructive evaluation.[](https://www.spiedigitallibrary.org/conference-proceedings-of-spie/12779/127791W/Research-on-bridge-defect-detection-technology-based-on-image-processing/10.1117/12.2689360.full)[](https://www.sciencedirect.com/science/article/abs/pii/S003259101930628X) In [video processing](/page/Video_processing), watershed facilitates motion-based segmentation by applying the transform to temporal gradients or [optical flow](/page/Optical_flow) fields across frames. This approach segments moving objects from static backgrounds in MPEG-compressed streams, utilizing watershed on difference images to track regions with coherent motion, achieving real-time performance suitable for [surveillance](/page/Surveillance) with segmentation overlap metrics above 80%. [Optical flow](/page/Optical_flow) integration further refines boundaries in dynamic scenes, enabling robust partitioning of foreground elements in sequences with varying illumination.[](https://link.springer.com/chapter/10.1007/11595755_93)[](https://www.spiedigitallibrary.org/conference-proceedings-of-spie/3846/0000/Video-segmentation-based-on-watershed-algorithm-and-optical-flow-motion/10.1117/12.360455.full) Case studies highlight watershed's practical impact, such as in the International Symposium on Biomedical Imaging (ISBI) cell tracking challenges, where marker-based watershed variants have been pivotal in segmenting dense cell populations, contributing to top-performing entries with [Dice](/page/D.I.C.E.) coefficients of 0.85-0.92 for nucleus detection in [phase-contrast microscopy](/page/Phase-contrast_microscopy). In commercial photo editing, watershed principles underpin selective segmentation tools in software like [Adobe Photoshop](/page/Adobe_Photoshop) for isolating objects in complex scenes, facilitating non-destructive edits in professional workflows.[](https://pubmed.ncbi.nlm.nih.gov/29993863/)[](https://www.nature.com/articles/s41592-023-01879-y)[](https://www.tandfonline.com/doi/abs/10.1080/02533839.2009.9671524) Future trends emphasize integrating watershed with [artificial intelligence](/page/Artificial_intelligence) for end-to-end segmentation pipelines, where [deep learning](/page/Deep_learning) models preprocess images to generate adaptive markers, enhancing watershed's handling of noisy or low-contrast data in biomedical and [remote sensing](/page/Remote_sensing) applications. This hybrid approach, as seen in convolutional neural network-guided watersheds for cellular analysis, boosts overall accuracy by 10-20% in challenging datasets while maintaining computational efficiency. Recent advances as of 2025 include GPU-based parallel partitioning for faster hierarchical segmentation and automatic methods for cancerous lesion detection in histology images.[](https://pmc.ncbi.nlm.nih.gov/articles/PMC8759575/)[](https://link.springer.com/article/10.1007/s10853-023-08901-w)[](https://arxiv.org/abs/2410.08946)[](https://www.mdpi.com/2076-3417/14/22/10394)

Add your contribution
Related Hubs
User Avatar
No comments yet.