Playing with Kruskal: algorithms for flat and hierarchical watershed cuts

1 Introduction

• Watersheds partition images or weighted graphs into catchment basins, while hierarchical watersheds produce nested partitions by progressively merging regions.For edge-weighted graphs, watershed cuts are closely related to minimum spanning trees.Source: §1 · pp. 1–2
• The article reviews flat, hierarchical, supervised, and unsupervised watershed definitions for edge-weighted graphs.It positions watershed cuts within broader connections to combinatorial optimization and computational geometry.Source: §1 · p. 2
• A Kruskal-inspired framework uses the Binary Partition Tree by Altitude Ordering (BPTAO) to compute watershed variants through a modular pipeline.The pipeline covers graph construction, tree computation, seed selection, and cut extraction.Source: §1 · p. 2
• The BPTAO encodes minimum-spanning-tree structure, supports seed propagation, and enables direct extraction of segmentation boundaries or hierarchical saliency maps.The framework aims to provide a reference for researchers and practitioners and to facilitate implementation.Source: §1 · p. 2

2 Related work

• Watershed segmentation has developed through multiple algorithms and paradigms, with applications across remote sensing, medical, biological, and materials imaging.The review selects methods and related concepts rather than attempting an exhaustive survey.Source: §2 · p. 2

2.1 Early flooding-based methods on vertex-weighted graphs

• Early flooding methods mark seed pixels, then iteratively add unmarked neighbors in increasing weight order to label catchment basins and sometimes watershed divides.These approaches use vertex-weighted graphs, with pixels as vertices and pixel adjacency defining edges.Source: §2.1 · pp. 2–3

2.2 Hierarchical and stochastic watersheds

• Hierarchical watersheds organize regions into nested scales, while stochastic watersheds combine random-marker segmentations so persistent contours gain probability density.Geodesic saliency ranks contours by persistence across scales; stochastic methods aim to reduce oversegmentation as small, low-contrast contours fade.Source: §2.2 · p. 3

2.3 Edge-weighted graphs and combinatorial optimization

• Edge-weighted graphs encode pixel dissimilarities and connect segmentation to optimization methods including minimum spanning trees, min-cut/max-flow, and shortest-path forests.The review describes Felzenszwalb and Huttenlocher’s graph-based clustering as closely related to the MST problem.Source: §2.3 · p. 3

2.4 Watershed cuts and unifying frameworks

• Watershed cuts in edge-weighted graphs have equivalent catchment-basin and dividing-line characterizations and are closely related to MSTs.Related optimization links include power watersheds, which use a secondary optimality criterion to discriminate ties.Source: §2.4 · pp. 3–4

2.5 Extension, learning and large-scale processing

• Extensions include seed-free Mutex Watersheds, feature-subset ensembles, interactive and out-of-core methods, and learning-based markers or hierarchical contours.Watersheds also remain in use alongside machine learning as pre- or post-processing; reported examples include hyperspectral segmentation and interactive updates without full recomputation.Source: §2.5 · p. 4

2.6 Beyond images: surfaces, geometry, and terrains

• Watershed-like surface partitioning connects image analysis to ascending, descending, and Morse-Smale complexes, and to terrain applications such as digital elevation models.Ascending complexes are analogous to catchment basins, while descending complexes delineate regions through thalwegs.Source: §2.6 · pp. 4–5

2.7 Implementations

• Watershed algorithms are implemented in open-source and commercial or domain-specific platforms, and the review points readers to broader implementation surveys.The article uses the Higra hierarchical graph analysis library for its illustrations.Source: §2.7 · p. 5

3 Watershed cuts and hierarchies

• Basic cuts are unsupervised, seeded cuts use supplied markers, and hierarchical cuts progressively merge fine-scale regions into higher-scale regions.Hierarchical cuts may be unsupervised or semi-supervised.Source: §3 · p. 5

3.1 Watershed cuts

• A watershed cut partitions the graph so each region contains one regional minimum and every cut edge satisfies the drop-of-water principle.For image graphs, vertices represent pixels or voxels, adjacent pixels are linked, and edge weights measure dissimilarity.Source: §3.1 · p. 6
• A cut is a watershed cut exactly when it is the component partition of a minimum spanning forest rooted at the graph’s minima.Each forest component contains one minimum, and the forest has minimum total edge weight among subgraphs satisfying the stated conditions.Source: §3.1 · p. 7

3.2 Seeded watershed cuts

• Seeded cuts modify the weights by digging marker edges and applying closing by reconstruction, which removes undesired minima while preserving the markers.The resulting cut contains exactly one region for each marker.Source: §3.2 · p. 7
• A minimum spanning forest of the original graph rooted in the markers directly yields a seeded watershed cut.This provides an alternative to explicitly filtering the graph before computing the cut.Source: §3.2 · p. 7

3.3 Hierarchical watershed cuts

• A hierarchical watershed combines cuts of progressively filtered graphs, requiring nested partitions and extensive connected operators that remove minima according to a measure and scale.The filtration can be constructed from threshold components, removing those below a measure threshold and stacking the remaining components into a filtered map.Source: §3.3 · p. 8
• Multi-scale optimality characterizes hierarchical watersheds through minimum spanning forests rooted at minima whose extinction values meet each scale threshold.The converse holds when the filtration removes one minimum between every pair of successive levels; the result also implies that successive filtrations need not be computed if extinction values and nested forests are available.Source: §3.3 · p. 9

