Yukinori Kurita, Ryutarou Ohbuchi, View-Clustering and Manifold Learning for Sketch-based 3D Model Retrieval,short paper, Proc. CyberWorlds 2013, Oct. 21-23, 2013, Tokyo, Japan

View-Clustering and Manifold Learning for Sketch-based 3D Model Retrieval
Yukinori Kurita

Ryutarou Ohbuchi

Graduate School of Medicine and Engineering
University of Yamanashi
Yamanashi-ken, Japan
g11mk014_AT.yamanashi.ac.jp

Graduate School of Medicine and Engineering
University of Yamanashi
Yamanashi-ken, Japan
ohbuchi_AT.yamanashi.ac.jp

Abstract—Retrieval of 3D models by using 2D sketch query has
recently become an active area of research. However, retrieval
accuracy of the modality is still much lower than using a 3Dmodel example as query. In this paper, we propose analgorithm that employs manifold-learning based dimension
reduction for sketch-based 3D model retrieval. The algorithm
compares multi-view rendering of 3D models with the 2D
sketch. To improve distance computation, a distance metricadapted to data sample distribution is learned by using amanifold-learning algorithm, that is, Locally Linear
Embedding (LLE). In order to lower the cost of training the
LLE, we reduce number of training samples by clustering,either in feature space or in view space. Experimental
evaluation has shown that both view space clustering andfeature space clustering lowers training cost by more than 10times while significantly improving retrieval accuracy. A
compact 50 dimensional feature after the dimension reduction
is much faster to compare, and its retrieval accuracy is 40%
better than the original 30k dimensional feature. In terms of
training cost, view clustering approach costs 20 times less thanthe one using full set of features without clustering.

State of the art sketch-based 3D model retrieval
algorithms still suffer from low retrieval accuracies. A major
cause for this is the gap between sketches and rendered
images of 3D models. Hand-drawn sketches contain stylistic
variation (e.g., shaded, v.s. contour), abstraction (e.g., stick
figure man), inaccuracy and instability (e.g., wobbled lines).
Intra-class variability also exists on the side of 3D models.
Consequently, rendered images of 3D models are often notsimilar to hand-drawn sketches of the “same” class. Simple,
fixed distance metrics used in previous algorithms often fails.
We need a better approach than a simple distance metric, e.g.,
L2-norm, for comparing features of sketches and 3D models.
A possible approach is to use semantic labels, if available inthe database, for supervised or semi-supervised learning.
However, labels are often not available for learning.
In this paper, we propose to use an unsupervised learning
to improve distance metric. From the set of (unlabeled)features extracted from images of 3D models, we try to finda distance metric adapted to the distribution of the features ina high-dimensional feature space. Specifically, we proposed
to employ non-linear manifold-learning based dimension
reduction such as Locally Linear Embedding (LLE) [9].
Manifold learning tries to learn, or estimate, a lowdimensional manifold embedded in a high-dimensional input
feature space. A distance measured along the lower
dimensional manifold (a geodesic-like distance) often
produces higher retrieval accuracy than a simple distance,e.g., L1-norm, in the high-dimensional input feature space.
Furthermore, reduced dimension the processed features leads
to faster comparison among features.
An issue with a manifold learning algorithm such as LLE
is training cost. In case of the LLE, training cost depends on
the size of the training set and the dimensionality of features.
For sketch-based 3D model retrieval, M models in a databaseand Nv views per 3D model means training set size M  N v .
In a bid to reduce training cost of the LLE, we explore two
approaches; (1) View clustering LLE (cv_LLE): cluster
features in view space of each 3D model prior to train LLE,
and (2) Anchor clustering LLE (anc_LLE): cluster features of
all the views of all the 3D models altogether to find “anchor”
features prior to train LLE. We also explore a variation ofquery-by-sketch scheme that uses more than one sketches
per query. To evaluate its effect, we created a multi-sketch
query 3D model retrieval benchmark.
Our experiments showed that the LLE with both viewclustering and anchor clustering produced better accuracy
than without LLE. Retrieval accuracy in Mean Average
Precision (MAP) improved from 0.162 without the LLE to

3D shape retrieval; content-based multimedia retrieval; 3D
geometric modeling; manifold learning.

