Remembering Where Tiny Objects Were: Graph-Guided Sparse High-Resolution Detection for Video

Detectors lose very small objects, such as a distant drone or a vehicle a few pixels wide in aerial video, because their prediction layers look at the image at coarse resolution. The standard fix adds a fourth "P2" prediction head that reads features at one quarter of the input resolution, but running it densely over the whole frame is expensive. QueryDet's approach is to let a cheap coarse-resolution head guess where small objects might be and to evaluate the fine head only at those spots. That makes a single blurry or occluded frame fatal: if the coarse guess misses an object, the fine head never looks there. We propose to let the video's recent past decide where the fine head looks. A small graph over recently seen tiny-object candidates, with edges linking neighbors in space and matches across frames, predicts where each candidate should be now and whether it probably still exists. Those predictions are added to the coarse head's guesses as extra places to evaluate the fine head.

The claim is narrow and testable. When high-resolution computation is restricted to a sparse set of locations, the main limit on tiny-object recall in video comes from time, not from the fine features themselves. A spatio-temporal graph over candidates should recover objects that single-frame querying drops, at almost no extra cost. It should also beat simply projecting each old detection forward on its own, specifically in the conditions where neighbors carry information: camera ego-motion, dense groups such as convoys, and occlusions lasting several frames. If per-object forward projection matches the graph, the graph part of the claim is false, and the experiments are built to show that plainly.

What Exists and What Is Missing

Dedicated fine-resolution heads are well established for single images. Some works append a fourth head for extremely small road hazards (A Multi-Scale Traffic Object Detection Algorithm for Road Scenes Based on Improved YOLOv5) or a 104×104 prediction stage for scattered poppy plants (Low-Altitude Remote Sensing Opium Poppy Image Detection Based on Modified YOLOv3). Others remove the coarsest head entirely when no large objects appear (Li et al., Wang et al.). These works motivate our use of a fine head, but none of them has any temporal mechanism.

QueryDet supplies our core efficiency mechanism. It reports that a dense P2 head costs about 300% more computation and drops throughput from 13.6 to 4.85 FPS, and that sparse querying gives a 3.0× speedup while still improving small-object accuracy. QueryDet also documents the failure mode we target: an object the coarse head misses is lost for good. We keep its sparse evaluation of the fine head and change only where the query locations come from.

Video small-object detectors add time in other ways. XS-VID / YOLOFT fuses a multi-scale correlation pyramid (an optical-flow-like comparison of consecutive frames) into standard YOLOv8 levels. TransVisDrone runs a video transformer over P3–P5 features. TDCNet embeds frame differencing into 3D convolutions for infrared targets. All three work densely on regular grids and do not use a sparse fine head. They are our competitors on accuracy, not sources of our method.

Two works come closest in using graphs or topology for video. MSGNet builds sparse top-k patch graphs, but for aligning RGB with thermal imagery and matching adjacent frames, and it predicts on standard YOLOv8 heads. The UAV tracking work with TFAM and TIEM uses deformable attention to encode object-to-context topology, which yields MOTA and IDF1 gains on VisDrone2019 and UAVDT. Its topology serves re-identification embeddings rather than deciding where to compute, and it saturates at a history of two frames. Our graph instead exists to choose where the expensive fine head is evaluated.

From traffic forecasting we borrow the graph design itself: decoupled spatial and temporal attention in the style of GMAN, which also reports robustness when most history is missing. That robustness is exactly the regime of intermittently visible tiny objects. We keep the graph shallow because stacked graph layers are known to blur node features together (over-smoothing). This is a real risk when the nodes are small objects with similar appearance.

Core Mechanism

The detector is YOLOv8 with P2, P3 and P4 heads, a QueryDet-style query head on P3, and sparse convolution on P2. Alongside it we maintain a candidate memory. The nodes are the fine-head detections from the last $T$ frames (we will test $T$ from 2 to 8) plus high-scoring query-head cells. The memory is capped at a few hundred nodes, so graph computation stays negligible next to the backbone.

Each node carries four things: its P2 feature vector, its box, its confidence, and its age. Spatial edges connect each node to its $k$ nearest candidates within the same frame. Temporal edges connect candidates in consecutive frames that are close in position and similar in feature.

Two to three alternating layers of spatial and temporal attention then produce two outputs per node: a predicted displacement $\Delta_i$ into the current frame $t$, and a persistence probability $p_i$ that the object still exists. The fine head at frame $t$ is evaluated on

$$Q_t = Q^{\text{coarse}}_t \cup \{\, \mathcal{N}(x_i + \Delta_i) : p_i > \tau \,\},$$

where $Q^{\text{coarse}}_t$ is the set of locations flagged by the query head, $x_i$ is node $i$'s last position, $\mathcal{N}(\cdot)$ is a small P2 neighborhood around a point, and $\tau$ is a threshold. The new detections, with their P2 features, become the next frame's nodes. A secondary use of the same outputs is to rescore detections by $p_i$. The aim is to suppress static textured clutter that appears once and never moves consistently, which is the false-positive problem that shallow heads are known to have.

