Diverse Point Selection for High-Resolution Mask Refinement

Many segmentation systems save compute by predicting a coarse mask first and then fixing only a few hundred carefully chosen pixels at high resolution. The best-known example, PointRend, picks the pixels whose coarse prediction is closest to a coin flip. That rule has two blind spots. It wastes its budget on many near-identical points along the single most ambiguous stretch of boundary. It also never visits thin structures that the coarse mask confidently missed, such as a bicycle spoke, a cable, or an insect leg, because the coarse model is not uncertain there; it is simply wrong. We propose to treat point selection as a budgeted subset-selection problem with diminishing returns. A point is worth adding if its high-resolution features look unlike anything already selected and the region is plausibly mis-predicted. We solve this problem with randomized greedy selection: at each step, score only a small random sample of candidates instead of every pixel. This keeps the per-image cost close to PointRend's even when the fine grid has hundreds of thousands of pixels.

In two sentences: replace "refine the k most uncertain pixels" with "greedily pick k pixels that together cover the distinct kinds of fine-scale evidence the coarse mask may have gotten wrong," and make the greedy step cheap by scoring a random sample of candidates per step. The bet is that this recovers thin parts the coarse stage dropped, a failure mode that both PointRend and ESNet concede their refinement stages cannot fix. It should do so at the same point budget.

Core Claim

Point selection in coarse-to-fine refinement fails mainly because points are scored independently, not because there are too few of them. Our selection score is a weighted coverage objective defined over high-resolution feature vectors rather than pixel coordinates. Let $R$ be a random reference set of $m$ pixels drawn from the fine grid. Each pixel $j$ has a fine-feature embedding $z_j$ and an importance weight $w_j$. We choose a set $S$ of $k$ refinement points to maximize

$$F(S) = \sum_{j \in R} w_j \max_{i \in S} \mathrm{sim}(z_i, z_j),$$

where $\mathrm{sim}$ is a non-negative similarity, for example a clipped cosine similarity on fine features concatenated with a scaled position. The weight is

$$w_j = u_j + \lambda\, d_j,$$

with three ingredients. The term $u_j$ is the coarse uncertainty, which is PointRend's signal. The term $d_j$ is the disagreement between the coarse probability and a cheap linear probe applied to the fine features at pixel $j$. The constant $\lambda$ trades the two signals off.

The objective $F$ has a standard facility-location form, so it is monotone and submodular: adding a point never hurts, and adding one similar to an already-chosen point helps little. Two consequences follow. Redundant boundary points receive small marginal gains. A thin spoke has distinctive high-frequency features and high disagreement $d_j$, so it receives a large gain even when $u_j$ is near zero.

We optimize $F$ with stochastic greedy. At each step we score only $s \approx (n/k)\ln(1/\epsilon)$ random candidates out of the $n$ fine-grid pixels, so the total cost is roughly $n \ln(1/\epsilon)$ gain evaluations. Each evaluation costs $O(m)$ against the reference set. The unified analysis in Approximation Guarantees of Stochastic Greedy Algorithms for Subset Selection bounds the expected value of this procedure at $(1-e^{-\mu\gamma})$ of optimal. Here $\gamma$ measures how close the objective is to submodular, and equals 1 for our objective. The factor $\mu$ is determined by the sampling rate.

What is new is that the selection depends on fine-scale feature content and is optimized jointly over the whole set. To our knowledge, no point-based refinement head does either.

Positioning Against Prior Work

The method's host is PointRend: Image Segmentation As Rendering. PointRend upsamples a coarse prediction step by step, picks the top-$k$ points by $|p-0.5|$, and classifies each with a small multilayer network on interpolated fine and coarse features. We keep its rendering loop, point head, and feature taps unchanged and replace only the selection rule. Any gain we report is therefore attributable to selection alone.

Two works motivate the proposal by documenting the gap. ESNet gates shallow high-resolution features with continuous attention maps and restricts refinement to boundary pixels. Like PointRend, it cannot repair structures its coarse stage omits. Deep Interactive Thin Object Selection shows that downsampling erases one-pixel-wide parts, and supplies ThinObject-5K and the thin-region IoU metric that make the failure measurable.

Two papers from active learning, at the image level rather than the pixel level, supply the core intuition that uncertainty alone selects redundant samples. A Neural Pre-Conditioning Active Learning Algorithm to Reduce Label Complexity samples random candidate batches and keeps the one that best conditions a gradient Gram matrix, and it beats margin sampling on CIFAR-10. The Informative Vector Machine builds sparse active sets by entropy scoring over random candidate pools. Neither paper selects locations inside an image, so we move their insight from dataset-level acquisition to within-image point selection.

The algorithmic machinery comes from the stochastic greedy literature. Two papers matter here. Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization reports 10x to 100x speedups over deterministic greedy at comparable objective values. Do Less, Get More shows that subsampling candidates loses little utility in video summarization. Together they make it plausible that random candidate pools lose little against exhaustive greedy.

We also distinguish the work from things that share vocabulary or goals. Greedy Growing Enables High-Resolution Pixel-Based Diffusion Models is "greedy" only in the sense of adding layers in stages, and it processes pixels densely. SG-Net uses greedy matching only to link objects across video frames. Dense high-resolution backbones such as HRNet and UViT keep fine features everywhere. They are complementary to our method, because they supply better $z_j$, not competitors in point selection.

Research Program

