Detection as Revisable Search: Memory-Bounded Best-First Search over Gigapixel Image Pyramids

Fast detectors for gigapixel and aerial images all use the same trick. A cheap pass over a downsampled image guesses where objects are, and the expensive detector runs only on those regions. The weakness is that the guess is final. If the coarse pass misses a faint crowd in a corner, nothing ever looks there again.

Heuristic search has handled this kind of problem for decades. Recursive best-first search, which explores the most promising branch while remembering a revised score for every branch it abandons, can return to a discarded region when the region it chose turns out worse than expected. It does this while keeping memory under a fixed budget. We propose running gigapixel detection as that kind of search over a tree of image regions at increasing resolution. Each region's score is a learned estimate of how many objects it still hides, and each estimate is corrected as finer evidence arrives.

The two-sentence version is this. Treat "where should the expensive detector look next" as a best-first search over a resolution tree, where looking at a region at higher resolution revises the estimates stored at its ancestors, so that early mistakes can be undone. Do it under a fixed memory budget, and measure whether that revision beats one-shot cascades and simple ranked patch lists at equal detector compute.

Core Claim

Coarse-to-fine detectors make errors that are spatially correlated and resolution-dependent. A density map computed at 1/32 scale underestimates tiny, occluded people across whole regions, not at random pixels. A search that refines region estimates level by level, and backs the corrected values up the tree, should reach a given recall with fewer full-resolution detector passes than a pipeline that commits to one coarse ranking.

The specific mechanism is taken from recursive best-first search. The search descends into the highest-valued child as long as that child's value exceeds the best alternative elsewhere in the tree, which serves as the local threshold. When it backs out, it stores the child's revised value in the parent. It can therefore switch back to a sibling at exactly the right moment without keeping the whole frontier in memory.

The claim is falsifiable, and it has two parts. The first part is that hierarchical refinement with backed-up values matters: it should beat a static priority list over leaf patches that uses the same scoring network. The second part is that a memory bound can be imposed at small cost. We will measure how much speed is lost when the cache of intermediate feature maps is capped, relative to unbounded best-first search.

We do not claim provable optimality. The scoring function is a neural network and is not admissible, meaning it is not guaranteed never to underestimate. Any statement about missed objects will be statistical, obtained by calibration on held-out images.

Where This Sits

Three strands of prior work supply the method.

The first is memory-bounded search. Sen and Bagchi's MREC (Fast Recursive Formulations for Best-First Search That Allow Controlled Use of Memory) caches explicit nodes until a memory budget fills and then falls back to recursive re-expansion. Bhattacharya and Bagchi showed the same smooth interpolation for game trees by making the queue size a parameter (Making Best Use of Available Memory When Searching Game Trees).

The second is recursive best-first search in AND/OR spaces. RBFAOO+ (Anytime Recursive Best-First Search for Bounding Marginal MAP) and UBFS (Anytime Anyspace AND/OR Best-First Search for Bounding Marginal MAP) bring recursive thresholding and prune-and-re-expand to these spaces. The RBFAOO+ result is directly relevant: at a 1GB limit it was "the only algorithm that never crashed," while unbounded best-first solvers failed on most instances.

The third is detection-side scoring. SaccadeDet (SaccadeDet: A Novel Dual-Stage Architecture for Rapid and Accurate Detection in Gigapixel Images) supplies the multi-scale density regression we reuse as a node scorer.

Several papers motivate the gap by pruning irreversibly or without search.

SaccadeDet discards about 95% of the image after one low-resolution pass. ClusDet (Clustered Object Detection in Aerial Images) crops predicted clusters and fails on isolated objects outside them.

PAN (Speed up Object Detection on Gigapixel-level Images with Patch Arrangement) comes closest structurally. It builds a multi-grained patch tree, but it filters that tree with a policy trained by REINFORCE and never re-expands a discarded subtree. Our proposal keeps PAN's tree but replaces its filter with search that can revise its choices. We deliberately leave out PAN's patch-packing step, which could be added on top of either method.

Mathe et al. (Reinforcement Learning for Visual Object Detection) search sequentially with a learned fixation policy. They report that the policy is prone to overfitting. Their state is a trajectory, not a tree with backed-up values.

One line of work constrains the design. Exact subwindow branch-and-bound, I-ESS and A-ESS (Efficient algorithms for subwindow search in object detection and localization), obtains real bounds only because its quality function is linear in precomputed features. That result tells us that once a deep network is in the loop, exact bounds are off the table. We accept this and aim for calibrated estimates instead.

Research Program

Search tree. A PANDA image (PANDA: A Gigapixel-Level Human-Centric Video Dataset) is decomposed into a quadtree over an image pyramid. The root is the whole image at roughly 1/32 scale. Each child is one quadrant rendered at twice the parent's resolution, and leaves are full-resolution detector-sized chips. Child regions overlap by a margin so that objects on boundaries are not truncated.

Expanding a node. Expanding a node runs a light scoring network on its crop. For each child, the network outputs a predicted count of objects in several size buckets (tiny, small, middle, large, following SaccadeDet's density heads), restricted to objects that are not yet resolvable at the current level. Objects that are already resolvable at the current level are detected there by a shared detection head and removed from the count. At the leaves, the full detector (RTMDet, matching SaccadeDet's gaze stage) runs.

Node value. A node's value is its predicted count of still-undetected objects. After its children are expanded, the node's value is replaced by the sum of their revised values. This is the backup step. In classic recursive best-first search the parent inherits its best child's cost; here it inherits a count, because the goal is total recall rather than a single path.

