ACM International Conference on Multimedia Information Retrieval, October 30-31, 2008, Vancouver, Canada
Accepted as an oral paper.

Ranking on Semantic Manifold for
Shape-Based 3D Model Retrieval
Ryutarou Ohbuchi

Toshiya Shimizu

University of Yamanashi
4-3-11 Takeda, Kofu-shi
Yamanashi-ken, 400-8511, Japan+81-55-220-8570

University of Yamanashi
4-3-11 Takeda, Kofu-shi
Yamanashi-ken, 400-8511, Japan+81-55-220-8570

ohbuchiAT yamanashi.ac.jp

shimizutsyAT gmail.com

ABSTRACT

1. INTRODUCTION

Semantics associated with 3D shapes are often as important as theshapes themselves in defining “shape similarity” among them. So
far, only a small subset of 3D model retrieval methods took
semantics into account. Most popular approach to semantic 3D
model retrieval is based on Relevance Feedback (RF), an iterative,
interactive approach for a system to learn a semantic class that
embodies “user intention” for the query. A drawback of a typicalRF-based method is its low initial performance as it starts cold
without any semantic knowledge. An alternative approach is offline learning of multiple semantic classes. The approach produces
a good retrieval performance without per-query training iterations,but is unable to capture user intention per-query. The method
proposed in this paper attempts to combine benefits of the two
approaches so that both shared multiple semantic classes and perquery intention can be captured to improve 3D model retrieval.
Our method first learns, off-line, the multiple semantic classes byusing a semi-supervised manifold learning algorithm to produce a“semantic manifold” of the input features. The RF iteration basedon manifold ranking algorithm is then run on the semantic
manifold. Our empirical evaluation showed that this method
significantly outperforms the manifold ranking run in the original,
ambient feature space.

Three-dimensional (3D) models have become ubiquitous. It is
used for 3D games running on mobile-phones and on game
consoles, for such Web-based applications as Google Earth, formedical diagnostics, and for mechanical or architectural design.
The need to organize these 3D models and related contents for
effective creation, distribution, and consumption has prompted
study into shape-based retrieval of 3D models. A shape-based 3Dmodel retrieval system, by definition, compares shape of 3Dmodels for their retrieval [18, 7]. However, retrieval performancesof these systems have been insufficient due to so-called semantic
gap between shape features and semantics associated with them.
For example, 3D models that share a similar meaning may havedifferent shape, or 3D models that have different meanings may
share similar shape. Significant amount of work has been
performed to narrow the semantic gap, mostly in the field ofimage and video retrieval, but also in the field of 3D model
retrieval.
By far the most popular approach to bridge the semantic gap isRelevance Feedback (RF). In a RF based retrieval system, thesystem and the user work interactively and iteratively to capture a
within-session semantics of the user. Given a query, the system
first presents the user with an initial set of retrieval. The user thentells the system her/his preference on some or all of the models in
the initial retrieval. The feedback choice may be positive,

Categories and Subject Descriptors
H.3.3 [Information Search and Retrieval]: Information filtering.
I.3.5 [Computational Geometry and Object Modeling]: Surface
based 3D shape models.

Input feature space

General Terms
Algorithms, Experimentation.

Keywords
3D polygonal models content-based retrieval, manifold ranking,manifold learning, semi-supervised learning.

Adapt tofeaturedistribution

Unlabeledtraining set

Adapt tosemantic
classesLabeledtraining set

User

Unsupervised
Dimension
Reduction
Feature distribution adapted manifold
Supervised
Dimension
Reduction
Semantics adapted manifold

Relevance
feedback tags

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that
copies bear this notice and the full citation on the first page. To copy
otherwise, or republish, to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.
Conference’08, Month 1–2, 2008, City, State, Country.
Copyright 2008 ACM xxxxxxxxxxxxxxxx…$5.00.

Adapt to withinsession semantics

Manifold
Ranking

Overall relevance rank

Figure 1: The proposed algorithm runs the manifold
ranking-based relevance feedback on a manifold thatreflects multiple semantic classes that are learned off-line.
1

ACM International Conference on Multimedia Information Retrieval, October 30-31, 2008, Vancouver, Canada
Accepted as an oral paper.
[23] as the shape feature, which has the Mean First Tier Highly
Relevant (FT-HR) score of 27% by itself if evaluated by using the
SHREC 2006 benchmark [21]. The score increased to 58% withthe multiresolution feature fusion and adaptation to multiple
semantic classes by using the SSDR algorithm [11]. By learning
both long-term and within-session semantics, our proposed
method produced FT-HR=83% after only three RF iterations if
top 20 models are allowed to be tagged for their relevance. If top
50 retrievals are allowed to be tagged for their relevance per RF
iteration, FT-HR>90% is achieved after only three RF iterations.
These figures are significantly better than the FT-HR=59.4%
produced by using the same manifold ranking-based RF algorithm
run in the original features space.

