Computer Vision and Image Understanding 119 (2014) 57–80

Contents lists available at ScienceDirect

Computer Vision and Image Understanding
journal homepage: www.elsevier.com/locate/cviu

A comparison of methods for sketch-based 3D shape retrieval q
Bo Li a,b, Yijuan Lu a,⇑, Afzal Godil b, Tobias Schreck c, Benjamin Bustos d, Alfredo Ferreira e,
Takahiko Furuya f, Manuel J. Fonseca e, Henry Johan g, Takahiro Matsuda f, Ryutarou Ohbuchi f,
Pedro B. Pascoal e, Jose M. Saavedra d,ha

Department of Computer Science, Texas State University, San Marcos, USA
Information Technology Laboratory, National Institute of Standards and Technology, Gaithersburg, USA
Computer and Information Science, University of Konstanz, GermanydDepartment of Computer Science, University of Chile, Chilee
Instituto Superior Técnico/ Technical University of Lisbon/ INESC-ID, PortugalfComputer Science and Engineering Department, University of Yamanashi, Yamanashi, Japang
Visual Computing, Fraunhofer IDM@NTU, SingaporehComputer Vision Research Group, ORAND S.A., Santiago, Chilebca r t i c l e

i n f oArticle history:
Received 23 September 2013
Accepted 22 November 2013
Available online 7 December 2013
Keywords:
Sketch-based 3D model retrieval
Evaluation
SHREC contest
Large-scale
Benchmarka b s t r a c t
Sketch-based 3D shape retrieval has become an important research topic in content-based 3D object
retrieval. To foster this research area, two Shape Retrieval Contest (SHREC) tracks on this topic have beenorganized by us in 2012 and 2013 based on a small-scale and large-scale benchmarks, respectively. Six
and ﬁve (nine in total) distinct sketch-based 3D shape retrieval methods have competed each other inthese two contests, respectively. To measure and compare the performance of the top participating
and other existing promising sketch-based 3D shape retrieval methods and solicit the state-of-the-art
approaches, we perform a more comprehensive comparison of ﬁfteen best (four top participating algorithms and eleven additional state-of-the-art methods) retrieval methods by completing the evaluationof each method on both benchmarks. The benchmarks, results, and evaluation tools for the two tracks
are publicly available on our websites [1,2].
Ó 2013 Elsevier Ltd. All rights reserved.

1. Introduction
Sketch-based 3D model retrieval is focusing on retrieving relevant 3D models using sketch(es) as input. This intuitive and convenient scheme is easy for users to learn and use to search for 3Dmodels. It is also popular and important for related applications
such as sketch-based modeling and recognition, as well as 3D
animation production via 3D reconstruction of a scene of 2D
storyboard [3].
However, most existing 3D model retrieval algorithms target
the Query-by-Model framework, that is, using existing 3D models
as queries. In the areas of content-based 2D image retrieval andimage synthesis, sketch-based methods have been addressed forsome time now. In 3D model retrieval, on the other hand, lesswork has to date considered the Query-by-Sketch framework. In
fact, it is a non-trivial task to perform sketch-based 3D model retrieval and also more difﬁcult compared with the Query-by-Modelq

This paper has been recommended for acceptance by Nicu Sebe.

⇑ Corresponding author. Address: 601 University Drive, Department of Computer
Science, Texas State University, San Marcos, TX 78666, United States. Fax: +1 512
245 8750.
E-mail address: lu@txstate.edu (Y. Lu).
1077-3142/$ - see front matter Ó 2013 Elsevier Ltd. All rights reserved.
http://dx.doi.org/10.1016/j.cviu.2013.11.008

case. This is because there exists a semantic gap between thesketches humans draw and the 3D models in the database, implying that the structure of the query and target objects differ. Specifically, target objects are typically given as precisely modeled
objects, while the query sketch may differ drastically in level of detail, abstraction, and precision. In addition, until now there is nocomprehensive evaluation or comparison for the large number ofavailable sketch-based retrieval algorithms. Considering this, weorganized the Shape Retrieval Contest (SHREC) 2012 track on
Sketch-Based 3D Shape Retrieval [1,4], held in conjunction withthe ﬁfth Eurographics Workshop on 3D Object Retrieval, to foster
this challenging research area by providing a common small-scale
sketch-based retrieval benchmark and soliciting retrieval resultsfrom current state-of-the-art retrieval methods for comparison.
We also provided corresponding evaluation code for computing a
set of performance metrics similar to those typically used to evaluate Query-by-Model techniques. The objective of this track was toevaluate the performance of different sketch-based 3D model retrieval algorithms using both hand-drawn and standard line drawings sketch queries on a watertight 3D model dataset. Every
participant performed the queries and sent us their retrieval results. We then did the performance assessment.

58

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

A satisfactory success has been achieved in the SHREC’12 sketch
track [4]. However, the contest has limitations in terms of its evaluation of different sketch-based retrieval algorithms based on arather small benchmark and a comparison of a limited number ofmethods. Eitz et al. [5] provided us the largest sketch-based 3D
shape retrieval benchmark until 2012, based on the Princeton
Shape Benchmark (PSB) [6] with one user sketch for each PSB model. However, until now no comparative evaluation has been doneon a very large-scale sketch-based 3D shape retrieval benchmark.
Considering this and encouraged by the successful sketch-based
3D model retrieval track in SHREC’12 [4], in 2013 we organized another track [2,7] with a similar topic in SHREC’13 to further foster
this challenging research area by building a very large-scale benchmark and soliciting retrieval results from current state-of-the-art
retrieval methods for comparison. Similarly, we also provided corresponding evaluation code for computing the same set of performance metrics as the SHREC’12 sketch track. For this track, theobjective was evaluating the performance of different sketchbased 3D model retrieval algorithms using a large-scale handdrawn sketch query dataset for querying from a generic 3D model
dataset.
After ﬁnishing the above two SHREC contests, we have foundthat the participating methods for the two contests are not completely the same, thus a conclusion of the current state-of-the-art
algorithm is still unavailable. In addition, to provide a more complete reference for the researchers in this research direction, it isnecessary to perform a more incisive analysis on different participating methods w.r.t their scalability and efﬁciency performance,
as well as the two benchmarks used in the two contest tracks.
Motivated by the above two ﬁndings, we decided to perform a follow-up study by completing a more comprehensive evaluation ofcurrently available top sketch-based retrieval algorithms on thetwo benchmarks such as to perform a more comprehensive comparison on them and solicit the state-of-the-art approaches. Thus,
we sent invitations to the participants as well as the authors ofrecently published related papers (according to our knowledge)
to ask them to contribute to the new comprehensive evaluation.
Totally, 6 groups accepted our invitations and agreed to submit
their results on schedule. Finally, 15 best-performing methods (4top participating algorithms and 11 additional state-of-the-art approaches; totally 17 runs) from 4 groups successfully submitted
their results, including running results (e.g. retrieval lists and timing information) and method description, which are also available
on the SHREC’12 and SHREC’13 sketch track website [1,2]. After
that, we performed a comparative evaluation on them.
In this paper, we ﬁrst review the related work (w.r.t. techniques
and benchmarks, respectively) in Section 2. Then, in Section 3 weintroduce the two benchmarks (one small-scale and one largescale) used in the two contest tracks. Section 4 gives a brief introduction of the contributors of the paper. A short and concise
description for each contributed method is presented in Section 5.
Section 6 describes the evaluation results of the 15 sketch-based
3D retrieval algorithms on the SHREC’12 small-scale benchmark
and SHREC’13 large-scale benchmark, respectively. Section 7
further comments on the benchmarks and analyzes the contributed algorithms w.r.t the performance they achieved. Section 8
concludes the paper and further lists several future research
directions.

2. Related work
2.1. Sketch-based 3D model retrieval techniques
Existing sketch-based 3D model retrieval techniques can be categorized differently according to dissimilar aspects: Local versus

global 2D features; Bag-of-Words framework versus direct shape feature matching; Fixed views versus clustered views; With versus without view selection. In this section, we will review some typicalrecent work in this ﬁeld.
In 2003, Funkhouser et al. [8] developed a search engine which
supports both 2D and 3D queries based on an extended version of
3D spherical harmonics [9] from 3D to 2D. Yoon et al. [10] andSaavedra et al. [11] developed their sketch-based 3D model retrieval algorithms based on suggestive contours [12] feature views
sampling and diffusion tensor ﬁelds feature representation or
structure-based local approach (STELA). Aono and Iwabuchi [13]proposed an image-based 3D model retrieval algorithm based on
the Zernike moments and Histogram of Oriented Gradient (HOG)features. Eitz et al. [14–16,5,17] implemented their sketch-based
2D/3D object retrieval algorithms by utilizing the Bag-of-Words
framework and local features including HOG and its modiﬁed
versions, as well as a feature named Gabor local line-based feature(GALIF). Shao et al. [18] developed an efﬁcient and robust contourbased shape matching algorithm for sketch-based 3D model retrieval. Li and Johan [19] performed ‘‘View Context’’ [20] based 2D
sketch-3D model alignment before 2D-3D matching based on relative shape context matching [21]. Li et al. [22] further developed asketch-based 3D model retrieval algorithm based on the idea of
performing sketch recognition before sketch-model matching.
Recently, 2D line drawings have also been utilized to reconstruct correspondent 3D models, which often involves sketchbased 3D shape retrieval techniques. Several line drawing-based
reconstruction algorithms [23–25] have been proposed based on
the idea of 2D parts separation, 3D parts search and combination
to create a 3D model based on its 2D line drawing. On the other
hand, Xie et al. [26] developed a sketching-based 3D modiﬁcationand variation modeling interface based on the idea of parts assembly. Further, Sketch2Scene [27] builds a 3D scene based on a 2D
scene sketch by incorporating an analysis of structural context
information among the objects in the 2D scene.
2.1.1. 2D feature views
Matching 3D models with a 2D sketch requires us to sample andrender appropriate 2D feature views of a 3D model for an as accurate as possible feature correspondence between the 2D and 3D
information. In this section, we review typical feature views (someexamples are shown in Fig. 1) that have often been used or are
promising in sketch-based 3D retrieval algorithms.
2.1.1.1. Silhouette view. This is to simply render the black and white
image to represent a view of a 3D model. It has been adopted inseveral latest sketch-based 3D model retrieval algorithms, suchas Kanai [28], Ohbuchi et al. [4], Aono and Iwabuchi [13].
2.1.1.2. Contour or outline feature view. Contours are a serial ofpoints where the surface blends sharply and becomes invisible tothe viewer [12]. They have been utilized in Tatsuma and Aono[29], Aono and Iwabuchi [13], and Li and Johan [19].
2.1.1.3. Suggestive contours feature view [12]. Suggestive contours
are contours in the nearby views, that is, they will become contours after rotating the model a little bit. They have been used in
the following sketch-based 3D model retrieval algorithms: Yoonet al. [10,30], Saavedra et al. [31] and Eitz et al. [5,4] (using both
occluding contours and suggestive contours).
2.1.1.4. Apparent ridges. Apparent ridges [32] are deﬁned as the lociof points that maximize a view-dependent curvature and they areextensions beyond ridge and valleys [33]. They have been utilizedby Eitz et al. [14] in their retrieval algorithm.

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

59Fig. 1. Example feature views: (a) A horse model (in curvature view); (b) Silhouette feature view; (c) Contours (green) and suggestive contours (blue) feature views; (d)Apparent ridges feature view. (For interpretation of the references to color in this ﬁgure legend, the reader is referred to the web version of this article.)

2.1.1.5. Other more sophisticated 3D line drawings. Recently, quite afew new and more sophisticated 3D line drawings have been proposed. We regard them as promising in achieving even better results compared with those features mentioned above. They
include photic extremum lines (PEL) [34] and its GPU-accelerated
version GPEL [35], demarcating curves [36], perceptual-saliency
extremum lines [37], Laplacian lines [38], Difference-of-Gaussian(DoG)-based 3D line drawing [39], as well as the latest multi-scale
curves on 3D surface [40]. For the classiﬁcation and characteristicsof the above methods, please refer to the survey written by Doug
DeCarlo [41].
2.1.2. 2D shape descriptors
For a sketch-based 3D model retrieval algorithm, developing or
selecting an appropriate 2D shape descriptor is an important partto represent a 2D sketch as well as the 2D feature views of a 3Dmodel, such as those mentioned in Section 2.1.1. In this section,
we present several typical and promising 2D shape descriptors
for sketch-based retrieval.
Fourier descriptor (FD) is an important shape descriptor and has
been successfully applied in many pattern recognition related
applications such as shape analysis, classiﬁcation and retrieval aswell as character recognition [42]. However, it assumes that we
can get the boundary information of a shape beforehand and it
does not consider the internal information of the shapes. Considering the above limitations, Zhang and Lu [43,44] extended the Fourier descriptor and proposed a more robust and accurate shapedescriptor called generic Fourier descriptor (GFD) which applies
Fourier transform on a polar-raster sampled shape image.
Zernike moments feature [45] is one typical moment descriptor
that outperforms other moments in terms of performance in different applications. For example, 3D Zernike moments [46] feature
has been developed to deal with 3D model retrieval. Revaud
et al. [47] proposed an improved Zernike moments [45] comparator which considers not only the magnitude of the moments (classic Zernike moments comparator) but also their phase information.
They demonstrated its better performance than the classic one.
Local binary pattern [28,48] divides the surrounding regions ofany pixel in a binary image into eight directions, computes the percentages of the pixels falling in each bin and regards this distribution information as a local binary pattern (LBP) encoded using an
8-bit binary number, and ﬁnally represents the whole image basedon the statistical distribution of all the local binary patterns. It canbe used to measure the similarity between the 2D sketch after a
pre-processing and the rendered feature images of a 3D model.
Shape context [21] is a log-polar histogram and deﬁnes the relative distribution of other sample points with respect to a sample
point. It has been successfully applied in diverse tasks. The default
shape context deﬁnition partitions the surrounding area of a sample point of a 2D shape into 5 distance bins and 12 orientation bins.
Thus, the shape context is represented by a 5  12 matrix. Different points have different shape context features in one shape andsimilar points in two similar shapes usually have similar shapecontext features. Shape context is scale and transformation-invariant but not rotation-invariant. To achieve the property of rotation
invariance, in [21] a relative frame is deﬁned by adopting the local
tangent vector at each point as the reference x axis for angle computation and we refer to it as relative shape context. In addition,
Edge histogram [49] can be regarded as an alternative of shapecontext for sketch representation.
Scale-invariant feature transform (SIFT) [50] feature together
with the Bag-of-Features (BoF) framework has many applications
in various computer vision research ﬁelds. To optimize the search
accuracy, efﬁciency and memory usage in a large scale image retrieval scenario which utilizes SIFT features and BoF framework,
Jégou et al. [51] proposed a new compact image representation
to aggregate SIFT local descriptors. It achieves a signiﬁcantly better
performance than BoF on condition that the feature vectors usedhave the same size. In addition, Ohbuchi et al. [52,53] proposedseveral extended versions of SIFT feature for 3D retrieval, such as
Dense SIFT (DSIFT), Grid SIFT (GSIFT) and One SIFT (1SIFT) which
also have achieved good retrieval performance.
Histogram of Oriented Gradients (HOG) [54] was ﬁrst proposed
for human detection based on the local and combinational orientation and magnitude distribution of the gradients in each grid of animage. According to the characteristics of a sketch, HOG has been
modiﬁed and applied in sketch-based 2D and 3D object retrieval.
For example, to perform a large-scale 3D model retrieval, Eitz
et al. [17] utilized a simpliﬁed HOG (SHOG) feature (ﬁrst proposedin [16]), which only concerns the orientation information. HOG
was also successfully used in sketch-based image retrieval, for instance, like [49]. Eitz et al. [16] also performed a comparative evaluation on several 2D shape descriptors for sketch-based image
retrieval, including HOG, SHOG, local shape context and a modiﬁed
version of shape context named ‘‘Spark’’ feature.
Other recent 2D shape representations or transforms include
tensor representation, which was used in Yoon et al. [10] and Eitz
et al. [49], as well as the latest feature Gabor local line-based feature (GALIF) [5] which has demonstrated outperforming performance than SIFT [50], Spherical Harmonics [8], and Diffusion
Tensor representation [10]. Motivated by the idea of Curvelet
transform [55], GALIF is a transformation type feature and it
approximates Curvelet by utilizing Gabor ﬁlters which only respond to some special frequency and orientation.
2.2. Sketch-based 3D shape retrieval benchmarks
2.2.1. Snograss and Vanderwart’s standard line drawings (1980)
Snograss and Vanderwart [56] built a dataset of 260 standardline drawings. These sketches were originally designed for experiments in cognitive psychology. They were carefully designed to becomparable regarding four variables fundamental to memory andcognitive processing, including name agreement, image agreement, familiarity, and visual complexity. Their main target is to explore the correlation among those four cognition factors and thispioneer work was followed by several research work with respect

