Eurographics Workshop on 3D Object Retrieval (2008), pp.

19
I. Pratikakis and T. Theoharis (Editors)

Similarity Score Fusion by Ranking Risk Minimization

for 3D Object Retrieval
Submission ID: 1005

Abstract
In this work, we introduce a score fusion scheme to improve the 3D object retrieval performance. The state of
the art in 3D object retrieval shows that no single descriptor is capable of providing fine grain discrimination required by prospective 3D search engines. The proposed fusion algorithm linearly combines similarity information
originating from multiple shape descriptors and learns their optimal combination of weights by minimizing the
empirical ranking risk criterion. The algorithm is based on the statistical ranking framework [CLV07], for which
consistency and fast rate of convergence of empirical ranking risk minimizers have been established. We report the
results of ontology-driven and relevance feedback searches on a large 3D object database, the Princeton Shape
Benchmark. Experiments show that, under query formulations with user intervention, the proposed score fusion
scheme boosts the performance of the 3D retrieval machine significantly.
Categories and Subject Descriptors (according to ACM CCS): H.3.3 [Information Search and Retrieval]: Retrieval
Models I.5.1 [Models]: Statistical

1. Introduction
Next generation search engines will enable query formulations, other than text, relying on visual information encoded
in terms of images and shapes. The 3D search technology,
in particular, targets specialized application domains ranging from computer aided design to molecular data analysis. In this search modality, the user picks a query from a
catalogue of 3D objects and requests from the retrieval machine to return a set of "similar" database objects in decreasing relevance. 3D object retrieval hinges on shape matching,
that is, determining the extent to which two shapes resemble each other. Shape matching is commonly done by reducing the characteristics of the shapes to vectors or graph-like
data structures, called shape descriptors [BKS 05, TV04,
IJL 05], and then, by evaluating the similarity degrees between the descriptor pairs. We call the similarity degree between two descriptors as the matching score between two
shapes. In the retrieval mode, the matching scores between
a query and each of the database objects are sorted. The retrieval machine then displays database objects in descending
order of the scores. Effective retrieval means that the objects
displayed in the upper part of the list better match the query
object than the rest of the list.
Ongoing research in 3D object retrieval shows that no
submitted to Eurographics Workshop on 3D Object Retrieval (2008)

single shape descriptor is capable of providing satisfactory

retrieval performance for a broad class of shapes and independently of the associated semantics [TV04, SMKF04].
Figure 1 displays the response of two different descriptors
from the density-based framework [ASYS07a], A and B, to
two different queries from the Princeton Shape Benchmark
(PSB) [SMKF04]. The first query is a biplane model and the
second one is a chair model. In response to the biplane, descriptor A returns correctly four biplanes in the first three
and in the sixth matches, while the fourth and the fifth retrieved models are not biplanes, but still flying objects that
can be considered as relevant. Descriptor B, on the other
hand, returns models that are completely irrelevant to the
biplane query (three shelf models, two coarse human models and a microscope!). For the chair query, Descriptor B
is more successful since it has retrieved six chair models;
while descriptor A, after first three correct matches, returns
two tree models and a monument! Thus, the adequacy of
the descriptors A or B depends on the nature of the query.
Furthermore, these examples can be multiplied; for instance,
there are cases where sets of relevant matches for different
descriptors are even disjoint. Much like in the case of classifier construction, we conjecture that improved retrieval algorithms can be built by using diverse set of descriptors/scores

Submission ID: 1005 / Similarity Score Fusion for 3D Object Retrieval

imizers have been established. Third, our algorithm operates on scores, and not on descriptors themselves. This adds
greater generality and flexibility to our algorithm for a broad
spectrum of retrieval applications.

Figure 1: Response of two different descriptors A and B to

two different queries biplane and chair

provided there is a practical way to choose and/or combine