negative, or both. The system may allow additional inputs, suchas a degree of positive-ness. A RF system would capture the user
feedback by using a learning algorithm and tries to improve thenext round of retrieval by modifying features, distance metric,
query set, etc. After several relevance feedback iterations, the user
would be presented with a much improved set of retrieval results.
The RF approach has been employed in retrieving 2D images and
2D movies (see, for example, [14, 15, 24, 20, 6]). It is also used in
retrieving 3D shape models [3, 8, 9]. Elad et al [3] used Support
Vector Machine (SVM), a learning classifier, for the relevance
feedback learning. Novotni et al [9] compared several kernel
based classifiers, including SVM, Biased Discriminant Analysis(BDA) and its kernelized version kernel-BDA, for their retrieval
performance in a RF setting. The method by Leifman, et al [8]tries to make maximum use of small numbers of training samples
by switching from the LDA for a small number of training
samples (e.g., <20) to the BDA for larger numbers of training
samples. Relevance feedback is quite powerful. For example,
Novotni et al [9] reports the performance measured in weighted
mean precision increased from 30% to over 70% after 10 RF
iterations. Despite its success, RF framework has its weakness. A
typical within-session RF framework is being able to capture only
one semantic class per query session. Furthermore, every query
session starts cold so that even a well-established long-term
semantic class must be taught time and again for each query
session.

The contribution of this paper can be summarized as follows;• Proposal of a novel 3D model retrieval method that combines
short-term, per-query-session user intention and establishedmultiple semantics classes for an improved retrieval
performance.
• Experimental evaluation of the proposed method by using astandard 3D model retrieval benchmark. Evaluation showedthat manifold ranking on the semantic manifold significantly
outperforms the same in the original feature space.
The following of this paper is structured as follows. The next
section will describe our proposed method, followed by Section 3
on experiments and their results. We will summarize the paper in
Section 4.

Many learning algorithms are designed for single-class learning
so that the performance drops sharply if it needs to handle
multiple classes. For example, a bundle of SVMs, each one a onevs.-the other classifier, has been used for multiple classrecognition. However, the performance of the bundle is not very
good. Also, one often wants to retrieve a 3D model that is not in
the “correct” class but is similar in shape (or semantics) to thequery. For such a purpose, a hard-decision learning classifier that
produces yes/no result is not as desirable. A graded, smoothtransition in similarity (or dissimilarity) values is needed.

2. METHOD
Proposed method is novel in that it combines manifold learningbased semi-supervised dimension reduction algorithm with amanifold ranking-based relevance feedback algorithm in order tocapture both a set of long-term, shared, multiple semantic classes
and a per-query-session (1-class) user intention. Multiple (e.g., 30
to 100) semantic classes are learned by using off-line semisupervised dimension reduction algorithm by Ohbuchi, et al [11].
It maps the original, ambient feature space onto a lower
dimensional “semantic manifold”. Then, a short-lived, per-session
semantic class is captured by using relevance feedback based on
Manifold Ranking (Mrnk) algorithm [25, 6] run on the semantic
manifold. The use of semantic-manifold instead of the original,
ambient feature space for the manifold ranking improves theeffectiveness of the manifold ranking algorithm significantly.

In this paper, we propose a 3D model retrieval method that takes
into account both a semantic class that reflects user intention forthe session, and shared and well-established multiple semantic
classes for an improved retrieval performance (Figure 1). To
capture multiple semantic classes, the method utilizes the SemiSupervised Dimension Reduction (SSDR) algorithm of Ohbuchi etal. [11] that combines two stages of locality preserving manifold
learning algorithms to produce “semantic” sub-manifold that
captured both a distribution of unlabeled features and multiple
semantic classes. To adapt to per-query-session user intention, a
relevance feedback framework based on the Manifold Ranking(Mrnk) algorithm [25, 6] is run on the semantic manifold
produced by the SSDR. The manifold ranking is one of the mostpowerful RF algorithms; according to He, et al [6], Mrnk
outperformed both Support Vector Machine (SVM) [24] andSVMacitive [20, 21] in relevance feedback image retrieval
experiments. To our knowledge, the proposed method is the firstsuccessful attempt to perform relevance feedback on a manifoldthat reflects multiple semantic classes.

To capture multi-scale shape features, our method uses themultiresolution shape comparison approach of Ohbuchi et al, al[11] based on a mathematical morphology-like Multi-Resolution(MR) representation. Given a 3D model and a set ofpredetermined scale values, or alpha, the approach first creates a
set of 3D MR shape models by using the 3D alpha shapes
algorithm [2]. Once the MR set of 3D models is obtained, a(single resolution) feature extraction algorithm is applied to themodel at each resolution level.

Our experimental evaluation of the proposed algorithm showed
the effectiveness of the proposed algorithm in capturing both
long-term, shared semantics and within-session semantics (userintention). We used the Surflet-Pair Relation Histograms (SPRH)

The SSDR and the manifold ranking based relevance feedback
may be applied to the MR set of features in several different ways.
The proposed algorithm performs the SSDR and the manifold
ranking based relevance feedback separately at each resolution

2.1 Multiresolution Feature Fusion

2

