IPSJ Transactions on Computer Vision and Applications Vol.4 108–118 (Oct. 2012)[DOI: 10.2197/ipsjtcva.4.108]

Research Paper

Optimized Codebook Construction and Assignmentfor Product Quantization-based
Approximate Nearest Neighbor Search
Yusuke Uchida1,a)Koichi Takagi1

Shigeyuki Sakazawa1

Received: October 31, 2011, Accepted: July 5, 2012, Released: October 19, 2012

Abstract: Nearest neighbor search (NNS) among large-scale and high-dimensional vectors has played an importantrole in recent large-scale multimedia search applications. This paper proposes an optimized codebook construction algorithm for approximate NNS based on product quantization. The proposed algorithm iteratively optimizes both codebooks for product quantization and an assignment table that indicates the optimal codebook in product quantization.
In experiments, the proposed method is shown to achieve better accuracy in approximate NNS than the conventional
method with the same memory requirement and the same computational cost. Furthermore, use of a larger number ofcodebooks increases the accuracy of approximate NNS at the expense of a slight increase in the memory requirement.
Keywords: approximate nearest neighbor search, high-dimensional indexing, product quantization

1. Introduction
Nearest neighbor search (NNS) in a high-dimensional space
plays an important role in many computer vision algorithms
and applications, where high-dimensional feature vectors such as
SIFT [1] or GIST [2] are frequently used. Given a set of data
points in a metric space and a query point in the same metricspace, NNS is defined as the problem of identifying the data
point(s) nearest to the query point. In this paper, we focus on
Euclidean space NNS, which is relevant to many applications.
The kd-tree [3] is one of the best solutions for NNS in a lowdimensional space, while its eﬀectiveness declines as dimensionality increases due to the so-called “curse of dimensionality.” Inorder to deal with this problem, approximate approaches such as
ANN [4] or LSH [5] have attracted much attention. In an approximate NNS, a search result will fail to be the exact nearest neighbor point with a probability that is characterized by the parameters of the approximate NNS algorithms. It is reported that a randomized kd-tree algorithm [6], [7] and a hierarchical k-means tree
algorithm [8] perform better than ANN and LSH [8]. The randomized kd-tree algorithm constructs multiple randomized kdtrees, and these trees are explored simultaneously according toa single priority queue, which is referred to as a best-bin-firstsearch [9]. The priority is determined by the distance between aquery point and each bin boundary in the kd-trees. In Ref. [10], an
improved algorithm for kd-tree construction is proposed, where apartition axis is formed by combining two or more coordinate
axes instead of selecting a single coordinate axis. The hierarchical k-means tree algorithm also explores the hierarchical k-means
tree [11] in a best-bin-first manner based on the distance between
1a)KDDI R&D Laboratories, Inc., Fujimino, Saitama 356–8502, Japan
ys-uchida@kddilabs.jp

c 2012 Information Processing Society of Japana query point and each branch node in the tree. The algorithm
referred to as FLANN [8] optimally selects randomized kd-trees
or a hierarchical k-means tree for indexing according to the given
data distribution and the user’s requirements, and it provides fully
automated parameter selection.
For the sake of eﬃciency, all of the above-mentioned methods require the indexed vectors themselves to be stored in themain memory. However, this requirement is not feasible whenhandling large-scale datasets, e.g., when indexing millions of images [12], [13]. In order to address this issue, short code-based
NNS methods are proposed: feature vectors are compressed into
short codes and NNS is performed in the compressed domain. In
short code-based NNS, the tradeoﬀ between search accuracy andthe size of short codes is an important performance measure in
addition to the tradeoﬀ between search accuracy and computational cost in standard approximate NNS. Because short codebased NNS methods usually perform a linear search, computational costs are almost the same among diﬀerent methods depending on the size of short codes. One of the most common ways torealize a short code-based method is to utilize random projections like LSH [5]. Although the LSH algorithm has been thoroughly studied at a theoretical level, it requires short codes witha relatively large size to maintain approximate NNS accuracy. In
Ref. [12], an algorithm referred to as spectral hashing (SH) has
been proposed. The algorithm achieves better search accuracy
with smaller codes than LSH. It formulates a binary hashing as agraph partitioning problem and solves it by assuming a uniform
distribution over the data. In Ref. [14], an objective function isdefined so that hash functions preserve the input distances when
mapping to the Hamming space. An eﬃcient algorithm to optimize the objective function is also proposed. In Ref. [15], a transform coding-based method is proposed. This method realizes

108

IPSJ Transactions on Computer Vision and Applications Vol.4 108–118 (Oct. 2012)

data-driven allocation of bits to components. It has been shown tooutperform LSH and SH in approximate NNS and scene classification problems. Recently, a product quantization-based method
has been proposed [13], where the distances between a query vector and quantized reference vectors can be calculated eﬃciently.
It has been shown to outperform the methods mentioned abovein terms of approximate NNS accuracy with the same short code
size [13], [15]. The tradeoﬀ between search time and accuracy isfurther improved by a non-exhaustive search framework.
In a non-exhaustive framework [13], a coarse quantization is
first performed and the resulting residual (error) vectors are further quantized by the product quantizer. Although the residual
vectors follow diﬀerent distributions depending on the assigned
Voronoi cells, which are defined by the coarse quantizer, theconventional method quantizes them irrespective of the assigned
cells, resulting in the degradation of quantization performance.
Because quantized reference vectors are used for distance calculations in the product quantization-based method, ineﬀective
quantization leads to low search accuracy.
In this paper, in order to solve the problem of product quantization in Ref. [13], we propose a modified product quantizationbased approximate NNS method, which utilizes an arbitrary number of codebooks in product quantization. Our main contribution is the development of an iterative codebook construction algorithm for product quantization. This algorithm optimizes thecodebooks by iteratively executing an update step and assignment
step similar to the k-means algorithm. In the update step, thecodebooks are updated so that total quantization error is reduced
for a fixed assignment table, which defines the assignments fromresidual vectors to the codebooks. In the assignment step, the assignment table is optimized for the fixed codebooks to minimize
the error. The resulting optimized codebooks can reduce quantization error considerably, improving the accuracy of approximate
NNS search. In experiments, the proposed method is shown toachieve better accuracy in approximate NNS compared with theconventional method with the same memory requirement and thesame computational cost. Furthermore, use of a larger numberof codebooks increases the accuracy of approximate NNS at theexpense of a slight increase in the memory requirement.

