Training a segmentation network normally needs a human to outline every object in every image, which can take over an hour for a complex street scene. A cheaper route is to collect a few scribbles or clicks per image and spread them outward into full masks, called pseudo-labels, that the network then trains on. Current spreading methods have two problems. First, they rebuild the whole propagation from scratch whenever anything changes: a new click arrives, or the network's sense of where boundaries lie improves. The cost is high enough that one method runs at a quarter of image resolution. Second, they decide which propagated pixels to trust with hand-picked cutoffs, such as "ignore the most uncertain 6%." Those cutoffs were tuned on one dataset and have no reason to carry over to another.
This note proposes a propagation method that fixes both problems in one data structure. Each unlabeled pixel takes the label of the seed it can reach along the cheapest path, where crossing a strong learned boundary is expensive. We maintain that assignment the way robot path planners maintain routes in a changing map: when a click is added or boundary costs shift, only pixels whose cheapest path actually changed are revisited. The trust decision becomes a statistical test rather than a tuned cutoff. A pixel's label is accepted only if the boundary separating it from the competing class would be unlikely to arise from boundary values shuffled at random. The "unlikely" level is fixed in advance at an expected count of one false acceptance per image, so nothing is tuned per dataset. Rejected pixels are excluded from the training loss, and they are also the natural places to ask an annotator for the next click.
Core Claim
Geodesic seed assignment is a shortest-path problem, and it supports two things that existing propagators do not. It can be repaired incrementally, so propagation runs at full resolution and updates only where new information changes paths. Its runner-up path also gives a per-pixel test statistic with a simple null model, so the abstention rule needs no tuned threshold. We claim that this abstention rule matches a quantile cutoff tuned on the target dataset, and beats one transferred from another dataset. This should hold across PASCAL VOC, PASCAL Context and Cityscapes. We also claim that incremental repair makes the click-by-click annotation loop cheap enough to run interactively.
The main scientific bet is the abstention test. The incremental machinery is what makes full-resolution operation and the active loop practical. If the test fails to transfer better than a tuned cutoff, the proposal loses most of its value. Repair alone would be an engineering speedup.
Relation to Prior Work
Three propagators define the starting point. ScribbleSup builds a graphical model over superpixels, spreads scribbles by color, texture and network features, and alternates with network training for three rounds. It reaches 63.1% mean intersection-over-union (mIoU) on VOC 2012. Its superpixel and edge-weight parameters are heuristic, and each round re-runs inference over the full image. RAWKS treats propagation as random-walk hitting probabilities and learns boundaries by backpropagating through a sparse linear solve. Two of its properties motivate this proposal. Its propagator exceeds 80% mIoU when it abstains on the 6% most uncertain pixels, which shows that abstention is where much of the quality comes from. Its global solve forced it down to quarter resolution. We keep its idea of learned boundaries but replace the linear solve with a path problem that can be repaired, and we replace the 6% figure with a test. P2Seg handles single-point instance supervision with fixed affinity and distance thresholds. We treat it as further evidence that threshold sensitivity is widespread, not as a direct competitor, since our first target is semantic segmentation.
The repair mechanism comes from D* Lite and its relative, Lifelong Planning A*. These planners keep two numbers per node: the current cost estimate $g$, and a one-step lookahead $rhs$ computed from neighbors. Only nodes where the two disagree are queued for update. Seed assignment is a multi-source shortest-path problem with no heuristic. With no heuristic there is nothing to make inconsistent, so the correctness guarantees D* Lite gives for consistent heuristics apply directly. In D* Lite a new obstacle becomes a local cost change. Here a new click is a new zero-cost source, and a boundary update is a set of changed edge costs. Two warnings from the search literature constrain the design. D* Lite itself notes that memory per node becomes a problem on large grids. Fringe-Saving A* shows that bookkeeping can cancel the savings when changes are not local. We therefore measure the fraction of pixels that become inconsistent after each kind of change, rather than assuming locality.
The abstention test comes from the a contrario tradition. On Straight Line Segment Detection accepts a structure only when its expected number of occurrences under a noise model, the Number of False Alarms (NFA), is below one. Quasi-a-contrario plane segmentation shows the same rule adapting to changing LiDAR point density without retuning. The same paper on line segments warns that exhaustive testing over combinations of structures costs $O(N^5)$. We avoid that cost by testing one fixed candidate per pixel, the runner-up path the search already produces, rather than enumerating groupings.
Kanungo et al. is the closest prior pairing of parameter-free selection with incremental computation. It merges regions under a minimum description length (MDL) cost and updates region fits from summary statistics. Its merging is greedy and irreversible, its features are low-level, and it takes no human seeds. Our structure can be revised in both directions, and it is driven by sparse labels. LabOR supplies the active-annotation setting. It picks uncertain pixels by disagreement between two classifiers, with fixed budgets of about 2.2% of pixels or 40 points per image, and it retrains globally after each round. We borrow its evaluation protocol on GTA5-to-Cityscapes. We query where our test rejects, and we update pseudo-labels by repair.
Research Program
The propagator works on the full-resolution pixel graph. Edge costs come from a boundary head trained jointly with the segmentation network, as in RAWKS. The cost of a path is the sum of the boundary strengths it crosses. For each pixel $p$ we store two quantities: $d_1(p)$, the cheapest cost to any seed, together with that seed's class $c_1$, and $d_2(p)$, the cheapest cost to a seed of any other class. Keeping the second-best class requires a two-label variant of the $g$/$rhs$ bookkeeping, and that variant is the main algorithmic piece to build. A new click inserts a source and enqueues its neighbors. A boundary-head update changes edge costs, and only the endpoints of changed edges are enqueued. We will report how far each kind of change spreads.
For the test, let $\pi_2(p)$ be the runner-up path from $p$ to the competing class, and let $n$ be its length in pixels. Let $k$ be the number of pixels on $\pi_2(p)$ whose boundary strength exceeds the strongest boundary crossed by the winning path $\pi_1(p)$. The null hypothesis is that boundary strengths along a path are independent draws from the image's own distribution of boundary strengths. Under that null, each pixel exceeds the level with probability $q$, the empirical tail fraction for the image. The test is
$$\mathrm{NFA}(p) = M \cdot \sum_{j=k}^{n} \binom{n}{j} q^{j}(1-q)^{n-j},$$
where $M$ is the number of pixel-class tests in the image. The label $c_1$ is accepted when $\mathrm{NFA}(p) < 1$. In words, a pixel's label is trusted when the competing class sits behind a boundary too strong and consistent to be chance. The level of 1 has the fixed meaning of at most one expected false acceptance per image under the null. The independence assumption is the weakest part, because neighboring boundary strengths are correlated. We will check calibration directly by measuring how often accepted pixels are wrong on held-out dense masks, and we will try a block-shuffled null if the independent one proves too permissive.
Training alternates network updates with incremental refreshes of $d_1$ and $d_2$, and the loss uses accepted pixels only. In the active setting, each round queries the rejected pixels with the largest $d_1$. The new clicks are inserted by repair, with no global recomputation.
Baselines
The naive reference propagates scribbles by the same geodesic assignment with no abstention and recomputes from scratch each round. It shows how much abstention adds.
RAWKS is the strongest scribble propagator with a learned boundary. Its reported VOC 2012 result is 61.4% mIoU; ScribbleSup reports 63.1% on the same benchmark. On PASCAL Context, RAWKS reports 37.4% and ScribbleSup 36.1%. To keep the comparison fair, we will re-run both with the same backbone, the same scribble annotations and the same training schedule, and report our re-runs alongside the published figures. Beating them means higher final mIoU on both datasets with no per-dataset retuning of our method.
The ablation that isolates the key ingredient is our own propagator with the NFA test replaced by a quantile cutoff. The cutoff is run in three ways: fixed at 6%, tuned on VOC dense validation masks and transferred to the other datasets, and oracle-tuned on each target's dense masks. The NFA rule should match the oracle within one mIoU point and beat the transferred cutoff. We will also compare pseudo-label quality at matched coverage against RAWKS's reported figure of over 80% mIoU at 6% abstention.
For speed, the same propagator with full recomputation produces identical labels, so it isolates wall-clock time and the number of pixel updates. We run it on the same hardware at full resolution.
For active annotation, the baseline is LabOR's reported 63.5% mIoU with about 40 points per image on GTA5-to-Cityscapes. We match its point budget and adaptation backbone, and beating it means higher mIoU at equal clicks. We also include a prompted foundation segmentation model (SAM), which takes scribble or click coordinates as input; there is no reported result on Lacuna for SAM on these benchmarks, so we will run it ourselves. Finally, DenseCRF post-processing of the propagated labels, with parameters tuned on VOC, serves as the fixed-parameter classical reference.
Why not just…?
Why not just tune the abstention cutoff on a validation set? In a new domain, that validation set would have to be densely annotated, which is the cost the method exists to avoid. A cutoff tuned on one dataset should drift on another, because object scale and the mix of objects and "stuff" regions change the right fraction to reject. This alternative is a real threat. The oracle-tuned cutoff in our ablation may well match the NFA rule. The proposal's claim rests on transfer, so the decisive comparison is NFA against the cutoff transferred from VOC to Context and to Cityscapes.
Why not just prompt a pretrained foundation model with the clicks? It may produce better masks on natural images. It is still not threshold-free, since it needs cutoffs on its stability and quality scores, and the infrared small-target study reports unstable point-supervised pseudo-labels in low-contrast domains. We will run it as a baseline. If it wins on VOC, the NFA test can still be applied to its outputs, using its mask logits as boundary costs. That would turn a loss into a demonstration that the test is useful on its own.
Why not just recompute from scratch on a GPU? For training-time refreshes, global feature drift may make most pixels inconsistent anyway. In that case recomputation is the honest choice, and we will report it. Repair matters where changes are genuinely local: inserting a click in the annotation loop, and running at full resolution where RAWKS had to downsample. The measured fraction of inconsistent pixels per change will settle this question.
Proposed Experiments
On VOC 2012 and PASCAL Context with scribbles, we report final mIoU, pseudo-label precision and coverage, and the calibration of the NFA rule. Calibration is measured as the observed error rate of accepted pixels against the target of one false acceptance per image. On GTA5-to-Cityscapes we run the active loop at matched point budgets and report mIoU against clicks, along with the per-click update latency of repair versus recomputation.
The decisive checks are three. NFA abstention must beat a transferred quantile cutoff and come within one point of the per-dataset oracle. Accepted pixels must be wrong at a rate close to the nominal level. Click insertion must touch a small fraction of pixels. If the first check fails, the proposal reduces to a fast propagator. If the third check fails, it reduces to a better abstention rule.
References
- ScribbleSup: Scribble-Supervised Convolutional Networks for Semantic Segmentation
- Learning Random-Walk Label Propagation for Weakly-Supervised Semantic Segmentation
- P2Seg: Pointly-supervised Segmentation via Mutual Distillation
- D*Lite
- On Straight Line Segment Detection
- Robust 3-D Plane Segmentation From Airborne Point Clouds Based on Quasi-A-Contrario Theory
- A fast algorithm for MDL-based multi-band image segmentation
- LabOR: Labeling Only if Required for Domain Adaptive Semantic Segmentation
- Diffuse to Detect: Bi-Level Sample Rebalancing with Pseudo-Label Diffusion for Point-Supervised Infrared Small-Target Detection