them.
While the problem of choosing and/or discovering the
best descriptor sets for the retrieval task can be addressed
in an unsupervised setting as in [SKP06], we conjecture that
supervised approaches may provide more semantic and appealing search results. The specific approach presented in
this work is a score fusion scheme that uses a certain amount
of supervision. We formulate the problem of score fusion
as follows. How can one combine a set of similarity scores
{sk } into a final scoring function = k wk sk to achieve
better retrieval result than with anyone of them? We tackle
this score fusion problem by minimizing a convex regularized version of the empirical risk associated with ranking
instances. We follow the statistical learning framework developed in [CLV07] and identify that learning a linear scoring function can be cast into a binary classification problem in the score difference domain. Given a query, the set
of weights {wk } found as the solution of the binary classification problem can be considered as optimal also with respect to the empirical risk associated with ranking instances.
Our score fusion approach can be employed with different
types of supervisory information provided by the user, as in
ontology-driven search and relevance feedback.
The contribution of the present work is three-fold. First,
to the best of our knowledge, there is no prior work in the
3D domain using statistical ranking techniques to combine
shape similarity information coming from different descriptors. The ranking approach differs from more classical relevance feedback schemes (for an application in 3D shape
retrieval, see [LMT05] and references therein). In retrieval,
the goal is not only to classify objects but also to learn a
scoring function so that one can order them as a function of
their relevance with respect to a given query. In this sense,
statistical ranking provides a more general means of learning inter-object similarities than classification. Second, the
present work is a direct application of a recently introduced
rigorous statistical framework [CLV07], where consistency
and fast rate of convergence of empirical ranking risk min-

The paper is organized as follows. In Section 2, we introduce the score fusion problem and give a solution based
on support vector machines (SVM) [HTF01]. We also explain the use of our score fusion algorithm in two different
protocols, bimodal and two-round searches, which can be
viewed as particular instances of ontology-driven search and
relevance feedback respectively. In Section 3, we give an
overview of the density-based framework [ASYS07a] that
we use for shape description. In Section 4, we experiment
on PSB [SMKF04] and show the degree by which we can
boost the retrieval performance of density-based shape descriptors using the proposed score fusion algorithm. In the
final Section 5, we conclude and discuss further research directions.
2. Score Fusion by Ranking Risk Minimization
2.1. The Score Fusion Problem
Consider the problem of ranking two generic database
shapes x and x0 based on their relevance to a query shape q.
Suppose that we have access to K similarity values sk and s0k
for each of the pairs (x, q) and (x0 , q) respectively. These K
similarity measures can be obtained from different descriptor sets and/or by using different metrics operating on the
same set of descriptors. In our context, a similarity value
sk , simk (x, q) arises from a certain shape descriptor and reflects some, possibly different, geometrical and/or topological commonality between the database shape x and the query
shape q. An ideal similarity measure should score higher for
similar shape pairs as compared to less similar ones. In retrieval problems, a shape x in the database that is more similar to the query q is expected to be ranked higher than any
other intrinsically less similar shape x0 . These similarity values/scores can be written more compactly in the vector form
as s = [s1 , . . . , sK ] RK . Our objective is to build a scalarvalued final scoring function of the form (x, q) = hw, si,
where w = [w1 , . . . , wK ] RK is a vector, whose components
form the weights of the corresponding scores sk . The scoring
function should assign a higher score to the more relevant
shape, i.e., it should satisfy the following property:
(x, q) > (x0 , q)
(x, q) < (x0 , q)

if x is more relevant to q than x0 ,

otherwise,

where ties are arbitrarily broken. The relevance of the shapes

x and x0 to the query q can be encoded by indicator variables
y and y0 respectively. In this work, we assume crisp relevances y = 1 (relevant) and y = 1 (not relevant), in which
case, the above property reads as:
(x, q) > (x0 , q)
(x, q) < (x0 , q)

if y y0 > 0,
if y y0 < 0.

submitted to Eurographics Workshop on 3D Object Retrieval (2008)

Submission ID: 1005 / Similarity Score Fusion for 3D Object Retrieval

The function must subsume the similarity information

