Iterative Quantization: A procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval
Yunchao Gong, Svetlana Lazebnik, Albert Gordo, Florent Perronnin
This paper addresses the problem of learning similarity-preserving binary codes for efficient similarity search in
large-scale image collections. We formulate this problem in terms of finding a rotation of zero-centered data so as to minimize
the quantization error of mapping this data to the vertices of a zero-centered binary hypercube, and propose a simple and efficient
alternating minimization algorithm to accomplish this task. This algorithm, dubbed iterative quantization (ITQ), has connections
to multi-class spectral clustering and to the orthogonal Procrustes problem, and it can be used both with unsupervised data
embeddings such as PCA and supervised embeddings such as canonical correlation analysis (CCA). The resulting binary codes
significantly outperform several other state-of-the-art methods. We also show that further performance improvements can result
from transforming the data with a nonlinear kernel mapping prior to PCA or CCA. Finally, we demonstrate an application of ITQ
to learning binary attributes or “classemes” on the ImageNet dataset.
Published in IEEE Transactions on Pattern Analysis and Machine Intelligence, special issue of best CVPR papers.