IPSJ Transactions on Computer Vision and Applications Vol.5 153–162 (Aug. 2013)[DOI: 10.2197/ipsjtcva.5.153]

Research Paper

Large-scale Image Retrieval as a Classification Problem
Yusuke Uchida1,a)Shigeyuki Sakazawa1

Received: October 10, 2012, Accepted: April 30, 2013, Released: August 23, 2013

Abstract: In this paper, we propose a new, eﬀective, and unified scoring method for local feature-based image retrieval. The proposed scoring method is derived by solving the large-scale image retrieval problem as a classification
problem with a large number of classes. The resulting proposed score is based on the ratio of the probability density
function of an object model to that of a background model, which is eﬃciently calculated via nearest neighbor density
estimation. The proposed method has the following desirable properties: (1) has a sound theoretical basis, (2) is more
eﬀective than inverse document frequency-based scoring, (3) is applicable not only to quantized descriptors but also
to raw descriptors, and (4) is easy and eﬃcient in terms of calculation and updating. We show the eﬀectiveness of the
proposed method empirically by applying it to a standard and improved bag-of-visual words-based framework and ak-nearest neighbor voting framework.
Keywords: specific object recognition, bag-of-visual words, approximate nearest neighbor search, Hamming embedding, product quantization, naive-bayes nearest-neighbor

1. Introduction
With the advancement of both stable interest region detectors [1] and robust and distinctive descriptors [2], local featurebased image or object retrieval has attracted a great deal of attention. Particularly, it has become applicable to large-scale
databases with a bag-of-visual words (BoVW) framework [3].
Figure 1 illustrates the standard framework of a BoVW-based
image retrieval system. In the BoVW framework, local featurepoints or regions are detected from an image, and feature vectors
are extracted from them. These feature vectors are quantized into
visual words (VWs) using a visual codebook (visual vocabulary),
resulting in a histogram representation of VWs. Image similarity is measured by 1 or 2 distance between the normalized histograms. As VW histograms are generally sparse, an inverted
index data structure and a voting function enable an eﬃcient similarity search. The equivalency between 2 distances and scoresobtained with the voting function is described in Ref. [4] in detail. A weighting scheme based on inverse document frequency(IDF) [3], [5] is integrated with the voting function to improve
performance. Finally, geometric verification [6] is performed torefine and re-rank the results obtained with the voting function.
Although the BoVW framework realizes eﬃcient retrieval,
there is some room for improvement in terms of accuracy. One
significant drawback of VW-based matching is a hard-assignment
problem: two features are considered to be matched if and only
if they are assigned to the same VW [4]. There are two major extensions of VW-based matching designed to alleviate thisproblem: post-filtering approaches [4], [7] and multiple assignment (or soft assignment) approaches [4], [8]. In post-filtering
approaches, after VW-based matching, unreliable matches are fil1a)KDDI R&D Laboratories, Inc., Fujimino, Saitama 356–8502, Japan
ys-uchida@kddilabs.jp

c 2013 Information Processing Society of Japan

tered out according to (estimated) distances between query andreference features. In multiple assignment approaches, query features are matched not only with reference features assigned to thenearest VW but also with reference features assigned to the knearest VWs.
In this paper, in order to solve these problems, we propose
a new, unified scoring method applicable to many conventionalframeworks. The optimal scoring method is derived by solving
the large-scale image retrieval problem as a classification problem with a large number of classes. The proposed score is basedon the ratio of the probability density function of an object model
to a background model, which is eﬃciently calculated in an onthe-fly manner via nearest neighbor density estimation. In experiments, we show the eﬀectiveness and versatility of the proposedscoring method by applying it to a BoVW framework and a knearest neighbor voting framework. This paper is the extended
version of the paper [9] that appeared in ICPR 2012. Particularly, we conduct detailed experiments in terms of the parameterin the proposed method and discuss the eﬀect of normalization
term in the proposed score. Furthermore, the proposed method
is thoroughly compared with original classification method andstate-of-the-art methods.

2. Improving BoVW-based Image Retrieval
In this section, an overview is provided of related work which
improves BoVW-based image retrieval in terms of feature matching and the problems associated with conventional methods are
outlined at the end of this section.
There are two major approaches used to improve the performance of BoVW-based image retrieval in terms of feature
matching: post-filtering approaches and multiple assignment approaches. Post-filtering and multiple assignment respectively
contributes to the precision and recall of feature matching, and153

IPSJ Transactions on Computer Vision and Applications Vol.5 153–162 (Aug. 2013)

Fig. 1 Standard framework of local feature-based image retrieval system.

