Recall-Guaranteed Tile Selection for High-Resolution Detection

High-resolution detectors for drone, aerial, and tree-crown imagery waste most of their compute on empty background. In VisDrone, objects cover only about 8% of pixels. Current methods prune with a cheap "guide" network that guesses where objects are, and they run the expensive detector only there. These guides have two weaknesses. First, they use a fixed threshold, so when the guide misses an object, nothing downstream can recover it. Second, they report savings in arithmetic operations (FLOPs) that mostly fail to appear in wall-clock time. We propose a scheduler that treats the guide as a heuristic in a search problem, judged by total runtime. Each image is cut into regular, fixed-size tiles. The guide scores every tile. For each image, the scheduler picks the smallest set of tiles whose expected share of missed objects stays below a user-chosen rate. The rate is calibrated on held-out images, so the guarantee holds in measured practice and is not just a hoped-for property of the threshold. Before running anything, a measured hardware cost model checks whether pruning is worth it for this image. If it is not, the scheduler falls back to processing every tile.

In two sentences, the idea is this. Choose how many high-resolution tiles to send to the heavy detector per image, using a calibrated bound on how many objects the cheap guide is allowed to lose. Then refuse to prune whenever measured GPU latency says pruning would not pay. The contribution is a recall guarantee plus a wall-clock break-even rule for coarse-to-fine detection, which no current method provides.

Core Claim

The search-planning literature frames runtime as $T = N \times t_{\text{node}}$: the number of nodes evaluated times the cost per node. Multi-Dimensional Heuristic Searching makes the point that a more informed heuristic helps only if the drop in $N$ outweighs the rise in $t_{\text{node}}$. Coarse-to-fine detection is exactly this trade-off, but it is rarely analyzed that way. Here $N$ is the number of high-resolution regions evaluated and $t_{\text{node}}$ is the heavy detector's per-region latency. The guide's own runtime is a "probing tax," in the sense of Prediction-Based Adaptive Variable Ordering Heuristics for Constraint Satisfaction Problems: it can exceed what it saves.

When is Tree Search Useful for LLM Planning? It Depends on the Discriminator found that guided search beats simple re-ranking only once the guiding evaluator passes roughly 90% accuracy. We expect the vision analogue to hold as well. Below some per-image level of guide reliability, pruning loses to plain tiling at equal accuracy. Our claim is that this cliff can be detected per image at runtime, and that a calibrated selection rule can move the operating point to it.

Concretely, let $p_i$ be the guide's score for tile $i$. Let $S_\lambda$ be the tiles taken in decreasing score order until the summed score of the tiles left out falls below a threshold $\lambda$. Let $c(k)$ be the measured batched latency of the heavy detector on $k$ tiles. The scheduler runs

$$ T(\text{image}) = t_g + \min\big(c(|S_\lambda|),\; c(K)\big), $$

where $t_g$ is the guide's latency and $K$ is the total number of tiles. The fallback to all $K$ tiles is triggered when $c(|S_\lambda|)$ comes within a margin of $c(K)$. The threshold $\lambda$ is chosen on a calibration split with a distribution-free risk-control procedure. That procedure picks the largest $\lambda$ for which the average fraction of ground-truth object centers falling outside $S_\lambda$ stays below a target $\varepsilon$, with a finite-sample correction. The guarantee holds on average over images drawn like the calibration set. It does not hold under domain shift, and we test shift explicitly.

Relation to Prior Work

Four systems motivate the gap and also set the bar.

QueryDet predicts coarse heatmaps on low-resolution pyramid levels and computes stride-4 features only at flagged locations with sparse convolutions. It uses a static query threshold.

ESOD predicts an objectness mask after the network stem and slices feature patches before the neck. It is purely feedforward, and it has no notion of how much it is allowed to miss.

A Coarse to Fine Framework for Object Detection in High Resolution Image groups heatmap hits into irregular chips with a merge step.

CaTDet uses a tracker plus a light proposal network on video. It documents the hardware problem that constrains our design: an 8× drop in operations gave only a 2× wall-clock speedup, because scattered patches fragment GPU memory access.

None of the four selects compute per image against a recall target, and none decides from measured latency whether pruning should happen at all. Our design keeps tiles regular and same-sized so that selected work is a dense batch. This is a direct response to the CaTDet result.

Two older lines supply ideas but differ in mechanism. Reinforcement Learning for Visual Object Detection trains a fixation policy with a per-evaluation penalty and reports about 70× fewer evaluations at matched car AP on PASCAL VOC. It charges every evaluation the same fixed cost, needs unstable policy-gradient training, and was never tested on dense high-resolution scenes. We keep its explicit cost accounting but replace the learned policy with a calibrated ranking rule. Optimal Visual Search with Highly Heuristic Decision Rules shows that a trivial "Max Rule" can rival full Bayesian inference in human search on synthetic noise. We use a max-pooled tile score as one of our guide variants, to test whether such a cheap rule is a good enough guide on real imagery. On the planning side, A Comparison of Cost Partitioning Algorithms for Optimal Classical Planning shows that cheap sequential heuristic combination beats solving an exact optimization at every node. That is a methodological reason to prefer a simple calibrated rule over per-image optimization of the tile set.

Research Program

We build three components and study one question.

The first component is a family of guides at increasing cost. The cheapest is a max-pooled objectness score from the detector's own stem features. Next is a small convolutional heatmap head, as in QueryDet. The most expensive is ESOD's mask predictor, re-purposed to emit per-tile scores. Measuring $t_g$ for each places guides along the per-node-cost axis of the trade-off.