We build the selector as a drop-in module for the Detectron2 PointRend implementation. At each subdivision step the module runs three operations. It first computes $u_j$ on the upsampled grid. It then computes $d_j$ from a linear probe on the finest feature tap; the probe is trained with the same point-wise loss as the point head and adds negligible parameters. Finally it draws a reference set $R$ of $m$ pixels, stratified so that high-$w$ regions are not undersampled, and runs stochastic greedy to pick $k$ points. Selection is non-differentiable, which matches PointRend: gradients flow through the point head and the probe at the chosen points.

At training time, the same selector chooses supervised points. We will test whether this matters relative to PointRend's training-time sampling scheme.

The analysis has three parts. First, we measure how close stochastic greedy comes to deterministic greedy on $F$ as the sample size $s$ varies. This checks the theoretical claim on correlated pixel grids, which are far from the unstructured ground sets the theory assumes. Second, we measure wall-clock overhead against PointRend at matched $k$. Third, we report a recovery diagnostic. For each ground-truth connected thin component that is absent from the coarse mask, we record whether any selected point lands on it and whether the final mask recovers it. This is the quantity the core claim actually concerns.

Baselines

The naive reference point is the coarse mask head upsampled bilinearly with no point refinement. It shows how much any refinement buys.

The strongest existing method is PointRend's uncertainty top-$k$ selection, run from the official Detectron2 code with the same backbone, schedule, number of subdivision steps, and per-step point budget $k$. PointRend reports a 2.8 AP gain over Mask R-CNN for Cityscapes instance segmentation, a 1.2 mIoU gain over DeepLabV3 for Cityscapes semantic segmentation, and a 1.6 AP gain on COCO measured against LVIS-quality masks. These figures are relative improvements; no absolute PointRend AP is reported in the material available to us, so we will reproduce the absolute numbers ourselves. To beat this baseline we need a statistically reliable gain over PointRend across three seeds, at an equal point budget and within 10% of its latency. The gain we care about most is thin-region IoU and the component-recovery rate, with no loss in overall mask AP.

A second baseline adds cheap diversity in coordinate space. It takes top-uncertain points but suppresses any candidate within radius $r$ of an already-chosen point, in the style of non-maximum suppression. A variant instead mixes the top-uncertain points with a fixed fraction drawn uniformly at random. We tune $r$ and the mixing fraction on validation data with the same budget we give $\lambda$ and $m$.

Three ablations isolate the key ingredients. The first keeps the full selector but sets $\mathrm{sim}$ to use positions only. This separates feature-space coverage from simple spatial spreading. The second sets $\lambda = 0$, which separates the disagreement signal from the coverage objective. The third replaces stochastic greedy with deterministic greedy, which isolates whether randomization costs accuracy or only saves time.

For thin-object benchmarks we also compare with TOS-Net. It reports 65.1% thin-region IoU on HRSOD in its interactive setting. Because that setting uses clicks, we treat the number as a reference rather than a like-for-like target.

Why not just…?

Why not just spread uncertain points out spatially with suppression? This is the most serious threat. It captures the redundancy half of our argument almost for free. However, it cannot place points on a confidently mis-predicted thin part, because suppression only reorders points that are already uncertain. If the coordinate-only ablation and the suppression baseline match our selector on the component-recovery rate, the feature-space objective adds nothing. In that case we would reduce the contribution to the disagreement weight $d_j$ plus suppression. The experiment is designed to show which of these outcomes holds.

Why not just refine more points? A larger $k$ eventually covers everything, and PointRend's own motivation is that it reaches crisp masks at about 30x less compute than dense heads. We therefore report accuracy-versus-point-budget curves for both methods. Our claim holds only if our curve dominates, meaning we reach PointRend's best thin-region IoU with fewer points. If the curves merge at modest $k$, the problem is a budget problem, not a selection problem.

Why not just use a high-resolution backbone? HRNet reaches 81.1% mIoU on Cityscapes with HRNetV2-W48 by keeping fine streams throughout the network. This is orthogonal to our method rather than a substitute. We will run both selectors on an HRNetV2 backbone. If our gain disappears there, that suggests better features alone fix the coarse stage's omissions; that outcome would itself be informative about when cascades are worth having.

Why not just use deterministic greedy? On correlated pixel grids, exhaustive greedy may be affordable at $224 \times 224$. The ablation reports both accuracy and time. If deterministic greedy is equally fast at the resolutions tested, randomization matters only at the native 2K resolutions of HRSOD and ThinObject-5K, where we expect the per-step cost of scanning all $n$ candidates to dominate.

Proposed Experiments

We run instance segmentation on Cityscapes and on COCO with LVIS-quality evaluation masks, and semantic segmentation on Cityscapes, using PointRend's protocols and backbones. For thin structures we train on ThinObject-5K and evaluate on its test split and on HRSOD, in a non-interactive setting with a box prompt. We report mask AP, boundary-sensitive AP on LVIS annotations, mIoU, thin-region IoU, the component-recovery rate, and latency per image.

The decisive check is the component-recovery rate on thin parts missing from the coarse mask, compared at equal $k$ across three selectors: PointRend, the suppression baseline, and ours. Our method must recover clearly more of these components while keeping Cityscapes and COCO AP no worse than PointRend. A second check verifies the theory in practice: stochastic greedy should achieve at least 95% of deterministic greedy's value of $F$ at a sample size $s$ well below $n$.

If our selector improves AP but not component recovery, the gain comes from reduced redundancy, not recovery, and the "thin parts the coarse stage dropped" claim fails. If it improves neither, point selection is not the bottleneck.