Eurographics Workshop on 3D Object Retrieval (2010), pp. 1–8
I. Pratikakis, M. Spagnuolo, T. Theoharis, and R. Veltkamp (Editors)

SHREC’10 Track: Non-rigid 3D Shape Retrieval
Z. Lian1,2 , A. Godil1 , T. Fabry3 , T. Furuya4 , J. Hermans3 ,R. Ohbuchi4 , C. Shu5 , D. Smeets3 , P. Suetens3 , D. Vandermeulen3 , S. Wuhrer5
1 National Institute of Standards and Technology, Gaithersburg, USA
2 Beihang University, Beijing, PR China
3 Katholieke Universiteit Leuven, Belgium
4 University of Yamanashi, Japan
5 National Research Council, Canada

Abstract
Non-rigid shape matching is one of the most challenging fields in content-based 3D object retrieval. The aim of the
SHREC 2010 - Shape Retrieval Contest of Non-rigid 3D Models is to evaluate and compare the effectiveness ofdifferent methods run on a non-rigid 3D shape benchmark consisting of 200 watertight triangular meshes. Threegroups with six methods have participated in this track and the retrieval performance was evaluated using six
commonly-used metrics.
Categories and Subject Descriptors (according to ACM CCS): I.5.4 [Pattern Recognition]: Computer Vision—
H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval—

1. Introduction
After years of rapid development, 3D shape retrieval has become an important area of research in several fields including computer graphics, pattern recognition, machine vision,and so on. However, previous efforts have been mainly devoted to the retrieval of rigid 3D models, and thus how toefficiently and effectively compare non-rigid shapes is still achallenging problem in the field of content-based 3D object
retrieval. As we know, non-rigid objects are commonly seenin our surroundings. Take Figure 1 for an example, a humanbeing can appear in quite different postures, which might
be identified as different kinds of objects using traditional
rigid-shape analyzing techniques. Up to now, just a few
methods have been reported to address this problem, generally, they utilized local features (e.g. [SF07] [OOFB08]),
or global isometric-invariant features (e.g. [EK03] [RpSS]),or the combination of above two features (e.g. [GSCO07])
to generate 3D shape descriptors, that are invariant or approximately invariant under isometric transformations (e.g.
bending and articulation).
To promote the investigation of non-rigid 3D shape retrieval, we organized the SHREC 2010 - Shape Retrieval
Contest of Non-rigid 3D Models. In this track, we provided
submitted to Eurographics Workshop on 3D Object Retrieval (2010)

a non-rigid shape database, that contains 200 watertight 3D
meshes with randomized name indexes, based on the McGill
Shape Benchmark [ZKCS05]. Each participant was asked tosubmit up to five dissimilarity matrices calculated using their
methods in one week. Finally, six matrices were submitted
by three groups, and then the retrieval performance was measured and compared using six standard evaluation metrics.

Figure 1: Examples of non-rigid models.
The remainder of the paper is organized as follows. Section 2 shows the data collection of a non-rigid shape benchmark. Section 3 indicates how to measure the retrieval performance based on the benchmark, while participants’ information is described in Section 4. Afterwards, Section 5
discusses briefly the methods tested in this track and Section
6 demonstrates the evaluation results. Finally, the conclusionof this paper is provided in Section 7.

2

Z. Lian et al. / SHREC’10 Track: Non-rigid 3D Shape Retrieval

Figure 2: Models of our database that is divided into 10 classes.

2. Data Collection

4. Participants

The database used in this track consists of 200 watertight 3D
triangular meshes, which are selected from the McGill Articulated Shape Benchmark database [ZKCS05] [SZM∗ 08].
Eleven of these original models are modified (or replaced by
new models created by us) to make sure that all meshes inour database are watertight and they don’t have any topology errors. We then equally classify these 200 models into
10 categories based on their semantic meanings, as shownin Figure 2, each class contains 20 objects with distinct postures.

There are three groups participating in this track and, totally,
six dissimilarity matrices have been submitted,