residing in the individual scores sk in order to emulate the
ideal similarity notion between shapes, hence to achieve a
better retrieval performance. Given the linear form (x, q) =
hw, si, score fusion can be formulated as the problem of finding a weight vector w, which is optimal according to some
criterion, as we explain in the following section.
2.2. Ranking Risk Minimization
The criterion of interest is the so-called empirical ranking
risk (ERR) defined as the number of misranked pair of database shapes (xm , xn ) with respect to a query q. Formally, we
can write this criterion as:
1
ERR(; q) = I {((xm , q) (xn , q)) (ym yn ) < 0} .
T m<n
(1)
where T is the number of shape pairs (xm , xn ) and I{} is
the 0-1 loss, which is one if the predicate inside the braces
is true and zero otherwise. ERR simply counts the number
of misranked shape pairs in the database with respect to the
query. Basically, if (xm , q) < (xn , q) but ym > yn , the scoring function (, q) (wrongly) assigns a higher score to xn
than to xm while xm is relevant to the query q but xn is not.
Thus the scoring function has made an error in ranking xn
and xm with respect to the query q and ERR should be incremented by one. Such misrankings are naturally undesirable
and our task is to find a scoring function (or more appropriately its parameters w) so that the number of misranked pairs
is as small as possible.
We can identify ERR as an empirical classification error. To see this, first let z , (y y0 )/2, taking values within
{1, 0, 1}. We observe then the following:

1
x should be ranked higher than x0 ,
z=
1 x should be ranked lower than x0 .
When z = 0, i.e., if shapes x and x0 are both relevant (y =
y0 = 1) or both not relevant (y = y0 = 1), we have no particular preference in ranking them with respect to each other
(we can decide arbitrarily). Corresponding to each non-zero
z, we can define a score difference vector v, which is given
simply by v , s s0 , the difference between the score vectors s and s0 of the shapes x and x0 respectively. With this
new notation and writing the scoring function explicitly in
terms of its parameters w, Eq. 1 now reads as
1
ERR(w; q) =
T

I {zm,n hw, vm,n i < 0} ,

(2)

m<n

where the index pairs (m, n) correspond to pairs of shapes

xm and xn whose respective relevance labels ym and yn are
different (zm,n is either 1 or 1). Thus, we have converted
ERR written in terms of score vectors s and relevance indicators y (Eq. 1) into an empirical classification error in terms
of score difference vectors v and rank indicators z (Eq. 2). In
both cases, the sought-after parameter vector w is the same.
submitted to Eurographics Workshop on 3D Object Retrieval (2008)

Figure 2: Bimodal protocol

As is the common practice in statistical learning [HTF01],

we replace the 0-1 loss in Eq. 2 with a convex loss function and we add a regularization term on some norm of w
to obtain a tractable convex optimization problem in w. In
particular, using the hinge loss as the convex loss and the
L2 -norm as the regularization term leads to the well-known
SVM problem, for which we can find a global solution.
In summary, the problem of finding the parameter vector
w of the linear scoring function is the same as the SVM
problem in the domain of score difference vectors. The key
point here is that the weight vector learned by SVM in the
score difference domain can directly be used to evaluate the
scoring function at the matching stage. We can now summarize the training algorithm to learn the parameter w of the
scoring function :
Given
Database shapes xn
Query q
Relevance labels yn
K different shape description schemes
(1) Calculate a score vector sn RK for each (xn , q)-pair.
(2) Identify the pairs of labels (ym , yn ) such that ym yn 6= 0.
(3) Construct the score difference vectors vm,n and their
rank indicators zm,n .
(4) Run the SVM algorithm to learn the weight vector w
RK , using the set {(vm,n , zm,n )}m<n RK {1, 1}.
2.3. Applications
In this section, we illustrate our score fusion scheme in two
different retrieval protocols: (i) bimodal search and (ii) tworound search.
2.3.1. Bimodal Protocol
In the bimodal protocol, the user provides a textual description associated with the query shape (see Figure 2). The keyword can be selected from one of the predefined shape concepts. We call this protocol as bimodal since the query is formulated in terms of two information modalities, a 3D shape

Submission ID: 1005 / Similarity Score Fusion for 3D Object Retrieval

and a concept keyword. This protocol can be viewed as

