Hall-Interval Counting Losses for Dense Oriented Object Detection

Detectors that find tilted objects, such as ships packed along a dock or products crammed onto a shelf, must make two kinds of decision during training. First, they decide which prediction is responsible for which real object (the "assignment"). Second, they measure how well each responsible prediction overlaps its object. Transformer detectors in the DETR family enforce a strict one-prediction-per-object rule using the Hungarian algorithm, a global matching solver run on a full table of pairwise overlap scores at every training step. Cheaper alternatives assign each prediction to its nearest object independently. These local rules are fast, but they lose the one-to-one guarantee: several predictions crowd onto the same object, and the detector falls back on Non-Maximum Suppression (NMS), a hand-tuned filter that deletes overlapping boxes and is known to delete real neighbours in crowded scenes.

Constraint programming has studied this exact trade-off for decades. When a global "all different" rule is broken into pairwise "these two must differ" rules, each solver step gets cheaper but the solver loses the ability to see that, for example, five variables cannot share four values. Search then explodes. The fix that keeps both speed and reasoning power is to add counting constraints over intervals, so-called Hall-interval capacity constraints. We propose the geometric analogue. A detector with cheap local assignment gets a differentiable loss that compares, inside many thin image strips, how many objects the predictions claim against how many objects are actually there. Rotated boxes are represented as Gaussians, so each strip count is a closed-form sum of one-dimensional Gaussian probabilities. The claim to test is that these counts restore most of the one-to-one behaviour of global matching without NMS, that they do clearly better than pairwise repulsion between predictions, and that the gap grows with scene density, as the constraint-programming theory predicts.

Core Claim

The source of the idea is Decompositions of All Different, Global Cardinality and Related Constraints. That paper replaces a monolithic matching propagator with 0/1 indicators $A_{ilu}$ (does variable $i$ fall in interval $[l,u]$?) and capacity sums $\sum_i A_{ilu} \le u-l+1$. It shows the decomposition keeps bound consistency, a guarantee that no value is left in a variable's range unless some full solution could use it. In practice the effect is large. On pigeonhole problems with $n=11$, the pairwise "binary inequality" decomposition needed 29 seconds and nearly a million backtracks in MiniSat+, while the interval decomposition needed 0.1 seconds and 10 backtracks. Ranking Constraints shows the same failure from the other side: decompositions that miss over-subscribed intervals time out at 30 minutes, while a specialised $O(n \log n)$ interval propagator does not. Together these papers motivate the proposal. They also constrain it: pairwise decompositions are predicted to be the wrong design.

On the detection side, Rethinking Rotated Object Detection with Gaussian Wasserstein Distance Loss and The KFIoU Loss for Rotated Object Detection turn a rotated box into a 2D Gaussian. This replaces costly polygon clipping with smooth matrix operations. We reuse that representation. Both papers apply it only as a one-to-one regression loss between a prediction and its already-assigned target. Neither says anything about the global constraint among all predictions.

Our contribution sits in that gap: a Gaussian "interval capacity" term that acts on the whole set of predictions at once. Concretely, a query $q$ predicts a confidence $s_q$ and a Gaussian with mean $m_q$ and covariance $\Sigma_q$. Projecting onto a unit direction $u$ gives a 1D Gaussian with mean $u^\top m_q$ and variance $\sigma_q^2 = u^\top \Sigma_q u$. Within that projection, a strip $I=[a,b]$ receives a soft predicted count

$$\hat C(I) = \sum_q s_q \left[\Phi\!\left(\tfrac{b-u^\top m_q}{\sigma_q}\right) - \Phi\!\left(\tfrac{a-u^\top m_q}{\sigma_q}\right)\right],$$

where $\Phi$ is the standard normal cumulative distribution function. The target count $C(I)$ is computed the same way from the ground-truth Gaussians with $s=1$. The loss sums over-subscription $\max(0,\hat C(I)-C(I))$ and under-subscription $\max(0,C(I)-\hat C(I))$ across a family of strips over $K$ directions. The over-subscription term is the direct analogue of a violated Hall interval: it fires when duplicates crowd a region.

Strip counts are a relaxation of exact matching, so they do not imply that a one-to-one matching exists. They play the role of bound consistency, which is weaker than full domain consistency but much stronger than pairwise reasoning. Using all $O(L^2)$ intervals over $L$ grid cells would reproduce the auxiliary-variable explosion the constraint-programming literature warns about. We therefore use dyadic intervals, $O(L \log L)$ of them, in the spirit of pyramid decompositions, and compute them by prefix sums over the projected values.

Research Program

The base detector is an oriented Deformable-DETR in the style of AO2-DETR: Arbitrary-Oriented Object Detection Transformer. That model matches queries to objects with the Hungarian algorithm under a rotated-IoU cost and needs no NMS. We replace its global matching with local assignment: each query regresses toward its nearest ground truth under Gaussian distance, using the KFIoU loss. We then add the strip-capacity loss on the confidences and centres.

One known risk has to be handled in the design. Two duplicates can each settle at confidence 0.5, which satisfies every count but defeats thresholding. We break such ties by scaling each query's over-subscription gradient by one minus its Gaussian overlap with its assigned target, so the worse-localised duplicate is suppressed. We also add a small penalty pushing confidences toward 0 or 1. The tie-breaking mechanism will be reported separately, because it is the most likely point of failure.

The program has three parts. The first is a profiling study that measures what fraction of training step time global matching actually consumes as the number of objects per image grows. The file contains no reported timing numbers, so this must be measured rather than assumed. The second is a controlled synthetic benchmark of rendered rows of rotated rectangles with tunable packing density and aspect ratio. It plays the role that pigeonhole problems play in constraint programming: it isolates where pairwise reasoning fails. The third is full training on real benchmarks.