they are complementary. Both approaches are reviewed in thissection.
Several methods have also been proposed with the intentionof improving the performance of BoVW-based image retrieval
other than the approaches mentioned above such as the utilization of spatial information [4], [10], [11], [12], [13], query expansion approaches [14], [15], [16], and re-ranking based on knearest neighbors [13], [17]. These methods are complementary
to the proposed method and not discussed in detail in this paper.
2.1 Post-filtering Approaches
As the naive BoVW framework suﬀers from many false
matches of local features, post-filtering approaches are proposed
to suppress unreliable feature matches [4]. In this section, an
overview of post-filtering approaches to improve naive VW-based
image retrieval is presented. There are two important componentsof post-filtering approaches: distance estimation and filtering criteria.
2.1.1 Distance Estimation
As mentioned previously, after VW-based matching, distances
between a query feature and reference features that are assigned
to the same visual word as the query feature are estimated forpost-filtering. As distance calculations between an original queryfeature vector and original reference feature vectors are undesirable in terms of computational cost and memory requirement tostore raw reference feature vectors [18], short code based methods are used for this purpose. Feature vectors are encoded into
short codes and distances between feature vectors are approximated by distances between the short codes. This approach improves time eﬃciency and reduces memory requirement in the
distance calculation. Two diﬀerent distance estimation methods
are described below.
◦ Hamming embedding (HE): In Refs. [4], [19], feature vectors extracted from reference images are encoded into binary
codes (typically 32–128 bit codes) via random orthogonal
projection followed by thresholding for binarizing projected
vectors. While all VWs share a single random orthogonal
matrix, each VW has individual thresholds so that feature
vectors are binarized into 0 or 1 with the same probability. These codes are stored in an inverted index with image identifiers (sometimes with other information on the features [19]). In a search step, after VW-based matching, Hamming distances between codes of query and matched refer-c 2013 Information Processing Society of Japanence features are calculated. Matched features with larger
Hamming than a predefined threshold are filtered out, as thisconsiderably improves the precision of matching with only
slight degradation of recall.
◦ Product quantization (PQ): In Ref. [18], a productquantization-based method is proposed and shown tooutperform other short codes like spectral hashing (SH) [20]or a transform coding-based method [21] in terms of the
trade-oﬀ between code length and accuracy in approximate
nearest neighbor search. In the PQ method, a reference feature vector is decomposed into low-dimensional subvectors.
Subsequently, these subvectors are quantized separately
into a short code, which is composed of corresponding
centroid indices. The distance between a query vector anda reference vector is approximated by the distance between
a query vector and the short code of a reference vector.
Distance calculation is eﬃciently performed with a lookup
table. Note that the PQ method directly approximates the
Euclidean distance between a query and reference vector,
while the Hamming distance obtained by the HE method
only reflects their similarity.
2.1.2 Filtering Criteria
Based on the estimated distances described above, unreliablefeature matches are filtered out. There is room for discussion on
how to utilize the distances. To date, several criteria are used for
filtering.
◦ Distance criterion: The most straightforward way is to filter
out reference features with larger (approximated) distances
than the predefined threshold [4], [22].
◦ Rank criterion: The alternative is to use the k-nearest neighbor features in voting and to filter out the others [18]. In
this case, for each feature vector in a query image, reference
features are sorted according to distances between the queryfeature and the reference features in ascending order, andcorresponding top-k reference features are used in voting.
◦ Ratio criterion: In the same way as the rank criterion, for eachfeature vector in a query image, distances between the queryfeature and reference features in the same VW are sorted inascending order. Then reference features in the top-p percentile are used in voting [7].
2.2 Multiple Assignment Approaches
While post-filtering approaches try to improve the precision offeature matches with only slight degradation of recall, multiple
assignment approaches improve recall at the cost of the precision of feature matches. The basic idea here is, at a search step,to assign a query feature not only to the nearest VW but to theseveral nearest VWs. This technique alleviates the problem ofquantization error; sometimes, similar features are assigned to
diﬀerent VWs. In Ref. [8], each query feature is assigned to the
fixed number of the nearest VWs and the influence of a matchedfeature to image similarity is weighted according to the distance
between the query feature and the assigned VWs. In Ref. [4], thedistance d0 to the nearest VW from a query feature is used todetermine the number of multiple assignments, where the queryfeature is assigned to the VWs such that the distance to the VWs

154

IPSJ Transactions on Computer Vision and Applications Vol.5 153–162 (Aug. 2013)

is smaller than αd0 (α = 1.2 in Ref. [4]). This approach adaptively changes the number of assigned VWs according to the ambiguity of the feature. As post-filtering approaches and multiple
assignment approaches are complementary, it is desirable to use
multiple assignment in conjunction with post-filtering.
2.3 Scoring of Feature Matches
After feature matching as described above, scores of feature
matches should be determined to vote the scores to the corresponding reference images. The square of the IDF value associated with the corresponding VW is used as a base score [3].
At the same time, weighting terms related to distance metrics and filtering criteria are considered for further improvement [4], [7], [23], [24].
In Ref. [23], the weight is calculated as a Gaussian function ofa Hamming distance between the query and reference vector. In
Ref. [4], the weight is calculated based on the Hamming distance
between the query and reference vector and the probability massfunction of the binomial distribution. In Ref. [24], the weight iscalculated based on rank information because a rank criterion isused in post-filtering in the literature, while in Ref. [7], the weightis calculated based on ratio information. Thus, as mentioned
before, these scoring methods have been specialized to certain
frameworks, i.e., they depend on distance metrics and filtering
criteria. Hence, they require trial-and-error processes when being
applied to diﬀerent frameworks. In addition, because these scoring methods have little theoretical basis and are not optimal, they
result in unsatisfactory performance compared with their potential. Therefore, a comprehensive scoring method is needed thathas a theoretical basis and is applicable to any frameworks without having to consider and try many diﬀerent scoring methods.

3. Proposed Approach
In this section, in order to solve the problems mentioned before, a unified scoring method is proposed. The proposed scoring
method is derived by solving the large-scale image retrieval problem as a classification problem with a large number of classes,
which can be applied to many existing frameworks. We firstpresent the probabilistic formulation of the proposed scoring
method, starting with a classification problem similar to Ref. [25].
Then, in order to make it applicable to large-scale image retrieval,an approximation is introduced. Finally, the detailed formulationof the proposed score is obtained via non-parametric density ratio
estimation.
3.1 Probabilistic Formulation
Given a query image Q, the objective is to find a similar image
R ĵ from a large number of reference images R1 , · · · , Rm . In thispaper, we consider images to be similar if they share a same object [26]. Considering it as a classification problem, we start withmaximum-a-posteriori estimation: ĵ = arg max j p(R j |Q). Assuming p(R j ) is uniform, the maximum-a-posteriori estimation
reduces to a maximum likelihood estimation:ĵ = arg max p(R j |Q) = arg max p(Q|R j ).
j

j

(1)

Letting Q = {q1 , · · · , qn } denote the descriptors of the query im-

c 2013 Information Processing Society of Japanage Q, with the naive Bayes assumption, we get:p(Q|R j ) = p(q1 , · · · , qn |R j ) =n

p(qi |R j ).

(2)

i=1

As pointed out in Ref. [25], if we assume all query descriptors arederived from only the object model O j of R j , p(Q|R j ) tends to be
too small even if Q and R j share the same object. In Ref. [25], theproblem is alleviated by estimating p(qi |R j ) using a few dozen images representing the same class. As this is not practical for largescale image or object retrieval, we directly model p(qi |R j ) by a
mixture of the object model O j of R j and a background model B
distinct from O j :p(qi |R j ) = λp(qi |O j ) + (1 − λ)p(qi |B).

(3)

If we deal with only the quantized version of descriptors (visual
words), this is identical to language modeling (LM) [5] in the areaof information retrieval (IR). Combining Eqs. (1)–(3), we obtain:ĵ = arg max
j= arg maxj= arg max
j

