Ryutarou Ohbuchi, Jun Kobayashi, Unsupervised Learning from a Corpus for Shape-Based 3D Model Retrieval, accepted, ACM MIR 2006,
Santa Barbara, CA, U.S.A., Oct. 2006

Unsupervised Learning from a Corpus
for Shape-Based 3D Model Retrieval
Ryutarou Ohbuchi

Jun Kobayashi

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

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

ohbuchi at yamanashi dot ac dot jp

g05mk014 at ccn dot yamanashi dot ac dot jp

ABSTRACT

1. INTRODUCTION

Arguably the most important issues in shape-based 3D model
retrieval are methods to extract powerful yet compact shapefeatures and methods to properly and promptly compare the shapefeatures. In this paper, we explore a method to improve feature
distance computation by employing unsupervised learning of thesubspace of 3D shape features from a corpus. We employ analgorithm called Laplacian Eigenmaps proposed by Belkin, et al.
to learn a manifold spanned by shape features of 3D models in the
corpus. The learned manifold is approximated by an RBF network,
onto which shape features are projected. Distances among shapefeatures can then be computed effectively on the learned manifold.
We combine this learning-based distance-computation methodwith a method to extract multiresolution shape features proposedby Ohbuchi, et al. Our experimental evaluation showed that the
proposed method could significantly improve retrieval
performance. Learning alone improved performance of two shapefeatures we tried by about 5%. A combination of learning andmultiresolution shape feature allowed about 10% gain in
performance. As an example, the trained, multiresolution versionof the SPRH gained 10% over the original single resolution,
untrained SPRH shape feature.

An increased popularity of 3D models, from games on
cellular phones to CAD models for automobile parts, has
prompted research into effective reuse of 3D models throughshape-based retrieval of 3D models [25, 13]. While a number ofshape comparison methods have been proposed, the retrieval
performance has not been satisfactory. There are many possible
reasons for this. For one, the shape feature may be inadequate; thefeature might not capture shape features that are relevant. Or, it
could be the inadequacy of similarity, or dissimilarity (distance)computation method. Even if the feature contains salient
information, the shape dissimilarity measure may not be using it
effectively. Added factors are both inter-personal and intrapersonal variability of shape similarity criteria. My shapesimilarity judgment may be different from yours. Or, myjudgment today may be different from that of yesterday.
In this paper, we explore a method to improve distancecomputation among shape feature vectors. Given a set of ndimensional feature vectors (points in \ n ), we assume that thefeature vectors spans a m-dimensional ( m ≤ n ) non-linear
subspace of the \ n . We employ unsupervised learning toestimate the non-linear subspace. Specifically, we use theLaplacian Eigenmaps proposed by Belkin, et al [3] for thelearning. Once such a subspace could be learned, n-dimensionalfeature vectors of 3D models could be projected onto the subspace
so that a distance among a pair of feature vectors can becomputed as a geodesic on the subspace. Our experimental
evaluation showed that learning from a corpus of 3D shapemodels does improve retrieval performance. Retrieval
performances of both AAD [19] and SPRH [28] shape features,
measured in R-precision, increased by more than 5% by learningfrom a 4,000 model 3D model corpus. A combination ofmultiresolution shape feature extraction approach by Ohbuchi etal [18] and the learning produced about 10% increase inperformance compared to the original (single-resolution) shapefeatures. As an example, the trained, multiresolution (MR)version of the SPRH surpassed the performance of the Light Field
Descriptor by Chen et al. [7].

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. I.4.8 [Scene Analysis]: Object
recognition. I.2.6 [Learning]: Induction.

General Terms
Algorithms, Performance, Experimentation, Measurement.

Keywords
Shape-based 3D model retrieval, content-based retrieval, manifold
learning.
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.
MIR'06, October 26–27, 2006, Santa Barbara, California, USA.
Copyright 2006 ACM 1-59593-495-2/06/0010...$5.00.

This paper is organized as follows. In the following section,
we will review learning applied to shape-based retrieval of 3Dmodels. We will describe, in Section 3, our retrieval algorithm
based on manifold learning and multiresolution shape features.

1

Ryutarou Ohbuchi, Jun Kobayashi, Unsupervised Learning from a Corpus for Shape-Based 3D Model Retrieval, accepted, ACM MIR 2006,
Santa Barbara, CA, U.S.A., Oct. 2006
Experiments and their results are described in Section 4, followed,
in Section 5, by conclusion and future work.

is essentially He’s method applied to shape-based 3D model
retrieval with some modifications.

2. PREVIOUS WORK

3. METHOD

Learning based approach to similarity retrieval can beclassified into on-line learning and off-line learning. The on-line
learning approach tries to learn human intentions interactively,e.g., through iterative relevance feedback or by interactive
grouping of examples. An advantage of this approach is its
capability to adapt to personal preference or even to changes inpersonal preference over time or occasion. The off-line learning
approach learns from a prescribed training database prior to actual
retrieval. The learning may be unsupervised to learn the structureof subspace on which the measured features exist. Or, the learning
may be supervised, e.g., by using a pre-categorized database.