2. Product Quantization for Nearest Neighbor
SearchIn this section, we briefly review the product quantizationbased approximate NNS system [13]. It consists of an oﬄine
indexing step and an online search step. In the indexing step,reference vectors Y with a dimension of d are encoded into shortcodes via product quantization, and these short codes are stored
in a database. In the search step, for each query vector x with thesame dimension d, the system returns the k-nearest neighbor vectors from a k-NN search or the vectors with a distance less thana given threshold  from a range search. This is accomplished by
calculating the approximate distance ḋ(x, y) between the query
vector x and reference vector y in the database. The approximate
distances are eﬃciently calculated from the query vector x andthe short codes in the database. The notation used in this paper issummarized in Table 1.
2.1 Indexing with Product Quantization
In the indexing step, a reference vector y is first decomposed
into m d∗ -dimensional subvectors u1 , · · · , um :y = (y1 , · · · , yd∗ , · · · , yd−d∗ +1 , · · · , yd )T ,

uT1

(1)

uTm

where d∗ = d/m. Subsequently, these subvectors are quantizedseparately using m codebooks P1 , · · · , Pm , which is referred to as
product quantization. In this paper, a codebook used in productquantization is referred to as a PQ codebook. We assume that∗each PQ codebook Pl has k∗ centroids pl,1 , · · · , pl,k∗ ∈ Rd . The
l-th subvector ul is quantized into ql (ul ) = pl,al using l-th PQ
codebook Pl , where
al = arg min ∗ ||ul − pl,a ||2 .

(2)

1≤a≤k

As a result, y is quantized into q(y):q(y) = (q1 (u1 )T , · · · , qm (um )T )T = (pT1,a1 , · · · , pTm,am )T .

(3)

Table 1 Notations.
Symboldmd∗FP1 , · · · , Pm
k∗
C
k
r
P1 , · · · , Pr
R1,1 , · · · , Rk ,mTw

Notation
Dimensionality of feature vectors.
The number of vector decomposition in product quantization.
Dimensionality of subvectors, where d∗ = d/m.
A set of training vectors with a dimension of d.
Codebooks used in the conventional product quantization (PQ codebooks), where∗
Pi = (pi,1 , · · · , pi,k∗ ) and pi,a ∈ Rd .
The size of PQ codebooks (the number of centroids).
A codebook used in coarse quantization (CQ codebook), where C = (c1 , · · · , ck )and c j ∈ Rd .
The size of CQ codebook (the number of centroids).
The number of PQ codebooks used in the proposed method.
Codebooks used in the proposed product quantization (PQ codebooks), where∗
Pi = (pi,1 , · · · , pi,k∗ ) and pi,a ∈ Rd .
Sets of residual subvectors with a dimension of d∗ used in the construction of PQ
codebooks. R j,l represents the set of l-th subvectors of the training vectors that areassigned to the j-th centroid in coarse quantization.
Assignment table T ∈ Nk ×m . T j,l indicates the identifier of the PQ codebook withwhich l-th residual subvectors assigned to the j-th centroid in coarse quantization
should be quantized.
The number of inverted lists to be searched in the multiple assignment strategy.

c 2012 Information Processing Society of Japan

Section
§2
§2.1
§2.1
§2.1
§2.1
§2.1
§2.3.1§2.3.1
§3
§3
§3.1
§3.1
§4.5

109

IPSJ Transactions on Computer Vision and Applications Vol.4 108–118 (Oct. 2012)

Fig. 1

Relationship among the true distance d(x, y), the approximate distance d(x, q(y)), and the quantization error d(y, q(y)).

A tuple (a1 , · · · , am ), the short code representation of y, is stored
for search purposes. As al ranges from 1 to k∗ , the length of theshort code becomes mlog2 k∗ . The PQ codebooks should becreated prior to indexing using a large number of training vectors
F : the l-th PQ codebook is created by clustering a set of the l-th
subvectors of the training vectors F using the k-means algorithm.
2.2

Distance Calculation between Query Vector and ShortCode
In the search step, a query vector x is also decomposed intom d∗ -dimensional subvectors u1 , · · · , um . The distance d(x, y) between the query vector x and a reference vector y is approximatedby the distance d(x, q(y)) between the query vector x and quantized reference vector q(y) with the short code (a1 , · · · , am ): m||ul − pl,al ||2 .
(4)
d(x, y) ≈ ḋ(x, y) = d(x, q(y)) =improvement. The product quantization-based scheme can be integrated with an inverted index to avoid exhaustive searches andthus further increase eﬃciency. The non-exhaustive framework is
referred to as an inverted file with asymmetric distance computation (IVFADC) in Ref. [13].
2.3.1 Indexing in IVFADC
In the indexing step in the IVFADC framework, a reference
vector y is first quantized with a coarse quantizer. We refer tothe codebook used in coarse quantization as the CQ codebook.
The reference vector y is quantized into qc (y) = c ĵ using the CQ
codebook C with k centroids c1 , · · · , ck ∈ Rd , whereĵ = arg min  ||y − c j ||2 .
1≤ j≤kSubsequently, the residual vector r ĵ from the corresponding centroid c ĵ is calculated asr ĵ = y − c ĵ .

1≤a≤k

For eﬃciency, lookup table F is prepared when a query vector x
is given:
Fl,a = ||ul − pl,a ||2 (1 ≤ l ≤ m, 1 ≤ a ≤ k∗ ).

(5)Using this lookup table, the approximate distance ḋ(x, y) is calculated: m
ḋ(x, y) =Fl,al .
(6)
l=1

Figure 1 illustrates the relationship among the true distanced(x, y), the approximate distance d(x, q(y)), and the quantization
error d(y, q(y)). The triangular inequality givesd(x, y) ≤ d(x, q(y)) + d(y, q(y)),
d(x, q(y)) ≤ d(x, y) + d(y, q(y)).

(7)

The equation can be modified asd(x, y) − d(x, q(y)) ≤ d(y, q(y)),−d(y, q(y)) ≤ d(x, y) − d(x, q(y)).

(8)

Finally, we obtain:|d(x, y) − d(x, q(y))| ≤ d(y, q(y)).

(9)

