Lost in the Tail: Addressing Geographic Imbalance in Urban Visual Place Recognition

Conference: ECCV 2026
arXiv: 2607.00090
Code: To be confirmed (compute provided by Lambda, code in preparation)
Area: Image Retrieval / Visual Localization
Keywords: Long-tailed Distribution, Visual Place Recognition, Geographic Imbalance, Distribution-aware, Characteristic Function Distance

TL;DR

This paper identifies a severe long-tailed geographic distribution issue (head-to-tail sample ratio up to 300:1) in city-scale visual place recognition datasets. It proposes the DAPR framework: during training, it uses Low-visit Bias Loss for inverse-frequency weighting and classifier bias calibration; during inference, it employs characteristic function distance in the frequency domain for distribution-aware re-ranking, outperforming the previous state-of-the-art hybrid pipeline on the SF-XL benchmark by 18.3% R@1.

Background & Motivation

Visual Place Recognition (VPR) aims to localize a query image in a geo-tagged reference database, which is a foundational capability for city-scale applications such as autonomous driving and patrol robotics. Recently, classification-based VPR methods partition city maps into discrete geographic grid cells (e.g., 20m×20m cells), treating each cell as a category and training a classifier to learn discriminative place descriptors. During inference, the classifier first filters the entire database, followed by similarity retrieval within the candidate pool. However, current VPR datasets (such as SF-XL, GSV-Cities, MSLS) rely heavily on Google Street View or crowdsourcing platforms for data collection. Consequently, image density is largely determined by traffic flow and photographer frequency rather than the richness of geographic features. This implies that bustling main roads accumulate thousands of training images, whereas residential areas, alleys, and low-traffic urban corridors—which happen to exhibit the highest intra-class visual diversity—contain only a dozen or even a few training samples.

This geographic imbalance is far more severe than expected. Taking the SF-XL benchmark as an example, sorting the geographic categories by sample count into head (top 30%), middle (40%), and tail (bottom 30%) reveals a head-to-tail sample ratio of approximately 300:1. Head categories contain over 3,000 images, whereas tail categories have as few as 12. Ironically, the authors' quantitative analysis reveals that the variance of pairwise feature similarity within tail categories is actually larger—meaning that those areas, which are already the most difficult to recognize due to their rich visual content, receive the least training signals. The per-class Recall@1 curve drops precipitously in the tail categories, yet safety-critical application scenarios (such as autonomous patrol robots in GPS-denied environments) rely most heavily on reliable localization in these exact areas. Existing methods completely overlook this conflict: classifiers rely on L2 distance for post-filtering re-ranking, and L2 distance treats all classes equally. As a result, the compact and dense representation of head categories naturally dominates matching, systematically underestimating the tail categories.

Core Idea: The Distribution-Aware Place Recognition (DAPR) framework is proposed. During training, the LB Loss balances gradient contributions across categories using inverse-frequency weighting coupled with prior logit calibration. During inference, for hybrid pipeline scenarios, Characteristic Function Distance (CFD) is utilized in the frequency domain for distribution-aware re-ranking, ensuring that the dense, compact representations of head categories no longer dominate matching decisions.

Method

Overall Architecture

DAPR is a model-agnostic, plug-and-play framework containing two core modules deployed at the training and inference stages, respectively. Training stage: Given a long-tailed geographic image dataset, features are first extracted using DINOv2, and then the feature extractor and classifier are trained via the LB Loss. The LB Loss couples three mechanisms—inverse-frequency sample weighting (amplifying tail gradients), prior logit calibration (boosting tail logits), and large-margin cosine similarity (separating inter-class boundaries)—to eliminate training bias caused by the long-tailed distribution. Inference stage (hybrid pipeline scenario): The classifier filters the entire database to a candidate category pool (~450 categories per query for SF-XL). CFD is then applied to perform frequency-domain re-ranking on this candidate pool, comparing the compactness (amplitude) and directional alignment (phase) of feature distributions to ensure a fair comparison between head and tail categories.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Long-tailed Geo-images<br/>Head-to-tail ratio ~300:1"] --> B["DINOv2 Feature Extraction"]
    B --> C["LB Loss Training:<br/>Inverse-frequency Weighting<br/>+ Logit Calibration<br/>+ Large-margin Cosine Loss"]
    C --> D["Balanced Embeddings<br/>+ Classifier Weights"]
    D --> E["Inference: Classifier Filtering<br/>Database -> Candidate Pool<br/>(~450 classes/query)"]
    E --> F["CFD Frequency Re-ranking:<br/>Amplitude (Compactness) +<br/>Phase (Directional Alignment)"]
    F --> G["Top-K Localization Results"]