60

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

to different languages such as French [57,58], Spanish [59] and Portuguese [60].
2.2.2. Cole et al.’s line drawing benchmark (2008)
Cole et al. [61] built a line drawing benchmark (together withcorresponding 3D models) such as to study the relationship between human-drawn sketches and computer graphics featurelines. They created line drawings of 12 models including bones,
mechanical parts, tablecloths and synthetic shapes. However,
either the number of sketches or that of models is very small.
2.2.3. Saavedra and Bustos’s sketch dataset (2010)
Saavedra and Bustos [62] built a small sketch dataset (rotation
variations of 53 sketches) to test the performance of their sketchbased image retrieval algorithm.
2.2.4. Yoon et al.’s sketch-based 3D model retrieval benchmark (2010)
To perform sketch-based 3D model retrieval and evaluate theiralgorithm, Yoon et al. [10] built a benchmark which contains 250
sketches for the 260 models of the Watertight Model Benchmark(WMB) dataset [63] and the sketches and models are categorized
into 13 classes.
2.2.5. Eitz et al.’s sketch-based shape retrieval benchmark
Eitz et al. [5] built a sketch dataset containing one sketch foreach of the 1814 models in the Princeton Shape Benchmark (PSB)[6] dataset.
2.2.6. Eitz et al.’s sketch recognition benchmark (2012)
Eitz et al. [17] also built a sketch recognition benchmark whichcontains 20000 sketches, divided into 250 classes, each with 80
sketches. Currently, it is the most comprehensive sketch dataset.
2.2.7. Comparison with our two benchmarks
The ﬁrst three datasets or benchmarks cannot be used directlyfor our purpose while the fourth also has its limitations, such as
the bias of different number of sketches per class and lacking ofcomprehensiveness. Considering these, we have built the
SHREC’13 Sketch Track Benchmark using 7200 sketches selectedfrom the large sketch collection presented in [17] as query objects,
and the SHREC’12 Sketch Track Benchmark which was extended
from Yoon et al.’s benchmark. These two benchmarks either eliminate certain bias or add new evaluation datasets, thus are morecomprehensive and objective when used to evaluate existing or
newly developed sketch-based 3D model retrieval algorithms.
3. Benchmarks
In the SHREC’12 and SHREC’13 sketch tracks, we have built two
sketch-based 3D model retrieval benchmarks, featuring smallscale and large-scale benchmarks, and sketches without and withinternal features, respectively. In this section, we also introduce
several evaluation metrics that are generally used to measure theretrieval performance of a sketch-based 3D model retrieval
algorithm.
3.1. Small-scale benchmark: SHREC’12 Sketch Track Benchmark
3.1.1. 3D target dataset
The 3D benchmark dataset is built based on the WatertightModel Benchmark (WMB) dataset [63] which has 400 watertightmodels, divided into 20 classes, with 20 models each. The 3D target
dataset contains two versions: Basic and Extended. The Basic version comprises 13 selected classes from the WMB dataset witheach 20 models (in summary, 260 models). In the basic version,

all 13 classes are considered relevant for the retrieval challenge.
Fig. 2(a) shows one typical example for each class of the basic
benchmark. The Extended version adds to the basic version all
remaining 7 classes of the WMB dataset (each 20 models). These
additional classes, however, are not considered relevant for the retrieval challenge but added to increase the retrieval difﬁculty of thebasic version. Fig. 2(b) illustrates typical examples for theseremaining 7 irrelevant classes. The extended version is utilized totest the scalability of a sketch-based retrieval algorithm.
3.1.2. 2D query set
The 2D query set comprises two subsets, falling into two different types.
 Hand-drawn sketches. We utilize the hand-drawn sketch datacompiled by TU Darmstadt and Fraunhofer IGD [10]. It contains
250 hand-drawn sketches, divided into 13 classes. The querysketches were produced by a number of students asked to draw
objects from the given categories without any further instructions. The sketches represent a spectrum of different sketchingstyles and qualities and are used to simulate retrieval by nonexpert users. They feature sketches with few internal featurelines. One typical example for each class is shown in Fig. 2(c).
 Standard line drawings. We also select 12 relevant sketchesfrom the Snograss and Vanderwart’s standard line drawings
dataset [56]. Note that just one sketch per query class is available in these drawings. Note that these queries are meant as apreliminary ﬁrst step in eventually building a benchmark which
controls for sketch standardization. Owing to their professional
design quality the sketches can be considered representing‘‘ideal’’ queries. Some examples are shown in Fig. 2(d).
In the SHREC’12 sketch track, the two subsets were needed to
be tested separately. However, users can also form a query set bycombining these two to form a query set which contains diverse
types of sketches.
3.2. Large-scale benchmark: SHREC’13 Sketch Track Benchmark
3.2.1. Overview
Our large-scale sketch-based 3D model retrieval benchmark [2]is built on the latest large collection of human sketches collectedby Eitz et al. [17] and the well-known Princeton Shape Benchmark(PSB) [6]. To explore how humans draw sketches and for the purpose of human sketch recognition using a crowdsourcing approach,they collected 20000 human-drawn sketches, categorized into 250
classes, each with 80 sketches. This sketch dataset is regarded as
exhaustive in terms of the number of object categories. Furthermore, it represents a basis for a benchmark which can provide anequal and sufﬁciently large number of query objects per class,avoiding query class bias. In addition, the sketch variation withineach class is high. Thus, we believe a new sketch-based 3D model
retrieval benchmark built on [17] and the PSB benchmark [6] canfoster the research of sketch-based 3D object retrieval methods.
This benchmark presents a natural extension of the benchmark
proposed in [5] for very large-scale 3D sketch-based retrieval.
PSB is the most well-known and frequently used 3D shapebenchmark and it also covers many commonly occurring objects.
It contains two datasets: ‘‘test’’ and ‘‘train’’, each has 907 models,
categorized into 92 and 90 distinct classes, respectively. Most of
the 92 and 90 classes share the same categories with each other.
However, PSB has quite different numbers of models for different
classes, which is a ‘‘target class’’ bias for retrieval performance
evaluation. For example, in the ‘‘test’’ dataset, the ‘‘ﬁghter_jet’’class has 50 models while the ‘‘ant’’ class only has 5 models. In[5] the query sketch dataset and the target model dataset sharethe same distribution in terms of number of models in each class.

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

61

Fig. 2. Typical 3D model and 2D sketch for each class of the SHREC’12 Sketch Track Benchmark.

Considering the above fact and analysis, we build the benchmark (available in [2]) by ﬁnding common classes in both thesketch [17] and the 3D model [6] datasets. We search for the relevant 3D models (or classes) in PSB and the acceptance criterion is
as follows: for each class in the sketch dataset, if we can ﬁnd therelevant models and classes in PSB, we keep both sketches andmodels, otherwise we ignore both of them. In total, 90 of 250 classes, that is 7200 sketches, in the sketch dataset have 1258 relevant
models in PSB. The benchmark is therefore composed of 7200
sketches and 1258 models, divided into 90 classes. Fig. 3 shows
example sketches and their relevant models of 18 classes in thebenchmark. We randomly select 50 sketches from each class fortraining and use the remaining 30 sketches per class for testing,while the 1258 relevant models as a whole are remained as thetarget dataset. The SHREC’13 sketch track participants need to submit results on the training and testing datasets, respectively. To

provide a complete reference for the future users of our benchmark, we evaluate the contributed algorithms on both the testingdataset (30 sketches per class, totally 2700 sketches) and the complete benchmark (80 sketches per class, 7200 sketches).
3.2.2. 2D sketch dataset
The 2D sketch query set comprises the selected 7200 sketches(90 classes, each with 80 sketches), which have relevant models
in PSB [6], from Eitz et al.’s [17] human sketch recognition dataset.
These sketches often contain internal feature lines. One example
indicating the variations within one class is demonstrated in Fig. 4.
3.2.3. 3D model dataset
The 3D model dataset is built on the PSB dataset [6]. The target
3D model dataset comprises 1258 selected models distributed on
90 classes.

Fig. 3. Example 2D sketches and their relevant 3D models in the SHREC’13 Sketch Track Benchmark.

62

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

Fig. 4. An example of intra-class variations of hand-drawn sketches: 35 sketches of the ‘‘cell phone’’ class.

Finally, it is normalized by the optimal DCG,

3.3. Evaluation metrics
To have a comprehensive evaluation of a sketch-based 3D model retrieval algorithm based on the above two benchmarks, we employ seven commonly adopted performance metrics in Query-byModel retrieval techniques. They are Precision-Recall plot (PR),Nearest Neighbor (NN), First Tier (FT), Second Tier (ST), E-Measures(E), Discounted Cumulated Gain (DCG) [6] and Average Precision(AP) [64]. We also have developed the code [1,2] to compute themfor the two benchmarks. Their meaning and deﬁnitions are listed
below.
 Precision-Recall plot (PR): Precision measures the percentageof the relevant models in the top K (16 K 6 n) retrieval list,
where n is the total number of models in the dataset. Recall calculates how much percentage of the relevant class in the database has been retrieved in the top K retrieval list.
 Nearest Neighbor (NN): NN is the precision of top 1 retrieval
list.
 First Tier (FT): Assume there are C relevant models in the database, FT is the recall of the top C-1 retrieval list.
 Second Tier (ST): Similarly, ST is the recall of the top 2(C-1)
retrieval list.
 E-Measure (E): E-Measure is motivated by the fact that people
are more interested in the retrieval results in the ﬁrst page.
Thus, it is deﬁned [6] to measure the retrieval performance ofthe top 32 models in a retrieval list,

2
:
1
þ
P
R

E¼1

ð1Þ

 Discounted Cumulated Gain (DCG): Since relevant models
appear in the front of the retrieval list are more important thanthose in the rear of the list, DCG is deﬁned as the normalized
summed weighted value related to the positions of the relevant
models. A retrieval list R is ﬁrst transformed into a list G, where
Gi ¼ 1 if Ri is a relevant model, otherwise Gi ¼ 0. DCG is thendeﬁned as follows.