n

i=1
n

i=1
n

i=1

p(qi |R j ) = arg max
jn

log p(qi |R j )i=1log(λp(qi |O j ) + (1 − λ)p(qi |B))log


λ p(qi |O j )+1 .
1 − λ p(qi |B)

Finally, we get the voting score si j :
λ p(qi |O j )+1 .
si j = log
1 − λ p(qi |B)

(4)

(5)

For each qi , the voting score si j is assigned to each R j . The re
sulting score s j = i si j corresponds to the similarity measure
between Q and R j .
3.2 Approximation with Nearest Neighbors
In the above formulation, it is necessary to calculate si j for all
R j . Similarly, minr∈R j ||qi − r||2 should be calculated for all R j
in Ref. [25], where R j denotes a set of descriptors of R j . These
processes involve finding nearest neighbors of qi from R j foreach R j . Letting nC denote the number of classes and nD denote the average number of descriptors in an image, the calculation of si j for all R j has a time cost of O(nC · nD ) if brute-force
search is adopted. This can be accelerated from O(nC · nD ) toO(nC · log nD ) by using eﬃcient approximate nearest neighborsearch algorithms [18], [27], [28] which can find approximate
nearest neighbors of qi from nD descriptors in O(log nD ). The
computational cost does not become a fatal flaw in classification
problems where nD  nC . However, it is intractable in the largescale image retrieval problem where nC  nD because nC corresponds to the number of images or objects in a database.
In order to make it tractable, the following simple approximation is adopted. We assume the set of nearest neighbor descriptors
N(qi ) of qi (e.g., k-nearest neighbors of qi ) was obtained against
all reference descriptors. Then, p(qi |O j ) is calculated only for
R j at least one of whose descriptors appears in N(qi ), and otherwise we assume p(qi |O j ) = 0. Because the voting score si j

155

IPSJ Transactions on Computer Vision and Applications Vol.5 153–162 (Aug. 2013)

Fig. 2

An example of multiple levels of neighbors N1 (qi ), · · · , Nk (qi ) of qi
in the feature space (k = 3).

becomes 0 if p(qi |O j ) = 0, the voting is performed eﬃciently.
With this approximation, the computational cost is reduced from
O(nC ·log nD ) to O(log nC ·nD ) because approximate nearest neighbors of qi are searched from nC · nD descriptors only once insteadof searching nearest neighbors from nD descriptors and repeating
nC times.
3.3 Non-parametric Density Ratio Estimation
Finally, the voting score si j is calculated using N(qi ). As
shown in Fig. 2, we assume that multiple levels (subsets) of
neighbors N1 (qi ), · · · , Nk (qi ) of qi are defined, which satisfy
N1 (qi ) ⊂ N2 (qi ) ⊂ · · · ⊂ Nk (qi ) = N(qi ),(6)

where N1 (qi ) is the most fine-grained level of neighbors of qi andNk (qi ) is the most coarse-grained level of neighbors of qi . An
intuitive and practical example of Nt (qi ) is the t nearest neighbordescriptors of qi . For each Nt (qi ) (1 ≤ t ≤ k), and for each R j
one of whose descriptors appears in Nt (qi ), the densities p(qi |O j )and p(qi |B) in Eq. (5) are estimated via k-nearest neighbor density
estimation:p(qi |O j ) =|Nt (qi )| j
|Nt (qi )|all, p(qi |B) =.
|R j | · Vt
|Rall | · Vt

(7)where |Nt (qi )| j is the number of descriptors of R j that appear in
Nt (qi ), Rall is all reference descriptors j R j , Vt is the volume ofa hypersphere with radius ||qi − r̂t ||2 , and r̂t ∈ Nt (qi ) is the farthest descriptor from qi . Combining Eqs. (5) and (7), we obtainthe score sti j for Nt (qi ):
λ |Nt (qi )| j /|R j |sti j = log+1 ,1 − λ |Nt (qi )|all /|Rall |(8)where the normalization terms about the numbers of descriptors
in a query image and reference images are naturally considered
as |R j | and |Rall |. We adopt t such that it maximizes sti j for each qi
and R j :si j = max sti j .
1≤t≤k

(9)

If we adopt fixed t = k, the information of the multiple levels ofneighbors N1 (qi ), · · · , Nk (qi ) is discarded and only the information of the most coarse-grained level of neighbors Nk (qi ) is used,
resulting in the degradation of accuracy. For instance, in Fig. 2,
we assume that the two blue cross marks represent the descriptors of R1 and the two red cross marks represent the descriptorsof R2 . Intuitively, an inequality p(qi |O1 ) > p(qi |O2 ) holds. If we

c 2013 Information Processing Society of Japan

Fig. 3 Overview of the improved BoVW framework based on productquantization.

adopt the definition of Eq. (9), t = 1 is selected for R1 and t = 3 isselected for R2 , resulting in distinctive scores si1 > si2 . However,
if fixed t = 3 is used for both of R1 and R2 , si1 becomes equal tosi2 . The eﬀect of Eq. (9) is empirically evaluated in Section 5.2.
More concrete examples of the formulation are shown in thefollowing section. One advantage of this scoring method is thatan up-to-date score is eﬃciently calculated in an on-the-fly manner using N(qi ), even if the database is modified. The only requirement is to store the number of descriptors |R j | in each reference image.

4. Implementation Details
Although the proposed scoring method described in Section 3
can be applied to many conventional frameworks by appropriately defining the nearest neighbors N1 (qi ), · · · , Nk (qi ) = N(qi )of qi , we mainly apply the proposed method to one of the state-ofthe-art frameworks (described in Section 2) which improves the
BoVW framework by having distance estimation based on product quantization [7], [18]. In this section, we describe the framework evaluated in the experiments in detail. Figure 3 provides an
overview of the framework.
4.1 Feature Detection and Description
From query and reference images, a set of feature vectors is extracted. We adopt Hessian-Aﬃne [29] and SIFT [30] as the feature detector and descriptor, respectively. The software *1 provided by the authors of Ref. [1] is used in the experiments. We
denote the i-th feature vector of the query image by qi ∈ Q and
the h-th feature vector of the j-th reference image by r jh ∈ R j .
4.2 Feature Indexing with Product Quantization
We adopt a product quantization-based method [7], [18] to improve the BoVW framework, namely IVFADC. In the indexing(oﬀ-line) step in IVFADC, a reference vector r jh with d dimension *2 is quantized with a coarse quantizer in the same way as
the BoVW framework. We refer to the codebook used in coarse
quantization as the CQ codebook. This is the same as what is*1*2