Key Designs

1. LB Loss (Low-visit Bias Loss): Inverse-Frequency Weighting coupled with Prior Logit Calibration

The motivation for the LB Loss stems directly from statistical observations: head categories have many samples, and their gradients dominate each optimization step, causing tail signals to be drowned out by noise. Simply amplifying tail gradients might lead to divergence due to a small number of samples becoming outliers. The LB Loss solves this by integrating three mechanisms into a single loss function, sharing a single class frequency prior \(p_c = n_c/N\).

First, class distribution re-weighting is performed. Each category \(c\) is assigned a weight \(w_c \propto (p_c + \epsilon)^{-\beta}\), normalized to ensure gradient magnitude stability, where \(\beta \in [0,1]\) controls the strength of re-weighting. This means that each training sample in the tail categories receives a higher weight in the loss function, thereby amplifying their contribution to the gradients. Second, prior logit calibration is applied: a class-frequency-dependent bias term \(\nu_c = -\kappa \log(p_c / (1-p_c))\) is added to the classifier's logit, where \(\kappa\) controls the calibration strength. Since \(p_c\) is very small for tail categories, \(\nu_c\) is positive. During classification, the model adds a positive bias to the tail logit by default, compensating for the prior imbalance at the decision boundary level. Finally, these two terms are embedded into a large-margin cosine loss (for classification paradigms) or a multi-similarity loss (for retrieval paradigms). Taking the classification version \(L^{cls}_{lb}\) as an example, it enforces inter-class separation via the angular margin of CosFace, and then embeds the weight \(w_c\) and bias \(\nu_c\) into the softmax cross-entropy. Ablation studies show that all three components are indispensable—using any single mechanism alone cannot match the performance of their joint application, and the LB Loss improves the baseline cross-entropy on the SF-XL hybrid pipeline by 13.9% R@1.

2. CFD (Characteristic Function Distance): Multi-scale Frequency-Domain Distance Search

The LB Loss corrects training bias, but distribution imbalance persists during inference. Although the hybrid pipeline filters the full database to a candidate pool, heterogeneity in feature distributions still exists within the candidate pool: feature clusters of head categories are tight and compact, whereas those of tail categories are sparse and dispersed. Under standard L2 or cosine similarity, their distributional shapes are ignored, and queries for tail categories are systematically biased toward the nearest head category clusters.

The key insight of CFD is that mapping features to the frequency domain naturally exposes distribution compactness as amplitude and directional similarity as phase. For a query feature set \(S_q\) and a candidate category \(j\) feature set \(S_j\), the empirical characteristic functions \(\Phi_q(t_k)\) and \(\Phi_j(t_k)\) are calculated over \(K\) frequency points \(\mathbf{T}=\{t_k\}_{k=1}^K\). According to Euler's formula \(\Phi(t_k)=|Φ(t_k)|e^{iα(t_k)}\), the amplitude \(|Φ(t_k)|\) encodes the compactness of the set—tight clusters yield higher amplitudes, while dispersed clusters yield lower amplitudes—and the phase \(α(t_k)\) encodes the spatial direction of features. The frequency points \(\mathbf{T}\) are hierarchically sampled from 4 log-scale isotropic Gaussian distributions to capture both fine-grained local patterns and global structures.

To balance the roles of amplitude and phase in matching, CFD introduces adaptive weighting: it first computes the average amplitude ratio between the query and candidate categories \(r^{(j)}=\bar{A}_q/\bar{A}_j\) (compactness ratio), and then obtains the amplitude weight \(α_w^{(j)}=\min(α \cdot r^{(j)}, 1)\) and phase weight \(λ_w^{(j)}=1-α_w^{(j)}\). The final distance is a weighted average of two components: amplitude difference (squared difference) and phase difference (circular distance with \(2\pi\) wrapping), each multiplied by their adaptive weights and summed. When a candidate category's feature distribution is sparse (common in tail categories), \(\bar{A}_j\) is small, \(r^{(j)}\) becomes larger, and the amplitude weight dominates. Consequently, CFD prioritizes compactness over directional alignment, inherently creating a fairer comparison for tail categories. Remarkably, this \(r^{(j)}\) also serves as a confidence estimator for the query (a high amplitude ratio implies tight features and more reliable matching), requiring no extra stochastic embeddings or post-processing. CFD is strictly used during inference because computing characteristic functions for over 110,000 classes during training would incur \(O(B \times C \times K \times D)\) complexity, making it computationally intractable.

Loss & Training

The LB Loss comes in two versions. The classification version is based on the large-margin cosine loss:

