![](https://csdnimg.cn/release/download_crawler_static/10138387/bg3.jpg)
2
[21] uses a binary signature to refine quantized SIFT
or GIST descriptors in a bag-of-features image search
framework.
In this paper, we construct short codes using quanti-
zation. The goal is to estimate distances using vector-
to-centroid distances, i.e., the query vector is not quan-
tized, codes are assigned to the database vectors only.
This reduces the quantization noise and subsequently
improves the search quality. To obtain precise distances,
the quantization error must be limited. Therefore, the
total number
k of centroids should be sufficiently large,
e.g., k = 2
64
for 64-bit codes. This raises several issues
on how to learn the codebook and assign a vector. First,
the number of samples required to learn the quantizer
is huge, i.e., several times
k. Second, the complexity of
the algorithm itself is prohibitive. Finally, the amount of
computer memory available on Earth is not sufficient to
store the floating point values representing the centroids.
The hierarchical k-means see (HKM) improves the
efficiency of the learning stage and of the corresponding
assignment procedure [15]. However, the aforementioned
limitations still apply, in particular with respect to mem-
ory usage and size of the learning set. Another possibility
are scalar quantizers, but they offer poor quantization er-
ror properties in terms of the trade-off between memory
and reconstruction error. Lattice quantizers offer better
quantization properties for uniform vector distributions,
but this condition is rarely satisfied by real world vectors.
In practice, these quantizers perform significantly worse
than k-means in indexing tasks [22]. In this paper, we
focus on product quantizers. To our knowledge, such a
semi-structured quantizer has never been considered in
any nearest neighbor search method.
The advantages of our method are twofold. First, the
number of possible distances is significantly higher than
for competing Hamming embedding methods [20], [17],
[19], as the Hamming space used in these techniques
allows for a few distinct distances only. Second, as a
byproduct of the method, we get an estimation of the
expected squared distance, which is required for
ε-radius
search or for using Lowe’s distance ratio criterion [23].
The motivation of using the Hamming space in [20],
[17], [19] is to compute distances efficiently. Note, how-
ever, that one of the fastest ways to compute Hamming
distances consists in using table lookups. Our method
uses a similar number of table lookups, resulting in
comparable efficiency.
An exhaustive comparison of the query vector with all
codes is prohibitive for very large datasets. We, therefore,
introduce a modified inverted file structure to rapidly
access the most relevant vectors. A coarse quantizer
is used to implement this inverted file structure, where
vectors corresponding to a cluster (index) are stored in
the associated list. The vectors in the list are represented
by short codes, computed by our product quantizer,
which is used here to encode the residual vector with
respect to the cluster center.
The interest of our method is validated on two
kinds of vectors, namely local SIFT [23] and global
GIST [18] descriptors. A comparison with the state of
the art shows that our approach outperforms existing
techniques, in particular spectral hashing [19], Hamming
embedding [20] and FLANN [9].
Our paper is organized as follows. Section II intro-
duces the notations for quantization as well as the prod-
uct quantizer used by our method. Section III presents
our approach for NN search and Section IV introduces
the structure used to avoid exhaustive search. An evalua-
tion of the parameters of our approach and a comparison
with the state of the art is given in Section V.
II. B
ACKGROUND: QUANTIZATION, PRODUCT
QUANTIZER
A large body of literature is available on vector
quantization, see [24] for a survey. In this section, we
restrict our presentation to the notations and concepts
used in the rest of the paper.
A. Vector quantization
Quantization is a destructive process which has been
extensively studied in information theory [24]. Its pur-
pose is to reduce the cardinality of the representation
space, in particular when the input data is real-valued.
Formally, a quantizer is a function
q mapping a D-
dimensional vector x ∈ R
D
to a vector q(x) ∈ C =
{c
i
; i ∈ I}, where the index set I is from now on
assumed to be finite:
I = 0 . . . k − 1. The reproduction
values c
i
are called centroids. The set of reproduction
values
C is the codebook of size k.
The set V
i
of vectors mapped to a given index i is
referred to as a (Voronoi) cell, and defined as
V
i
, {x ∈ R
D
: q(x) = c
i
}.
(2)
The
k cells of a quantizer form a partition of R
D
. By
definition, all the vectors lying in the same cell
V
i
are
reconstructed by the same centroid c
i
. The quality of a
quantizer is usually measured by the mean squared error
between the input vector
x and its reproduction value
q(x):
MSE(q) = E
X
d(q(x), x)
2
=
Z
p(x) d
q(x), x
2
dx,
(3)