Graph attribute encoding and sparse graph integral histograms for efficient aerial localization

Abstract

Visual localization for unmanned aerial vehicles in satellite-denied environments traditionally relies on matching onboard camera imagery to geospatial reference maps. However, direct image-based matching is highly susceptible to seasonal, environmental, and temporal variations. To overcome these limitations, we propose a modality-agnostic, graph-based visual localization pipeline that abstracts building neighborhoods into robust structural representations. By extracting building footprints and applying Delaunay triangulation, we construct spatial graphs where nodes represent buildings and edges encode their relative positions. To facilitate rapid and scalable matching within this framework, we introduce two methods: the bag-of-graph-attributes for generating efficient subgraph descriptors and the sparse graph integral histogram data structure for highly accelerated approximate subgraph search. Furthermore, this extended work investigates the pipeline’s structural breaking points by comparing synthetic graph perturbations against real-world artifacts from various segmentation models, alongside a graph neural network baseline. Because under-segmentation critically degrades matching performance by effectively deleting structural nodes, we integrate a topology-aware segmentation model utilizing a separation-preserving loss for instance topology to explicitly prevent instance merging. Comprehensive evaluations across four diverse datasets demonstrate that our end-to-end approach achieves over a 2000× speedup for reference graphs exceeding 150,000 nodes, maintains high retrieval accuracy under severe structural noise, and maximizes localization reliability in the presence of real-world detection errors.