I. INTRODUCTION
Three-dimensional shape model (3D model) has been
adopted in such wide variety of applications as mechanicaldesign, medical diagnostics, and entertainment (e.g., games).
As number of 3D models explodes, organization andmanagement of 3D models through content-based search andretrieval has become an important subject of study.
3D shape models may be queried by 3D model example
or by textual tags. But a 3D model appropriate for a querymay not be available and 3D models usually has no
keywords attached. One could also use photograph of a real
object as a query, but such an object may not be around. A
viable alternative in querying 3D shape models is to use ahand-drawn 2D sketch as the query [13][11][2][10]. With
tablets and phones having touch and/or pen interface
everywhere, this is a very attractive alternative.
Sketch-based 3D model retrieval algorithms compare a
2D line-drawing sketch with a 3D shape model by
converting the 3D model into dozens of 2D images renderedfrom multiple viewpoints. The rendering often tries to mimicline-drawing, e.g., by using suggestive contour rendering
algorithm [1]. Then, a feature extracted from the sketch iscompared to features extracted from the multi-view rendered
images of the 3D models.

Yukinori Kurita, Ryutarou Ohbuchi, View-Clustering and Manifold Learning for Sketch-based 3D Model Retrieval,short paper, Proc. CyberWorlds 2013, Oct. 21-23, 2013, Tokyo, Japan
0.215 with the view-clustering LLE. Furthermore, twoclustering-based methods did better than the LLE that spent along time to learn the manifold from all the features.
Meanwhile, dimension of feature is reduced from 30k to
mere 50, leading to much faster search through the database.
As expected, using multiple sketches per query did improve
retrieval accuracy, and the improvements are more notable if
multiple-sketch query is combined with dimension reduction
by using anchor-clustering LLE or view-clustering LLE.
We will describe the proposed algorithm in the next
section, followed by description of experiments and result in
Section III. We conclude the paper in Section IV.

(4) anc_LLE: This approach uses k-means algorithm, withk  N anc , to cluster M  N v per-view features of 3D models
in a database at once to find N anc  M  Nv “anchor” features(Figure 2). These Nanc anchor features, found as centroids ofclusters, are used to train the LLE. Similar approach is usedpreviously by [3] and [7].
M  Nv per-view
featuresNcv features per 3D model
after view clusteringM  Ncv
clustered-view

II. ALGORITHM
Our sketch-based 3D model retrieval algorithm converts
both query sketch and 3D model into silhouette images forimage-based comparison. Silhouette, instead of suggestive
contour, is chosen as the middle ground as SIFT feature [8]performed better on silhouettes than on line drawings.
A 3D model placed at coordinate origin is rendered fromNv viewpoints spaced uniformly in solid angle. We use
Nv=42 in the experiments below, after [4]. From eachsilhouette image, the algorithm extracts SIFT features
densely sampled on or around the silhouette, as with our BFDSIFT algorithm [4]. For 3D models, a set of SIFT features
extracted from each silhouette image is integrated into a perviewpoint 3D model feature by using Bag-of-Features (BoF)
approach. For faster visual vocabulary (i.e., visual codebook)learning and vector quantization, the algorithm uses ERCTree [5] clustering algorithm. A 3D model is described by aset of Nv per-view features.
To extract a feature from a sketch, the line-drawing
sketch is converted into a silhouette-like image. To do so, thealgorithm first tries to close gaps in lines by applying dilation
operation. Then, area-fill is applied to create silhouette-like
images out of the sketch. This process succeeds on most, but
not all, of the sketches. After converting to silhouette,densely sampled SIFT features are are integrated into afeature vector per sketch by using the same codebook
learned from silhouette images of 3D models. Both sketchfeature and per-view 3D model feature have dimensionalityof 30k, typical of BoF histograms.
Our proposed algorithm uses LLE to learn a low
dimensional manifold on which distance is computed. To
reduce the cost of LLE training, we employ two clusteringbased sample reduction algorithms. We compare following
four methods for distance computation.
(1) Baseline: Baseline algorithm without dimension
reduction.
(2) LLE: LLE is trained by using all the M  N v features tofind the low-dimensional manifold.
(3) cv_LLE: This approach tries to reduce Nv for each 3Dmodel by clustering (Figure 1). The algorithm first computes
many (Nv=42) per-view features. Then, k-means clustering isapplied to find N vc  N v “synthetic” viewpoints by settingk  N vc . Total number of features per database to be learned
by LLE is thus reduced to M  N vc .