3.4 Watershed cuts from a hierarchy

• A seeded hierarchical cut is obtained by computing a hierarchical watershed, converting it to a saliency map, then taking a watershed cut of that map using the markers.The saliency weight records the highest scale at which an edge’s endpoints remain in distinct regions, so thresholding recovers cuts in the hierarchy.Source: §3.4 · p. 10

4 Algorithmic scheme overview

• The pipeline represents the input image as an edge-weighted graph, commonly using pixels as vertices and 4- or 8-connected pixel adjacencies as edges.The resulting graph is the input to BPTAO construction.Source: §4 · p. 10
• A BPTAO is constructed by incrementally merging regions along graph edges in a total order until one region remains.Its leaves correspond to graph vertices, while its nodes represent connected components formed during Kruskal’s minimum-spanning-tree algorithm.Source: §4 · p. 10
• Seed or marker selection determines whether the resulting watershed segmentation is flat or hierarchical and how many regions it contains.Options include regional minima and user-provided seeds, with supervised or unsupervised methods available.Source: §4 · p. 11
• For a flat watershed, watershed-cut edges are identified in one BPTAO pass from leaves to root; hierarchical watersheds also require edge saliencies.Weighted or ordered markers determine the levels at which connected regions are merged.Source: §4 · p. 11
• After watershed nodes and any required saliencies are computed, the pipeline constructs the segmentation’s connected components; flat contours can be obtained with one pass over the edges.For the hierarchical case, the MST saliency map can be computed in time linear in the number of edges.Source: §4 · p. 11

5 Building a Binary Partition Tree

• Kruskal’s algorithm processes edges in increasing weight order, adding an edge to the MST and merging its endpoint regions when they are distinct.It stops when all vertices have merged into one region.Source: §5 · p. 13
• Recording each merge as a parent-child relation makes the BPTAO equal to the sequence of increasingly coarser graph partitions.The tree preserves merge history separately because path compression and rank optimization in union-find collapse region-merging sequences.Source: §5 · p. 13
• The modified Kruskal algorithm initializes each graph vertex as a singleton and creates a new tree node whenever an accepted MST edge merges two regions.The new node becomes the parent of the subtrees associated with the merged regions.Source: §5 · p. 14
• After BPTAO construction, the paper’s remaining algorithms use a fixed number of passes and run in time linear in the input tree’s number of nodes.The construction itself takes O(|E|α(|V|)) plus edge sorting, which is O(|E| log(|E|)) generally or O(|E|) when linear sorting is possible.Source: §5 · p. 14
• The BPTAO uses leaves for graph vertices and internal nodes for MST edges, with each internal node’s altitude given by its associated edge weight.Its nodes are arranged in topological order from leaves to root, enabling simple tree traversal.Source: §5 · pp. 14–15

6.1 Seeds for non-hierarchical watershed cuts

• Regional minima provide a watershed-consistent choice of seeds, while user scribbles and supervised methods offer other ways to guide seed placement.User scribbles can become cumbersome as image size and complexity increase; supervised approaches include predicting user inputs or generating seeds from learned contours.Source: §6.1 · pp. 15–16
• The minima algorithm traverses the BPTAO bottom-up, counting minima in each subtree and marking a node when its subtree has none and its altitude differs from its parent’s.MinimaOneLeaf then propagates each minimum’s status to one leaf, selecting a single representative leaf for each minimum.Source: §6.1 · pp. 15–16

6.2 Weighted seeds for hierarchical watershed cuts

• Weighted seeds order regions by importance and produce nested segmentations from a single region to a level where each seed has its own region.The stated motivation is that regions of interest may occur at multiple segmentation levels, with post-processing often needed to filter spurious noise.Source: §6.2 · p. 16
• Extinction values order regional minima using attributes such as area, volume, or depth computed on BPTAO nodes and propagated toward leaves.The attributes represent properties of catchment basins, including area, volume, and dynamics.Source: §6.2 · p. 16
• Before extinction values are computed, equal-altitude parent-child nodes are treated as tree artifacts by replacing a node’s attribute with the maximum of its children’s values.The attribute-based extinction computation is linear in |V|.Source: §6.2 · pp. 16–17
• Weighted seeds are formed by assigning each seeded minimum its extinction value and giving unseeded vertices null weight.The binary minima seeds are first extracted using the minima and one-leaf algorithms.Source: §6.2 · p. 17

7.1 Watershed-cut from seeds

• A watershed-cut edge is identified when both children of its BPTAO node contain at least one seed.The algorithm first propagates seed presence from leaves toward the root, then marks qualifying MST edges in a second pass.Source: §7.1 · p. 17
• Seeding one vertex in each regional minimum yields the usual unsupervised watershed cut of the graph.The illustrated graph has three minima; the resulting watershed nodes correspond to MST edges {b, c} and {d, h}.Source: §7.1 · p. 17, Figure 7 · p. 18