Basic approach is similar to the 2D image retrieval proposed
by He, et al. in [11]. He’s method learns the manifold of 2D
image features in the training set by using the Laplacian
Eigenmaps (LE) by Belkin, et al. [3] and approximate the
manifold by using a Radial Basis Function (RBF) network. We
combine this learning based framework for similarity comparison
with a multiresolution approach to feature extraction for 3Dmodels proposed by Ohbuchi, et al. [18], and add a databasesubsampling step to contain computational cost.
We first describe the method for a single resolution shapefeature. We then extend the approach to deal with multiresolution
shape features in Section 3.5. The proposed method (using asingle resolution shape feature) can be divided into two phases;
the learning phase and the retrieval phase (See Figure 1). Each
phase consists of the following steps:

Relatively small number of work exploiting learning has so
far been published for shape-based 3D model retrieval. Interactive
relevance feedback, a form of on-line interactive learning, hasbeen explored by several researchers for 3D model retreival [9, 1,
14, 16]. Elad et al. is among the first to apply Support Vector
Machines (SVM) learning in an on-line learning setting to
improve 3D model retrieval [8]. Leifman et al. [14] performed
Kernel Principal Component Analysis (Kernel PCA) for an
unsupervised learning of a feature subspace before applying a
relevance feedback technique that employs Biased Discriminant
Analysis (BDA) or Linear Discriminant Analysis (LDA) on thelearned subspace. Novotni et al. [16] compared several learning
methods, SVM, BDA, and Kernel-BDA, for their retrieval
performance in a relevance feedback setting. Unlike relevance
feedback, unsupervised off-line learning has seen very little
attention in 3D model retrieval. The Kernel-PCA employed by
Leifman et al. [14] is an example. The purity proposed by Bustos
et al. [5] can also be considered as a weak form of unsupervised
off-line learning. Purity is an estimate of the performance of ashape descriptor determined by using a pre-classified training
database. Bustos used the purity to weight distance obtained frommultiple shape descriptors.

The learning phase:(1) Extract shape feature vector: Extract n-dimensional feature
vectors from the K models in the training database (i.e.,
corpus).
(2) Select training samples: To reduce computational costs,
subsample the training set down to L ( L ≤ K ) features
vectors.
(3) Learn manifold: Perform unsupervised learning of the mmanifold ( m ≤ n ) spanned by the n-dimensional training
samples by using Laplacian Eigenmaps by Belkin, et al. [3].
(4) Approximate the manifold: Construct a continuous
approximation g of the manifold by using the RBF network[5].
(5) Project features of the models in the database: Projectfeatures of all the models in the database onto the mmanifold using the approximation, and store the results
together with the corresponding 3D models.

Classical methods for unsupervised learning of subspace
includes PCA and MDS, both of which are quite effective if thefeature points lie on or near a linear subspace of the input space.
However, if the subspace is non-linear, these methods do notwork well. Many non-linear methods have been proposed for
unsupervised learning of subspace; Self-Organizing Map (SOM)
and Kernel-PCA are some of the well-known examples [10].
Recently, a class of geometrically inspired non-linear methods,
called “manifold learning” has been proposed for learning the mmanifold of measured feature vectors. Some of the examples ofmanifold learning algorithms are Isomap [26], Locally Linear
Embedding (LLE) [23], and Laplacian Eigenmaps (LE) [3].
Manifold learning has been applied to many problems, including
motion analysis, multimedia data retrieval [11], and others. A
property (drawback) of LE, LLE, and Isomap is that these
mapping are defined only for the feature vectors in the training set.
To query a 3D model outside of the training set, however, itsfeature vector must have an image on the manifold. In a 2D image
retrieval setting, He et al [11] solved this problem by using Radial
Basis Function (RBF) network [6, 10] for a continuous
approximation of the manifold. The work presented in this paper

The retrieval phase:(1) Extract shape feature vector: Extract an n-dimensionalfeature vector from the query model.
(2) Map the feature onto the manifold: Map the n-dimensionalfeature vector onto the approximated m-manifold g .
(3) Compute distance on the manifold: Compute distancesfrom the query model to all the models in the database on g .
(4) Retrieve and present the top p matches: Retrieve themodels in the database having the p-smallest distances fromthe query model.

3.1 Shape feature
For the experiments, we chose the AAD by Ohbuchi et al.
[19] and the SPRH by Wahl, et al. [28] as the basic shape features
for the experiments described in this paper. We call these singleresolution (SR) versions of the feature SR-AAD and SR-SPRH,
respectively. (Multiresolution shape features and their integration
with the learning framework will be described in Section 3.4.)
Both AAD and SPRH are global shape features that are
inherently invariant to rigid body transformation. They are2

Ryutarou Ohbuchi, Jun Kobayashi, Unsupervised Learning from a Corpus for Shape-Based 3D Model Retrieval, accepted, ACM MIR 2006,
Santa Barbara, CA, U.S.A., Oct. 2006
extensions of the D2 by Osada et al. [21]. The D2 is a 1D
histogram of a distance computed between a pair of points
generated at random locations on the surface of the 3D models to
be compared. The AAD is a 2D joint histogram of a distance andan angle formed by the normal orientations of a pair of points,
while the SPRH is a 4D joint histogram of three angles and a
distance. Any shape feature can be used in the proposed learning
framework provided that the feature produce feature vector.
Some shape comparison methods do not produce feature vectors,
and thus the proposed learning framework can’t be applied. For
example, the LFD [6], which involves combinatorial method tofind a distance among a pair of models, can’t be used with theproposed learning approach.

Learning phase
K models

distribution by concentrating samples at points that are wellspaced yet farthest from each other.