M=4, Nv=6

Ncv=2

M  Ncv  8

Figure 1. View clustering: For each 3D model, Nv per-view features are
clustered into k<Nv distinct “synthetic views”.

M  Nv per-view
featuresNanc features per database
after anchor clustering

Nanc anchor
features

M=4, Nv=6

Nanc=10Figure 2. Anchor clustering: All the M  Nv features extracted from all
the models are clustered into Nanc  M  Nv anchor features.

To reduce dimension of features using the LLE, thefeature is projected onto the low-dimensional manifold foundby training the LLE. However, the LLE can’t handle out-ofsample features. Thus, low-dimensional manifold isapproximated by using the RBF-network, as proposed by He,
et al [6].
For both cv_LLE and anc_LLE, we used k-means cluster
centers as new set of features. One could do otherwise, forexample, one could select, for each cluster, one of original
features closest to the computed centroid. We decided to use
centroids since centroids produced better retrieval accuracy,esp. for cv_LLE, than using one of original features.
To compute distance among a sketch feature xp and perview feature xq of 3D models, all the methods (1)~(4) use
Kullback Leibler Divergence (KLD) below.
mx 
D KLD  x p , x q     x p ,i  x q ,i  log  p ,i 
x 
i 1
 q ,i (1)

An overall distance between a sketch and a 3D model isthe average of all the distances from the sketch feature to all
the features associated with the 3D model. For example, forthe cv_LLE, it is the average of Ncv distances from the sketch
to the Ncv (synthetic view) features of the 3D model.
III. EXPERIMENTS AND RESULTS
We conducted experiments to compare evaluate three
LLE-based algorithm for their retrieval accuracy andcomputational cost. For the cv_LLE and the anc_LLE,
influences of Ncv and Nanc are evaluated. We also evaluatedeffectiveness of multi-sketch query.

Yukinori Kurita, Ryutarou Ohbuchi, View-Clustering and Manifold Learning for Sketch-based 3D Model Retrieval,short paper, Proc. CyberWorlds 2013, Oct. 21-23, 2013, Tokyo, Japan

1.
2.

Present a 3D model to the subject by using a very
simple interactive viewer that is capable of usercontrolled rotation of the model.
Ask subject to draw, using a pen tablet, three views of
the 3D model.

We asked 10 subjects to draw 3 sketches per 3D modelfor the 160 models in the database. Thus, we have 160 sets ofqueries, each having three sketches (that is, total of 480
sketches). Some of the experiments below used all the 3sketches per query, while other experiments used only one of
the three sketches per query. If only one of the sketches isused as a query in an experiment, the sketch having thesmallest ID number is selected. Table I shows examples of
3D models and their respective query sketches drawn by the
subjects.
TABLE I.

EXAMPLES OF SKETCHES IN THE BENCHMARK (RIGHT) AND
3D MODELS (LEFT) SHOWN AS EXAMPLES TO SUBJECTS.

SampleSketch 1

Sketch 2

Sketch 3

0.30
0.25
0.20
MAP

A. Multi-sketch query benchmark
We created a sketch-based 3D model retrieval benchmark
whose query sketch set consists of 3 sketches per query. Thatis, an object the user wish to retrieve is illustrated by using 3
sketches, typically from different viewpoints. As the retrieval
target, we selected M=497 models (classified into 40
categories) from the 907 models (classified into 92
categories) of the Princeton Shape Benchmark (PSB) test set[12]. We used the subset since some of the PSB models are
not conducive to sketching. Three sketches per 3D model are
generated as follows;

information is inevitably lost. However, as Figure 3 shows,
retrieval accuracy improved as the number Ncv decreased.
The clustering might have eliminated spurious views andthus spurious matches.

0.15
0.10

cv_LLE
LLE
Orig.

0.05
0.00
5

10

15

20

25

Ncv
Figure 3. Number of view clusters and retrieval accuracy.

C. Anchor LLE
With M=497 models and Nv=42, there are 20,874 perview image features of 3D models in the database. We
clustered them down to Nanc=100~2000 using the anc_LLE,
for retrieval experiments. As Figure 4 shows, retrieval
accuracy stayed pretty much the same until it went down a
bit at Nanc =100.
0.30
0.25
0.20
MAP

