SHREC 2007 http://www.aimatshape.net/event/SHREC/SHREC 2007 CAD model track https://engineering.purdue.edu/PRECISE/shrec/results

A database-adaptive distance measure for 3D model retrieval
Jun Kobayashi, Akihiro Yamamoto, Toshiya Shimizu, Ryutarou Ohbuchi
Graduate School, University of Yamanashi.
jun066 AT quartz.ocn.ne.jp, g05mk039 AT yamanashi.ac.jp,
g06mk009 AT Yamanashi.ac.jp, ohbuchi AT yamanashi.ac.jp
database of 2D images by using unsupervised learning.
The method learns the non-linear subspace, ormanifold, of features from large number of (unlabeled)
2D images. The dimension of an input feature isreduced by projecting the feature onto the manifold. Adistance among a pair of dimension reduced and“salient” features corresponds to a geodesic distanceon the manifold. He et al used the Laplacian
Eigenmaps (LE) proposed by Belkin, et al [1] to learn
the non-linear manifold. As the manifold generated by
LE is defined only at the training samples, themanifold is smoothly approximated to handle queries
not in the training set.
We adopted He’s approach for 3D model retrieval
in [9]. We applied the dimension reduction using theLE algorithm on two shape features. For both of thefeatures, the dimension reduced feature overtook theoriginal, untrained feature in retrieval performance
when the number of training samples is more thanabout 1,500. For the unsupervised learning of feature
manifold, we (quasi-) randomly sampled a set ofmodels from the union of 1,814 model Princeton
Shape Benchmark database [12] and 10,911 model
National Taiwan University database [7].
Later, we further explored the approach byexperimenting with six learning-based dimension
reduction algorithms, both linear and non-linear [10].
These six dimension reduction algorithms are pairedwith eight shape features in a set of experiments. Of
the dimension reduction methods we compared, thelocally constrained, non-linear methods such as LE andLocally Linear Embedding (LLE) [11] performed thebest. The best performing pair among those tested
performed on a par with the top finisher in the SHREC
2006 contest, that is, Makadia’s method.
To enter the SHREC 2007 CAD track, we used thesame approach as described in [9, 10]. We used the setof “generic” 3D models as in [9, 10], not CAD specific
3D models, for learning the manifold. Our method
came in first in every performance index for theAbstract
The distance measure, in addition to the shapefeature is a key factor in shape based 3D model
retrieval. We employed a database adaptive distancemeasure for 3D model retrieval in the SHREC 2007
CAD track. The method described in this paper uses afeature dimension reduction based on an unsupervised
learning of features to produce salient, lower
dimensional feature from the original feature. Ourmethod also combines a multiresolution shapecomparison approach with the database adaptive
distance measure. Our experiments the SHREC 2007
CAD track showed that both adaptive distancemeasure and multiresolution shape comparison
approach added a few percent each to the original
shape feature. Our method came in first in the SHREC
2007 CAD track despite the fact that the distancemeasure was trained by using a set of “generic” 3Dmodels that are not CAD specific.

1. Introduction
Two of the most important components in a hapebased 3D model retrieval system [13] are the shapefeature and the distance measure used. Intuitively,
shape similarity decision would depend on shapes ofmodels in the database to be compared, or a shape ofthe specific model to be queried. For example, afeature might excel at retrieving a class of models but
not for the others classes. The shape similarity decision
would also have inter-user variations as well intra-uservariation depending on intention of the specific query.
Despite these possible variations, most of the previous
method uses a fixed feature and a fixed distancemeasure. Several researchers experimented with
relevance feedback for on-line, interactive adaptationof distance measure [6] while the other tried queryadaptive combination of distances generated frommultiple features [2].
Xhaofei He et al proposed, in the context of 2D
image retrieval, a distance measure that adapts to the1SHREC 2007 http://www.aimatshape.net/event/SHREC/SHREC 2007 CAD model track https://engineering.purdue.edu/PRECISE/shrec/results
contest even though the training samples are not CAD
model specific.
This paper is organized as follows. We will
describe in Section 2, the algorithm we employed. It isfollowed in Section 3 by the experimental results wehave done using the SHREC 2007 CAD track
benchmark. Section 3 will present the summary andfuture work.