Here, |d(x, y) − d(x, q(y))| corresponds to the error in distance approximation, and is bounded by the quantization error d(y, q(y)).
2.3 Integration with Inverted Index
Although approximate nearest neighbor search with productquantizers is fast, the search is exhaustive and there is room forc 2012 Information Processing Society of Japan(11)Then, in order to reduce quantization error in the coarse quantizer,
the residual vector r ĵ is quantized via product quantization in thesame manner as described in Section 2.1. The residual vector r ĵis divided into m subvectors r ĵ,1 , · · · , r ĵ,m . The residual subvectorr ĵ,l is quantized into ql (r ĵ,l ) = pl,al using the PQ codebook Pl ,whereal = arg min ∗ ||r ĵ,l − pl,a ||2 .

l=1

(10)

(12)

Finally, the short code (a1 , · · · , am ) is stored in the ĵ-th list of theinverted index with the vector identifier.
2.3.2 Distance Calculation in IVFADC
In the search step in the IVFADC framework, a query vector x
is first quantized using the CQ codebook, and the residual vectorr ĵ from the corresponding centroid is calculated. Subsequently,
the approximate distances between the residual vector r ĵ and theshort codes in the index are calculated. These distances correspond to the approximate distances between the query vector andthe reference vectors. In contrast to the exhaustive search described in Section 2.2, only the short codes in the ĵ-th list of theinverted index are concerned, whereĵ = arg min  ||x − c j ||2 .
1≤ j≤k(13)Compared with the exhaustive search, IVFADC is shown toachieve a better tradeoﬀ between approximate NNS accuracy andsearch speed [13].
2.3.3 Codebook Construction for IVFADC
In the case of IVFADC, the CQ codebook and PQ codebooks
should be created prior to indexing. The CQ codebook is constructed by clustering a large set of the training vectors F using
the k-means algorithm to obtain k centroids c1 , · · · , ck ∈ Rd .
Then, by subtracting corresponding centroid vectors from training vectors, a set of residual vectors is created. Subsequently, theresidual vectors are divided into m residual subvectors. Finally,for each l, the l-th PQ codebook is constructed by clustering a
set of l-th residual subvectors of the residual vectors using the
k-means algorithm.

110

IPSJ Transactions on Computer Vision and Applications Vol.4 108–118 (Oct. 2012)

Fig. 2The number of feature vectors assigned to a centroid and the meansquare distance between the feature vectors and the centroid are plotted. The CQ codebook with a size of 1,024 is created from 4M SIFT
feature vectors with the k-means algorithm.

2.4 Ineﬀectiveness in Product Quantization
In Ref. [13], residual subvectors from the same position in vector decomposition are quantized with the same PQ codebook irrespective of the cells into which corresponding residual vectors arequantized in coarse quantization. Because these cells have diﬀerent residual vector distributions, the quantization of residual subvectors from diﬀerent distributions with the same PQ codebook
is ineﬀective in terms of reducing quantization error, which results in the degradation of approximate NNS accuracy. Figure 2
shows the relationship between the number of feature vectors assigned to a centroid and the mean square distance between thefeature vectors and the centroid. Since the mean square distancereflects the size of a cell, Fig. 2 indicates that there are marked
diﬀerences in the size of the Voronoi cells, and it implies thatthe distributions of residual vectors are also quite diﬀerent depending on the cells. To handle this diversity, an identical PQ
codebook for each cell and for each position of residual subvectors may be used for product quantization. However, the memory
requirements for the PQ codebooks become very large relative tothe number of centroids k in the coarse quantization. This requirement would be intractable in some situations where large k
(e.g., from 10K to 1M in Ref. [6]) is often used. For example,
assuming that the number of centroids k of the CQ codebook is
100K, the number of centroids k∗ of each PQ codebook is 256,and 128-dimensional SIFT features are indexed; this means thatapproximately 100K × 256 × 128 3 Gbytes of memory is required to store only the PQ codebooks. Furthermore, to generalize the PQ codebooks to non-training vectors, k times as many
training vectors as in the case of creating a single PQ codebook
for each residual subvector position are required.

3. Proposed Approach
As explained in Section 2, residual subvectors have diﬀerent
distributions depending on the assigned centroids in coarse quantization. In this paper, we propose the use of an arbitrary numberr (1 ≤ r ≤ k × m) of PQ codebooks P1 , · · · , Pr in product quantization, where residual subvectors from similar distributions sharethe same PQ codebook. In the conventional method, a residual
subvector is quantized by a PQ codebook that is specified onlyby the position l of the residual subvector in vector decomposition, while the proposed method specifies a PQ codebook not

c 2012 Information Processing Society of Japan

only by the position l of the residual subvector but also by theidentifier j of the centroid into which the corresponding reference vector is quantized in coarse quantization. Figure 3 shows
an intuitive illustration of the proposed approach. The proposed
algorithm creates semi-optimal PQ codebooks to minimize theexpected mean square error (MSE) in product quantization for agiven r. Because the error in product quantization corresponds tothe upper bound of error in distance approximation as shown in
Section 2.2, it is very important to reduce the error to improve theaccuracy of product quantization-based approximate NNS. In thissection, an algorithm to create an arbitrary number r of optimized
PQ codebooks to minimize RMSE is proposed. In the algorithm,
an assignment table T is also created. The table specifies the PQ
codebook to be used in the quantization of a residual subvector
depending on the position of the residual subvector and the centroid into which the corresponding residual vector is quantized incoarse quantization. Indexing and search algorithms using optimized PQ codebooks are also described.
3.1 Multiple Codebook Construction
In this section, the codebook construction algorithm is described. It includes the construction of CQ codebook C for coarse
quantization, PQ codebooks P1 , · · · , Pr for product quantization,
and an assignment table T . We first construct a CQ codebook C
by clustering the set of training vectors F with the k-means algorithm. The residual vectors of the training vectors from theircorresponding centroids in C are calculated. Subsequently, all theresidual vectors are divided into m residual subvectors with a dimension of d∗ . Let R j,l denote the set of l-th residual subvectorsthat are assigned to the j-th centroid in coarse quantization. Our
objective is to create optimized PQ codebooks P1 , · · · , Pr and an
assignment table T that minimize the expected MSE in productquantization. Here, T j,l indicates the identifier of a PQ codebook
with which l-th residual subvectors assigned to the j-th centroid
in coarse quantization should be quantized. The objective is formulated ask me(R j,l , PT j,l ),(14)minimize:
j=1 l=1

where e(R j,l , Pi ) represents the sum of the squares of errors inquantizing a set of residual subvectors R j,l with PQ codebook Pi :e(R j,l , Pi ) =min ∗ ||r j,l,b − pi,a ||2 .
(15)
1≤b≤|R j,l |1≤a≤k

