An Alternative to IDF: Effective Scoring for Accurate Image Retrieval
with Non-Parametric Density Ratio Estimation
Yusuke Uchida, Koichi Takagi, Shigeyuki Sakazawa
KDDI R&D Laboratories, Inc.
{ys-uchida, ko-takagi, sakazawa}@kddilabs.jp
Abstract
In this paper, we propose a new scoring method for
local feature-based image retrieval. The proposed scoreis based on the ratio of the probability density functionof an object model to that of background model, whichis efficiently calculated via nearest neighbor density estimation. The proposed method has the following desirable properties: (1) a sound theoretical basis, (2) effectiveness than IDF scoring, (3) applicability not only
to quantized descriptors but also to raw descriptors,and (4) ease and efficiency of calculation and updating.
We show the effectiveness of the proposed method empirically by applying it to a bag-of-visual words-based
framework and a k-nearest neighbor voting framework.

1. Introduction
With the advances in both stable interest region detectors [6] and robust and distinctive descriptors [5], local feature-based image or object retrieval has attracted
significant attention. It has also become applicable tolarge-scale databases owing to the bag-of-visual words(BoVW) framework [12]. In the BoVW framework, local feature points or regions are first detected in an image, then feature descriptors are extracted from them.
These feature vectors are quantized into visual words(VWs) using a visual codebook, resulting in a histogram
representation of VWs. In many cases, image similarity
is measured by the L2 distance between the normalized
histograms. As the histograms are generally sparse, aninverted index data structure and a voting function enables an efficient similarity search. The equivalency between L2 distances and scores obtained with the voting
function is described in [3] in detail. In order to emphasize distinctive VWs, the inverse document frequency(IDF) scoring [12] has been widely used, and shown tobe effective.

Though the BoVW framework realizes efficient retrieval, some degradation of accuracy is caused byquantization [2]. Two major approaches are proposed to alleviate quantization error: post-filtering
approaches [3, 4, 14] and multiple assignment approaches [10, 3, 7]. In the post-filtering approaches, after the VW-based matching, unreliable matches are filtered out according to the estimated distances between
query and reference descriptors. In the multiple assignment approaches, a query descriptor can be matched
not only with reference descriptors in the nearest VW,
but also with reference descriptors in the several nearestVWs. Although quantization error is alleviated, all theabove methods still depend on IDF scoring in voting,which is designed for words or quantized descriptors.
In other words, the score is still quantized.
In this paper, we propose a new scoring method applicable to both quantized and unquantized descriptors.
The proposed score is based on the ratio of the probability density function of an object model to a backgroundmodel, which is efficiently calculated in an on-the-flymanner via nearest neighbor density estimation. In experiments, we show the effectiveness of the proposedscoring method by applying it to a BoVW framework
and a k-nearest neighbor voting framework.

2. Proposed Approach
In this section, we first present the formulation of the
proposed scoring method, starting with a classification
problem. Then, in order to make it applicable to largescale image retrieval, an approximation is introduced.
Finally, the score is calculated via non-parametric density ratio estimation.

2.1. Probabilistic formulation
Given a query image Q, the objective is to find asimilar image Rĵ from a large number of reference images R1 , · · · , RnC . Considering it as a classification

problem, we start with maximum-a-posteriori estimation: ĵ = arg maxj p(Rj |Q). Assuming p(Rj ) is uniform, the maximum-a-posteriori estimation reduces toa maximum likelihood estimation:ĵ = arg max p(Rj |Q) = arg max p(Q|Rj ).
(1)
jj