Baselines

The naive reference point is local nearest-object assignment with no constraint between predictions. It is run once without NMS, which shows the raw duplicate problem, and once with tuned rotated NMS, the conventional repair. A second naive point is the same detector trained with Smooth L1 coordinate regression instead of KFIoU. This anchors how much the Gaussian loss itself contributes; KFIoU reports a 9.90% AP75 gain over Smooth L1 on HRSC2016 (The KFIoU Loss for Rotated Object Detection).

The strongest existing method is global Hungarian matching. We run it in two forms. The first follows AO2-DETR's rotated-IoU matching cost. AO2-DETR reports 77.73% mAP on DOTA-v1.0, 58.0% AP on SKU110K-R and 97.47% mAP on HRSC2016 (AO2-DETR: Arbitrary-Oriented Object Detection Transformer). The second uses a cheap KFIoU-based matching cost, which is the fairest global competitor because it removes polygon clipping from matching. We also include ARS-DETR as an orientation-aware variant: it weights angle error by aspect ratio during Hungarian matching and loss, and reports 74.16% AP50 and 49.41% AP75 on DOTA-v1.0 with ResNet-50 (ARS-DETR: Aspect Ratio Sensitive Oriented Object Detection with Transformer).

Every arm shares the backbone, query count, training schedule and data augmentation. Every arm receives the same hyperparameter search budget, eight runs over loss weights and thresholds, on a held-out split. All arms are reimplemented in one PyTorch codebase built on the mmrotate tooling of the h2rbox-mmrotate repository, with KFIoU and GWD ported from yangxue0827/RotationDetection. Our own reproduction of AO2-DETR, not the published number, is the comparison target. Published numbers serve only as a sanity check on that reproduction.

The key ablation replaces strip counts with pairwise Gaussian repulsion between confident predictions, a penalty on the Wasserstein overlap of every pair of predictions near the same object. This is the "binary inequality" decomposition in geometric form. A second ablation compares all intervals against dyadic intervals.

Beating the strongest baseline means three things. Without NMS, our model must match the Hungarian-KFIoU arm to within 0.5 AP75 on DOTA-v1.0 and HRSC2016. It must exceed that arm on SKU110K-R, where density is highest. And it must beat pairwise repulsion by a margin that widens with density on the synthetic benchmark.

Why not just…?

Why not just keep Hungarian matching with a Gaussian cost? This is the most serious threat. If KFIoU makes the cost table cheap and the cubic-time solver is a small fraction of each step, the speed motivation for decomposition disappears. The profiling study settles this directly. If matching costs less than a few percent of step time even on SKU110K-R, we drop the speed claim. The remaining claim is then narrower but still useful: interval counts give a dense, set-level training signal that global matching also lacks, and they let one-to-many assignment, which converges faster, run without NMS. If the strip loss fails to beat the Hungarian-KFIoU arm in either accuracy or convergence epochs, the proposal has failed.

Why not just use one-to-many assignment and NMS? NMS deletes valid neighbours when tilted objects sit side by side, as documented for DOTA and SKU110K-R (DOTA: A Large-Scale Dataset for Object Detection in Aerial Images; AO2-DETR: Arbitrary-Oriented Object Detection Transformer). Its threshold also does not transfer across aspect ratios (ARS-DETR: Aspect Ratio Sensitive Oriented Object Detection with Transformer). The local-plus-NMS arm with a tuned threshold measures this, and the synthetic density sweep shows where its recall collapses.

Why not just add pairwise repulsion between predictions? Pairwise repulsion is cheaper to explain and needs no interval machinery. The constraint-programming evidence is that pairwise decompositions miss over-subscribed groups. Two predictions slightly offset on one of three tightly packed ships each look acceptable pairwise while the strip is still over-full. This is what the pigeonhole and graceful-graph results show for binary inequalities (Decompositions of All Different, Global Cardinality and Related Constraints). Pairwise repulsion is also quadratic in the number of predictions. If the repulsion ablation matches the strip loss at every density, the analogy is wrong and we will say so.

Why not just use exact SkewIoU everywhere? Exact rotated overlap gives zero gradient for non-overlapping boxes and has boundary discontinuities (Rethinking Rotated Object Detection with Gaussian Wasserstein Distance Loss). It also does not address the duplicate problem at all, which is a set-level issue rather than a per-pair one.

Proposed Experiments

The synthetic benchmark comes first and is the decisive check on mechanism. We sweep packing density, from isolated objects to rows with gaps smaller than box width, and aspect ratio, from 1:1 to 1:8. We measure duplicate rate (the fraction of objects claimed by two or more confident predictions), miss rate, and AP75 for local-only, pairwise repulsion, strip counts and Hungarian matching. The prediction is specific. All methods agree at low density. Local-only and pairwise repulsion diverge from Hungarian as density rises. Strip counts track Hungarian closely.

On DOTA-v1.0, HRSC2016 and SKU110K-R we report AP50 and AP75. We also report duplicate and miss rates, training step time broken into forward, matching and loss components, and the number of epochs needed to reach 95% of final AP75. These measurements address both the claim of NMS-free accuracy and the known slow convergence of DETR-style oriented detectors. We further test on square-like categories in DOTA, such as storage tanks and roundabouts, where the Gaussian loses heading information. Strip counts depend on centres and extents rather than angle, so they should neither help nor hurt there, and any change would point to an interaction we have not anticipated.

The proposal fails if strip counts do not separate from pairwise repulsion as density increases. It also fails if they cannot reach the Hungarian-KFIoU arm without NMS on SKU110K-R.