3.3 Manifold learning and approximation
Belkin’s LE performs estimation of an m-manifold byfollowing the steps below;(1) Construct an adjacency graph: A feature vector of a modelin the training database is a point in the n-dimensionalfeature space U = \ n . Construct an mesh G by connecting
k-nearest points using Euclidian distance in U.
(2) Create mesh Laplacian matrix for G : Create a mesh
Laplacian matrix L = D − W , in which W is an adjacency
matrix for G ,⎧1, if vertices i and j are adjacent;wij = ⎨
otherwise.
⎩0,

Retrieval phase
Query modeland D is the diagonal matrix satisfying the following
equation.

3D modeldatabaseDii =K models

Featureextraction

Featureextraction

K features

Select training
samplesL ≤ K features

Learn
manifold g

Map the feature
onto gm-D

Computedistanceg

m-D

distance

Approximate g
by RBF network
n-D

Retrievalm-Dfeatures

…

m-D

m-D
featuresjiNote that g is defined only for the points in the training set.
To project a feature vector (e.g, a query) not in the training
samples onto g, He et al. [11] approximated g by using RBF
network. We used an implementation of Chen’s RBF algorithm[6] included in the Neural Network Toolkit of the MatLab for theapproximation.

3D modeldatabaseg

Map features
onto gj(3) Perform an Eigenanalysis of L : Find eigenvalues λi(1 ≤ i ≤ n) and eigenvectors fi (1 ≤ i ≤ n) of L by solving
the generalized eigenproblem Lf = λ Df .
(4) Find a manifold g: Sort eigenvectors in an ascending order.
The least m eigenvectors (but excluding the first eigenvectorf0 ) defines mapping ϕ : x i → ( f1 (i ),..., fm (i ) ) that maps apoint xi ∈ U = \ n onto m-manifold g.

Approx’dmanifold g

n-D

∑w

3.4 Distance computationgWe used Cosine distance for distance computations, for bothlearned and not-learned versions of the AAD and SPRH shapefeatures. Cosine distance is computed simply as the inner productof a pair of normalized feature vectors. In addition, forcomparison, we used Kullback-Leibler divergence (KLD) [28] tocompute distance for the SPRH shape feature without learning.

Approx’dmanifold g

g : Mapping from n-D feature vector to m-D feature vector, defined
only at samples learned.
g : Approximate, continuous mapping from n-D feature vector to m-Dfeature vector.

Cosine distance was selected from four distance measures,
L1, L2, Cosine, and KLD, after experimental evaluation of theirperformances.

Figure 1. The learning phase (left) and the retrieval phase (right)of the proposed method.

In the case of AAD, our experiment showed that the Cosine
distance and KLD performed identically, outperforming both L1
norm and L2 norm. (The original paper [19] uses L2 norm.)

3.2 Training sample selection
Learning a manifold by using LE could be expensive both intime and in space. A naïve method for the eigendecomposition
used for the LE costs O ( n2 ) space and O ( n3 ) time. The RBF
network regression also costs significant amount of spatial andtemporal computational costs. To reduce these costs, we tried toestimate an approximate manifold by using a sampled subset ofthe corpus. We tried several subsampling methods, namely:(1) Pseudo-random sequence in C++ library, (2) Sobol’s quasirandom sequence [22], (3) Niederreiter’s quasi-random sequence[4], and (4) Max-min approach proposed by Liu, et al. [15]. In
Monte-Carlo methods, quasi-random sequences are known to
reduce variance. The max-min approach by Liu, et al try toquickly approximate the “outermost shape” of the feature point

In the case of SPRH, the Wahl et al. used KLD [28], and that
the KLD outperformed three other distance measures weexperimented. (See Table 1 for the comparison among KLD and
Cosine distance.) However, KLD can’t be used if a feature vector
contains negative values, which is the case for learned feature
vectors. We thus used the second best, the Cosine distance, for the
SPRH in all the experiments that follows. For comparison, we
included the results for SPRH using KLD for the cases without
learning.

3

Ryutarou Ohbuchi, Jun Kobayashi, Unsupervised Learning from a Corpus for Shape-Based 3D Model Retrieval, accepted, ACM MIR 2006,
Santa Barbara, CA, U.S.A., Oct. 2006
Distances of a pair of MR-shape features are combined using
a fixed weight linear combination. In the experiments described inthis paper, the weights are fixed at 1.0 across the resolution levels.

Table 1. Distance measure and performance of the SPRH.
FeatureSR-SPRH

DistancemeasureKLD
Cosine

RP

11A
37.4
35.6

In the following, a single resolution shape features are
prefixed with “SR”, and a multiresolution shape features are
prefixed with “MR”. Also, learned shape feature are prefixed with“L”. In addition, postfix “C” or “K” may accompany theseacronyms indicating distance computation methods; “C” for
Cosine distance or “K” for KLD. Thus, for example, “SR-SPRHK” stands for the “single-resolution SPRH using KLD”, while “LMR-AAD-C” stands for the “learned multi-resolution AAD using
Cosine distance”.

40.1
38.4

3.5 Exploiting multiresolution shape features
The multiresolution (MR) feature extraction method
proposed by Ohbuchi et al. [18, 20] is known to improve
performance of some of the shape comparison methods. The
multiresolution approach may be able to extract more shapefeature from a model. Also, the multiresolution approach may
conform better to the human perception and/or cognition incomparing 3D shapes. The approach by Ohbuchi et al. firstcreates a set of 3D MR shape features. Once a set of MR models
is obtained, appropriate (single resolution) shape feature iscomputed at each of the multiple resolution levels to produce a setof multi-resolution shape feature vectors. An advantage of thismultiresolution (MR) representation is that it can be computed forpolygon soup models or even for point set models (by skipping
the step 1 below.) Briefly, the method computes a set of
multiresolution shape feature as below (see Figure 2);