http://www.featurespace.org/
In the case of SIFT vectors, d = 128.

156

IPSJ Transactions on Computer Vision and Applications Vol.5 153–162 (Aug. 2013)referred to as visual words or a visual codebook in the context of
BoVW-based image retrieval or recognition.
In the indexing step, a reference vector r jh is first quantized intocâ using the CQ codebook C with k centroids c1 , · · · , ck ∈ Rd ,whereâ = arg min  ||r jh − ca ||2 .

(10)

1≤a≤k

Subsequently, the residual vector r̄ jh from the corresponding centroid câ is calculated asr̄ jh = r jh − câ .

(11)Then, the residual vector r̄ jh is decomposed into u subvectors∗r̄1jh , · · · , r̄ujh ∈ Rd , where d∗ = d/u. Subsequently, these subvectors are quantized separately using u codebooks P1 , · · · , Pu ,which is referred to as product quantization. In this paper, a codebook used in product quantization is referred to as a PQ codebook. We assume that each PQ codebook Pl has k∗ centroids∗
pl1 , · · · plk∗ ∈ Rd . Using the l-th PQ codebook, the l-th subvectorr̄ljh is quantized into plbl , where
bl = arg min ∗ ||r̄ljh − plb ||2 .

(12)

1≤b≤k

Finally, the short code (b1 , · · · , bu ) is stored in the â-th list of theinverted index with the identifier j of the reference image. The
size of the short code is represented by u log2 k∗ bits.
4.3 Distance Calculation in IVFADC
In the search step in IVFADC, a query vector qi is first quantized using the CQ codebook, and the residual vector q̄i from thecorresponding centroid is calculated in the same manner as theindexing. Subsequently, the distance between the residual vector q̄i and short codes (b1 , · · · , bu ) in the corresponding list in the
inverted index are calculated. These distances correspond to theapproximate distances between the query vector qi and the reference vectors r jh :d(qi , r jh ) = d(q̄i , r̄ jh ) ≈u||q̄li − plbl ||2 .

(13)

l=1

This distance calculation is performed eﬃciently using a lookup
table T , which is precomputed when a query vector qi is given:
T lb = ||q̄li − plb ||2 (1 ≤ l ≤ u, 1 ≤ b ≤ k∗ ).

(14)

Using the table, Eq. (13) is rewritten asd(qi , r jh ) ≈uT lbl .

(15)

l=1

4.4 Voting with the Proposed Scoring Method
After the distance calculation described in Section 4.3, pairs ofimage identifier and distance are obtained. These pairs are sorted
according to the distances and top-k results are used to calculate
the proposed score described in Section 3 in voting. In this case,the t-th subset Nt (qi ) in Eq. (6) is defined as t nearest vectors of qi .
In this paper, we refer to this framework as the k-nearest neighbor(k-NN) voting framework. The voting algorithm is summarizedc 2013 Information Processing Society of Japan

Algorithm 1 k-NN voting function with the proposed score
Require: Q = {qi }ni=1 , {R j }mj=1
Ensure: s j ← similarity score between Q and R j (1 ≤ j ≤ m)
1: s1 , · · · , sm ← 0
2: for i = 1 to n do
3:z1 , · · · , zm ← 0
4:
c1 , · · · , cm ← 0
5:
r1 , · · · , rk ← (approximate) k nearest vectors of qi among {R j }mj=1
6:
for t = 1 to k do
7:
jt ← the reference identifier associated with rt
8:
c jt ← c jt + 1
9:if v jt < c jt /t then10:v jt ← c jt /t
11:
end if
12:
end for13:
for j = 1 to m do14:
s j ← s j + log(α j z j + 1)
15:
end for
16: end forTable 1 Summary of diﬀerent versions of the proposed method.
Section§5.2

Voting framework
BoVW

§5.3

Improved BoVW

§5.4

k-NN

Nt (qi )A set of reference descriptors thatare quantized into one of t nearest
VWs of qi .
A set of t nearest reference descriptors of qi .
A set of t nearest reference descriptors of qi .

in Algorithm 1.
In Algorithm 1, given query vectors Q and reference vectors
R1 , · · · , Rm , similarity scores s1 , · · · , sm between a query image
Q and reference images R1 , · · · , Rm are obtained. For each query
vector qi , k-nearest vectors r1 , · · · , rk of qi are obtained in Line 5.
In Lines 6–12, maxt |Nt (qi )| j /|Nt (qi )|all in Eq. (8) is obtained as z j ,where |Nt (qi )| j = c j and |Nt (qi )|all = t. In Line 14, the proposed
score is calculated and voted to the reference image R j , where α j
is precomputed using constant values in Eq. (8) for eﬃciency:
αj =λ 1/|R j |.
1 − λ 1/|Rall |(16)

Algorithm 1 is applicable not only to product quantization-based
approximate nearest neighbor search but also applicable to any(approximate) nearest neighbor search algorithms such as locality sensitive hashing [31] as shown in Section 5.4.
In this paper, the parameters recommended in Ref. [18] areused; the size of the CQ and PQ codebooks k and k∗ are set to
20,000 and 256 respectively, and the number of vector decomposition u is set to 8.

5. Experimental Evaluation
In this section, we show the eﬀectiveness and versatility of the
proposed scoring method by applying it to the BoVW framework(Section 5.2), the improved BoVW framework (Section 5.3),
and the locality sensitive hashing-based k-NN voting framework(Section 5.4). Table 1 summarizes the diﬀerent versions of the
proposed method evaluated in the experiments.

157

IPSJ Transactions on Computer Vision and Applications Vol.5 153–162 (Aug. 2013)