3. Evaluation
Participants are asked to apply their methods to calculate
the dissimilarity between every two objects and then generate corresponding dissimilarity matrices. Since our database
contains 200 objects, the matrix is composed of 200 × 200
floating point numbers, where the number at position (i, j)
represents the dissimilarity between models i and j.
Given a dissimilarity matrix, the retrieval performance ofthe method can be quantitatively evaluated based on the following statistics: 1) Nearest Neighbor (NN), 2) First Tier
(FT), 3) Second Tier (ST), 4) E-measure (E), and 5) Discounted Cumulative Gain (DCG). In order to give the reader
a more intuitive feeling about the results, precision-recall
curves are also computed for each class as well as the whole
database. More details about these standard evaluation metrics can be found in [SMKF04]. In fact, we directly used thereliable source code provided by the Princeton Shape Benchmark [SMKF04] to carry out the evaluation.

1. MR-BF-DSIFT-E and BF-DSIFT-E run by R. Ohbuchi
and T. Furuya, from University of Yamanashi, Japan.
2. DMEVD_run1, DMEVD_run2, and DMEVD_run3 run
by D. Smeets, T. Fabry, J. Hermans, D. Vandermeulenand P. Suetens, from Katholieke Universiteit Leuven,
Belgium.
3. CF run by S. Wuhrer and C. Shu, from National ResearchCouncil, Canada.
5. Methods
5.1. Bag-of Densely-Sampled Local Visual Features, by
R. Ohbuchi and T. Furuya
The algorithm compares 3D shapes based on their appearances, that are, range images of the object rendered frommultiple viewpoints. The algorithm is designed so that it
could handle (1) a diverse range of shape representations,
including polygon soup, point set, or B-rep solid, and (2)models having articulation or deformation.
Appearance based comparison gives the algorithm its
ability to handle diverse shape representation. Multipleviewpoint rendering of dozens of range images coupled with
(2D) rotation invariant image feature gives the algorithm its
rotation invariance. Invariance to articulation and/or global
deformation is achieved through the use of a set of multiscale, local, visual features integrated into a feature vector
per 3D model by using Bag-of-Features (BoF) approach. A
submitted to Eurographics Workshop on 3D Object Retrieval (2010)

Z. Lian et al. / SHREC’10 Track: Non-rigid 3D Shape Retrieval

3

Figure 3: Flow of the Bag-of-Feature Dense-SIFT with ERC-Tree (BF-DSIFT-E) algorithm.

feature vector per 3D model makes the cost of comparison
among a pair of 3D models much lower than comparing setsof features, each consisting of thousands of local features.
The algorithm is called Bag-of- Features Dense-SIFT with
Extremely randomized tree (BF-DSIFT-E). Please refer tothe paper by Furuya et al. [FO09] for the details. While most
3D model retrieval algorithms deal with invariance to similarity transformation, very few algorithms achieve invariance to articulation while being able to accept 3D models
having diverse set of 3D shape representations.
Figure 3 shows the processing flow of the BF-DSIFT- E
algorithm. After normalizing the model for its position andscale, dozens of range images of the model are generated byusing multiple virtual cameras looking inward at the model
sitting at the coordinate origin. From each range image, ouralgorithm densely and randomly samples a few hundredsof local, multiscale image feature Scale Invariant Feature
Transform (SIFT) by David Lowe [Low04]. Salient point
detector of the SIFT is disabled for the dense sampling. A
SIFT feature, typically having 128 dimensions, encodes position, orientation, and scale of gray-scale gradient changeof the image about the sample point.
A 3D model is rendered into 42 depth images, each oneof which then is sampled at 300 or so random locations.
Thus, a 3D model is described by a set of about 12k SIFT
features. The set of thousands of visual features is integrated into a feature vector per model by using BoF (e.g.,[CDF∗ 04] [SZ03]). The BoF approach vector quantizes, orencodes, a SIFT feature into a representative vector, or a“visual word”, using a previously learned codebook. Visual
words are accumulated into a histogram, which is the feature vector for the 3D model. The optimal dimension of thehistogram, that is, the dimension of BoF-integrated feature
vector, depends on the database. The dimension of featuresubmitted to Eurographics Workshop on 3D Object Retrieval (2010)

