Approximate search as a source coding problem, with application to large scale image and object recognition

Approximate search as a source coding problem, with application to large scale image and object recognition

Place: CVC - Large Lecture Room Affiliation: TEXMEX Research Team, INRIA, Rennes Cedex. FRANCE

Image recognition, which is used in many applications such as copy detection or location recognition, requires to handle and search into large databases of descriptors, typically in the order of billions of vectors. This raises an efficiency problem, but also the problem of memory resources.

In this talk, I will first discuss sp,e existing indexing techniques that address this problem. I will then show that the search problem can be cast into a source coding framework, where the database vectors are approximated by product quantization. The Euclidean distance between a query vector and a database vector is estimated in the compressed domain based on the quantized database descriptors, thanks to the properties of the product quantizer. The method is advantageously combined with an inverted file to avoid exhaustive search.

I will finally present some recent developments in this field, and demonstrate the effectiveness of my technique within an image search demonstrator.

  http://people.rennes.inria.fr/Herve.Jegou