Yes, We CANN: Constrained Approximate Nearest Neighbors for Local Feature-Based Visual Localization

Abstract

Large-scale visual localization systems continue to relyon 3D point clouds built from image collections usingstructure-from-motion. While the 3D points in these modelsare represented using local image features, directly match-ing a query image's local features against the point cloud ischallenging due to the scale of the nearest-neighbor searchproblem. Many recent approaches to visual localization havethus proposed a hybrid method, where first a global (per im-age) embedding is used to retrieve a small subset of databaseimages, and local features of the query are matched onlyagainst those. It seems to have become common belief thatglobal embeddings are critical for said image-retrieval invisual localization, despite the significant downside of hav-ing to compute two feature types for each query image. Inthis paper, we take a step back from this assumption and pro-pose Constrained Approximate Nearest Neighbors (CANN),a joint solution of k-nearest-neighbors across both the ge-ometry and appearance space using only local features. Wefirst derive the theoretical foundation for k-nearest-neighborretrieval across multiple metrics and then showcase howCANN improves visual localization. Our experiments onpublic localization benchmarks demonstrate that our methodsignificantly outperforms both state-of-the-art global feature-based retrieval and approaches using local feature aggrega-tion schemes. Moreover, it is an order of magnitude faster inboth index and query time than feature aggregation schemesfor these datasets. Code will be released.