Single-stage instance segmenters predict hundreds of candidate object masks in one pass and then use a fast heuristic to throw away duplicates. That heuristic decides which objects the system finally reports, yet nobody solves the underlying problem exactly. The problem is: given scored, overlapping candidate masks, pick the subset that best explains the image. It is avoided because it is an integer program, and integer programs are assumed too slow for real time. This proposal argues that this assumption depends on how the numbers in the program are written down. Theoretical work shows that the same integer program can be fast to solve when its coefficients are small integers (equivalently written in "unary", as a count of ones) and NP-hard when they are large integers written in binary. The selection problem in segmentation has a natural knob that controls this: how finely mask areas and scores are quantized.
The plan has three parts. First, measure the structure of real candidate-overlap graphs from SOLOv2 and CondInst on COCO. Second, build an exact selector whose running time is polynomial in the quantization resolution and exponential only in a small structural parameter. Third, test whether exact selection with a foreground-coverage constraint recovers objects, especially in crowded scenes, that the parallel suppression in SOLOv2 discards. The project includes an early test that can kill it: an oracle bound on how much any selector could gain from the existing candidates.
Core Claim
Duplicate removal in single-stage segmentation can be posed as a small integer program with two parts. The first is pairwise overlap penalties between candidate masks. The second is one or two global constraints tying the selected masks to a predicted foreground map. Real overlap graphs on COCO likely have a small "fracture backdoor": a handful of large "hub" masks (crowd-spanning or low-quality wide masks) whose removal splits the remaining candidates into tiny clusters. If area and score coefficients are quantized to $U$ levels, this program can be solved exactly in time roughly $2^{b}\cdot c\cdot U^{2}$, where $b$ is the number of hub masks and $c$ is the number of clusters. The same algorithm becomes exponential in the bit length if areas are kept at full binary precision.
The scientific claim has two halves. The first is structural: the backdoor is small on real data. The second is about encoding: a coarse unary $U$ costs almost nothing in mask AP while turning exact selection into a millisecond-scale computation. The practical claim is that exact selection with coverage consistency beats Matrix NMS on crowded and small-object subsets, without hurting overall AP.
Where This Sits
The complexity side supplies the method and the predictions. Solving Integer Linear Programs with a Small Number of Global Variables and Constraints defines fracture backdoors: a few variables or constraints whose removal leaves components of size at most $p$. It shows ILP is tractable in these parameters when coefficients are bounded, that Unary ILP is in XP for constraint backdoors, and that binary-encoded ILP is NP-hard even at $p=1$. That last result is the warning that motivates quantization. Our global coverage constraint is exactly a constraint backdoor with large area coefficients, so the paper predicts that unary quantization of areas is what makes it tractable.
Unary Integer Linear Programming with Structural Restrictions shows the same pattern for signed clique-width: it is polynomial when everything is unary, and NP-hard if either domains or coefficients go binary. It constrains us. Structure alone will not save the coverage constraint, and its $O(|I|^{4k})$ dynamic program is too slow to use directly, which is why we target fracture structure instead. Neither paper has ever been applied to vision post-processing.
Parallel results tell the same story. Encoding bounds move verification across complexity classes in The Computational Complexity of Satisfiability in State Space Models and in 2D vector addition systems (Englert et al.). We borrow the lesson that encoding is a design parameter, not a fixed fact. We do not borrow their machinery.
The segmentation side supplies the regime. SOLOv2 predicts masks per grid cell and replaces sequential suppression with Matrix NMS. Matrix NMS decays each score by pairwise mask overlaps in one matrix operation, taking under 1 ms. It is a heuristic with no global objective, and the file records that SOLOv2 struggles when several small objects crowd one cell. CondInst generates a tiny per-instance mask head but still depends on box NMS to remove duplicates.
Single-Stage Open-world Instance Segmentation with Cross-task Consistency Regularization aligns predicted masks with a global foreground map during training. We reuse that idea at inference, as a hard constraint during selection rather than a training loss. MEInst (Mask Encoding for Single Shot Instance Segmentation) and ESE-Seg (Explicit Shape Encoding) are the existing "encoding" work at this intersection, but they compress the mask itself into PCA or Chebyshev coefficients. They say nothing about the complexity of choosing among masks. Our proposal leaves the mask representation untouched and changes only how selection numbers are encoded.
Research Program
Formulation. For an image with $n$ candidate masks, let $x_i\in\{0,1\}$ indicate whether candidate $i$ is kept, and let $q_i\in\{0,\dots,K\}$ be its confidence quantized to $K$ levels. Let $p_{ij}\in\{0,\dots,K\}$ be a quantized penalty for keeping both $i$ and $j$, growing with their mask IoU, over the edge set $E$ of overlapping pairs. Let $a_i\in\{0,\dots,U\}$ be the mask area quantized to units of $1/U$ of the image, and $A$ the quantized area of the predicted foreground map. Selection solves
$$\max_{x}\; \sum_i q_i x_i - \sum_{(i,j)\in E} p_{ij}\, x_i x_j \quad \text{s.t.}\quad A-\delta \le \sum_i a_i x_i \le A+\delta,$$
where $\delta$ is a tolerance. The two-sided constraint says the kept masks should roughly account for the foreground, no more and no less. The lower bound is what lets the selector keep a lower-scoring mask that Matrix NMS would have decayed away, if dropping it would leave foreground unexplained. The foreground map comes from a one-channel head added to the mask feature branch, trained with the same loss as in the open-world paper.
Solver. We find a small variable backdoor $B$ of hub masks using the backdoor-detection procedure from the fracture-backdoor paper, which the file reports runs in $O((k+1)^k|E(G)|)$. For each of the $2^{|B|}$ assignments to the hubs, the remaining clusters become independent. Each cluster has at most $p$ candidates and is enumerated exhaustively. This produces a table mapping each quantized covered area to the best cluster score. Tables are then merged by max-plus convolution over area levels up to $U$, and the coverage constraint is checked at the end. This is the pseudo-polynomial step. It is polynomial in $U$ because $U$ is effectively unary. With full-precision areas, the same merge has exponentially many distinct sums, which is the knapsack hardness the ILP theory predicts.
We will batch this computation on GPU across hub assignments, with a fallback to Matrix NMS whenever $|B|$ or $p$ exceeds a cap. The fallback guarantees worst-case latency.
Structural study. Before any accuracy claim, we measure on COCO val2017 the distribution of backdoor size $|B|$, cluster size $p$, and their joint tail. We do this for SOLOv2 and CondInst candidates, stratified by instance count per image; COCO averages 7.7 instances per image (Microsoft COCO). This study is publishable on its own terms. It answers empirically the question the file leaves open, namely whether segmentation overlap matrices have the bounded structure that the parameterized results require.
Encoding study. We sweep $U$ and $K$ from very coarse to near-continuous. Two quantities are measured: the AP lost against a full-precision exact solve, done offline with a generic ILP solver, and the selector latency. The prediction is that AP saturates at small $U$ while latency grows roughly as $U^2$. That pattern would show a practical regime where the unary encoding is essentially free.
Baselines
The naive reference point is greedy mask NMS. It sorts by score and removes any candidate whose mask IoU with an already-kept mask exceeds a threshold. We tune that threshold on a held-out split of train2017.
The strongest existing method is Matrix NMS inside SOLOv2. SOLOv2 reports 39.7% mask AP on COCO test-dev with ResNet-101 and under 1 ms of post-processing. It is the strongest competitor because it is the selector the field actually uses with grid-based candidates, and it already exploits pairwise mask overlaps. We will run the released SOLOv2 weights and swap only the selector. All selectors therefore see identical candidates, backbone, and resolution. Each selector gets the same tuning budget: an equal number of hyperparameter configurations on the same held-out split, covering Matrix NMS's decay kernel and our $\lambda$, $\delta$, $K$, and $U$. For CondInst we compare against its box NMS; it reports 37.8% mask AP on test-dev with ResNet-50.
Beating Matrix NMS means three things, all with the foreground head's added compute counted. First, a gain on AP-small and on the most crowded image tercile that exceeds the seed-to-seed spread of the foreground head. Second, no loss on overall mask AP. Third, selector latency that fits a real-time budget we will report. The file gives no reported result for any exact selector or for crowded-subset AP, so these comparisons are new measurements.
Three ablations isolate the key ingredients. The first removes the coverage constraint, leaving only pairwise penalties; this asks whether the global constraint, rather than exactness, is what helps. The second replaces the quantized solver with a generic ILP solver on full-precision coefficients; this gives the "exact, unencoded" reference for both accuracy and latency. The third is an oracle selector that picks, from the same candidates, the subset that maximizes AP against ground truth. The oracle bounds what any selector could achieve.
Why not just…?
Why not just tune Matrix NMS or Soft-NMS harder? Matrix NMS can only lower scores based on overlap. It has no notion of whether the kept set explains the foreground, so it cannot deliberately keep a lower-scored object that fills an otherwise unexplained region. Whether this matters is an empirical question. The tuning-budget-matched comparison on crowded subsets settles it. If tuned Matrix NMS matches us there, the coverage idea fails and we will report that.
Why not just call an off-the-shelf ILP solver per image? This is a real threat. With roughly a hundred candidates, a commercial solver may often finish quickly. Our ablation runs exactly this solver on the same objective. If it is as fast and as accurate at the tail of the latency distribution, the contribution reduces to the formulation and the structural study, and we will say so. Our expected advantage is bounded worst-case latency. That comes from the explicit $2^{|B|}\cdot c\cdot U^2$ guarantee and the fallback, which matter for deployment. Generic branch-and-bound offers no such bound on the quantized-area knapsack component.
Why not just learn duplicate removal end to end, for example with one-to-one matching during training? This is also a serious alternative. It removes post-processing entirely, but it requires retraining the detector and changes the candidate pool, so it answers a different question. We will include a learned rescoring head trained on frozen SOLOv2 candidates with the same compute budget as our foreground head. That gives a fair learned competitor that does not change candidate generation.
Why not just fix grid congestion in the candidate generator? If the true objects never appear among the candidates, no selector can recover them. The oracle selector measures this directly. If oracle AP on crowded subsets barely exceeds Matrix NMS, selection is not the bottleneck and the project should be redirected toward candidate generation.
Proposed Experiments
The decisive first experiment is the oracle bound on COCO val2017 using SOLOv2 and CondInst candidates. It reports the gap between oracle selection and Matrix NMS (or box NMS), broken down by instance count and object size. A negligible gap ends the accuracy agenda.
The second experiment is the structural study of $|B|$ and $p$. If more than a small fraction of crowded images need the fallback, the parameterized algorithm is impractical, though the measurement still stands.
The third experiment is the encoding sweep over $U$ and $K$, with AP measured against the full-precision exact solve and latency measured on one V100-class GPU. It tests the central prediction: coarse unary quantization keeps nearly all of the exact solver's accuracy and makes its latency polynomial in $U$.
The fourth experiment is the head-to-head comparison against greedy NMS, Matrix NMS, box NMS, the generic solver, and the learned rescorer on COCO test-dev. We report overall AP, AP-small, crowded-tercile AP, and full pipeline latency.
As a transfer check, we would rerun the structural study and the comparison on a densely cluttered mask dataset. The contraband X-ray data in A Novel Incremental Learning Driven Instance Segmentation Framework is the obvious candidate if it is obtainable; no reported result was found on Lacuna for it. Heavy occlusion there should produce larger hubs and stress the backdoor assumption.
References
- Solving Integer Linear Programs with a Small Number of Global Variables and Constraints
- Unary Integer Linear Programming with Structural Restrictions
- The Computational Complexity of Satisfiability in State Space Models
- Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete
- SOLOv2: Dynamic and Fast Instance Segmentation
- Conditional Convolutions for Instance Segmentation
- Single-Stage Open-world Instance Segmentation with Cross-task Consistency Regularization
- Mask Encoding for Single Shot Instance Segmentation
- Explicit Shape Encoding for Real-Time Instance Segmentation
- Microsoft COCO: Common Objects in Context
- A Novel Incremental Learning Driven Instance Segmentation Framework to Recognize Highly Cluttered Instances of the Contraband Items