5.1 Experimental Setup
In the experiments, three distinct publically available datasets
are used. The details of these datasets are summarized as follows.
◦ Kentucky: The University of Kentucky recognition benchmark dataset *3 is provided by the authors of Ref. [26]. It
includes 2,550 diﬀerent objects or scenes. Each of these objects is represented by four images taken from four diﬀerent
angles, making 10,200 images in all. These images are usedas both reference and query images. This dataset is used in
Sections 5.2 and 5.3, focusing on large-scale image retrieval.
◦ Stanford MVS: The Stanford mobile visual search dataset *4contains camera-phone images of products, CDs, books, outdoor landmarks, business cards, text documents, museum
paintings and video clips. While it includes eight classes
of images, we use CD class images in this paper. These images consist of 100 reference images and 400 query images.
In the experiments, all images are resized so that the longsides of images are less than 640 pixels, keeping the original
aspect ratio. This dataset is used in Section 5.4, focusing on
image recognition on mobile phones.
◦ MIRFLICKR-1M: The MIR Flickr collection *5 is provided
by the authors of Ref. [32]. It includes 1 million images
downloaded from the social photography site FlickrTM . We
use this dataset as a distractor set in order to confirm thescalability of the proposed method in Sections 5.3 and 5.4.
Figure 4 shows sample images from the three datasets.
As an indicator of retrieval performance, mean average precision (MAP) [4], [26] is used. For each query, a precision-recall
curve is obtained based on the retrieval results. Average precision
is calculated as the area under the precision-recall curve. Finally,
the MAP score is calculated as the mean of average precisions
over all queries. Because the applications of the proposed method
only modify the scoring part of the conventional frameworks, thecomputational cost and database size of the proposed method istheoretically the same as the conventional methods. Therefore,
in the experiments, we focus on the evaluations of the proposedscoring method in terms of accuracy.
5.2 Application to the BoVW Framework
In order to show the eﬀectiveness and versatility of the proposed scoring method, first it is applied to the standard BoVW
framework [3]. In this case, a set of the nearest neighbor descriptors N(qi ) of qi is defined as a set of reference descriptors that arequantized into the same VW as qi . As subsets of N(qi ) in Eq. (6),only a single subset (k = 1) is defined:
N(qi ) = N1 (qi ) = {r ∈ Rall | q(r) = q(qi )},(17)