Original model

α values αι at level(surface-based)

i computed basedon the diameter ofthe model.

Generate point-set
Point set model

Level 6 model= original

Compute α-shapes(1) Compute a multiresolution representation: The surfacebased input model is converted into a point-based model byMonte-Carlo sampling of the surfaces of the model. A set of
L-1 scale values αι, i=1…L-1 is computed based on the sizeof the model. The set of scale values are used to normalize
size among shape models. Then, compute L-1 3D alphashapes from the point set model by using the L-1 scale values
αι. Of L resolution levels, coarser (L-1) levels are computedby using the 3D alpha shapes [8]. The finest resolution level
L uses the original polygon soup model.

Level =1

2

3

4

5

6

MR representation (L=6)

MR-x shape-descriptor

Figure 2. Computing a MR-x multiresolution shape feature set.
(This example shows 2D histogram of the AAD [19] shapefeature x.)(2) Compute multiresolution shape feature set: Apply a shapefeature extraction method x to a model at each resolution
level of the MR, creating a set of multiresolution shapefeatures MR-x.
Figure 3 shows an example of the MR representation for asurface-based 3D model of a biplane.

Original model.

Given the MR representation, learning based approachdescribed above can be applied in two different ways.
(1) Learning features at each resolution level: In the learning
phase, learn a manifold at each of the L-level MR
representation. In the retrieval phase, a distance is calculated
at each of the L levels of MR representation. Then L distancevalues are combined into a single overall distance.
Combination can be performed, for example, by using fixedweight linear-combination or by using purity [5].
(2) Learning features as a multiresolution feature set:
Concatenate L feature vectors from the L resolution levels
into a big feature vector, and learn a manifold from theconcatenated vector. Distance among a pair of models is
computed using the learned manifold.

Point sampled model(2,048points)

Level 1(α1)

Level 2(α2)

Level 3(α3)

Level 4(α4)

Level 5(α5)

Level 6(≅orig.)

Figure 3. An example of MR representation for the surface-basedmodel of a biplane. A feature per level is computed for the set forshape comparison.

In the experiments described in this paper, we chose to apply
the former approach. Principal reason for this choice is the highcomputational and spatial cost of the latter approach.

4

Ryutarou Ohbuchi, Jun Kobayashi, Unsupervised Learning from a Corpus for Shape-Based 3D Model Retrieval, accepted, ACM MIR 2006,
Santa Barbara, CA, U.S.A., Oct. 2006
best, closely followed by the pseudo-random number sequence.
The performance difference between the Niederreiter’s sequenceand the Sobol’s sequence was negligible. Note that we used thedefault parameters for the Niederreiter’s sequence [4], whose
results might have been different if we were to use a different setof parameters. In the experiments that follow, we will use the
Niederreiter’s sequence for subsampling unless otherwise stated.

4. EXPERIMENTS AND RESULTS
We implemented the learning algorithm in Matlab (Release12.1). Others, such as, feature extraction, distance computation,
retrieval and results evaluation are implemented in C++.
We use 3D model databases for two purposes;(1) unsupervised learning, and (2) performance evaluation. For
learning, we used the union of the training set of the Princeton
Shape Benchmark (PSB) [24] database containing 907 models andthe National Taiwan University 3D Model Database (NTU) ver. 1[17] containing 10,911 models. As our method uses unlabeled
samples for learning, we ignored the category attached to the PSB
training set. (The NTU database does not have any category orlabeling.) We sampled the union, containing 11,818 models byusing one of the four sampling strategies described in Section 3.2.
For evaluation, we used the test set of the PSB that contains 907
models classified into 92 “base” categories. We used thiscategorization as the ground truth for the following experiments.
For the performance evaluation, we picked a model from the test
database of size K as the query, and ranked all the other (K-1)
models in an ascending order of the distance computed.

30

20

2000

1500

As quantitative measures of performance, we used Rprecision (RP) and 11 point average precision (11P) figures andthe precision-recall plot [2]. The R-precision is the ratio, in
percentile, of the models retrieved from the desired class Ck (i.e.,the same class as the query) in the top R retrievals, in which R is
the size of the class Ck . In computing the R-precision, we did
not count the query q among the retrieved model, i.e., thenumerator, which is divided by Ck − 1 . (Note that RP is similar
but different from the First Tier used in the SHREC 2006
benchmark [27].) The 11-point average 11A is the average ofprecision values taken at 11 equally spaced recall values {0.0, 0.1,
0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0}. An 11P average precision
value can be considered as a summary of a recall-precision plot,
which emphasizes overall performance. The RP and 11P values
presented below are a mean over all the K=907 queries. As areference of performance, we included the performance figure
obtained by using Light Field Descriptor (LFD) by Chen, et al.
[7] in some of the results.

1000

500

10

4000

Pseudo random
Max-MinNiederreiter
Sobol
SR-AAD Cosine.
2500

R-precision40

Number of learned models(a) R-precision (RP) values for the SR-AAD feature by using four
subsampling schemes. Dotted line shows the RP value for theoriginal SR-AAD feature.

30

20

2000

1500

500

1000