(
DCGi ¼G1

i¼1

DCGi1 þ lgGi i otherwise
2

ð2Þ

DCG ¼

DCGn
PC

1þ

1
j¼2 lg2 jð3Þwhere n is the total number of models in the dataset and C is thetotal number of relevant models in the class.
 Average Precision (AP): AP is to measure the overall performance and it combines precision, recall as well as ranking positions. It can be computed by counting the total area under thePrecision-Recall plot curve. A good AP needs both high recall
and precision.
4. Contributors
The ﬁrst four authors of this paper built the above two benchmarks, and organized the SHREC’12 and SHREC’13 tracks on the topic of sketch-based 3D retrieval and this follow-up study. Totally, 4groups successfully contributed the following 15 methods (17runs), including 4 top algorithms in the SHREC’12 and SHREC’13
sketch tracks (performance of other participating methods can befound in [1,4,2,7]) which are SBR-2D-3D, SBR-VC, BF-fDSIFT (amodiﬁed version of DSIFT) and FDC, as well as 11 additional
state-of-the-art methods.
 BF-fDSIFT, BF-fGALIF, BF-fGALIF + BF-fDSIFT; CDMR-BF-fDSIFT,
CDMR-BF-fGALIF, CDMR-BF-fGALIF + CDMR-BF-fDSIFT; UMRBF-fDSIFT, UMR-BF-fGALIF and UMR-BF-fGALIF + UMR-BFfDSIFT submitted by Takahiko Furuya, Takahiro Matsuda, andRyutarou Ohbuchi from the University of Yamanashi, Japan(Section 5.1).
 SBR-2D-3D_NUM_100, SBR-2D-3D_NUM_50, SBR-VC_NUM_100
and SBR-VC_NUM_50 submitted by Bo Li and Yijuan Lu from Texas
State University, USA; and Henry Johan from Fraunhofer
IDM@NTU, Singapore (Sections 5.2 and 5.3).
 Hierarchical Topology 3D Descriptor submitted by Pedro B.
Pascoal, Alfredo Ferreira and Manuel J. Fonseca from Instituto
Superior Técnico/ Technical University of Lisbon/ INESC-ID, Portugal (Section 5.4).
 HELO-SIL, HOG-SIL, and FDC submitted by Jose M. Saavedra
from University of Chile, Chile and ORAND S.A., Chile and Benjamin Bustos from University of Chile, Chile (Section 5.5).

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

63

5. Methods
5.1. Distance metric learning on Bag-of-Densely sampled local features
for sketch-based 3D shape retrieval [65,4], by T. Furuya, T. Matsuda
and R. Ohbuchi
5.1.1. Method overview
To compare a hand-drawn sketch to a 3D model, most of
existing methods compare a human-drawn 2D sketch with aset of multi-view rendered images of a 3D model. However, there
is a gap between sketches and rendered images of 3D models.
As human-drawn sketches contain stylistic variation, abstraction,
inaccuracy and instability, these sketches are often dissimilar torendered images of 3D models. The entries of their methods
employ unsupervised distance metric learning to overcome thisgap.
First approach, called Uniform Manifold Ranking, or UMR, is ofunsupervised kind. It treats a feature extracted from a sketch anda feature (e.g., BF-GALIF [5]) extracted from a view of a 3D modelon the same ground. From a set of features, which include featuresof both sketches and 3D models, the UMR learns a graph structure
or a Uniform Manifold (UM) that reﬂects low-dimensional structureof features. (It is called ‘‘uniform’’ as same feature extraction algorithm is used for both sketches and rendered images of 3D models,
and these features are meshed into a single manifold graph.)
Assuming N m 3D models rendered from N v viewpoints, and N s
sketches, total of N s þ ðN m  N v Þ features are connected to form
the UM. Then diffusion distance from the feature of the sketch
query to the features of multi-view renderings of 3D models arecomputed by using Manifold Ranking (MR) algorithm proposed by
Zhou et al. [66].
In the experiments, they use either the BF-fGALIF, which is a
modiﬁed version of BF-GALIF by Eitz et al. [5] (Fig. 5(a)), or the
BF-fDSIFT, which is a regressed version of BF-DSIFT [4] (Fig.5(b)),
to form the UM.
Second approach, called Cross-Domain Manifold Ranking, or
CDMR, may be either unsupervised, semi-supervised, or supervised[65]. For the experiment described in this paper, they used the
CDMR in the unsupervised mode. It is called cross-domain since
it tries to bridge the gap between features extracted from two heterogeneous domains, i.e., hand-drawn sketch images and multiview rendered images of 3D models. Unlike UMR, which forms amanifold of features by using single feature, CDMR allows for theuse of multiple measures of similarities, both feature-based andsemantic-label based, to form an integrated Cross Domain Manifold(CDM) that spans heterogeneous domains (See Fig. 6). A set ofsketch images are formed into manifold of sketch images by using
a feature (e.g., BF-GALIF [5]) optimal for sketch-to-sketch comparison. Another manifold that connects 3D models are formed byusing a feature (e.g., BF-DSIFT [52]) that is optimal for comparison
among 3D models. These two manifolds are then cross-linked byusing a feature that is adept at comparing a sketch image to a viewof 3D model, e.g., [5]. The CDM is a graph containing N s þ N m vertices. Additionally, if available, class labels may also be used forcross-linking the domains. Semantic labels help signiﬁcantly if asketch (e.g., a stick ﬁgure human) is dissimilar to multi-view renderings of 3D models (e.g., a realistic 3D model of human). Similarity from a sketch query to a 3D model is computed by using MR[66] algorithm, as is the case with the UMR. The diffusion of relevance value originates from the query, and spreads via edges of
the CDM to 3D models. The diffusion occurs among 2D sketches,from 2D sketches to 3D models across the domain, and among
3D models. Note that, if a corpus of sketches is available in the
database, the CDMR automatically performs a form of query
expansion. The relevance is ﬁrst diffused from the query to its

Fig. 5. Image-based feature comparison processes (applicable to ﬁxed distance,
UMR, and CDMR).

Fig. 6. Feature comparison using Unsupervised Cross-Domain Manifold Ranking(CDMR).

neighboring sketches. Then, these sketches (expanded query set)
behave as multiple secondary sources of diffusion.
For CDMR, they use two different features ﬁt for the purposes toform subparts of the CDM. To form a manifold of 2D sketches, theyuse BF-fGALIF. To form a manifold of 3D models, they use BF-DSIFT[52]. To link sketches with 3D models using feature similarity, theyuse either BF-fGALIF or BF-fDSIFT (Fig.5).

64

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

Descriptions of the BF-fGALIF and BF-fDSIFT features will bepresented in the next section. For the BF-DSIFT, please refer tothe original paper by Furuya et al. [52]. They then brieﬂy describe
the UMR and the CDMR [65] algorithms.

5.1.3. Ranking retrieval results
For the experiments, similarity ranking of retrieval results are
performed by using three different algorithms; ﬁxed distance, theUMR, and the CDMR.

5.1.2. Features used in the experiments
5.1.2.1. BF-fGALIF. BF-GALIF [5] proposed by Eitz et al. is designed
for sketch-based 3D model retrieval. Their variation called
BF-fGALIF (Fig.5(a)) is similar but not identical to the original.
For each 3D model, the model is rendered into Suggestive Contour (SC) [12] images from multiple viewpoints and a set of fGALIF
features is computed for each view. They use 42 viewpoints spaced
uniformly in solid angle and image resolution of 256  256 pixels.
Unlike original GALIF, their fGALIF uses black background for the
SC images (see Fig.5(a)).
Each rendered image is then normalized for rotation. To do so,they exploit response images produced by Gabor ﬁltering on therendered image. Gabor ﬁlter captures orientation of lines andintensity gradient in the image. For each pixel in the response image, a response vector is calculated according to the direction ofGabor ﬁlter and response magnitude at the pixel. The response
vectors calculated at all the pixels in the image are voted against
a histogram. The histogram comprises 18 orientation bins and voting is done according to orientation and magnitude of the response
vectors. After voting, the image is rotated to the direction of themost populated orientation bin.
After normalizing for the rotation, fGALIF features are extracteddensely at regular grid points on the image. They extract 1024 fGALIF features per image. Bandwidth and other parameters for theGabor ﬁlter are determined through preliminary experiments sothat the retrieval accuracy is the highest among the combinationsof parameters they tried.
For each sketch image, fGALIF features are computed after theimage is resized to 256  256 pixels. Computation of fGALIF is carried out in the same manner as for a sketch image and for a rotation-normalized SC image of a 3D model.
The set of 1024 fGALIF features extracted from an image is integrated into a BF-fGALIF feature vector per image by using a standard Bag-of-Features (BF) approach. This integration reduces costof image-to-image matching signiﬁcantly compared with directlycomparing a set of features to another set of features. They usedvocabulary size of 2500. They used k-means clustering to learn
the vocabulary, and used kd-tree to accelerate vector quantizationof fGALIF features into words of the vocabulary.

5.1.3.1. Fixed distance. Symmetric version of Kullback–Leibler Divergence (KLD) is used as ﬁxed distance metric between a pair of BF features. KLD performs well when comparing a pair of probability
distributions, i.e., histograms. Distance between a sketch and a 3Dmodel is the minimum of the 42 distances computed from a BF feature of the sketch and a set of 42 BF features of the 3D model.

5.1.2.2. BF-fDSIFT. Original Bag-of-Features Dense SIFT (BF-DSIFT)[52] computes a feature per 3D model for comparison among 3Dmodels. Here, they use a variant of it, called BF-fDSIFT [4] (Fig.5(b))
to compare a sketch image with multiple images rendered frommultiple views of a 3D model.
The BF-fDSIFT turns both sketch and 3D model into silhouette
images for comparison. To turn a line-drawing sketch with possible
gaps in its circumference into a silhouette, dilation operation toclose the gaps is followed by area ﬁlling. Some of the sketches failto become silhouettes, but they tolerate them. To turn a 3D model
into a set of silhouette images, it is rendered from 42 viewpoints
into silhouettes of 256  256 pixels each.
On each silhouette image, SIFT [50] features are densely andrandomly sampled. They extract 1200 SIFT features per image.
There is no need to normalize images for rotation as SIFT is inherently invariant (to some extent) to rotation, translation, and scaling. The set of 1200 SIFT features extracted from an image is
integrated into a BF-fDSIFT feature vector per image by using the
BF approach. They used vocabulary size of about 10000. They use
ERC-Tree [67] algorithm to accelerate both vocabulary learning(clustering) and vector quantization of SIFT features.

5.1.3.2. Uniform Manifold Ranking (UMR). Input of the UMR is the
BF-fGALIF or the BF-fDSIFT features of the sketches and the rendered images of 3D models. A graph is represented as a sparse matrix W of size ðN s þ N m  N v Þ  ðN s þ N m  N v Þ where N s and N m are
the number of sketches and 3D models in a database respectively,
and N v is the number of views for rendering (i.e., N v ¼ 42). The
similarity between vertices i and j is computed by Eq. (4) whered (xi ; xj ) is KLD between feature vectors xi and xj , and kNN (xi ) isa set of k-nearest neighbors of xi .

8< exp  dðxi ;xj Þ2
if xj 2 kNNðxi Þ
r
Wij ¼
:
0
otherwise

ð4Þ

They normalize W for S,
1

1

S ¼ D2 WD2

ð5Þ

where D is a diagonal matrix whose diagonal element isP
Dij ¼ j Wij . They use the following iterative form of the MR to ﬁnd
relevance values in F given initial value, or ‘‘source’’ matrix Y. A
higher relevance means a smaller distance.

Ftþ1 ¼ aSFt þ ð1  aÞYð6Þ

Y is a diagonal matrix of size ðN s þ Nm  Nv Þ  ðNs þ Nm  Nv Þ that deﬁnes source(s) of relevance value diffusion. If a vertex i is the sourceof diffusion Yii ¼ 1 and, if not, Yii ¼ 0. In their case, the vertex corresponding to the query sketch becomes the source of diffusion.
Fij is the relevance score of the rendered image j given the sketch
i. Hence – Fij is the adaptive distance derived from the MR. Final relevance score between the sketch and the 3D model is the maximumof the 42 scores computed between the sketch and a set of 42 rendered images of the 3D model.
They add preﬁx ‘‘UMR-’’ before the feature extraction method(e.g., UMR-BF-fGALIF or UMR-BF-fDSIFT) to indicate UMR processed algorithms. Parameters for the UMR (i.e., k; r; a) are determined through preliminary experiments. Table 1 shows
combination of the parameters for the UMR-BF-fGALIF and the
UMR-BF-fDSIFT.
To further improve retrieval accuracy, they experimented withcombining the BF-fGALIF and BF-fDSIFT features via a late-fusion
approach, that is, simply adds distances due to BF-fGALIF and BFfDSIFT. Here, each distance may be treated with UMR or not. They
denote the combination of ﬁxed distances by ‘‘BF-fGALIF + BFfDSIFT’’ and the combination of adaptive distances by ‘‘UMR-BFfGALIF + UMR-BF-fDSIFT’’.
5.1.3.3. Cross Domain Manifold Ranking (CDMR). The CDM graph isrepresented as a matrix WCDM whose vertices are the features fromthe sketch domain and the 3D model domain. WCDM is size ofðN s þ N m Þ  ðN s þ N m Þ where N s and N m are the number of sketchesand 3D models in a database respectively.

WCDM ¼



WSS

WSM

WMS

WMM


ð7Þ

65

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80
Table 1
Parameters for the UMR.
Benchmark

Methodkra

SHREC’12

UMR-BF-fGALIF
UMR-BF-fDSIFT

30
1400.00010.00500.9
0.9

SHREC’13

UMR-BF-fGALIF
UMR-BF-fDSIFT

100
160

0.00250.00500.9
0.9

The submatrix WSS having size N s  N s is the manifold of sketchfeatures. Similarity between a pair of sketches is computed byusing the BF-fGALIF. For sketch-to-sketch feature comparison, they
do not normalize for image rotation as most sketches drawn byhuman are already aligned to a canonical orientation. The submatrix WMM having size N M  N M is a manifold of features of 3Dmodels. Similarity between a pair of 3D models is computed byusing their 3D model-to-3D model comparison method BF-DSIFT[52]. The submatrix WSM of size N S  N M couples two submanifolds
WMM and WSS that lie in different domains, that are, sketch featuredomain and 3D model feature domain. Similarity between a pair ofa sketch and a 3D model is computed by using the BF-fGALIF or the
BF-fDSIFT described in Section 5.1.2. The submatrix WMS of size
N M  N S is a zero matrix as they assume no diffusion of similarity
occurs from 3D models to sketches.
For each submatrix, the similarity between vertices i and j iscomputed by Eq. (8) where dðxi ; xj Þ is KLD between feature vectors
xi and xj . The parameter r controls diffusion of relevance value
across the CDM. They use different values rSS ; rMM , and rSM foreach of the submatrices WSS ; WMM , and WSM .

(
Wij ¼



dðx ;x Þ
exp  ri j
if i – j0ð8Þ

otherwise

After generating the CDM graph WCDM , the MR is applied on
WCDM to diffuse relevance value from the sketch query to the 3Dmodels over the CDM across the domain boundary.
They normalize WCDM for SCDM by Eq. (5). They use the following
closed form of the MR to ﬁnd relevance values in F given source
matrix Y. Fij is the relevance value of the 3D model j given thesketch i. A higher relevance means a smaller distance.

F ¼ ðI  aSCDM Þ1 Y

ð9ÞThey add preﬁx ‘‘CDMR-’’ before the feature comparison method used for computing WSM (e.g., CDMR-BF-fGALIF or CDMR-BFfDSIFT) to indicate CDMR processed algorithms.
Parameters for the CDMR (i.e., rSS ; rMM ; rSM and a) are determined through preliminary experiments. Table 2 summarizes combination of the parameters for the CDMR-BF-fGALIF and the CDMRBF-fDSIFT.
They also experimented with combining the CDMR-BF-fGALIF
and CDMR-BF-fDSIFT. They employ a simple late-fusion approach
identical to the one used for the UMR. They denote the
combination of relevance values derived from the two features as‘‘CDMR-BF-fGALIF + CDMR-BF-fDSIFT’’.

5.2. Sketch-based 3D model retrieval based on 2D–3D alignment andshape context matching (SBR-2D–3D) [19,4,7], by B. Li, Y. Lu and H.
Johan
The main idea of the sketch-based retrieval algorithm proposedin [19] is that they want to maximize the chances that they haveselected the most similar or optimal corresponding views forcomputing the distances between a 2D sketch and a set of selected
sample views of a 3D model, while not adding additional online
computation and avoiding the brute-force comparison between
the sketch and many sample views of the model. They implemented the idea by utilizing a 3D model feature named View
Context [20], which has a capability of differentiating different
sample views of a 3D model. The candidate views selection rule
is as follows: a sample view is replaced with the sketch and if its
new View Context is very similar to the original one, then it isregarded as a candidate view. During online retrieval, for each
3D model, a set of candidate views are efﬁciently shortlisted in
the 2D–3D alignment according to their top View Context similarities as that of the sketch. Finally, a more accurate shape context
matching [21] algorithm is employed to compute the distances
between the query sketch and the candidate sample views. The
algorithm is composed of precomputation and online retrieval
stages, which are illustrated in Fig. 7. Some important details andmodiﬁcations about the algorithm are ﬁrst given below.
Silhouette and outline feature views are respectively selected
for View Context feature extraction and shape context-based
2D–3D matching. Two sets of examples are shown in Fig. 8. For aquery sketch, a silhouette feature view is generated based on thefollowing six steps: binarization, Canny edge detection, morphological closing (inﬁnite times, which means repeating until the image does not change), and ﬁlling holes, inversion and resizing into a
256  256 image. The corresponding outline feature view is very
easy to obtain based on the silhouette feature view. An integrated
image descriptor, which contains region, contour, and geometricalinformation of the silhouette and outline feature views, is utilized
to compute View Context. Considering the large-scale retrieval scenario, to reduce computational cost, they set the number of sample
points to represent a contour feature view to 50 and only keep the
top 4 candidate views during 2D–3D alignment. On the other hand,to save the memory needed to load the shape context features during online retrieval, they use the short integers to code the locations of the 5  12 bins and values during the loading of theprecomputed shape context features.
For clarity, the main steps of the algorithm are further describedas follows.

Table 2
Parameters for the CDMR.
Benchmark

Method

rSS

rMM

rSM

a

SHREC’12

CDMR-BF-fGALIF
CDMR-BF-fDSIFT

0.010
0.040

0.025
0.015

0.040
0.030

0.9
0.8

SHREC’13

CDMR-BF-fGALIF
CDMR-BF-fDSIFT

0.006
0.005

0.010
0.010

0.025
0.025

0.9
0.9

66

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

Online Retrieval Stage

Sketch’s shape context

Sketch’s View Context

Sketch query

2D-3Dalignment

2D-3D
matching& rankingfeature view

View Context…
3D modeldatasetView sampling

Shape context

Fig. 7. Flow chart of the sketch-based 3D model retrieval algorithm based on 2D–3D alignment and shape context matching.

5.2.5. Sketch-Model distance computation
Comparing the sketch with every candidate outline view using
the relative shape context matching and regarding the minimum
relative shape context distance obtained as the sketch-model
distance.

Fig. 8. The feature views of a 3D teddy model and a 2D ant standard line drawing
sketch. For each row, from left to right: model/sketch, silhouette view; outline view.

5.2.1. Feature extraction
Silhouette and outline feature views are generated for both 2D
sketches and 3D models to effectively and efﬁciently measure thedifferences among them.
5.2.2. Feature distance
A computationally efﬁcient integrated image descriptor named
ZFEC is adopted for View Context computation. It contains a region-based Zernike moments feature Z for the silhouette view
and a contour-based Fourier descriptor feature F for the outline
view. Additionally, eccentricity feature E and circularity feature C
are also utilized to extract the geometric feature of the outline
view. To more accurately measure the difference between thesketch and each candidate view, the relative shape context matching method [21] is adopted.
5.2.3. Sketch’s View Context feature extraction
The integrated image descriptor distances between the sketch
and all the base views of the target model are computed and theresulting distance vector Dk ¼ hd1 ; d2 ; . . . ; dm i is named sketch’s
View Context.
5.2.4. 2D–3D alignment
To align the 2D sketch and a 3D model, some candidate views
are short listed by keeping a certain percentage (e.g. 20% or 16
sample views for the track) of the sample views with top View
Context similarities as the sketch, in terms of correlation similarity
Si ,Ds  Dk
Si ¼  si k  ;D D 
i

ð10Þ
th

where Dsi and Dk are the View Contexts of the i sample view V si ofthe 3D model and the 2D sketch, respectively.

5.2.6. Ranking and output
Sorting all the sketch-model distances between the sketch andthe models in an ascending order and listing the retrieved models
accordingly.
The two runs, SBR-2D-3D_NUM_100 (for small-scale benchmark, Section 6.1) and SBR-VC_NUM_50 (for large-scale benchmark, Section 6.2), are two variations of the original SBR-2D-3D
by setting the number of sample points for the contour(s) of eachsketch, referred to as NUM, to 100 and 50, respectively.
5.3. Sketch-based 3D model retrieval based on view clustering andshape context matching (SBR-VC) [68,7], by B. Li, Y. Lu and H. Johan
3D models often differ in their visual complexities, thus there isno need to sample the same number of views to represent eachmodel. Motivated by this, a Sketch-Based Retrieval algorithm
based on adaptive View Clustering and Shape Context matching,named SBR-VC, has been proposed. Based on the viewpoint entropy distribution of a set of sample views of a model, they propose a
3D model visual complexity metric, based on which the number ofthe representative views of the 3D model is adaptively assigned.
Then, a Fuzzy C-Means view clustering is performed on the sample
views based on their viewpoint entropy values and viewpoint locations. Finally, shape context matching [21] is utilized during online
retrieval for the matching between a query sketch and therepresentative views for each target model. The retrieval algorithm
comprises precomputation and online retrieval stages. An overview of the algorithm is shown in Fig. 9.
The key component of the retrieval algorithm is viewpoint
entropy-based adaptive view clustering, which comprises thefollowing three steps.
5.3.1. Viewpoint entropy distribution
For each model, they sample a set of viewpoints by setting thecameras on the vertices of a subdivided icosahedron Ln obtained byn times Loop subdivision on a regular icosahedron L0 . Viewpoint
entropy distributions of three models utilizing L3 for view sampling are demonstrated in Fig. 10. It can be seen that for a 3D model, the complexity of its entropy distribution pattern is highly
related to the complexity of its geometry. For instance, the two

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

View sampling

Viewpoint
entropy

3D visualcomplexity

views number
assignment

67

Viewpoint
entropy-based
view clustering

Retrieval Stage:
Query sketch
Shape context matching

Ranking& output

Fig. 9. An overview of the SBR-VC algorithm. The ﬁrst row is for precomputation while the second row is for retrieval stage.

complex models, horse and Lucy, have a more complicated pattern
than the relatively simpler model ﬁsh.
5.3.2. Viewpoint entropy-based 3D visual complexity
The visual complexity metric is deﬁned based on a class-level
entropy distribution analysis on a 3D dataset. Mean and standard
deviation entropy values m and s among all the sample views of
a 3D model are ﬁrst computed, followed by an average over all
the pmodelsﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃfor
ﬃ each class. 3D visual complexity C is deﬁned as^ 2 , where ^s and m^ are the normalized s and m by their
C ¼ ^s2 þ mrespective maximums over all the classes. The metric is capableof reasonably reﬂecting the semantic distances among different
classes of models.
5.3.3. Viewpoint entropy-based adaptive views clustering
Utilizing the visual complexity value C of a model, the numberof representative outline feature views N c is adaptively assigned:
N c ¼ C2  N 0 (for small-scale benchmark, Section 6.1) or N c ¼ C6  N 0(for large-scale benchmark, Section 6.2), where N 0 is the total number of sample views and it is set to 81 in the algorithm. To speed up
the retrieval process on the large-scale benchmark in Section 6.2,
they choose the parameter setting of 16, compared with the selection of 12 in the originally proposed algorithm. Finally, a Fuzzy CMeans view clustering is performed to obtain the representative
views.

The two runs, SBR-VC_NUM_50 and SBR-VC_NUM_100, are twovariations of the original SBR-VC by setting the number of sample
points for the contour(s) of each sketch, referred to as NUM, to 50
and 100, respectively.
5.4. Hierarchical Topology 3D Descriptor (HTD) for sketch-based 3D
shape retrieval [69,70], by P.B. Pascoal, A. Ferreira and M.J. Fonseca
In order to compare a 3D object with a 2D sketch, it is required
to extract 2D views of the object. In the ﬁrst step, the 3D object isrendered using the Cel-shading technique so that the object isdrawn with a black outline and interior contour lines.
The black outline is drawn slightly larger than the object itself,
and then using backface culling, back-facing triangles are hidden
due to rendering the object as solid-ﬁlled. Afterwards, they extract
20 views of the 3D model from different camera positions. This approach is based on the method presented by Chen et al. [71], butinstead of using 10 silhouettes they use all the 20 positions of
the dodecahedron to get all possible sketches. An overview of the
Hierarchical Topology 3D Descriptor process is demonstrated inFig. 11.
For each image, they then use an algorithm proposed by Ferreira et al. [69] that detects polygons deﬁned by a set of line segments and saves them in a vector format image. The algorithm
can be summarized in 4 major steps, as illustrated in Fig. 12.

Fig. 10. Viewpoint entropy distribution examples: First row shows the models (front views); Second row demonstrates the viewpoint entropy distribution of each model
seen from the viewpoint with respect to its front view. Entropy values are mapped as colors on the surface of the spheres based on HSV color model and smooth shading. Red:
small entropy; green: mid-size entropy; blue: large entropy. (For interpretation of the references to color in this ﬁgure legend, the reader is referred to the web version of thisarticle.)68

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

First, it detects the line segment intersections using the Bentley–Ottmann algorithm [72]. Then, creates a graph induced by
the drawing, where vertices represent endpoints or proper intersection points of line segments and edges represent maximal relatively open subsegments that contain no vertices. The third stepﬁnds the Minimum Cycle Basis (MCB) [73] of the graph inducedin the previous step, using the algorithm proposed by Horton[74]. Last step constructs a set of polygons based on cycles in thepreviously found MCB. This is straight-forward if we transform
each cycle into a polygon, where each vertex in the cycle represents a vertex in the polygon and each edge in the cycle represents
an edge in the polygon.
Finally, for classiﬁcation, they used a method proposed by Sousa
and Fonseca [70] which uses a graph-based technique to describe
the spatial arrangement of drawing components, combined withgeometric information.
Their process starts by applying a simpliﬁcation step, to remove
small visual details while retaining dominant shapes in a drawing.
After simpliﬁcation, they identify visual elements, namely polygons and lines, and extract geometric and topological informationfrom drawings.
The topology is simpliﬁed into the eight topological relationships deﬁned by Egenhofer and Al-Taha [75] (Disjoint, Meet, Overlap, Contain, Inside, Cover, Covered-By and Equal), starting fromtheir neighborhood graph for topological relationships. This graphhas a well-deﬁned structure, with a root node representing thewhole drawing and each next level of the graph describing polygons contained in the blocks identiﬁed before, adding more drawing details. Therefore, by going down in the depth of the graph, weare ‘‘zooming in’’ in drawing details as illustrated in Fig. 13.
The resulting descriptor is a multidimensional vector, whose
size depends on graph complexity. Very complex drawings will
yield descriptors with higher dimensions, while simple drawings
will result in descriptors with lower sizes. To solve this issue, they
use the graph spectra to convert graphs into feature vectors, solving the problem of isomorphism between topology graphs to themuch simpler computation of distances between descriptors. To
generate the graph spectrum, ﬁrstly it creates the adjacency matrix

Fig. 12. Polygon detection process [69].

Fig. 13. Drawing and topology graph.

of the graph; secondly calculates its eigenvalues; and ﬁnally sorts
the absolute values to obtain the topology descriptor as shown in
Fig. 14.
As for the geometric information, it uses a general shape recognition library called CALI [76]. By applying this method to eachgeometric entity in the ﬁgure, it provides complete description of
the geometry of a drawing. The geometry and topology descriptors
thus computed are combined and used as the descriptor for therespective image.
5.5. Sketch feature extractors based on 3D models silhouettes [7], by
J.M. Saavedra and B. Bustos Saavedra
One of the most critical problems when we face the sketch
based 3D model retrieval is trying to obtain a good sketch-like representation from objects that are not sketches by themselves.
Therefore, considering the importance of a good sketch-like representation from 3D models, they propose a minimal strategy based

Fig. 11. Overview of the Hierarchical Topology 3D Descriptor process.

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

69

Fig. 14. Block diagram for topology descriptor computation.

on computing an external contour (Silhouette) of 3D models from adeﬁned number of viewpoints. After this stage, they compute a setof low-level features for each contour. Finally, they apply a similarity search to get a ranking under an input sketch. These involved
processes lead to a framework composed of three stages: (1) Preprocessing, (2) Feature extraction, and (3) Similarity search. They
describe each one of these stages as follows.
5.5.1. Pre-processing
They divide this stage into two sub-stages aiming to pre-process a 3D model and pre-process an input sketch. The goal of bothsub-stages is to obtain a simple representation that allows the nextstage to compute a low-level feature in an easier way.
5.5.1.1. 3D model pre-processing. They compute 2D projections
from each 3D model using six deﬁned viewpoints (top, bottom,
right, left, back, front). The external contour of each projection isthen extracted discarding internal holes in the underlying image.
An example of this representation is shown in Fig. 15.
5.5.1.2. Sketch pre-processing. Considering that a sketch is commonly drawn roughly, which produces disconnected strokes, theirﬁrst stage is to connect all the strokes using a sequence of morphological dilation operations. After that, they extract the external
contour of each sketch. Similar to the 3D model pre-processing,internal holes of sketches will be discarded. An example of their results in this stage is presented in Fig. 16.
5.5.2. Feature extraction
They take the result produced by the previous stage to compute
low-level features. In this stage, they propose to use three feature
extraction methods: Histogram of Edge Local Orientations (HELO)
proposed by Saavedra et al. [62], Histogram of Oriented Gradients(HOG) proposed by Dalal et al. [54], and a Fourier descriptor using
the approach presented by Zhang et al. [77].
5.5.2.1. Histogram of Edge Local Orientations based on Silhouettes(HELO-SIL). HELO, proposed by Saavedra et al. [62], is a method forcomputing a histogram of edge orientations in the context ofsketch-based image retrieval. HELO computes a K-bin histogram
based on local edge orientations. To get the HELO feature vector,
the sketch is divided into a W  W grid. Then, an edge orientation
is estimated for each cell in the grid. Compared with other orientation-based approaches, the main difference is that HELO estimatesFig. 16. A sketch and its silhouette representation.

a representative orientation by computing squared gradients inside a cell.
Let ½Gx ; Gy T be the corresponding gradient vector for a pixel
ðx; yÞ in a sketch image. The squared gradient is computed for eachpixel doubling its gradient angle and squaring its gradient length.
To this end, the gradient vector is represented in its corresponding
polar coordinates. The squared gradient ½Gsx ; Gsy T corresponding to
the gradient ½Gx ; Gy T is computed as follows,



Gsx
Gsy

"
¼

G2x  G2y
2Gx  Gy

#
:

ð11Þ

The estimated orientation for a cell is the orientation of the averagesquared gradient ½Gsx ; Gsy  computed for the cell. Finally, a K-bin histogram is computed using the angles of all average squared gradients for each cell.
In order to exploit local information of sketches, they divide thesketch image into 6  6 blocks, and compute a 36-bin HELO
descriptor for each block. Then, they concatenate all the local HELO
descriptors to get the ﬁnal feature vector. In addition, they set
W ¼ 25.
5.5.2.2. Histogram of Oriented Gradients based on Silhouettes (HOGSIL). The HOG [54] approach allows us to compute a histogram ofgradient orientations by concatenating local orientation histograms computed in small regions. This approach divides the sketch
image into C  C-size cells. For each cell a K-bin histogram of orientation is computed. In order to increase the robustness of thedescriptor, each local histogram is then normalized using information of neighbor histograms. To this end, blocks of B  B cells areformed. In this point, it is possible to form blocks with or without
overlapping.
In their experimental evaluation, they set C ¼ 16, B ¼ 3, K ¼ 9,
and they use the non-overlapping block approach. In addition,
since the size of the descriptor depends on the size of the input image, they resize all the silhouette images, obtained from the 2D
projections as well as from input sketches, to 100  100 pixels.
5.5.2.3. Fourier Descriptors on 3D models Silhouettes (FDC). Let X be
the set of x-coordinates and Y be the set of y-coordinates of aboundary. The Fourier descriptor is computed over the centroid
distance C which is obtained as follows,

C ¼ distE ðX  xc ; Y  yc Þ;
Fig. 15. A 3D model and three silhouettes taken from top, front and left viewpoints
respectively.

ð12Þ

where ðxc ; yc Þ is the centroid of the shape and distE is the Euclidean
distance. To deal with different boundary sizes, they sample 128

70

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

points using the equal arc-length sampling as suggested by Zhang
et al. [42].
Next, they apply a Fourier Transform on the sample set. Let F be
the computed Fourier descriptor with 256 entries. To deal with therotation invariance issue, they use the magnitude of the Fourier
descriptor. In addition, considering that the sample set is composed of real values, they take only half of the Fourier entries. Finally, to deal with different scales, the descriptor is normalizedwith respect to F 0 , so the ﬁnal descriptor is given by,

FD ¼



jF 1 j jF 2 j
jF 128 j;;...;:
jF 0 j jF 0 j
jF 0 jð13Þ

5.5.3. Similarity search
To improve the efﬁciency of the searching, they use a KD-Treeindex together with the Manhattan distance to search all the database of 3D models. For indexing and retrieving, they use the FLANN(Fast Library for Approximate Nearest Neighbors) implementation
provided by Muja et al. [78].

dataset). Table 8 lists the timing information in seconds and comparison results. In this distributed evaluation, it was not possible tocontrol for the hardware platform (roughly comparable for allgroups, though) or implementation efﬁciency of the setups. However, we believe that the timing information is useful for an
approximate comparison of the runtime requirements of thealgorithms.
Last but not least, we evaluate the scalability of the different
methods to irrelevant models (Section 3.1.1) in the dataset. Table 7
lists the percentage of performance decreases when using the extended target dataset instead of the basic one (using hand-drawn
sketch queries). Similarly, we also list the ranking information interms of scalability. Furuya’s CDMR-BF-fGALIF has best scalability,
closely followed by CDMR-BF-fGALIF + CDMR-BF-fDSIFT. In the
Rank 2, UMR-BF-fGALIF, SBR-2D-3D_NUM_100, UMR-BF-fGALIF + UMR-BF-fDSIFT and SBR-VC_NUM_100 share similar scalability. Compared with the above six approaches, the other threemethods exhibit a stronger decrease in retrieval performance
when adding 140 irrelevant models to the target dataset. Pleasealso note that compared with fGALIF, fDSIFT often has more decreases in retrieval performance.

6. Results
6.1. Small-scale benchmark: SHREC’12 Sketch Track Benchmark

6.2. Large-scale benchmark: SHREC’13 Sketch Track Benchmark

In this section, we perform a comparative evaluation of the results of the 14 runs submitted by 3 of the 4 groups on SHREC’12
Sketch Track Benchmark (Pascoal’s results are not available on thisbenchmark; Li’s SBR-VC and SBR-2D-3D select NUM = 100 only).
We measure retrieval performance based on the 7 metrics mentioned in Section 3.3: PR; NN; FT; ST; E; DCG and AP. In addition,
we also compare their scalability and efﬁciency.
As described in Section 3.1, there are two versions of target
dataset (Basic and Extended) as well as two types of sketch datasets (hand-drawn sketches and standard line drawings). This results in four combinations: (1) Hand-drawn sketch queries andBasic version of target dataset; (2) Standard line drawing queries
and Basic version of target dataset; (3) Hand-drawn sketch queries
and Extended version of target dataset; and (4) Standard line drawing queries and Extended version of target dataset. Comparisons of
the 14 contributed methods for the above four cases are shown in
Fig. 17 and Tables 3–6.
First, we start with the overall performance evaluation. As
shown in the aforementioned ﬁgures and tables, Furuya’s CDMRBF-fGALIF + CDMR-BF-fDSIFT performs best, closely followed by
CDMR-BF-fGALIF. Then, CDMR-BF-fDSIFT, UMR-BF-fGALIF + UMRBF-fDSIFT, UMR-BF-fGALIF, SBR-VC_NUM_100 and SBR-2D3D_NUM_100 succeed. Performance of the remaining three methods is comparable and the disparity among them is relatively
small. In a word, these runs can be ranked in several groups
according to the overall performance and we also provide thisranking information (‘‘R’’) in the following Tables 3–12. If we consider non-machine learning approaches, Li’s SBR-VC and SBR-2D3D perform best and they outperform either the GALIF or the DSIFT
feature-based methods and we can expect better performance if
we apply ‘‘CDMR’’ on them.
Second, we look into different types of queries. Compared withhand-drawn sketch queries, standard line drawing queries usuallyachieve superior performance. One possible explanation for this isthat this dataset only contains a single line drawing per class,which has been carefully created to convey shape as well as salientfeatures of that class.
Third, we asked contributors to also provide timing information, together with their hardware and software conﬁgurations,
to compare runtime requirements of their methods, based on thesecond case (hand-drawn sketch queries and extended target

Similarly, a comparative evaluation of 16 runs (Li’s SBR-2D-3D
selects NUM = 50 only) of all the 15 contributed methods has been
performed on the latest large-scale benchmark of SHREC’13 Sketch
Track Benchmark. As described in Section 3.2, the complete querysketch dataset is divided into ‘‘Training’’ and ‘‘Testing’’ datasets,
which is to accustom to machine learning-based retrieval algorithms. To provide complete reference performance data for both
non-learning based and learning-based approaches, such as thecontributed ‘‘CDMR-’’ and ‘‘UMR-’’ methods, we evaluate the submitted results on both ‘‘Training’’ and ‘‘Testing’’ datasets, as wellas the complete sketch dataset. Fig. 18 and Tables 9–11 compare
the contributed methods in terms of the 7 performance metrics
on the above three datasets, respectively.
Similar as the results on the small-scale SHREC’12 Sketch Track
Benchmark, the aforementioned ﬁgure and table show that Furuya’s CDMR-BF-fGALIF + CDMR-BF-fDSIFT performs best, closely
followed by their CDMR-BF-fGALIF and CDMR-BF-fDSIFT. Then,
UMR-BF-fGALIF + UMR-BF-fDSIFT, BF-fGALIF + BF-fDSIFT, UMRBF-fDSIFT and UMR-BF-fGALIF succeed, followed by the four methods of BF-fDSIFT, BF-fGALIF, SBR-VC and SBR-2D-3D. HOG-SIL,
HELO-SIL and FDC have comparatively inferior performance, butthey outperform HTD. We also can ﬁnd that ‘‘CDMR-’’ based approaches often consistently (either in small-scale or large-scale retrieval scenarios) achieve better performance than their ‘‘UMR-’’
based counterparts. Similarly, if we only compare non-machinelearning approaches, Li’s SBR-VC_NUM_100 is comparable to BFfGALIF and BF-fDSIFT, which are outperformed by their combinational one. SBR-2D-3D_NUM_50 is also comparable to SBRVC_NUM_50.
However, when compared with the performance obtained on
the SHREC’12 Sketch Track Benchmark which employed a muchsmaller benchmark, the performance of all the methods is muchless successful. For example, even for the best-performing approach of CDMR-BF-fGALIF + CDMR-BF-fDSIFT, the decreases(comparing the performance on the ‘‘Complete’’ benchmark of
SHREC’13 Sketch Track Benchmark and the ‘‘Hand-drawn and Basic’’ benchmark of SHREC’12 Sketch Track Benchmark) are 61.2%,
68.2%, 62.9%, 71.3%, 44.9% and 63.7% in NN, FT, ST, E, DCG andAP, respectively. This ﬁnding is worth noting because it evidently
raises the issue of the scalability in the case of large-scale
sketch-based model retrieval.

71

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

Furuya (CDMR−BF−fGALIF+CDMR−BF−fDSIFT)
Furuya (CDMR−BF−fGALIF)
Li (SBR−2D−3D_NUM_100)
Li (SBR−VC_NUM_100)
Furuya (UMR−BF−fGALIF+UMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF)
Furuya (BF−fGALIF)
Furuya (BF−fGALIF+BF−fDSIFT)
Furuya (CDMR−BF−fDSIFT)
Furuya (UMR−BF−fDSIFT)
Furuya (BF−fDSIFT)
Saavedra (HOG−SIL)
Saavedra (HELO−SIL)
Saavedra (FDC)

1.2

1

1

0.8
Precision

0.8

Furuya (CDMR−BF−fGALIF+CDMR−BF−fDSIFT)
Furuya (CDMR−BF−fGALIF)
Li (SBR−2D−3D_NUM_100)
Li (SBR−VC_NUM_100)
Furuya (UMR−BF−fGALIF)
Furuya (UMR−BF−fGALIF+UMR−BF−fDSIFT)
Furuya (BF−fGALIF)
Furuya (BF−fGALIF+BF−fDSIFT)
Furuya (CDMR−BF−fDSIFT)
Furuya (UMR−BF−fDSIFT)
Furuya (BF−fDSIFT)
Saavedra (HOG−SIL)
Saavedra (HELO−SIL)
Saavedra (FDC)

1.2

0.6
0.6

0.4
0.4

0.2
0.2

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0

0.1

0.2

0.3

0.4

RecallFuruya (CDMR−BF−fGALIF+CDMR−BF−fDSIFT)
Furuya (CDMR−BF−fGALIF)
Li (SBR−2D−3D_NUM_100)
Li (SBR−VC_NUM_100)
Furuya (UMR−BF−fGALIF+UMR−BF−fDSIFT)
Furuya (UMR−BF−fDSIFT)
Furuya (BF−fGALIF+BF−fDSIFT)
Furuya (BF−fGALIF)
Furuya (CDMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF)
Furuya (BF−fDSIFT)
Saavedra (HOG−SIL)
Saavedra (FDC)
Saavedra (HELO−SIL)

1.2

1

0.6

0.7

0.8

0.9

1

Furuya (CDMR−BF−fGALIF+CDMR−BF−fDSIFT)
Furuya (CDMR−BF−fGALIF)
Li (SBR−2D−3D_NUM_100)
Li (SBR−VC_NUM_100)
Furuya (UMR−BF−fGALIF+UMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF)
Furuya (BF−fGALIF)
Furuya (BF−fGALIF+BF−fDSIFT)
Furuya (CDMR−BF−fDSIFT)
Furuya (UMR−BF−fDSIFT)
Furuya (BF−fDSIFT)
Saavedra (HOG−SIL)
Saavedra (HELO−SIL)
Saavedra (FDC)

1.2

1

0.8
Precision

0.8

0.5
Recall

0.6

0.6

0.4
0.4

0.2

0.2

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Recall

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

RecallFig. 17. Precision-Recall plot performance comparisons of the four cases of SHREC’12 Sketch Track Benchmark: (a) Hand-drawn sketch queries and Basic version of target
dataset. (b) Hand-drawn sketch queries and Extended version of target dataset. (c) Standard line drawing queries and Basic version of target dataset. (d) Standard line
drawings queries and Extended version of target dataset.

We noticed that all the retrieval performance metrics values are
not high, which is mainly due to the challenges of the benchmark.
Firstly, the 80 sketches in a query class represent many variationsof an object, which adds the difﬁculty for accurate retrieval and deserves a higher standard on the scalability of retrieval algorithms.
Secondly, as mentioned in Section 3.2.1, the query class bias has already been solved by making each query class contain the same
number of sketches, while the bias in the target class still exists.
There is a large variation in the number of models in different

classes. For example, the ‘‘airplane’’ class contains 184 target models while the ‘‘ant’’ class only has 5 models. Thus, to accurately retrieve these classes of models in the First Tier and Second Tier is
difﬁcult. Therefore, their performance metrics values, especiallyon NN, FT and ST, are relatively much lower and this happens to
all the 15 running methods. One demonstrating example is shownin Fig. 19. More details about the variations in the performancewith respect to different classes for each contributed method canbe found in the SHREC’13 sketch track homepage [2]. The

72

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

Table 3
Other Performance metrics for the performance comparison on the Hand-drawn sketch queries and Basic version of target dataset. ‘‘R’’ denotes the ranking group number.
Contributor

Method

NN

FT

ST

E

DCG

AP

R

FuruyaBF-fDSIFT
BF-fGALIFBF-fGALIF + BF-fDSIFTCDMR-BF-fDSIFTCDMR-BF-fGALIF
CDMR-BF-fGALIF + CDMR-BF-fDSIFT
UMR-BF-fDSIFT
UMR-BF-fGALIF
UMR-BF-fGALIF + UMR-BF-fDSIFT

0.364
0.600
0.596
0.504
0.688
0.708
0.396
0.612
0.572

0.295
0.367
0.369
0.428
0.617
0.641
0.303
0.443
0.458

0.454
0.513
0.529
0.604
0.767
0.806
0.493
0.576
0.619

0.312
0.357
0.365
0.418
0.556
0.582
0.333
0.411
0.434

0.610
0.689
0.689
0.701
0.813
0.833
0.617
0.718
0.728

0.321
0.393
0.399
0.491
0.661
0.681
0.345
0.478
0.486

3
3
3
2
1
1
3
2
2

Li

SBR-VC_NUM_100
SBR-2D-3D_NUM_100

0.664
0.688

0.427
0.415

0.587
0.581

0.413
0.411

0.730
0.731

0.461
0.459

2
2

Saavedra

HELO-SIL
HOG-SIL
FDC

0.228
0.256
0.164

0.168
0.183
0.147

0.307
0.312
0.250

0.196
0.203
0.164

0.522
0.529
0.490

0.201
0.210
0.168

4
4
4

Table 4
Other performance metrics for the performance comparison on the Hand-drawn sketch queries and Extended version of target dataset. ‘‘R’’ denotes the ranking group number.
Contributor

Method

NN

FT

ST

E

DCG

AP

R

FuruyaBF-fDSIFT
BF-fGALIFBF-fGALIF + BF-fDSIFTCDMR-BF-fDSIFTCDMR-BF-fGALIF
CDMR-BF-fGALIF + DMR-BF-fDSIFT
UMR-BF-fDSIFT
UMR-BF-fGALIF
UMR-BF-fGALIF + UMR-BF-fDSIFT

0.280
0.516
0.508
0.340
0.648
0.668
0.296
0.572
0.492

0.225
0.317
0.317
0.349
0.566
0.585
0.235
0.387
0.392

0.370
0.446
0.461
0.531
0.741
0.770
0.406
0.530
0.554

0.244
0.307
0.316
0.362
0.535
0.554
0.269
0.375
0.387

0.552
0.646
0.648
0.631
0.787
0.801
0.560
0.684
0.684

0.246
0.332
0.338
0.399
0.616
0.625
0.274
0.426
0.418

3
3
3
2
1
1
3
2
2

Li

SBR-VC_NUM_100
SBR-2D-3D_NUM_100

0.576
0.628

0.372
0.371

0.519
0.520

0.360
0.364

0.682
0.692

0.392
0.400

2
2

Saavedra

HELO-SIL
HOG-SIL
FDC

0.116
0.188
0.108

0.097
0.123
0.087

0.183
0.223
0.170

0.115
0.139
0.108

0.443
0.466
0.426

0.122
0.143
0.104

4
4
4

Table 5
Other performance metrics for the performance comparison on the Standard line drawing queries and Basic version of target dataset. ‘‘R’’ denotes the ranking group number.
Contributor

Method

NN

FT

ST

E

DCG

AP

R

FuruyaBF-fDSIFT
BF-fGALIFBF-fGALIF + BF-fDSIFTCDMR-BF-fDSIFTCDMR-BF-fGALIF
CDMR-BF-fGALIF + CDMR-BF-fDSIFT
UMR-BF-fDSIFT
UMR-BF-fGALIF
UMR-BF-fGALIF + UMR-BF-fDSIFT

0.667
0.500
0.667
0.667
0.750
0.750
0.750
0.500
0.750

0.442
0.421
0.471
0.583
0.629
0.679
0.525
0.487
0.546

0.658
0.612
0.717
0.833
0.792
0.871
0.733
0.617
0.692

0.436
0.410
0.510
0.580
0.567
0.619
0.529
0.442
0.494

0.747
0.722
0.765
0.800
0.842
0.866
0.779
0.752
0.796

0.477
0.443
0.498
0.633
0.694
0.727
0.563
0.517
0.568

3
3
3
1
1
1
2
2
2

Li

SBR-VC_NUM_100
SBR-2D-3D_NUM_100

0.667
0.750

0.521
0.542

0.713
0.700

0.503
0.516

0.799
0.807

0.570
0.580

2
2

Saavedra

HELO-SIL
HOG-SIL
FDC

0.167
0.583
0.250

0.221
0.233
0.208

0.379
0.413
0.329

0.256
0.263
0.237

0.550
0.606
0.549

0.254
0.289
0.226

4
4
4

remaining bias deserves our further improvement, such as making
each class contain the same number of 3D models by adding moremodels from other 3D model benchmarks.
Finally, we have a similar approximate efﬁciency performancecomparison on this benchmark, as shown in Table 12. Obviously,
Saavedra’s three methods are still the most efﬁcient, followed by
Furuya’s BF-fGALIF and BF-fDSIFT. Li’s two methods still have thesame ranks. However, Furuya’s two ‘‘CDMR-’’ approaches dropfrom rank 2 to rank 4 while their two ‘‘UMR-’’ methods also drop
1 or 2 places. We compare the changes in timing information between the large-scale SHREC’13 Sketch Track Benchmark (1258models) and the small-scale SHREC’12 Sketch Track Benchmark(400 models) in Fig. 20. From the numbers, we also can ﬁnd thatthe response time of ‘‘CDMR-’’ and ‘‘UMR-’’ approaches increase a
lot with the increase of number of target 3D models. With the scaleof the target database is increased by 3.2 times from 400 to 1258
models, the response time of CDMR-BF-fDSIFT, CDMR-BF-fGALIF,
UMR-BF-fDSIFT and UMR-BF-fGALIF is correspondingly increased
by about 730.3, 1230.9, 173.2, and 247.0 times; while it is 1.0
and 0.8 for BF-fDSIFT, BF-fGALIF, and 3.5 times for HOG-SIL,
HELO-SIL and FDC, respectively. While, for SBR-VC and SBR-2D3D, the response time has been reduced 10.7% and 75.4% respectively by selecting fewer representative views or sample points.
In a word, the above best-performing approaches CDMR-BF-fGALIF
and CDMR-BF-fDSIFT have inferior performance on efﬁciency, thus
have much room for further improvement in this regard.

73

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

Table 6
Other performance metrics for the performance comparison on the Standard line drawing queries and Extended version of target dataset. ‘‘R’’ denotes the ranking group number.
Contributor

Method

NN

FT

ST

E

DCG

AP

R

FuruyaBF-fDSIFT
BF-fGALIFBF-fGALIF + BF-fDSIFTCDMR-BF-fDSIFTCDMR-BF-fGALIF
CDMR-BF-fGALIF + CDMR-BF-fDSIFT
UMR-BF-fDSIFT
UMR-BF-fGALIF
UMR-BF-fGALIF + UMR-BF-fDSIFT

0.583
0.417
0.417
0.500
0.583
0.500
0.667
0.500
0.667

0.337
0.337
0.388
0.467
0.542
0.533
0.442
0.371
0.433

0.512
0.496
0.613
0.717
0.717
0.783
0.671
0.550
0.642

0.356
0.346
0.394
0.494
0.519
0.551
0.455
0.388
0.455

0.684
0.656
0.697
0.724
0.781
0.778
0.733
0.701
0.739

0.376
0.336
0.394
0.523
0.590
0.589
0.490
0.427
0.479

3
3
3
1
1
1
2
2
2

Li

SBR-VC_NUM_100
SBR-2D-3D_NUM_100

0.750
0.750

0.442
0.454

0.629
0.625

0.439
0.442

0.747
0.750

0.477
0.476

2
2

Saavedra

HELO-SIL
HOG-SIL
FDC

0.083
0.417
0.167

0.121
0.163
0.100

0.246
0.271
0.221

0.151
0.167
0.138

0.454
0.541
0.455

0.157
0.214
0.127

4
4
4

Table 7
Scalability comparison in terms of performance decrease (%, in terms of percentage of the performance results on the Basic version of target dataset) on the Hand-drawn sketch
queries. ‘‘R’’ denotes the ranking group number.
Contributor

Method

NN

FT

ST

E

DCG

AP

R

FuruyaBF-fDSIFT
BF-fGALIFBF-fGALIF + BF-fDSIFTCDMR-BF-fDSIFTCDMR-BF-fGALIF
CDMR-BF-fGALIF + CDMR-BF-fDSIFT
UMR-BF-fDSIFT
UMR-BF-fGALIF
UMR-BF-fGALIF + UMR-BF-fDSIFT

23.1
14.0
14.8
32.5
5.8
5.6
25.3
6.5
14.0

23.7
13.6
14.1
18.5
8.3
8.7
22.4
12.6
14.4

18.5
13.1
12.9
12.1
3.4
4.5
17.6
8.0
10.5

21.8
14.0
13.4
13.4
3.8
4.8
19.2
8.8
10.8

9.5
6.2
6.0
10.0
3.2
3.8
9.2
4.7
6.0

23.4
15.5
15.3
18.7
6.8
8.2
20.6
10.9
14.0

4
3
3
3
1
1
4
2
2

Li

SBR-VC_NUM_100
SBR-2D-3D_NUM_100

13.3
8.7

12.9
10.6

11.6
10.5

12.8
11.4

6.6
5.3

15.0
12.9

2
2

Saavedra

HELO-SIL
HOG-SIL
FDC

49.1
26.6
34.2

42.3
32.8
40.8

40.4
28.5
32.0

41.3
31.5
34.2

15.1
11.9
13.1

39.3
31.9
38.1

5
5
5

Table 8
Timing information comparison on the ‘‘hand-drawn and extended’’ dataset of SHREC’12 Sketch Track Benchmark: t is the average response time (in seconds) per query. ‘‘R’’denotes the ranking group number.
Contributor (with computer conﬁguration)

MethodLanguaget

R

Furuya (CPU: Intel Core i7 3930 K @ 3.20 Hz; GPU: NVIDIA GeForce GTX 670; Memory: 64 GB; OS: Ubuntu 12.04)

BF-fDSIFT
BF-fGALIF
CDMR-BF-fDSIFTCDMR-BF-fGALIF
UMR-BF-fDSIFT
UMR-BF-fGALIF

C++, CUDA
C++
C++
C++
MatlabMatlab

0.62
0.27
0.83
0.50
314.82109.77

2
2
2
2
4
3

Li (CPU: Intel Core 2 Duo E7500 @ 2.93 GHz; Memory: 16 GB; OS: Windows 7 64-bit)

SBR-VC_NUM_100
SBR-2D3D_NUM_100

C/C++
C/C++

233.77178.56

4
3

Saavedra (CPU: Intel Core i7-3770 CPU @ 3.40 GHz; Memory: 8 GB; OS: Ubuntu 11.10)

HOG-SIL
HELO-SIL
FDC

C++
C++
C++

0.02
0.02
0.02

1
1
1

A brief analysis on the computational efﬁciency of the ‘‘CDMR-’’and ‘‘UMR-’’ approaches is as follows. Both approaches are used to
improve accuracy of inter-feature distance and employ so called‘‘manifold ranking’’ [66] as its inter-feature distance metric learning.
Manifold ranking comprises two steps: manifold graph formationand diffusion, which respectively have a upper bound of computational complexity of O (N 2 ) and O (N 3 ), where N is the total numberof feature vectors. For the UMR, the matrix representing the manifold graph is sparse, thus its actual cost is much less than O (N 3 ),but still much more than O (N). The UMR forms a graph connecting
all the features from all the views (42 views per 3D model) of all

the 3D models. Therefore, if there are 1000 models in a database,N = 42  1000 = 42000. It is true that this big size, e.g. N = 42000,
pushes the limit of computational cost, both in terms of space andtime. For the CDMR, the matrix representing the manifold graph is
not sparse, but a much smaller number of feature vectors (thus smaller graph) leads to less computational cost than the UMR. A CDMR
graph is smaller because it uses only one feature vector for each
3D model. Both UMR and CDMR produce better accuracy than simple
distance computation among a pair of features. However, they arecomputationally expensive, and thus are not scalable for large
benchmarks and deserve further study.

74

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

Table 9Performance metrics for the performance comparison on the training dataset of the SHREC’13 Sketch Track Benchmark. ‘‘R’’ denotes the ranking group number.
Contributor

Method

NN

FT

ST

E

DCG

AP

R

FuruyaBF-fDSIFT
BF-fGALIFBF-fGALIF + BF-fDSIFTCDMR-BF-fDSIFTCDMR-BF-fGALIF
CDMR-BF-fGALIF + CDMR-BF-fDSIFT
UMR-BF-fDSIFT
UMR-BF-fGALIF
UMR-BF-fGALIF + UMR-BF-fDSIFT

0.153
0.183
0.210
0.217
0.238
0.273
0.160
0.170
0.208

0.099
0.101
0.123
0.158
0.175
0.205
0.115
0.120
0.131

0.158
0.154
0.185
0.231
0.267
0.301
0.182
0.185
0.201

0.095
0.089
0.106
0.136
0.149
0.167
0.107
0.104
0.115

0.354
0.355
0.381
0.413
0.428
0.459
0.369
0.371
0.387

0.119
0.118
0.142
0.196
0.215
0.247
0.136
0.135
0.152

3
3
2
1
1
1
2
2
2

Li

SBR-VC_NUM_100
SBR-VC_NUM_50
SBR-2D-3D_NUM_50

0.160
0.131
0.133

0.097
0.082
0.080

0.149
0.130
0.126

0.085
0.076
0.075

0.349
0.333
0.330

0.113
0.098
0.097

3
3
3

Pascoal

HTD

0.019

0.017

0.033

0.018

0.241

0.025

5

Saavedra

HOG-SIL
HELO-SIL
FDC

0.104
0.104
0.062

0.066
0.061
0.049

0.104
0.092
0.085

0.059
0.052
0.051

0.304
0.300
0.295

0.082
0.076
0.062

4
4
4

Table 10
Performance metrics for the performance comparison on the testing dataset of the SHREC’13 Sketch Track Benchmark. ‘‘R’’ denotes the ranking group number.
Contributor

Method

NN

FT

ST

E

DCG

AP

R

FuruyaBF-fDSIFT
BF-fGALIFBF-fGALIF + BF-fDSIFTCDMR-BF-fDSIFTCDMR-BF-fGALIF
CDMR-BF-fGALIF + CDMR-BF-fDSIFT
UMR-BF-fDSIFT
UMR-BF-fGALIF
UMR-BF-fGALIF + UMR-BF-fDSIFT

0.145
0.176
0.213
0.217
0.242
0.279
0.154
0.159
0.209

0.099
0.101
0.123
0.156
0.174
0.203
0.113
0.119
0.131

0.154
0.156
0.186
0.231
0.263
0.296
0.178
0.179
0.195

0.093
0.091
0.107
0.135
0.146
0.166
0.104
0.102
0.113

0.351
0.354
0.379
0.411
0.427
0.458
0.366
0.367
0.386

0.115
0.119
0.143
0.193
0.215
0.246
0.133
0.131
0.152

3
3
2
1
1
1
2
2
2

Li

SBR-VC_NUM_100
SBR-VC_NUM_50
SBR-2D-3D_NUM_50

0.164
0.132
0.132

0.097
0.082
0.077

0.149
0.131
0.124

0.085
0.075
0.074

0.348
0.331
0.327

0.114
0.098
0.095

3
3
3

Pascoal

HTD

0.017

0.016

0.031

0.018

0.240

0.024

5

Saavedra

HOG-SIL
HELO-SIL
FDC

0.110
0.110
0.069

0.069
0.064
0.048

0.107
0.096
0.085

0.061
0.054
0.051

0.307
0.302
0.296

0.084
0.079
0.051

4
4
4

Table 11
Performance metrics for the performance comparison on the complete SHREC’13 Sketch Track Benchmark. ‘‘R’’ denotes the ranking group number.
Contributor

Method

NN

FT

ST

E

DCG

AP

R

FuruyaBF-fDSIFT
BF-fGALIFBF-fGALIF + BF-fDSIFTCDMR-BF-fDSIFTCDMR-BF-fGALIF
CDMR-BF-fGALIF + CDMR-BF-fDSIFT
UMR-BF-fDSIFT
UMR-BF-fGALIF
UMR-BF-fGALIF + UMR-BF-fDSIFT

0.150
0.180
0.211
0.217
0.239
0.275
0.158
0.166
0.209

0.099
0.101
0.123
0.157
0.175
0.204
0.114
0.119
0.131

0.157
0.154
0.186
0.231
0.265
0.299
0.180
0.182
0.199

0.094
0.090
0.106
0.135
0.148
0.167
0.106
0.103
0.114

0.353
0.354
0.380
0.412
0.428
0.459
0.368
0.370
0.387

0.118
0.119
0.142
0.195
0.215
0.247
0.135
0.134
0.152

3
3
2
1
1
1
2
2
2

Li

SBR-VC_NUM_100
SBR-VC_NUM_50
SBR-2D-3D_NUM_50

0.161
0.131
0.133

0.097
0.082
0.079

0.149
0.130
0.125

0.085
0.076
0.074

0.349
0.332
0.329

0.113
0.098
0.096

3
3
3

Pascoal

HTD

0.018

0.017

0.032

0.018

0.241

0.024

5

Saavedra

HOG-SIL
HELO-SIL
FDC

0.106
0.106
0.065

0.067
0.062
0.048

0.105
0.094
0.085

0.060
0.053
0.051

0.305
0.301
0.296

0.083
0.077
0.062

4
4
4

7. Discussions
7.1. Methods
We classify all contributed 15 methods with respect to the different classiﬁcation methods mentioned in the ﬁrst paragraph of

Section 2.1. Most methods employ local features, except that
SBR-VC, SBR-2D-3D, FDC and HTD perform global feature matching. Only SBR-VC and SBR-2D-3D perform view selection while
all the other methods adopt the approach of ﬁxed view sampling.
All the 9 methods of the Furuya’s group adopt a Bag-of-Words
framework and among them 6 ‘‘CDMR-’’ and ‘‘UMR-’’ based

75

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

Table 12
Timing information comparison on the ‘‘Testing’’ dataset of SHREC’13 Sketch Track Benchmark: t is the average response time (in seconds) per query. ‘‘R’’ denotes the ranking
group number. Note that for SBR-VC, the number of representative views N c ¼ C6  N 0 .
Contributor (with computer conﬁguration)

MethodLanguaget

R

Furuya (CPU: Intel Core i7 3930 K @ 3.20 Hz; GPU: NVIDIA GeForce GTX 670; Memory: 64 GB; OS: Ubuntu 12.04)

BF-fDSIFT
BF-fGALIF
CDMR-BF-fDSIFTCDMR-BF-fGALIF
UMR-BF-fDSIFT
UMR-BF-fGALIF

C++, CUDA
C++
C++
C++
MatlabMatlab

1.26
0.49
606.96615.9554853.77
27219.49

2
2
4
4
5
5

Li (CPU: Intel Core 2 Duo E7500 @ 2.93 GHz; Memory: 16 GB; OS: Windows 7 64-bit)

SBR-VC_NUM_100
SBR-VC_NUM_50
SBR-2D3D_NUM_50

C/C++
C/C++
C/C++

208.85
68.92
43.93

4
3
3

Pascoal (CPU: Intel Core i7-2760QM CPU @ 2.40 GHz (8CPU); Memory: 16 GB; OS: Windows 8)

HTD

Java

0.32

2

Saavedra (CPU: Intel Core i7-3770 CPU @ 3.40 GHz; Memory: 8 GB; OS: Ubuntu 11.10)

HOG-SIL
HELO-SIL
FDC

C++
C++
C++

0.09
0.09
0.09

1
1
1

methods utilize a distance metric learning approach [66] (one typeof machine learning techniques) to signiﬁcantly improve the performance of their methods; while the remaining 6 methods contributed by the other 3 groups directly compare global featuresand do not adopt any machine learning approach.
Based on the fact that all the top algorithms on the two benchmarks are machine learning technique-based ones and it contributes much to the best performance obtained, we regard it as apromising approach to advance the performance of existing
retrieval algorithms. This can be also found in our performance
evaluation results: though SBR-VC and SBR-2D-3D are at least
comparable to BF-fGALIF and BF-fDSIFT, CDMR-BF-fGALIF
evidently outperforms either of them after employing the‘‘CDMR-’’ distance learning approach. However, though utilizing amachine learning approach can obviously improve the retrieval
performance of a sketch-based retrieval algorithm, it may alsosigniﬁcantly increase its retrieval time. Therefore, more researchand improvements are deserved to solve this contradictory issue
in order to apply machine learning techniques into sketch-based
3D model retrieval in a scalable manner.
In terms of 2D shape descriptors, shape context, GALIF, DSIFT and
HOG (refer to [4,14–16,5,17]) features are relatively more promisingin achieving top performance if compared with Fourier descriptors,
and structure or topology-based ones. We also have found that compared with global shape descriptors based on direct feature matching, it is much easier for local shape descriptors to achieve realtime efﬁciency while combined with a Bag-of-Words framework.

retrieval methods in terms of accuracy, scalability and efﬁciency.
Overall, Furuya’s CDMR-BF-fGALIF + CDMR-BF-fDSIFT and CDMRBF-fGALIF methods perform best, followed by the ﬁve comparable
methods of Furuya’s CDMR-BF-fDSIFT, UMR-BF-fGALIF + UMR-BFfDSIFT and UMR-BF-fGALIF, as well as Li’s SBR-VC_NUM_100 and
SBR-2D-3D_NUM_100; (2) On the large-scale benchmark, we candraw a similar conclusion: Furuya’s three CDMR-based algorithms(CDMR-BF-fGALIF + CDMR-BF-fDSIFT, CDMR-BF-fGALIF and CDMRBF-fGALIF) have the best performance, followed by their three
UMR-based algorithms (UMR-BF-fGALIF + UMR-BF-fDSIFT, UMRBF-fDSIFT and UMR-BF-fGALIF) and their hybrid approach BF-fGALIF + BF-fDSIFT. Furuya’s BF-fDSIFT, BF-fGALIF and Li’s SBR-VC and
SBR-2D-3D succeed them and they outperform Saavedra’s three
approaches (HOG-SIL, HELO-SIL and FDC) which are again better
than HTD. However, compared with the case of small-scale benchmark, all the performance drops drastically, which indicates boththe challenge of the large-scale benchmark and the new issues ofscalability of existing sketch-based retrieval algorithms. This will
also be helpful to guide our research on developing new sketchbased 3D retrieval algorithms or extending current methods toaccustom to the large-scale retrieval scenarios.
8.2. Efﬁciency comparison

The SHREC’12 Sketch Track Benchmark could be extended bysketch data as currently being compiled by other researchers, making
it more representative. Also, controlling the level of standardization
with respect to sketch parameters such as sketching quality, style,and level of detail is deemed interesting. The standard query sketches[56] included in this benchmark are a starting point to this direction.
While, the SHREC’13 Sketch Track Benchmark could be extended byadding more models to the target 3D model dataset to make each classcontain the same number of models, which will remove the remaining
bias and make the benchmark more representative.

(1) On the small-scale benchmark, in terms of retrieval speed,
we observe large differences between all methods: from 0.02 s(Saavedra’s three methods) to 314.82 s (Furuya’s UMR-BF-fDSIFT).
In this case, the best-performing ‘‘CDMR-’’ based methods, together with BF-fDSIFT and BF-fGALIF are interactive, while otherremaining approaches need improvement in this regard. (2) On
the large-scale benchmark, the difference in the retrieval speed iseven larger: from 0.09 s (Saavedra’s three methods) to 54853.77 s(Furuya’s UMR-BF-fDSIFT). What is more, we observe that the
speed of the top ‘‘CDMR-’’ based methods drops drastically(7301230 times slower) when scaled to a less than 2.5 times bigger benchmark, thus they can be further improved in this aspect.
Saavedra’s three methods are still the fastest, followed by Pascoal’s
HTD; while Li’s SBR-VC and SBR-2D-3D methods extend their retrieval time proportionally according to the scale of thebenchmark.

8. Conclusions and future work

8.3. Concluding remark

8.1. Overall performance evaluation

In conclusion, the small-scale sketch-based retrieval track is theﬁrst attempt to include this topic in SHREC in order to foster thischallenging and interesting research direction. Even though it isthe ﬁrst time, we already have 5 groups who have successfully

7.2. Benchmarks(1) On the small-scale benchmark, we performed a comprehensively comparative evaluation of 14 state-of-the-art sketch-based

76

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80
0.5

0.5
Furuya (CDMR−BF−fGALIF+CDMR−BF−fDSIFT)
Furuya (CDMR−BF−fGALIF)
Furuya (CDMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF+UMR−BF−fDSIFT)
Furuya (BF−fGALIF+BF−fDSIFT)
Furuya (UMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF)
Furuya (BF−fGALIF)
Furuya (BF−fDSIFT)
Li (SBR−VC_NUM_100)
Li (SBR−VC_NUM_50)
Li (SBR−2D−3D_NUM_50)
Saavedra (HOG−SIL)
Saavedra (HELO−SIL)
Saavedra (FDC)
Pascoal (HTD)

0.45

0.4

0.35

0.3

0.45

0.4

0.35

0.3

0.25

0.25

0.2

0.2

0.15

0.15

0.1

0.1

0.05

0.05

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Furuya (CDMR−BF−fGALIF+CDMR−BF−fDSIFT)
Furuya (CDMR−BF−fGALIF)
Furuya (CDMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF+UMR−BF−fDSIFT)
Furuya (BF−fGALIF+BF−fDSIFT)
Furuya (UMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF)
Furuya (BF−fGALIF)
Furuya (BF−fDSIFT)
Li (SBR−VC_NUM_100)
Li (SBR−VC_NUM_50)
Li (SBR−2D−3D_NUM_50)
Saavedra (HOG−SIL)
Saavedra (HELO−SIL)
Saavedra (FDC)
Pascoal (HTD)

0
0

1

0.1

0.2

0.3

0.4

Recall

0.5

0.6

0.7

0.8

0.9

1

Recall0.5
Furuya (CDMR−BF−fGALIF+CDMR−BF−fDSIFT)
Furuya (CDMR−BF−fGALIF)
Furuya (CDMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF+UMR−BF−fDSIFT)
Furuya (BF−fGALIF+BF−fDSIFT)
Furuya (UMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF)
Furuya (BF−fGALIF)
Furuya (BF−fDSIFT)
Li (SBR−VC_NUM_100)
Li (SBR−VC_NUM_50)
Li (SBR−2D−3D_NUM_50)
Saavedra (HOG−SIL)
Saavedra (HELO−SIL)
Saavedra (FDC)
Pascoal (HTD)

0.45

0.4

0.35

0.3

0.25

0.2

0.15

0.1

0.05

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

RecallFig. 18. Precision-Recall diagram performance comparisons on different datasets of the SHREC’13 Sketch Track Benchmark for the 16 runs of the 15 contributed methods.

participated. On the other hand, the large-scale sketch-based retrieval track is an attempt to further foster this challenging andinteresting research direction encouraged by the success of
SHREC’12 Sketch-based 3D shape retrieval track. Though thebenchmark is very challenging, we still have 3 groups who havesuccessfully participated in the track and they have contributed 5
runs of 4 methods. Through these two tracks, we provided two
common platforms (the two benchmarks) to solicit current
sketch-based 3D model retrieval approaches in terms of both
small-scale and large-scale retrieval scenarios. This helps us identify state-of-the-art methods as well as future research directions

for this research area. We also hope that the small-scale andlarge-scale sketch retrieval benchmarks together with the evaluation code will become useful references for researchers in thiscommunity.
To comprehensively evaluate the participating methods in the
two tracks and other sketch-based 3D model retrieval algorithms,
solicit the state-of-the-art approaches, and provide a more complete reference for the researchers in this community, we invite related authors to run their methods on both benchmarks. Finally, adetailed comparative evaluation has been accomplished based on
17 contributed runs of 15 (4 top participating algorithms and 11

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80
1

Furuya (CDMR−BF−fGALIF+CDMR−BF−fDSIFT)
Furuya (CDMR−BF−fGALIF)
Furuya (CDMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF+UMR−BF−fDSIFT)
Furuya (BF−fGALIF+BF−fDSIFT)
Furuya (UMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF)
Furuya (BF−fGALIF)
Furuya (BF−fDSIFT)
Li (SBR−VC_NUM_100)
Li (SBR−VC_NUM_50)
Li (SBR−2D−3D_NUM_50)
Saavedra (HOG−SIL)
Saavedra (HELO−SIL)
Saavedra (FDC)
Pascoal (HTD)

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Recall

1
Furuya (CDMR−BF−fGALIF+CDMR−BF−fDSIFT)
Furuya (CDMR−BF−fGALIF)
Furuya (CDMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF+UMR−BF−fDSIFT)
Furuya (BF−fGALIF+BF−fDSIFT)
Furuya (UMR−BF−fDSIFT)
Furuya (UMR−BF−fGALIF)
Furuya (BF−fGALIF)
Furuya (BF−fDSIFT)
Li (SBR−VC_NUM_100)
Li (SBR−VC_NUM_50)
Li (SBR−2D−3D_NUM_50)
Saavedra (HOG−SIL)
Saavedra (HELO−SIL)
Saavedra (FDC)
Pascoal (HTD)

0.9
0.8
0.7

Precision

0.6
0.5
0.4
0.3
0.2
0.1
0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

RecallFig. 19. Precision-Recall diagram performance comparisons of the ‘‘airplane’’ and‘‘ant’’ classes on the complete SHREC’13 Sketch Track Benchmark for the 15
contributed methods.

additional state-of-the-art approaches) best retrieval methods on
the two benchmarks. This evaluation work helps us to identify
the state-of-the-art approaches in terms of accuracy, scalability
and efﬁciency, existing problems and current challenges, as wellas promising research topics and techniques.
8.4. Future work
This evaluation work helps us to identify the state-of-the-art
approaches in terms of accuracy, scalability and efﬁciency,
existing problems and current challenges, as well as promising77

research topics and techniques. Therefore, we identify the future direction of this research area is developing efﬁcient algorithms which are scalable to different sizes and types of sketch
queries and models. It can be achieved in the following eight aspects.

 Scalable and interactive retrieval algorithms. In our evaluation, compared with the case of the small-scale benchmark,the performance of all the methods drops drastically on thelarge-scale benchmark, which evidently raises the issue of scalability of existing sketch-based retrieval algorithms. On theother hand, for some best-performing approaches their retrieval
time increases too fast on a larger dataset, which creates a hurdle for their applications. It is well known that highly interactive response times are a key requirement for interactive
sketch-based retrieval applications such as shadow drawing
for interactive retrieval [79], or modeling by sketched example.
Scalability of query processing time with respect to large target
database and descriptor sizes is an important issue yet to beaddressed. One possibility is to take advantage of already developed high-dimensional or metric index structures [80,81],
which can accelerate the typically many nearest-neighbor computations required. However, this implies restricting thedescriptors to vector spaces and metric distance functions. In
case that more complex descriptors or distance functions are
required for the retrieval task, developing ad hoc index structures may be required to efﬁciently fulﬁll this task. Also, we
see bag-of-words approaches in conjunction with inverted indices as promising to provide scalable answer times.
 Building large-scale benchmarks. Since scalability is so important an issue, we should create a large-scale sketch-based 3D
retrieval benchmark, in terms of both 2D sketches and 3D models, to evaluate the scalability property of sketch-based retrieval
methods.
 Interdisciplinary research directions. We notice that generally
the retrieval performance, either in terms of accuracy or efﬁciency, is far from satisfactory and the performance of existing
sketch-based retrieval algorithms drops apparently whenscaled to a large collection. To improve the retrieval accuracy,
we recommend utilizing knowledge and techniques from otherrelated disciplines, such as pattern recognition, machine learning, and computer vision. For example, to increase the accuracy
and efﬁciency in sketch-based retrieval, we can perform sketch
recognition ﬁrst and use the result to prioritize the comparison
between a query sketch and 3D models in the database. During
the evaluation, we have found that all the top algorithms on thetwo benchmarks utilize machine learning technique, which
contributes much to the best performance obtained. Therefore,
machine learning is another promising interdisciplinary
approach to further improve the performance of existing retrieval algorithms. However, we need to pay more attention to thescalability properties of the machine learning techniques
employed and make sure they or their variations can meet thereal time requirements of the retrieval applications.
 Query adaptive sketch-based retrieval algorithms. On theeffectiveness side, another promising direction for future work
is to consider adaptive sketch-based retrieval algorithms. Given
that different types (or modes) of user sketches can occur (suchas perspective, orthogonal, and abstract versus realistic), different descriptor types may be best suited for the search, depending on the sketch type. Adaptive retrieval systems could
improve the search by deciding an appropriate descriptor which
best supports the type of sketch query. Sketch-type dependent
evaluation benchmarking is needed to understand the possible
relationships between sketch types and method performance.

78

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80
810SHREC’12 Sketch Track
SHREC’13 Sketch Track
7

10

6

Average response time per query (ms)

10

5

10

4

10

3

10

2

10

1

10

0

10

fDSIFTfGALIF

C−fDSIFT C−fGALIF U−fDSIFT U−fGALIF

SBR−VC SBR−2D−3D

HOG

HELO

FDC

Fig. 20. Timing information comparison of the contributed algorithms based on the small-scale SHREC’12 Sketch Track Benchmark (‘‘Hand-drawn and Extended’’ dataset, 400
models) and the large-scale SHREC’13 Sketch Track Benchmark (‘‘Testing’’ dataset, 1258 models). Logarithmic scaling is applied on the Time axis. Methods fDSIFT, fGALIF, CfDSIFT, C-fGALIF, U-fDSIFT, and U-fGALIF denote BF-fDSIFT, BF-fGALIF, CDMR-BF-fDSIFT, CDMR-BF-fGALIF, UMR-BF-fDSIFT, and UMR-BF-fGALIF, respectively. Note that for
SBR-VC, NUM is set to 100 for both SHREC’12 and SHREC’13 Tracks, while different number of representative views have been adopted (N c ¼ C2  N 0 and N c ¼ C6  N 0 for
SHREC’12 Sketch Track and SHREC’13 Sketch Track, respectively, see Section 5.3). Also note that different NUM values are used for SBR-2D-3D (NUM = 100 for SHREC’12
Sketch Track and NUM = 50 for SHREC’13 Sketch Track).

 Semantics-driven sketch-based retrieval and search intention study. To bridge the semantic gap between 2D sketchesand 3D models, a promising research direction is to develop
algorithms and benchmarks that deal more directly withsemantics (e.g., semantic categories) and search intention(e.g., per session speciﬁcation user intention, speciﬁcally, forexample, by relevance feedback).
 Developing new local shape descriptors. According to theevaluation, we have found that most efﬁcient retrieval algorithms adopt local shape descriptors. On the other hand, theretrieval algorithms based on HOG, GALIF, and DSIFT local shapedescriptors, or the shape context global shape descriptor, outperform those based on Fourier descriptors, or structure or
topology-based descriptors, in terms of retrieval accuracy.
Therefore, developing novel local shape descriptors is a relatively more promising research direction to meet the requirements of future applications, which require high efﬁciency
and accuracy.
 Domain speciﬁc sketch based retrieval algorithms and theirevaluation methods. We can extend sketch-based retrieval
for retrieving objects in images such as photographs and paintings; or special 3D objects like clothes and protein molecules. As
such, it is necessary to build an appropriate image and 3Dmodel database for benchmarking. New evaluation metrics
may be also needed for the speciﬁc domains.
 Scene sketch and partial sketch-based 3D retrieval. Generally,
existing sketch-based 3D model retrieval algorithms assume
there is only one object in the query sketch, and do not consider
the case of a 2D scene sketch query containing several objects,
which may overlap each other and also have their spatial context information. Therefore, sketch-based 3D model retrieval
in the context of a 2D scene sketch deserves our further explo-

ration. Finally, we note that our benchmarks address, in spirit,
the global retrieval model. Future benchmarking for sketchbased retrieval may in particular address partial sketch-based
3D retrieval algorithms which target interactively establishingcorrespondence between a partial sketch of an object and 3Dmodel parts.

Acknowledgments
This work has been supported by the Army Research Ofﬁce
grant W911NF-12-1-0057, Texas State University Research
Enhancement Program (REP), and NSF CRI 1305302 to Yijuan Lu,
as well as the Shape Metrology IMS to Afzal Godil.
The work of Benjamin Bustos has been funded by Fondecyt(Chile) Project 1110111.
The work of Pedro B. Pascoal, Alfredo Ferreira, Manuel J. Fonseca
reported in this paper has been supported by national funds
through FCT under contract Pest-OE/EEI/LA0021/2013.
Henry Johan is supported by Fraunhofer IDM@NTU, which isfunded by the National Research Foundation (NRF) and managed
through the multi-agency Interactive & Digital Media Programme
Ofﬁce (IDMPO) hosted by the Media Development Authority of Singapore (MDA).
We would like to thank Mathias Eitz (TU Berlin, Germany),
James Hays (Brown University, USA) and Marc Alexa (TU Berlin,
Germany) who built the large collection of sketches.
We would also like to thank Sang Min Yoon (Yonsei University,
Korea), Maximilian Scherer (TU Darmstadt, Germany), Tobias
Schreck (University of Konstanz) and Arjan Kuijper (Fraunhofer
IGD) who collected the TU Darmstadt and Fraunhofer IGD sketchdata.

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80

We would also like to thank Daniela Giorgi, Silvia Biasotti, Laura
Paraboschi (CNR-IMATI, Italy) who built the Watertight ShapeBenchmark for SHREC 2007 and Snograss and Vanderwart who
built the standard line drawings dataset, as well as Philip Shilane,
Patrick Min, Michael M. Kazhdan, Thomas A. Funkhouser (Princeton University, USA) who built the Princeton Shape Benchmark.
References[1] <http://www.itl.nist.gov/iad/vug/sharp/contest/2012/SBR/>, 2013.
[2] <http://www.itl.nist.gov/iad/vug/sharp/contest/2013/SBR/>, 2013.
[3] A.-P. Ta, C. Wolf, G. Lavoué, A. Baskurt, 3D object detection and viewpoint
selection in sketch images using local patch-based Zernike moments, in: S.D.
Kollias, Y.S. Avrithis (Eds.), CBMI, IEEE Computer Society, 2009, pp. 189–194.
[4] B. Li, T. Schreck, A. Godil, M. Alexa, T. Boubekeur, B. Bustos, J. Chen, M. Eitz, T.
Furuya, K. Hildebrand, S. Huang, H. Johan, A. Kuijper, R. Ohbuchi, R. Richter,
J.M. Saavedra, M. Scherer, T. Yanagimachi, G.-J. Yoon, S.M. Yoon, SHREC’12
track: Sketch-based 3D shape retrieval, in: Eurographics Workshop on 3D
Object Retrieval (3DOR), 2012, 2012, pp. 109–118.
[5] M. Eitz, R. Richter, T. Boubekeur, K. Hildebrand, M. Alexa, Sketch-based shape
retrieval, ACM Trans. Graph. 31 (2012) 31:1–31:10.
[6] P. Shilane, P. Min, M.M. Kazhdan, T.A. Funkhouser, The Princeton shapebenchmark, in: Shape Modeling International, IEEE Computer Society, 2004,
pp. 167–178.
[7] B. Li, Y. Lu, A. Godil, T. Schreck, M. Aono, H. Johan, J.M. Saavedra, S. Tashiro,
SHREC’13 track: large scale sketch-based 3D shape retrieval, in: Eurographics
Workshop on 3D Object Retrieval (3DOR), 2013, 2013, pp. 89–96.
[8] T. Funkhouser, P. Min, M. Kazhdan, J. Chen, A. Halderman, D. Dobkin, D. Jacobs,
A search engine for 3D models, ACM Trans. Graph. 22 (2003) 83–105.
[9] M.M. Kazhdan, T.A. Funkhouser, S. Rusinkiewicz, Rotation invariant sphericalharmonic representation of 3D shape descriptors, in: L. Kobbelt, P. Schröder, H.
Hoppe (Eds.), Symposium on Geometry Processing, ACM International
Conference Proceeding Series, vol. 43, Eurographics Association, 2003, pp.
156–164.
[10] S.M. Yoon, M. Scherer, T. Schreck, A. Kuijper, Sketch-based 3D model retrieval
using diffusion tensor ﬁelds of suggestive contours, in: A.D. Bimbo, S.-F.
Chang, A.W.M. Smeulders (Eds.), ACM Multimedia, ACM, 2010, pp. 193–200.
[11] J.M. Saavedra, B. Bustos, M. Scherer, T. Schreck, STELA: sketch-based 3D model
retrieval using a structure-based local approach, in: F.G.B.D. Natale, A.D.
Bimbo, A. Hanjalic, B.S. Manjunath, S. Satoh (Eds.), ICMR, ACM, 2011, pp.
26:1–26:8.
[12] D. Doug, F. Adam, R. Szymon, S. Anthony, Suggestive contours for conveying
shape, ACM Trans. Graph. 22 (2003) 848–855.
[13] M. Aono, H. Iwabuchi, 3D shape retrieval from a 2D image as query, in: Signal& Information Processing Association Annual Summit and Conference (APSIPAASC) 2012, 2012, pp. 1–10.
[14] M. Eitz, K. Hildebrand, T. Boubekeur, M. Alexa, Sketch-based 3D shape
retrieval, in: SIGGRAPH Talks, ACM, 2010, p. 1.
[15] M. Eitz, K. Hildebrand, T. Boubekeur, M. Alexa, An evaluation of descriptors forlarge-scale image retrieval from sketched feature lines, Comput. Graph. 34(2010) 482–498.
[16] M. Eitz, K. Hildebrand, T. Boubekeur, M. Alexa, Sketch-based image retrieval:benchmark and bag-of-features descriptors, IEEE Trans. Visual. Comput.
Graph. 17 (2011) 1624–1636.
[17] M. Eitz, J. Hays, M. Alexa, How do humans sketch objects?, ACM Trans Graph.
31 (2012) 44:1–44:10.
[18] T. Shao, W. Xu, K. Yin, J. Wang, K. Zhou, B. Guo, Discriminative sketch-based 3Dmodel retrieval via robust shape matching, Comput. Graph. Forum 30 (2011)2011–2020.
[19] B. Li, H. Johan, Sketch-based 3D model retrieval by incorporating 2D–3Dalignment, Multimedia Tools Appl. 65 (2013) 363–385.
[20] B. Li, H. Johan, View context: a 3D model feature for retrieval, in: S. Boll et al.
(Eds.), MMM 2010, LNCS, vol. 5916, Springer, Heidelberg, 2010, pp. 185–195.
[21] S. Belongie, J. Malik, J. Puzicha, Shape matching and object recognition using
shape contexts, IEEE Trans. Pattern Anal. Mach. Intell. 24 (2002) 509–522.
[22] B. Li, Y. Lu, R. Fares, Semantic sketch-based 3D model retrieval, in: ICME, IEEE,
2013, pp. 1–4.
[23] T. Xue, J. Liu, X. Tang, Example-based 3D object reconstruction from line
drawings, in: CVPR, IEEE, 2012, pp. 302–309.
[24] T. Xue, J. Liu, X. Tang, Object cut: complex 3D object reconstruction throughline drawing separation, in: The Twenty-Third IEEE Conference on Computer
Vision and Pattern Recognition (CVPR), 2010, 2010, pp. 1149–1156.
[25] J. Liu, Y. Chen, X. Tang, Decomposition of complex line drawings with hiddenlines for 3D planar-faced manifold object reconstruction, IEEE Trans. PatternAnal. Mach. Intell. 33 (2011) 3–15.
[26] X. Xie, K. Xu, N.J. Mitra, D. Cohen-Or, B. Chen, Sketch-to-design: context-based
part assembly, Comput. Graph. Forum 32 (2013) 233–245.
[27] K. Xu, K. Chen, H. Fu, W.-L. Sun, S.-M. Hu, Sketch2scene: sketch-based coretrieval and co-placement of 3D models, ACM Trans. Graph. 32 (2013) 123:1–
123:15.
[28] S. Kanai, Content-based 3D mesh model retrieval from hand-written sketch,Int. J. Interact. Des. Manuf. 2 (2008) 87–98.
[29] A. Tatsuma, M. Aono, Multi-Fourier spectra descriptor and augmentation with
spectral clustering for 3D shape retrieval, Vis. Comput. 25 (2009) 785–804.

79[30] S.M. Yoon, A. Kuijper, View-based 3D model retrieval using compressive
sensing based classiﬁcation, in: The 7th International Symposium on Imageand Signal Processing and Analysis, ISPA 2011, IEEE, 2011, pp. 437–442.
[31] J.M. Saavedra, B. Bustos, T. Schreck, S.M. Yoon, M. Scherer, Sketch-based 3Dmodel retrieval using keyshapes for global and local representation, in:Eurographics Workshop on 3D Object Retrieval (3DOR), 2012, 2012, pp. 47–50.
[32] T. Judd, F. Durand, E.H. Adelson, Apparent ridges for line drawing, ACM Trans.
Graph. 26 (2007) 19.
[33] Y. Ohtake, A.G. Belyaev, H.-P. Seidel, Ridge-valley lines on meshes via implicit
surface ﬁtting, ACM Trans. Graph. 23 (2004) 609–612.
[34] X. Xie, Y. He, F. Tian, H.S. Seah, X. Gu, H. Qin, An effective illustrativevisualization framework based on photic extremum lines (PELs), IEEE Trans.
Vis. Comput. Graph. 13 (2007) 1328–1335.
[35] L. Zhang, Y. He, H.S. Seah, Real-time computation of photic extremum lines(PELs), The Visual Comput. 26 (2010) 399–407.
[36] M. Kolomenkin, I. Shimshoni, A. Tal, Demarcating curves for shape illustration,
ACM Trans. Graph. 27 (2008) 157.
[37] Y. Miao, J. Feng, Perceptual-saliency extremum lines for 3D shape illustration,
The Visual Comput. 26 (2010) 433–443.
[38] L. Zhang, Y. He, J. Xia, X. Xie, W. Chen, Real-time shape illustration using
Laplacian lines, IEEE Trans. Vis. Comput. Graph. 17 (2011) 993–1006.
[39] L. Zhang, J. Xia, X. Ying, Y. He, W. Mueller-Wittig, H.S. Seah, Efﬁcient and robust
3D line drawings using difference-of-gaussian, Graph. Models 74 (2012) 87–98.
[40] M. Kolomenkin, I. Shimshoni, A. Tal, Multi-scale curve detection on surfaces,
in: CVPR, IEEE, 2013, pp. 1–8.
[41] D. DeCarlo, Depicting 3D shape using lines, Proc. SPIE 8291 (2012). 829116–
829116–16..
[42] D. Zhang, G. Lu, A comparative study of Fourier descriptors for shape
representation and retrieval, in: Proceedings of the Fifth Asian Conference
on Computer Vision (ACCV02), 2002, pp. 646–651.
[43] A. Sajjanhar, G. Lu, D. Zhang, Image retrieval using modiﬁed generic fourier
descriptors, in: B. Gupta (Ed.), Computers and their Applications, ISCA, 2004,
pp. 32–35.
[44] D. Zhang, G. Lu, Shape-based image retrieval using generic Fourier descriptor,
Signal Process. Image Commun. (2002) 825–848.
[45] A. Khotanzad, Y. Hong, Invariant image recognition by Zernike moments, IEEE
Trans. Pattern Anal. Mach. Intell. 12 (1990) 489–497.
[46] M. Novotni, R. Klein, 3D Zernike descriptors for content based shape retrieval,in: Proceedings of the 8th ACM Symposium on Solid Modeling andApplications, ACM Press, 2003, pp. 216–225.
[47] J. Revaud, G. Lavoué, A. Baskurt, Improving Zernike moments comparison for
optimal similarity and rotation angle retrieval, IEEE Trans. Pattern Anal. Mach.
Intell. 31 (2009) 627–636.
[48] T. Ojala, M. Pietikäinen, D. Harwood, A comparative study of texture measureswith classiﬁcation based on featured distributions, Pattern Recog. 29 (1996)
51–59.
[49] M. Eitz, K. Hildebrand, T. Boubekeur, M. Alexa, A descriptor for large scale
image retrieval based on sketched feature lines, in: C. Grimm, J.J. L Jr., (Eds.),
SBM, Eurographics Association, 2009, pp. 29–36.
[50] D.G. Lowe, Distinctive image features from scale-invariant keypoints, Int. J.
Comput. Vision 60 (2004) 91–110.
[51] H. Jegou, M. Douze, C. Schmid, P. Pérez, Aggregating local descriptors into a
compact image representation, in: The Twenty-Third IEEE Conference on
Computer Vision and Pattern Recognition (CVPR), 2010, 2010, pp. 3304–3311.
[52] T. Furuya, R. Ohbuchi, Dense sampling and fast encoding for 3D model
retrieval using bag-of-visual features, in: S. Marchand-Maillet, Y. Kompatsiaris(Eds.), CIVR, ACM, 2009, pp. 17:1–8.
[53] R. Ohbuchi, T. Furuya, Scale-weighted dense bag of visual features for 3Dmodel retrieval from a partial view 3D model, in: S. Marchand-Maillet, Y.
Kompatsiaris (Eds.), IEEE ICCV 2009 Workshop on Search in 3D and Video(S3DV), ACM, 2009, pp. 63–70.
[54] N. Dalal, B. Triggs, Histograms of oriented gradients for human detection, in:2005 IEEE Computer Society Conference on Computer Vision and Pattern
Recognition (CVPR 2005), IEEE Computer Society, 2005, pp. 886–893.
[55] E. Candès, D. Donoho, Curvelets: A surprisingly effective nonadaptive
representation of objects with edges, in: L.L. S et al. (Ed.), Curves andSurfaces, Vanderbilt University Press, Nashville, TN, 1999, pp. 1–16.
[56] J.G. Snodgrass, M. Vanderwart, A standardized set of 260 pictures: norms forname agreement, image agreement, familiarity, and visual complexity, J.
Experimen. Pyschol.: Human Learn. Mem. 6 (1980) 174–215.
[57] F.-X. Alario, L. Ferrand, A set of 400 pictures standardized for French: Norms
for name agreement, image agreement, familiarity, visual complexity, image
variability, and age of acquisition, Behav. Res. Meth. Instrum., Comput. 31(1999) 531–552.
[58] P. Bonin, R. Peereman, N. Malardier, A. Mot, M. Chalard, A new set of 299
pictures for psycholinguistic studies: French norms for name agreement,
image agreement, conceptual familiarity, visual complexity, image variability,
age of acquisition, and naming latencies, Behav. Res. Meth. Instrum., Comput.
35 (2003) 158–167.
[59] M. Sanfeliu, A. Fernandez, A set of 254 Snodgrass–vanderwart pictures
standardized for spanish: norms for name agreement, image agreement,
familiarity, and visual complexity, Behav. Res. Meth. Instrum., Comput. 28(1996) 537–555.
[60] S. Pompia, M. Miranda, O. Bueno, A set of 400 pictures standardised for
portuguese: norms for name agreement, familiarity and visual complexity forchildren and adults, Arquivos de Neuro-Psiquiatria 59 (2001) 330–337.

80

B. Li et al. / Computer Vision and Image Understanding 119 (2014) 57–80[61] F. Cole, A. Golovinskiy, A. Limpaecher, H.S. Barros, A. Finkelstein, T.A.
Funkhouser, S. Rusinkiewicz, Where do people draw lines?, ACM Trans
Graph. 27 (2008) 1–11.
[62] J.M. Saavedra, B. Bustos, An improved histogram of edge local orientations for
sketch-based image retrieval, in: M. Goesele, S. Roth, A. Kuijper, B. Schiele, K.
Schindler (Eds.), DAGM-Symposium, Lecture Notes in Computer Science, vol.
6376, Springer, 2010, pp. 432–441.
[63] R.C. Veltkamp, F.B. ter Haar, SHREC 2007 3D Retrieval Contest, Technical
Report UU-CS-2007-015, Department of Information and Computing Sciences,
Utrecht University, 2007.
[64] B. Li, H. Johan, 3D model retrieval using hybrid features and class information,
Multimedia Tools Appl. 62 (2013) 821–846.
[65] T. Furuya, R. Ohbuchi, Ranking on cross-domain manifold for sketch-based 3Dmodel retrieval, in: Cyberworlds 2013, 2013, pp. 1–8.
[66] D. Zhou, O. Bousquet, T.N. Lal, J. Weston, B. Schölkopf, Learning with local andglobal consistency, Advances in Neural Information Processing Systems, vol.
16, MIT Press, 2004, pp. 321–328.
[67] P. Geurts, D. Ernst, L. Wehenkel, Extremely randomized trees, Mach. Learn. 63(2006) 3–42.
[68] B. Li, Y. Lu, H. Johan, Sketch-based 3D model retrieval by viewpoint entropybased adaptive view clustering, in: U. Castellani, T. Schreck, S. Biasotti, I.
Pratikakis, A. Godil, R.C. Veltkamp (Eds.), 3DOR, Eurographics Association,
2013, pp. 49–56.
[69] M. Fonseca, A. Ferreira, J. Jorge, Sketch-based retrieval of vector drawings, in:
Sketch-based Interfaces and Modeling, 2011, 2011, pp. 181–201.
[70] P.M.A. Sousa, M.J. Fonseca, Sketch-based retrieval of drawings using spatial
proximity, J. Vis. Lang. Comput. 21 (2010) 69–80.

[71] Y.-T. Shen, D.-Y. Chen, X.-P. Tian, M. Ouhyoung, 3D model search engine basedon Lightﬁeld descriptors, in: Eurographics, 2003, 2003, pp. 1–7.
[72] J.L. Bentley, T. Ottmann, Algorithms for reporting and counting geometricintersections, IEEE Trans. Comput. 28 (1979) 643–647.
[73] M.M. Syslo, An efﬁcient cycle vector space algorithm for listing all cycles of aplanar graph, SIAM J. Comput. 10 (1981) 797–808.
[74] J.D. Horton, A polynomial-time algorithm to ﬁnd the shortest cycle basis of agraph, SIAM J. Comput. 16 (1987) 358–366.
[75] M.J. Egenhofer, K.K. Al-Taha, Reasoning about gradual changes of topologicalrelationships, in: A.U. Frank, I. Campari, U. Formentini (Eds.), Spatio-Temporal
Reasoning, Lecture Notes in Computer Science, vol. 639, Springer, 1992, pp.
196–219.
[76] M.J. Fonseca, C. Pimentel, J.A. Jorge, CALI: An online scribble recognizer for
calligraphic interfaces, in: Proceedings of the 2002 AAAI Spring Symposium
Sketch Understanding, 2002, pp. 51–58.
[77] D. Zhang, G. Luo, An integrated approach to shape based image retrieval, in:Proceedings of the 5th Asian Conference on Computer Vision (ACCV 2002),
2002, 2002, pp. 652–657.
[78] M. Muja, D.G. Lowe, Fast approximate nearest neighbors with automaticalgorithm conﬁguration, in: Proceedings of the International Conference on
Computer Vision Theory and Applications (VISAPP), 2009, 2009, pp. 331–340.
[79] Y.J. Lee, C.L. Zitnick, M.F. Cohen, Shadowdraw: real-time user guidance forfreehand drawing, ACM Trans. Graph. 30 (2011) 27:1–27:10.
[80] H. Samet, Foundations of Multidimensional and Metric Data Structures,Morgan Kaufman Publishers Inc., San Francisco, CA, USA, 2005.
[81] P. Zezula, G. Amato, V. Dohnal, M. Batko, Similarity search: the metric spaceapproach, Advances in Database Systems, vol. 32, Springer, 2006.