an ontology-driven search and necessitates an off-line stage
during which the weight vectors associated with each shape
concept are learned. Note that the criterion of Section 2.2
is per-query and should be extended to a per-concept risk
ERR(w, C), where C stands for the working concept. This
can be done straight-forwardly by averaging per-query risks
associated with a given concept, that is,
ERR(w; C) =

1
ERR(w; q),
|C| qC

where |C| is the number of training shapes belonging to C.

However, since the minimization should be performed in the
score difference domain, the problem turns out to be a very
large-scale one even for moderately sized classes. Given a
training database D of size |D|, the number of score difference instances per concept is |C| (|C| 1) (|D| |C|),
e.g., for |D| = 1000 and for |C| = 10, the number of training
instances becomes 90000, in which case we incur memory
problems using standard SVM packages [CL01]. To alleviate this intractability, we develop two heuristics solving |C|
separate SVM problems of smaller size:

Figure 3: Two-round protocol on-line version

C
Average per-query weight vector. The weight vector w
for a given shape concept is computed as the average
q corresponding to the
of the per-query weight vectors w
training shapes within that class, that is,
C =
w

1
w q .
|C| qC

q is obtained by the algoThe per-query weight vector w

rithm given in Section 2.2. We denote this heuristic by
AVE-W.
Per-class risk minimization using per-query support
vectors. In this second heuristic, we exploit the sparsity
of the SVM solution, which means that the per-query
weight vector found by the algorithm in Section 2.2 is
the weighted sum of usually a small number of training
score difference instances, called as support vectors (svs)
in general SVM terminology. It is a well known fact that,
for a given binary classification problem, the SVM solution remains identical when only the svs are provided
for training [HTF01]. The svs form a parsimonious surrogate for the set of training instances with exactly the same
separability properties in the original data. Accordingly,
the learning of a per-concept weight vector can be carried
out in two stages. First, we identify the svs of per-query
problems by per-query minimization. Then, we pool all
the svs corresponding to a given concept and perform the
minimization using this newly formed set to learn the perconcept weight vector. We repeat this procedure as many
times as the number of predefined shape concepts. We denote this heuristic by PCMIN-W.

Figure 4: Two-round protocol off-line version

2.3.2. Two-round Protocol

The two-round protocol is a particular form of relevance
feedback and requires user intervention during the querying process. In the first round, the retrieval machine returns
a ranked list of shapes using a simple scoring scheme, e.g.,
the sum of the available raw scores 1 = k sk . After the
first found, we can invoke the score fusion scheme in two
different ways:
On-line. The user marks M shapes among the returned
ones, as either relevant (y = 1) or non-relevant (y = 1)
with respect to his/her query (see Figure 3). In the second
round, the retrieval machine returns a refined ranked list
using the scoring function w = hw, si. The weight vector
w is learned on-line using the M marked shapes as training instances. In order not to demand too much from the
user, M should not be large and is typically limited to a
few first shapes. For example, when M = 8 and the number of positive M + and negative instances M are equal
(M + = M = 4), the total number of training score difference vectors is just 16. Consequently, on-line learning
is computationally feasible.
submitted to Eurographics Workshop on 3D Object Retrieval (2008)

Submission ID: 1005 / Similarity Score Fusion for 3D Object Retrieval

Off-line. In this variant of the two-round search, all the

