Megumi Endoh, Tomohiro Yanagimachi, Ryutarou Ohbuchi, Efficient manifold larning for 3D model retrieval by using clustering-based training sample
reduction, poster paper, Proc. IEEE Int'l Conf. on Acoustics, Speech, and Signal Processing, Kyoto, Japan, March 2012 (2012).

EFFICIENT MANIFOLD LEARNING FOR 3D MODEL RETRIEVAL BY USING
CLUSTERING-BASED TRAINING SAMPLE REDUCTION
Megumi Endoh, Tomohiro Yanagimachi, and Ryutarou Ohbuchi,
Dept. of Computer Science and Engineering
University of Yamanashi
Kofu, Yamanashi-ken, Japan
g10mk006AT gmail.com, tomohiro.yanagimachiAT gmail.com, ohbuchiAT yamanashi.ac.jp
ABSTRACT
Retrieval accuracy in content-based multimedia retrieval canbe improved by using distance metric learned from
distribution of features in input feature space. One way toachieve this is by dimension reduction via manifold-learning,such as Locally Linear Embedding [8]. While effective in
improving retrieval accuracy, these algorithms have highcomputational cost that depends on feature dimensionality dand number of training samples N. In this paper, we explore
a clustering-based approach to reduce number of training
samples; it uses L cluster centers (L<<N) computed from N
input features as training samples. We propose to use
extremely randomized clustering tree [3] for clustering.
Experiments showed that the proposed approach produces
better retrieval performance than random sampling, and thatthe randomized tree is much faster than the k-means
algorithm.
Index Terms— Content-based 3D model retrieval,
distance metric learning, manifold learning, randomized tree
clustering.
1. INTRODUCTION
Three-dimensional (3D) shape model has gained its status asa multi-media data type. It is used in designing andmanufacturing mechanical parts, architectural design, inmedical diagnosis, and in entertainment. User-generated
contents are also flourishing. The Google 3D Warehouse
now holds hundreds millions of 3D shape models.
Accordingly, effective and efficient management of 3Dmodels, especially via content based retrieval by their shape,
has become quite important (e.g., [9]).
Generic processing pipeline for shape-based retrieval of 3Dmodels starts with extraction of shape descriptors, or feature,from query and database 3D models. Then, distance, ordissimilarity among features of the query model anddatabase models are computed to rank retrieval results.
Earlier 3D model retrieval algorithms used “fixed” distance,e.g., L2- or L1-norm. However, learned distance metricadapted to the feature distribution could significantly
improve retrieval performance. In [6], so-called manifold

learning algorithm such as Laplacian Eigenmaps (LE) [1] orLocally Linear Embedding (LLE) [8] is used for
unsupervised non-linear dimension reduction. Given large
enough number of feature samples in an ambient, or input,
feature space, these algorithms find non-linear mapping onto
lower dimensional subspace or “manifold” on whichsamples lie. By computing distance on the manifold, insteadof the ambient feature space, better distance can be obtained.
In addition to improved distance and thus improved retrieval
accuracy, lower feature dimension also leads to lower
temporal and spatial computational cost during the searchthrough the database.
However, these manifold learning algorithms arecomputationally expensive. For example, during the training
stage, LE and LLE constructs a graph connecting featurepoints, followed by Singular Value Decomposition (SVD)
of its graph Laplacian. Using a naïve algorithm, graphconstruction requires O(N2) distance computations. If we
use L2-norm, each distance requires O(d) multiplications
and additions. SVD of a graph Laplacian takes O(N3) timeusing a naïve algorithm. We have to find some way toefficiently learn a manifold from a training set having alarge number of samples (e.g., 104~) and a high feature
dimensionality (e.g., 102~105).
Assuming that the dimensionality of feature is given,approaches to deal with large number of samples have been
explored. The simplest of the approaches is to pseudorandomly or quasi-randomly [6, 7] down sample the training
set. Another approach is to use Nystrom low-rankapproximation [12, 2].
In this paper, we propose to cluster the N input features sothat the computed L (L<<N) cluster centers become new
training samples. Our hope is that, cluster centers,
themselves created by unsupervised learning of feature
distribution, could better represent distribution of input
features than a simple down-sampling. For the clustering,
we propose to use Extremely Randomized Clustering tree
(ERC-tree) of Guerts, et al [3] for the task. While k-means isa “standard” clustering algorithm, it is quite slow if thefeature dimension, number of features, and/or the number ofcluster is large. And if clustering is too slow, total cost oflearning, which is a sum of the cost of clustering andMegumi Endoh, Tomohiro Yanagimachi, Ryutarou Ohbuchi, Efficient manifold larning for 3D model retrieval by using clustering-based training sample
reduction, poster paper, Proc. IEEE Int'l Conf. on Acoustics, Speech, and Signal Processing, Kyoto, Japan, March 2012 (2012).

