Ryutarou Ohbuchi, Takahiko Furuya, Distance Metric Learning and Feature Combination for Shape-Based 3D Model Retrieval, poster
paper, Proceedings of the ACM workshop on 3D object retrieval 2010, Firenze, Italy, (2010).

Distance Metric Learning and Feature Combinationfor Shape-Based 3D Model Retrieval
Ryutarou Ohbuchi

Takahiko Furuya

University of Yamanashi
4-3-11 Takeda, Kofu-shi
Yamanashi-ken, 400-8511, Japan

University of Yamanashi
4-3-11 Takeda, Kofu-shi
Yamanashi-ken, 400-8511, Japan

ohbuchiAT yamanashi.ac.jp

snc49925AT gmail.com

ABSTRACTThis paper proposes a 3D model retrieval algorithm that employs
an unsupervised distance metric learning with a combination of
appearance-based features; two sets of local visual features and aset of global features. These visual features are extracted fromrange images rendered from multiple viewpoints about the 3Dmodel to be compared. The local visual features are bag-offeatures histograms of a set of Scale Invariant Feature Transform(SIFT) features by Lowe [7] sampled at either salient or dense andrandom points. The global visual feature is also a SIFT featuresampled at an image center. The proposed method then uses anunsupervised distance metric learning based on the Manifold
Ranking (MR) [15] to compute distances between these features.
However, the original MR may not be effective when applied to aset of features having certain distance distribution. We propose anempirical method to adjust the distance profile so that the MR
becomes effective. Experiments showed that the retrieval
algorithm using a linear combination of distances computed fromthe proposed set of features by using the modified MR performed
well across multiple benchmarks having different characteristics.

Categories and Subject Descriptors
H.3.3 [Information Search and Retrieval]: Information filtering.
I.3.5 [Computational Geometry and Object Modeling]: Curve,
surface, solid, and object representations. I.4.8 [Scene Analysis]:
Shape.

General Terms
Algorithms, Experimentation.

Keywords
Content-based retrieval, manifold ranking, distance metriclearning, bag-of-features, 3D geometric modeling, 3D object
retrieval, feature combination.

1. INTRODUCTION
Effective and efficient management of 3D models, especially via
content based retrieval by their shape [5][11], has become an
important tool in such diverse areas as mechanical design, medical
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 priorspecific permission and/or a fee.
3DOR’10, October 25, 2010, Firenze, Italy.
Copyright 2010 ACM 978-1-4503-0160-2/10/10...$10.00.

diagnosis, 3D game, as well as movie and 3D TV content
production.
Of various 3D model retrieval methods, view-based approaches,the Light Field Descriptor (LFD) [1] being an early example, haveenjoyed high retrieval performance. The view-based approaches
also have an advantage, for they are relatively immune tovariations in shape representations, e.g., voxels, B-Rep solids,
polygon soup, point set, etc. Recently, view-based 3D model
matching approaches employing multi-view, multi-scale, local
visual features, e.g., the BF-SIFT [8] and the BF-DSIFT [3] hasbeen proposed. To integrate thousands or tens of thousands of
local features extracted from multiple images, the method
employed a Bag-of-Features (BoF) approach [2][10][13]. The
BoF integration produces a feature per 3D model, making themodel to model comparison faster and easier than comparing setsof local features. The method produced very good retrieval
performance for articulated models, and performed as well as theother methods for rigid models. However, their distancecomputation employed one of several fixed distance metrics. It
has been shown in image retrieval and other fields that a distancemetric adaptive to distribution of features in the feature space
improves distance computation, and thus retrieval performance.
In this paper, to further improve retrieval performance, we apply
Manifold Ranking of Zhou et al [15] on the features produced bybag-of-visual features algorithms for 3D model retrieval. In doing
so, we discovered that certain distribution of distances made the
MR ineffective for high-dimensional feature vectors produced bysome of bag-of-features approaches. We thus propose anempirical method to adjust the distance distribution in order toimprove efficacy of the MR algorithm. Experiments showed that
our modified MR algorithm, called DA-MR, for Distance Adjusted
Manifold Ranking, works quite well.
Renderrange
imagesExtract
featureComputedistance