The second component is the calibrated selector and the fallback rule described above. The latency function $c(k)$ is profiled once per GPU and batch configuration, so the break-even decision is grounded in measured time rather than FLOPs.

The third component is an analysis tool. For each image it records the guide's realized tile recall, the number of tiles selected, and the latency. From these we fit the per-image reliability level below which tiling wins, which tests whether the "discriminator cliff" transfers to spatial search.

The heavy detector is held fixed: one standard high-capacity detector run on tiles. This isolates the scheduling question from detector architecture.

Baselines

The naive reference point is uniform overlapping tiling. The same heavy detector runs on every tile in one dense batch. This is both the accuracy ceiling for a given detector and the hardware-friendliest possible workload. It is the most dangerous baseline, because of CaTDet's evidence that irregular savings evaporate on GPUs. We run it with the identical detector, tile size, overlap, and GPU, and we tune its batch size for throughput. Beating it means matching its AP within 0.5 points at substantially lower median and 95th-percentile per-image latency.

The second reference is global downsampling to the detector's native resolution. It shows how much accuracy pruning must preserve. The VisDrone-DET2019 challenge report gives 16.09% AP for a Cascade R-CNN baseline, against about 29.6% for top entries, which illustrates the cost of losing resolution.

The strongest existing method is ESOD. On VisDrone it reports 37.9% AP at 30.9 FPS, with GFLOPs reduced from 412.2 to 183.5 relative to its YOLOv5 baseline. It also reports QueryDet at 28.3% AP under its comparison setting. QueryDet itself reports +2.1 mAP and 2.3× speedup on VisDrone over its own high-resolution baseline. Because these numbers come from different detectors, we will not compare against them directly. Instead we place ESOD-style feature slicing and QueryDet-style sparse querying on the same heavy detector and backbone, with equal training epochs and an equal hyperparameter-search budget, and measure all methods' wall-clock latency on the same GPU. Beating ESOD means a better AP-versus-latency curve at matched backbone, plus a lower realized object-miss rate at equal latency.

For TinyPerson, the coarse-to-fine framework reports 46.4 AP50. For SelvaBox, the dataset paper reports 48.60 RF1₇₅ with DINO Swin-L in-distribution and 41.91 zero-shot on BCI50ha. No reported result was found on Lacuna for ESOD on UAVDT or TinyPerson.

The key ablation replaces the per-image calibrated selector with a single static global score threshold. This is QueryDet's design choice. The static threshold is tuned on the same calibration split to reach the same average recall. Two further ablations remove the fallback rule and substitute irregular merged chips for regular tiles. The second one measures how much of the wall-clock gain comes from regularity alone.

Why not just…?

Why not just tile uniformly and rely on GPU batching? This is a real threat. CaTDet's 8×-to-2× gap shows that hardware can erase pruning gains, and batched solvers such as Batched First-Order Methods for Parallel LP Solving in MIP show that regular parallel workloads can be fast. Our answer is to keep the selected work regular, so it batches like tiling, and to fall back to tiling exactly when the profiled latency says it wins. If our latency curve does not dominate tiling on sparse benchmarks (VisDrone, SelvaBox orthomosaics), we will report that pruning is unjustified on that hardware. The break-even analysis is designed to say where that line sits.

Why not just tune QueryDet's static threshold lower? A well-tuned global threshold may get most of the benefit. Images vary widely in object density, though: VisDrone mixes near-empty frames with crowded intersections. A single threshold therefore over-selects tiles on empty images and under-selects on crowded ones, and it carries no guarantee on missed objects. The static-threshold ablation at matched average recall settles this directly. If it matches our curve, the per-image calibration is not worth its complexity, and we will say so.

Why not just learn a selection policy with reinforcement learning, as Mathe et al. did? Their policy shows that cost-penalized sequential search can cut evaluations about 70×. However, it is trained with delayed-reward policy gradients, which the file notes are prone to overfitting. It also offers no recall bound. A calibrated ranking rule needs no policy training and gives a checkable miss-rate guarantee. We consider the policy's sequential re-probing of ambiguous regions a possible later extension, not a necessary starting point.

Proposed Experiments

We train on VisDrone and TinyPerson, test transfer from VisDrone to UAVDT, and use SelvaBox for very large orthomosaics, including its zero-shot BCI50ha split. We report AP and small-object AP (or RF1₇₅ on SelvaBox), the realized fraction of ground-truth objects outside the selected tiles, median and 95th-percentile per-image wall-clock latency on a fixed GPU, and FLOPs. Reporting FLOPs alongside latency exposes the gap between the two.

There are three decisive checks. First, across five calibration-split seeds, the realized in-distribution miss rate must stay at or below $\varepsilon$ for targets of 1%, 3%, and 5%. Under the VisDrone-to-UAVDT and BCI50ha shifts, we measure how far the guarantee breaks. Second, the scheduler's AP-versus-latency curve must dominate both the static-threshold ablation and uniform tiling. Third, the fitted per-image break-even reliability must predict on held-out images whether pruning beats tiling. That would establish the spatial analogue of the discriminator-accuracy cliff.

If the cheap Max-Rule guide matches the learned heatmap head under the calibrated selector, that result also matters. It would mean the guarantee comes from calibration rather than from guide capacity.