shapes in the database have their individual weight vectors stored, which have already been learned off-line (see
Figure 4). The individual per-query weight vectors can be
obtained as in the bimodal protocol. At querying time, the
user is asked to mark just the first relevant item in the
displayed page of the results. The second round evaluates
the scoring function w = hw, si using the weight vector
corresponding to the marked shape. Clearly, this protocol
does not perform any on-line learning and constitutes a
less demanding option than the former in terms of user
interaction needed, as the user is asked to mark just one
item.
3. Density-Based Shape Description Framework
Although the research on 3D shape descriptors for retrieval
started just a decade ago or so, there is a considerable
amount of work reported so far. The most up-to-date and
complete reviews in this rapidly evolving field are given
in [BKS 05, TV04, IJL 05]. The score fusion algorithm described in the previous section can be used with any type
of shape descriptors. In the present work, we employ a relatively recent 3D shape description methodology, the densitybased framework (DBF) [ASYS07a]. As we expose in this
section, DBF produces a rich set of descriptors, which has a
good retrieval performance compared to other state-of-theart methods.
In DBF, a shape descriptor consists of the sampled probability density function (pdf) of a local surface feature evaluated on the surface of the 3D object. The sampling locations
of the pdf are called targets and the pdf value at each target is
estimated using kernel density estimation (KDE). The vector
of estimated feature pdf values is a density-based shape descriptor. In [ASYS07b], the discriminative power of several
multivariate surface features within DBF has been investigated on different databases. Three of these features are particularly interesting as they capture local surface information
up to second-order:
parametrizes the coor At zero-order, the R-feature (R, R)
dinates of a surface point at a distance R from the objects
center of mass. The unit direction of the ray traced from

the center of mass to the point is denoted by R.

parametrizes the tan At first-order, the T-feature (D, N)
gent plane at a surface point. Here, D stands for the absolute normal distance of the tangent plane to the center
is the unit normal at the point.
of mass and N
At second-order, the S-feature (R, A, SI) carries categorical local surface information through the shape index
SI [KvD92], which is enriched

 by the radial distance R

N
.
and the alignment A ,  R,

Using DBF, these local features are summarized into

global shape descriptors that we denote as R-, T- and Sdescriptors. A simple way to benefit from different types of
submitted to Eurographics Workshop on 3D Object Retrieval (2008)

Table 1: Retrieval Performance of State-of-the-Art Descriptors on PSB Test Set

DBI
CRSP
RTS

NN (%)
66.5
67.9
67.4

DCG (%)
66.3
66.8
65.0

shape information carried by these descriptors is to sum their

corresponding similarity values sk , that is, 1 = k sk . The
retrieval performance of this basic score fusion, denoted as
RTS, on PSB test set (907 objects in 92 classes) is shown
in the third row of Table 1 in terms of discounted cumulative
gain (DCG) and nearest neighbor (NN) measures. Note that
this fusion is unsupervised and does not involve any statistical learning.
In Table 1, we also display performance figures corresponding to two state-of-the-art descriptors: depth buffer
images (DBI) [BKS 05] and concrete radialized spherical
projection descriptor (CRSP) [PPT07]. DBI is a 2D imagebased method, which describes a shape by the low-frequency
Fourier coefficients of six depth buffer images captured
from orthogonal parallel projections. CRSP, on the other
hand, is built upon the radialized extent function descriptor [BKS 05], which describes the shape as a collection of
spherical functions giving the maximal distance from center
of mass as a function of spherical angle and radius. CRSP
provides further rotation invariance by considering the PCA
of both surface points and surface normals for pose normalization. DBI among 2D methods and CRSP among 3D
methods are the best performing descriptors on PSB test
set in their own methodological categories based on the results reported in [BKS 05] and [PPT07] respectively. From
Table 1, we see that the performance of RTS is comparable to those of both DBI and CRSP. The good performance of the RTS-descriptor can be explained by the
following facts: (i) all the available local surface information up to second order is exploited within the KDE setting
except pairwise cross-correlations between the involved features (e.g., between R and T); (ii) KDE copes with measurement uncertainties due to small pose normalization errors,
small shape variations and/or mesh degeneracies; (iii) invariance against coordinate axis mislabelings and mirror reflections is achieved by taking the maximum similarity value between two shapes over the set of coordinate axis relabelings
and mirror reflections. These aspects have been thoroughly
discussed in C. B. Akgls Ph.D. thesis [Akg07].
Learning-based fusion of two or three scores does not
have enough degrees of freedom to boost the retrieval performance significantly. We conjecture that we can reap the
benefits of statistical ranking upon employing a larger set
of descriptors produced by DBF. To prove our conjecture,
we decided to decompose the pdf of a feature into cross-

Submission ID: 1005 / Similarity Score Fusion for 3D Object Retrieval

sections. Observe first that all of the R-,T- and S- descriptors

