We present a novel algorithm, Compact Kd-Trees (CompactKdt), that achieves state-of-the-art performance in searching large scale object image collections. The algorithm uses an order of magnitude less storage and computations by making use of both the full local features (e.g. SIFT) and their compact binary signatures to build and search the K-Tree. We compare classical PCA dimensionality reduction to three methods for generating compact binary representations for the features: Spectral Hashing, Locality Sensitive Hashing, and Locality Sensitive Binary Codes. CompactKdt achieves significant performance gain over using the binary signatures alone, and comparable performance to using the full features alone. Finally, our experiments show significantly better performance than the state-of-the-art Bag of Words (BoW) methods with equivalent or less storage and computational cost.

Distributed Kd-Trees is a method for building image retrieval systems that can handle hundreds of millions of images. It is based on dividing the Kd-Tree into a “root subtree” that resides on a root machine, and several “leaf subtrees”, each residing on a leaf machine. The root machine handles incoming queries and farms out feature matching to an appropriate small subset of the leaf machines. Our implementation employs the MapReduce architecture to efficiently build and distribute the Kd-Tree for millions of images. It can run on thousands of machines, and provides orders of magnitude more throughput than the state-of-the-art, with better recognition performance. We show experiments with up to 100 million images running on 2048 machines, with run time of a fraction of a second for each query image.

Indexing quickly and accurately in a large collection of images has become an important problem with many applications. Given a query image, the goal is to retrieve matching images in the collection. We compare the structure and properties of seven different methods based on the two leading approaches: voting from matching of local descriptors vs. matching histograms of visual words, including some new methods. We derive theoretical estimates of how the memory and computational cost scale with the number of images in the database. We evaluate these properties empirically on four real-world datasets with different statistics. We discuss the pros and cons of the different methods and suggest promising directions for future research.

Gathering a large collection of images has been made quite easy by social and image sharing websites, e.g. flickr.com. However, using such collections faces the problem that they contain a large number of duplicates and highly similar images. This work tackles the problem of how to automatically organize image collections into sets of similar images, called image families hereinafter. We thoroughly compare the performance of two approaches to measure image similarity: global descriptors vs. a set of local descriptors. We assess the performance of these approaches as the problem scales up to thousands of images and hundreds of families. We present our results on a new dataset of CD/DVD game covers.