ACM International Conference on Multimedia Information Retrieval, October 30-31, 2008, Vancouver, Canada
Accepted as an oral paper.
multiple semantic classes. Note that the dimensionality of thesemantic manifold is significantly smaller than the input feature
space. For example, a 625-dimensional SPRH feature has been
reduced down to a 50-dimensional vector on the SA-manifold.

level (Figure 2). The L relevance ranks produced by the manifold
ranking are combined into an overall relevance rank among thepair of models by using a uniform weight linear combination.

2.2 Semi-Supervised Dimension Reduction

The SSDR algorithm can be summarized as follows, whose
details can be found in the paper by Ohbuchi, et al [11].

The Semi-Supervised Dimension Reduction (SSDR) algorithm
consists of two steps. The first step is adaptation to the feature
distribution by using an Unsupervised Dimension Reduction(UDR) algorithm. We call the step Feature set Adaptation (FA),and the manifold produced by the FA is a FA-manifold. For theexperiments that follow, we use the Locally Linear Embedding(LLE) [13] for the UDR. The LLE is a globally non-linear but
locally linear dimension reduction algorithm that learns amapping from the input space onto a subspace, or a manifold,unsupervised. As the LLE produces a mapping defined only at thetraining samples, the mapping is smoothly and continuously
approximated by using the RBF-network [4]. A new feature in theoriginal ambient space is projected onto the approximatedmanifold to transform it into a point on a FA-manifold.

(1) Extract feature: Extract a k-dimensional feature from eachmodel in the unlabeled set of 3D models MUL of size p for
the UDR. For the experiments that follow, we used theSurflet Pair Relation Histograms (SPRH) by Wahl, et al. [23].
(2) Unsupervised Learning of Feature Distribution: Given
the set of p unlabeled features, an UDR algorithm learns thel-dimensional subspace SUDR spanned by the set. The
resulting SUDR maps an input k-dimensional feature to theinterim, l-dimensional FA-manifold in which l < k . We
used the LLE for the UDR. For the LLE, we must
approximate the SUDR so that it is defined everywhere in the
input space. We used the RBF-network [4] for theapproximation.

The second step adapts the FA-manifold to the multiple,
predefined semantic classes by using a Supervised Dimension
Reduction (SDR) algorithm. We call the process Semantics
Adaptation (SA), and the manifold produced by the SA is a SAmanifold. For the experiments that follow, we used Supervised
Locality Preserving Projections (SLPP) algorithm by Xhaofei He,
et al. [5] and the Local Fisher Discriminant Analysis (LFDA) by
Sugiyama, et al. [17]. Both SLPP and LFDA are linear, and try to
decrease distance among samples in the same class while trying toincrease distances among different classes. The difference is that
the LFDA allows multimodality in a semantic class. Using theSDR, features in the FA-manifold are mapped onto the SAmanifold, which is adapted to both feature distribution and(3) Off-Line Supervised Learning of Semantic Classes:
Extract k-dimensional features from the set of labeled 3Dmodels M SL for the SDR. Note that the size q of the M SL istypically much smaller than the size p of the MUL . A SDR
algorithm then learns categories from the q labeled featuresin a batch and encodes the knowledge into the mdimensional subspace S SDR to be used for later SDRs. The
manifold maps an interim l-dimensional feature onto thesalient, m-dimensional feature used for retrieval. We used the
SLPP [5] and the LFDA [17] for the SDR.
(4) DB pre-processing: For each k-dimensional input feature of
all the models in the database M D , employ the UDR andSDR in succession to produce m-dimensional salient featurethat incorporates semantic concepts learned from the labeledmodels in the training set M SL . Store the salient feature
together with the corresponding 3D model for later retrieval.
As the dimension m of a salient feature is much smaller thanthe dimension k of the corresponding input feature, cost of
distance computation and feature storage are significantly
reduced.

3D model tocompareGenerate
multiresolution(MR) model set

Extract feature
UDR or SSDR

0

1

0

1

…
…

L-2

L-1

L-2

L-1

When a query session starts, the feature of the query model isprocessed by the UDR and then the SDR described above so thatit also mapped onto the SA-manifold. The user presents thesystem with the query feature mapped onto the SA-manifold. The
system performs the manifold ranking in the unsupervised mode
to retrieve initial retrieval set. Then, the Relevance Feedback (RF)iteration starts. At the ith RF iteration, the user is presented with
top S retrieval results for feedback. We refer to the size S as
Relevance Feedback scope, or RF-scope. To provide feedback,our method simply tags the positive samples, a method that fits
most naturally with the manifold ranking algorithm. The detailed
steps for a retrieval session are as follows;…

MR feature set of theother 3D model
Relevance feedback
Manifold ranking…

Fuse relevance ranks+(1) Query Feature Extraction and Processing: Extract the
input feature of the query model mq ∈ M Q and perform the
UDR and SDR in succession to produce a feature in the SAmanifold having dimension m.

Overall relevance rank
Figure 2: The semi-supervised dimension reduction and the
manifold ranking steps are performed per resolution level,
and relevance ranks from multiple resolution levels are
fused into an overall relevance.