where q(r) and q(qi ) denote the identifiers of the nearest neighbor
VWs of r and qi . Then, si j is calculated using only frequencies of
VWs:
⎛
⎞
i)
⎜⎜⎜ λ tf q(q⎟⎟⎟/|R j |jsi j = log ⎜⎜⎝⎜
(18)
+ 1⎟⎟⎠⎟ ,q(q)
1 − λ tf i /|Rall |
all
*3
*4
*5

http://www.vis.uky.edu/˜stewe/ukbench/
http://www.stanford.edu/˜dmchen/mvs.html
http://press.liacs.nl/mirflickr/

c 2013 Information Processing Society of Japan(a) Kentucky dataset. Images in each row represent the same object.

(b) Stanford MVS dataset. Images in the top row are examples of reference
images and images in the bottom row are examples of query images.

(c) MIRFLICKR-1M dataset.
Fig. 4

Example images from three datasets used in the experiments.

Fig. 5 Comparison of scoring methods in the BoVW framework.

where tf wj represents the frequency of the w-th VW in R j , and tf wall
the frequency of the w-th VW in all reference images.
The above proposed score si j is evaluated using the Kentucky
dataset. Figure 5 shows the MAP scores obtained with diﬀerent scoring methods as a function of λ (valid only for the proposed method). The following three scoring methodsare com
q(q )
w 2
pared: (1) Baseline uses normalized frequency tf j i /w (tf j )q(q )of q(qi )-th VW, (2) IDF uses IDF weighted frequency tf j i ·w
w 2(idf q(qi ) )2 /w (tf j · idf ) , and (3) Prop uses si j in Eq. (18) as avoting score, respectively. The IDF weight of the w-th VW is calculated according to the number of all reference images and thenumber of reference images which have at least one descriptor
assigned to the w-th VW:

158

IPSJ Transactions on Computer Vision and Applications Vol.5 153–162 (Aug. 2013)

Table 2 Comparisons of the proposed method with the IDF method.
Object ID
466
631
2068
1741
1315

(a) Best 5 objects.
Prop
IDF
Diﬀ.
0.888
0.484
+0.4041.0
0.604+0.3960.942
0.559+0.3830.954
0.574+0.3800.869
0.491+0.378#descriptors
304
1,828
973
386
1,698

Object ID
1820
2297
2331
1828
2184

(b) Worst 5 objects.
Prop
IDF
Diﬀ.
0.523
0.986
−0.4630.582
1.0−0.4180.534
0.911−0.3770.585
0.865−0.2800.582
0.818−0.236#descriptors
4,358
4,238
4,316
4,758
3,708

idf w = log|{R j }|.
|{R j | tf wj > 0}|(19)

Although the IDF weighting significantly improves the accuracyof the baseline scoring method, the proposed method achieves
further improvement. In addition, the accuracy is not so sensitive
to the choice of λ. The best MAP score of 0.814 is achieved withrelatively small λ (λ = 0.07), which implies that there are a small
number of features useful for object recognition [33]. Objectwise MAPs are also calculated for 2,550 objects. Table 2 summarizes (a) the best 5 objects and (b) the worst 5 objects of the
proposed method compared with the IDF method. In the table,
object identifiers, the MAP scores of the proposed method andthe IDF method, the diﬀerences of them, and the average numbersof descriptors are shown. We found that the proposed method
performs better than the IDF method for objects with small numbers of descriptors, while worse for objects with large numbersof descriptors; on average, the proposed method outperforms the
IDF method. This is related to the normalization terms associated with the number of descriptors |R j | of a reference image: inthe proposed method, each score is approximately proportional
to log(C/|R j | + 1) according to Eq. (8) or Eq. (18), while, in thecase of the IDF method with 2 normalization, each score is approximately proportional to |R j |−1/2 . Figure 6 shows the graphof y = log(2,000/x + 1)/x−1/2 , which represents the ratio of thescore in the proposed method to the score in the IDF method as afunction of the number of descriptors in a reference image *6 . The
scores of the proposed method are relatively small compared with
the IDF method for images with large numbers of descriptors.
In the BoVW framework, the proposed scoring method can beused in conjunction with the multiple assignment approaches described in Section 2.2. For simplicity, we adopt a fixed number
k for multiple assignment. In this case, the t-th subset Nt (qi ) in
Eq. (6) is defined as a set of reference descriptors that are assigned
to one of the t nearest VWs of qi :{r ∈ Rall | q(r) = q s (qi )},(20)
Nt (qi ) =1≤s≤t

where q s (qi ) denotes the identifier of the s-th nearest VW of
*6

q(q )

q(q )

We assume that λ = 0.1, tf j i = 1, and tf all i /|Rall | = 1/20,000 inq(q )Eq. (18), resulting C
2,000. The term tf all i /|Rall | is approximately
equal to the probability 1/k with which a descriptor is assigned to a certain visual word, where k (= 20,000) is the number of the visual words.

c 2013 Information Processing Society of Japan

Fig. 6 The ratio of the score in the proposed method to the score in the IDF
method as a function of the number of descriptors in a reference image. The average number of descriptors in the Kentucky dataset isabout 1,700.

Fig. 7 Evaluation of the proposed scoring method under diﬀerent settings.

qi . Figure 7 shows the MAP scores obtained with the proposedscoring method with diﬀerent settings as a function of λ. Prop,
Propmax k = 3, and Propmax k = 5 represent the results of the proposed scoring methods where k is respectively 1, 3, and 5. We
can see that the proposed scoring method is eﬀective even if it isused in conjunction with multiple assignment approaches. The
best MAP score is improved from 0.814 (k = 1, λ = 0.07) to
0.838 (k = 3, λ = 0.1) and 0.846 (k = 5, λ = 0.1).
In Fig. 7, the modified version of the proposed scoring method
is also compared. Propfixed uses the fixed t = k in the calculation of the proposed score; the score is defined as si j = skij
instead of the original definition si j = max1≤t≤k sti j in Eq. (9).
However, in this case, the degree of improvement attained bymultiple assignment is not significant compared with the original scoring method. The best MAP scores of Propfixed k = 3
and Propfixed k = 5 are 0.823 (λ = 0.1) and 0.825 (λ = 0.1), respectively. This is because, if the fixed t = k is used, the useful
information of the multiple subsets N1 (qi ), · · · , Nk (qi ) cannot be
exploited.
5.3 Application to the improved BoVW Framework
In this section, the proposed scoring method is applied to theimproved BoVW framework described in Section 4, and compared with the conventional methods.
Figure 8 (a) shows a comparison of scoring methods in the approximate k-NN voting framework. These methods diﬀer only

159

IPSJ Transactions on Computer Vision and Applications Vol.5 153–162 (Aug. 2013)(a) Accuracy as a function of λ.

(b) Accuracy as a function of k.

(c) Accuracy as a function of p.

Fig. 8 Comparison of scoring methods in the approximate k-NN voting framework.

Table 3Comparisons with state-of-the-art methods.

(a) MAP and KS of the proposed method.
MAP
KS

Prop

Prop+MA3

Prop+MA5

Prop+MA5+RS

0.884
3.43

0.896
3.48

0.899
3.49

0.912
3.55

(b) KS of state-of-the-art methods.
Ref. [13] Ref. [13]+ Ref. [12] Ref. [11] Ref. [6] Ref. [17] Ref. [23]KS 3.52
3.56
3.26
3.29
3.45
3.67
3.64

Fig. 9 The distributions of the proposed scores.

in terms of scoring; in other respects, they are the same as the
proposed system described in Sections 4.1–4.3. First, the following four methods are considered: (1) IDF [18] votes the IDF
scores to the top-k reference images (k = 6), (2) IDF [7] votes
the IDF scores to the top-p percent reference images instead of
the top-k (p = 0.03), (3) IDF+weight [7] votes the scores of
idf 2 · exp(−p2 /σ2 ) to the top-p percent reference images (p =0.05, σ = 0.05), and (4) Prop votes the proposed scores describedin Algorithm 1 to the top-k reference images (k = 24). Parameters
used in these methods are optimized with a grid search in parameter space. It is shown that the accuracy is significantly improvedby using the proposed scoring method instead of IDF scoring,even if the IDF score is corrected with ratio information [7]. The
proposed scoring method achieves the best MAP score of 0.884
with λ = 0.002. Figure 8 (b) shows the accuracy of Prop with
λ = 0.002 and IDF [18] as a function of k, and Fig. 8 (c) shows
the accuracy of IDF [7] and IDF+weight [7] as a function of p. We
can see that the accuracy of the scoring methods without weighting (IDF [18] and IDF [7]) decreases if k or p is set to a large
value, while the accuracy of the scoring methods with weighting (Prop and IDF+weight [7]) monotonically increases as k or p
increases. Although optimal λ in Fig. 8 (a) is diﬀerent from thatin Fig. 5 and in Fig. 7, we found that resulting scores are similar.
Figure 9 shows the distributions of the proposed score with the
BoVW framework (λ = 0.1) and that with the improved BoVW
framework (λ = 0.002). Average scores are about 1.0 (0.744 in
the BoVW framework and 1.112 in the improved BoVW framework). When λ is small (e.g., λ = 0.002), it may seem that Eq. (3)reduces to p(qi |R j ) = p(qi |B). However, the first term λp(qi |O j )in Eq. (3) is not negligible because p(qi |O j ) is relatively larger

c 2013 Information Processing Society of Japanthan p(qi |B); assuming |Nt (qi )| j = 1, |Nt (qi )|all = k = 20, and|Rall |/|R j | = 10,000 in Eq. (7), then p(qi |O j )/p(qi |B) = 500. Notethat |Rall |/|R j | is approximately equal to the number of reference
images.
In Fig. 8, the proposed scoring method is also evaluated in conjunction with a fixed number of multiple assignments [8] with
the number of assignments being either 3 (Prop+MA3) or 5
(Prop+MA5), where several number of lists corresponding to thenearest VWs of qi in the inverted index are searched. In this case,multiple assignment simply improves the accuracy (recall) of the
k-nearest neighbor search results in product quantization-basednearest neighbor search. The best MAP score of the proposedscoring method is improved from 0.884 to 0.896 (Prop+MA3)
and 0.899 (Prop+MA5).
In order to compare the proposed method with state-of-theart methods, the proposed method is evaluated in terms of Kentucky score (KS), which is the average number of relevant images in the query’s top 4 retrieved images as in Ref. [26]. We
also evaluate the proposed method with RootSIFT (RS) descriptor [16] as Prop+MA5+RS, where each SIFT descriptor is simply 1 -normalized and each element is square rooted. Table 3
shows the comparisons of the proposed method with state-ofthe-art methods. Although the proposed method does not utilize
any geometric information nor depend on re-ranking approach, itachieves comparable or even better results than the state-of-theart methods. We also evaluated the original naive-bayes nearestneighbor (NBNN) method [25]. The NBNN method achieved a
MAP score of 0.800 even if exact nearest neighbor distances areused. This result comes from the fact that only a single training image is available for each class in image retrieval problems,
where the NBNN classifier reduces to a nearest-neighbor-image(NN-image) classifier [25]. In terms of eﬃciency, the NBNN
method with approximate nearest neighbor search [27] requires
0.035 seconds to calculate a distance between a query image and areference image; the NBNN method takes 357 seconds per query
against the Kentucky dataset which consists of 10,200 images,

160

IPSJ Transactions on Computer Vision and Applications Vol.5 153–162 (Aug. 2013)

Fig. 10 Comparison of the proposed scoring method using diﬀerent sizes ofthe dataset.

while the proposed method takes 0.66 seconds per query. Processing times were measured using a program with a single thread
on a machine with a Core i7 970 CPU.
Finally, we confirm the scalability of the proposed scoring
method by adding the MIRFLICKR-1M dataset as a distractor.
Figure 10 shows the MAP scores obtained by the proposed scoring method with λ = 0.002 as a function of the number k of nearest neighbors. The following four sizes of the dataset are evaluated; Kentucky corresponds to Prop in Fig. 8 (b), where only
the Kentucky dataset is used in the evaluation. Kentucky+10K,
Kentucky+100K, and Kentucky+1M represents the results of the
proposed method, where 10 K, 100 K, and 1 M images out of the
MIRFLICKR-1M dataset are added to the Kentucky dataset as
a distractor. We can see that the proposed scoring method requires relatively large k to obtain adequate results when the sizeof the dataset is increased. This is because the error caused by
the approximation introduced in Section 3.2 is increased as thesize of the dataset is increased. However, the degradation of theaccuracy caused by the increase of dataset is relatively small compared with conventional methods. In the case of the conventional
method [7], if the 1 M distractor images are added, the MAP scoredeclines from 0.845 to 0.757 [7], which corresponds to 10.4%
degradation. Meanwhile, in the case of the proposed method,
the MAP score declines from 0.885 to 0.852 (k = 200), whichcorresponds to only 3.7% degradation. It can be said that theeﬀectiveness of the proposed scoring method becomes more significant when the database size is increased. This is because thebackground model p(qi |B) is taken into account in the proposedscoring method, where the accuracy of k-nearest neighbor density
estimation is improved as the number of samples is increased.
5.4 Application to a Diﬀerent Framework
In this section, the proposed scoring method is evaluated underquite diﬀerent settings from those in Sections 5.2 and 5.3: a different feature extraction method, approximate nearest neighborsearch method, and dataset are used. Considering image recognition applications on mobile devices, the following settings areused.
For feature extraction, we adopt ORB [34], which utilizes
multi-scale FAST detector [35] and oriented BREIF descriptor [36]. Because ORB realizes very fast detection and descrip-

c 2013 Information Processing Society of Japan

Fig. 11 MAP as a function of the number k of nearest neighbors used invoting.

tion, it even works on mobile phones. The implementation of the
OpenCV library *7 is used in the experiment. Up to 500 ORB
features are extracted from three scales. For approximate nearest
neighbor search to get top-k descriptors, locality sensitive hashing [31] is used, where the number of hash tables and the size ofthe hash key is set to 20 and 210 , respectively. For the dataset,
we use the CD class images from the Stanford MVS dataset. The
Stanford MVS dataset is designed to be used for the evaluation ofvisual recognition systems on mobile devices.
Figure 11 compares the proposed scoring method in Algorithm 1 with the baseline method, which votes a score of 1.0 toreference images corresponding to the top-k nearest neighbor descriptors of qi . In the figure, the proposed method achieves better
accuracy than the baseline method for all k. The two methods
are also evaluated using a larger dataset, which consists of the
CD class images and 1,000 images from the MIRFLICKR-1M
dataset. If the 1 K images are added as a distractor, the best MAP
score of Baseline declines from 0.750 to 0.635 (15.3% degradation), while the best MAP score of Prop declines from 0.793
to 0.755 (4.8% degradation *8 ). The proposed scoring method ismore eﬀective in the larger dataset, which is consistent with theresults in Section 5.3.

6. Conclusion
In this paper, we have proposed a new, eﬀective, and unified
scoring method for local feature-based image retrieval. The proposed scoring method has been derived by solving the large-scale
image retrieval problem as a classification problem with a large
number of classes. The resulting proposed score is based on theratio of the probability density function of an object model to thatof a background model, which is eﬃciently calculated via nearest
neighbor density estimation. The eﬀectiveness of the proposed
method was confirmed by applying it to a standard and improved
bag-of-visual words-based framework and a k-nearest neighborvoting framework. The proposed method can also be used inconjunction with many other methods such as hierarchical vocabulary [26] or learned vocabulary [37], where the matched descriptors can be ordered. As a future research topic, we are interested*7*8

http://opencv.org/
This degradation is relatively larger than that in Fig. 10. It is probably
due to the diﬀerence in the discriminative power of the SIFT and ORB
descriptors.

161

IPSJ Transactions on Computer Vision and Applications Vol.5 153–162 (Aug. 2013)

in the application of the proposed method to other modalities suchaudio and structured data.
References
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]

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).
Mikolajczyk, K. and Schmid, C.: A Performance Evaluation of Local
Descriptors, IEEE Trans. PAMI, Vol.27, No.10, pp.1615–1630 (2005).
Sivic, J. and Zisserman, A.: Video google: A text retrieval approachto object matching in videos, Proc. ICCV, pp.1470–1477 (2003).
Jégou, H., Douze, M. and Schmid, C.: Improving bag-of-features forlarge scale image search, IJCV, Vol.87, No.3, pp.316–336 (2010).
Roelleke, T. and Wang, J.: TF-IDF Uncovered: A Study of Theories
and Probabilities, Proc. SIGIR, pp.435–442 (2008).
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).
Uchida, Y., Takagi, K. and Sakazawa, S.: Ratio Voting: A New Voting
Strategy for Large-Scale Image Retrieval, Proc. ICME, pp.759–764(2012).
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).
Uchida, Y., Takagi, K. and Sakazawa, S.: An Alternative to IDF:
Eﬀective Scoring for Accurate Image Retrieval with Non-ParametricDensity Ratio Estimation, Proc. ICPR, pp.1285–1288 (2012).
Zhao, W.L. and Ngo, C.W.: Scale-Rotation Invariant Pattern Entropy for Keypoint-based Near-Duplicate Detection, IEEE Trans. Image Processing, Vol.18, No.2, pp.412–423 (2009).
Lin, Z. and Brandt, J.: A Local Bag-of-Features Model for LargeScale Object Retrieval, Proc. ECCV, pp.294–308 (2010).
Zhang, Y., Jia, Z. and Chen, T.: Image Retrieval with GeometryPreserving Visual Phrases, Proc. CVPR, pp.809–816 (2011).
Shen, X., Lin, Z., Brandt, J., Avidan, S. and Wu, Y.: Object retrieval
and localization with spatially-constrained similarity measure and kNN re-ranking, Proc. CVPR, pp.3013–3020 (2012).
Chum, O., Philbin, J., Sivic, J., Isard, M. and Zisserman, A.: Total
Recall: Automatic Query Expansion with a Generative Feature Modelfor Object Retrieval, Proc. ICCV, pp.1–8 (2007).
Chum, O., Mikulı́k, A., Perdoch, M. and Matas, J.: Total Recall II:
Query Expansion Revisited, Proc. CVPR, pp.889–896 (2011).
Arandjelović, R. and Zisserman, A.: Three things everyone should
know to improve object retrieval, Proc. CVPR, pp.2911–2918 (2012).
Qin, D., Grammeter, S., Bossard, L., Quack, T. and Gool, L.V.: Helloneighbor: Accurate object retrieval with k-reciprocal nearest neighbors, Proc. CVPR, pp.777–784 (2011).
Jégou, H., Douze, M. and Schmid, C.: Product Quantization for Nearest Neighbor Search, IEEE Trans. PAMI, Vol.33, No.1, pp.117–128(2011).
Jégou, H., Douze, M. and Schmid, C.: Hamming Embedding andWeak Geometric Consistency for Large Scale Image Search, Proc.
ECCV, pp.304–317 (2008).
Weiss, Y., Torralba, A. and Fergus, R.: Spectral Hashing, Proc. NIPS,
pp.1753–1760 (2008).
Brandt, J.: Transform Coding for Fast Approximate Nearest Neighbor
Search in High Dimensions, Proc. CVPR, pp.1815–1822 (2010).
Uchida, Y., Agrawal, M. and Sakazawa, S.: Accurate Content-Based
Video Copy Detection with Eﬃcient Feature Indexing, Proc. ICMR(2011).
Jégou, H., Douze, M. and Schmid, C.: On the burstiness of visualelements, Proc. CVPR, pp.1169–1176 (2009).
Jain, M., Benmokhtar, R., Grosand, P. and Jégou, H.: Hamming Embedding Similarity-based Image Classification, Proc. ICMR (2012).
Boiman, O., Shechtman, E. and Irani, M.: In Defense of NearestNeighbor Based Image Classification, Proc. CVPR, pp.1–8 (2008).
Nistér, D. and Stewénius, H.: Scalable Recognition with a Vocabulary
Tree, Proc. CVPR, pp.2161–2168 (2006).
Muja, M. and Lowe, D.G.: Fast Approximate Nearest Neighborswith Automatic Algorithm Configuration, Proc. VISAPP, pp.331–340(2009).
Andoni, A.: Near-Optimal Hashing Algorithms for Approximate
Nearest Neighbor in High Dimensions, Proc. FOCS, pp.459–468(2006).
Mikolajczyk, K. and Schmid, C.: Scale & Aﬃne Invariant Interest
Point Detectors, IJCV, Vol.60, No.1, pp.63–86 (2004).
Lowe, D.G.: Distinctive Image Features from Scale-Invariant Keypoints, IJCV, Vol.60, No.2, pp.91–110 (2004).