DistanceAdjusted
Manifold
Ranking

distance

DA-MR

salient
SSIFT

random & dense
Render

DSIFT

distance

DA-MR

distance

DA-MR

Combined
distance+

center
1SIFT

Figure 1. An overview of the proposed algorithm. The
Distance Adjusted Manifold Ranking (DA-MR) is effective
for high-dimensional features of the BF-DSIFT [3].

Ryutarou Ohbuchi, Takahiko Furuya, Distance Metric Learning and Feature Combination for Shape-Based 3D Model Retrieval, poster
paper, Proceedings of the ACM workshop on 3D object retrieval 2010, Firenze, Italy, (2010).
We also experiment with combination of both local and global
visual features for more robust 3D model retrieval algorithm. A
method using local feature only could have difficulty
distinguishing some of the shapes, e.g., pipes bent in U shape andin S shape, for they have almost identical local features. A globalfeature, on the other hand, would have difficulty handling
articulated shapes, e.g., snakes in various different posture. We
explore combinations of (1) bag of salient local visual feature,(2) bag of dense and random local visual feature, and (3) global
visual feature, to see if a robust combination could be found.

3.

Contributions of this paper can be summarized as follows.
(1) Identification of a difficulty in applying the Manifold
Ranking [15] algorithm for certain high dimensional featuresoften produced by bag-of-features approach. We propose anempirical remedy for the difficulty. Experimental evaluationof the proposed remedy shows its effectiveness.

4.

(2) Demonstration of a combination of local and global featuresthat could produce a 3D model retrieval method that performrobustly for a database containing unknown composition of
rigid and articulated/globally deformed models.
The remaining parts of this paper are structured as follows. We
will describe the proposed algorithm in Section 2. Empiricalevaluation of the proposed algorithm will be presented in
Section 3, followed by summary and future work in Section 4.

5.

2. ALGORITHM

6.

In this section, we first describe two variations of our bag of local
visual features approach to 3D model feature extraction [8][3].
We then describe a method to improve distance computation
among a pair of such feature vectors by using the Manifold
Ranking [15] algorithm having distance profile modification.

2.1 Local and Global Visual Features
We combine three methods to compute feature a vector describing
a 3D model. The first two, the Bag-of-Features Salient SIFT (BFSSIFT) [8], Bag-of-Features Dense SIFT (BF-DISFT) [3] by
Ohbuchi, Furuya, Osada, et al. are based on local features
extracted from multi-view range image renderings. These local
features are integrated into a feature vector per 3D model by using
the bag-of-features approach.
For the global feature, we propose a simple one; per-View Match
One SIFT (VM-1SIFT) based also on SIFT. The VM-1SIFT also
employs multi-view range image renderings, but extract a globalfeature, which is a SIFT feature, per range image. Thus a 3Dmodel is described by a set of global features whose number
equals the number of views.

2.1.1 Bag-of-Local Visual Features
The BF-SSIFT and BF-DSIFT computes a feature per 3D model
following the steps below;
1.

2.

Partially normalize pose: Both BF-SSIFT and BF-DSIFT
perform partial pose normalization for translation anduniform scaling so that the model is centered at origin andfits within a sphere of radius 1.0.
Render multi-view range images: Render range images ofthe model from N r viewpoints spaced evenly in the solid
angle. We used Nr=42 for the experiments below, following