3

ACM International Conference on Multimedia Information Retrieval, October 30-31, 2008, Vancouver, Canada
Accepted as an oral paper.
(2) Initial ranking and retrieval: Apply the manifold ranking
algorithm [25, 6] in the unsupervised mode to the features inthe database and to the (initial) query to compute the initialranking of the models in the database against the query.
Retrieve and present top-ranked S models for the relevance
feedback tagging.

neighbors on the manifold. At the equibilium, the higher the
diffused value, the higher the similarity rank of the points in the
database to the (expanded) query set. As the diffusion occurs
along the manifold, similarity rank thus computed are better thanthose computed directly in the input feature space.
Create the affinity matrix W where Wij indicates the similarity
between samples xi and x j(3) Relevance feedback tagging: Perform relevance feedbackon the S models retrieved by tagging relevant models withthe “positive”, and the others with none.

⎧⎛ d ( xi , x j ) ⎞⎪ exp ⎜⎜ −⎟⎟ if i ≠ j
Wij = ⎨
σ⎝⎠⎪0otherwise⎩(4) Re-ranking and retrieval: Expand the query set byconsidering the database models having “positive” tag as thepart of the expanded query set. Perform manifold ranking
using the expanded query set. Retrieve highest ranking
models for relevance feedback tagging. If not satisfied withthe retrieved set, go to step (3) above.

The distance metric d ( xi , xi ) used for the affinity matrix affects
the ranking. We will compare L1-norm, L2-norm, L0.5-norm as
well as Cosine distance for their ranking performance. The
positive parameter σ defines the radius of influence. Note that
Wii = 0 since there is no ark connecting a point with itself. The
matrix W is positive symmetric. We then form a normalizedgraph Laplacian L ,2.3 Manifold Ranking
Our method uses the manifold ranking [25] algorithm for
relevance feedback learning. Manifold ranking is a graph-basedlearning algorithm that can be used in unsupervised, supervised,or semi-supervised mode. We used the manifold ranking
algorithm by Zhou, et al. [25], among others. The manifold
ranking algorithm tries to rank distances (or similarity) of points
from a given sample on the manifold of all the samples, taking
global distribution of the samples into account.

