{
 "id": "epmdzt5knq",
 "slug": "watershed-algorithm",
 "title": "Watershed algorithm",
 "updated": "2026-10-25",
 "topic_path": [
  {
   "id": "technology",
   "label": "Technology and the built world",
   "api_url": "https://www.edgepedia.org/api/v1/topics/technology"
  },
  {
   "id": "technology.computing",
   "label": "Computing and digital systems",
   "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing"
  },
  {
   "id": "technology.computing.ai",
   "label": "Artificial intelligence and data",
   "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai"
  },
  {
   "id": "technology.computing.ai.perception_language",
   "label": "Language and vision AI",
   "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.perception_language"
  },
  {
   "id": "technology.computing.ai.computer_vision",
   "label": "Computer vision",
   "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.computer_vision"
  },
  {
   "id": "technology.computing.ai.cv_methods",
   "label": "Vision methods and geometry",
   "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.cv_methods"
  },
  {
   "id": "technology.computing.ai.cv_methods.low_level_analysis",
   "label": "Low-level image analysis",
   "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.cv_methods.low_level_analysis"
  }
 ],
 "geo": [
  {
   "id": "geo.nongeo.t1946.technology.computing.ai.perception_language",
   "label": "Non-geographic · 1946 to 2000: Language and vision AI",
   "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.perception_language",
   "path": [
    {
     "id": "geo.nongeo",
     "label": "Non-geographic",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo"
    },
    {
     "id": "geo.nongeo.t1946",
     "label": "Non-geographic · 1946 to 2000",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946"
    },
    {
     "id": "geo.nongeo.t1946.technology",
     "label": "Technology and the built world",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology"
    },
    {
     "id": "geo.nongeo.t1946.technology.computing",
     "label": "Computing and digital systems",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing"
    },
    {
     "id": "geo.nongeo.t1946.technology.computing.ai",
     "label": "Artificial intelligence and data",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai"
    },
    {
     "id": "geo.nongeo.t1946.technology.computing.ai.perception_language",
     "label": "Language and vision AI",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.perception_language"
    }
   ]
  }
 ],
 "excerpt": "The watershed algorithm is an image-segmentation method from mathematical morphology that treats pixel intensities as terrain elevation, flooding catchment basins from seed points to separate touching objects.",
 "snippet": "The watershed algorithm is an image-segmentation method from mathematical morphology that treats pixel intensities as terrain elevation, flooding catchment basins from seed points to separate touching objects.",
 "node": "technology.computing.ai.cv_methods.low_level_analysis",
 "markdown": "# Watershed algorithm\n\nThe watershed algorithm is an image-segmentation method from mathematical morphology that treats pixel intensities as the elevation of a topographic relief and partitions the image into catchment basins separated by watershed lines, by flooding the relief from seed points.<sup>[1](https://scikit-image.org/docs/stable/auto_examples/segmentation/plot_watershed.html)</sup> In practice it is applied to a gradient image.<sup>[2](https://pure.rug.nl/ws/files/127130790/parwshed.pdf)</sup> The method produces closed contours without thresholds or parametric edge fitting, and it remains a standard tool for separating touching objects in biological, medical, and materials imaging.<sup>[3](https://people.cmm.minesparis.psl.eu/users/beucher/publi/watershed.pdf)</sup>\n\n| Key fact | Value or statement | Source |\n|---|---|---|\n| Output | A labeled partition into catchment basins; pixels where basins of different markers meet form the watershed lines | <sup>[1](https://scikit-image.org/docs/stable/auto_examples/segmentation/plot_watershed.html)</sup> |\n| Defining analogy | A catchment basin is the set of points from which a drop of water flows to a given minimum; shared points of overlapping basins form the watersheds | <sup>[3](https://people.cmm.minesparis.psl.eu/users/beucher/publi/watershed.pdf)</sup> |\n| Complexity of flooding algorithms | \\( O(N) \\) in the number of image elements when using hierarchical queues, yet runtimes differ by orders of magnitude across implementations | <sup>[4](https://www.mdpi.com/2313-433X/8/5/127)</sup> |\n| Over-segmentation | Flooding from all regional minima of the gradient yields far too many basins; markers are the standard remedy | <sup>[5](https://perso.telecom-paristech.fr/bloch/ANIM/CorpsCalleux/Meyer1994.pdf)</sup> |\n| Graph formulation | Watershed cuts on edge-weighted graphs coincide with minimum-spanning-forest cuts, linking the method to Kruskal's algorithm | <sup>[6](https://doi.org/10.1109/tpami.2008.173)</sup> |\n| Application fields | Remote sensing, medical imaging, biological imaging, and material science | <sup>[7](https://link.springer.com/article/10.1007/s10851-026-01347-0)</sup> |\n\n## How it works\n\nThe image is read as a relief.<sup>[3](https://people.cmm.minesparis.psl.eu/users/beucher/publi/watershed.pdf)</sup> The drop-of-water definition attaches to each minimum the set of all points whose descending paths reach it; where basins of several minima overlap, their common points form the watershed lines.<sup>[3](https://people.cmm.minesparis.psl.eu/users/beucher/publi/watershed.pdf)</sup> The equivalent flooding picture places a source at every regional minimum, lets all floods rise at uniform speed, and erects a dam wherever two floods meet; the union of the dams is the watershed line.<sup>[5](https://perso.telecom-paristech.fr/bloch/ANIM/CorpsCalleux/Meyer1994.pdf)</sup>\n\nFormally, the flooding can be written with threshold sets: starting from the minimum-level set \\( X_{h_{\\min}} \\), each step unions the next threshold with the influence zone of the previous set, \\( X_{h+1} = \\min_{h+1} \\cup \\, \\mathrm{IZ}_{T_{h+1}}(X_h) \\); a pixel adjacent to two different basins is marked as a watershed node.<sup>[2](https://pure.rug.nl/ws/files/127130790/parwshed.pdf)</sup> Meyer gave a rigorous definition using the topographic distance, the length of the steepest descending path weighted by the lower slope; the catchment basin of a minimum is the set of points closer to it than to any other minimum under this distance, which yields Dijkstra-type shortest-path algorithms.<sup>[5](https://perso.telecom-paristech.fr/bloch/ANIM/CorpsCalleux/Meyer1994.pdf)</sup>\n\n## How it is done\n\nA typical marker-controlled pipeline runs as follows. First, compute a gradient (commonly the morphological gradient) so that object boundaries appear as ridges.<sup>[2](https://pure.rug.nl/ws/files/127130790/parwshed.pdf)</sup> Second, select markers: one inside each object and one for the background.<sup>[5](https://perso.telecom-paristech.fr/bloch/ANIM/CorpsCalleux/Meyer1994.pdf)</sup> Third, modify the relief so that its only minima are the markers, by replacing the gradient \\( g \\) with a reconstruction \\( g' \\) in which marker pixels are set to 0; after this homotopy modification any watershed algorithm can be applied.<sup>[5](https://perso.telecom-paristech.fr/bloch/ANIM/CorpsCalleux/Meyer1994.pdf)</sup> Fourth, flood: the immersion algorithm sorts pixels by increasing gray value and floods plateaus through a FIFO queue,<sup>[8](https://doi.org/10.1109/34.87344)</sup> while distance-based versions use hierarchical or priority queues; scikit-image's queue orders by pixel value and then entry time, settling ties in favor of the closest marker.<sup>[9](https://github.com/scikit-image/scikit-image/blob/v0.17.2/skimage/segmentation/_watershed.py)</sup> In OpenCV the user labels sure foreground with positive integers, sure background with another label, and unknown areas with 0; after `cv.watershed` the boundary pixels are marked with -1.<sup>[10](https://docs.opencv.org/5.0/py_tutorials/py_imgproc/py_watershed/py_watershed.html)</sup>\n\nFlooding-based implementations commonly achieve computational complexity \\( O(N) \\), where \\( N \\) is the number of image elements, when using hierarchical queues, although priority-queue variants operate in \\( O(N \\log N) \\) time,<sup>[19](https://richard.science/sci/2014_depressions.pdf)</sup> but processing speed depends strongly on data structures, language, and optimization; published benchmarks of marker-controlled implementations on volumetric images found execution-time differences of several orders of magnitude.<sup>[4](https://www.mdpi.com/2313-433X/8/5/127)</sup> The Vincent–Soille immersion algorithm runs in time linear in the number of pixels.<sup>[2](https://pure.rug.nl/ws/files/127130790/parwshed.pdf)</sup>\n\n## Origin\n\nA workshop paper from the Centre de Géostatistique et de Morphologie Mathématique in [Fontainebleau](https://www.edgepedia.org/fontainebleau) defines contours as the watersheds of the gradient modulus of the gray function and presents the method as non-parametric, requiring no threshold and producing closed contours; its two examples are bubble detection in a radiographic plate and facet detection in steel fractures.<sup>[3](https://people.cmm.minesparis.psl.eu/users/beucher/publi/watershed.pdf)</sup> Published accounts differ on where the transformation itself begins: Vincent and Soille's 1991 paper states that the watershed transformation as a morphological tool is due to H. Digabel and Ch. Lantuéjoul, whose data were piles of binary images representing successive thresholds of a bituminous surface's relief, with the grayscale extension credited to Beucher and Lantuéjoul,<sup>[8](https://doi.org/10.1109/34.87344)</sup> while Meyer's historical account treats the 1979 paper as the origin of the watershed notion for segmentation.<sup>[5](https://perso.telecom-paristech.fr/bloch/ANIM/CorpsCalleux/Meyer1994.pdf)</sup> Both attributions are reported here without adjudication. The efficient immersion-simulation algorithm of L. Vincent and P. Soille, published in 1991 in [IEEE Transactions on Pattern Analysis and Machine Intelligence](https://www.edgepedia.org/ieee-transactions-on-pattern-analysis-and-machine-intelligence), made the transform practical on ordinary computers,<sup>[8](https://doi.org/10.1109/34.87344)</sup> and reviews date the algorithmic immersion definition to that paper.<sup>[11](https://sci2s.ugr.es/sites/default/files/ficherosPublicaciones/2344_10.1007-978-3-319-62359-7_12.pdf)</sup> Fernand Meyer's 1994 paper in Signal Processing supplied the topographic-distance definition,<sup>[5](https://perso.telecom-paristech.fr/bloch/ANIM/CorpsCalleux/Meyer1994.pdf)</sup> and Laurent Najman and Michel Schmitt's 1994 Signal Processing paper extended the definition to the continuous plane and proved the convergence of the Beucher–Lantuéjoul construction.<sup>[12](https://doi.org/10.1016/0165-1684%2894%2990059-0)</sup>\n\n## Variants\n\n**Marker-based versus unseeded.** Flooding from all regional minima produces severe over-segmentation because spurious minima are numerous; the marker strategy floods only from selected sources and became the dominant morphological segmentation paradigm.<sup>[5](https://perso.telecom-paristech.fr/bloch/ANIM/CorpsCalleux/Meyer1994.pdf)</sup> Unseeded watershed on a noisy gradient gives oversegmented results.<sup>[10](https://docs.opencv.org/5.0/py_tutorials/py_imgproc/py_watershed/py_watershed.html)</sup>\n\n**Algorithm families.** Shortest-path algorithms build zones of influence for various distance functions; thinning-based algorithms iteratively lower pixels until a watershed remains. The topological watershed is defined through W-destructible points: a W-thinning lowers such points by one until none remain, and the pass value between two points is the minimum over all paths of the maximum value along the path.<sup>[13](https://perso.esiee.fr/~dpt-it/tw/ismm05ncb.pdf)</sup>\n\n**Watershed cuts.** On edge-weighted graphs, the watershed cut is the set of edges linking two distinct basins.<sup>[14](https://minesparis-psl.hal.science/hal-01111752/document)</sup> J. Cousty, G. Bertrand, L. Najman, and M. Couprie proved two central results in their 2009 IEEE Transactions on Pattern Analysis and Machine Intelligence paper: a cut is a watershed cut if and only if every point has a steepest-descent path to a minimum (the drop-of-water principle), and a set of edges is a watershed cut if and only if it is a minimum-spanning-forest cut for the minima; a border-thinning transformation computes such cuts in linear time without sorting, whatever the range of the input map.<sup>[6](https://doi.org/10.1109/tpami.2008.173)</sup> The MST equivalence connects the method to [Kruskal's algorithm](https://www.edgepedia.org/kruskals-algorithm) and supports marker-based and hierarchical computations.<sup>[7](https://link.springer.com/article/10.1007/s10851-026-01347-0)</sup>\n\n**Hierarchical watershed and waterfall.** The waterfall applies a watershed transform to a graph of basins, mainly to cope with over-segmentation in non-supervised segmentation; it is non-parametric but inherits defects from the underlying transform.<sup>[15](https://people.cmm.minesparis.psl.eu/users/beucher/publi/P-Algorithm_SB_BM.pdf)</sup> In hierarchical watersheds generally, minima are ordered by extinction values such as area or volume, obtainable in linear time from the Binary Partition Tree by Altitude Ordering.<sup>[7](https://link.springer.com/article/10.1007/s10851-026-01347-0)</sup>\n\n## Applications\n\nThe classic use is separating touching or overlapping objects for [instance segmentation](https://www.edgepedia.org/instance-segmentation), typically by combining a [distance transform](https://www.edgepedia.org/distance-transform) with watershed.<sup>[10](https://docs.opencv.org/5.0/py_tutorials/py_imgproc/py_watershed/py_watershed.html)</sup> In cell and nucleus counting, deep-learning-enhanced marker-controlled watershed is described as a popular recent method for automatic 3D nuclei segmentation, in which CNNs create nuclei masks and markers, an H-minima transform of depth \\( h \\) suppresses weak local minima in the distance transform to reduce over-segmentation, and the watershed performs the instance segmentation.<sup>[16](https://pmc.ncbi.nlm.nih.gov/articles/PMC9306214/)</sup> Documented application areas include remote sensing, medical imaging, biological imaging, and material science,<sup>[7](https://link.springer.com/article/10.1007/s10851-026-01347-0)</sup> plus pore-network extraction from 3D X-ray CT, chromosome karyotyping, retinal melanin granule segmentation in OCT, and live-cell fluorescence microscopy.<sup>[4](https://www.mdpi.com/2313-433X/8/5/127)</sup>\n\n## Limitations and alternatives\n\n**Over-segmentation** is the principal failure mode: computing watersheds of the raw gradient mostly results in the correct contours being lost in a mass of irrelevant ones,<sup>[8](https://doi.org/10.1109/34.87344)</sup> because many local minima produce many small basins; markers and hierarchical watersheds are the standard remedies.<sup>[2](https://pure.rug.nl/ws/files/127130790/parwshed.pdf)</sup> **Sequential-flooding bias** is a second one: processing queued pixels at the same level in order introduces deformations that can grow to arbitrary size and makes the watershed line non-unique.<sup>[17](https://www.ipol.im/pub/art/2022/215/article.pdf)</sup> **Line placement precision** depends on neighborhood size: larger chamfer neighborhoods place lines more precisely, and under Matheron's tough test model with quasi-parallel watershed lines most first-neighbor algorithms fail except the chamfer algorithms.<sup>[5](https://perso.telecom-paristech.fr/bloch/ANIM/CorpsCalleux/Meyer1994.pdf)</sup> Among learned alternatives, the Deep Watershed Transform trains a network to predict the watershed energy itself, so that each basin corresponds to a single instance and all dividing ridges sit at the same height, allowing instance extraction by a single-level cut with constant runtime regardless of the number of instances.<sup>[18](https://openaccess.thecvf.com/content_cvpr_2017/papers/Bai_Deep_Watershed_Transform_CVPR_2017_paper.pdf)</sup>\n\n## References\n\n1. [Watershed segmentation, skimage documentation](https://scikit-image.org/docs/stable/auto_examples/segmentation/plot_watershed.html)\n2. [The Watershed Transform: Definitions, Algorithms and Parallelization Strategies (Roerdink & Meijster, Fundamenta Informaticae)](https://pure.rug.nl/ws/files/127130790/parwshed.pdf)\n3. [Use of Watersheds in Contour Detection (Beucher & Lantuéjoul, 1979)](https://people.cmm.minesparis.psl.eu/users/beucher/publi/watershed.pdf)\n4. [A Review of Watershed Implementations for Segmentation of Volumetric Images (J. Imaging, MDPI)](https://www.mdpi.com/2313-433X/8/5/127)\n5. [Topographic distance and watershed lines (F. Meyer, Signal Processing 38, 1994, 113-125)](https://perso.telecom-paristech.fr/bloch/ANIM/CorpsCalleux/Meyer1994.pdf)\n6. [J. Cousty and colleagues (2009). Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle. IEEE Transactions on Pattern Analysis and Machine Intelligence.](https://doi.org/10.1109/tpami.2008.173)\n7. [Playing with Kruskal: A State-of-the-Art Report on Watershed Cuts (J. Mathematical Imaging and Vision)](https://link.springer.com/article/10.1007/s10851-026-01347-0)\n8. [L. Vincent, P. Soille (1991). Watersheds in digital spaces: an efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysis and Machine Intelligence.](https://doi.org/10.1109/34.87344)\n9. [skimage/segmentation/_watershed.py source](https://github.com/scikit-image/scikit-image/blob/v0.17.2/skimage/segmentation/_watershed.py)\n10. [Image Segmentation with Watershed Algorithm, OpenCV Tutorials](https://docs.opencv.org/5.0/py_tutorials/py_imgproc/py_watershed/py_watershed.html)\n11. [An Updated Review on Watershed Algorithms (Springer book chapter)](https://sci2s.ugr.es/sites/default/files/ficherosPublicaciones/2344_10.1007-978-3-319-62359-7_12.pdf)\n12. [Watershed of a continuous function (Signal Processing, 1994)](https://doi.org/10.1016/0165-1684%2894%2990059-0)\n13. [Watersheds and Mosaic Images (Couprie & Bertrand, ISMM 2005)](https://perso.esiee.fr/~dpt-it/tw/ismm05ncb.pdf)\n14. [Watersheds on weighted graphs (F. Meyer)](https://minesparis-psl.hal.science/hal-01111752/document)\n15. [Waterfall algorithm paper (Beucher and Meyer, CMM)](https://people.cmm.minesparis.psl.eu/users/beucher/publi/P-Algorithm_SB_BM.pdf)\n16. [Marker-controlled watershed with deep edge emphasis and optimized H-minima transform for automatic segmentation of densely cultivated 3D cell nuclei](https://pmc.ncbi.nlm.nih.gov/articles/PMC9306214/)\n17. [A Parallel, O(n) Algorithm for an Unbiased, Thin Watershed (IPOL 2022)](https://www.ipol.im/pub/art/2022/215/article.pdf)\n18. [Deep Watershed Transform for Instance Segmentation (CVPR 2017)](https://openaccess.thecvf.com/content_cvpr_2017/papers/Bai_Deep_Watershed_Transform_CVPR_2017_paper.pdf)\n19. [2014 depressions (richard.science)](https://richard.science/sci/2014_depressions.pdf)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Language and vision AI › Computer vision › Vision methods and geometry › Low-level image analysis*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Sep 30, 2026; Oct 25, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n",
 "same_as": [],
 "url": "https://www.edgepedia.org/watershed-algorithm",
 "markdown_url": "https://www.edgepedia.org/watershed-algorithm.md",
 "license": {
  "name": "Edgepedia Community License 1.0",
  "url": "https://www.edgepedia.org/edgepedia/license",
  "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.",
  "spdx": "LicenseRef-Edgepedia-Community-1.0"
 },
 "credit": "\"Watershed algorithm\", Edgepedia (EdgeChat), https://www.edgepedia.org/watershed-algorithm. Edgepedia Community License 1.0.",
 "credit_md": "\"[Watershed algorithm](https://www.edgepedia.org/watershed-algorithm)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/watershed-algorithm](https://www.edgepedia.org/watershed-algorithm). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).",
 "credit_html": "\"<a href=\"https://www.edgepedia.org/watershed-algorithm\">Watershed algorithm</a>\", Edgepedia (EdgeChat), <a href=\"https://www.edgepedia.org/watershed-algorithm\">https://www.edgepedia.org/watershed-algorithm</a>. <a href=\"https://www.edgepedia.org/edgepedia/license\">Edgepedia Community License 1.0</a>.",
 "speakable": "The watershed algorithm is an image-segmentation method from mathematical morphology that treats pixel intensities as terrain elevation, flooding catchment basins from seed points to separate touching objects."
}