the paper by Furuya, et al. [3]. The rendering is done on a
GPU via OpenGL API.
Extract SIFT features: From the set of range images,
extract local, multi-scale, multi-orientation, visual features byusing the Scale Invariant Feature Transform (SIFT) [7]algorithm. A SIFT feature encodes position, orientation, andscale of gray-scale gradient change about its sample point.
For the BF-SSIFT, we employ the original SIFT algorithm,
which first detects interest, or “salient” points, and thencomputes 128D SIFT feature at each of these interest points.
For the BF-DSIFT, we disable the interest point detector, andsampling positions are chosen randomly and densely. The
BF-SSIFT extracts ~1k SIFT features per 3D model, while
BF-DSIFT extracts about ~10k SFIT features per 3D model.
Quantize SIFT features into visual words: Encode a local
feature into a visual word drawn from a vocabulary of size
N v by using a pre-learned codebook. The codebook islearned, unsupervised, from tens of thousands of SIFT
features extracted from a set of models, e.g., the models inthe database to be retrieved. The encoding, or Vector
Quantization (VQ), is a closest point query in a highdimensional (e.g., 128D for SIFT feature) space. To speed up
the learning and encoding, the algorithm uses Extremely
Randomized Clustering Tree (ERC-Tree) by Guerts, et al [4].
Generate histogram: Visual words are accumulated into ahistogram having N v bins, which then becomes the feature
vector for a 3D model.
Compute distance: Dissimilarity among a pair of feature
vectors (the histograms) is computed. The distance may becomputed by using “fixed” distance metrics, such as
Kullback-Leibler Divergence (KLD) or L1-Norm, or by dataadaptive distance metric, e.g., by using the Manifold
Ranking (MR) algorithm by Zhou et al [15].

()

There are many possible methods to compute distance d xi , x jamong features xi and x j We compared the following three. Let.
n be the dimension of the vectors. Then, L1 norm d L1 xi , x j isdefined as follows.

(() ∑k xik − x jknd L1 xi , x j =)(1)

The second, Cosine distance d cos (xi , x j ) , gives angular cosine
distance between the two vectors;
d cos ( x i , x j ) = 1 −xi ⋅ x j(2)

xi ⋅ x j

Another distance is the Kullback-Leibler Divergence (KLD),
which is sometimes referred to as information divergence, or
relative entropy. It is known to work well for comparing
histograms. We used its symmetric version as follows;nd KLD ( xi , x j ) =xkj∑ ( x − x ) ln x
kj

i =1

ki

(3)

ki

Normally, distance among a pair of 3D models is the distanceamong their respective features computed by using one of the
distances above. In this paper, we employ the Manifold Ranking[15], with a modification discussed in Section 2.3, so that theresulting distance is adapted to the distribution of features in thefeature space. In experiments described in Section 3, we compareRyutarou Ohbuchi, Takahiko Furuya, Distance Metric Learning and Feature Combination for Shape-Based 3D Model Retrieval, poster
paper, Proceedings of the ACM workshop on 3D object retrieval 2010, Firenze, Italy, (2010).
the three distances above with their MR-treated versions for
retrieval performance.

2.1.2 Global Visual Feature
The global visual feature is called 1SIFT, and is based also on
Lowe’s SIFT. After rendering the 3D model from N r viewpoints,
as with the BF-DSIFT, the 1SIFT extracts only one SIFT feature(thus the name 1SIFT) at the center of each range image so that
the SIFT feature acts as a global feature per range image. The
VM-1SIFT does not employ the BoF approach, but uses a set of
N r SIFT features to describe a 3D model.
To compute distance among a pair of 3D models, the VM-1SIFT
compute distances among all the v × v pairs of SIFT features, andchoose the minimum of these distances as the overall distanceamong the 3D model pair. Let xip and x jq be the 1SIFT featuresfrom the view p and q of the 3D models Xi and X j , respectively.
Then the distance D ( x i , x j ) between models Xi and X j aredefined as below. Here, the distance d xip , y jq is one of the
Cosine, L1, or KLD distances shown above.

(

)

N
⎪⎧ i
⎪⎫
D ( x i , x j ) = ∑ min ⎨ ∑ d ( x ip , y jq ) ⎬
⎪
⎪⎭
p =1
⎩ q =1Ni(4)The VM-1SIFT performed surprisingly well for a database of
rigid shapes. As shown in Section 3.1, it performed better than the
LFD [1] for the PSB [9] database, for example.
Figure 2a and Figure 2b show examples of sampling patterns for arange image of the SSIFT and the DSIFT. Number of samples per
range image Np for the SSIFT is determined “automatically” by
the interest point detector of the SIFT algorithm. Np for the DSIFT,
on the other hand, is a user-defined parameter. Overall, we set the
numbers of features per 3D model to be 1.3k for the SSIFT and
13k for the DSIFT in the experiments below. Figure 2c shows an
obvious sampling pattern of the 1SIFT. The number of sample per
range image for the 1SIFT is, by definition, one.