vector is experimentally chosen as about 30k for the nonrigid model.
To extract this many features quickly, a fast GPUbased implementation of SIFT algorithm called SiftGPU
by Wu [Wu] is applied. The Extremely Randomized Clustering Tree, or ERC-Tree, by Guerts et al. [GEW06], isalso used for both feature set clustering during codebook
learning and for vector quantization of SIFT features. Witha small penalty in retrieval performance, the ERC-Tree ismuch faster than k-means clustering during codebook learning and naive linear search during VQ.
To derive ranked list of retrieval results given a query,
two methods are employed: simple distance computation using Kullback-Leibler Divergence (KLD), and a
distance-metric learning approach called Manifold Ranking(MR) [ZWG∗ 03] with a small modification. In the retrieval
experiment, the version that used KLD is named BF-DSIFTE, while the one used MR is named MR-BF-DSIFT-E. The
KLD below performs well for comparing two histogrambased feature vectors x and y.
nydKLD (x, y) = ∑ (yi − xi )ln i
xi
i=1

The MR first estimates the distribution of features in a
low-dimensional subspace, or “manifold” approximated bya mesh. The mesh is created based on the proximity of feature points, and its edges are weighted based on the distanceamong the feature points. It then computes similarity among
the features on the manifold using a process similarity solving a diffusion equation. A relevance rank is diffused fromthe source, that is, the query. At an equilibrium state, theconcentration of the relevance rank at a feature point indicates its closeness to the query. KLD is utilized to form the
manifold mesh on which the diffusion takes place.

4

Z. Lian et al. / SHREC’10 Track: Non-rigid 3D Shape Retrieval

5.2. Inelastic Deformation Invariant Modal
Representation, by D. Smeets, T. Fabry, J.
Hermans, D. Vandermeulen and P. Suetens
In this section, a 3D shape recognition method which is invariant for inelastic deformations is proposed, while not requiring explicit point correspondences for shape comparison.
5.2.1. Inelastic deformation invariant representations
The 3D shapes are represented by inelastic deformation invariant matrices: the geodesic distance matrix (GDM) andthe diffusion distance matrix (DDM). The former contains
the geodesic distance between each pair of points on the surface. This distance is the length of the shortest path on theobject surface between two points on the object. Geodesic
distances are calculated by solving the Eikonal equation,|∇T (P)| = 1, on the surface, which can be achieved witha fast marching algorithm for triangulated meshes [PC08].
Isometric deformations, and thus also inelastic deformations, leave these geodesic distances unchanged.

Figure 5: The diffusion distance matrix as an elastic deformation invariant representation, after a diffusion time oftD = 200 (left) and tD = 800 (right).

order invariant, this correspondence should not be known.
As such, object recognition reduces to direct comparison of
the shape descriptors without the need to establish explicit
point correspondences. For computational reasons, only thek largest singular values are calculated. For the GDM, k is
chosen to be 19, for the DDM 11.
5.2.3. Shape descriptor comparison
The modal representations of the GDM and DDM, calculated for tD = 800, are then compared using the normalized
Euclidean distance and fused together with the product rule.
5.3. Non-Rigid Shape Retrieval Using Canonical Forms,
by S. Wuhrer and C. Shu

Figure 4: The geodesic distance matrix as an elastic deformation invariant representation of the object shown left.
The diffusion distance matrix contains the average diffusion distance between each pair of points on the surface. The
average diffusion distance is the probability that a particle,
started in one point, arrives at the other point after a diffusion
process ran for a certain time tD . This distance is calculated
solving the heat equation, ∂t u = α∆X u, on the surface. Practically this can be achieved by solving the generalized eigen
decomposition problem of the discretized Laplace-Beltrami
operator, LΦ = λAΦ. A is a term proportional to the area ofthe triangles in the mesh and L is the laplacian of the surface [BBK∗ 09].
5.2.2. Sampling order invariant modal representations
Using the elastic deformation invariant distance matrices,a shape descriptor is needed that is invariant to the sampling order of points on the surfaces represented. It can beproved that the modal representation of these distance matrices, i.e. the singular value matrix, is invariant to the samplingorder under the condition that each point on one surface
has one corresponding point on the other surface [SFH∗ 09].
Therefore, the surfaces are resampled such that each surface
has the same number of points assuming a one to one correspondence. However, as the shape descriptor is sampling