c 2013 Information Processing Society of Japan


[31]
[32]
[33]
[34]
[35]
[36]
[37]

Gionis, A., Indyk, P. and Motwani, R.: Similarity Search in High Dimensions via Hashing, Proc. VLDB, pp.518–529 (1999).
Huiskes, M.J., Thomee, B. and Lew, M.S.: New trends and ideas invisual concept detection: The MIR flickr retrieval evaluation initiative,
Proc. MIR, pp.527–536 (2010).
Turcot, P. and Lowe, D.G.: Better Matching with Fewer Features: The
Selection of Useful Features, Proc. WS-LAVD, pp.2109–2116 (2009).
Rublee, E., Rabaud, V., Konolige, K. and Bradski, G.: ORB: An eﬃcient alternative to SIFT or SURF, Proc. ICCV, pp.2564–2571 (2011).
Rosten, E. and Drummond, T.: Machine learning for high-speed corner detection, Proc. ECCV, pp.430–443 (2006).
Calonder, M., Lepetit, V., Strecha, C. and Fua, P.: BRIEF: Binary
Robust Independent Elementary Features, Proc. ECCV, pp.778–792(2010).
Mikulı́k, A., Perdoch, M., Chum, O. and Matas, J.: Learning a Fine
Vocabulary, Proc. ECCV, pp.1–14 (2010).

Yusuke Uchida received his Bachelor
Degree of Integrated Human Studies from
Kyoto University, Kyoto, Japan, in 2005.
He received a degree of Master of Informatics from Graduate School of Informatics, 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.

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 then hehas been with its R&D Division, and now
he is a senior manager of the 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 Takayoshi Yamashita)162