(a) SSIFT, Np=38(b) DSIFT, Np=304(c) 1SIFT, Np=1

Figure 2. Sampling patterns of a range image for the BFSSIFT and BF-DSIFT.

2.2 Data-Adaptive Distance via Manifold
Ranking
Intuitively, the MR algorithm simulates “diffusion” of relevancevalue from a feature point (e.g., that of a query) on an irregularly
connected graph of high-dimensional features points (e.g., that of
all the 3D models in a database). The graph, or mesh, is typicallyformed by connecting a point to its k-nearest-neighbors. The
proximity used during mesh generation is determined by using a
distance measure, e.g., L1-norm, in the ambient feature space.
This distance metric affects the mesh topology. Each edge of thegraph is added with a weight computed from the distance among

the vertices of the edge. The weight represents “diffusion
coefficients” of the relevance value over the edges; the higher theweights, the more easily the relevance value diffuses. The
diffusion of relevance value happens on a graph from the source,i.e., a query.
The meshing step creates the affinity matrix W where Wij
indicates the similarity between feature points xi , and x j ;⎧⎛ d ( xi , x j ) ⎞⎪ exp ⎜⎜ −⎟⎟ if i ≠ j
Wij = ⎨σ⎝⎠⎪otherwise⎩ 0(5)Note that Wii = 0 since there is no ark connecting a point withitself. The matrix W is positive symmetric.
After the meshing, the algorithm forms a normalized graphLaplacian L ,
−

1

−

1

L = D 2 (D − W)D 2(6)

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 The ranking vector
TF = ⎡⎣ f1," , f n ⎤⎦ can then be estimated by iterating the following
until convergence;F(t +1) =1
1S( I − L ) F (t ) +
1+ μ
1+ μ

(7)

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* .

The MR algorithm iteratively diffuses the initial value of labelTsource vector S = ⎡⎣ s1,", sn ⎤⎦ , in which si = 1 corresponds to thequery. At the equilibrium, the higher the diffused relevance value
at a point, the higher the similarity rank of the point to the query.
As the diffusion occurs on the manifold via multiple paths,
similarity ranks thus computed are better than those computed
directly in the input feature space. The distance metric d ( xi , xi )used for forming the affinity matrix W affects diffusion of rank
values during the ranking process. If Wij is very low, due to avery high d ( xi , xi ) , the rank value won’t diffuse easily, possibly
impeding the ranking process.
Computational cost is an issue to be considered for applying MR.
MR is performed once per query, and cost of MR is dominated by
the cost of meshing and computing F* . The cost increases withthe size of matrix L , that is, the number of features n.

2.3 Distance Statistics and Manifold Ranking
While MR is known to work in various multimedia information
retrieval settings, our initial attempt in applying MR to the BFDSIFT and BF-1SIFT degraded their retrieval performances. On
the other hand, MR boosted the performance of the BF-SSIFT.
We investigated the cause, and found that the MR did not workfor certain distribution of distances. Figure 3 shows distance
distribution for the BF-SSIFT, the BF-DSIFT, and the VM-1SIFT,
computed by using the KLD. The profile is computed by using the
MSB, and is an average over all the queries.

Ryutarou Ohbuchi, Takahiko Furuya, Distance Metric Learning and Feature Combination for Shape-Based 3D Model Retrieval, poster
paper, Proceedings of the ACM workshop on 3D object retrieval 2010, Firenze, Italy, (2010).
In the figure, “Original” indicate the distances without the
proposed adjustment. The profile for the original BF-DSIFT
shows a very large jump in distance from the query (rank 0) to its
nearest neighbor (rank 1). As equation (5) for Wij indicates, sucha large distance from query to its nearest neighbor creates edges
having very low diffusion coefficients, preventing the diffusion of
relevance rank over the network of features. We thus devised a
simple empirical Distance Transformation (DT) to remove thejump, which is to simply subtract from all the distance values theamount of the jump prior to computing weights Wij . In Figure 3,
adjusted distance plots are indicated as “Adjusted”