7.2 Hierarchical watershed cuts from weighted seeds

• Ordering seeds by importance gives nested segmentations rooted in subsets of the most important seeds.In edge-weighted graphs, minimum spanning forests rooted at each such subset define a sequence satisfying the causality principle.Source: §7.2 · p. 18
• Weighted seeds produce a hierarchical cut by assigning each watershed edge the minimum of the maximum seed weights in its two child subtrees.The resulting edge saliencies can be converted into hierarchy levels through connected components; the method runs in quasi-linear time when input edges are already sorted.Source: §7.2 · p. 18

8 Extraction of connected components

• For non-weighted seeds, label components after removing the watershed-cut edges from the BPTAO’s building edges.This yields the single segmentation associated with the binary cut.Source: §8 · p. 19
• For weighted seeds, select a hierarchical segmentation level by saliency threshold or desired region count, then label its connected components.For r regions, retain the r − 1 watershed-cut edges with highest saliency; for threshold λ, discard cut edges with saliency below λ.Source: §8 · p. 19
• To retain all levels, construct a tree from the BPTAO of an MST whose watershed-cut edges carry their saliency values and whose other building edges have weight zero.Source: §8 · p. 19

9.1 Unsupervised watershed-cut

• The unsupervised flat-cut route builds the BPTAO and MST, seeds graph minima, identifies watershed-cut nodes, and labels components.Figure 9 demonstrates an application of this pipeline.Source: §9.1 · p. 20

9.2 Seeded watershed cut

• The non-hierarchical seeded route accepts vertices that need not be regional minima, then extracts cut edges and labels components.It is a direct generalization of the minima-seeded route, and Figure 11 demonstrates an application.Source: §9.2 · p. 20

9.3 Tree representation of an area-based hierarchical watershed

• The area-based hierarchical tree route weights minima seeds by extinction values, computes watershed-edge saliencies, and builds a BPTAO over the reweighted MST.The BPTAO algorithm is used first on the input graph and again on the reweighted MST.Source: §9.3 · p. 20

9.4 Watershed cut from a hierarchical watershed

• A cut from a hierarchical watershed can be selected by keeping the k highest-weight watershed edges or by applying a threshold, then labeling components.The use case starts from a hierarchy and extracts a segmentation rather than constructing its tree representation.Source: §9.4 · pp. 20–21

9.5 Seeded hierarchical watershed cut

• For a seeded hierarchical cut, apply the seeded watershed method to the BPTAO of the saliency-reweighted MST rather than to the original graph.The pipeline uses user input seeds after computing the hierarchical watershed; Figure 14 demonstrates an application.Source: §9.5 · p. 21

10 Conclusion

• The framework links the BPTAO’s encoding of graph minima to seed-induced watershed nodes, which correspond bijectively to watershed-cut edges.Weighted seeds give induced nodes persistence values that translate into a saliency map or hierarchy in graph space.Source: §10 · p. 22
• The authors provide algorithms for the framework’s steps and demonstrate its modularity through use cases in a Python Notebook using Higra.Source: §10 · p. 22
• The article’s use cases do not exhaust watershed applications; cited directions include hierarchy filtering, energy-based optimization, non-horizontal cuts, and machine-learning combinations.Future work plans parallel, distributed, and massively parallel algorithms targeted for GPUs.Source: §10 · p. 22

• L. Najman was partially supported by Khalifa University of Science and Technology under Award No. KU-INT-FSU-2026-004-8471000027.Source: Declarations · p. 22
• The authors declare no conflict of interest.Source: Declarations · p. 22
• No datasets were generated or analysed during the study.Source: Declarations · p. 22
• All authors contributed equally to writing and revising the manuscript.Source: Declarations · p. 22

A Appendix: Proof of Theorem 4

• Lemma 5 ensures a forest rooted at the earlier marker set extends to one rooted at its subset, supporting the induction step.Source: A Appendix: Proof of Theorem 4 · pp. 29, 31
• Lemma 6 certifies an MSF when every feasible edge swap replaces an edge by one of at least its weight.The induction step applies this exchange criterion to the newly added edge.Source: A Appendix: Proof of Theorem 4 · pp. 29, 31
• For a one-by-one filtration, cut-edge weights are unchanged across earlier levels, a property established by induction and used in proving Theorem 4.Each step removes exactly one minimum.Source: A Appendix: Proof of Theorem 4 · pp. 29–30
• In the forward implication, an MSF rooted at minima surviving level λ remains an MSF through the filtration, so Theorem 2 makes Cλ a watershed cut.The assumed hierarchy principle then yields a hierarchical watershed.Source: A Appendix: Proof of Theorem 4 · p. 30
• For every filtration level λ, a hierarchical watershed cut Cλ is the component partition of an MSF rooted at minima whose extinction values are at least λ.Source: A Appendix: Proof of Theorem 4 · p. 30
• The backward proof builds the level-i forest by adding a minimum-weight edge between the two regions merged at that level.The one-by-one step removes one minimum, and the proof uses the forest from level i−1 to obtain the required component partition and roots.Source: A Appendix: Proof of Theorem 4 · p. 31