manifold learning, can’t be reduced. In addition, L2-norm
used at the core of k-means algorithm is known to suffer inquality if applied to high-dimensional features.
Experimental evaluation has shown that retrieval
performances due to k-means and ERC-tree clustering areabout equal, both of which are significantly better than one
due to quasi-random sampling. In terms of computationalcost, the ERC-tree is much faster than k-means.
2. METHOD
Our retrieval algorithm consists of two phases, the learning
phase and retrieval phase.
The learning phase:(1) Extract shape feature vector: Extract d-dimensionalfeature vectors from the N 3D models in the training
database (i.e., corpus).
(2) Select training samples: To reduce computationalcosts, subsample the training set down to L (features vectors. We compare three down-sampling
methods, Quasi-Random Sampling (QRS), K-Means
Clustering (kMC), and ERC-tree clustering (ERC).
(3) Learn manifold: Perform unsupervised learning of them-manifold () spanned by the d-dimensional
Learning phase
N models

Retrieval phase
Query model

3D modeldatabase
N models
Extract 3D
shape featureN features
Select trainingsamples
L  N features
Learn
manifold g LLE

Extract 3D
shape feature Approximatede-D vector
manifold g
Map e-D featureg
onto g
d-D vectord-DComputed-D
distancefeaturesdistance
3D modelApproximate g RBF
Retrievaldatabase
network
g
e-D vector
Map e-Dfeatures onto g
d-D vector
d-Dfeatures…

g
Approximatedmanifold g

g : Mapping from e-D feature vector to d-D feature vector,
defined only at training samples.
g : Approximate, continuous mapping from e-D feature vector tod-D feature vector.

Figure 1. Retrieval pipeline using manifold learning for
distance metric learning

training samples by using LLE [8].
(4) Approximate the manifold: Construct a continuous
approximation of the manifold by using the RBF
kernel regression.
(5) Project features of the models in the database:
Project features of all the models in the database onto
the m-manifold using the approximation, and store theresults together with the corresponding 3D models.
The retrieval phase:(1) Extract shape feature vector: Extract a d-dimensionalfeature vector from the query model.
(2) Project the feature onto the manifold: Map the ddimensional feature vector onto the approximated mmanifold .
(3) Compute distance on the manifold: Computedistances from the query model to all the models in thedatabase on .
(4) Retrieve and present the top p matches: Retrieve themodels in the database having the p-smallest distancesfrom the query model.
2.1. Training Sample Selection
We will compare three different algorithms for sample
reduction; one is the standard pseudo- (or quasi-) random
sampling approach, and the other two are clustering based
approach. We compared two clustering algorithms, k-meansclustering and ERC-tree clustering.
 Quasi-Random Sampling (QRS): Instead of popular
pseudo-random sampling, we used quasi-random
sampling, which produced slightly better retrieval
accuracy than pseudo-random sampling [6]. The set ofexperiments that follow uses Niederreiter’s quasirandom sequence.
 k-means Clustering (kMC): Well known k-meansclustering produces k clusters given the cluster number
k as a parameter. We use standard, or Lloyds’
algorithm.
 Extremely Randomized Clustering tree (ERC): The
ERC-tree [3] is a randomized, tree-based clustering
algorithm which subdivides the feature space into ahalf by each added tree node. Each subdivision is due
to a hyper plane perpendicular to one of the coordinate
axes. For each subdivision, the algorithm first
randomly picks the dimension (or axis) to subdivide,and then randomly chooses the point (a scalar value)on the selected axis at which a separating hyperplane isplaced. Subdivision of the feature space continues until
the number of data points per subspace is below a set
parameter Smin. While the Smin affects the number ofclusters L, that is, number of reduced samples, exact
value of L differ from a run to another due to therandomized nature of the algorithm. The L can also becontrolled by pruning the tree, but we don’t perform
any pruning.

Megumi Endoh, Tomohiro Yanagimachi, Ryutarou Ohbuchi, Efficient manifold larning for 3D model retrieval by using clustering-based training sample
reduction, poster paper, Proc. IEEE Int'l Conf. on Acoustics, Speech, and Signal Processing, Kyoto, Japan, March 2012 (2012).

2.2. Unsupervised Dimension Reduction
To obtain learned distance metric, we used manifold-based,
unsupervised dimension reduction by LLE [8]. Given a setof N unlabeled e-dimensional ambient (original) features,
LLE algorithm learns the d-dimensional subspace S spannedby the ambient feature set. The resulting S maps an input edimensional feature onto the d-dimensional feature in whichd  e . For LLE, the manifold S is defined only for thetrained features points. Thus, to handle out-of-samplefeatures, e.g., that of query, manifold S must beapproximated so that it is defined everywhere in the input
space. Following [4], we used RBF-network algorithm forthe approximation.
The retrieval algorithm stores, in the database, the(projected) d-dimensional feature together with thecorresponding 3D model for later retrieval. As thedimension d is much smaller than the dimension e of thecorresponding ambient feature, cost of distance computationand feature storage are significantly reduced.
We used the LLE implementation available in the MatLab
Statistical Learning Toolbox. Mesh of the features for theLLE is computed by proximity in L2-norm, and the weight
for the edges of the mesh is 0/1 (as opposed to the heatkernel). The MatLab Neural Network Toolkit is used forRBF-network. Parameters for the LLE and RBF-network,
such as neighbourhood size for the LLE, reduced dimensiond, bandwidth of the RBF, are found experimentally to havethe best retrieval performance among the tested.
3. EXPERIMENTS AND RESULTS

However, as we can’t obtain such a large benchmark dataset,
we settled for the National Taiwan University (NTU)
database [5] containing 10,908 unlabeled models. From theNTU database, we created/selected smaller number offeatures for LLE to learn by using the method described inSection 2.1. As numerical indices of retrieval performance,
we use Mean Average Precision (MAP).
Figure 1 shows, for three sample reduction methods tested,retrieval performance in R-Precision. Due to the randomized
nature of the ERC-tree, retrieval performance varies. Notealso that, for ERC-tree, the number of clusters L also
scatters a bit, as it can only be controlled indirectly by Smin.
For k-means, on the other hand, the number of samples canbe set exactly by the parameter k. In cases of QRS and kMC
the number of training samples can be controlled precisely,
and retrieval performances indicated are averages of 5 trials.
The figure shows that distance metric learning in the form of
unsupervised dimension reduction by using LLE does
improve retrieval performance, compared to the case using
fixed distance as well as the case using LLE combined with
QRS. It also shows that, in terms of retrieval performance,
for the number of samples tested, ERC-tree is equal or better
than the much slower k-means clustering. “Raw”
performance of MAP=0.248 using fixed distance is pushed
up to MAP=0.32~0.33 for the ERC-tree clustering.
0.34
0.33
0.32
Retrieval precision (MAP)

Since the feature space is subdivided into subspaces by a setof orthogonal hyperplanes, the quality of the clusters
produced by ERC-tree may not seem as good as those
produced by k-means. This is true in a low-dimensionalfeature space. However, k-means algorithm is disadvantaged
in a high-dimensional feature space, as the algorithm uses
L2-norm and that the L2-norm is known to behave poorly ina high-dimensional feature space. Consequently, clusters
produced by ERC-tree could be better than k-means clusters.
In terms of computational cost, ERC-tree is much faster thank-means.

0.31
0.30
0.29
ERCkMCQRSNo learning

0.28
0.27
0.26
0.25
0.24
0

2,000

4,000

6,000

Number of training samples

We experimentally evaluated the efficacy of sample
selection methods, both in terms of retrieval accuracy andcomputational cost, using LLE in 3D model retrieval setting.
As shape feature, the experiment uses Surflet-Pair Relation
Histograms (SPRH) [11] having d=625. To evaluate, we use
SHREC 2006 [10] 3D model retrieval benchmark
containing 1,814 of diverse 3D shape models. All themodels in the SHREC 2006 benchmark database areclassified into ground truth classes. The SHREC 2006 query
set contains 30 out-of-sample models. To train LLE, weneed large number of 3D models. Ideally, we’d like to havea large dataset, e.g., a database having >100k 3D models.

Figure 1. Training sample reduction methods and retrieval
performance.
Figure 2 compares total cost of distance metric learning, thatis, sum of time required for sample reduction and LLE
learning. Broken lines are for clustering only, while solidlines are for total learning time. Total learning time includes
clustering for sample reduction and LLE learning. The latterincludes LLE learning, RBF approximation, and projectionof 1,814 database features.
It is clear from the graph that kMC is too expensive; sample
reduction by kMC took more time than manifold learningMegumi Endoh, Tomohiro Yanagimachi, Ryutarou Ohbuchi, Efficient manifold larning for 3D model retrieval by using clustering-based training sample
reduction, poster paper, Proc. IEEE Int'l Conf. on Acoustics, Speech, and Signal Processing, Kyoto, Japan, March 2012 (2012).

itself. As the number of output samples (i.e., clusters)
increases, computation time for k-means increases very
rapidly. On the other hand, temporal cost of ERC issignificantly smaller than LLE learning, efficiently reducing
number of samples. Temporal cost of ERC clustering is only
a fraction of that of kMC.
Overall, sample reduction by ERC combined with LLEbased dimension reduction performed well both in terms ofretrieval accuracy and computational cost.

those who created benchmark databases. This research has
been funded in part by the Ministry of Education, Culture,Sports, Sciences, and Technology of Japan (No. 18300068).
6. REFERENCES[1][2]
12,000kMC
kMC+LLEERC
ERC+LLE

Execution time [s]10,000
8,000

[3]
[4]
[5]

6,000
[6]
4,000
[7]

2,000

[8]

00

2,000

4,000

6,000

Number of training samples (i.e., clusters)

Figure 2. Number of training samples (i.e., clusters) aftersample reduction to time needed for sample reduction.
4. SUMMARY AND FUTURE WORKIn this paper, we proposed a clustering-based sample
number reduction to improve efficiency of manifoldlearning based unsupervised distance metric learning.
Experimental evaluation showed that proposed reduction
method using Extremely Randomized Clustering (ERC)
trees [3] significantly outperforms (quasi-) random samplingin terms of retrieval accuracy. If compared to k-means based
sample reduction, ERC-tree based approach is much faster,while attaining equal or better retrieval accuracy.
To quantify the efficiency and efficacy of sample reduction
methods for large scale 3D model retrieval, we need to scale
up the training as well as benchmark database. We also needto experiment with other features, e.g., those having higher
dimensionality. To process even larger number of samples,or to process even higher dimensional features, proposed
approach is not efficient enough. We are currently
investigating improvements to further reduce computational
cost without losing retrieval accuracy.
5. ACKNOWLEDGEMENTS
The authors would like to thank those who carefully
reviewed the paper. The authors also would like to thank[9]

M. Belkin,
P. Niyogi,
Laplacianeigenmaps
fordimensionality reduction and data representation, NeuralComputation, 15(6), pp. 1373-1396, (2003).
C. Fowlkes, S. Belongie, F. Chung, and J. Malik. Spectralgrouping using the Nyström method, IEEE PAMI, 26(2)，pp. 214–225, 2004.
P. Guerts, D. Ernst, L. Wehenkel, Extremely randomizedtrees, Machine Learning, 2006, 36(1), 3-42, (2006).
X. He, W-Y. Ma, H-J. Zhang, Learning an Image Manifold
for Retrieval, Proc. ACM Multimedia 2004, pp. 17-23 (2004)
NTU 3D Model Database ver.1
http://3d.csie.ntu.edu.tw
R. Ohbuchi, J. Kobayashi, Unsupervised Learning from a
Corpus for Shape-Based 3D Model Retrieval, Poster paper,Proc. ACM MIR 2006, pp. 163-172, (2006).
R. Ohbuchi, A. Yamamoto, J. Kobayashi, Learning semantic
categories for 3D Model Retrieval, Proc. ACM MIR 2007,
pp. 31-40, (2007).
S.T. Roweis, L.K. Saul, Nonlinear Dimensionality Reduction
by Locally Linear Embedding, Science, 290(5500), pp.23232326, (2000).
J.W.H. Tangelder, R. C. Veltkamp: A survey of content
based 3D shape retrieval methods. Multimedia Tools Appl.
39(3): 441-471 (2008)[10] R. C. Veltkamp, R. Ruijsenaars, Michela Spagnuolo, R. VanZwol, F. ter Haar, SHREC2006 3D Shape Retrieval Contest,
Utrecht University Dept. Information and Computing
Sciences Technical Report UU-CS-2006-030 (ISSN: 09243275)[11] 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.
[12] C. Williams, M. Seeger, Using the Nyström method to speed
up kernel machines. Advances in Neural Information
Processing Systems 13, pp. 682-688, (2001).