In the above equation, r j,l,b represents the b-th training subvector
in R j,l . This optimization problem requires that the assignment
table T and the PQ codebooks P1 , · · · , Pr should be optimized simultaneously. Because it is an NP-hard problem, we propose anapproximate algorithm which iteratively optimizes (1) the assignment table T for the fixed PQ codebooks P1 , · · · , Pr and (2) thePQ codebooks for the fixed assignment table T .
The proposed codebook construction procedure is summarizedin Algorithm 1. The algorithm consists of an initialization step(Line 1), an update step (Lines 3–5), and an assignment step(Lines 6–22). In the initialization step, the assignment table T
and initial labels s j,l = (s j,l,1 , · · · , s j,l,|R j,l | ) are initialized. The initialization of T is described in Section 3.2 in detail. The label s j,l,b

111

IPSJ Transactions on Computer Vision and Applications Vol.4 108–118 (Oct. 2012)(a) Product quantization in the conventional method.
Fig. 3(b) Product quantization in the proposed method.

Intuitive illustration of the proposed approach for k = 3, m = 4, r = 2. Each ellipse illustrates the∗probability density function p(r j,l ) defined in the feature space Rd , where r j,l is the l-th residual
subvector of a reference vector that is assigned to the j-th centroid in coarse quantization. Darker
area corresponds to higher density. Probability distribution p(r j,l ) is diﬀerent depending on bothj and l. PQ codebooks are represented by Voronoi diagrams. Each blue arrow points to the PQ
codebook that is used to quantize the residual subvector r j,l . (a) In the conventional scheme, eachresidual subvector r j,l is assigned to the PQ codebook according to only l; residual subvectorsthat follow quite diﬀerent distrubutions may be quantized with the same PQ codebook, resulting
in large quantization error. (b) In the proposed scheme, each residual subvector r j,l is optimallyassigned to the PQ codebook according to not only l but j; residual subvectors that follow similar
distributions tend to be quantized with the same PQ codebook adapted to the distributions, which
reduces quantization error.

Algorithm 1 PQ codebook construction
Require: R j,l (1 ≤ j ≤ k , 1 ≤ l ≤ m), r
Ensure: P1 , · · · , Pr , T
1: initialize T , s j,l (1 ≤ j ≤ k , 1 ≤ l ≤ m)
2: repeat3:
for i = 1 to r do
4:
update Pi by clustering T j,l =i R j,l using initial labels s j,l for R j,l5:
end for6:
for j = 1 to k do
7:for l = 1 to m do
8:
e←∞
9:
for i = 1 to r do
10:ê ← 011:
for b = 1 to |R j,l | do
12:ê ← ê + min1≤a≤k∗ ||r j,l,b − pi,a ||213:ŝ j,l,b ← argmin1≤a≤k∗ ||r j,l,b − pi,a ||2
14:
end for15:
if e > ê then16:e ← ê
17:
T j,l ← i18:
s j,l ← ŝ j,l19:
end if
20:
end for21:
end for22:
end for23: until a fixed number of iterations are performed

is used as the initial label of the b-th training subvector r j,l,b in the
k-means clustering in the update step. The label s j,l,b is initializedc 2012 Information Processing Society of Japan

by a random value ranging from 1 to k∗ in the initialization step,and is updated with the identifier of the centroid in Pi closest tor j,l,b in the assignment step. The update step and assignment step
are iterated for a fixed number of times.
Update step. In the update step, Eq. (14) is minimized by updating the PQ codebooks P1 , · · · , Pr for the fixed assignment table T . For each i, the i-th PQ codebook Pi is updated using theresidual subvectors assigned to Pi . As the assignment is definedby the assignment table T , the update step is simply achieved byclustering the residual subvectors T j,l =i R j,l to obtain k∗ centroids
pi,1 , · · · , pi,k∗ . In the clustering, the initial label s j,l,b is used for theb-th training subvector r j,l,b in R j,l to accelerate and stabilize theclustering instead of starting with random labels. As the labels
s j,l = (s j,l,1 , · · · , s j,l,|R j,l | ) for R j,l are obtained in the assignment
step, random labels are used only in the first update step.
Assignment step. In the assignment step, Eq. (14) is minimized by updating the assignment table T for the fixed PQ codebooks P1 , · · · , Pr . For each R j,l , the quantization error ê in quantizing R j,l with the PQ codebook Pi is calculated for all i (lines 9–20). The identifier of the PQ codebook that minimizes the quantization error is stored in T j,l (line 17). The identifier of the centroid
in Pi closest to r j,l,b is also stored in s j,l,b (line 13 and 18) for the
update step.
The diﬀerence between the proposed method and the conventional method for the construction of PQ codebooks is summarized in Fig. 4. The proposed method becomes identical to theconventional method when we set r = m and T j,l = l. CQ code-112

IPSJ Transactions on Computer Vision and Applications Vol.4 108–118 (Oct. 2012)(a) PQ codebook construction procedure in the conventional method.
Fig. 4(b) PQ codebook construction procedure in the proposed method.

The diﬀerence between the conventional method and the proposed method for the constructionof PQ codebooks. (a) In the conventional method, the l-th PQ codebook is constructed by clustering a collection of residual subvectors R1,l , · · · , Rk ,l irrespective of the centroids to which thecorresponding training vectors are assigned in coarse quantization. (b) In the proposed method,
the i-th PQ codebook is constructed by clustering a collection of residual subvectors R j,l such that
T j,l = i. The assignment table T and the PQ codebooks P1 , · · · , Pr are iteratively optimized in theassignment step and the update step, respectively.

book C, PQ codebooks P1 , · · · , Pr and the table T created in thisprocedure are used in both the indexing and search procedures.
Computational cost. The computational cost required by the
proposed algorithm is examined. The update step involves performing k-means clustering. It costs O(nave · nitr · k∗ · d∗ ) time
to update each PQ codebook, where nave denotes the average
number of residual subvectors assigned to each PQ codebook,and nitr denotes the number of iterations in k-means clustering.
Let nall denote the number of all training subvectors; it costsO(r · nave · nitr · k∗ · d∗ ) = O(nall · nitr · k∗ · d∗ ) time to update
all PQ codebooks to be computed. The assignment step requires
the distances between all training subvectors j,l R j,l and all centroids of the PQ codebooks P1 · · · , Pr . It costs O(nall · r · k∗ · d∗ )time. While nitr is fixed at a relatively small value in this paper(nitr = 5), r ranges from 1 to k × m. Therefore, the computational
cost of our PQ codebook construction algorithm is O(nall ·r·k∗ ·d∗ )in many cases.
3.2 Initialization in PQ Codebook Construction
In this section, we introduce two algorithms to initialize the assignment table T for the construction of the PQ codebooks. The
first is a very simple approach: assign random labels to table T
in the same manner as that used in the k-means algorithm. The
other is a k-means++-like initialization algorithm inspired by the
k-means++ algorithm [16], where initial centroids are chosen iteratively until the predefined number of centroids is selected; thenext centroid is chosen from all samples according to a probability proportional to the squared distances to the nearest centroids
that have been already chosen. The k-means++ algorithm improves both the speed and the accuracy of k-means by carefully
choosing initial seeds. In our case, samples and centroids correspond to sets of residual subvectors and PQ codebooks, respectively. The squared distance between a sample and a centroid
corresponds to the sum of squares of errors in the quantization of
a set of residual subvectors using a PQ codebook.