are radialized in the sense that they capture the distribution
of some subfeature at concentric shells with radius rk (or dk
for the T-descriptor). The subfeatures are the radial direction
for the R-descriptor, the normal N
for the T-descriptor and
R
the (A, SI)-pair for the S-descriptor. We refer to these distributions as cross-sectional descriptors. For instance, let us take
the NR NR = 8 128 = 1024-target pdf of the R-feature,
where NR = 8 is the number of points sampled within the
R-domain and NR = 128 is the number of points sampled on
the unit-sphere. The 1024-point R-descriptor is then considered as NR = 8 chunks of NR = 128-point cross-sectional descriptors, each of which can be used to evaluate a similarity
score sk between two objects at a given concentric shell, say
at a distance rk from the origin. Of course, these individual
scores do not capture the shape similarity to the full extent.
However, this decoupling adds more degrees of freedom to
the subsequent score fusion stage, where we learn a distinct
weight wk for each of the individual scores sk by ranking
risk minimization. Accordingly, for each of the R-, T- and
S-descriptors, we obtain 8 per-chunk similarity scores and
work with 24 scores in total.
4. Experiments
We have tested our score fusion algorithm on a modified version of PSB. Originally, PSB training and test sets do not
share the same shape classes. Accordingly, we have merged
these two sets into a single one, consisting of 1814 models
in 161 classes. The number of classes shared by the original
training and test sets is 21, hence the merged PSB contains
90 + 92 21 = 161 classes. We have then split them into
two subsets A and B of sizes 946 and 868, drawing them
randomly from the same 161 classes. This reorganization of
the PSB database offers us an even more challenging problem since the number of classes is increased from 92 to 161.
Thus, it should be expected that the DCG value on this new
dataset with basic score fusion decreases as compared to the
value on the original PSB test set given in Table 1.
4.1. Performance in Bimodal Search
Recall that the bimodal search protocol assumes the existence of a training set categorized into a fixed set of concepts. Learning is done off-line. In the bimodal experiments,
we have considered PSB class labels as concept keywords.
We have taken the PSB Set A as the training set, which we
have used to learn per-concept weight vectors. PSB Set B has
been reserved for testing purposes. In Table 2, we provide
the results of fusing 8 R-scores, 8 T and 8 S-scores, making 24 scores in total. We also display the results of the basic
SUM rule for reference (i.e., that of RTS). Although, the
learning-based score fusion does improve the average DCG
performance significantly on the training set, it does not lead
to a significant gain in the test set (only 2% using the AVE-W
heuristic). That is, learning-based score fusion does not work

Table 2: DCG (%) Performance of Score Fusion in the Bimodal Protocol

Rule
SUM
AVE-W
PCMIN-W

PSB Set A
61.628.1
71.826.5
74.925.2

PSB Set B
60.628.1
62.628.4
62.527.7

AVE-W: Weights averaged over training queries

PCMIN-W: Weights found by per-concept minimization
See also Section 2.3.1

Table 3: DCG (%) Performance of Score Fusion in the

Bimodal Protocol when the basic SUM rule instead of
learning-based score fusion has been used for negatively affected concepts
Rule
PSB Set B # P.A. Concepts
SUM
60.628.1
AVE-W
64.024.1
106
PCMIN-W 64.423.9
100
P.A. Concepts: Positively Affected Concepts

well for certain concepts. This might be due to heuristicsbased learning of per-concept weight vectors, but, we think
that the following arguments better explain the situation:
For some concepts, the linear similarity model might not
be flexible enough to maintain good classification accuracy in the score difference domain. When instances from
queries belonging to a certain concept are pooled together,
the discrimination problem in the score difference domain
might become more complex than what can be solved using a simple linear decision boundary. However, if the linear similarity model were totally unacceptable, we would
not expect a good performance on the training set either.
In fact, in only 4 out of 161 concepts in PSB Set A, the
AVE-W fusion has worsened the performance by not more
than 2.3% DCG points with respect to the baseline SUM
rule. In PSB Set B, on the other hand, 61 concepts (again
out of 161) have suffered from an average performance
loss of 8.5% DCG points.
In Table 3, we provide the DCG scores when we use the
basic SUM rule instead of learning-based score fusion
(AVE-W or PCMIN-W) for negatively affected concepts
(i.e., those concepts for which learning-based score fusion has worsened the DCG performance). The right most
columns give the number of positively affected concepts.
We deduce that the linear similarity model is adequate for
the training set and generalizes well on the previously unseen instances of 100 concepts in the test set.
4.2. Performance in Two-round Search
In the two-round query formulation, the benefits of the proposed score fusion scheme become much more evident. To
submitted to Eurographics Workshop on 3D Object Retrieval (2008)

