CS Paper Radar

Playing with Kruskal: algorithms for flat and hierarchical watershed cuts

Jean Cousty, Laurent Najman, Benjamin Perret, Deise Santana Maia

cs.CV ·submitted 2026-10-07 13:03 UTC · v1
publishedunusual

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.

Journal ref
Journal of Mathematical Imaging and Vision, 2026, 68 (5), pp.65

Closest papers

Nearest neighbours by meaning across the whole index.

The Power Watershed as a Differentiable Segmentation Layer

cs.CV cs.NEeess.IVmath.OC ·2026-10-28 ·Galia Akl, Laurent Najman, Hugues Talbot
code/data similarity 0.69
Abstract

Can a Watershed transform, the classical tool of morphological segmentation, be placed at the end of a deep network and trained through? The Power Watershed (PW) is the limit of the seeded Random Walker (RW) as p grows to infinity with edge weights raised to the power p. At every finite p the RW solves a sparse positive-definite linear system and is exactly differentiable with respect to the edge weights and the unaries through one adjoint solve; its multi-label form costs one right-hand side per label, and its limit is the PW. We study this family as the last layer of a segmentation network, the watershed layer (WS layer). A conditioning study measures how the solve, the gradient and the distance to the limit evolve with p, and the implicit gradient is checked against unrolling. On synthetic data with correct edge costs the WS layer transforms a soft prediction into an exact boundary. On nuclei segmentation (PanNuke), a binary WS layer is level with a thresholded U-Net. With the instances as labels, the WS layer turns the U-Net into an instance segmenter whose number of labels is set per image by the markers rather than by the output layout, and the network is trained through that partition: instance F1 score rises from 0.656 to 0.795 over a U-Net with connected components, level with the same network followed by a tuned marker watershed. At the training temperature the partition is a watershed of the learned costs, and the finite temperature lets the solve hedge, discounting weak markers and sharing contested pixels. The hedging puts the WS layer 0.015--0.020 F1 ahead of the baseline when trained on a tenth of the data, at the price of having to deploy the finite-p solve rather than its exact limit at inference. Code and the full experimental record are released.

0.36

UI-VISA: U-Net Initialized Vascular Image Segmentation Architecture

cs.CV ·2026-09-01 ·Asees Kaur, Suzanne S. Sindi, Erica M. Rutter
similarity 0.56
Abstract · 9 pages, 6 figures

Accurate segmentation of vascular structures in digital subtraction angiography (DSA) images remains challenging due to the thin, elongated, and branching nature of blood vessels. Pixel-wise deep learning approaches such as U-Net achieve strong general-purpose segmentation performance but often produce fragmented or discontinuous predictions in fine vascular regions, since they do not explicitly enforce structural connectivity. Region growing algorithms preserve spatial context and topological continuity, but are highly sensitive to seed point initialization and can be computationally expensive. We propose UI-VISA (U-Net Initialized Vascular Image Segmentation Architecture), a hybrid pipeline that combines the complementary strengths of both approaches. UI-VISA uses U-Net's foreground predictions as informed seed points for a CNN-guided region growing algorithm, which then iteratively refines the segmentation by enforcing local connectivity and recovering fine vessel details that U-Net alone tends to miss or over-predict. We evaluate UI-VISA against standalone U-Net and a prior region-growing-based method (VISA) using 5-fold cross-validation on 26 DSA images. UI-VISA achieves the highest mean Dice and clDice scores across folds, and a paired Wilcoxon signed-rank test shows the improvement in clDice is statistically significant ($p=0.023$), consistent with the method's design goal of preserving vascular connectivity, while the improvement in Dice does not reach significance ($p=0.104$).

0.22

Computationally Efficient Pathology Segmentation using Knowledge Distillation from Foundation Models

eess.IV ·2026-09-03 ·Jiaqi Lv, Yijie Zhu, Saki Okada, Maxwell Stanley Renna, Robert Goldin +2 more
similarity 0.55
Abstract · Submitted to Medical Image Analysis