c 2012 Information Processing Society of Japan

Algorithm 2 Initialization in the PQ codebook construction
Require: R j,l (1 ≤ j ≤ k , 1 ≤ l ≤ m), r
Ensure: T
1: randomly select R̂ j,l and create PQ codebook P1 by clustering it
2: for j = 1 to k do
3:for l = 1 to m do
4:
e j,l ← e(R j,l , P1 )5:
T j,l ← 1
6:
end for
7: end for
8: for i = 2 to r do
9:select R̂ j,l with the probability e j,l / kj=1 m
l=1 e j,l and create PQ codebook Pi by clustering it
10:for j = 1 to k do
11:for l = 1 to m do
12:
if e j,l > e(R j,l , Pi ) then13:e j,l ← e(R j,l , Pi )14:
T j,l ← i
15:
end if16:
end for17:
end for
18: end for

The k-means++-like initialization algorithm is summarized in
Algorithm 2. In the algorithm, the PQ codebooks P1 , · · · , Pr are
created in order, and the assignment table T is updated accordingly. First, P1 is created by clustering randomly selected R̂ j,l(line 1). All residual subvectors are assigned to P1 and the quantization error e j,l in quantizing R j,l with the PQ codebook P1 is calculated (line 4–5). Then, P2 , · · · , Pr are created recursively. For
each i, Pi is created by clustering R̂ j,l , where R̂ j,l is selected witha probability proportional to the quantization error e j,l . The quantization error e j,l corresponds to the minimum quantization error
in quantizing R j,l achieved using one of the previously created PQ
codebooks P1 , · · · , Pi−1 (line 9). For each R j,l , the assignment table and the quantization error is updated if the new PQ codebook
Pi produces a lower quantization error than the current best PQ

113

IPSJ Transactions on Computer Vision and Applications Vol.4 108–118 (Oct. 2012)codebook (line 12–15). After the PQ codebooks P1 , · · · , Pr are
created, the initial assignment table T is obtained.
3.3 Indexing Using Optimized PQ Codebooks
The indexing step is almost the same as in the conventional
method described in Section 2.3.1 except that, in our scheme, thePQ codebook used in residual subvector quantization is identified
by the assignment table T . The reference vector y is quantized
into qc (y) = c ĵ using CQ codebook C:
ĵ = arg min  ||y − c j ||2 .
1≤ j≤k(16)

The residual vector r ĵ from the corresponding centroid is calculated thus:r ĵ = y − c ĵ .

(17)

Residual vector r ĵ is then divided into m subvectors r ĵ,1 , · · · , r ĵ,m .
The PQ codebook Pî used for the l-th residual subvector is identified by the assignment table T as î = T ĵ,l . Then residual subvectorr ĵ,l is quantized into qî (r ĵ,l ) = pî,al , where
al = arg min ∗ ||r ĵ,l − pî,a ||2 .
1≤a≤k

(18)

Finally, the short code (a1 , · · · , am ) is stored in the ĵ-th list of theinverted index with the vector identifier.
3.4 Distance Calculation Using Optimized PQ Codebooks
In the search step, query vector x is first quantized using the
CQ codebook C:
ĵ = arg min  ||x − c j ||2 .
1≤ j≤k(19)

The residual vector r ĵ of x is calculated and divided into m subvectors r ĵ,1 , · · · , r ĵ,m in the same manner as in the indexing step.
Then, the distance table F is created for subsequent distance calculations. Note that short codes in the ĵ-th list in the inverted
index are created using the PQ codebooks PT ĵ,1 , · · · , PT ĵ,m , insteadof P1 , · · · , Pm .
Fl,a = ||r ĵ,l − pT ĵ,l ,a ||2 (1 ≤ l ≤ m, 1 ≤ a ≤ k∗ ).

(20)

There is no additional computational cost caused by the use ofa larger-than-m number r of PQ codebooks because the size oftable F is still the same as in the conventional method (m × k∗ ).
Finally, the approximate distances between the query vector andthe reference vectors in the ĵ-th list of the inverted index are calculated. The approximate distance between the query vector x
and the reference vector y with code (a1 , · · ·, am ) is eﬃciently
calculated using the lookup table F: m
ḋ(x, y) =
Fl,al
(21)
l=1

This step also requires the same computational cost as that in theconventional method.

4. Experimental Results
In this section, the datasets used for the evaluation are briefly
presented. Then, we evaluate the proposed method and the conventional method in terms of quantization error and accuracy in
NNS in detail.

c 2012 Information Processing Society of Japan

Table 2 Summary of the SIFT and GIST data sets.
dimensionality# of training vectors# of reference vectors# of query vectors(HesAﬀ-)SIFT
128
4,000,000
1,000,000
100,000

Grid-SIFT
128
4,000,000
-

GIST
384
4,000,000
1,000,000
100,000

