Iterative Quantization: A Procrustean Approach to Learning Binary Codes

Yunchao Gong and Svetlana Lazebnik

Introduction

As the amount of image data is growing fast, encoding high dimensional image descriptor as compact binary string gains many benefits, like computation speed or storage. We generally use PCA directly to reduce the dimension of data. However, the variance of the data in each PCA direction is different, higher-variance directions carry much more information, encoding each direction with the same number of bits is bound to produce poor performance.

Dimension Reduction

We want to make the variance of each bit maximized and the bits are pairwise uncorrelated. We can do this by maximizing the objective function: 

Binary Quantization

Using binary code to represent data means we have to quantize the data into binary code. Of course, the smaller quantization error is better. The author found that we can randomly rotate the projected data

and

.

So we have to minimize the quantization loss function

The minimization procedure is iteratively do the following two steps:

(1)Fix R and update B

(2)Fix B and update R

Step (1) means we have to maximize

To do step (2), we first compute the SVD of B^T*V as A*B*C^T, and let R=C*A^T.

Evaluation

The accuracy line of this work is the most top one, means it's the best.

More result