SHREC'08 Entry: Local 2D Visual Features for CAD Model Retrieval
Kunio Osada, Takahiko Furuya, Ryutarou Ohbuchi
University of Yamanashi†

ABSTRACTA local shape feature has an advantage in dealing with deformableor articulated 3D models. We evaluate the performance of ourlocal, 2D visual features and their integration method based of thebag-of-features approach on the SHREC’08 CAD Model Tracktask. The evaluation showed that, it performed very well, winningthe 2nd place in the contest, although it lost to a method that
employs supervised learning of classes in the benchmark dataset.
KEYWORDS: Content-based retrieval, multi-scale feature, ScaleInvariant Feature Transform.
INDEX TERMS: H.3.3 [Information Search and Retrieval]:
Information filtering. I.3.5 [Computational Geometry and Object
Modeling]: Surface based 3D shape models. I.4.8 [SceneAnalysis]: Object recognition.
1INTRODUCTION

To enter the last year’s SHREC 2007 CAD Model Track (CMT),
we used the shape feature for polygon soup models, and appliedan unsupervised dimension reduction to find a subspace adapted
to distribution features for the kind of models found in thedatabase [6]. An interesting observation was that the feature
extracted from convex hull of the models in the database stillachieved quite good retrieval performance, about as good as thesecond place in the contest. However, we also observed that someof the models in a class shares local feature but not their overall
shape, the kind extracted by convex hull.
In this entry to the SHREC 2008 CMT, we employ a methodthat compares shape by multi-scale, local, 2D visual features [4].
Local features are quite promising, especially for an articulated
shape or for partial matching. However, distance computation
using hundreds or thousands of local features per model can becostly. In the method we employed [4], we fuse local visualfeatures into a feature vector for efficient model-to-modelcomparison.
2METHOD

The method we used, whose detail is described in [4], compares
shapes of 3D models visually by using a set of local features
extracted from 2D depth images of the model (Figure 1). The
depth images are generated by viewing the model placed at thecoordinate origin from multiple orientations. Of required threeaxes of rotational invariance, two are achieved by the multipleview rendering of the model.
The local feature set for each depth image is extracted by using
the SIFT, which first selects (what the algorithm thinks) salient
points and then computes a 128D feature that encodes scale and†

4-3-11 Takeda, Kofu-shi, 400-8511, Japan.
osada.researchAT gmail.com, t03kf030AT yamanashi.ac.jp,
ohbuchiAT yamanashi.ac.jp.
LEAVE 0.5 INCH SPACE AT BOTTOM OF LEFT
COLUMN ON FIRST PAGE FOR COPYRIGHT BLOCK

orientation of grayscale changes local to the salient points in theimage. The rotational invariance of the SIFT feature handles theone remaining axis of rotational degrees-of-freedom. The SIFT
algorithm extracts more than a dozen of features per depth image,and a model is rendered from 42 view orientations. The 3D model
thus has a set of thousands of local visual features.
Computing a distance among a pair of 3D models having
thousands of local features each can be expensive. A simpleminded algorithm would take O(n 2 ) time assuming the average
number of local feature per model to be n. With a large database,this cost of distance computation becomes dominant compared tothe cost of feature extraction
To simplify distance computation, we combine these local
visual features into a single feature vector by using so-called bagof-features (BoF) approach [1, 5, 7]. The BoF approach is inspired
originally by the bag-of-words approach in text retrieval, whichcharacterizes a text document by a histogram of words’
occurrences in the document. In our method, a vector-quantized
local feature is treated as (visual) word, whose frequency per 3Dmodel is accumulated into a histogram, which becomes the feature
for the model.
The codebook for vector quantization is learned unsupervised,
off-line, by using thousands of visual features generated from themodels in the database to be queried. We used the well-known kmeans clustering algorithm to learn the codebook. After theclustering using k-means algorithm, the barycenter of each cluster
becomes the representative vector of the cluster. Once thecodebook is learned, given a feature vector, its quantized vector
can be found by searching through the codebook (i.e, the list ofbarycenters) for the vector closest to the feature vector. Given kcluster centers, that is, the vocabulary size of k, vector
quantization takes O(k) time. Vector quantization takes significant
amount of time for a large number of local features, e.g., forpreprocessing an entire database.
3EXPERIMENTS AND RESULTS

We used the SHREC 2008 CAD Model track, which queries
Engineering Shape Benchmark (ESB) database [2], forperformance evaluation. There are 45 query models, and theground truth classes in the database are “highly relevant” only.
We varied a parameter of the method, the vocabulary size k tofind a best performing result file. To compute distance among thehistograms, we compared the Kullback-Leibler Divergence (KLD)
used in [4] and Cosine measure for their retrieval performance.
Table 1 shows the performance of the proposed BoF-SIFT
algorithm using two different distance measures and threedifferent vocabulary sizes. The table also lists the performance
figures for (1) our Semi-Supervised Dimension Reduction (SSDR)
based method [8], and (2) our previous Unsupervised Dimension
Reduction (UDR) based method that finished 1st in the SHREC
2007 CMT [7].
The BoF-SIFT using Cosine measure and vocabulary size
k=1,200 achieved the best Mean First Tier (FT) of 44%,outperforming our previous UDR-based algorithm [5] with its
FT=41%.
In the SHREC’08 CMT, the BoF-SIFT method with its
FT=44% ranked at 2nd place. The method using morphologicalmultiresolution feature set combined with SSDR [7] won the 1st

