When a radiologist marks an MRI slice with a few quick strokes ("this is myocardium, this is background"), a segmentation pipeline must spread those sparse marks into a full pixel mask. The spreading step decides which neighbouring pixels "look alike," usually through one fixed similarity rule, such as intensity difference with a hand-set bandwidth. That rule is tuned once per dataset and breaks when a scanner, coil, or contrast protocol changes. We propose to build the similarity separately for each image. It would be a weighted mix of several simple similarity measures (intensity at several scales, local texture, spatial proximity, and deep-feature similarity). The weights would be chosen by holding out some of the expert's own strokes and asking which mix best reconstructs them.
The scribble does double duty in this scheme. It supervises the image and it also validates the method on that same image, at no extra annotation cost. This is multiple kernel learning, meaning the fitting of non-negative weights over a set of base similarity functions, here moved from dataset-level classification to the per-image pixel graph. The claim is narrow and testable. Fitting a handful of mixing weights per image from held-out strokes should close much of the gap between scribble supervision and full supervision, with the largest gains under scanner shift. As a side product, the held-out-stroke error flags which images need more expert attention.
Core Claim and How It Differs From Prior Work
Scribble pipelines spread labels with one affinity. Learning to Segment Medical Images with Scribble-Supervision Alone expands strokes with a classical random walk, trains a U-Net, refines with a CRF, and gates uncertain pixels with Monte Carlo dropout. It reaches 88.0% Dice on ACDC cardiac MRI versus 91.2% fully supervised, and 78.1% versus 81.8% on NCI-ISBI 2013 prostate. Its authors name CRF hyperparameter sensitivity as a main limitation, which motivates us. Learning Random-Walk Label Propagation for Weakly-Supervised Semantic Segmentation (RAWKS) learns a single edge map across the dataset by differentiating through the random-walk linear system. The cost of doing this inside network training forces it to 1/4 resolution. We borrow its implicit differentiation but use it for a different job. We fit roughly ten scalar weights per image, with no network in the loop, so the solve can run at full resolution, and RAWKS's learned edge map can itself be one base kernel.
On the kernel side, three papers each supply part of the idea, and none of them works on pixel graphs. Constrained clustering and multiple kernel learning without pairwise constraint relaxation is the closest existing work. It chooses kernel weights to satisfy must-link and cannot-link constraints on tabular data, using gradient-free search, and lists extension to non-tabular domains as future work. We move that idea to pixel graphs, where strokes give dense, spatially structured constraints, and we replace black-box search with a differentiable held-out-stroke loss. CLEF2007: Image Annotation Task: an SVM-based Cue Integration Approach showed that combining local and global kernels beats single cues on radiographs, but only for image-level categories. Localized multiple kernel learning makes weights input-dependent. We test a restricted version of it as an extension: two weight vectors, one for pixels near strokes and one for far pixels.
Insights from Classifying Visual Concepts with Multiple Kernel Learning constrains the design. In that paper, sparse weights (54.58% average precision on VOC 2009) lost to plain equal-weight averaging (55.85%), while mildly non-sparse weights won (56.70%). We therefore default to $l_p$ norms with $p$ slightly above 1 and treat sparsity as something to test, not assume. This sits against the case for sparse regional selection made by Embedding Anatomical or Functional Knowledge in Whole-Brain Multiple Kernel Learning Models. We read the difference as one between selecting regions and fusing cues, and we test it directly.
Mechanism
For an image, build a sparse 8-neighbour pixel graph. Base kernel $m$ assigns edge weights $W_m$, for example Gaussian intensity differences at bandwidths spanning a decade, gradient-orientation and local-texture kernels, and cosine similarity of features from a frozen encoder. The combined graph is $W(\beta)=\sum_m \beta_m W_m$, with $\beta_m\ge 0$ and $\|\beta\|_p\le 1$.
Split the expert's strokes into groups $s=1,\dots,S$. Let $P_{-s}(\beta)$ be the random-walk class probabilities obtained by seeding with all strokes except group $s$, which takes one sparse Laplacian solve. The weights solve
$$\beta^\star=\arg\min_{\|\beta\|_p\le 1,\ \beta\ge 0}\ \sum_{s=1}^{S}\ \mathrm{CE}\big(P_{-s}(\beta)[\Omega_s],\,y_s\big),$$
where $\Omega_s$ are the pixels of group $s$, $y_s$ their labels, and CE is cross-entropy. Gradients come from implicit differentiation of the linear system, as in RAWKS. With $\beta^\star$ fixed, all strokes seed the final pseudo-mask, and a standard U-Net trains on it with the same uncertainty gating as the scribble-only pipeline above. The leftover held-out loss is a per-image quality score.
A 256×256 slice gives about 65k nodes, so each solve by conjugate gradient takes milliseconds, and the full fit is cheap enough to run interactively while the expert annotates. The obvious failure mode is that held-out strokes lie in easy interior regions and say little about boundaries. We address this by splitting strokes by position along the stroke, so held-out segments approach boundaries, and we measure whether held-out loss tracks true boundary error.
Research Program
The program has three parts. First, build the per-image fitting procedure and the base-kernel library, and check on images with full masks that held-out-stroke loss correlates with the Dice of the resulting pseudo-mask; without that correlation the method has no basis. Second, run the full pipeline on the benchmarks below and analyse the learned weights: do they shift systematically across scanners and organs, do bandwidths move with contrast, and is the deep-feature kernel always dominant? If the deep-feature kernel takes nearly all the weight on every image, the method reduces to deep affinity and the proposal fails on its own terms. Third, use the quality score for annotation triage: route the images with the highest held-out loss back for one extra stroke, and measure Dice gained per additional expert second.
Baselines
The naive reference point is a U-Net trained with cross-entropy on stroke pixels only, with no propagation. It shows how much any spreading step contributes at all.
The strongest existing method on the medical benchmarks is the random-walk, CRF, and uncertainty-gating pipeline of Learning to Segment Medical Images with Scribble-Supervision Alone, which reports 88.0% Dice on ACDC and 78.1% on NCI-ISBI 2013. We re-run it on our exact scribbles, backbone, and epoch budget. We give its random-walk bandwidth and CRF parameters the same total tuning budget as our method, measured in validation-set evaluations, and report its published numbers alongside. Beating it means higher mean Dice on identical scribbles, plus a reduced gap to full supervision on the shifted-site test, with paired significance across patients.
On DeepLesion, the strongest competitor is the RECIST-initialised GrabCut co-segmentation of Weakly Supervised Lesion Co-Segmentation on Ct Scans at 90.3% mean Dice. Here we only swap GrabCut for our propagation, treating axis pixels as foreground and a margin ring as background, and keep their network fixed. A gain under that swap isolates pseudo-mask quality.
RAWKS is the closest learned-affinity competitor. Its reported numbers are natural-image only (61.4% mIoU on VOC 2012), and we found no reported result on Lacuna for RAWKS on medical data, so we re-implement it on ACDC with matched compute.
Three ablations isolate the key ingredient. The equal-weight sum of the same base kernels tests whether weighting matters at all. Dataset-level weights, fit once on pooled training strokes, test whether the per-image fitting is what helps. The single best base kernel, including the deep-feature kernel alone, tests whether mixing adds anything over choosing one kernel.
Why not just…?
Why not just tune the random-walk bandwidth and CRF once per dataset? That is exactly the brittle setup the scribble-only pipeline's authors flag, and it should hold up in-distribution. The multi-site prostate experiment settles this. We tune on one site and test on the others, and compare the dataset-level weights ablation against per-image weights. If per-image fitting does not beat per-dataset tuning under shift, the core claim is wrong.
Why not just let the network learn affinity end to end, as RAWKS does or as a U-Net implicitly does? This is a real threat. With enough images, a network trained on partial labels may absorb contrast variation itself. The deep-feature kernel enters our library precisely so that it can win if it should. We also test it alone as a baseline. The proposal survives only if the mix beats it, especially with few training images and on unseen scanners. Learned affinities are fit to the training distribution, while our weights are refit on every test-time scribble.
Why not just average the kernels equally? In Insights from Classifying Visual Concepts with Multiple Kernel Learning, equal averaging beat sparse weighting and lost to non-sparse weighting by under a point of average precision, so averaging is a strong and honest baseline. We report it directly. We also sweep $p$ from 1 to infinity, where large $p$ approaches equal weights, so the results show where the per-image optimum lies.
Proposed Experiments
The benchmarks are ACDC (left ventricle, right ventricle, myocardium), NCI-ISBI 2013 prostate, the seven-site prostate collection used in Continual atlas-based segmentation of prostate MRI (RUNMC, BMC, HCRUDB, UCL, BIDMC, HK, DecathProst) for shift, and DeepLesion with its RECIST marks. For prostate shift, we train on one site and test across the remaining sites, with propagation run on each target image's own scribbles. Metrics are Dice and 95th-percentile Hausdorff distance, pseudo-mask Dice on training images, and the Spearman correlation between held-out-stroke loss and true pseudo-mask Dice. All of these are compared at matched scribble density, with simulated strokes generated by a fixed skeletonisation protocol.
Three results are decisive. First, the held-out loss must correlate with pseudo-mask quality across images; otherwise selecting weights from strokes is not justified. Second, per-image weights must beat the dataset-level ablation on shifted prostate sites, which shows that adapting to each image is what matters. Third, under the triage experiment, extra strokes sent to high-loss images must yield more Dice per expert second than the same strokes spread at random. That final check ties the method directly to the cost of expert time.
References
- Learning to Segment Medical Images with Scribble-Supervision Alone
- Learning Random-Walk Label Propagation for Weakly-Supervised Semantic Segmentation
- Constrained clustering and multiple kernel learning without pairwise constraint relaxation
- CLEF2007: Image Annotation Task: an SVM-based Cue Integration Approach
- Localized multiple kernel learning
- Insights from Classifying Visual Concepts with Multiple Kernel Learning
- Embedding Anatomical or Functional Knowledge in Whole-Brain Multiple Kernel Learning Models
- Weakly Supervised Lesion Co-Segmentation on Ct Scans
- Continual atlas-based segmentation of prostate MRI