Size Matters: Exhaustive Geometric Verification for Image Retrieval
12th European Conference on Computer Vision (ECCV), Springer (2012), pp. 674-687
Henrik Stewenius, Steinar H. Gunderson, Julien Pilet
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.