place with FT=78%, and the method by Napoleon et al finishedthe 3rd.
When we looked into each query, the SSDR-based method
achieved FT=100% for the majority of the queries. However,some of the queries do favor the local features of BoF-SIFT
instead of the SSDR-based method. For example, the BoF-SIFT
works better than the SSDR-based method for the Query 19; theBoF-SIFT gave FT=69%, while the SSDR-based method gave
FT=0%. In this query, a local feature, the teeth of a gear, is more
important than the global shape of cylinder. The SSDR-based
method retrieved cylindrical objects instead of gears. An
appropriate fusion of these two methods would give us a strongerhybrid approach.
4CONCLUSION[8] and a local feature based method like this for better retrieval
performance.
REFERENCES
[1]

[2]

[3]
[4]
[5]

The Bag-of-Features SIFT method, which combines thousands of
local visual features into a feature vector, is quite effective. It
produced Mean First Tier of 44% to rank at 2nd place in theSHREC’08 CAD Model Track, trailing only the method based on
Semi-Supervised Dimension Reduction [8].
In the future, we plan to explore methods to reduce
computational costs for vector quantization and codebooklearning. We also plan to apply some form of learning-basedalgorithm, supervised and unsupervised, to the BoF-SIFT method
for a performance boost. We also would like to investigate afusion of a global feature based shape matching method such as
Render multi-view
range images

Extract 2D local
visual features

View 1

[6]

[7]

[8]

G. Csurka, C.R. Dance, L. Fan, J. Willamowski, C. Bray, Visual
Categorization with Bags of Keypoints, Proc. ECCV ’04 workshop
on Statistical Learning in Computer Vision, pp.59-74, (2004)
S. Jayanti, Y. Kalyanaraman, N. Iyer, K. Ramani, Developing An
Engineering Shape Benchmark for CAD Models, CAD, 38(9),(2006)
David G. Lowe, Distinctive Image Features from Scale-Invariant
Keypoints, Int’l Journal of Computer Vision, 60(2), November 2004.
R. Ohbuchi, K. Osada, T. Furuya, T. Banno, Salient local visualfeatures for shape-based 3D model retrieval, Proc. SMI ‘08, (2008).
J. Sivic, A. Zisserman, Video Google: A text retrieval approach toobject matching in Videos, Proc. ICCV 2003, Vol. 2, pp. 1470-1477,(2003).
R.C. Veltkamp, F.B. ter Harr, SHREC 2007 3D Shape Retrieval
Contest, Dept of Info and Comp. Sci., Utrecht Univ., Tech. Report
UU-CS-2007-015, (2007).
J. Winn, A. Criminisi, T. Minka, Object categorization by learned
universal visual dictionary, Proc. ICCV05, Vol. II, pp.1800-1807,(2005).
A. Yamamoto, M. Tezuka, T. Shimizu, and R. Ohbuchi, SHREC’08
Entry: Semi-Supervised Learning for 3D CAD Model Retrieval,
Proc. SMI 2008 (2008)..
Generate ahistogram

Vector quantize features
into visual words
Bags-ofvisual words

Bag-offeatures

Featurevector
HistogramView i…

…

⎛ 2⎞⎜ ⎟⎜ 4⎟⎜1⎟⎝ ⎠

View 42
Figure 1. Bag-of-Feature SIFT algorithm integrates thousands of local visual features per model, extracted from multi-view depth images, intoa feature vector for efficient feature-to-feature comparison.
Table 1. Retrieval performances of the IM-VSIFT and the Semi-Supervised Dimension Reduction (SSDR)-based method [8].

Supervised

MethodDistancemeasureCosineNo

BoF-SIFTKLDNoYesUDR [6]SSDR [8]AP-HR: Mean Average Precision (highly relevant)
DAR: Mean Dynamic Average Recall
NCG @25: Mean Normalized Cumulated Gain @25Vocabulary
size k1000
1200
1500
1000
1200
1500

AP-HR
0.44890.4764
0.46820.4506
0.43600.43440.43370.7997

FT-HR
[%]
42.26
44.28
43.71
43.83
43.69
43.61
41.23
78.17

DAR
0.53240.5676
0.55550.54410.53670.53000.53570.7943NCG@25
0.47270.50130.4876
0.48150.47240.47190.50230.7887NDCG@250.52370.56030.54180.53090.51900.51860.5341
0.7916

FT-HR: Mean First Tier (Highly Relevant)
NDCG @25: Mean Normlized Discounted Cumulated Gain @25