500,000

A big jump.

We chose the vocabulary size (codebook size) Nv based on
preliminary experiments. The Nv used for the experiments arelisted in Table 1. For the BF-SSIFT, we used k-means clustering
for codebook learning, combined with a linear search for feature
encoding (i.e., vector quantization). This is feasible since thenumber of SIFT features per 3D model of 700~1,100 andvocabulary size Nv~1.2k are both moderate. Due to the use of kmeans clustering for codebook learning, the vocabulary sizes for
BF-SSIFT are rounded numbers. In comparison, the BF-DSIFT
generated, on average, about 13k SIFT features per 3D model.
The ERC-Tree vector quantizer used in the BF-DSIFT is arandomized algorithm, and its number of vocabulary Nv is notrounded. Vocabulary size Nv for BF-DSIFT is controlled
indirectly by a parameter. The MR has the regularization
parameter μ and the region of influence parameter σ . In thefollowing experiments, we varied μ and σ in the range
0.0025 ≤ μ ≤ 50.0 , and 0.01 ≤ σ ≤ 0.5 , respectively, and used thebest performing combination of the parameters.

Distance

00

Figure 4. Examples of 3D models from the Princeton ShapeBenchmark (PSB) (a) [9] and the McGill Shape Benchmark(MSB) (b) [14].
number of views Nr =42, and range images size 256 × 256 pixels.
Number of samples per range image for the BF-DSIFT is fixed at
Np=300. Vocabulary size Nv for the BF-SSIFT and BF-DSIFT
depends on visual complexity of the range images, and thus on thecomplexity and diversity of shapes in the 3D model database.

300,000
100,000(b) MSB

MSB database (KLD, average of all queries)

400,000
200,000(a) PSB

50

100

150
200
250
Rank
BF-SSIFT (Original)
BF-SSIFT (Adjusted)
BF-DSIFT (Original)
BF-DSIFT (Adjusted)
1SIFT (Original)検索件数
1SIFT (Adjusted)
Figure 3. Nearest neighbor is very far from the query forcertain (feature, distance metric) combination, e.g., (MSB
BF-DSIFT, Kullback-Leibler Divergence).

2.4 Multiple Feature Combination
To combine multiple features, we employ a simple late-fusion
approach, by computing linear combination of distances derived
from multiple features. Here, each distance may or may be theresult of Manifold Ranking.

3. EXPERIMENTS AND RESULTS
We performed the experiments using three benchmark databases:
the MSB [14] for highly articulated but less detailed shapes, thePSB [9] for a set of diverse and detailed shapes. Figure 4 shows
examples of 3D models from the two databases. The MSB
consists of 255 models in 10 classes. The MSB include sucharticulated shapes as “humans”, “octopuses”, “snakes”, “pliers”,
and “spiders”. The PSB contains two equal-sized subsets, thetraining set and test set, each consisting of 907 models and about
90 classes. For our evaluation, we used the PSB test set
partitioned into 92 classes. The PSB contains a more diverse set of
3D shapes than the MSB. To evaluated retrieval performanceusing the PSB, we used every model in the PSB test set of 907
models as queries to retrieve models in the test set. Similarly for
the MSB, all the models in the database are used as queries.
Same database is used for both visual codebook learning andretrieval experiments. That is, the codebook generated by using
the MSB database, for example, is used to query the MSB. We
used the training set size Nt = 50,000 of SIFT features extracted
from multi-view images of models in a database for training. For
both codebook learning and for retrieval, we used the following
set of parameters. We fixed, for the BF-SSIFT and BF-DSIFT, theAs the performance index, we used Recall-Precision plot and Rprecision. R-precision is a ratio, in percentile, of the models
retrieved from the desired class C k (i.e., the same class as thequery) in the top R retrievals, in which R is the size of the classCk .
Table 1. Vocabulary sizes used for the experiments.
Database
PSB
MSB