\[L^{cls}_{lb} = -w_c \cdot \log\left(\frac{\exp(z_c - \nu_c)}{\sum_{j=1}^C \exp(z_j - \nu_j)}\right)\]

where \(z_j = s \cdot (d - m \cdot \mathbb{I}[j=c])\), \(d\) is the cosine similarity between the feature and classifier weights, \(s\) is the scaling factor, and \(m\) is the angular margin. The retrieval version embeds the inverse-frequency weight \(w_{y_i}\) and logit bias \(\nu_{y_j}\) into the multi-similarity loss. Training is conducted with a DINOv2 backbone, Adam optimizer, a batch size of 256, and a learning rate of \(6 \times 10^{-6}\) for 200 epochs. In the classification pipeline, \(\beta=0.01\) and \(\kappa=0.05\); in the retrieval pipeline, \(\kappa=0.01\). During inference, the amplitude base weight of CFD is set to \(\alpha=0.7\).

Key Experimental Results

Main Results

Method	Backbone	Inference Time	R@1 v1	R@1 v2
D&C (Hybrid Baseline)	EfficientNet	30 ms	71.4	87.6
SALAD (Retrieval-only)	DINOv2	4805 ms	87.6	93.5
BoQ (Retrieval-only)	DINOv2	21333 ms	83.7	92.8
SALAD* (+LB Loss)	DINOv2	4823 ms	88.0	94.5
BoQ* (+LB Loss)	DINOv2	21047 ms	88.8	93.7
DAPR-M (Ours, Hybrid)	DINOv2	74 ms	89.7	94.3

DAPR-M outperforms all retrieval-only methods (4 to 21 seconds) on test v1 with an inference time of only 74 ms, while substantially surpassing the D&C hybrid baseline (by +18.3% / +6.7%) on test v1/v2. The plug-and-play efficacy of LB Loss is also verified on SALAD and BoQ.

Ablation Study

Configuration	R@1 v1	R@1 v2	Description
DINOv2 + CE + L2	75.8	91.1	Baseline
+ LB Loss (Replacing CE)	88.0	93.8	+12.2% / +2.7%
+ LB Loss + CFD (Replacing L2)	89.7	94.3	+1.7% / +0.5%
LogitAdjust Loss Alternative	88.0	93.3	Calibration-only
Focal Loss Alternative	86.4	94.0	Hard-sample weighting-only
Ours LB Loss (Joint)	89.7	94.3	Weighting + Calibration + Large Margin

The ablation study indicates that LB Loss is the primary contributor to performance improvement (+12.2%), with CFD providing an additional +1.7%. LB Loss outperforms both LogitAdjust (calibration-only) and Focal Loss (weighting-only), confirming the necessity of coupling the two mechanisms.

Key Findings

• LB Loss brings consistent improvements across different backbones (EfficientNet, ResNet101, DINOv2) and pipelines (classification-only, retrieval-only, hybrid), indicating that geographic long-tailed distribution is a data-level bottleneck rather than a model-specific issue.
• Performance breakdown across head/middle/tail categories shows that the tail category achieves the greatest gains (+1.47% R@1, +7.35% R@5), validating that the LB Loss successfully targets its design objective of correcting the neglected tail regions.
• CFD outperforms L2 by 5.6% R@1 on the tail categories (test v1), confirming that the frequency-domain amplitude component effectively captures the distribution compactness of sparse features.
• The memory footprint of the DAPR-M hybrid pipeline is only 1.35 MB (for a candidate pool of 450 768-d descriptors), compared to 94.8 GB for the retrieval-only SALAD, making large-scale city deployment highly practical.
• LB Loss yields consistent tail category improvements on multi-city benchmarks such as MSLS and Pitts30k (BoQ* achieves +2.70% R@1 on MSLS tail categories), verifying its cross-city generalization performance.

Highlights & Insights

• Problem discovery itself is a contribution: This work is the first to systematically identify the 300:1 long-tailed geographic distribution in city-scale VPR datasets. It quantitatively proves that tail regions (characterized by low traffic volume but high visual diversity) are precisely where safety-critical deployment scenarios (e.g., patrol robots, GPS-denied zones) are concentrated, directly highlighting the practical urgency of this problem.
• The "three-mechanism coupling" of LB Loss is highly informative: Combining inverse-frequency weighting (gradient rebalancing) + logit calibration (decision boundary correction) + large-margin cosine loss (feature discriminability), all sharing the same class prior \(p_c\), complements each other seamlessly. Removing any single component during ablation degrades performance—this rigorously coupled ablation design serves as a methodological exemplar.
• The adaptive weight design of CFD is elegant: \(r^{(j)}=\bar{A}_q/\bar{A}_j\) naturally encodes "the compactness of the query relative to the candidate classes", automatically amplifying the amplitude weight for tail categories. It accomplishes implicit confidence estimation during retrieval without requiring extra training.
• Huge victory for computational efficiency: The hybrid pipeline + compact candidate pool (450 vs. 2.8 million for the full database) + a single DINOv2 backbone achieves or even surpasses the accuracy of retrieval-only methods (which take seconds per query) in only 74 ms per query—a crucial and decisive factor for large-scale real-world deployment.