Submission ID: 1005 / Similarity Score Fusion for 3D Object Retrieval

evaluate the performance in this search protocol, we have reserved the PSB Set A as the database shapes and PSB Set B
as the query shapes. The first round results have been obtained by the basic SUM rule (i.e., RTS).
In Figure 5, we display the DCG performance of the online sub-protocol as a function of the number of marked
items M from 4 to 32. In this figure, the line at the bottom
stands for the DCG of the first round (i.e., the performance
of the SUM rule, DCG = 62%). The line at the top stands
for the DCG when all database models are marked as either relevant or non-relevant, serving as an empirical ideal,
i.e., the maximum achievable DCG on this data set using the
presented score fusion algorithm and the running set of description schemes (DCG = 79%). Based on these results,
we make the following comments:
As the number of marked items M increases, we observe a
steep increase in the DCG performance, compatible with
theoretical fast rates of convergence proven in [CLV07].
The DCG profile converges smoothly to the empirical
ideal as the user marks more and more items in the first
round.
To give certain performance figures, for M = 8, DCG obtained after fusing the scores becomes 68%, giving a 6%
improvement compared to the baseline. The 70% DCG
barrier is reached after M = 12 marked items.
In Figure 6, we display the DCG performance of the offline sub-protocol as a function of the number of displayed
items M again 4 to 32. We emphasize that, in this mode,
M refers to the number of displayed items and the user interaction needed is limited to mark just one shape, the first
relevant one after the first round. Accordingly, here, M is not
related to the convergence of the algorithm. Increasing M
does not cost anything in terms of user interaction. After this
clarification, we have the following comments:
At M = 4, score fusion boosts the retrieval performance
by 4% and the DCG profile keeps a slow but constant
increase as the number of displayed items M in the first
round is increased.
In a typical retrieval scenario, displaying M = 32 items
has no cost. These results tell us that we can obtain DCG
improvements by 5% with respect to the baseline. Noting that the performances of top 3D shape descriptors differ only by a couple of percentage points, this 5% gain can
be considered as significant and comes virtually at no cost
at the querying process. The only bottleneck is the off-line
processing of the database shapes to learn the weight vectors, which may eventually be used in the second round.
With on-line score fusion, we can obtain significant improvements as the user is asked to mark more and more
items. In special applications where the user voluntarily
marks the demanded number of items, the on-line scheme
is preferable. The off-line scheme, on the other hand, comes
at no cost at query time and still yields satisfactory improvesubmitted to Eurographics Workshop on 3D Object Retrieval (2008)

Figure 5: DCG performance of the two-round search with

on-line learning as a function of the number of marked items
M in the first round

Figure 6: DCG performance of the two-round search with

off-line learning as a function of the number of displayed
items M in the first round

ments. Sample two-round searches using these two variants

are shown in Figures 7 and 8.
5. Conclusion
Several studies in the 3D domain pointed out the nonexistence of a single "miracle" 3D shape descriptor to provide adequate discrimination for retrieval [TV04, SMKF04].
In this work, motivated by the fact that different descriptors may work well on different sets of shape classes, we
have addressed a relatively less studied problem in 3D object retrieval: combining multiple shape similarities to boost
the retrieval performance. Our linear score fusion algorithm
based on ranking risk minimization proved to be effective on
ontology-driven bimodal query formulations and much more
on the two-round protocol, which is a particular instance of
relevance feedback. In the future, we plan to compare this

Submission ID: 1005 / Similarity Score Fusion for 3D Object Retrieval