Retrieval phase:

2. The retrieval method1.

Ourretrievalalgorithm
uses
data-driven
unsupervised learning to find a non-linear subspace of
shape features for dimension reduction and thendistance computation (See Figure 1);

2.

Database pre-processing phase:1.

3.

Learning phase:
1.
2.
3.

Feature extraction: Extract n-dimensionalfeature vectors from the K models in the training
database (i.e., corpus).
Sample selection: If necessary, to reduce
computational costs, sub-sample the training set
down to L ( L ≤ K ) features.
Manifold learning: Perform unsupervised
learning of the m-manifold ( m ≤ n ) from the ndimensional training samples by using a manifold
learning algorithm. Certain learning algorithm
produces a manifold defined only at the set oftraining samples. In such a case, to handle queriesoutside of the training set, continuously
approximate the manifold.

LearningDB
pre-processing

Training
DB

RetrievalDB

Featureextraction

Featureextraction

Featureextraction

Sampleselection

Dimensionreduction

Dimension
reduction

Manifoldlearning
Manifold

Salientfeature4.

Feature extraction: Extract an n-dimensionalfeature from the query model.
Dimension reduction: Project the n-dimensionalfeature of the query onto the (approximated) mmanifold to obtain m-dimensional salient feature.
Distance computation: Compute distances fromthe query model to all the models in the databaseusing their m-dimensional salient features using
cosine distance.
Retrieval: Retrieve the models in the databasehaving the p-smallest distances from the query.

To choose the combination of feature and dimension
reduction method for the SHREC 2007 CAD track, wechose six dimension reduction algorithms including
PCA, Kernel PCA, LE, and LLE [10]. We coupledthese with the eight shape features including the SPRHand Spherical Harmonics (SH) [5]. Note that all thefeatures we compared are purely geometric andapplicable to polygon soup models as well as towatertight surface based models. Topological featuresuch as position and/or number of through holes is notused. The distance between a pair of salient features iscomputed by using Cosine distance. We chose theCosine distance after comparing L1-norm, L2-norm,and Cosine distance for their retrieval performance.
For the training, we would have two majoralternatives; (1) use CAD specific 3D models, e.g., thatof the Purdue University Engineering ShapeBenchmark (PUESB), (2) use “generic” 3D models
found, for example, the National Taiwan University
3D Model Database (NTUD) [7].
What we used for the SHREC 2007 CAD track is aset of “generic” 3D models, that is, the union of thetraining set of the Princeton Shape Benchmark (PSB)
database containing 907 models and the National
Taiwan University 3D Model Database (NTUD) ver.
1.0 containing 10,911 models. The NTU database does
not have any labels. The labels in the PSB training set
are simply ignored. By using a quasi-random sequence(Niederreiter sequence), we sub-sampled the union(12,775 models) down to 4,000, 5,000, or 10,000
models for the training.
Some of the learning algorithms have parameters,e.g., number of output dimensions, neighborhoods size
k for manifold reconstruction, and spreads of RBF

Retrieval
Query model

Distancecomput’nDistance

3D modelSalient featureDimension reduction: Project the feature of each
3D model in the database onto the (approximated)m-manifold to obtain an m-dimensional “salient”
feature. Store each salient feature together with acorresponding 3D model.

Retrieval…

Figure 1. Our 3D model retrieval algorithm using
database-adaptive distance measure.

2

SHREC 2007 http://www.aimatshape.net/event/SHREC/SHREC 2007 CAD model track https://engineering.purdue.edu/PRECISE/shrec/results
Originalmodel

2007 CAD track, we chose the best performing
combination, the multiresolution (MR) SPRH feature
dimension reduced by using the LLE algorithm and5,000 training models.

Point set modelgeneration

3. The experimental results

Point setmodel

