Scalable Recognition with a Vocabulary Tree

TLDR

The scheme builds on popular local‑descriptor indexing techniques and is robust to background clutter and occlusion. The authors present a recognition scheme that scales efficiently to a large number of objects. The scheme hierarchically quantizes local‑region descriptors in a vocabulary tree, fully integrating quantization and indexing, and evaluates recognition quality via retrieval on a database with ground truth, demonstrating scalability to up to one million images. The vocabulary tree yields dramatic improvements in retrieval quality, enabling live recognition of CD covers from a 40,000‑image database and scaling to one million images, with the tree’s direct quantization being a key advantage.

Abstract

A recognition scheme that scales efficiently to a large number of objects is presented. The efficiency and quality is exhibited in a live demonstration that recognizes CD-covers from a database of 40000 images of popular music CD’s. The scheme builds upon popular techniques of indexing descriptors extracted from local regions, and is robust to background clutter and occlusion. The local region descriptors are hierarchically quantized in a vocabulary tree. The vocabulary tree allows a larger and more discriminatory vocabulary to be used efficiently, which we show experimentally leads to a dramatic improvement in retrieval quality. The most significant property of the scheme is that the tree directly defines the quantization. The quantization and the indexing are therefore fully integrated, essentially being one and the same. The recognition quality is evaluated through retrieval on a database with ground truth, showing the power of the vocabulary tree approach, going as high as 1 million images.