In this section, a method is presented that evaluates the dissimilarity between two Non-Rigid 3D models S(0) and S(1)represented by triangular meshes. The method proceeds by
deforming the meshes into pose-invariant canonical forms
X (0) and X (1) and by computing the dissimilarity between
S(0) and S(1) using the Euclidean distance between X (0) andX (1) .
Canonical forms were introduced by Elad and Kimmel [EK03]. The canonical form X (i) of a surface S(i) is the
mapping of S(i) to R(d) , such that the Euclidean distances
between the mapped vertices approximate the geodesic distances between the original vertices well. Here, d is the dimension of the target space. We set d = 3 in our experiments.
The canonical form is computed via multi-dimensional scaling with the geodesic distances between vertices on thetriangular manifold as dissimilarities. Hence, the canonical form of a non-rigid body is pose-invariant. The fast
marching [KS98] is first used to compute geodesic distanceson S(i) , and then the least-squares multi-dimensional scaling [BG97] is applied to compute the canonical form in R3 .
For increased space efficiency, the canonical form is computed using a coarse-to-fine strategy as outlined by Wuhrer
et al. [WSAB07]. The approach by Wuhrer et al. consistsof two steps. First, n0 vertices of S(i) are used to computea canonical form at low resolution. Second, the remaining
vertices of S(i) are added to the canonical form one by one
submitted to Eurographics Workshop on 3D Object Retrieval (2010)

Z. Lian et al. / SHREC’10 Track: Non-rigid 3D Shape Retrieval

by minimizing a least-squares energy function. In our experiments, n0 = 500.
To compute the dissimilarity δ, the average distance ofpoints on X (0) to their nearest neighbors on X (1) is calculated
and vice versa. More precisely, the dissimilarity is computedas,δ=∑ p∈X (0) ||NX (1) (p), p||n(0)+∑ p∈X (1) ||NX (0) (p), p||n(1)5probably because they are all specifically designed for nonrigid 3D shapes. Considering the values of NN and DCG,
Smeets’s DMEVD_run1 give the best results, while if webased the evaluation on FT, ST, and E-measure, Ohbuchi’s
MR-BF-DSIFT-E would take the first place. Similar observations can be made from Figure 6, where the precisionrecall curves of the best two runs submitted by Ohbuchi etal. and Smeets et al. are both very close to the ideal horizontal line (i.e. the perfect result). Yet, it is hard to say clearly
which method obtains the best performance.

where n(i) is the number of vertices of X (i) , p ∈ X (i)means that p is a vertex of X (i) , NX (i) (p) is the vertex of
X (i) that is closest to p , and ||., .|| denotes the Euclidean
distance between two vertices. Kd-trees is applied to speed
up the nearest neighbor search [AM93].
6. Results
In this section, we present the results of the threegroups that submitted six runs, which are denoted as MRBF-DSIFT-E, BF-DSIFT-E, DMEVD_run1, DMEVD_run2,
DMEVD_run3, and CF, respectively, to this track. Given thesix 200 × 200 dissimilarity matrices obtained using thesemethods, we carry out evaluations not only on the average
performance of the whole database, but also on the result
corresponding to each specific class. The performance measures adopted here are the five quantitative statistics (i.e. NN,
FT, ST, E, and DCG) and the Precision-recall plot mentioned
in Section 3.

Figure 6: Precision-recall curves of all runs evaluated forthe whole database.
Table 1 and Figure 6 show the retrieval performance of all
six methods evaluated on the whole database. As we can see
from Table 1 where quantitative retrieval statics are reported,these methods obtain good results on the given database,submitted to Eurographics Workshop on 3D Object Retrieval (2010)