Automatic tissue segmentation is essential for large-scale analysis of histopathology whole-slide images (WSIs), but accurate pixel-level segmentation remains challenging. Pixel-level annotations are expensive to obtain, models pre-trained on natural images may transfer poorly to histopathology, and pathology foundation models, despite their strong representations, are computationally expensive to deploy at scale. We address these challenges with a foundation-model knowledge distillation framework for efficient tissue segmentation. We first train Virchow2-based segmentation teachers, including a LoRA-adapted variant, achieving state-of-the-art or highly competitive performance across four datasets: PUMA, IGNITE, BEETLE, and a private blood vessel segmentation dataset. We then transfer response-level and feature-level knowledge from these teachers into compact student networks. Distillation consistently improves student performance over supervised training alone, producing state-of-the-art or near state-of-the-art results with substantially fewer parameters and up to ten-fold higher inference throughput than foundation-model-based segmentation networks. These results show that foundation-model knowledge can be effectively transferred to efficient segmentation models for scalable deployment without compromising performance. Models trained on the public datasets will be released through TIAToolbox.

0.35

BEACON: A Versatile Accelerator for Computational Pathology Applications

cs.AR ·2026-09-10 ·Sumanth Gudaparthi, Ananth Krishna Prasad, Lin Jia, Rajeev Balasubramonian, Srinivasan Parthasarathy
similarity 0.54
Abstract

While accelerators for AI have seen great commercial success, it is challenging to replicate that success for other specialized domains due to a number of factors. We make the case that barriers for new accelerators can be lowered by starting with a baseline AI accelerator, and adding minimal logic to support new operators demanded by new specialized domains. This leads to a versatile chip that can be manufactured at high volume and deployed for a range of popular applications. We refer to this as the AI+X approach. This paper explores its potential for the emerging domain of Computational Pathology, which involves analysis of large whole-slide tissue images with a multi-stage pipeline. The pipeline requires support for a number of different kernels and operators - early stages perform segmentation and feature extraction, followed by graph creation with k nearest neighbor (kNN) algorithms, and finally inference with an iterative graph convolutional network (GCN) that alternates between Aggregation and Combination. We show that these stages execute inefficiently on a range of baseline CPU, GPU, AI, and GCN accelerators. That inefficiency is addressed with a combination of software re-structuring and small modifications to a baseline systolic AI accelerator. Many of the above kernels can be mapped to a systolic accelerator by offering a flexible datapath between processing elements and register access mechanisms. We add support for feature aggregation, load balanced execution, Euclidean distance calculation, binning, and counter aggregation. This additional flexibility and logic grows the area of a baseline AI chiplet by 1.1x, but by avoiding the memory wall and offering high parallelism, the proposed accelerator BEACON yields over an order of magnitude higher throughput for Computational Pathology than baseline CPU and GPU platforms.

0.11

MOXIE: Discovering Alternative Explanations for Biomedical Image Classifiers

cs.CV cs.LGcs.NE ·2026-10-03 ·Abiha Tahsin Chowdhury, Rahul Dubey
similarity 0.53
Abstract

Segment-based explanation methods such as LIME return a single explanation for each prediction, computed from one fixed image segmentation. This hides two important facts: a prediction can be supported by many different sets of image segments, and the segmentation itself shapes which explanations can be found. We introduce MOXIE (Multi-Objective eXplanation Imaging Engine), an evolutionary framework that searches for segment subsets that preserve the classifier's confidence while keeping as little of the image as possible. Instead of one explanation, MOXIE returns a Pareto front of alternative explanations that range from compact to highly faithful. We evaluate MOXIE with NSGA-II and four segmentation methods (SLIC, Felzenszwalb, Watershed and Voronoi) on BloodMNIST and HAM10000 datasets, using the same evaluation budget as LIME. Results show that MOXIE achieves a higher hypervolume than LIME on every image. LIME's explanations often appear convincing, yet the classifier's confidence collapses when only the highlighted segments are shown. MOXIE's fronts reveal how much of the image is needed to preserve the model's confidence and which contextual regions influence it. We also find that segmentation strongly affects evaluation: methods with unequal segment sizes appear most compact when segments are counted. These results show that alternative explanations provide a more complete view of a model's decision than a single explanation.

0.21

Efficient 3D plant segmentation through multiscale graph learning and optimized geometric processing

cs.CV ·2026-11-07 ·Jesus Ivan Ruiz-Martinez, Andres Mendez-Vazquez, Eduardo Rodriguez-Tello
similarity 0.53
Abstract