LLE has a set of parameters, the neighborhood size knn toform a graph representing manifold, the size of reduced
dimension R, and RBF kernel radius C. We fixed k=500,
R=50, and C=250 for the experiments below.
As the index of retrieval accuracy, we use Mean Average
Precision (MAP).

0.15
0.10

anc_LLE
LLE
Orig.

0.05
0.00
0

500

1000

Nanc

1500

2000

Figure 4. Number of anchors and retrieval accuracy.

B. View clustering (cv_LLE)
In this experiment, we evaluated the impact of number ofclustered views Ncv on retrieval accuracy.
One might assume that clustering Nv=42 per-view
features down to a smaller number Ncv of “synthetic”
viewpoints would negatively impact retrieval accuracy, as

D. Multi-sketch query and manifold learning
As we assumed, using multiple sketches per query did
improve retrieval accuracy as shown in Figure 5. It is a tradeoff for a user; accuracy or cost of drawing more sketches.
It appears that performance improvement due to multiple
query sketches is more prominent for the cv_LLE and theanc_LLE, in which distance metric learning is more effective,
than the other two cases. We also observe that the anc_LLE
appears to work better than the cv_LLE for multiple sketches
per query case. Tetrieval accuracy for the 1 sketch query is
about equal among cv_LLE and anc_LLE. However, for the
3 sketch query, accuracy of the anc_LLE is better than the
cv_LLE.
E. Number fo sketches, retrieval accuracy, andcomputational cost
Table II. lists computational costs of four methods alongwith their retrieval accuracies measured in MAP. This set ofexperiments is done by using 3 sketches per query.

Yukinori Kurita, Ryutarou Ohbuchi, View-Clustering and Manifold Learning for Sketch-based 3D Model Retrieval,short paper, Proc. CyberWorlds 2013, Oct. 21-23, 2013, Tokyo, JapanIf we compare retrieval accuracy, methods using the LLE
did better than the one (Baseline) without the LLE. Of thethree cases that employed the LLE, those using training
sample reduction (the cv_LLE and the anc_LLE) produced
higher accuracy than the one without, that is, the LLE traind
by using all the training samples. For this 3 sketch query case,
MAP scores for the cv_LLE and the anc_LLE are 40% and
47% better, respectively, than the Baseline without the LLE.
Dimension reduction impacted positively on the retrieval
cost. Using compact 50-dimensional features, the LLE, thecv_LLE, and the anc_LLE took only 1/4[s] per query to
search through the database. In comparison, the Baseline
using the 30k dimensional features took nearly 20[s].
As for the training cost, clustering based approaches, theanc_LLE and the cv_LLE did significantly reduce the
combined cost of LLE and RBF approximation. However,total cost of preprocessing a database must include the costof clustering for the cv_LLE and the anc_LLE. The cv_LLE
has an advantage here, as it is very quick to cluster 42
features. In comparison, the anc_LLE took a very long time,
2,489 min or about 40 hours, to cluster 20,874 per-view
features in the entire database. Thus for the total cost of
preprocessing, the cv_LLE wins handily; the cv_LLE took
223 min while the anc_LLE took 2,489 min to preprocess.
Overall, for this benchmark dataset, cv_LLE is the best
trade-off among retrieval accuracy, retrieval cost, anddatabase preprocessing cost. For databases that are
significantly larger, a combination of approaches used in the
cv_LLE and the anc_LLE may be necessary.
Base1

0.162

Base3

0.175

LLE1

0.173

LLE3

0.188

cv_LLE1

0.215

cv_LLE3

0.246

anc_LLE1

0.213

anc_LLE3

0.257

0.00

0.10

0.20

0.30

MAP
Figure 5. Retrieval accuracy of 4 algorithms measure by using 1 sketch(suffix 1) and 3 sketches (suffix 3) as query.
TABLE II.
COMPUTATION TIMINGS. TIME TO PRE-PROCESS DATABASE(I.E., CLUSTERING, LLE, AND RBF-NETWORK APPROXIMATION) ARE INMINUTES, WHILE TIME TO RETRIEVE SINGLE QUERY IS IN SECONDS.
3 sketches
per query