Training supervises three outputs. Displacement is supervised on VisDrone and UAVDT, which have track identities. XS-VID boxes will be linked across frames by nearest-neighbor matching, with the matching noise reported. Persistence is supervised by whether the ground-truth object is present at frame $t$. A query-recall loss rewards $Q_t$ for covering ground-truth tiny objects. It is charged against a fixed query budget, so the graph cannot win simply by querying everywhere.

We expect the graph to beat per-object extrapolation for a specific reason. Under ego-motion, every node shifts coherently, and spatial attention can pool that shared shift. In a formation, a neighbor's motion predicts where a missing member should be. A lone per-track motion model sees neither.

Baselines

The naive reference is static YOLOv8 with P3–P5 heads, reported at 33.6 AP on XS-VID in XS-VID. We add a static dense P2 variant to measure how much a fine head alone contributes and what it costs.

The main mechanistic competitor is single-frame sparse querying: QueryDet's cascade sparse query re-implemented on our exact YOLOv8 P2–P4 backbone. QueryDet reports +2.1 mAP over its baseline and a 2.3× speedup on VisDrone, but no absolute VisDrone value is in the file, so we will re-run it rather than quote a number.

The strongest published video competitor is YOLOFT-L, at 36.4 AP on XS-VID in XS-VID. We will train it with its released recipe and also retrain it on our backbone and schedule.

The ablation that isolates the key ingredient is Kalman carry-forward querying. It is identical to our system except that each past detection is projected forward by a constant-velocity Kalman filter, with Hungarian association, and added to $Q_t$, with no graph at all. A second ablation keeps the temporal edges but removes the spatial edges, isolating what neighbor message passing contributes. A third lets a recurrent convolutional network (ConvGRU) carry the P3 query heatmap across frames, which is grid-based temporal memory with no nodes.

All systems will share the same training data, input resolution (1024 on XS-VID), epochs, augmentation, and tuning budget, which is an equal number of hyperparameter trials per method. All sparse methods will be compared at matched query budgets and reported on accuracy-versus-FLOPs curves.

Beating the field means three things. First, exceeding the re-run YOLOFT-L on XS-VID extremely-small AP at lower FLOPs. Second, exceeding single-frame sparse querying on extremely-small AP at equal query budget. Third, and decisively for the graph, exceeding Kalman carry-forward by a margin larger than seed variance across three seeds in the stratified conditions described below.

Why not just…?

Why not just carry previous detections forward with a Kalman filter? This is the most serious threat. It directly fixes QueryDet's dropout for objects that were recently detected. Nothing in the file shows that graph message passing beats per-track extrapolation for choosing where to query, so we treat it as an open question rather than a settled one. The ablation above answers it. We will stratify test frames by camera ego-motion magnitude, by the number of neighbors within a fixed radius, and by occlusion length. If the graph's advantage is not concentrated in high-ego-motion, dense, or long-occlusion frames, we will report that carry-forward suffices and recast the contribution as temporal querying without the graph.

Why not just run a dense P2 head with flow-style motion features, as YOLOFT does? Dense P2 is the recall ceiling for any sparse method, and we report it as such. Its cost is documented, though: QueryDet measures a drop from 13.6 to 4.85 FPS. YOLOFT's authors also report that correlation pyramids lose scale awareness when larger objects move in complex ways. Our accuracy-per-FLOP curves show whether sparse graph querying reaches dense-P2-plus-motion accuracy at a fraction of the cost.

Why not just lower QueryDet's threshold? A lower threshold raises recall only by querying more of the frame, which moves toward dense cost. It also cannot help when the coarse evidence is truly absent, as in a blurred frame. Plotting recall against query budget for both methods settles this. If the graph helps, its curve should dominate the threshold sweep at every budget.

Why not just use a video transformer or recurrent memory on the coarse maps? TransVisDrone had to drop from 1280p to 640p for real-time throughput, losing 3% AP, and that was without a P2 head. The ConvGRU-heatmap ablation tests the cheapest version of this idea. It is a fair competitor, and if it matches the graph at equal cost, we will say so.

Proposed Experiments

The primary benchmark is XS-VID, reported as AP split into extremely small, relatively small, and generally small objects. VisDrone video and UAVDT test transfer to a setting with track identities. We also add the MOTA and IDF1 tracking metrics there, because persistence-based rescoring should propagate into tracking.

The central diagnostic is query recall: the fraction of ground-truth extremely small objects whose location lies inside $Q_t$. We measure it on "dropout frames," where the single-frame query head misses an object that was detected within the previous $T$ frames. Query recall is reported jointly with FLOPs and FPS.

The decisive checks come in two stages. First, graph-guided querying must raise query recall on dropout frames over single-frame querying at equal budget; if it does not, the premise fails. Second, it must beat Kalman carry-forward in the high-ego-motion and high-density strata. We also run the removed-spatial-edge ablation and a sweep over history length $T$. The sweep tests whether the graph uses longer history than the two frames at which the TFAM/TIEM tracker saturated. A final exploratory probe asks whether graph context can replace a pruned P5 head, as in the heads-pruned designs cited above, without losing accuracy on relatively small objects.