MethodBF-SSIFTBF-DSIFTBF-SSIFTBF-DSIFT

Vocabulary size
Nv
1,200
30,215900
31,770R-Precision
[%]
44.8
54.1
75.7
75.5

3.1 Distance Adjustment for the MR
This experiment evaluates effectiveness of the proposed Distance
Adjustment (DA) in improving MR. Table 2 and Table 3 compare
retrieval accuracies in R-Precision of five features, the BF-SSIFT,
BF-DSIFT, VM-1SIFT, SHD and SPRH. We used the executables
available online for the SHD and the SPRH. Table 2 and Table 3
show results for the PSB and MSB benchmarks, respectively. The
distance d ( x, y ) is computed using three methods, the KLD, L1norm, and Cosine distance (COS). Three rows for each featureare; (1) “None” for no MR, (2) “MR” for original MR, andRyutarou Ohbuchi, Takahiko Furuya, Distance Metric Learning and Feature Combination for Shape-Based 3D Model Retrieval, poster
paper, Proceedings of the ACM workshop on 3D object retrieval 2010, Firenze, Italy, (2010).
(3) “DA-MR” for MR with DA. For each table, “*” indicates thebest performer for the feature.
Without the DA, the MR is not effective for the BF-DSIFT and
the VM-1SIFT. However, with the DA, performances of the VM1SIFT and the BF-DSIFT improved significantly. For example,
MR with DA pushed the performance of the BF-DSIFT up to RPrecision=60.4% for rigid models (PSB), and R-Precision=90.7%
for articulated models (MSB). For some other features, such as the
BF-SSIFT and SPRH [12], the original MR (without DA) was
more or less effective. However, in some cases, the DA improved
efficacy of the MR for those features as well. For example, for the
MSB, the SPRH feature benefited more from the DA-MR than theoriginal MR. The SHD feature is an exception among those fivefeatures evaluated; the DA did not have clear influence on its
retrieval performance using MR.

Table 3. Manifold ranking and retrieval performance withand without Distance Adjustment (DA) (MSB database).

BF-SSIFTBF-DSIFTVM-1SIFT
SHD

Figure 5 and Figure 6 show recall-precision plots for the VM1SIFT, BF-SSIFT, and BF-DSIFT, each with and without the DAMR. For comparison, performances of the SHD and LFD features
without the MR (i.e., original features) are plotted.

SPRH

BF-SSIFTBF-DSIFTVM-1SIFT
SHD
SPRH

None
MR
DA-MR
None
MR
DA-MR
None
MR
DA-MR
None
MR
DA-MR
None
MR
DA-MR

1

0.6
0.4
0.2
0
0

0.2

0.4

RecallSHD
VM-1SIFTBF-DSIFT
MR-BF-SSIFT

0.6

0.8

1

LFD
BF-SSIFT
MR-VM-1SIFT
MR-BF-DSIFT

Figure 6. Recall-precision plot for the MSB database.

3.2 Feature Combinations
We tried several combinations of (1) bag of salient local visualfeature, (2) bag of dense and random local visual feature, and(3) global visual feature, to see if they improve retrieval
performance, and to see if they improve robustness of the retrieval
algorithm against the composition of databases. For various
combinations, Table 4 shows retrieval performances for the PSB,
and Table 5 shows the retrieval performances for the MSB. For
comparison, we included performance figures for the LFD [1] andthe Spherical Harmonics Descriptor [6].

0.8Precision

0.8
Precision

R-Precision [%]
KLD
L1
COS
44.8
33.6
42.3
48.0
46.9
44.2
* 50.3
*50.8
45.6
54.1
54.4
51.1
53.1
54.5
51.5
*60.4
59.3
55.8
50.9
44.2
42.2
44.4
48.1
49.2
*56.5
52.7
51.4
35.4
39.6
38.3
39.0
40.7
*42.0
38.8
*42.5
41.7
36.3
36.3
34.6
*39.4
38.1
36.6
*39.9
39.1
36.7