Preprocessing database
[min]
LLE+
Total
k-means
RBF

Baseline.

Retrieval(per query)[s]Distance
comp.
19.62

Retrievalaccuracy
[MAP]
0.175

LLE

0.00

4350.654350.65

0.24

0.188

cv_LLE

1.95

221.15223.10

0.26

0.246

anc_LLE2489.4829.95

2519.43

0.24

0.257

IV. CONCLUSION AND FUTURE WORKTo improve retrieval accuracy and to reduce cost offeature comparison of sketch based 3D model retrieval, thispaper explored manifold learning based dimension reductionof per-view image features by using the LLE [9]. We also
explored effect of multiple-sketch query. To this end, we
created a benchmark having a set of multiple sketch queries.
To reduce cost of training the LLE, we explored two
approaches to reduce number of training samples of the LLE.
The anc_LLE clusters the entire features set of the databaseat once, while the cv_LLE clusters, for each 3D model, perview features of the 3D model.
Experimental evaluation showed that clustering based
reduction of features, both the cv_LLE and the anc_LLE, do
reduce LLE training cost while significantly improving
retrieval accuracy. At the same time, dimension reduction
positively impacted the cost of comparing a sketch to 3Dmodels for retrieval. The experiments also showed thatmulti-sketch query and manifold learning based dimension
reduction work synergistically to improve retrieval accuracy.
ACKNOWLEDGEMENTS
Funding provided by the Ministry of Education, Culture,
Sports, Sciences, and Technology of Japan (No. 18300068).
REFERENCE[1]

D. DeCarlo, A. Finkelstein, S. Rusinkiewicz, A. Santella, Suggestive
Contours for Conveying Shape, ACM TOG, 22(3), pp. 848-855,(2003).
[2] M. Eitz, R. Richter, T. Boubekeur, K. Hildebrand, and M. Alexa,
Sketch-Based Shape Retrieval, ACM TOG, 31(4) pp.1-10, (2012).
[3] M. Endoh, T. Yanagimachi, R. Ohbuchi, Efficient manifold learningfor 3D model retrieval by using clustering-based training sample
reduction, Proc. IEEE ASSP 2012, pp. 2345-2348, (2012).
[4] T. Furuya, R. Ohbuchi, Dense sampling and fast encoding for 3Dmodel retrieval using bag-of-visual features, ACM CIVR 2009, Article
No. 26, (2009).
[5] P. Geurts, D. Ernst, L. Wehenkel, Extremely randomized trees,
Machine Learning Journal, 63(1), pp. 3-42 (2006).
[6] X. He, W-Y. Ma, H-J. Zhang, Learning an Image Manifold forRetrieval, Proc. ACM Multimedia 2004, 17-23 (2004)[7] W. Liu, J. Wang, S-F. Chang, Hashing with graphs, Proc. ICML 2011,(2011).
[8] D. G. Lowe, Distinctive Image Features from Scale-Invariant
Keypoints, Int’l Journal of Computer Vision, 60(2), November 2004.
[9] S. T. Roweis, L. K. Saul, Nonlinear Dimensionality Reduction by
Locally Linear Embedding, Science, 209(22), pp. 2323–2326, (2000).
[10] J. M. Saavedra, B. Bustos, T. Schreck, S. M. Yoon, M. Scherer,
Sketch-based 3D model retrieval using keyshapes for global and local
representation, Proc. 5th Eurographics conference on 3D Object
Retrieval (EG 3DOR) 2012, pp. 47-50, (2012).
[11] T. Shao, W. Xu, K. Yin, J. Wang, K. Zhou, B. Guo, Discriminativesketch-based 3D model retrieval via robust shape matching,Computer Graphics Forum, 30(7), (also as Proc. Pacific Graphics
2011) , (2011).
[12] P. Shilane, P. Min, M. Kazhdan, T. Funkhouser, The Princeton ShapeBenchmark, SMI ‘04, pp. 167-178, (2004).
http://shape.cs.princeton.edu/benchmark/[13] S. M. Yoon, M. Scherer, T. Schreck, A. Kuijper, Sketch-based 3Dmodel retrieval using diffusion tensor fields of suggestive contours.
ACM Multimedia 2010, pp. 193-200, (2010).