10

Several parameters of the LE and the RBF need to be fixed.
We performed some preliminary experiments to determine thenumber of neighborhood k for the mesh construction and the
spread σ of the RBF (a Gaussian function) for the RBF network
approximation. For the SR-AAD and MR-AAD, we chosek = 12 and σ = 0.6 , after experiments that varied k in the range[8, 20] and σ in the range [0.4, 1.0]. For the SR-SPRH and MRSPRH, we chose k = 40 and σ = 1.2 , after experiments thatvaried k in the range [12, 50] and σ in the range [0.2, 1.4].

4000

Pseudo random
Max-MinNiederreiter
Sobol
SR-SPRH-KLD
SR-SPRH-Cosine
2500

R-precision40

Number of learned models(b) R-precision (RP) values for the SR-SPRH shape feature
obtained by using four subsampling schemes. Dotted line shows
the RP value for the original SPRH shape feature (i.e., SR-SPRHKLD), and the broken line shows the RP value for the SR-SPRH
using Cosine distance.

Figure 4. Database subsampling schemes and performance. For
AAD (a) and for SPRH (b), plots of R-precision at different
number of training samples L are shown for four subsampling
schemes.

4.1 Sub-sampling methods and performance
We compared four sub-sampling schemes for their retrieval
performance by varying the number of learned samples. The
experiment was done by using the SR-AAD and SR-SPRH shapefeatures.
Figure 4 shows the results. While the Max-Min farthest point
sampling scheme [15] performs the best at a fewer number ofsamples (e.g., 500~1000 samples), other sampling schemes
produce better results with a larger number of samples (>1500
samples). At the largest number of training samples tested, theNiederreiter’s sequence and the Sobol’s sequence performed the

4.2 Manifold dimension vs. retrieval
performance
We performed experiments to determine the relationshipbetween the dimension m of the manifold and the retrieval
performance. The original SR-AAD feature has 256 dimensions[19] and the original SR-SPRH has 625 dimensions [28].

5Ryutarou Ohbuchi, Jun Kobayashi, Unsupervised Learning from a Corpus for Shape-Based 3D Model Retrieval, accepted, ACM MIR 2006,
Santa Barbara, CA, U.S.A., Oct. 2006

Based on the experiment, dimensions of manifold m for eachshape feature to be used for the experiments in Section 4.3 were
picked. When in doubt, we tried err on the side of having moredimension, disregarding computational costs. For L-SR-AAD andfor each resolution level of L-MR-AAD, m=220 (< n=256) is used.
For L-SR-SPRH and for each resolution level of L-MR-SPRH (ateach resolution level), m=500 (< n=625) is used. (While theassessment based only on Figure 4(b) suggests the dimension of
about 200 for the SR-SPRH, other figures such as 11Pwere taken
into consideration.)

Figure 5 shows, for SR-AAD and SR-SPRH, changes inretrieval performance due to the number of dimension m of the
manifold. In the case of the AAD, the retrieval performance of the
trained version (L-SR-AAD-C) increased with the number ofdimensions. The performance of the trained version (solid linewith markers) surpasses that of the original at about m=40, a
dimension significantly smaller than the original 256. In otherwords, for SR-AAD-C, m=40 or 1/5 of the size of original vector,
is sufficient to achieve the performance level equal or better thanthe original. In the case of the SPRH, the performance of thelearned version L-SR-SPRH-C (using Cosine distance) topped out
at about 200 dimensions. Compared to the untrained originalusing KLD (SR-SPRH-K), the trained version is only marginallybetter at about m>200. If compared to the untrained SPRH using
Cosine distance (SR-SPRH-C), however, the trained version
performed significantly better. Interestingly, as we will discuss in
Section 4.3, L-MR-SPRH-C, the learned MR-version of the
SPRH using Cosine distance behaves differently; it somehow
achieves significant performance gain of about 5% over theuntrained MR-SPRH-K using KLD.

4.3 Number of samples vs. retrieval
performance
Figure 6 shows the change in retrieval performance due tolearning for the SR-AAD, MR-AAD, SR-SPRH, and MR-SPRH
shape features. Table 2 shows a summary of performance
evaluation results. Overall, the manifold learning increased theperformance by about 5%, and the multiresolution method added
another 5%, for an overall increase of about 10% for both AAD
and SPRH. As a result of the combined improvement, theperformance of the SPRH measured in RP increased from 37.4%
to 47.7%, surpassing that of our benchmark Light Field
Descriptor [7].

In terms of dimension reduction, the method could not findclear low-dimensional manifold, in both SR-AAD and SR-SPRH
features. This is not very surprising, as 3D shapes most likely
won’t have a clear low-dimensional manifold of fixed dimension.
(As opposed to, for example, human animation data constrained
physically by skeletal structure, etc.)

Notice in Figure 6 that the performances of every shapefeature drop well below the original (i.e., untrained) versions.
This can be explained as follows; the manifold estimated using asmall number of samples are so warped that the distancecomputation suffered, compared even to the original space. As thenumber of samples increase, the learning captures the shape of the
manifold enough to produce equal or better results. Please note
that, considering the number of dimensions for the features,training samples size L is very small. Consider the SR-AAD
feature having 256 dimensions. A set of 256 uniformly distributed
samples means, on average, only one sample are taken perdimension.

R-precision

40

35

L-SR-AAD
Orig. SR-AAD

30
20

40

60 100 140 180
Manifold dimension