Figure 7: Precision-recall curves of the best runs of eachparticipant evaluated for two classes in the non-rigid
database.
Figure 7 and Figure 8 display the Precision-recall curvesof the best runs (i.e. Ohbuchi’s MR-BF-DSIFT-E, Smeets’s
DMEVD_run1, and Wuhrer’s CF) of each group measured for every class in the non-rigid database. We observe
that, none of these methods could guarantee better performance against others for all kinds of models. For example, Wuhrer’s CF obtained the best result when searchingfor teddy bears, and Smeets’s DMEVD_run1 clearly outperforms other methods considering the retrieval of spiders, while Ohbuchi’s MR-BF-DSIFT-E is without doubt thebest for hands, octopuses, and pliers. Generally speaking,algorithms developed by Ohbuchi et al. and Smeets et al.
work considerably well for every class in this track, as theirprecision-recall curves all appear in the top right parts ofthese figures.
In addition to the calculation of these performance statistics, we have also created a web interface [NIS], which displays the retrieved models for all objects and methods, toanalyze the results. Using the web interface, users are able
to examine the responses of the participants’ methods to individual query models and visually inspect the effectivenessof the methods for every object in the database. Several retrieval examples are shown and compared in Figure 9, where
two queries are provided to search for similar models using
three different methods. We find that, no method always outperforms others for every query object and they all have theirown strengths as well as weaknesses for particular models.
Base on the criterion of method classification describedin Section 1, the participants’ algorithms can be divided

6

Z. Lian et al. / SHREC’10 Track: Non-rigid 3D Shape Retrieval

Table 1: Retrieval performance of all runs evaluated using five standard measures evaluated for the whole database.

Figure 8: Precision-recall curves of the best runs of each participant evaluated for other eight classes in the non-rigid database.

into two categories, 1) methods using local features: MRBF-DSIFT-E and BF-DSIFT-E; 2) methods using global
isometric-invariant features: DMEVD and CF. We speculatethat the combination of these two kinds of invariant features
could give better retrieval performance for non-rigid models. It should also be pointed out that, the MR-BF-DSIFT-E
method apply an unsupervised machine learning algorithm(i.e. manifold ranking) which can be applied to enhance theresults of any other approaches. However, the time consuming manifold ranking might not well suited for the retrieval
application in large-scale databases.

7. Conclusion
In this paper, we first described the database of non-rigid 3D
shapes and then mentioned how to measure retrieval performance for the SHREC 2010 - Shape Retrieval Contest of
Non-rigid 3D Models. Afterwards, we briefly introduced thesix methods used by three groups who participated in thistrack. Finally, experimental results were presented to compare the effectiveness of different algorithms.
The non-rigid track organized this year is the first attemptin the history of SHREC to specifically focus on the performance evaluation of non-rigid 3D shape retrieval algorithms, and it is far from perfect. On the one hand, until recently just a few such kinds of practical methods have beenreported, therefore, we only had three groups taking part inthis track. On the other hand, because both creating and collecting large numbers of articulated watertight models are
not trivial tasks, we had to evaluate the participates’ methods
based on a small database consisting of 200 models. Hopefully, there will be more researchers working on non-rigid
3D shape retrieval in the future, and more groups will participate in the next SHREC non-rigid track, where a large-scale
database could be available.

submitted to Eurographics Workshop on 3D Object Retrieval (2010)

Z. Lian et al. / SHREC’10 Track: Non-rigid 3D Shape Retrieval

7

Figure 9: Retrieval examples of three methods using the web interface of the SHREC non-rigid track. The left bottom in the
web interface displays the thumbnail of a query and the right top part shows retrieved models.

ACKNOWLEDGMENTS
This work has been supported by the SIMA and the IDUS
program. We would like to thank the Shape Analysis Groupin McGill University for providing the McGill 3D ShapeBenchmark database, and we are also grateful to Benny Cheung for creating the web interface mentioned in this paper.

R., M AHMOUDI M., S APIRO G.: A Gromov-Hausdorff framework with diffusion geometry for topologically-robust non-rigid
shape matching. International Journal of Computer Vision(2009). published online.
[BG97] B ORG I., G ROENEN P.: Modern Multidimensional Scaling Theory and Applications. Springer, 1997.

References[CDF∗ 04] C SURKA G., DANCE C. R., FAN L., W ILLAMOWSKI
J., B RAY C.: Visual categorization with bags of keypoints. In
Proc. ECCV’04 workshop on Statistical Learning in Computer
Vision (2004), pp. 59–74.

[AM93] A RYA S., M OUNT D. M.: Approximate nearest neighbor queries in fixed dimensions. In ACM-SIAM Symposium on
Discrete Algorithms (1993), pp. 271–280.

[EK03] E LAD A., K IMMEL R.: On bending invariant signatures
for surface. IEEE Trans. Pattern Analysis and Machine Intelligence 25, 10 (2003), 1285–1295.

