SHREC'08 Entry: Semi-Supervised Learning for
Semantic 3D Model Retrieval
Akihiro Yamamoto, Masaki Tezuka, Toshiya Shimizu, Ryutarou Ohbuchi
University of Yamanashi†

ABSTRACT
A shape feature by itself is not sufficient for effective 3D modelretrieval. Long-lasting semantics shared by a community as well
as a short-lived intention of a user determines the similarity of 3Dmodels. In this paper, we describe a method of shape-based 3Dmodel retrieval that employs off-line, semi-supervised learning ofmultiple classes in the database to capture long-lasting, sharedsemantic knowledge. The method performs two learning based
dimension reductions, first one to accommodate distribution offeatures in the feature space and the second one to accommodate
the semantic knowledge embodied in a set of user-definedsemantic labels. We evaluate the method by using the SHREC’08
3D Generic and CAD Models Track.

(a)

1INTRODUCTION

Shape-based retrieval of 3D models could benefit significantly
from supervised learning of commonly shared semantic classes oran intention of a user. Overall shape of bananas and dolphins aresimilar. In such a case, a supervised learning scheme would help a
lot in distinguishing semantic classes.
An intention is often captured by using Relevance feedback(RF), which learns, supervised, an intention of a user throughinteractive user feedback. The RF approach captures an intention,
a semantics that lasts a short period and shared by a few. A
drawback of the RF is that every retrieval session must start anew
with a low retrieval performance.
To exploit long-lived, commonly shared knowledge, orsemantics, one may employ an off-line supervised learning ofmultiple semantic classes. Supervised learning of multiple
semantic classes can be difficult, due to small number of labeled
examples per class and mutually conflicting constraints frommultiple classes.
We have previously proposed a semi-supervised dimension
reduction (SSDR) approach [3] to learn multiple semantic classes
off-line, and successfully improved retrieval performance of thePrinceton Shape Benchmark (PSB) [5], a collection of “generic”
and diverse 3D models. In this paper, we apply the same approach†

4-3-11 Takeda, Kofu-shi, 400-8511, Japan.
yama.akihiroAT jp.fujitsu.com, g06mk009AT yamanashi.ac.jp
t04kf026AT yamanashi.ac.jp, ohbuchiAT yamanashi.ac.jp

Salient
featurem-dim.
featureUDRk >mp unlabeledmodels(b)p >> qInput
featurek-dim.
featureSDR

Salient
featurem-dim.
featurek>mp >> q

KEYWORDS: Content-based retrieval, manifold learning, multiscale feature.
INDEX TERMS: 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 [SceneAnalysis]: Object recognition.

Input
featurek-dim.
feature(c)Inputfeaturek-dim.
featureInterim
featurel-dim.
featureUDR

k>lp unlabeledmodels

q labeledmodelsSalientfeaturem-dim.
featureSDRl>mp >> q

q labeledmodelsFigure1. Unsupervised (UDR) (a), Supervised (SDR) (b), and theSemi-Supervised (SSDR) (c) dimension reduction methods.

to two SHREC’08 Tracks.
2METHODThe SSDR method [3] first generates a 6-level set ofmorphological Multi-Resolution (MR) models from each model inorder to compare features at finer as well as coarser (i.e., nearlyconvex hull) scales. Following steps, the feature extraction,dimension reduction, and distance computation, are all performedat each resolution level before the distances from all MR-levels
are fused into an overall distance (Figure 2).
To extract a feature, a model is converted from a surface model
to a point set model via quasi-Monte-Carlo sampling of thesurfaces. Then the Surflet Pair Relations Histogram (SPRH)
algorithm [7] is applied to compute a k=54=625D histogram. The
method then performs Unsupervised Dimension Reduction (UDR)
to map the input k-D feature onto a subspace of l-D adapted to thedistribution of the features. This step makes the next step, thesupervised learning, easier. The interim feature is then processedby Supervised Dimension Reduction (SDR) algorithm trained byusing a labeled training set to produce a salient feature. Thedimension m of the salient feature after the SDR step is typicallyhas a much smaller than the dimension k of the original feature.
Distances computed at six MR levels are combined into one bysimply summing them.
We compare the retrieval performance among four methods;(1) (multiresolution version of the) original SPRH feature,(2) UDR processed feature (Figure 1a), (3) SDR processed feature(Figure 1b), and (4) SSDR processed feature (Figure 1c). To