220

In both Table 2 and Figure 6, the numbers of learned models
are limited to either 4000 or 5000 in spite of the corpus size of
11,818. This limitation is due to the large memory consumptionof the RBF network regression algorithm we used, and also to thememory limitation of the MatLab we used.

255(a) Trained L-SR-AAD feature (solid line) and the original AAD
without learning (broken line).

40
R-precision

Table 2. A summary of retrieval performance showing the effectof learning..

(b) Trained L-SR-SPRH-C feature using Cosine distance (solidline) and the original SPRH using both KLD (SR-SPRH-K) and
Cosine distance (SR-SPRH-C).

Base MR/
FeatureTrain?
feature SR
name
No
SR-AADSR
Yes
L-SR-AAD
AAD
No
MR-AADMR
Yes L-MR-AAD
No SR-SPRH-K
SR
No SR-SPRH-C
SPRH
Yes L-SR-SPRH
No
MR-SPRHMR
Yes L-MR-SPRH
LFD-

Figure 5. Dimensionality of feature vectors after dimension
reduction vs. retrieval performance measured in RP figure [%].

SR: Single Resolution
L: Number of training samples.

35
L-SR-SPRH-C
Orig.SR-SPRH-K
Orig.SR-SPRH-C

30
25

50

100 200 300 400
Manifold dimension

500

600

6

L

4000
4000
5000
5000
-

RP
[%]
33.5
37.1
40.3
43.9
37.4
35.6
37.8
42.5
47.5
45.9

MR: Multi Resolution

11P
[%]
36.3
39.5
43.9
46.8
40.1
38.4
38.7
45.7
50.1
49.3

60

60

50

50

40

40

30

Learned 1R
Learned 11A
Orig. 1R
Orig. 11A

20

40

40

30
Learned 1R
Learned 11A
Orig. 1R
Orig. 11A

Learned 1R
Learned 11A
Orig. 1R
Orig. 11A

20(c) Number of learned models and the performance for the MRAAD shape descriptor.

2500

2000

1500

1000

500

10

4000

2000

1500

1000

500

30

Number of learned models

5000

50

4000

50

precision

60

2500

precision

60

Number of learned models

2500(b) Number of learned models and retrieval performance for the
SR-SPRH shape descriptor.

(a) Number of learned models and retrieval performance for the
SR-AAD shape descriptor.

10

2000

500

4000

2500

2000

1500

1000

Number of learned models

Number of learned models

20

1500

10

10
500

Learned 1R
Learned 11A
Orig. 1R
Orig. 11A
1000

20

30

4000

precision

precision

Ryutarou Ohbuchi, Jun Kobayashi, Unsupervised Learning from a Corpus for Shape-Based 3D Model Retrieval, accepted, ACM MIR 2006,
Santa Barbara, CA, U.S.A., Oct. 2006(d) Number of learned models and the performance for the MRSPRH shape descriptor.

Figure 6. Size of the learned models L vs. retrieval performance for the four shape features. All the training sets are sampled by using
Niederreiter’s sequence.
“relevant” results, indicating models that are close to the models
in the correct category.

4.4 Retrieval example
Figure 7 shows examples of retrieval by using the model of
an office chair (#801) in the PSB test set as a query. The model
belongs to the category that contains total of 20 models.

It can be seen that both unsupervised learning (L-) andmultiresolution shape feature extraction (MR-) produced
performance gain. The combination of the two approaches (LMR-xxx) produced the best results for both AAD and SPRH shapefeatures. For the MR feature extraction, the untrained(multiresolution) MR-AAD (Figure 7(e)) retrieved 10 out of 20
office chair models in the top 19 retrievals, compared to 8 models
for the untrained (single resolution) SR-AAD (Figure 7(a)).
Unsupervised learning improved performance as well; those withlearning (on the right hand side of the Figure 7) performed better
than their counterparts without learning (on the left hand side of
the Figure 7.). For example, trained L-MR-SPRH retrieved 12 out
of 20 office chair models (Figure 7(h)), compared to only 8 office

The interface displays the query model at the top left corner,in addition to the 20 retrieval results in the 4-rows by 5-columns
matrix format. The top left position of the 4 by 5 matrix displays
the best match, which is almost always the query itself. (Note that,some shape comparison method might return a model other thanitself as the top match.) Thus, up to 19 “true” retrieval results canbe displayed in this “first page”. In the image, those in the correct
category (office chair) are marked by solid rectangle, indicating“highly relevant”, results. Those marked by broken line are7

Ryutarou Ohbuchi, Jun Kobayashi, Unsupervised Learning from a Corpus for Shape-Based 3D Model Retrieval, accepted, ACM MIR 2006,
Santa Barbara, CA, U.S.A., Oct. 2006
chair models for the untrained MR-SPRH (Figure 7(g)). Noticealso that the relevant results (“near misses”) increased
significantly by learning across features, often displacing suchirrelevant retrievals as trucks, houses, and computer monitors. For
example, while MR-SPRH (Figure 7(g)) contained 12 relevant
retrievals (R=12/20) in the top 19, L-MR-SPRH (Figure 7(h))
contained 18 relevant retrievals (R=18/20) in the top 19.

of the query model onto the manifold, followed by cosine distancecomputations.)
Our experiments on the relation of subspace dimension andretrieval performance found no clear dimension of the subspace.
This is not very surprising, as shape features for 3D shapes won’t
span a well-defined low-dimensional subspace of a low dimension.
It is unclear if some other non-linear unsupervised learningalgorithms, such as LLE and Isomap, might be able to do better indiscovering the subspace for improved retrieval performance. We
definitely would like to experiment with these other learningalgorithms.

