Labeling a few randomly chosen pixels per image is one of the cheapest ways to supervise semantic segmentation, the task of assigning a class to every pixel. Most methods spend the same fixed budget on every image, for example 40 points each. That is wasteful. A sky-and-road highway frame needs few points, while a cluttered intersection with poles, signs, riders and bicycles needs many. Deciding which image is which is a statistics problem. After a small first round of random clicks, we want to know how diverse each image's true pixel-class distribution is, including the rare classes the clicks have not yet hit. The obvious estimate, computing the entropy of the observed click histogram, is systematically too low when the number of clicks is comparable to the number of classes. It underestimates exactly the cluttered images that most need more labels.
Work on estimating functionals of discrete distributions from few samples shows how to remove most of this bias. That work replaces the badly behaved part of a function such as $-p\log p$ near zero with its best low-degree polynomial approximation, and then estimates each power of $p$ exactly without bias from sample counts. This proposal applies that machinery to annotation allocation. The two fit unusually well: uniform random point labeling makes the annotation literally a multinomial sample from the image's class distribution, so the estimators' assumptions hold exactly rather than by analogy. We propose a two-stage protocol. Annotators first label a few random points per image. A bias-corrected estimator then predicts each image's label diversity, and the remaining budget is spent where that estimate says it is needed.
Core Claim
When per-image point budgets are near or below the number of classes ($n \lesssim k$, with $k = 19$ on Cityscapes), polynomial bias-corrected estimates of per-image label entropy and of the rare-class-sensitive power sum $F_{1/2}(P)=\sum_c \sqrt{p_c}$ rank images by true label diversity much more accurately than plug-in, pseudo-count-smoothed, or first-order-corrected estimates. Allocating a fixed total click budget by these estimates should improve target-domain segmentation over uniform allocation at equal annotation cost. The claim has a cheap, decisive first test that needs no network training: dense ground-truth masks give the true per-image distributions, so estimator accuracy can be measured directly by subsampling.
Why the estimation literature applies here, and where it does not
The method comes from four papers. Minimax Estimation of Functionals of Discrete Distributions shows that the bias of the plug-in estimator equals the error of a Bernstein polynomial approximation, which converges slowly for functions with a sharp corner at zero. Optimal entropy estimation on large alphabets via best polynomial approximation uses the fact that, under Poisson-distributed sample sizes, falling factorials of a count are unbiased for powers of its probability. Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approximation builds the hybrid estimator we reuse. It applies a degree-$L$ best polynomial approximation, with $L$ on the order of $\log k$, to classes seen rarely, and a bias-corrected plug-in to classes seen often. Minimax Estimation of Functionals of Discrete Distributions extends the approach to power sums with $\alpha<1$, where plug-in needs $n \gg S^{1/\alpha}$ samples and the polynomial estimator needs $n \gg S^{1/\alpha}/\ln S$. Concretely, for a class $c$ with count $N_c$ out of a Poisson($n$) number of clicks, a polynomial $\sum_m a_m p^m$ is estimated by
$$\widehat{g}(N_c)=\sum_{m=0}^{L} a_m \frac{N_c(N_c-1)\cdots(N_c-m+1)}{n^m},$$
and this estimate is exactly unbiased for $\sum_m a_m p_c^m$.
Two constraints from the same literature shape the design. First, Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem? proves that adding pseudo-counts does not improve the plug-in rate, however the pseudo-count is tuned. We still include it as a baseline, because asymptotic rate results need not decide the outcome at $k=19$. Second, the gains in this literature are logarithmic in $k$, and its constants are unspecified (Minimax Rates…). With only 19 classes the improvement could be small, and our first experiment is designed to find out. One known weakness of these estimators does not arise here. They usually depend on an unknown support size, but in segmentation the class vocabulary is fixed and known.
We deliberately do not follow the more obvious crossover suggested by the research file, which is to swap a bias-corrected KL divergence into softmax-based consistency losses such as Con2R's (Graph-Constrained Contrastive Regularization for Semi-weakly Volumetric Segmentation), or into entropy-based acquisition. A network's softmax output is not a frequency computed from a small sample, so there is no counting bias for these estimators to correct. That combination would borrow the vocabulary of the theory without meeting its assumptions. Click histograms do meet them.
Research Program
The work is built in three layers. The first is an estimator study. On Cityscapes (fine annotations) and on GTA5 (dense synthetic labels), we compute each image's exact pixel-class distribution. We then simulate Poisson($n$) uniform clicks for $n$ from 5 to 80 and compare entropy and $F_{1/2}$ estimators by mean squared error and by Spearman rank correlation with the true value across images. Ranking accuracy is what allocation actually consumes. The polynomial degree constant and the switching threshold are tuned only on GTA5, which is the labeled source domain, so no target labels enter tuning.
The second layer is the allocation protocol on GTA5→Cityscapes domain adaptation, the setting of LabOR: Labeling Only if Required for Domain Adaptive Semantic Segmentation. LabOR picks about 40 points per image where two classifier heads disagree and reaches 63.5% mIoU. We keep the total budget at 40 points per image on average. Stage one labels $n_0 = 10$ uniform random points per image. Stage two splits the remaining 30-per-image average across images in proportion to estimated diversity, with a floor and a cap. Within each image, the stage-two points can be placed either uniformly at random or by LabOR's disagreement criterion. The downstream segmentation training is LabOR's own pipeline, unchanged, so only the click placement differs.
The third layer is a collapse monitor for self-training, which reuses stage-one clicks at no extra cost. Self-training on noisy pseudo-labels can lose rare classes over successive rounds. We therefore compare the estimated true per-image diversity with the diversity of the model's dense pseudo-labels on the same image. A persistent gap flags images whose rare classes are being absorbed into frequent ones. Such images are then given extra clicks or excluded from pseudo-labeling. This addresses the error-cascade problem that the research file notes for point-supervised methods.
Baselines
The naive reference point is uniform allocation: every image gets 40 points, placed by LabOR's disagreement criterion, which is LabOR's PPL setting as published. The strongest existing method is LabOR itself. Its reported number is 63.5% mIoU on GTA5→Cityscapes with 40 points per image, against a 66.7% fully supervised result and 66.6% for its segment-based variant at 2.2% of pixels (LabOR). We will rerun it from the same initialization, with the same backbone, number of training iterations and total click count, so that the comparison does not rest on reproduced numbers alone.
The ablations that isolate the key ingredient keep the two-stage protocol and the training identical and change only the diversity estimator used for allocation. The estimators compared are the plug-in entropy of the stage-one histogram, Miller–Madow correction, Dirichlet pseudo-count smoothing with the pseudo-count tuned on GTA5, and the polynomial hybrid. A further control allocates by the entropy of the model's own predicted class histogram for each image, which costs no stage-one clicks. Finally, a random-allocation control assigns the same varying per-image budgets but in shuffled order, which shows whether gains come from the diversity signal or merely from varying budgets. Beating LabOR means at least one mIoU point at equal total clicks, averaged over three seeds and with non-overlapping spread. On rare classes such as pole, traffic sign, rider and bicycle, we additionally require the per-class IoU gain over the plug-in ablation to exceed seed-to-seed variation.
Why not just…?
Why not just use the plug-in entropy, or Miller–Madow, on the stage-one clicks? Theory says both fail when $n \ll k$. Minimax Rates… reports that its estimator significantly outperforms Miller–Madow in that regime, because Miller–Madow's correction assumes many samples per class. With $k=19$ and $n_0=10$ we are in that regime, but at a small $k$ where the log-factor advantage is modest. This alternative is a real threat. The estimator study measures ranking correlation directly, and if the polynomial estimator's ranking is not clearly better there, the allocation hypothesis is withdrawn before any training is run.
Why not just add pseudo-counts? Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem? proves that smoothing does not change the plug-in rate. Smoothing also mainly shifts all estimates by a similar amount rather than reordering images. It is nonetheless included and tuned, since the finite-$k$ behavior is an empirical question.
Why not just use the model's uncertainty to decide which images get more points, with no random clicks? LabOR already uses disagreement between classifier heads to place points within an image. Extending that signal to rank whole images is free and would plausibly work. Its weakness is that it measures the model's confusion rather than the scene's true composition. Under domain shift, an early model can be confidently wrong about rare classes it never predicts. The no-click control in the ablations tests this head-on. If it matches the polynomial-estimate allocation, then stage-one random clicks are not worth their cost, and we would report that.
Why not just match the pseudo-labels' class proportions to the click histogram, as in learning from label proportions? Class proportions are linear in the probabilities, so plug-in estimates of them are already unbiased, and this is a sensible training constraint. It solves a different problem from deciding where to spend clicks, so it can be combined with our allocation. For the collapse monitor, we compare a monitor based on raw proportions with one based on bias-corrected $F_{1/2}$. The comparison asks whether a functional that weights rare classes, estimated without bias, flags collapse earlier than noisy proportions of rare classes do.
Decisive Checks
The first check needs no training. On Cityscapes subsamples with $n \le 20$, the polynomial estimator must beat plug-in, Miller–Madow and Dirichlet smoothing on rank correlation with the true per-image entropy and $F_{1/2}$. If it does not, the project stops or is redirected to settings with larger vocabularies, such as COCO panoptic labels with object categories. The second check is the main comparison: at equal total clicks, polynomial-estimate allocation must beat LabOR's reported 63.5% mIoU, and must beat our own rerun and the plug-in-allocation ablation, with the gain concentrated on rare classes. The third check is that the collapse monitor's flags predict which images lose rare-class IoU over successive self-training rounds better than the monitor based on raw proportions does. As a transfer test, the same allocation logic applied to choosing which slices to label in BraTS volumes would be compared against Con2R's reported 43.2 mIoU with 24 slices (Con2R). Here, random-voxel clicks within candidate slices play the role of stage one.
References
- Maximum Likelihood Estimation of Functionals of Discrete Distributions
- Optimal entropy estimation on large alphabets via best polynomial approximation
- Minimax rates of entropy estimation on large alphabets via best polynomial approximation
- Minimax Estimation of Functionals of Discrete Distributions
- Does dirichlet prior smoothing solve the Shannon entropy estimation problem?
- Graph-Constrained Contrastive Regularization for Semi-weakly Volumetric Segmentation
- LabOR: Labeling Only if Required for Domain Adaptive Semantic Segmentation