4.1 Datasets
In our experiments, datasets with local SIFT descriptors [1] andglobal GIST descriptors [2], which are frequently used in the areaof image retrieval and recognition, are used to evaluate the accuracy of approximate NNS. For each of the two descriptors, three
types of vectors are required to evaluate the accuracy of approximate NNS [13]: training vectors, reference vectors, and query
vectors. Training vectors are used to construct all of the CQ andPQ codebooks.
In the case of the SIFT descriptor, ANN SIFT1M descriptors *1
are used as reference vectors. Although the dataset also includes
100K training vectors and 10K query vectors, the number oftraining vectors is insuﬃcient for the proposed method, as shownin Section 4.4. To deal with this problem, 4M training vectors
and 100K query vectors are extracted from Flickr60K descriptors,
which form a part of the INRIA Holidays dataset *2 . We refer theabove-mentioned SIFT descriptor as HesAﬀ-SIFT because it isextracted Hessian-Aﬃne region [17], while another type of SIFT
descriptor called Grid-SIFT is also introduced in Section 4.3. As
the Grid-SIFT descriptor is used only in Section 4.3, we simply
refer to the HesAﬀ-SIFT descriptor as SIFT in the other sections.
For the GIST descriptor, 4M training vectors, 1M reference
vectors, and 100K query vectors are extracted from the 80 Million Tiny Images dataset *3 , as provided in Ref. [18]. Since thisincludes not only 32×32 color images but also precomputed 384dimensional GIST feature vectors, these precomputed vectors areused in this paper. The SIFT and GIST data sets used in the experiments are summarized in Table 2.
The following experiments were performed on a machine witha Core i7 970 CPU and 24 GB of main memory. Parameters usedin the experiments follow the parameters shown to be appropriate
in Ref. [13]: k = 1,024, m = 8, k∗ = 256 for the SIFT vectors,
and k = 1,024, m = 8, 24, k∗ = 256 for the GIST vectors. Coarse
and product quantization were performed by exhaustive searchwith SIMD instructions. Processing times were measured using
a program with a single thread.
4.2 The Impact of Initialization Methods
In this section, we evaluate the two initialization methods described in Section 3.2 using the root mean square error (RMSE)
measure, the random assignment method (base) and the kmeans++-like initialization method (k-means++). A CQ codebook with a size of 1,024 created from the 4M training SIFT vectors is used for coarse quantization. This CQ codebook is also
used in the following experiments. The number r of PQ codebooks is fixed at 64, and 4M training vectors are used to create
PQ codebooks. Figure 5 shows RMSE and elapsed time at the
*1
*2
*3

http://corpus-texmex.irisa.fr/
http://lear.inrialpes.fr/˜jegou/data.php
http://horatio.cs.nyu.edu/mit/tiny/data/index.html

114

IPSJ Transactions on Computer Vision and Applications Vol.4 108–118 (Oct. 2012)

Table 3 RMSE for two types of SIFT vectors.
HesAﬀ-SIFT
Grid-SIFT(a) HesAﬀ-SIFT

Prop r=1
0.27740.2870Conv
0.27150.2852

Prop r=80.25940.2740(b) Grid-SIFT

Fig. 5 Comparison of initialization methods. RMSE at the end of each iteration and elapsed time at that point are shown for up to 20 iterations.
The average and minimum RMSEs over 10 runs are plotted.

Fig. 6end of each iteration in the construction of PQ codebooks. We
can see that although the k-means++-like initialization method
requires additional processing time at the first iteration, it provides a better tradeoﬀ between computational cost and RMSE.
PQ codebooks with smaller RMSE provide more accurate distance approximation, resulting in better accuracy of approximate
NNS. In the following experiments, all PQ codebooks are created with the k-means++-like initialization, and the number of
iterations is set to 10.

where r = 1, 8 and the conventional method. In the case of
HesAﬀ-SIFT, using diﬀerent PQ codebooks according to the positions of subvectors (Conv) reduces quantization error comparedwith the case where all subvectors share a single PQ codebook(Prop r = 1). However, the proposed method where r = 8
achieves further improvement over the conventional method byallowing subvectors from diﬀerent positions to share the same PQ
codebooks. In the case of Grid-SIFT, Conv achieves almost thesame quantization error as Prop r = 1, while Prop r = 8 reduces
quantization error. This is because the position of the subvectors does not aﬀect the distribution of the subvectors, while theassigned centroid identifiers in coarse quantization do aﬀect the
distribution of the subvectors. Note that Conv and Prop r = 8
require the same amount of memory for PQ codebooks. Figure 6
shows the ratio of residual vector sets at each position that areassigned to each PQ codebook: the (l, i)-th entry of the matrix
represents the ratio of R j,l (1 ≤ j ≤ k ) that satisfies T j,l = i tok . In the case of the conventional method, the matrix is identicalto the identity matrix. It can be said that the proposed codebook
construction algorithm automatically adjusts PQ codebooks andthe assignment table to incoming vectors with diﬀerent statisticalproperties.

4.3 Adjusting PQ Codebooks and Assignment Table
The proposed codebook construction algorithm adjusts both
PQ codebooks and an assignment table to incoming vectors by iterative optimization. In this section, we explore the optimization
capacity using two types of SIFT vectors with diﬀerent characteristics. One is a SIFT vector describing local invariant regions detected by the Hessian-Aﬃne detector (HesAﬀ-SIFT). The otherone is a SIFT vector describing a regular grid [19] in an image(Grid-SIFT). HesAﬀ-SIFT represents feature vectors whose subvectors follow diﬀerent distributions depending on the positionsof subvectors, while Grid-SIFT represents feature vectors whosesubvectors follow the same distribution independent of the positions of subvectors. In typical SIFT implementations, a target patch to be described is divided into 4 × 4 blocks and an
8-dimensional subvector is extracted from each of the blocks, resulting in a 128-dimensional SIFT vector. In the case of HesAﬀSIFT, subvectors of diﬀerent blocks follow diﬀerent distributions
due mainly to two reasons; (1) a patch to be described includes
a blob-like area: some blocks corresponds to the blob-like area
and the others correspond to non blob-like area, (2) the contribution of each pixel in a patch to feature vectors is weighted by
a Gaussian function of the distance from the center of the patch(pixels far from the center have less impact on feature vectors).
Although many implementations have also adopted a Gaussian
weighting function in describing Grid-SIFT feature vectors, inorder to compare two diﬀerent types of feature vectors, we do
not use Gaussian weighting for Grid-SIFT: the Grid-SIFT vectors
used in the experiment are extracted from randomly downloaded
Flickr images using a modified version of the VLFeat library *4 .
Table 3 shows RMSE measures for the proposed method*4

http://www.vlfeat.org

c 2012 Information Processing Society of Japan

Assignment matrix obtained by the proposed method where r = 8
for HesAﬀ-SIFT and Grid-SIFT features. The (l, i)-th entry of thematrix represents the ratio of R j,l that satisfies T j,l = i for 1 ≤ j ≤ k .