compute distance, the original SPRH used the Kullback-Leibler
divergence, while the UDR, SDR, and SSDR processed features
used Cosine measure. We used the Locally Linear Embedding(LLE) [4] for the UDR, and Supervised Locality Preserving
Projections (SLPP) [1] for the SDR.
ComputeExtract
feature UDR SDR distenceSumdistances

Originalmodel GenerateMRmodelFigure 2. A set of morphological multiresolution models areconstructed from the original model for shape comparison. Feature
extraction, dimension reduction, and distance computation are
performed at each resolution level. Distance from multiple
resolution levels are integrated into an overall distance by summing.

3

Query set 2 (Q2). The SDR algorithm is trained by using theclasses of the Q1 only, a set of classes identical to the SHREC
2006 ground truth set classes.
Various parameters for learning algorithms are set to maximize
the retrieval performance based on a preliminary set ofexperiments.
3.2
EXPERIMENTS AND RESULTSFor the Generic Models Track, Table 1 and Figure 2 show
excerpts of performance evaluation results. In the case of Q1, theFT=34.93% of the original feature went up to FT=45.4% after theUDR. The SDR applied directly to the original feature produced
the FT=38.49%, a figure marginally better than the original, butworse than that of the UDR. The proposed SSDR method yielded
the best retrieval performance FT=58.33% for Q1, 23%
improvement over the original, MR-SPRH feature.
The performance figures of the method for the Q2 are markedly
worse than those for the Q1. In the SHREC’08 GMT, the SSDR
method ranked 1st place for the Q1. However, the rank dropped to3rd place for the Q2. This drop in performance is explained by thefact that the SSDR method is trained by using Q1, but not Q2.
Still, the performance of the SSDR method for Q2 is significantly
better than that of the UDR method, suggesting that the learning
done in the SDR stage for the Q1 classes do generalize to theclasses in Q2.
The method is computationally efficient during retrieval, as all
the costly learning is done during the preprocessing stage, off-line.
Furthermore, the cost of comparison, which is dominant for alarge database, is reduced due to dimension reduction. For the six
level MR, the dimension of the original, 625×6=3,750, is reduced
to 40×6=240 with according reduction in computational cost.

SSDR

36.26

SDR

38.49

GENERIC MODELS TRACK

We used our method in the SHREC’08 Generic Models Track(GMT) for which we briefly summarize the training data andexperimental results.
3.1
TRAINING DATA
We trained the UDR algorithm by using the union of the PSB andthe National Taiwan University shape benchmark down-sampled
to 5,000 models. In the SHREC 2008 GMT, the query set
identical to that of SHREC 2006 query set (30 models) is called
Query set 1 (Q1), and the new query set (30 models) is called

30.20

UDR

58.33

45.40
Q2

Original

34.93
020

Q140

60

80

100Figure 2. Comparison of the performance across methods andquery sets using Mean First Tier (Highly Relevant).

Table 1. Retrieval performances of the Semi-Supervised Dimension Reduction (SSDR)-based method measured using the SHREC 2008
Generic Models Track.
Queryset12Method

UDRDim.
lSDR
Dim.
mDistance

Original
UDR
SDR
SSDR
Makadia (run2)
UDR
SSDR

350400350
400305050KLD
CosineCosineCosineCosineCosineRetrieval performance
MAP-HR

MAP: Mean Average Precision (HR-Highly relevant, R-Relevant)
DAR: Mean Dynamic Average Recall
NCG@25: Mean Normalized Cumulated Gain @25

0.3761
0.46870.40400.63090.48690.28180.4081

MAP-R
0.35520.42780.38930.5846
0.4364
0.23630.3603

AFT-HR
34.93%
45.40%
38.49%
58.33%
44.77%
30.20%
36.26%

AFT-R
32.84%42.18%
37.33%
53.63%
40.55%
26.14%
34.05%

DAR
0.4631
0.54130.46670.65140.54990.36160.4480MNCG@250.45190.55670.48860.65780.54980.37680.4612

MNDCG@250.51010.60490.51590.68790.5906
0.41200.4681

AFT: Mean First Tier (HR-Highly relevant, R-Relevant)
NDCG@25: Mean Normalized Discounted Cumulated Gain @25

4CAD MODELS TRACK

