Playing with Kruskal: A State-of-the-Art Report on Watershed Cuts
Unknown authors
Sep 2026· Journal of Mathematical Imaging and Vision· Vol 68· 0 citations· 108 references
TL;DR
This article presents a detailed end-to-end pipeline of algorithms to compute (hierarchical) watershed segmentations, starting from the computation of graph-based image representations, up to the computation of connected components of the final (hierarchical) segmentation.
Abstract
In the framework of edge-weighted graphs, watersheds have proven to be linked to well-known optimization problems, as Minimum Spanning Tree, which allowed the design of efficient algorithms for computing (hierarchical) watershed segmentations. In the present article, after reviewing the literature related to watershed segmentation, we present a detailed end-to-end pipeline of algorithms to compute (hierarchical) watershed segmentations, starting from the computation of graph-based image representations, up to the computation of connected components of the final (hierarchical) segmentation. We consider the several variations of watersheds, including their supervised and unsupervised versions, and the various ways of computing seeds, to name a few. For the first time, we bring together all these watershed notions and algorithms in a compact and understandable way. We aim at providing a reference for those interested in employing and reimplementing the watershed segmentation framework for their task at hand.
In the framework of edge-weighted graphs, watersheds have proven to be linked to well-known optimization problems, as Minimum Spanning Tree, which allowed the design of efficient algorithms for computing (hierarchical) watershed segmentations. In the present article, after reviewing the literature related to watershed...
J. Cousty, Laurent Najman, Benjamin Perret et al.· Journal of Mathematical Imag...· 0 citations
The component tree is a graph-based structure that represents in a lossless way the spatial / spectral information carried by a grey-level image. The component tree models the inclusion of the connected components over the successive threshold sets of an image, thus leading to two dual variants: the max-tree, obtained...
Wonder Alexandre Luz Alves, N. Passat, D. J. Silva et al.· Journal of Mathematical Imag...· 0 citations
Density decomposition characterizes the multi-level dense structure of large networks and supports a wide range of graph mining applications. Given a graph
G = (V, E)
, it assigns each vertex an integral dense number (IDN) and produces a nested sequence of layers D
0
⊇ D
1
⊇ ... ⊇ D
p
that capture increasingl...
Ya-Long Zhang, Rong-Hua Li, Qi Zhang et al.· Proceedings of the ACM on Ma...· 0 citations
This paper studies an offline translation-query problem between two simple polygons. Given polygons 𝐴 and 𝐵 and a query translation 𝑡 = (𝑑𝑥, 𝑑𝑦), the task is to compute an additional correction vector 𝑎 so that 𝐵 + 𝑡 + 𝑎 is separated from 𝐴, or reaches the minimum corrective translation required by the evaluated solver...
Bin Zhang· International Conference on...· 0 citations
Gatd is the first GPU-accelerated framework for 𝜂 -threshold decomposition, co-designed with GPU architecture to enable efficient parallelization and achieves speedups of up to four orders of magnitude over state-of-the-art CPU-based methods and existing GPU-based graph processing frameworks.
Tree-encoded partitionings of graphs are fundamental tools for the decomposition and approximation of graph signals. For the efficient approximation of such graph signals, we develop strategies based on $hp$-refinement by combining domain decomposition with an improved local approximation using polynomials of higher de...
Giacomo Elefante, Wolfgang Erb, M. Multerer· 0 citations
Related blog posts
Microsoft Research Blog· microsoft.comOct 29, 2026
Host Sowbhagya Suresh shares some of the latest news and cutting-edge research from across Microsoft—from understanding the challenges facing coding agents to uncovering how people use AI at work and improving extended-range weather forecasting. The post Microsoft Research Focus – Edition #97 appeared first on Microsoft Research.
MIT News · Artificial Intelligence· news.mit.eduOct 28, 2026
Professor Paris Smaragdis develops computers with superhuman hearing for applications like speech recognition, music understanding, and environmental monitoring.
For decades, a fundamental question about the difficulty of computing in high-dimensional spaces has resisted proof. New research resolves this question, removing a major theoretical obstacle to understanding the efficiency of randomized algorithms used across science and computing. The Kannan–Lovász–Simonovits (KLS) conjecture was proposed in 1995. It asks whether, for a broad class of high-dimensional […] The post Solving a 31-year-old grand challenge in mathematics – the KLS conjecture appear…
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