4.4 The Number of PQ Codebooks and Quantization Error
In this section, we evaluate the proposed method in terms ofthe tradeoﬀ between the number r of PQ codebooks and RMSE.
Figure 7 (a) shows RMSE in the construction of PQ codebooks
after convergence. Figure 7 (b) shows RMSE calculated using
the reference vectors, which are extracted from a diﬀerent dataset
from the training dataset. This shows that quantization error is
reduced in proportion to the logarithm of r. It is also shown that
if a suﬃcient number of training vectors is available, the resulting
PQ codebooks are well generalized against non-training vectors.
When the number of training vectors is insuﬃcient, increasing
the number of PQ codebooks does not contribute to a reductionin the quantization error for non-training vectors.
We also evaluate the relative root mean squared error(RRMSE) for each r to investigate the impact of the reductionof RMSE. We use a random 100K pairs (x, y) of the reference
vectors such that both vectors are assigned to the same centroid
in coarse quantization. RRMSE is calculated as

115

IPSJ Transactions on Computer Vision and Applications Vol.4 108–118 (Oct. 2012)(a) w = 1(a) RMSE for the training vectors.

(b) w = 16(b) RMSE for the reference vectors.
Fig. 7

RMSE for the training and reference vectors with a diﬀerent numberof training vectors.

Fig. 8 Relationship between RMSE in product quantization and RRMSE
in distance approximation. PQ codebooks created with 4M training
vectors are used. RRMSE is calculated for 100K pairs of the reference vectors, which are chosen so that the two reference vectors are
assigned to the same centroid in coarse quantization.


 ⎡
 ⎤
⎢⎢⎢ d(x, y) − ḋ(x, y) 2 ⎥⎥⎥⎥⎥⎦.
RRMSE = E ⎢⎢⎣d(x, y)(22)

Note that ḋ(x, y) is defined by the distance between x and q(y),which is the quantized version of y. Figure 8 shows the relationship between the RMSE in product quantization and the RRMSE
in distance approximation. Because RRMSE is linearly reduced
as RMSE is reduced, it can be said that the reduction of RMSE
in product quantization directly contributes to the reduction of
actual error in distance appoximation.
4.5 Accuracy of Nearest Neighbor Search
In this section, the approximate NNS accuracy of the proposed
method and the conventional method is evaluated using the SIFT

c 2012 Information Processing Society of Japan

Fig. 9Recall@R for SIFT features as a function of the number r of PQ
codebooks obtained by the proposed method and the conventional
method.

and GIST features in order to show the eﬀectiveness of the proposed method against diﬀerent types of vectors. The search quality is measured with Recall@R in the same way as Ref. [13]. That
indicates the proportion of query vectors for which the correct
nearest neighbor is found in the top-R search results. For eachquery vector, its nearest neighbor vector among the reference vectors obtained with exact distance calculations is used as a groundtruth.
Multiple assignment [13], [20] is also adopted here. Denoting
the number of assignments by w, w lists corresponding to the wnearest neighbor centroids in the coarse quantization are searchedin an inverted index, instead of searching a single list corresponding to the nearest neighbor centroid. In this case, computational
cost in the search procedure becomes w times larger, providing
more accurate search results.
Figure 9 shows Recall@R for 1M SIFT vectors obtained byusing a diﬀerent number of PQ codebooks. It shows that the proposed method improves Recall@R as the logarithm of the number r of PQ codebooks irrespective of R. Comparing the proposed method where r = 64 and the conventional method, in thecase where w = 16, Recall@10 is improved from 0.684 to 0.768,
which corresponds to a 12% improvement over the conventional
method.
The memory requirement is increased from 33 KB to 262 KB,
which corresponds to 2% of the size of the database in this case *5 .
Because the memory requirement for PQ codebooks is indepen*5

For each reference feature vector, it requires 4 byte and 8 byte to store an
identifier and short code respectively. Therefore, the size of the database(inverted index) is roughly (4 + 8) × 1,000,000 byte (= 12 MB).

116

IPSJ Transactions on Computer Vision and Applications Vol.4 108–118 (Oct. 2012)

Table 4 Processing times [sec] for coarse quantization (CQ), lookup table
construction (LUT), and distance calculation (Dist).
w=1
w = 16

CQ
3.887
3.887

LUT
0.773
11.436Dist
0.757
12.160Total
5.417
27.483(a) w = 1(a) w = 1(b) w = 8(b) w = 8(c) w = 64
Fig. 11 Recall@R for GIST features as a function of the number r of PQ
codebooks obtained by the proposed method and the conventional
method. The number of subvectors m is set to 24.

(c) w = 64
Fig. 10

Recall@R for GIST features as a function of the number r of PQ
codebooks obtained by the proposed method and the conventional
method. The number of subvectors m is set to 8.

dent of the size of the database, the increase in the amount ofmemory required becomes negligible as the size of a dataset increases.
Table 4 shows processing times [sec] for coarse quantization(CQ), lookup table construction (LUT), and distance calculation(Dist). They are measured using 100K queries against 1M SIFT
vectors with w = 1 and w = 16. The most time consuming process
is coarse quantization in the case where w = 1, while it is lookup
table construction and distance calculation where w = 16 because
a computational cost proportional to w is required in lookup table
construction and distance calculation.
Figure 10 shows Recall@R for 1M GIST vectors obtained us-

c 2012 Information Processing Society of Japan

ing a diﬀerent number of PQ codebooks, where the number ofsubvectors is set to 8. We can see a similar tendency to the casewhere SIFT vectors are used. Comparing the proposed method
where r = 64 and the conventional method, in the case wherew = 64, Recall@10 is improved from 0.399 to 0.454, which corresponds to a 13% improvement over the conventional method.
Compared with the results for the SIFT dataset, the accuracy isrelatively low. This is due to the high-dimensionality of the GIST
descriptor; while the dimension of the GIST subvector is threetimes larger than the SIFT subvector, they are coded with thesame length (bits) in the experiments.
Figure 11 shows Recall@R for 1M GIST vectors obtained using a diﬀerent number of PQ codebooks, where the number ofsubvectors is increased from 8 to 24. Accordingly, the size ofshort codes for the GIST vectors is increased from 8 bytes to
24 bytes. This is the same condition as the 8-byte short codes
for the SIFT vectors in terms of bits per dimension. From the117

IPSJ Transactions on Computer Vision and Applications Vol.4 108–118 (Oct. 2012)

Table 5 The average number of searched candidates and Recall@∞ for the
SIFT and GIST vectors with diﬀerent w.

# of candidates
Recall@∞SIFT
w=1
w = 16
1,041
17,2450.45850.9602w=1
1,291
0.2968GIST
w=8
10,486
0.7218w = 6478,7240.9596