Letting Q = {q1 , · · · , qn } denote the descriptors of thequery image Q, with the naive Bayes assumption, weget:n∏p(Q|Rj ) = p(q1 , · · · , qn |Rj ) =p(qi |Rj ). (2)i=1As pointed out in [2], if we assume all query descriptors
are derived from only the object model of Rj , p(Q|Rj )tends to be too small even if Q and Rj share the sameobject. In [2], the problem is alleviated by estimating p(qi |Rj ) using a few dozen images representing thesame class. As this is not practical for large-scale image
or object retrieval, we model p(qi |Rj ) by a mixture of
the object model of Rj and a background model distinct
from Rj :p(qi |Rj ) = λp(qi |Rj ) + (1 − λ)p(qi ),(3)where Ri denotes a set of descriptors in the reference
image Rj . If we consider the descriptors Q and Rj
as words, this is identical to LM (language modeling)RSV [11] in the area of information retrieval (IR). Combining Eqs. (1)–(3), we obtain:nn∑∏p(qi |Rj ) = arg max
log p(qi |Rj )ĵ = arg max
j= arg max
j= arg max
j

i=1n
∑
i=1n
∑
i=1

j

i=1log(λp(qi |Rj ) + (1 − λ)p(qi ))log(λ p(qi |Rj )+ 1).
1 − λ p(qi )(4)Finally, we get the voting score sij :λ p(qi |Rj )sij = log(+ 1).
(5)
1 − λ p(qi )For each qi , the∑voting score sij is assigned to each Rj .
The resulting i sij corresponds to the similarity measure between Q and Rj .

2.2. Approximation with nearest neighbors
In the above formulation, it is required to calculate
sij for all Rj . Similarly, minr∈Rj ||qi − r||2 should be
calculated for all Rj in [2]. Letting nC denote the number of classes and nD denote the average number of descriptors in an image, the the calculation of sij for all
Rj has a time cost of O(nC ·log(nD )) with efficient (approximate) nearest neighbor search algorithms [8, 1, 4].
This does not become a fatal flaw in classification prob-lems where nD ≫ nC . However, it is intractable inlarge-scale 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 nearest neighbor descriptors D(qi ) of qi (e.g., knearest neighbors of qi ) were obtained against all reference descriptors. Then, p(qi |Rj ) is calculated only for
Rj at least one of whose descriptors appears in D(qi ),and otherwise we assume p(qi |Rj ) = 0. Because thevoting score sij becomes 0 if p(qi |Rj ) = 0, the voting
is performed efficiently. With this approximation, thecomputational cost is reduced from O(nC · log(nD )) toO(log(nC · nD )).

2.3. Non-parametric density ratio estimation
Finally, the voting score sij is calculated using
D(qi ). We assume D(qi ) can be decomposed into mdisjoint sets D1 (qi ), · · · , Dm (qi ):m∪∩D(qi ) =Dt (qi ), Dt (qi ) Ds̸=t (qi ) = ∅. (6)t=1

We also assume that these disjoint sets are ordered:D1 (qi ) > D2 (qi ) > · · · > Dm (qi ),(7)so that they satisfy
t < s ⇔ p(qi |r ∈ Dt (qi )) > p(qi |r ∈ Ds (qi )). (8)For each Dt (qi ) (1 ≤ t ≤ m), and for each Rj oneof whose descriptors appears in Dt (qi ), the densitiesp(qi |Rj ) and p(qi ) in Eq. (5) are estimated via k-nearestneighbor density estimation:∑t|Ds (qi )|ntj, p(qi ) = s=1, (9)p(qi |Rj ) =|Rj | · Vt|Rall | · Vt
where ntj is the number of descriptors of R∪
j that appear
in Dt (qi ), Rall is all reference descriptors j Rj , Vt is√the volume of a hypersphere with radius ||qi − r̂t ||2 ,and r̂t ∈ Dt (qi ) is the farthest descriptor from qi . Combining Eqs. (5) and (9), we obtain:
λntj · |Rall |sij = log(+ 1). (10)∑1 − λ ts=1 |Ds (qi )| · |Rj |More concrete examples of the formulation are shownin the following section. One advantage of this scoring
method is that the up-to-date score is efficiently calculated in an on-the-fly manner using D(qi ), even if thedatabase is modified. The only requirement is to store
the number of descriptors |Rj | in each reference image.

