# Yes, we CANN: Constrained Approximate Nearest Neighbors for local feature-based visual localization

arXiv: https://arxiv.org/abs/2306.09012 · HTML: https://mlsanity.com/paper/2306.09012/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 53 references that are in the map.
- First posted on arXiv 15 Jun 2023.

## Builds on (most cited first, 22 of 22)

- [NetVLAD: CNN architecture for weakly supervised place recognition](https://mlsanity.com/paper/1511.07247/) (2015)
- [From Coarse to Fine: Robust Hierarchical Localization at Large Scale](https://mlsanity.com/paper/1812.03506/) (2018)
- [Fine-tuning CNN Image Retrieval with No Human Annotation](https://mlsanity.com/paper/1711.02512/) (2017)
- [Large-Scale Image Retrieval with Attentive Deep Local Features](https://mlsanity.com/paper/1612.06321/) (2016)
- [Image Matching across Wide Baselines: From Paper to Practice](https://mlsanity.com/paper/2003.01587/) (2020)
- [R2D2: Repeatable and Reliable Detector and Descriptor](https://mlsanity.com/paper/1906.06195/) (2019)
- [Back to the Feature: Learning Robust Camera Localization from Pixels to Pose](https://mlsanity.com/paper/2103.09213/) (2021)
- [Learning with Average Precision: Training Image Retrieval with a Listwise Loss](https://mlsanity.com/paper/1906.07589/) (2019)
- [Deep Visual Geo-localization Benchmark](https://mlsanity.com/paper/2204.03444/) (2022)
- [Learning and aggregating deep local descriptors for instance-level recognition](https://mlsanity.com/paper/2007.13172/) (2020)
- [DOLG: Single-Stage Image Retrieval with Deep Orthogonal Fusion of Local and Global Features](https://mlsanity.com/paper/2108.02927/) (2021)
- [Correlation Verification for Image Retrieval](https://mlsanity.com/paper/2204.01458/) (2022)
- [Large-scale, real-time visual-inertial localization revisited](https://mlsanity.com/paper/1907.00338/) (2019)
- [SOLAR: Second-Order Loss and Attention for Image Retrieval](https://mlsanity.com/paper/2001.08972/) (2020)
- [Benchmarking Image Retrieval for Visual Localization](https://mlsanity.com/paper/2011.11946/) (2020)
- [Detect-to-Retrieve: Efficient Regional Aggregation for Image Search](https://mlsanity.com/paper/1812.01584/) (2018)
- [Local Features and Visual Words Emerge in Activations](https://mlsanity.com/paper/1905.06358/) (2019)
- [Learning Super-Features for Image Retrieval](https://mlsanity.com/paper/2201.13182/) (2022)
- [Leveraging Deep Visual Descriptors for Hierarchical Efficient Localization](https://mlsanity.com/paper/1809.01019/) (2018)
- [Investigating the Role of Image Retrieval for Visual Localization -- An exhaustive benchmark](https://mlsanity.com/paper/2205.15761/) (2022)
- [Efficient Large Scale Inlier Voting for Geometric Vision Problems](https://mlsanity.com/paper/2107.11810/) (2021)
- [Further Results on Colored Range Searching](https://mlsanity.com/paper/2003.11604/) (2020)

## Built on by (most cited first, 4 of 4)

- [XFeat: Accelerated Features for Lightweight Image Matching](https://mlsanity.com/paper/2404.19174/) (2024)
- [Global-to-Local or Local-to-Global? Enhancing Image Retrieval with Efficient Local Search and Effective Global Re-ranking](https://mlsanity.com/paper/2509.04351/) (2025)
- [Weatherproofing Retrieval for Localization with Generative AI and Geometric Consistency](https://mlsanity.com/paper/2402.09237/) (2024)
- [Panoramic Distortion-Aware Tokenization for Person Detection and Localization in Overhead Fisheye Images](https://mlsanity.com/paper/2503.14228/) (2025)

## Abstract (arXiv)

Large-scale visual localization systems continue to rely on 3D point clouds built from image collections using structure-from-motion. While the 3D points in these models are represented using local image features, directly matching a query image's local features against the point cloud is challenging due to the scale of the nearest-neighbor search problem. Many recent approaches to visual localization have thus proposed a hybrid method, where first a global (per image) embedding is used to retrieve a small subset of database images, and local features of the query are matched only against those. It seems to have become common belief that global embeddings are critical for said image-retrieval in visual localization, despite the significant downside of having to compute two feature types for each query image. In this paper, we take a step back from this assumption and propose Constrained Approximate Nearest Neighbors (CANN), a joint solution of k-nearest-neighbors across both the geometry and appearance space using only local features. We first derive the theoretical foundation for k-nearest-neighbor retrieval across multiple metrics and then showcase how CANN improves visual localization. Our experiments on public localization benchmarks demonstrate that our method significantly outperforms both state-of-the-art global feature-based retrieval and approaches using local feature aggregation schemes. Moreover, it is an order of magnitude faster in both index and query time than feature aggregation schemes for these datasets. Code: urlhttps://github.com/google-research/google-research/tree/master/cann