[BBK∗ 09]

[FO09]B RONSTEIN A. M., B RONSTEIN M. M., K IMMEL

submitted to Eurographics Workshop on 3D Object Retrieval (2010)

F URUYA T., O HBUCHI R.: Dense sampling and fast en-

8

Z. Lian et al. / SHREC’10 Track: Non-rigid 3D Shape Retrieval
coding for 3d model retrieval using bag-of-visual features. In
Proc. ACM CIVR 2009 (2009).

[GEW06] G UERTS P., E RNST D., W EHENKEL L.: Extremely
randomized trees. Machine Learning 36, 1 (2006), 3–42.
[GSCO07] G AL R., S HAMIR A., C OHEN -O R D.: Pose-oblivious
shape signature. IEEE Trans. Visualization and Computer
Graphics 13, 2 (2007), 261–271.
[KS98] K IMMEL R., S ETHIAN J.: Computing geodesic paths on
manifolds. In Proc. the National Academy of Science (1998),
pp. 8431–8435.
[Low04] L OWE D. G.: Distinctive image features from scaleinvariant keypoints. International Journal of Computer Vision60, 2 (2004), 91–110.
[NIS] NIST:
The
SHREC
non-rigid
track.
http://www.itl.nist.gov/iad/vug/sharp/contest/2010/NonRigidShapes/.
[OOFB08] O HBUCHI R., O SADA K., F URUYA T., BANNO T.:
Salient local visual features for shape-based 3D model retrieval.
In Proc. IEEE international Conference on Shape Modeling andApplications (SMI’08) (2008), pp. 93–102.
[PC08] P EYRÉ G., C OHEN L. D.: Heuristically driven front
propagation for fast geodesic extraction. IJVCB 1, 1 (2008), 55–
67.
[RpSS] RUGGERI M. R., PATANE G., S PAGNUOLO M., S AUPE
D.: Spectral-driven isometry-invariant matching of 3D shapes.
International Journal of Computer Vision (in press).
[SF07] S HILANE P., F UNKHOUSER T.: Distinctive regions of 3d
surfaces. ACM Transactions on Graphics 26, 2 (2007).
[SFH∗ 09]

S MEETS D., FABRY T., H ERMANS J., VANDER MEULEN D., S UETENS P.: Isometric deformation modelling for

object recognition. In CAIP ’09: Proceedings of the 13th International Conference on Computer Analysis of Images and Patterns(2009), Jiang X., Petkov N., (Eds.), vol. 5702 of LNCS, pp. 757–
765.
[SMKF04] S HILANE P., M IN P., K AZHDAN M., F UNKHOUSER
T.: The princeton shape benchmark. In Proc. Shape Modeling
Applications (SMI’04) (2004), pp. 167–178.
[SZ03] S IVIC J., Z ISSERMAN A.: Video google: A text retrieval
approach to object matching in videos. In Proc. ICCV 2003
(2003), vol. 2, pp. 1470–1477.
[SZM∗ 08] S IDDIQI K., Z HANG J., M AXRINI D., S HOKOUFAN DEH A., B OUIX S., D ICKINSON S.: Retrieving articulated 3dmodels using medial surfaces. Machine Vision and Applications
19, 4 (2008), 261–274.
[WSAB07] W UHRER S., S HU C., A ZOUZ Z. B., B OSE P.: Posture invariant correspondence of incomplete triangular manifolds. International Journal of Shape Modeling 13, 2 (2007),
139–157.
[Wu] W U C.:
SiftGPU: A GPU implementation ofdavid lowe’s scale invariant feature transform (SIFT).
http://cs.unc.edu/ ccwu/siftgpu/.
[ZKCS05] Z HANGJ.,K APLOW
R.,
C HEN
R.,
S IDDIQI K.:
The mcgill shape benchmark.
http://www.cim.mcgill.ca/ shape/benchMark/ (2005).
[ZWG∗ 03] Z HOU D., W ESTON J., G RETTON A., B OUSQUETO., S CHOLKOPF B.: Ranking on data manifolds. In Proc. theConference on Advances in Neural Information Processing Systems (NIPS) (2003).

submitted to Eurographics Workshop on 3D Object Retrieval (2010)