Table 1a shows the retrieval performance figures byusing the SHREC 2006 benchmark. For example, thesalient (6-level) multiresolution feature LLE-MRSPRH-C trained using 5,000 models gained nearly
18% in First Tire Highly-Relevant (FT-HR) comparedto the original SPRH (=SR-SPRH-K), that is, thesingle resolution SPRH without the learning-based
adaptation of distance measure. The SR-SPRH-K used
Kullback-Leibler Divergence (KLD) as the distancemeasure [15]. The table also lists the performance
figures for the top finisher in the SHREC 2006 contest,
the Makadia’s method.
Table 1b shows the performance indices using theSHREC 2007 CAD track. The best performing is theLLE-MR-SPRH-C (Run6), which used a dimension
reduced, 6-level multiresolution set of SPRH features.
It has the FT-HR of 41.23%, which is 6.5% better thanthe original SPRH (=SR-SPRH-K) in the same
benchmark. The LLE-MR-SPRH-C (Run5) used 5level MR feature, omitting the level 0 (=convex hull).
Overall performance of the 5-level version (Run 5) isslightly lower than that of the 6-level version (Run 6).
The performance gain due to learning appears to be
more significant in the SHREC 2006 than in theSHREC 2007 CAD track. This may be due to the factthat we used the manifold trained by using the SHREC
2006-like 3D models for the SHREC 2007 CAD track.
It is interesting to note that the feature that uses only
the convex-hulls of the models for feature computation,
the MR-L0-SPRH-K, performed rather well. It would
have placed at about 4th place in the SHREC 2007
CAD track. This might be an indication that thesimilarity decision of the SHREC 2007 CAD track
depended heavily on the overall shape of the models.

3D α-shapes
computation
Levels

01

…

L-3

L-2

L-1

Featureextraction
Dimension
reduction
Distancecomputation+Overall distance

Figure 2. The multiresolution set of features isdimension reduced and distance computed
separately at each resolution levels before
integrated into an overall distance.
kernels for manifold approximation. We chose,through preliminary experiments using SHREC 2006
benchmark [14], a set of best-performing parameters.
We integrated the multiresolution 3D shapecomparison approach we have previously proposed [8]with the learning based approach described above (SeeFigure 2.) The multiresolution shape comparison
approach uses a mathematical morphology-like
multiresolution (MR-) representation to obtain
multiresolution set of shape features. We applied themanifold learning and dimension reduction separately
at each resolution level. That is, if the MR
representation has L resolution levels, a total of L
manifolds are learned using features computed foreach resolution level. Then, dimension reduction is
performed independently at each level. To compare apair of 3D models, a distance is calculated at each ofthe L levels of the MR representation. These L distancevalues are then combined into an overall distance
between the pair of models by using a fixed-weightlinear combination of the distances. We used theweight 1.0 for all the levels.
We conducted a set of preliminary experiments tocompare
retrieval
performancesofvarious
combinations of the methods. To enter the SHREC

4. Summary and future work
In this paper, we described the method we used forour entries in the SHREC 2007 CAD track. The
method employs unsupervised learning to estimate anon-linear subspace, or manifold of features.
Dimension reduction of the original feature using themanifold produces a salient feature that results inbetter retrieval performance. To enter the contest, weused the LLE algorithm [11] for the manifold learning,
and used a set of 5,000 “generic” 3D models for thetraining samples. By combining the learning based
adaptive distance measure with a multiresolution shape3

SHREC 2007 http://www.aimatshape.net/event/SHREC/SHREC 2007 CAD model track https://engineering.purdue.edu/PRECISE/shrec/results[6] 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.

comparison approach we have previously proposed,
we gained significant performance advantage to win
the SHREC 2007 CAD track.
First in the list of items to do is to see if a training
set consisting of CAD specific models would improvelearning and thus retrieval performance. We are alsointerested in applying the database-adaptive approachto the other tracks, e.g., the face model retrieval track.