3. Experimental evaluation
In this section, we show the effectiveness of the proposed scoring method by applying it to the BoVW andk-nearest neighbor (k-NN) voting frameworks.

0.9

Experiments were performed on the University ofKentucky recognition benchmark dataset1 provided by
the authors of [9]. It includes 2,550 different objects
or scenes. Each of these objects is represented byfour images taken from four different angles, making
10,200 images in all. These images are used as bothreference and query images. Mean average precision(MAP) [9, 3] is used as an indicator of retrieval performance. A visual codebook with size 20,000 is created using a dataset distinct from the images introduced
above.

Mean average precision

3.1 Experimental setup0.80.70.6DREIDF
Baseline
0.500.2

0.4

0.6

0.8

1λFigure 1: Comparison of scoring methods in the BoVWframework.
0.95

The proposed scoring method will now be applied tothe BoVW framework. In this case, D(qi ) is defined asa set of reference descriptors that are quantized into thesame VW as qi . This consists of only a single disjoint
set (m = 1):
D(qi ) = D1 (qi ) = {r ∈ Rall | q(r) = q(qi )}, (11)where q(r) and q(qi ) denote the identifiers of the corresponding VWs of r and qi after quantization. Then, sij
is calculated using frequencies of VWs:q(q )sij = log(i· |Rall |λ tf j+ 1),q(q)1 − λ tf i · |Rj |

(12)

all

where tf w
j represents the frequency of the w-th VW in
Rj , and tf w
all the frequency of the w-th VW in all reference images.
Figure 1 shows the MAP scores obtained with different scoring methods as a function of λ. The voting
score used for each method is as follows: tf for Baseline, tf · idf for IDF, and sij for density ratio estimation(DRE), respectively. It is clear that DRE achieves better
performance than Baseline and IDF, and the accuracy is
not so sensitive to the choice of λ. It can be said that theDRE scoring method is effective even if applied to thepure BoVW framework. The best MAP score of 0.811
is achieved with relatively low λ (λ = 0.06), which implies that there are a small number of features useful for
object recognition [13].

3.3. Exact k -NN voting framework
The proposed scoring method is applied to the kNN voting framework, where (approximate) k-nearest
1 http://www.vis.uky.edu/

˜stewe/ukbench/

Mean average precision

3.2. BoVW framework
0.90.85

DRE
Baseline
0.8048121620

kFigure 2: Comparison of scoring methods in the exact k-NN
voting framework.

neighbor descriptors of qi are extracted from all reference descriptors, and the corresponding reference images obtain the corresponding scores [4]. In this case,D(qi ) is defined as a set of the k-nearest neighbors ofqi , and Dt (qi ) contains∑only the t-th nearest neighbor:tm = k, ntj = 1, and s=1 |Ds (qi )| = t. Finally, sij
becomes very simple:
λ |Rall |sij = log(+ 1).
(13)
1 − λ t · |Rj |Although exact k-NN search requires impractical retrieval time, it gives us the upper bound performance ofthe proposed method, which is useful in the evaluationof the approximate k-NN-based system. Therefore, wefirst evaluate the exact k-NN version. Figure 2 shows
the comparison of scoring methods in the exact k-NN
voting framework. The fixed voting score 1.0 is usedfor Baseline because the IDF scoring is not applicable,
and sij with λ = 0.1 is used for DRE. The best MAP
scores of 0.912 and 0.902 are achieved by DRE withk = 20 and by Baseline with k = 10.

is based on the ratio of the probability density functionof an object model to that of a background model. The
effectiveness of the proposed method was confirmed byapplying it to the bag-of-visual words-based frameworkand the k-NN voting framework. The proposed method
can also be applicable to hierarchical vocabulary [9] orlearned vocabulary [7], where the matched descriptors
can be ordered. In the future, kernel density estimation
can be used for more accurate density estimation.

0.9

Mean average precision

0.88

0.86

0.84

DRE+[4]+MA5
DRE+[4]+MA3
DRE+[4]
IDF+[4]