4.5 SHREC 2006 benchmark results
We did not enter the SHREC 2006 3D shape retrieval contest[27], but we performed the benchmark as specified in the contest
using the method described in this paper. The SHREC 2006 uses
the 1,814 models of both training and test sets of the PSB as thetest database. The 30 query models are not included in the test
database. We learned the manifold by sampling a union of the
PSB (1,814 models) and the NTU (10,911 models) as described in
Section 4.1 using the Niederreiter’s quasi-random sequence. The
sizes of training sets are 5,000 for AAD and 4,500 for the SPRH.

ACKNOWLEDGMENTS
This research has been funded by the Ministry of Education,
Culture, Sports, Sciences, and Technology of Japan (No.
17500066 and No. 18300068).

REFERENCES

Excerpts of benchmark results are shown in Table 3. The
table includes, for reference, the top two performers from the
SHREC 2006 results. The performance of the learned, MR versionof the SPRH would have placed at the second or third place
overall if we were to enter the contest.

[1] I. Atmosukarto, W.K. Leow, Z. Huang, Feature Combination
and Relevance Feedback for 3D Model Retrieval, Proc.
MMM 2005, pp. 334-339, (2005).
[2] R. Baeza-Yates, B. Ribiero-Neto, Modern information
retrieval, Addison-Wesley (1999).

5. CONCLUSION AND FUTURE WORK

[3] M. Belkin, P. Niyogi, Laplacian eigenmaps for
dimensionality reduction and data representation, NeuralComputation 15, pp. 1373–1396, (2003).

In this paper, we proposed and evaluated a method for shapesimilarity based retrieval of 3D models that employs unsupervised
learning of a 3D shape corpus (i.e., a collection of 3D shapemodels). Our motivation was to improve distance computation
among shape features that are suspected to lie on a non-linear mdimensional ( m ≤ n ) subspace of the n-dimensional vector spacespanned by the feature vectors. The proposed method learns the
non-linear subspace, or manifold, spanned by the training samples,i.e., shape feature vectors of 3D model corpus, by using the
Laplacian Eigenmaps [3]. The manifold is approximated by RBF
network [6], onto which the feature vectors having high dimension
are projected. The distance computation among shape features arethen performed on the manifold. We combined this learning
approach with the multiresolution shape feature extraction method
proposed by Ohbuchi et al. [18].

[4] P. Bratley, B. L. Fox, H. Niederreiter, Algorithm 738:
Programs to Generate Niederreiter's Low-discrepancy
Sequences, ACM TOMS Algorithm 738.
[5] B. Bustos, D. Keim, D. Saupe, T. Schreck, D. Vranić,
Automatic Selection and Combination of Descriptors for
Effective 3D Similarity Search, Proc. IEEE MCBAR'04,
pp. 514-521, (2004).
[6] Chen, S., C.F.N. Cowan, P. M. Grant, Orthogonal Least
Squares Learning Algorithm for Radial Basis Function
Networks, IEEE Trans. on Neural Networks, 2(2), pp. 302309, (1991)[7] D.-Y. Chen, X.-P. Tian, Y.-T. Shen, M. Ouhyoung, On
Visual Similarity Based 3D Model Retrieval, Computer
Graphics Forum, 22(3), pp. 223-232, (2003).

The experimental evaluation showed that our proposed
method significantly improved shape-based 3D model retrieval
performance. For example, the learning improved retrieval
performances of both AAD [19] and SPRH [28] shape features by
about 5%, measured in R-precision. Combined with themultiresolution approach, both AAD and SPRH gained about 10%
in R-precision, rivaling one of the best performing shapecomparison method Light Field Descriptor by Chen, et al [7].

[8] H. Edelsbrunner, E. P. Mücke, Three-dimensional Alpha
Shapes, ACM TOG, 13(1), pp. 43-72, (1994).
[9] 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).
[10] S. Haykin, Neural network a comprehensive foundation,
Second Edition, Prentice Hall, 842pages, (1999).

Probably the most significant issue with the proposed method
is the computational cost, both spatial and temporal, of thelearning phase. As stated before, a naïve method for the
eigendecomposition used for the manifold estimation costs O( n2 )space and O( n3 ) time. The RBF network regression, currently thelimiting factor in increasing the training set size, also costs
significant amount of spatial and temporal computational. Thus,
one of the foremost issues is to reduce computational costs ofeigendecomposition and RBF network approximation. Note thatthe computational cost of the retrieval phase is not particularly
expensive. It only requires projection of the shape feature vector[11] Xiaofei He, Wei-Ying Ma, Hong-jiang Zhang: Learning an
Image Manifold for Retrieval, Proc. ACM Multimedia 2004,
pp. 17-23 (2004).
[12] Iyer, N., Kalyanaraman, Y., Lou, K., Jayanti, S., Ramani, K.,
A Reconfigurable, Intelligent 3D Engineering Shape Search
System Part I: Shape Representation, Proc. ASME DETC '03,
23rd CIE Conf. (2003).
[13] M. Iyer, S. Jayanti, K. Lou, Y. Kalyanaraman, K. Ramani,
Three Dimensional Shape Searching: State-of-the-art Review