Search order. The search descends into the child with the largest value for as long as that value exceeds the largest value among the alternatives outside the current subtree. When it backs out, it writes the revised value into the parent. A small slack margin on the threshold limits thrashing between near-equal siblings, which is a known failure mode when heuristics discriminate poorly. We will report the re-expansion rate so the size of this problem is visible.

Memory. Following MREC, a fixed-size cache holds feature maps of recently expanded nodes. When the cache is full, nodes are evicted, but their backed-up values are kept. Re-entering an evicted node means recomputing its features from pixels. The cache size $M$ is the knob that moves the method between a linear-memory recursive search and ordinary best-first search with an unbounded list of open nodes.

Anytime operation. The search can stop at any detector budget. At that point the sum of values over unexpanded nodes is the system's own estimate of remaining misses. We will calibrate a correction factor on validation images by split conformal prediction, so that the estimate becomes an upper bound on true remaining objects at a chosen coverage level such as 90%. This is the honest replacement for the formal bounds in RBFAOO+ and UBFS.

Training. The scoring network is trained on PANDA training scenes with count regression per size bucket. We then run a second round on the node crops that the search actually visits, so that the scorer sees the distribution it will face at test time.

Baselines

Uniform tiling. The naive reference point runs the same RTMDet detector over every full-resolution chip. PAN reports this needs "~13,000" passes per PANDA image. It defines the recall ceiling and the compute ceiling for every other method.

SaccadeDet. This is the strongest existing method. The file reports "0.760" AP50 on PANDA at "3.2 FPS" on a 3090 GPU. We will re-run it with the same gaze detector, the same training split and the same scorer backbone, so that the only difference from our method is irreversible thresholding versus revisable search. Its density threshold will be swept to trace a full AP50-versus-detector-passes curve rather than a single operating point.

PAN. PAN reports AP50 "0.715" with passes reduced "from ~13,000 to approximately 2,500–3,600 per image." We will compare against PAN's reported operating point and, where feasible, retrain PAN's patch-filter module with our detector.

What counts as beating these baselines. Our method must reach SaccadeDet's AP50 with clearly fewer full-resolution passes, or exceed it at matched passes and matched wall-clock time. It must also do so without exceeding the memory budget. Because published numbers use different detectors, the claim rests on the matched re-runs, not on cross-paper comparisons.

Static-ranking ablation. This ablation isolates the key ingredient. It uses the same scoring network, evaluated once on the downsampled root image to predict counts for every leaf chip. It then processes chips in descending order until the budget runs out, with no hierarchy and no value backup.

Unbounded best-first ablation. This runs the same tree and backup with a global list of open nodes and an unlimited feature cache. It isolates what the memory bound costs.

Why not just…?

Why not just lower SaccadeDet's threshold? Sweeping the threshold does trade compute for recall, and we include that sweep as a baseline. The question is whether the same recall can be bought more cheaply. A single coarse map cannot tell a truly empty region from a region whose tiny people it failed to see. A lower threshold therefore spends passes uniformly on both kinds of region. Revision at intermediate resolutions spends them where the coarse map was wrong. If the sweep's curve dominates ours, the idea is refuted for PANDA.

Why not just rank all leaf chips by a coarse score and process them in order? This is the real threat. Any cascade becomes anytime this way, and a list of 13,000 entries costs essentially no memory, so the memory argument alone does not justify a recursive search. The static-ranking ablation settles it directly. We expect the gap to appear mainly on small objects, where PANDA shows detectors fall to about 0.20 AP against about 0.75 on large ones, because those are exactly the objects a root-level score cannot see. If there is no gap, we will report that hierarchy and backup do not pay here.

Why not just learn the search policy with reinforcement learning, as PAN and Mathe et al. do? A learned policy could in principle discover re-expansion on its own. However, Mathe et al. report overfitting, and PAN's filter makes one irreversible decision per node. Our search has no policy parameters beyond the scorer and the threshold slack. Comparing against PAN under a scene-level train/test split will show whether the explicit search generalizes better.

Why not just run unbounded best-first search? On a workstation GPU with small images, this may be fine. The memory ablation quantifies the cost of the bound. The bound matters when feature maps for a 25k-by-14k pyramid exceed device memory. The RBFAOO+ experience, where unbounded best-first solvers crashed at 1GB, is the analogous case in graphical-model inference.

Decisive Experiments

Main comparison on PANDA. The primary result is a curve of AP50, and separately recall on small objects, against the number of full-resolution detector passes. It will be traced at 500, 1,000, 2,000 and 4,000 passes, with wall-clock time and peak GPU memory reported alongside. The curve will be plotted for our method, the static ranking, the swept SaccadeDet cascade, and tiling.

Memory sweep. We will repeat the main comparison at cache sizes $M$ ranging from a few nodes up to unbounded, reporting the re-expansion rate and the time overhead against the unbounded best-first ablation. Success means a curve that degrades gracefully, as MREC's did for classic search.

Isolated objects. On VisDrone we will test isolated objects, ClusDet's known failure case. ClusDet reports "28.4%" AP against "24.4%" for uniform tiling, using "approximately 40% fewer image forwards." We will check whether revisable search recovers objects outside clusters at equal forwards. On DOTA, the reference is Faster R-CNN Oriented at "54.13%" mAP. No reported number for ClusDet on DOTA was found on Lacuna, so we will generate that comparison ourselves.

Calibration. We will test the calibrated remaining-miss estimate on held-out PANDA scenes by checking that its stated coverage holds. As a stress test, we will measure how coverage degrades under the scene shift between PANDA's 21 locations.

Where the gain comes from. A positive result requires two things together: a clear margin over the static-ranking ablation on small objects, and a bounded-memory configuration within a modest time overhead of unbounded search. Absent either, the narrower conclusion is the one we would publish.