Similarity-preserving binary code obtained from quantization can efficiently accelerate the retrieval of large-scale image collections. This paper presents iterative quantization (ITQ) that iteratively minimizes quantization error by rotating the data before quantization. ITQ can be couple with any projection of data onto an orthogonal basis. Experiment results show outstanding performance on the retrieval of large-scale image collections especially when the length of binary code is short.
Technical details and results

Idea of ITQ

Figure 1 illustrate the idea of rotating data before quantization to reduce quantization error.

![](http://2.bp.blogspot.com/-riBFQ71aWKk/VRI4Aprwx5I/AAAAAAAAAxw/ggFrB14UGlw/s1600/toy.png)

Figure 1. Toy illustration of the proposed ITQ method
The data points (blue points) are quantized to the closest vertex of the binary cube. By rotating the data points to that shown in Figure 1 (c), the quantization error is reduced and the partitioning respects the structure of the cluster.

ITQ in unsupervised code learning

Given a set of n data points and let each data point be d dimension, the data matrix is denoted by

$X \in \mathbb{R}^{n \times d}$

The binary code matrix can be computed by 

$B = sgn(XW)$ 

$W \in \mathbb{R}^{d \times c}$

where W denotes the projection matrix computed by PCA in this case.

Let R denote any c x c orthogonal matrix. The quantization error after projection and rotation of the data matrix is denotes by

$Q(B,R) = ||B - VR||^{2}_F$

$V = XW$

The ITQ method minimizes the quantization error by seeking optimal R. Because of the quantization operator, the quantization error is not a smooth function and direct minimization of the quantization error is impractical. This paper propose optimizing R and B alternately like k-mean algorithm.  When R is fixed, B is computed by


When B is fixed, R is computed by

$B = sgn(VR)$

where S and "S hat" are the left-singular vector and right-singular vector of the matrix 
         
$B^TV$

Figure 2 shows the quantization error for learning a 32-bit ITQ code on the CIFAR dataset.

![](http://4.bp.blogspot.com/-F6wZGT5fl3E/VRJW5U2VvFI/AAAAAAAAAzg/aEt4DIDpV6E/s1600/quantization%2Berror.png)

Results

"PCA-ITQ" in the legend of the figures denote the proposed method.


![](http://3.bp.blogspot.com/-WbVup__p9CQ/VRJTBh7NKpI/AAAAAAAAAx8/DCUvfo5Ijuw/s1600/result1.png)

![](http://2.bp.blogspot.com/-dj6F3pd5WiM/VRJTBvF6G5I/AAAAAAAAAyA/WyW7He4TJOw/s1600/result2.png)