8Ryutarou Ohbuchi, Jun Kobayashi, Unsupervised Learning from a Corpus for Shape-Based 3D Model Retrieval, accepted, ACM MIR 2006,
Santa Barbara, CA, U.S.A., Oct. 2006[21] R. Osada, T. Funkhouser, B. Chazelle, D. Dobkin, ShapeDistributions, ACM TOG, 21(4), pp. 807-832, (2002).

and Future Trends, Computer Aided Design, 5(15), pp. 509530, (2005).
[14] G. Leifman, R. Meir, A. Tal, Semantic-oriented 3d shape
retrieval using relevance feedback, The Visual Computer(Pacific Graphics), 21(8-10), pp. 865-875, October 2005.

[22] W. H. Press et al., Numerical Recipes in C-The Art of
Scientific Programming, 2nd Ed., Cambridge University
Press, Cambridge, UK, 1992.

[15] Rong Liu, Varun Jain, Hao Zhang, Sub-sampling for
Efficient Spectral Mesh Processing, Proc. CGI 2006, LNCS
4035, pp. 172-184, Springer-Verlag, (2006).

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

[16] 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).

[24] 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[17] NTU 3D Model Database ver.1
http://3d.csie.ntu.edu.tw/[25] J. Tangelder, R. C. Veltkamp, A Survey of Content Based 3D
Shape Retrieval Methods, Proc. SMI '04, pp. 145-156.

[18] R. Ohbuchi, T. Takei, Shape-Similarity Comparison of 3D
Shapes Using Alpha Shapes, Proc. PG 2003, pp. 293-302,(2003).

[26] J. B. Tanenbaum, V. de Silva, J.C. Langford, A Global
Geometric Framework for Nonlinaer Dimensionality
Reduction, Science, 290(5500), pp. 2319-2323, (2000).

[19] Ryutarou Ohbuchi, Takahiro Minamitani, Tsuyoshi Takei,
Shape-similarity search of 3D models by using enhanced
shape functions, International Journal of Computer
Applications in Technology (IJCAT), 23(3/4/5), pp. 70-85,(2005).

[27] R. C. Veltkamp, R. Ruijsenaars, Michela Spagnuolo, R. Van
Zwol, F. ter Haar, SHREC2006 3D Shape Retrieval Contest,
Utrecht University Dept. Information and Computing
Sciences Technical Report UU-CS-2006-030 (ISSN: 09243275)
http://give-lab.cs.uu.nl/shrec/shrec2006/index.html[20] Ryutarou Ohbuchi, Yushin Hata, Combining Multiresolution
Shape Descriptors for 3D Model Retrieval, Proc WSCG 2006
(2006).

[28] 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).

Table 3. An excerpt of performance figures obtained by using the SHREC 2006 benchmark [27].
Train?
No

Yes

SHREC
2006

SR/
MR
SR

Featurename
SR-SR-AAD-C
SR-SPRH-K
SR-SPRH-C
MR
MR-AAD-C
MR-SPRH-K
MR-SPRH-C
SR
L-SR-AAD-C
L-SR-SPRH-C
MR
L-MR-AAD-C
L-MR-SPRH-C
Makadia, (run 2)
Dars, (run 1)

AP-HR

AP-R

0.23740.28860.2656
0.33220.37610.35850.27480.29790.37890.45390.48690.44750.26030.31790.28920.3246
0.3552
0.3416
0.27950.28370.35640.41050.43640.3952AP-HR: Mean Average Precision (highly relevant)
FT_HR: Mean First Tier (Highly Relevant)
DAR: Mean Dynamic Average Recall
NCG @25: Mean Normalized Cumulated Gain @25

FT-HR
[%]
24.55
26.68
25.03
31.02
34.93
33.42
29.81
30.85
36.58
43.12
44.77
42.75

FT-R
[%]
26.48
31.77
28.48
31.38
32.84
33.38
28.31
30.31
34.35
39.98
40.55
37.03

DAR
0.33640.39900.36500.43200.46310.43440.36690.3884
0.46870.5276
0.54990.5242NCG@25
0.34050.39200.35770.43860.45190.4362
0.39620.41170.47200.53790.54980.5246NDCG@250.37710.43840.40380.47930.51010.4856
0.42850.44280.5194
0.58710.5906
0.5791

AP-HR: Mean Average Precision (relevant)
FT_R: Mean First Tier (Relevant)
NDCG @25: Mean Normlized Discounted Cumulated Gain @25* Prefix “L-” indicates “learned” version of the shape feature.
* AAD-C was trained by using 5,000 samples, and SPRH-C was trained by using 4,500 samples.

9

Ryutarou Ohbuchi, Jun Kobayashi, Unsupervised Learning from a Corpus for Shape-Based 3D Model Retrieval, accepted, ACM MIR 2006,
Santa Barbara, CA, U.S.A., Oct. 2006=(a) SR-AAD, HR=8/20, R=11/20.

(b) L-SR-AAD. HR=10/20, R=15/20.

(c) SR-SPRH, HR=8/20, R=12/20.

(d) L-SR-SPRH, HR=9/20, R=13/20.

(e) MR-AAD, HR=10/20, R=15/20.

(f) L-MR-AAD, HR=14/20, R=19/20.

(g) MR-SPRH, HR=8/20, R=12/20.

(h) L-MR-SPRH, HR=12/20, R=18/20.

Figure 7. Examples of query using an office chair model. Learning clearly improved the retrieval results in this example

10