Superpixel-Based Image Segmentation Using Squared 2-Wasserstein Distances

Jisui Huang; Andreas Alpers; Ke Chen; Na Lei

cs.CVJan 22, 2026

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.

Abstract

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.

Figures & tables

\bigl(E_{ij}-h_{i}-h_{j},\;i,\;j\bigr)

Algorithm 1 Unsupervised SP optimization algorithm

Panel of Figure 1 — 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.

Panel of Figure 2 — 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).

Panel of Figure 3 — 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.

Panel of Figure 4 — 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).

Panel of Figure 5 — 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.

Panel of Figure 6 — 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.

Panel of Figure 7 — 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.

Panel of Figure 8 — 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 $\infty$ ), SMST and SP in (b) (yellow curves, 0.42s). (c–g) show segmentation results (yellow curves) from SAM, AR, ZZ, SMST, and SP, respectively.

Panel of Figure 9 — 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.

Panel of Figure 10 — 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$	$\mathbf{88.78}$
	Preproc. Time (s)	$\infty$	$\mathbf{0.08}$	$\infty$	$6.09$	$\mathbf{0.08}$
	Segm. Time (s)	$395.81$	$\mathbf{0.38}$	$2212.70$	$7.75$	$14.55$
Dataset 3
	DSC	$61.35$	$60.63$	$65.33$	$73.00$	$\mathbf{76.62}$

Table 1. Quantitative comparison of segmentation accuracy (Dice coefficient, DSC) and running time on Dataset 2 and 3.

Panel of Figure 11 — Figure 11. Segmentation of two images from the quantitative comparison on Dataset 2 (S3 and S4, Figs. and ); brackets show segmentation time (s) / DSC.

Superpixel Segmentation

See all 9 papers

A Unified Variational Framework for Deep Weakly Supervised Image Segmentation
Jul 22, 2026Yin King Chu, Lingfeng Li, Sung Ha Kang +2Image Segmentation Weakly Supervised Image Segmentation
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
H-SPAM: Hierarchical Superpixel Anything Model
Apr 13, 2026Julien Walther, Rémi Giraud, Michaël ClémentSuperpixel Segmentation Image Segmentation
Univ. Bordeaux, CNRS, Bordeaux INP, IMS, UMR 5218, France · Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, France
Unbalanced Optimal Transport Dictionary Learning for Unsupervised Hyperspectral Image Clustering
Mar 10, 2026Joshua Lentz, Nicholas Karris, Alex Cloninger +1Image Clustering Dictionary Learning
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

Jul 22, 2026J/K move · Enter open · S save

A Unified Variational Framework for Deep Weakly Supervised Image Segmentation

Yin King Chu, Lingfeng Li, Sung Ha Kang, Jianping Zhang+1

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

Image Segmentation Weakly Supervised Image Segmentation Weakly Supervised Learning

Open paper AskPDF arXiv

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.

Abstract

Superpixel Segmentation

Explore similar work

A Unified Variational Framework for Deep Weakly Supervised Image Segmentation

H-SPAM: Hierarchical Superpixel Anything Model

Unbalanced Optimal Transport Dictionary Learning for Unsupervised Hyperspectral Image Clustering