None
MR
DA-MR
None
MR
DA-MR
None
MR
DA-MR
None
MR
DA-MR
None
MR
DA-MR

1

Table 2. Manifold ranking and retrieval performance withand without Distance Adjustment (DA) (PSB database).

Algorithms

R-Precision [%]
KLD
L1
COS
75.7
64.6
70.3
84.4
78.2
79.9
*86.8
83.7
79.9
75.4
75.9
74.5
75.5
76.1
75.2
*90.7
88.4
84.7
48.2
43.3
41.7
42.7
47.2
46.0
*54.9
49.9
48.1
48.4
55.6
51.3
55.5
*61.6
58.5
54.7
*61.4
57.5
51.1
53.0
57.3
58.9
56.8
63.6
63.3
63.5
*65.2

Algorithms

0.6
0.4
0.2
0
0

0.2
SHD
VM-1SIFTBF-DSIFT
MR-BF-SSIFT

0.4

Recall

0.6

0.8
LFD
BF-SSIFT
MR-VM-1SIFT
MR-BF-DSIFT

Figure 5. Recall-precision plot for the PSB database.

1

For the rigid shapes of the PSB, the combination of VM-1SIFT
with BF-DSIFT performed the best, although the combination of
VM-1SIFT, BF-DSIFT, and BF-SSIFT performed about as well.
Note that the VM-1SIFT outperformed both LFD and SHD for the
PSB, an indication of the power of the SIFT. For the articulated
shapes of the MSB, as expected, combinations of two local
features, “BF-SSIFT + BF-DSIFT”, did the best. Note, however,that the combination “BF-SSIFT + BF-DSIFT + VM-1SIFT”
performed nearly as well. In another word, adding VM-1SIFT toRyutarou Ohbuchi, Takahiko Furuya, Distance Metric Learning and Feature Combination for Shape-Based 3D Model Retrieval, poster
paper, Proceedings of the ACM workshop on 3D object retrieval 2010, Firenze, Italy, (2010).
the mix of “BF-SSIFT + BF-DSIFT” did not hurt much. The
combination of all the three features, including the global one,may be a good bet for a database of an unknown composition.
Table 4. Feature combination and retrieval performancewith fixed and DA-MR distances (PSB benchmark).

Feature combinations
LFD (original)
SHD (original)
BF-SSIFTBF-DSIFTVM-1SIFTBF-SSIFT + BF-DSIFT
BF-SSIFT + VM-1SIFT
BF-DSIFT + VM-1SIFT
BF-SSIFT + BF-DSIFT + VM-1SIFT

Ranking method
Fixed
DA-MR
44.7
39.6
44.8
50.3
54.1
60.4
50.9
56.5
53.8
59.9
54.5
59.3
57.6
* 64.057.1* 63.6

Table 5. Feature combination and retrieval performancewith fixed and DA-MR distances (MSB benchmark).

Feature combinations
LFD (original)
SHD (original)
BF-SSIFTBF-DSIFTVM-1SIFTBF-SSIFT + BF-DSIFT
BF-SSIFT + VM-1SIFT
BF-DSIFT + VM-1SIFT
BF-SSIFT + BF-DSIFT + VM-1SIFT

Ranking method
Fixed
DA-MR
55.5
55.6
75.7
86.8
75.4
90.7
48.2
54.9
76.1
* 91.9
69.0
82.0
70.8
88.0
73.8
* 90.3

DSIFT, combination of features performed better on the PSB andabout equal for the MSB.

5. ACKNOWLEDGMENTS
The authors would like to thank those who carefully reviewed thepaper. This research has been funded in part by the Ministry of
Education, Culture, Sports, Sciences, and Technology of Japan(No. 18300068).

6. REFERENCES[1]

D-Y. Chen, X.-P. Tian, Y-T. Shen, M. Ouh-young, On
Visual Similarity Based 3D Model Retrieval, Computer
Graphics Forum, 22(3), 223-232, (2003).

[2]

