Size Matters: Exhaustive Geometric Verification for Image Retrieval

The overreaching goals in large-scale image retrieval are bigger,
better and cheaper. For systems based on local features we show
how to get both efficient geometric verification of every match
and unprecedented speed for the low sparsity situation.

Large-scale systems based on quantized local
features usually process the index one term at a time,
forcing two separate scoring steps: First, a scoring step
to find candidates with enough matches, and then a geometric
verification step where a subset of the candidates are checked.

Our method searches through the index a document at a time,
verifying the geometry of every candidate in a single pass.
We study the behavior of several algorithms with respect to index density---a
key element for large-scale databases. In order to further improve the
efficiency we also introduce a new
new data structure, called the counting min-tree, which outperforms other approaches
when working with low database density, a necessary condition for very large-scale systems.

We demonstrate the effectiveness of our approach with a proof of concept
system that can match an
image against a database of more than 90~billion images in just a few seconds.

• Machine Perception