Superpixel-Based Image Segmentation Using Squared 2-Wasserstein Distances
Authors: Jisui Huang, Andreas Alpers, Ke Chen, Na Lei
Organizations: Department of Mathematical Sciences, Centre for Mathematical Imaging Techniques (CMIT), University of Liverpool, Peach Street, Liverpool, L697ZL, Merseyside, United Kingdom. · School of Mathematical Sciences, Capital Normal University, West Third Ring Road North, Haidian District, Beijing, 100084, China. · Department of Mathematics and Statistics, University of Strathclyde, Richmond St, Glasgow, G11XH, Scotland, United Kingdom. · DUT-RU International School of Information Sciences & Engineering, Dalian University of Technology, Linggong Road, Dalian, 116024, Liaoning, China.
We present an efficient method for image segmentation in the presence of strong intensity inhomogeneities. The approach combines two levels of clustering: pixels are first grouped into superpixels using Power-SLIC, which admits a discrete optimal transport (OT) interpretation, and these superpixels are subsequently merged using squared 2-Wasserstein distances between their empirical distributions. We formulate the merging process as an adjacency-constrained hierarchical optimization problem with a regularized objective that accounts for the heterogeneities of previously formed regions. We establish NP-completeness of the associated global optimization problem, even for two final regions and two-bin histograms. For the proposed greedy algorithm, we prove exact recovery under suitable histogram separation conditions and derive an additive approximation bound for the regularized energy. Numerical experiments demonstrate competitive segmentation accuracy on images exhibiting substantial intensity inhomogeneity, while retaining computational efficiency.
Figure 1. Samples from Datasets 1–3. (a) First frame of the 74-frame video in Dataset 1 (1770 × 880) with a superimposed red mesh. (b,c) H&E-stained tissue images from Dataset 1 (1000 × 750; 950 × 730). (d,e) Cell images from Dataset 2 (600 × 600) with nuclei annotations. (f,g) Image from Dataset 3 (512 × 512) with annotation.
Figure 2. Selection of the optimal number of regions. The LT curve (a) shows a general decrease with minor fluctuations, while the ROC–LT curve (b) remains essentially zero over [1,162] , suggesting an optimal region number below 162 . Zoomed views (c, d) reveal peaks at 115 and 151 . Segmentations with 1835, 495, 425, 151, and 115 regions are shown in (e–i).
Figure 3. Segmentation vs. Oversegmentation. (a) Noisy grayscale image containing 25 white objects. (b) Power-SLIC result with 300 superpixels, serving as input to our algorithm. (c–e) Intermediate and final steps of the algorithm, merging into 200, 100, and finally 25 regions, respectively. (f) Power-SLIC output with 25 superpixels.
Figure 4. Comparison of OT-based segmentation and variance-based SMST. The first row (a–d) shows two images I1 and I2 from Dataset 1 partitioned into rectangular superpixels of sizes 40×40 (a), 30×30 (b), 80×80 (c), and 70×70 (d), respectively. The second row (e–h) shows SP results (times in seconds: 1.97, 0.28, 22.48, 16.12). The third row (i–l) shows SMST results (times in seconds: 0.35, 0.35, 0.37, 0.43).
Figure 5. Selective segmentation seeds: (a,c) images with foreground (red) and background (blue) seeds, labeled ‘f’ and ‘b’ respectively (numbers indicate order); (b,d) corresponding zoomed-in views.
Figure 6. Selective segmentation results for the image in Fig. using background marker b1 and incrementally added foreground markers: f1, f1-f2, f1-f3, f1-f4, and f1-f5. (a–e) SAM, (f–j) AR, (k–o) SP.
Figure 7. Selective segmentation results for the image in Fig. using background marker b1 and incrementally added foreground markers: f1, f1-f2, f1-f3, f1-f4, and f1-f5. (a–e) SAM, (f–j) AR.
Figure 8. Comparison of unsupervised segmentation models on Dataset 1. (a) and (b) show the intial level sets and superpixel, respectively: AR and ZZ in (a) (yellow curves, computation times ∞ ), SMST and SP in (b) (yellow curves, 0.42s). (c–g) show segmentation results (yellow curves) from SAM, AR, ZZ, SMST, and SP, respectively.
Figure 9. Unsupervised segmentation of the image in Fig. for two structures: purple cells (S1) and white cytoplasm (S2). Initializations via level sets (LS) for AR and ZZ are shown in (a, b); 4000 superpixels for SMST and SP in (c) (red channel for S1, remaining channels for S2). SAM does not allow separate-channel segmentation; its overall output is in (d). Results for S1 are in (e–h) and for S2 in (i–l). Computation times (S1/S2, in seconds): AR 829.51/570.32, ZZ 4304.50/4470.56, SMST 0.38/0.38, SP 5.98/4.26; superpixels in (c) computed in 0.17s, SAM in (d) in 7.42s.
Figure 10. Unsupervised segmentation of the image in Fig. for two structures: purple cells (S1) and white cytoplasm (S2). Initializations via level sets (LS) for AR and ZZ are shown in (a, b); 6000 superpixels for SMST and SP in (c) (red channel for S1, remaining channels for S2). SAM does not allow separate-channel segmentation; its overall output is in (d). Results for S1 are in (e–h) and for S2 in (i–l). Computation times (S1/S2, in seconds): AR 461.85/474.46, ZZ 2423.73/2434.59, SMST 0.42/0.38, SP 42.31/12.51; superpixels in (c) computed in 0.14s, SAM in (d) in 7.47s.
AR
SMST
ZZ
SAM
SP
Dataset 2
DSC
66.32
80.47
81.69
82.88
88.78
Preproc. Time (s)
∞
0.08
∞
6.09
0.08
Segm. Time (s)
395.81
0.38
2212.70
7.75
14.55
Dataset 3
DSC
61.35
60.63
65.33
73.00
76.62
Table 1. Quantitative comparison of segmentation accuracy (Dice coefficient, DSC) and running time on Dataset 2 and 3.
Figure 11. Segmentation of two images from the quantitative comparison on Dataset 2 (S3 and S4, Figs. and ); brackets show segmentation time (s) / DSC.
We propose a unified variational framework for image segmentation under sparse pixel-level supervision. Our method is based on a simplex-constrained Potts model with a smooth perimeter regularizer, yielding a convex, smooth energy functional that can be used as a training loss in weakly supervised deep learning paradigms or optimized efficiently using iterative methods. Sparse labels are incorporated into the data fidelity term by constructing a fuzzy membership function via a function extension problem in a Reproducing Kernel Hilbert Space (RKHS), which can effectively capture inhomogeneous intensity statistics. The derived discrete loss for training standard networks demonstrates robustness and consistent improvements over non-training and partial cross-entropy (PCE) baselines in experiments, achieving comparable performance without requiring ground-truth segmentation images.
Yin King Chu, Lingfeng Li, Sung Ha Kang +2
Department of Mathematics, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, China · Hetao Institute of Mathematics and Interdisciplinary Sciences, Shenzhen, Guangdong, China · School of Mathematics, Georgia Institute of Technology, Atlanta, GA, 30332, USA +2
Superpixels offer a compact image representation by grouping pixels into coherent regions. Recent methods have reached a plateau in terms of segmentation accuracy by generating noisy superpixel shapes. Moreover, most existing approaches produce a single fixed-scale partition that limits their use in vision pipelines that would benefit multi-scale representations. In this work, we introduce H-SPAM (Hierarchical Superpixel Anything Model), a unified framework for generating accurate, regular, and perfectly nested hierarchical superpixels. Starting from a fine partition, guided by deep features and external object priors, H-SPAM constructs the hierarchy through a two-phase region merging process that first preserves object consistency and then allows controlled inter-object grouping. The hierarchy can also be modulated using visual attention maps or user input to preserve important regions longer in the hierarchy. Experiments on standard benchmarks show that H-SPAM strongly outperforms existing hierarchical methods in both accuracy and regularity, while performing on par with most recent state-of-the-art non-hierarchical methods. Code and pretrained models are available: https://github.com/waldo-j/hspam.
Julien Walther, Rémi Giraud, Michaël Clément
Univ. Bordeaux, CNRS, Bordeaux INP, IMS, UMR 5218, France · Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, France
Hyperspectral images capture vast amounts of high-dimensional spectral information about a scene, making labeling an intensive task that is resistant to out-of-the-box statistical methods. Unsupervised learning of clusters allows for automated segmentation of the scene, enabling a more rapid understanding of the image. Partitioning the spectral information contained within the data via dictionary learning in Wasserstein space has proven an effective method for unsupervised clustering. However, this approach requires balancing the spectral profiles of the data, blurring the classes, and sacrificing robustness to outliers and noise. In this paper, we suggest improving this approach by utilizing unbalanced Wasserstein barycenters to learn a lower-dimensional representation of the underlying data. The deployment of spectral clustering on the learned representation results in an effective approach for the unsupervised learning of labels.
Joshua Lentz, Nicholas Karris, Alex Cloninger +1
Tufts University, Department of Mathematics, Medford, MA 02155, USA · University of California San Diego, Department of Mathematics, La Jolla, CA 92093, USA · University of California San Diego, Halıcıo˘glu Data Science Institute, La Jolla, CA 92093, USA