[14]
[15]
[16]
[17]

figure, it is found that the proposed method also improves theaccuracy compared with the conventional method. Comparing
the proposed method with m = 8, r = 8 (Fig. 10 (c)) and the
proposed method with m = 24, r = 24 (Fig. 11 (c)), in the casewhere w = 64, Recall@10 is significantly improved from 0.438
to 0.648. Therefore, it can be said that the proposed method,
as well as the PQ-based approximate NNS, works well for highdimensional vectors. An important point to be noted is that theaccuracy is bounded by Recall@∞ irrespective of the number ofsubvectors. Table 5 summarizes the average number of searchedcandidates and Recall@∞ for the SIFT and GIST vectors with
diﬀerent w. For the GIST vectors, w should be larger than that of
the SIFT vectors to obtain the same accuracy, due to the curse ofdimensionality.

5. Conclusion
We have proposed an optimized multiple codebook construction algorithm for approximate nearest neighbor search based on
product quantization. The algorithm iteratively optimizes bothcodebooks for product quantization and an assignment table thatindicates the optimal codebook in product quantization. Experimental results showed that the proposed method considerably
improves the accuracy of approximate nearest neighbor searchat the cost of a small increase of the memory required to store thecodebooks.
References
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]

Lowe, D.G.: Distinctive Image Features from Scale-Invariant Keypoints, IJCV, Vol.60, No.2, pp.91–110 (2004).
Oliva, A. and Torralba, A.: Modeling the Shape of the Scene: A
Holistic Representation of the Spatial Envelope, IJCV, Vol.42, No.3,
pp.145–175 (2001).
Friedman, J.H., Bentley, J.L. and Finkel, R.A.: An Algorithm for
Finding Best Matches in Logarithmic Expected Time, TOMS, Vol.3,
No.3, pp.209–226 (1977).
Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R. and Wu, A.Y.:
An Optimal Algorithm for Approximate Nearest Neighbor Searchingin Fixed Dimensions, JACM, Vol.45, No.6, pp.891–923 (1998).
Andoni, A.: Near-Optimal Hashing Algorithms for Approximate
Nearest Neighbor in High Dimensions, Proc. FOCS, pp.459–468(2006).
Philbin, J., Chum, O., Isard, M., Sivic, J. and Zisserman, A.: Object retrieval with large vocabularies and fast spatial matching, Proc.
CVPR, pp.1–8 (2007).
Silpa-Anan, C. and Hartley, R.: Optimised KD-trees for Fast Image
Descriptor Matching, Proc. CVPR, pp.1–8 (2008).
Muja, M. and Lowe, D.G.: Fast Approximate Nearest Neighborswith Automatic Algorithm Configuration, Proc. VISAPP, pp.331–340(2009).
Beis, J. and Lowe, D.G.: Shape Indexing Using Approximate
Nearest-Neighbour Search in High-Dimensional Spaces, Proc. CVPR,
pp.1000–1006 (1997).
Kulis, B. and Darrell, T.: Learning to Hash with Binary Reconstructive
Embeddings, Proc. NIPS, pp.1042–1050 (2009).
Nistér, D. and Stewénius, H.: Scalable Recognition with a Vocabulary
Tree, Proc. CVPR, pp.2161–2168 (2006).
Weiss, Y., Torralba, A. and Fergus, R.: Spectral Hashing, Proc. NIPS,
pp.1753–1760 (2008).
Jégou, H., Douze, M. and Schmid, C.: Product Quantization for Nearest Neighbor Search, TPAMI, Vol.33, No.1, pp.117–128 (2011).

c 2012 Information Processing Society of Japan


[18]
[19]
[20]

Jia, Y., Wang, J., Zeng, G., Zha, H. and Hua, X.S.: Optimizing kdtrees for scalable visual descriptor indexing, Proc. CVPR, pp.3392–
3399 (2010).
Brandt, J.: Transform Coding for Fast Approximate Nearest Neighbor
Search in High Dimensions, Proc. CVPR, pp.1815–1822 (2010).
Arthur, D. and Vassilvitskii, S.: k-means++: The Advantages of Careful Seeding, Proc. SODA, pp.1027–1035 (2007).
Mikolajczyk, K., Tuytelaars, T., Schmid, C., Zisserman, A., Matas, J.,
Schaﬀalitzky, F., Kadir, T. and Gool, L.V.: A Comparison of Aﬃne
Region Detectors, IJCV, Vol.60, No.1–2, pp.43–72 (2005).
Torralba, A., Fergus, R. and Freeman, W.T.: 80 Million Tiny Images:
A Large Data Set for Nonparametric Object and Scene Recognition,
TPAMI, Vol.30, No.11, pp.1958–1970 (2008).
Fei-Fei, L. and Perona, P.: A Bayesian hierarchical model for learning
natural scene categories, Proc. CVPR, pp.524–531 (2005).
Philbin, J., Chum, O., Isard, M., Sivic, J. and Zisserman, A.: Lost
in Quantization: Improving Particular Object Retrieval in Large Scale
Image Databases, Proc. CVPR, pp.1–8 (2008).

Yusuke Uchida received his Bachelor
degree of Integrated Human Studies from
Kyoto University, Kyoto, Japan, in 2005.
He received the degree of Master of Infomatics from Graduate School of Infomatics, Kyoto University, in 2007.
His research interests include large-scale
content-based multimedia retrieval, augmented reality, and image processing. He is currently with KDDI
R&D Laboratories, Inc.

Koichi Takagi received his B.E. and
M.E. degree from the Tokyo Institute ofTechnology in 1996 and 1998 respectively. He has been working at Kokusai
Denshin Denwa since 1998 and now is amanager in Technology Strategy Department at KDDI Corporation. From 1998 to2012, he was with KDDI R&D Laboratories, Inc. and worked in the area of video and audio processing,in particular coding and watermarking. He is a member of IPSJ.

Shigeyuki Sakazawa received his B.E.,
M.E., and Ph.D. degrees from Kobe University, Japan, all in electrical engineering, in 1990, 1992, and 2005 respectively. He joined Kokusai Denshin Denwa(KDD) Co. Ltd. in 1992. Since thenhe has been with its R&D Division, andnow he is a senior manager of Media andHTML5 Application Laboratory in KDDI R&D Laboratories
Inc., Saitama, Japan. His current research interests include videocoding, video communication system, image recognition and CG
video generation. He received the best paper award from IEICE
in 2003.

(Communicated by Naoko Nitta)

118