{

−

1

−

1

L = D 2 (D − W )D 2

Where D is a diagonal matrix in which Dij equals to the sum of
the i-th row of W , that is, Dij = ∑ j Wij Then the ranking vectorTf = ⎣⎡ f1,", f n ⎦⎤ can be estimated by iterating the following untilconvergence;}Let χ = x1,", xq , xq +1,", xn be a set of features in a mdimensional feature space \m , in which first q points from x1
to xq are the queries and the rest are the points we want to rank
according to their similarity to the queries. Let d : χ × χ → \denote a distance metric on χ , e.g., L1 norm or Cosine distance,that assigns a pair of points xi and xi a distance d ( xi , x j ) . Let
f : χ → \ be a ranking function that assigns each xi a ranking
Tscore fi , forming a rank vector f = ⎣⎡ f1,", f n ⎦⎤ . Let the nT
dimensional vector y = ⎣⎡ y1,", yn ⎦⎤ be a label vector.

f (t +1) =11Y( I − L ) f (t ) +
1+ μ
1+ μ

The parameter μ > 0 is a regularization parameter, and affects
retrieval performance and the convergence of the iteration above.
Let f * be the limit of the above iteration. Rank each point xi asa label yi = arg max j ≤ c fij* . In the case above, f * has a close
form solution;−1

The same manifold ranking algorithm may be used in two modes,
unsupervised and supervised. In the unsupervised mode, the goal
is to compute the similarity ranks of the 3D models in the
database to the (single) query. So we set yi = 1 for the querymodel only and yi = 0 for the rest, i.e., all the models in the
database. In the supervised 1-class learning mode under the
relevance feedback framework, the goal is to compute thesimilarity ranks of the 3D models in the database to the expanded
query set containing more than one points. The expanded query
set consists of the (initial) query model and all the models in the
database that are tagged as “positive” up to current relevance
feedback iteration. Thus, we set yi = 1 for the query model andthe models that are tagged “relevant” during the RF iterations.
The initial value yi = 0 is given to the other models in the
database without the “relevant” tag.

⎛1 ⎞f * = ⎜I + L⎟ Y
μ⎝⎠We tried both iterative and the closed-form solutions on MatLab,and mostly used the latter, closed-form solution, for it was fasteror our set of parameters when implemented in the MatLab.
Most of the compute-intensive work for the SSDR is in the preprocessing stage. The MR model set generation, feature extraction,
vector projection for dimension reduction, and manifold ranking
is needed per query. The manifold ranking in particular must run
once for every RF iteration, whose cost is dominated by the costof computing f * . The cost increases with the size of matrix L ,that is, the number of features n. On a contemporary PC, even fora dense matrix, it takes a few seconds to obtain f * for the
SHREC 2006 database having 1,814 models. Further reduction incomputational cost is possible if the affinity matrix Wij is madesparse by limiting the entries to the feature pairs having a distanceless than a certain threshold.

Intuitively, the process of manifold ranking resembles to theprocess of solving a diffusion equation on an irregular mesh. The
mesh, or the manifold, is generated by connecting feature points
in the high dimensional input features space based on their mutual
proximity. The proximity during mesh generation is determinedby using a distance measure, e.g., L1-norm, in the ambient feature
space. The manifold ranking algorithm iteratively diffuses theinitial value of yi = 1 given to the (expanded) query set to its

2.4 Distance Measures

We compared several distance measures, including Lk -norm for
k=0.5, 1.0, and 2.0, as well as the cosine measure for distance4

ACM International Conference on Multimedia Information Retrieval, October 30-31, 2008, Vancouver, Canada
Accepted as an oral paper.
Mrnk in unsupervised mode. Among the fixed distance metrics,
for both single resolution (Figure 3a) and multi-resolution fusion(Figure 3b) cases, the L0.5-norm performs the best, as suggested
in [1]. It is followed by the L1-norm and then the KLD. In thecase of the single-resolution (SR-) SPRH feature, its performance
improved from FT-HR=26.7% to FT-HR=31.9% by simply
switching from the KLD to L0.5-norm. For the unsupervised
Mrnk that adapts to the distribution of features, the L0.5-norm
performed the best again, followed by the L1-norm. The
performance of the original SR-SPRH using the KLD is FTHR=26.7%, while the unsupervised manifold ranking that
employed the L0.5-norm produced FR-HR=34.7%, an
improvement of 8.0%.

computation for retrieval, and for forming the affinity matrix W
to be used for manifold ranking. Let x = ( xi ) , y = ( yi ) are thefeature vectors and n is the dimension of the vectors. Dependingon the value of k, d k (x, y ) is the Manhattan distance if k=1.0, or
the Euclidian distance if k=2.0.
⎡
d k ( x, y ) = ⎢
⎣

∑(
n

i

xi − yi

k

)

1

⎤ k
⎥⎦

According to Aggarwal, et al [1], k<1.0, e.g., k=0.5 is expected toperform better for higher dimensional features. As the cosine
measure is a measure of similarity in the range [ 0,1] , weconverted it to a distance using the following equation;

x⋅y
x ⋅ y

US-MrnkSR-SPRH

d cos (x, y ) = 1 −nd KLD ( x, y ) =SR-SPRH

Another distance measure we employed is the Kullback-Leibler
divergence (KLD). The KLD is sometimes referred to as
information divergence, or relative entropy, and is not a distancemetric, for it is not symmetric;∑ ( y − x ) ln x
i

i =1

i

yi
i

cos
L2
L1
L05
cos
L2
L1
L05
KLD

29.3
28.2
33.1
34.7
24.8
24.2
28.8
31.9
26.7
10

3. EXPERIMENTS AND RESULTS

20

30

40

50

(a) Single-resolution SPRH feature.

MR-SPRH

US-MrnkMR-SPRH

Evaluation of relevance-feedback based retrieval algorithms for
3D models is not standardized. While the SHREC 2007 [22] listof track proposal included the “Relevance feedback” track, thetrack did not materialize as it saw no entrant. We thus
experimentally evaluated the proposed algorithm by simulating
relevance feedback on SHREC 2006 [21] database and query set,
as it is used widely by many researchers. The database in the
SHREC 2006 is the union of the test and train set of the Princeton
Shape Benchmark [16], which is a 1,814 model collection ofpolygon soup models. The SHREC 2006 uses 30 query models
that are not in the database. There are many different performancemeasures used in the SHREC 2006. Among them, we used theMean First Tier Highly Relevant (FT-HR). First Tier is a ratio, in
percentile, of the models retrieved from the desired class (i.e., thesame class as the query) in the top k retrievals, in which k is thesize of the class. The Mean First Tier is a mean over the 30 querymodels of the SHREC 2006. The designation “highly relevant”
comes from the fact that it uses the “correct” ground truth class,instead of the “approximately correct” ground truth class.

cos
L2
L1
L05
cos
L2
L1
L05
KLD

38.4
37.1
40.5
41.1
33.4
30.8
35.6
37.2
34.9
10

15

20

25

30

35

40

45

(b) Fusing multi-resolution SPRH features
Figure 3: Comparison of distance measures using thesingle-resolution and multi-resolution SPRH features.

3.2 Ranking on Semantic Manifold
In the second set of experiments, we compared the performanceof the manifold ranking algorithm applied to three different
manifolds; (1) the original feature, (2) the FA-manifold adapted tofeature set distribution produced by the UDR, (3) the SA-manifold
adapted to multiple semantic classes produced by the SSDR, thatis, the UDR followed by the SDR. In this set of experiments, weused the only the SPRH feature in the multiresolution featurefusion framework.

Performing relevance feedback experiment manually is not very
viable. We simulated human feedback using the SHREC 2006
ground truth class. At each one of the RF iterations, top S retrieval(i.e., relevance feedback scope) is scanned, and if a model in the
ground truth class for the query model is found in the top S
models, it is tagged as “relevant”. We assumed the user is error
free so that relevance feedback is always correct. (Some of thestudies on relevance feedback algorithms inject errors into the
feedback tags to evaluate robustness.)

For the SSDR we used the best performing parameters anddimension reduction algorithms according to Ohbuchi, et al [11].
We used the MR-SPRH feature, and applied the LLE [13] for the
UDR, followed by the LFDA [17] for the SDR. Compared to theoriginal dimension of 625 for the SPRH feature, the feature on the
FA-manifold is 300, and the feature on the SA-manifold is 50.

3.1 Distance Measures and Retrieval
Performance
In the first set of experiments, we compared four fixed distancemeasures, L0.5-norm, L1-norm, L2-norm, and KLD, with the5ACM International Conference on Multimedia Information Retrieval, October 30-31, 2008, Vancouver, Canada
Accepted as an oral paper.
performances if applied to the dimension reduced features,that are, features in the FA-manifold and the SA-manifold(Figure 5).

The UDR algorithm is trained by using 10,000 unlabeled models
quasi-randomly sampled from the NTU database [10]. The size ofthe neighbourhood for the LLE is chosen to be 2.0% of the size ofthe database, that is, 200, and the spread of the RBF network
kernel is 0.9. For the manifold ranking, we used μ = 100 and
σ = 0.001. To train the SDR, we used the SHREC 2006 database,with its 1,814 models and 30 classes.

The RF-Mrnk run on the SA-manifold performed the best,
followed by the RF-Mrnk run on the FA-manifold. With only
4 RF iterations using the RF scope size S=50, the RF-Mrnk
run on the SA-manifold reached FT-HR=93.3%, while the
RF-Mrnk run on the FA-manifold reached FT-HR=76.9%.
after 4 RF iterations. Compared to these two, the RF-Mrnk
run in the original feature space produced significantly lower
score of FT-HR=64.3%.

Figure 4 shows the summary comparison of performances ofvarious methods. In the figure, manifold ranking is applied to thefollowing three feature spaces;z SA: Manifold adapted to feature distribution and multiple
semantic classes by using the Semi-Supervised Dimension
Reduction [11].
z FA: Manifold adapted to feature distribution by using theUnsupervised Dimension Reduction [11].
z Orig.: Original feature space.

From these results, it can be concluded that the RF-Mrnk benefits
from both unsupervised and semi-supervised dimension reduction
applied to the original features. The manifold ranking algorithm
by itself tries to find a manifold spanned by the features in theambient space before applying relevance score diffusion.
However, RF-Mrnk appears to perform better if it is applied on
the lower dimensional FA-manifold adapted to feature
distribution and SA-manifold adapted to both feature distribution
and multiple semantic classes. The best retrieval performance isproduced by the RF-Mrnk run on the SA-manifold.

On these three spaces, two modes of manifold ranking algorithms,
the US-Mrnk for the unsupervised mode and RF-Mrnk for the
relevance feedback mode, are applied. These manifold ranking
algorithms used L0.5-norm to form the affinity matrix W. These
two modes of manifold ranking algorithms are compared against
No-Mrnk that employed Cosine distance directly on thesemanifolds. For the RF-Mrnk, relevance feedback scope size S of
20 and 50 are chosen; that is, top S retrievals were subjected to
RF tagging. The performance indices in the Figure 4 are obtained
after 4 RF iterations (plus the initial retrieval without feedback.)

RF-Mrnk RF-Mrnk
S=20
S=50

It is also interesting to note that the semi-supervised dimension
reduction algorithm [11] that learns multiple classes at once (FTHR=58.1%) performed nearly as well as the single class learning
using RF with S=20 (FT-HR=59.4%).

No-Mrnk US-Mrnk

As the baseline, the original SPRH feature (without
multiresolution feature fusion) using KLD for distancecomputation had the FT-HR=26.7%. By using the multiresolution(MR) feature extraction with 6 levels, Cosine distance, and linear
combination of the MR distances, the performance went up to FTHR=37.2% (The bar at the bottom of the Figure 5.). The
combination of the MR and the Feature set Adaptation (FA)produced FT-HR=45.4%, and the multiple semantic class learning
pushed it further to FT-HT=58.1%.
z Unsupervised Manifold Ranking in the original feature
space: Unsupervised Manifold Ranking (US-Mrnk) run in theambient space (original feature space) produced the FTHR=41.0%, which is significantly better than the FTHR=37.2% of the original MR-SPRH feature.

SA
FA
Orig.
SA
FA
Orig.
SA
FA
Orig.
SA
FA
Orig.

93.3
76.9
64.3
82.8
64.8
59.4
59.1
44.6
41.0
58.1
45.4
37.2
0

z Unsupervised Manifold Ranking in the dimension-reduced
feature spaces: US-Mrnk, however, did not improve retrieval
performance for the feature sets that are already dimension
reduced by using manifold learning algorithms described in[11]. When the US-Mrnk is applied to the FA-feature or SAfeature, their retrieval performances did not change
significantly. This outcome is to some extent expected since
the manifold ranking algorithm by itself tries to find its own
manifold by connecting the features in ambient space before
running a diffusion process on the manifold. The methods tofind manifold used by the manifold learning and manifold
ranking algorithms are quite similar.

20

40
60
FT-HR [%]

80

100

Figure 4: Retrieval performances of various methods basedon multi-resolution SPRH feature.

Figure 5a to Figure 5c show, for the three feature spaces on which
the RF-Mrnk took place, the relationship between the number of
RF iterations and the retrieval performance. The three feature
spaces are the Orig. (Figure 5a), FA (Figure 5b), and SA(Figure 5c) described above. The FT-HR values in Figure 4
corresponds to those in Figure 5 at RF iterations = 4.
For all of the three feature spaces, the performance reached its
saturation point after about 4 RF iterations excluding the initial
retrieval (0th iteration). Also, as expected, for all of the three
feature spaces, retrieval performance at saturation point improved
as the RF scope size S is increased.

z Supervised Manifold Ranking using Relevance Feedback:On-line supervised manifold ranking using the RelevanceFeedback framework (RF-Mrnk) did significantly improved
the scores for the original feature. RF-Mrnk also improved

6

ACM International Conference on Multimedia Information Retrieval, October 30-31, 2008, Vancouver, Canada
Accepted as an oral paper.
RF cases. In the example, manifold ranking-based RF works
significantly better if it is run on the feature-adapted manifold(RF-Mrnk-FA) or on the semantic adapted manifold (RF-MrnkSA) than in the ambient feature space (RF-Mrnk-Orig.).

100
S=10
S=30
S=50

90
FT-HR [%]

80

S=20
S=40
Original

70

4. CONCLUSION AND FUTURE WORK60

In this paper, we proposed a novel 3D model retrieval algorithm
that takes into account both long-lived semantics learned frommultiple semantic classes and a short-lived, within-session user
intention learned by using relevance feedback. The former isaccounted for by learning multiple (e.g., 30 to 100) semantic
classes at once, off-line, by using a Semi-Supervised Dimension
Reduction (SSDR) algorithm [11]. The latter is accounted for byusing a relevance-feedback framework based on the manifold
ranking algorithm [25]. The method performs manifold rankingbased relevance feedback on the semantic-manifold that embodies
both feature distribution and multiple semantic classes.

50
40
30
20
10
0

1

2

3

4 5 6 7
RF iterations

8

9

10

FT-HR [%](a) Original feature space + RF-Mrank.
100
90
80
70
60
50
40
30
20
10
0

S=10
S=30
S=50
0

1

2

3

4

Experimental evaluation showed that proposed approach is quite
effective. The use of semantic-manifold instead of the original,
ambient feature space improved the effectiveness of the manifold
ranking algorithm significantly. The manifold ranking-based RF
run on the original features achieved the First Tier Highly
Relevant (FT-HR) score of FT-HR=64%, if the feedback scope
S=50 is used. The same run on the semantic-adapted manifold
produced the FT-HR=93% after only 3 RF iterations withfeedback scope S=50.

S=20
S=40
Original
5

6

7

8

9

5. ACKNOWLEDGMENTS
The authors would like to thank Takahiko Furuya, Masaki Tezuka,
and Shun Kawamura for performing some of the experiments.
This research has been funded in part by the Ministry of
Education, Culture, Sports, Sciences, and Technology of Japan(No. 20500089).

10

RF iterations

FT-HR [%](b) FA-manifold + RF-Mrank.
100
90
80
70
60
50
40
30
20
10
0

6. REFERENCES[1] C.C. Aggarwal, A. Hinneburg, D.A. Keim, On the surprising
behavior of distance metrics in high dimensional space, Proc.
International Conf. On Database Theory (2001).
[2] H. Edelsbrunner, E.P. Mücke, Three-dimensional Alpha
Shapes, ACM TOG, 13(1), pp. 43-72 (1994).
S=10
S=30
S=50
0

1

2

3

4 5 6
RF iterations[3] M. Elad, A. Tal, S. Ar., Content based retrieval of vrml
objects – an iterative and interactive approach, Proc. EG
Multimedia 39, pp. 97-108 (2001).

S=20
S=40
Original
789[4] S. Haykin, Neural network a comprehensive foundation,
Second Edition, Prentice Hall, 842 pages (1999).
[5] X. He, P. Niyogi, Locality Preserving Projections, Advancesin Neural Information Processing Systems, 16, Vancouver,
Canada (2003).
http://people.cs.uchicago.edu/~xiaofei/LPP.html

10(c) SA-manifold + RF-Mrank.
Figure 5: RF based on manifold ranking on three feature
spaces, the original feature space (a), the FA-manifold (b),and the SA-manifold (c).

[6] J. He, M. Li, H-J Zhang, H. Tong, C. Zhang, ManifoldRanking Based Image Retrieval, Proc. ACM Multimedia
2004, pp. 9-16 (2004).

Figure 6 shows a set of retrieval examples for the SHREC 2006
query 20 (the “hand”, top left). Relevance feedback scope size
S=50 and 4 RF iterations (+ 1 initial retrieval) are used for all the[7] M. Iyer, S. Jayanti, K. Lou, Y. Kalyanaraman, K. Ramani,
Three Dimensional Shape Searching: State-of-the-art Review
and Future Trends, Computer Aided Design, 5(15), pp. 509530, (2005).

7

ACM International Conference on Multimedia Information Retrieval, October 30-31, 2008, Vancouver, Canada
Accepted as an oral paper.
[8] G. Leifman, R. Meir, A. Tal, Semantic-oriented 3d shape
retrieval using relevance feedback, The Visual Computer,21(8-10), pp. 865-875, (2005).

[17] M. Sugiyama, Dimensionality reduction of multimodal
labeled data by local Fisher discriminant analysis, Journal of
Machine Learning Research, 8, pp.1027-1061 (2007).

[9] M. Novotni, G.-J. Park, R. Wessel, R. Klein, Evaluation of
Kernel Based Methods for Relevance Feedback in 3D Shape
Retrieval, Proc. The Fourth International Workshop on
Content-Based Multimedia Indexing (CBMI'05) (2005).

[18] J. Tangelder, R. C. Veltkamp, A Survey of Content Based
3D Shape Retrieval Methods, Proc. SMI '04, pp. 145-156(2004).
[19] J. B. Tanenbaum, V. de Silva, J.C. Langford, A Global
Geometric Framework for Nonlinear Dimensionality
Reduction, Science, 290(5500), pp. 2319-2323 (2000).

[10] NTU 3D Model Database, ver.1, http://3d.csie.ntu.edu.tw/[11] R. Ohbuchi, A. Yamamoto, J. Kobayashi, Learning semantic
categories for 3D Model Retrieval, Proc. ACM MIR 2007,
pp. 31-40 (2007).

[20] S. Tong, E. Chang, Support vector machine active learningfor image retrieval, Proc. ACM Multimedia 2001, pp. 107118 (2001).

[12] J. Pu, K. Lou, K. Ramani, A 2D Sketch-Based User Interface
for 3D CAD Model Retrieval, Computer Aided Design andApplication, 2(6), pp.717-727 (2005).

[21] R. C. Veltkamp, R. Ruijsenaars, M. Spagnuolo, Roelof vanZwol, SHREC2006 3D Shape Retrieval Contest, Dept of Infoand Comp. Sci., Utrecht University, Technical Report UUCS-2006-030 (ISSN: 0924-3275).(2006).

[13] S.T. Roweis, L.K. Saul, Nonlinear Dimensionality Reduction
by Locally Linear Embedding, Science, 290(5500), pp. 23232326 (2000).

[22] R.C. Veltkamp, F.B. ter Harr, SHREC 2007 3D Shape
Retrieval Contest, Dept of Info and Comp. Sci., Utrecht
University, Technical Report UU-CS-2007-015 (2007).

[14] J.J. Roccio, Relevance feedback in information retrieval, The
SMART Retrieval System, pp. 313-323, Prentice-Hall (1971).

[23] E. Wahl, U. Hillenbrand, G. Hirzinger, Surflet-Pair-Relation
Histograms: A Statistical 3D-Shape Representation for Rapid
Classification, Proc. 3DIM 2003, pp. 474-481 (2003).

[15] Y. Rui, T.S. Huang, M. Ortega, S. Mehrotra, Relevance
feedback: a power tool for interactive content-based image
retrieval, IEEE Trans. Circuits and Systems for Video
Technology, p. 59-66 (1998).

[24] L. Zhang, F. Lin, B. Zhang, Support vector machine learningfor image retrieval, Proc. IEEE ICIP 2001, vol. 2, pp. 721724 (2001).

[16] P. Shilane, P. Min, M. Kazhdan, T. Funkhouser, The
Princeton Shape Benchmark, Proc. SMI ‘04, pp. 167-178(2004). http://shape.cs.princeton.edu/search.html

Query[25] D. Zhou, O. Bousquet, T.N. Lal, J. Weston, B. Schölkopf,
Learning with Local and Global Consistency, Proc. NIPS
2003 (2003).
Rank

1

2

3

4

5

Performance
6

7

8

9

10

FT-HR [%]NDCG@25
11.76

Orig.

0.181417.65

FA0.307541.18

SA0.6377

RFMrnkOrig
RFMrnkFA
RFMrnkSA

23.53
0.440676.47
0.857482.35
0.8943Figure 6: Retrieving the query20 (the “hand”, top left) from the SHREC 2006. Manifold-ranking based Relevance Feedback(RF-Mrnk) run on the Semantic Adapted manifold (RF-Mrnk-SA) performed the best, followed by the RF-Mrnk run on the
Feature Adapted manifold (RF-Mrnk-FA). (RF scope size S=50. RF iterations=4.)8