Binary Descriptors for Efficient Matching and Retrieval in Large Image Databases


July 25, 2011


Pascal Fua


Over the last decade, feature point descriptors such as SIFT and similar methods have become indispensable tools in the computer vision community. They are usually represented as high-dimensional vectors, such as the 128-dimensional SIFT or the 64-dimensional SURF vectors. While the descriptor’s high dimensionality is not an issue when only a few hundreds points need to be represented, it becomes a significant concern when millions have to be on a device with limited computational and storage resources.

In this talk, we will therefore discuss our approach to turning such floating-point descriptors into compact binary ones that require far less storage space and can be matched much faster than floating-point ones at no loss in precision and recall.

Binarizing real-values descriptors is achieved first by projecting them using a matrix designed either to solely minimize the in-class covariance of the descriptors or to jointly minimize the in-class covariance and maximize the covariance across classes and then thresholding the resulting projections. Retrieving the resulting binary descriptors involves an Approximate Nearest Neighbor algorithm that is efficient in Hamming space, which most state-of-the-art algorithms are not.


Pascal Fua

Pascal Fua received an engineering degree from Ecole Polytechnique, Paris, in 1984 and the Ph.D. degree in Computer Science from the University of Orsay in 1989. He joined EPFL (Swiss Federal Institute of Technology) in 1996 where he is now a Professor in the School of Computer and Communication Science. Before that, he worked at SRI International and at INRIA Sophia-Antipolis as a Computer Scientist. His research interests include shape modeling and motion recovery from images, analysis of microscopy images, and Augmented Reality. He has (co)authored over 150 publications in refereed journals and conferences. He has been an associate editor of IEEE journal Transactions for Pattern Analysis and Machine Intelligence and has often been a program committee member, area chair, and program chair of major vision conferences.