Plant organ segmentation on compact computing platforms requires accurate predictions and affordable geometric preparation. We develop and evaluate a multiscale edge based graph attention model that combines local shape descriptors, two neighborhood scales and a residual stem and leaf correction in approximately 78 thousand parameters. The engineering application is plant point cloud segmentation for precision agriculture, assessed through grouped accuracy experiments and physical Raspberry Pi 5 inference. Broad comparisons with hierarchical, graph and transformer baselines establish PointNeXt as the strongest external accuracy reference among the tested local recipes. A nested four variant ablation on a local maize collection separates geometric information from the combined multiscale configuration across seven outer groups and three seeds. The complete model achieves the highest mean intersection over union, 86.36%, although uncertainty and boundary errors qualify the contribution of each component. We then optimize full cloud principal component analysis, sampling and neighbor queries without changing learned weights or descriptor definitions. All 1,180 paired desktop comparisons on PlantNet and TomatoWUR preserve exact logits and predictions. Multiscale pipeline latency falls from 330.33 to 96.82 milliseconds on PlantNet and from 1,054.52 to 463.10 milliseconds on TomatoWUR. PointNeXt also benefits from optimized sampling and remains faster over the complete pipeline. These results support compact graph learning with reduced geometric overhead, while physical board measurements establish inference feasibility rather than energy efficiency or readiness for autonomous flight.

0.15

ReG-SAM: Reference Graph-Driven SAM for 2D Foundational Vessel Segmentation

cs.CV cs.AI ·2026-09-25 ·Donghang Lyu, Zichen Zhang, Oleh Dzyubachyk, Marius Staring
similarity 0.53
Abstract

Vessel segmentation in medical images is essential for many clinical tasks, ranging from diagnosis to treatment planning. However, it remains challenging due to complex vascular morphology and diverse imaging conditions. Existing deep learning methods rarely aim at building a generalizable vessel segmentor across anatomies and modalities. While the Seg- ment Anything Model (SAM) has shown promise for med- ical image segmentation, its original design does not fully exploit vascular morphology and struggles with fine-grained vascular structures, leading to suboptimal performance. In this paper, we propose ReG-SAM, a SAM-based framework tailored to 2D vessel segmentation that leverages reference graph set for enhancing vascular representations. Specifically, we introduce two modality-aware representations derived from the reference masks: graph prompt embeddings (GPEs) that encode global spatial features from graphs, and vascu- lar prototype embeddings (VPEs) that capture fine-grained modality-specific vessel characteristics from multi-scale fea- ture maps and vascular masks. Since both require vascular masks that are unavailable during inference and require robust modality-aware vascular feature representations, we construct a modality-wise vascular database and develop two reference graph-guided representation learning schemes for estimating GPEs and VPEs using samples from the database rather than ground-truth masks. Extensive experiments across 19 datasets demonstrate that ReG-SAM consistently outperforms existing baselines, even those using manual prompts, particularly on challenging thin vessels.

0.09

RiverScan: Learning to Accumulate on River Networks

cs.LG ·2026-11-13 ·He Zhu, Zhiyi Gao, Youhuan Yang, Han Quan, Ming Li
similarity 0.53
Abstract · 17 pages including references and appendices; 6 figures, 5 tables

Accurate runoff prediction across large river basins requires models to capture heterogeneous local hydrological responses and their accumulation downstream. River-network connectivity provides a natural structure for this task, but using it effectively requires learning how to combine contributions from subcatchments of different sizes. We frame this challenge as learning to accumulate and introduce RiverScan, a spatial operator based on area-weighted selective state-space recurrence. RiverScan recursively combines local temporal representations with accumulated upstream states in topological order. Contributing-area fractions account for subcatchment size, while learned retention controls how upstream information persists downstream. Experiments on 608 stations in the Danube basin show that RiverScan outperforms the evaluated temporal and graph baselines in overall predictive performance. Structural controls and ablations demonstrate that composing heterogeneous subcatchment representations in a manner aligned with hydrological accumulation substantially improves runoff prediction, with the benefits of correct topology growing along the river-network hierarchy. These findings establish physically structured accumulation as an effective inductive bias for hydrological modeling and motivate finer-grained, fully distributed AI-based hydrological models.

0.20