G. Csurka, C.R. Dance, L. Fan, J. Willamowski, C. Bray,
Visual Categorization with Bags of Keypoints, Proc.
ECCV ’04 workshop on Statistical Learning in Computer
Vision, 59-74, (2004).

[3]

T. Furuya, R. Ohbuchi, Dense sampling and fast encoding for
3D model retrieval using bag-of-visual features, Proc. ACM
CIVR 2009, (2009).

[4]

P. Guerts, D. Ernst, L. Wehenkel, Extremely randomized
trees, Machine Learning, 2006, 36(1), 3-42, (2006).

[5]

M. Iyer, S. Jayanti, K. Lou, Y. Kalyanaraman, K. Ramani,
Three Dimensional Shape Searching: State-of-the-art Review
and Future Trends, CAD, 5(15), 509-530, (2005).

[6]

M. Kazhdan, T. Funkhouser, S. Rusinkiewicz, Rotation
Invariant Spherical Harmonics Representation of 3D Shape
Descriptors, Proc. Symposium of Geometry Processing(SGP) 2003, 167-175 (2003).

[7]

D.G. Lowe, Distinctive Image Features from Scale-Invariant
Keypoints, Int’l Journal of Computer Vision, 60(2), (2004).

[8]

R. Ohbuchi, K. Osada, T. Furuya, T. Banno, Salient local
visual features for shape-based 3D model retrieval, Proc.
SMI ‘08, 93-102, (2008).

[9]

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

4. SUMMARY AND CONCLUSION
In this paper, we presented a 3D model retrieval algorithm thatcombines the BF-DSIFT algorithm [3] with a data-adaptive
distance computation using the Manifold Ranking (MR) [15]. In
doing so, we discovered that distance distribution produced by the
BF-DSIFT made the MR less effective. We thus proposed anempirical remedy called Distance Adjustment (DA) to be appliedprior to the MR. Our experimental evaluation showed that the DA
does improve efficacy of the MR for certain features. The original
MR was not effective at all if applied directly to BF-DSIFT
features. However, the MR with DA was effective for suchfeatures. With the DA-MR, for example, the retrieval performanceof the BF-DSIFT for the articulated models of the McGill ShapeBenchmark [14] improved from 76% to 91% in R-Precision.
We had successfully employed the BF-DSIFT with DA-MR toenter the SHREC 2010 tracks on “Non-rigid shapes” and “Generic
3D Warehouse” for the 1st place and the 1st place tie, respectively.
Using the DA-MR BF-DSIFT, a query for the SHREC 2010
Generic Warehouse is processed in about 2s, including the multiview rendering, SIFT feature extraction, BoF integration, and DAMR based ranking of the entire models in the database.
We also evaluated retrieval performances of combinations of local
and global features. We found that combination of distances
generated by three different features do improve robustness of theretrieval algorithm against composition of databases, with almost
negligible impact on retrieval performance. Compared to themethod we used for the SHREC 2010 tracks, the DA-MR BF-[10] J. Sivic, A. Zisserman, Video Google: A text retrieval

approach to object matching in Videos, Proc. ICCV 2003,
Vol. 2, 1470-1477, (2003).
[11] J.W.H. Tangelder, R. C. Veltkamp: A survey of content

based 3D shape retrieval methods. Multimedia Tools andApplications. 39(3), 441-471 (2008).
[12] E. Wahl, U. Hillenbrand, G. Hirzinger, Surflet-Pair-Relation

Histograms: A Statistical 3D-Shape Representation for Rapid
Classification, Proc. 3DIM 2003, 474-481, (2003).
[13] J. Winn, A. Criminisi, T. Minka, Object categorization bylearned universal visual dictionary, Proc. ICCV05, Vol. II,
1800-1807, (2005).
[14] J. Zhang, R. Kaplow, R. Chen, K. Siddiqi, The McGill ShapeBenchmark (2005).
http://www.cim.mcgill.ca/shape/benchMark/[15] D. Zhou, O. Bousquet, T.N. Lal, J. Weston, B. Schölkopf,

Learning with Local and Global Consistency, Proc. NIPS
2003 (2003).