[7] NTU 3D Model Database ver.1. http://3d.csie.ntu.edu.tw/[8] R. Ohbuchi, T. Takei, Shape-Similarity Comparison of3D Shapes Using Alpha Shapes, Proc. Pacific Graphics
2003, pp. 293-302, (2003).
[9] R. Ohbuchi, Jun Kobayashi, Unsupervised Learning froma Corpus for Shape-Based 3D Model Retrieval, poster paper,
Proc. ACM MIR 2006 (2006).
[10] R. Ohbuchi, J. Kobayashi, A. Yamamoto, T. Shimizu,
Comparison of dimension reduction methods for databaseadaptive 3D model retrieval, accepted, Proc. 5thInternational Workshop on Adaptive Multimedia Retrieval(AMR) 2007, Paris, France, July, 2007.
[11] S. T. Roweis, L. K. Saul, Nonlinear Dimensionality
Reduction by Locally Linear Embedding, Science, 290(5500),
pp. 2323-2326, (2000).
[12] 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[13] J. Tangelder, R. C. Veltkamp, A Survey of Content
Based 3D Shape Retrieval Methods, Proc. SMI '04, pp. 145156.
[14] R. C. Veltkamp, et al., SHREC2006 3D Shape RetrievalContest, Utrecht University Dept. Information andComputing Sciences Technical Report UU-CS-2006-030(ISSN: 0924-3275)[15] E. Wahl, U. Hillenbrand, G. Hirzinger, Surflet-PairRelation Histograms: A Statistical 3D-Shape Representation
for Rapid Classification, Proc. 3DIM 2003, pp. 474-481,(2003).

Acknowledgements
This research has been funded, in parts, by the Ministry ofEducation, Culture, Sports, Sciences, and Technology ofJapan (No. 17500066 and No. 18300068).

References[1] M. Belkin, P. Niyogi, Laplacian eigenmaps fordimensionality reduction and data representation, NeuralComputation 15, pp. 1373–1396, (2003).
[2] B. Bustos, D. Keim, D. Saupe, T. Schreck, D. Vranić,
Automatic Selection and Combination of Descriptors forEffective 3D Similarity Search, Proc. IEEE MCBAR'04,
pp. 514-521, (2004).
[3] S. Haykin, Neural network a comprehensive foundation,
Second Edition, Prentice Hall, 842 pages, (1999).
[4] Xiaofei He, et al., Learning an Image Manifold forRetrieval, Proc. ACM Multimedia 2004, pp. 17-23 (2004).
[5] M. Kazhdan, T. Funkhouser, S. Rusinkiewicz, Rotation
Invariant Spherical Harmonics Representation of 3D Shape
Descriptors, Proc. Symposium of Geometry Processing 2003,pp. 167-175 (2003).

Table 1a. Retrieval performance of our method measured using the SHREC 2006 [14].
# training
samples
SR-SPRH-K
MR-SPRH-K
LLE-MR-SPRH-C
5,000
LLE-MR-SPRH-C
10,000Makadia(Run 2)Features# of MRlevels
SR666-Distance

AP-HR

KLD
KLD
CosineCosine-0.2886
0.3761
0.46140.47470.4364

FT-HR
[%]
26.68
34.93
44.46
44.44
44.77

DAR
0.39900.46310.5341
0.53820.5499NCG@25
0.39200.45190.56040.5584
0.5498NDCG@250.43840.51010.59660.60130.5906

Table 1b. Retrieval performance of our method measured using the SHREC 2007 CAD track.
# training
samples
SR-SPRH-K
MR-SPRH-K
LLE-MR-SPRH-C (Run 6)
5,000
LLE-MR-SPRH-C (Run 5)
5,000
MR-L0-SPRH-KFeatures# of MRlevels
SR6651Distance

AP-HR

KLD
KLD
CosineCosineCosine0.37210.40550.43370.43190.3437

FT-HR
[%]
34.76
36.38
41.23
40.25
30.97

DAR
0.46420.50020.53570.53450.4400NCG@250.3916
0.43690.50230.48500.3896

NDCG@250.44780.49120.53410.52700.4327

AP-HR: Mean Average Precision (highly relevant)AP-R: Mean Average Precision (relevant)
FT_HR: Mean First Tier (Highly Relevant)
FT_R: Mean First Tier (Relevant)
ST_R: Second Tier (Relevant)
DAR: Mean Dynamic Average Recall
NCG @25: Mean Normalized Cumulated Gain @25
NDCG @25: Mean Normlized Discounted Cumulated Gain @25z“MR” denotes a multiresolution feature, while “SR” denotes a single resolution feature.
z
Suffix “-K” denotes distance computed by using Kullback-Leibler Divergence, while “-C” denotes Cosine distance.

4