0.82

0.8

0

0.02

0.04

0.06

0.08

0.1

References

λFigure 3: Comparison of scoring methods in the approximate
k-NN voting framework.

3.4. Approximate k -NN voting framework
Finally, we evaluate the proposed scoring methodin combination with the state-of-the-art productquantization-based
approximate
k-NNsearchmethod [4]. The parameters recommended in [4]are used2 . The voting score of the proposed method
is calculated by Eq. (13). The IDF scoring is also
applicable because qi is quantized in the process of
the approximate k-NN search3 . Figure 3 shows thecomparison of scoring methods in the approximate
k-NN voting framework. It is shown that the accuracy
is significantly improved by using the proposed scoring
method instead of the IDF scoring. In the experiment,
we chose the best k (k = 6) for the IDF scoring. For
the proposed scoring, we used an adaptive k depending
q(qi )
on the√frequency tf all of the assigned VW q(qi ) asq(q )k = tf all i . This choice was inspired by the rule of√thumb in k-NN density estimation: use the n nearest
samples out of n samples in estimation. This slightly
improved the best accuracy of DRE+[4] from 0.866(k = 14) to 0.869, and even better, it frees us from adifficulty in choosing k.
The DRE method is also evaluated in combination
with multiple assignment (MA) [10] for different numbers of assignments (3 and 5). It is shown that DRE with
5 MA achieves a MAP score of 0.898 with λ = 0.006,
which is a satisfactory result compared with the MAP
score of 0.912 obtained by the exact k-NN search.

4. Conclusion
In this paper, we have proposed a new scoring
method for local feature-based image retrieval, which
2 We set the size of the codebooks for product quantization k ∗ =256 and the number of vector decomposition m = 8.
3 We adopted the non-exhaustive version of [4] called IVFADC.

[1] A. Andoni. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In Proc.
of FOCS, pages 459–468, 2006.
[2] O. Boiman, E. Shechtman, and M. Irani. In defense ofnearest-neighbor based image classification. In Proc. ofCVPR, pages 1–8, 2008.
[3] H. Jégou, M. Douze, and C. Schmid. Improving bag-offeatures for large scale image search. IJCV, 87(3):316–336, 2010.
[4] H. Jégou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE Trans. on PAMI,33(1):117–128, 2011.
[5] K. Mikolajczyk and C. Schmid. A performance evaluation of local descriptors. IEEE Trans. on PAMI,27(10):1615–1630, Oct. 2005.
[6] K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, J. Matas, F. Schaffalitzky, T. Kadir, and L. V. Gool.
A comparison of affine region detectors. IJCV, 60(12):43–72, Nov. 2005.
[7] A. Mikulı́k, M. Perdoch, O. Chum, and J. Matas. Learning a fine vocabulary. In Proc. of ECCV, pages 1–14,2010.
[8] M. Muja and D. G. Lowe. Fast approximate nearest
neighbors with automatic algorithm configuration. InProc. of VISAPP, pages 331–340, 2009.
[9] D. Nistér and H. Stewénius. Scalable recognition witha vocabulary tree. In Proc. of CVPR, pages 2161–2168,2006.
[10] J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman. Lost in quantization: Improving particular object retrieval in large scale image databases. In Proc.
of CVPR, pages 1–8, 2008.
[11] T. Roelleke and J. Wang. Tf-idf uncovered: A studyof theories and probabilities. In Proc. of SIGIR, pages
435–442, 2008.
[12] J. Sivic and A. Zissermane. Video google: A text retrieval approach to object matching in videos. In Proc.
of ICCV, pages 1470–1477, 2003.
[13] P. Turcot and D. G. Lowe. Better matching with fewerfeatures: The selection of useful features. In Proc. ofWS-LAVD, 2009.
[14] Y. Uchida, M. Agrawal, and S. Sakazawa. Accuratecontent-based video copy detection with efficient feature indexing. In Proc. of ICMR, 2011.