kernel methods [HTF01] to learn a non-linear scoring function. Direct minimization of per-concept risks, optimization
of DCG-based criteria and kernelization of the score fusion
algorithm will constitute our future research directions in
this field.
References
[Akg07] A KGL C. B.: Density-based Shape Descriptors
and Similarity Learning for 3D Object Retrieval. PhD
thesis, Tlcom ParisTech and Bogazii University, 2007.
http://www.tsi.enst.fr/akgul/pdfs/thesis-cba-web.pdf.
[ASYS07a] A KGL C. B., S ANKUR B., Y EMEZ Y.,
S CHMITT F.:
Density-based 3D shape descriptors.
EURASIP Journal on Advances in Signal
Processing 2007 (2007), Article ID 32503, 16 pages.
doi:10.1155/2007/32503.

Figure 7: Two-round search with on-line learning on a human query

[ASYS07b] A KGL C. B., S ANKUR B., Y EMEZ Y.,

S CHMITT F.: Multivariate density-based 3D shape descriptors. In Proc. of the Shape Modeling International
(SMI07) (Lyon, France, June 2007).
[BKS 05] B USTOS B., K EIM D. A., S AUPE D.,
S CHRECK T., V RANIC D. V.: Feature-based similarity
search in 3D object databases. ACM Comput. Surv. 37, 4
(2005), 345387.
[CL01] C HANG C.-C., L IN C.-J.: LIBSVM: a library
for support vector machines, 2001. Software available at
http://www.csie.ntu.edu.tw/ cjlin/libsvm.
[CLV07] C LMENON S., L UGOSI G., VAYATIS N.:
Ranking and empirical risk minimization of U-statistics.
The Annals of Statistics to appear (2007).
[HTF01] H ASTIE T., T IBSHIRANI R., F RIEDMAN J.: The
Elements of Statistical Learning: Data Mining, Inference,
and Prediction. Springer-Verlag, New York, NY, 2001.
[IJL 05] I YER N., JAYANTI S., L OU K., K ALYANARA MAN Y., R AMANI K.: Three-dimensional shape searching: state-of-the-art review and future trends. ComputerAided Design 37, 5 (April 2005), 509530.
[KvD92] KOENDERINK J. J., VAN D OORN A. J.: Surface
shape and curvature scales. Image Vision Comput. 10, 8
(1992), 557565.

Figure 8: Two-round search with off-line learning on a

bench query

[LMT05] L EIFMAN G., M EIR R., TAL A.: Semanticoriented 3D shape retrieval using relevance feedback. The
Visual Computer 21, 8-10 (September 2005), 865875.
[PPT07]

ranking risk minimization-based approach to other relevance

feedback schemes as in [LMT05].

P. PAPADAKIS I. P RATIKAKIS S. P., T HEO T.: Efficient 3D shape matching and retrieval using
a concrete radialized spherical projection representation.
Pattern Recognition 40, 9 (2007), 24372452.

An immediate perspective for further research is to extend this general score fusion scheme to other type of shape
descriptors, notably to 2D image-based ones [BKS 05]. Furthermore, we may obtain performance improvements using

[SKP06] S CHRECK T., K EIM D. A., PANSE C.: Visual

feature space analysis for unsupervised effectiveness estimation and feature engineering. In ICME (2006), IEEE,
pp. 925928.

HARIS

submitted to Eurographics Workshop on 3D Object Retrieval (2008)

Submission ID: 1005 / Similarity Score Fusion for 3D Object Retrieval

[SMKF04] S HILANE P., M IN P., K AZHDAN M.,

F UNKHOUSER T.: The Princeton shape benchmark. In
Proc. of the Shape Modeling International 2004 (SMI04)
(Genoa, Italy, 2004), pp. 167178.
[TV04] TANGELDER J. W. H., V ELTKAMP R. C.: A
survey of content based 3D shape retrieval methods. In
Proc. of the Shape Modeling International 2004 (SMI04)
(Genoa, Italy, 2004), pp. 145156.

submitted to Eurographics Workshop on 3D Object Retrieval (2008)