4.1
TRAINING DATA
For the SHREC’08 CAD Models Track, we trained the UDR
algorithm by using “generic” 3D models; we used 4,000 models
quasi-randomly sampled from the union of the PSB and theNational Taiwan University shape benchmark. We must use
generic models since the ESB with its 866 models is not large
enough to train the UDR. The SDR algorithm is trained by using
the ESB models and classes.
4.2
EXPERIMENTS AND RESULTS
The results for this track are summarized in Figure 3. Here, weuse Mean First Tier (FT), among others, as the numericalperformance measure. The UDR improved the FT=36.38% of theoriginal feature to 42.75%. This is the method we used to enter theSHREC 2007 CMT [6], but with a slightly different parameter set.
The SDR applied directly to the original feature resulted inFT=57.72%, a significant 20% gain over the original. In contrast,in case of the PSB, the SDR-only method did not give significant
performance gain. The ESB classes may be easier to learn than thePSB. Finally, the SSDR yielded the best score, FT=78.16%,
adding 40% to the original.
Figure 4 shows the change of performance in FT as we vary thenumber of the salient feature dimension m after the SDR. Thegraph plots curves for multiple interim feature dimensions l={100,200, 300, 400, 500} after the UDR. The SSDR overtook SDRonly feature (625D) if the interim feature dimension l>300.
SSDR

78.16

SDR

57.72

UDR

42.75

Orig.

36.38
02040

60

80

100

Figure 3. Comparison of the performance using the Mean First Tier.
100%

Observation of per-query results seems to suggest the following
reasons for the good result; (1) the MR approach that exploits
features at multiple scales, (2) the SSDR that learned to use theSPRH feature effectively, and (3) the SPRH feature that detects
mutual orientation of surfaces about 3 axes parameterized bydistance. In the CMT, the SSDR obtained FT=100% for themajority of the queries.
Some of the CMT queries seem quite difficult even for a nonmechanical engineer human being to do. For example, Query 43,
Query 45 (the method has FT=100% on these two) and Query 3(The method has FT=0% on this) were both difficult for mystudents.
The method is computationally efficient. Costly learning isdone as a preprocessing. Once the UDR and SDR are trained, adimension reduction is simply a matrix-vector multiplication of al-dimensional (for the UDR) or m-dimensional (for the SDR)
vector. The dimension reduction makes the search through thedatabase much faster. Per resolution level, the dimension of theSSDR processed feature m=40, which is 1/15 of the original
feature having k=625. If all six MR levels are combined, thedimension is reduced from 625×6=3,750 to 40×6=240.
5REFERENCES
[1]

[2]

80%
Me an First Tie r

[3]
60%

[4]
40%

[5]
20%

[6]
0%
10110
210
310
SDR subspace dim ension (m)SDR( m=625)
UDR(l=200) +SDR
UDR(l=400) +SDR

410

UDR (l= 100)+ SDR
UDR (l= 300)+ SDR
UDR (l= 500)+ SDR

Figure 4. SDR subspace dimension m versus the retrieval
performance in Mean First Tier [%] for several UDR subspacedimensions l.

CONCLUSION

We have used a Semi-Supervised Dimension Reduction (SSDR)
method that exploits a large set of unlabeled models as well as asmall set of labeled models for an effective dimension reduction[3]. We combined the method with the SPRH feature and themultiresolution (MR) feature extraction approach.
Within the Generic Models Track, the Mean First Tier of 35%
for the original MR SPRH increased to 58% after the SSDR. As
expected, the method performed very well for the set classes it istrained for, the Q1, but not very well for the Q2.
Within the CAD Models Track, the Mean First Tier of 36% for
the original MR SPRH increased to 78% after the SSDR to win
the SHREC’08 CAD Model Track with a large (>30% in FirstTier) margin. It appears that a task like the CAD Model Trackbenefit a lot from supervised learning.

[7]

X. He, P. Niyogi, Locality Preserving Projections, Advances in
Neural Information Processing Systems, 16, Vancouver, Canada,(2003)
R. Ohbuchi, T. Takei, Shape-Similarity Comparison of 3D Shapes
Using Alpha Shapes, Proc. Pacific Graphics 2003, pp. 293-302,(2003).
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 byLocally Linear Embedding, Science, 290(5500), pp. 2323-2326,(2000)
P. Shilane, P. Min, M. Kazhdan, T. Funkhouser, The Princeton
Shape Benchmark, Proc. SMI ‘04, pp. 167-178, (2004).
R.C. Veltkamp, F.B. ter Haar, SHREC 2007 3D Shape Retrieval
Contest, Dept of Info and Comp. Sci., Utrecht Univ., Tech. Report
UU-CS-2007-015, (2007)
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).