Limitations & Future Work

• Currently, the long-tail definition relies entirely on sample counts per geographic class, ignoring "feature-level long-tails." Even if a class has sufficient samples, it remains challenging if its intra-class features vary drastically (e.g., across seasons or times of day). The authors note this as a valuable path for future exploration.
• CFD is used only during inference because computing characteristic functions for over 110,000 classes during training exhibits \(O(B \times C \times K \times D)\) complexity, rendering it computationally unfeasible. While a practical trade-off, this creates a mismatch risk by using different distance behaviors during training and inference.
• Adaptive partitioning (such as the k-d tree algorithm in CPlaNet, which adjusts boundaries to make class sample counts similar) and LB Loss address imbalance at different levels (data layout vs. learning signal). The paper only compares them individually instead of discussing their complementarity—combining adaptive partitioning as a first step with LB Loss for fine-grained calibration could potentially yield better results.
• Experiments are heavily concentrated on San Francisco (SF-XL), Pittsburgh (Pitts30k), and the multi-city MSLS benchmark, lacking extreme cross-domain testing (such as generalizing from urban to rural/forest environments). Whether the improvements on tail classes hold up in these scenarios remains undetermined.
• Failure analysis indicates that DAPR still struggles under dense canopy occlusion and extreme color/lighting changes. These issues are intrinsically feature-level mismatches that cannot be entirely solved by resolving sample-count-level long-tailed class distribution.

Related Work & Insights

• vs. D&C: D&C first proposed a hybrid classification-retrieval pipeline to boost inference efficiency for large-scale VPR, but used L2 distance which treats all classes equally. The key improvement of this work lies in identifying that L2 distance is unjust to tail classes, replacing standard distance metrics with CFD.
• vs. generic long-tailed learning methods (LogitAdjust, Focal Loss): LA only performs logit calibration, and FL only performs hard-sample weighting—each addressing only one mode of failure. LB Loss couples both and stacks large-margin cosine loss, surpassing both on the VPR task.
• vs. CosPlace / EigenPlaces: These methods also implement geographic grid classification + large-margin cosine loss, but implicitly assume category uniformity, overlooking the 300:1 sample count discrepancy across grids.
• vs. SALAD / BoQ (DINOv2 retrieval-only methods): These methods perform direct similarity searches over the full database. Although highly accurate, they incur massive memory and time overheads. This work demonstrates that hybrid pipelines remain highly competitive in the DINOv2 era—DAPR-M (74 ms) is 60 times faster than SALAD (4.8 s) with superior accuracy.

Rating

• Novelty: ⭐⭐⭐⭐ The identification of the problem (long-tailed geographic distribution) is a systematic first in the VPR field, although the methodology itself is an elegant synthesis of mature long-tailed learning techniques rather than a fundamentally brand-new framework.
• Experimental Thoroughness: ⭐⭐⭐⭐⭐ Verified across five benchmarks (SF-XL v1/v2, MSLS, Pitts30k, Nordland) with solid ablation studies, clear head/middle/tail stratified analysis, and thorough hyperparameter sensitivity checks.
• Writing Quality: ⭐⭐⭐⭐ The motivation and significance of the problem are well-articulated. The comparison in Figure 1 between the 300:1 imbalance and the wider diversity of tail classes is compelling. The equations are slightly dense but follow a logical sequence.
• Value: ⭐⭐⭐⭐⭐ Plug-and-play, model-agnostic, introduces zero inference overhead, and brings notable improvements—this combination of high practical utility and clear problem identification is highly favored in realistic engineering deployment scenarios.

Related Papers

• [CVPR 2026] HypeVPR: Exploring Hyperbolic Space for Perspective to Equirectangular Visual Place Recognition
• [ICCV 2025] A Hyperdimensional One Place Signature to Represent Them All: Stackable Descriptors For Visual Place Recognition
• [NeurIPS 2025] Addressing Mark Imbalance in Integration-free Neural Marked Temporal Point Processes
• [CVPR 2026] Drainage: A Unifying Framework for Addressing Class Uncertainty
• [CVPR 2026] Spectral Conformal Risk Control: Distribution-Free Tail Guarantees via Bayesian Quadrature