Ryutarou Ohbuchi and Takahiko Furuya, Scale-Weighted Dense Bag of Visual Features for 3D Model Retrieval from a Partial View
3D Model, accepted, Proc. ICCV 2009 workshop on Search in 3D and Video (S3DV) 2009, Sept. 27, Kyoto, Japan.

Scale-Weighted Dense Bag of Visual Features for
3D Model Retrieval from a Partial View 3D Model
Ryutarou Ohbuchi
University of Yamanashi
4-3-11 Takeda, Kofu-shi, Yamanashi-ken,
400-8511, Japan

Takahiko Furuya
University of Yamanashi
4-3-11 Takeda, Kofu-shi, Yamanashi-ken,
400-8511, Japan

ohbuchiAT yamanashi.ac.jp

snc49925AT gmail.com

Abstract
This paper describes a 3D shape model retrieval methodthat accepts, as a query, a 3D mesh obtained by a range
scan from a viewpoint. The proposed method visuallycompares single depth map of the query with depth maps ofa 3D model rendered from multiple viewpoints.
Comparison of the depth maps employs bag-of local visualfeatures extracted by using a modified version of Lowe’s
Scale-Invariant Feature Transform (SIFT). The method iscapable of retrieving 3D models having diverse shape
representations and is robust against articulation andglobal deformation of 3D shapes thanks to location-free
integration of local visual features. Two modifications to
the SIFT are made to avoid ill effects of range scanning
artifacts, such as jagged edges and cracks, that exist in thequery mesh. The two modifications are; (1) dense andrandom feature placement, and (2) importance sampling of
low-frequency images in the SIFT’s Gaussian image
pyramid. Our experimental evaluation showed that the
proposed method significantly outperforms previous
methods.

edition included, for the first time, a track on 3D model
retrieval by using a partial 3D model generated from aviewpoint as a query. Figure 1 shows examples of thequeries for the track. The track is organized by Afzal Godilof the National Institute of Standard Technology [1]. Two
methods, the Compact Multi-View Descriptor (CMVD) by
Axenopoulos and Daras [1, 4] and our Bag-of-Features
SIFT (BF-SIFT) [1, 8], participated in the sub-track. Bothmethods are appearance-based, so that 3D shapes arecompared based on the 2D renderings, e.g., binary and/or
depth images, of the 3D models. View based methods (e.g.,[3], [4], and [8]) have an advantage of being applicable to adiverse class of 3D shape representations, be it solid,
manifold mesh, point set, or polygon soup. So far as amodel can be rendered, its shape can be compared. In
comparison, other 3D shape comparison methods often
require the models to be defined by a specific 3D shape
representation.
The result of the SHREC 2009 Partial View Retrieval
Track showed that the best performing variations of the
CMVD and the BF-SIFT virtually tied in various
performance scores. Favourable classes are also split in half,each bettering the other on 10 out of 20 queries.
To compare between 3D models, the CMVD method by

1. Introduction
Interest in content based 3D model retrieval has been
increasing recently in the recent years due to popularity of
3D models used in game, movie special effect, mechanicaldesign, medicine, architecture, and many other applications[6, 9]. Most of existing 3D model retrieval methods accepts
a 3D model and returns a set of 3D models ranked by theirsimilarity to the query. In some of the applications,however, the query is not a complete 3D model, but a range
scan of a 3D object from a view (or from a few views).
Examples of partial view retrieval include navigation of arobot using Laser range scanners and retrieval ofarchaeological artefacts. This paper proposes and evaluatesa method for retrieving 3D objects from a partial view 3D
mesh model obtained from a single range scan.
An international 3D model retrieval contest SHape
REtrieval Contest was initiated in 2006, and its 2009(a)Partial-view 3D mesh models used as queries.

(b) Cracks.

(c)Jagged edges.

Figure 1: Examples of the SHREC 2009 Partial Model Retrieval
Track query models generated by Laser range scan (a). Cracks andjagged edges in query models ((b) and (c)).

Ryutarou Ohbuchi and Takahiko Furuya, Scale-Weighted Dense Bag of Visual Features for 3D Model Retrieval from a Partial View
3D Model, accepted, Proc. ICCV 2009 workshop on Search in 3D and Video (S3DV) 2009, Sept. 27, Kyoto, Japan.

Axenopoulos and Daras [1, 4] renders, after normalizing
for size and position, a set of multi-view 2D images of a 3Dmodel from a set of viewpoints located uniformly in thesolid angle. For each view, the CMVD renders both binaryand depth images. From each 2D image, the method
computes three rotation invariant global 2D image
descriptors, 2D Polar Fourier Transform, 2D Zernike
Moments, and 2D Krawtchouk Moments. To compare asingle view 3D model of the query with full 3D models, themethod treat as if the binary and depth images of the querymodel is one of the many views of a full 3D model.
The BF-SIFT method used for the contest is a variant ofour previous view-based method for full 3D model to full
3D model comparison with the same name [8]. The original
BF-SIFT renders, after normalizing for size and position, a
set of depth images of a 3D model from 42 viewpoints
distributed uniformly in solid angle. The BF-SIFT thencomputes, for each depth image, a set of multi-scale, local
2D image descriptors by using Lowe’s Scale Invariant
Feature Transform (SIFT) [7]. The SIFT first finds a few
dozen interest points in its multiscale image pyramid, andthen computes 128D features with scale and orientation
information for each of the interest point. About a thousand
SIFT features from 42 views per 3D model are integrated
into a feature vector for the 3D model by using
bag-of-features approach [2], through vector quantization
into “visual words” of SIFT features followed byaccumulation of the visual words into a histogram. A
histogram per 3D model then becomes a feature vector forthe model. An advantage of the BF-SIFT is its robustness
against articulation and global deformation of 3D models to
be compared, due to the use of local features and theirlocation-free integration into a feature vector per 3D modelby using the bag-of-features approach.
We entered the SHREC 2009 Partial View Retrieval
track [1] with two variations of the original BF-SIFT. The
first is the original BF-SIFT with its distance computation
step modified. We call the method Partial view
Bag-of-Features Interest point SIFT (P-BF-ISIFT) in thispaper. The P-BF-ISIFT has 42 feature vectors per full 3Dmodel, corresponding to 42 depth images. The 42 feature
vectors are compared against a feature vector computedfrom the depth image of the single-view query 3D model.
The comparison of a full 3D model with a partial viewmodel thus requires 42 distance computations.
The second variation is created in an attempt to improve
the retrieval performance of the P-BF-ISIFT above. The
variation combines grid sampling and interest point
sampling of local visual features; high frequency images
are sampled using the original SIFT with its interest point
detector while low frequency images are sampled at regulargrid points. We call this variation Partial view
Bag-of-Feature Interest point and Grid sampling SIFT
(P-BF-IGSIFT ) in this paper. Two reasons for themodification are; (1) to avoid effects of unwanted featurepoints at cracks and jagged edges found in range scanned
3D models, and (2) to increase number of samples in a
depth image of a view. Experiments showed that the hybrid
sampling P-BF-IGSIFT performed better than the interest
point based P-BF-ISIFT.
Figure 2a and 2d show interest points of the P-BF-ISIFT,
which are attracted to high frequency features such as theattachments of legs to the insect’s body, or to the leaves ofthe potted plant. However, the body of the insect or the pot
attracted only small number of interest points. Figure 2band 2e show feature points on grid point of theP-BF-IGSIFT for low frequency images. Body and legs ofthe insect, or the pot and leaves of the potted plant aresampled more evenly in the grid sampling.
In this paper, we propose a method for partial-view tofull 3D model comparison based also on our original
BF-SIFT [8]. The method is multi-view based, and employs
bag-of local visual features, which makes it robust against
articulation and global deformation of 3D shapes. However,unlike the P-BF-ISIFT or P-BF-IGSIFT, the proposed
method uses dense and random placement of a large
number of SIFT features. This increases the number offeatures per view and avoids ill effects of falsely detected(e.g., at the cracks) interest points. Furthermore, the method
emphasizes low-frequency or larger scale features in theimages by placing more samples in low frequency images
in the Gaussian image pyramid of the SIFT. This enables
the method to suppress high-frequency noise introduced byrange scan, and to capture more global shape features. We
call the method Partial view Bag-of-Features Dense SIFT,
or P-BF-DSIFT in this paper.
Our experimental evaluation using the SHREC 2009(a) P-BF-ISIFT,
Np=72(b) P-BF-IGSIFT,
Np=336(c) P-BF-DSIFT,
Np=306(d) P-BF-ISIFT,
Np=88(e) P-BF-IGSIFT,
Np=336(f)

P-BF-DSIFT,
Np=305Figure 2: SIFT sample points of the original P-BF-SIFT (a)(d),P-BF-IGSIFT for low frequency images (b)(e), and our proposed
P-BF-DSIFT-L (c)(f). Np indicates the number of SIFT features
per image.

Ryutarou Ohbuchi and Takahiko Furuya, Scale-Weighted Dense Bag of Visual Features for 3D Model Retrieval from a Partial View
3D Model, accepted, Proc. ICCV 2009 workshop on Search in 3D and Video (S3DV) 2009, Sept. 27, Kyoto, Japan.

Partial Models Retrieval benchmark showed that our
method significantly outperforms both the CMVD and ourprevious method P-BF-IGSIFT. Using the SHREC 2009
Partial View Retrieval benchmark, our proposed method
scored 37% in Mean First Tier. In comparison, both CMVD
and P-BF-IGSIFT scored 22% in Mean First Tier in thesame benchmark.

2. Method
Figure 3 shows the processing pipeline of the proposed
P-BF-DSIFT method. The process starts with depth-image
rendering; from 1 view for the partial view query 3D modeland from Ni views for the full 3D model. The method thenrandomly and densely places sample points, and extract
SIFT feature at each sample point. This gives a bag of SIFT
features per view, that is, per depth image. For each view,the SIFT features are vector quantized using pre-learned
codebook, and accumulated into a histogram for the view.
Finally, a histogram for the partial view query and a set ofNi multiple histograms for the 3D model is compared,
producing Ni distances. The minimum of the Ni distances
becomes the distance between the query and the 3D model.
We will explain the detail of each step in the following.

3D modelquery
Renderdepth images
view 1Ni views
view 1…
…

Extract
SIFT
featuresLocal
features

Vectorquantize（Nv clusters）

Visualwords

Generate
histogram(Vocabulary
size Nv)

Histogram

Computeminimum of
Ni distances

viewNi…
…

…

(3, 7, 1)

Feature vector(2, 6, 3)(5, 2, 4)Overall distance

Figure 3: Overview of the proposed Partial view Bag-of-Feature
Dense SIFT (P-BF-DSIFT) method.

2.1. Multi-View Depth Image Rendering
For a full 3D model, after normalizing for position andscale, the method renders the model from Ni viewpoints
uniformly spaced in solid angle into Ni depth images permodel. The method achieves approximate rotation
invariance against two out of three rotational degrees of
freedom via this multi-view rendering. Invariance toremaining one rotational degree of freedom is achieved via
the rotation invariance of the SIFT. We will experimentally
evaluate the effect of Ni on retrieval performance. For theexperiment described in this paper, image size of 256
256 pixels is used to render a full 3D model.
For a partial view 3D model, we render the model into an
image of size 1024 1024 pixels, which is then down
sampled with low-pass filtering to 256 256 pixels inorder to reduce aliasing artifacts. We use GPU for depth
image rendering.

2.2. Scale-Weighted SIFT Feature Extraction
In this step, a set of SIFT features are extracted fromeach depth image rendered. The SIFT [7] is a scale androtation invariant local visual feature having dimension of128. By employing a multiresolution image pyramid, theSIFT feature capture multi-scale and multi-orientation
image features. The original BF-SIFT [8] employed
Lowe’s SIFT without modification, which starts withinterest point detector, followed by the feature extraction atthese interest points. The SIFT places interest points at the
points having high gray level gradient across the scale. As
mentioned before, this causes problem if the rendered depth
image of the query model contains cracks and/or jagged
edges that are the result of Laser range scan.
On one hand, a large portion of the interest points areplaced at these cracks and jagged edges. On the other hand,
important yet smooth or feature-less parts of the model tend
to be undersampled as they generate much smaller numberof interest points. To counter these problems, our proposed
method introduced the following two changes:(1) Dense and Random Sampling: The proposed method
discards the interest point detector, and places a large
number of sample points at random locations for all theimages in the multi-scale image pyramid.
(2) Low-Frequency Emphasis: Noise in range scanned
query models, such as jagged perimeter edges andcracks are mostly of high-frequency, that is, smallerscale, features. To disregard the noise, our sampling
method emphasize low frequency component in theimage by importance sampling, that is, by allocating
more samples in the low-frequency images.
Low-frequency emphasis also enables the method to
capture more of global shape features.
Figure 4 shows examples of depth images in themultiresolution image pyramid. In this example, legs of theRyutarou Ohbuchi and Takahiko Furuya, Scale-Weighted Dense Bag of Visual Features for 3D Model Retrieval from a Partial View
3D Model, accepted, Proc. ICCV 2009 workshop on Search in 3D and Video (S3DV) 2009, Sept. 27, Kyoto, Japan.

insect model are visibly detached from the body in theimage having size 256 256. However, the discontinuity
become less noticeable as the image is low-pass filtered anddown sampled. For example, at the 64 64 image, while
the legs are still recognizable, they appear to be connectedto the body. At each scale, sample points for the dense
sampling are placed randomly at pixels having non-zeropixel values to concentrate samples on or near theforeground object.

256

256 128

128

64

64

32

32

16

16

Figure 4: Example of images in the multiresolution image
pyramid. (“” indicates the image size in pixels.)

Allocation of samples across the scale is controlled by ascale weighting parameter W. If we have M randomly
placed samples at a scale having image size
pixels,the next lower (i.e., larger scale) frequency image of image
size /2/2 has / randomly located samples. By
altering W, either high frequency or low frequency images
is emphasized. At
4.0 the number of samples is evenacross the scale. High frequency is emphasized if
4.0,
and low frequency is sampled more if
4.0.
We compare the P-BF-DSIFT with our previous
methods P-BF-ISIFT and P-BF-IGSIFT. Additionally, we
implemented a variation called Partial view Bag-of Grid
SIFT (P-BF-GSIFT) that uses grid sampling only. In
comparison, the P-BF-IGSIFT switches from grid samplingat low-frequency to interest-point sampling at highfrequency. In our P-BF-GSIFT, location of the grid points
are the same across the scale; in other words, the same
spatial location is sampled at various scale. In comparison,
the random placement of the P-BF-DSIFT is so that the
sample positions are different from one scale to the other.
Figure 2c and 2f show examples of sample points for the
proposed P-BF-DSIFT.
To speed up extraction of SIFT features, we use a GPU
implementation of SIFT named SiftGPU by Wu [10] for allof the P-BF-DSIFT, P-BF-GSIFT, and P-BF-DSIFT. Since
the SiftGPU is a SIFT with interest point detector, we
modified it for the P-BF-DSIFT and P-BF-GSIFT so that
SIFT sample locations can be specified.. For theP-BF-ISIFT, the original SiftGPU is used. With theincrease in the number of sample point for theP-BF-IGSIFT and P-BF-DSIFT sampling, acceleration byusing GPU brings significant speedup.

2.3. Vector quantization and histogram generation
Following the bag-of-features approach, the proposed

method performs Vector Quantization (VQ) of the SIFT
features generated from a range image into code vectors in
the pre-computed codebook. After the VQ, the frequenciesof code vectors, or “visual words”, are counted to create ahistogram. The histogram then becomes the feature vector
for the range image.
The codebook for the VQ is learned by clustering local
features generated from 3D models in the database. Vector
quantization then is a process of finding a code vector
closest to a feature to be quantized amongcode vectors.
The clustering for codebook learning often uses k-meansclustering. However, k-means takes a long time especially
if the number of features and the dimension of the feature
increase. Furthermore, finding the closest code vector inhigh dimensional feature space for thousands of features
per 3D model is quite time consuming. To speedup bothcodebook learning and the nearest neighbor search for VQ,
we use the randomized decision tree algorithm by Guerts[5]. A tree node of the decision tree corresponds to a
subdivision of feature space by a hyperplane perpendicular
to a coordinate axis. The quality of cluster created by the
randomized tree is less than that of the k-means. However,randomized tree is much faster than the k-means in learning
codebook and performing vector quantization.
After the VQ, the visual words generated areaccumulated into a histogram per range image (i.e., view)
whose dimension is equal to vocabulary size, or number ofclusters, .

2.4. Distance computation
A feature vector of the partial view query 3D model isfeature vectors of a 3D model in thecompared with
distances computed
database. The minimum of the
becomes the distance between the query and the 3D model.
For the distance measure, our method uses a symmetricversion of the Kullback-Leibler Divergence, or KLD. The
dimensional feature
distance,
between theanddue to KLD is computed as
vectors
follows;,ln

Note that the distance computation above is performedmeans a longer time
per view, so that a larger number ofto compare a full 3D model with a query.
To speed up the distance computation, we replace thefunction call to ln() with a table lookup. As the histogram isvery sparse and a histogram bin has a small integer value,
the table is quite compact, having only 100 entries. The
table is small enough to easily fit in a cache memory of amodern CPU.

Ryutarou Ohbuchi and Takahiko Furuya, Scale-Weighted Dense Bag of Visual Features for 3D Model Retrieval from a Partial View
3D Model, accepted, Proc. ICCV 2009 workshop on Search in 3D and Video (S3DV) 2009, Sept. 27, Kyoto, Japan.

We evaluated the method through the following fiveexperiments;(1) Sampling pattern and retrieval performance:
Compares the P-BF-DSIFT with P-BF-ISIFT and
P-BF-GSIFT for their retrieval performance.
(2) Scale-weighting and retrieval performance:
Quantifies effect of the scale-weighted sampling on
retrieval performance for the P-BF-DSIFT.
(3) Number of views and retrieval performance:
Quantifies effect of number of rendered views per
3D model on retrieval performance for theP-BF-DSIFT.
(4) Vocabulary size and retrieval performance:on
Quantifies effect of visual word vocabulary size
retrieval performance.
(5) Performance comparison with other methods:
Compares the retrieval performance of theP-BF-DSIFT with other methods.
(6) Computational cost: Quantifies computational costs
for the four processing steps of the P-BF-DSIFT.
For evaluation, we used the database and ground truth
categories of the SHREC 2009 Partial 3D Models Track [1].
The database consists of 720 models divided into 40 classes,
such as plant, furniture, and airplane. The query set is 20
partial view 3D models generated by range scanning real
objects using a viewpoint per model. As the numericalperformance index, we used Mean First Tier (MFT). First
Tier is the ratio of 3D models retrieved from the correctclass in the top retrievals, where is the size of thecorrect class. The number is averaged over all the queries toyield Mean First Tier.
Throughout the experiments, we used the following
parameters. We fixed the number of viewpoint for the
42 , except for the third
multi-view rendering toexperiment in which is varied. In rendering, 3D models
are rendered into 256 256 pixels. Partial view 3D model
is first rendered into 1024 1024 pixels, followed bysmoothing and down sampling into 256 256 pixels
before SIFT feature extraction. The codebook for vector
quantization is learned from a set of 500k SIFT features.
The set is a randomly selected subset of SIFT features
extracted from 3D models in the retrieval target database.

3.1. Sampling Pattern and Retrieval Performance
Figure 5 shows, for P-BF-ISIFT, P-BF-GSIFT, and
P-BF-DSIFT, the relationship between number of samples
and retrieval performance measured by MFT.
The plot for the P-BF-ISIFT is a point since its
isdetermined automatically by the interest point detector.
from
For the P-BF-GSIFT and P-BF-DSIFT, we varied
about 100 to 3,600. In this set of experiments, for all thesampling methods, scale weighting factor is set at W=4.0
for even sampling across the scale.
The best performing was the proposed P-BF-DSIFT,
followed by the P-BF-GSIFT. The performance of
P-BF-DSIFT increased with , but is saturated at around
1,200 with MFT = 32.5%. The P-BF-GSIFT gained
performance as
is increased, reaching MFT = 27.2% at
3,600. However, its performance never matched thatof P-BF-DSIFT in the range of
we have experimented
with. We suspect that the same regular grid points acrossthe multi-scale image pyramid of the P-BF-GSIFT
produced features having limited diversity. In comparison,
P-BF-DSIFT places samples at different positions acrossthe scale, presumably improving feature’s diversity.
Original SIFT with its interest point detector performed
the worst with its MFT 9.2%. Two primary reasons for
its low performance are the small sample counts per image(66) and the misplacement of samples around range
scanning artifacts such as cracks and jagged edges.
35
Mean First Tier [%]3. Experiments and Results

30
25
20
15

P-BF-ISIFT
P-BF-GSIFT
P-BF-DSIFT

10
5
0
0

1000

2000

3000

4000

Number of features per depth image Np
Figure 5: Number of samples
per depth image and retrieval
performance plotted for three sampling methods.

3.2. Scale-Weighting and Retrieval Performance
In this experiment, we evaluated the relationshipbetween the scale weighting parameter W and retrieval
performance. We use the P-BF-DSIFT, and its number of
1,200. We then tried various value
samples is set atof W in the range 1.0~12.0 to modify the allocation ofsamples over the scale space.
Figure 6 shows the result of the experiment. There is a
performance peak at W=1.5 with MFT = 37.2% where
low-frequency image has more samples thanhigh-frequency images. The performance at W=1.5 is about
5% better than when even sampling density is employed
across the scale.
Interestingly, there is little change in retrieval
performance between even sampling (W=4.0) andhigh-frequency emphasized sampling (W>4.0) across thescales.

Ryutarou Ohbuchi and Takahiko Furuya, Scale-Weighted Dense Bag of Visual Features for 3D Model Retrieval from a Partial View
3D Model, accepted, Proc. ICCV 2009 workshop on Search in 3D and Video (S3DV) 2009, Sept. 27, Kyoto, Japan.

(4) P-BF-DSIFT (LFE): P-BF-DSIFT with low frequency
1,200.
emphasis (W=1.5) and

35
30
25
P-BF-DSIFT
20
1.0

1.2

1.5

Low-emphasis

2.0

4.0

6.0

12.0

Even High-emphasis

Figure 6: Scale weighting parameter W and retrieval performance.
Importance sampling low-frequency images (W=1.5) improved
retrieval performance.

3.3. Number of Views and Retrieval Performance
It is expected that an increased number of views to
render depth images will provide better approximation torotational invariance, at the expense of higher cost of
distance computation. Figure 7 shows the relationshipto the retrieval
between the number of views
performance. As the graph shows, performance jumps
when is increased from 20 to 42, while the performancechange from 42 to 80 is negligible. In the following
42.
experiments, we fix the number of views
33
First Tier [%]

32
31
30
29
28
20

42

40
35
30
25
20
15
10
5
0
0

Scale weighting parameter W

6FirstTier [%]First Tier [%]

40

80

10000
20000
30000
Number of vocabulary Nv
P-BF-SSIFT
P-BF-GSIFT
P-BF-DSIFT (Even)
P-BF-DSIFT (LFE)
Figure 8: Vocabulary size and retrieval performance.

Note that each plot is not smooth due to the randomized
nature of the clustering algorithm [5].
for it has a small
P-BF-SIFT peaks out at a small
66. P-BF-GSIFT
average number of sample points
has its peak at about
10,000, and the performanceincreases past that point. P-BF-DSIFT also
drops as the
10,000, but the peak is
appears to have a peak pastless evident than in the case of P-BF-GSIFT. Compared tothe interest point sampling of the original P-BF-ISIFT, thedense sampling of the P-BF-DSIFT, and to some extent thegrid sampling of the P-BF-GSIFT appear to improve thediversify SIFT features extracted, thereby increasing the
vocabulary size having maximum retrieval performance. ,10,000, histograms for both P-BF-DSIFTAt aroundand P-BF-GSIFT are very sparse, dominated by bins
having 0 values. This is because the number of samples
1,200 is smaller than the number of bins
10,000If we compare among peak retrieval performances of themethods, the P-BF-DSIFT with low emphasis has thehighest retrieval performance, followed by theP-BF-DSIFT with even weighting.

Ni ( Number of Views )Figure 7: Number of views N and retrieval performance for theP-BF-DSIFT.

3.4. Vocabulary Size and Retrieval Performance
Figure 8 shows the effect of vocabulary sizeon theretrieval performance. We compared four different method
and parameter combinations;
66.
(1) P-BF-ISIFT: P-BF-ISIFT with average(2) P-BF-GSIFT: P-BF-GSIFT with
1,200.
(3) P-BF-DSIFT (Even): P-BF-DSIFT with even sampling
1,200.
(W=4.0) and3.5. Comparison with Other Methods
In this set of experiments, performances of the following
six variations of methods are compared;(1) CMVD: The method used by Axenopoulos and Daras[1, 4] for SHREC 2009. We used the best performing
one that uses depth map image for feature extraction.
(2) P-BF-IGSIFT: The method used by Furuya andOhbuchi [1] for the SHREC 2009 that combines grid
points and SIFT interest points.
(3) P-BF-SSIFT: Our implementation of P-BF-SIFT,
which uses interest-point only, i.e., original SIFT.

Ryutarou Ohbuchi and Takahiko Furuya, Scale-Weighted Dense Bag of Visual Features for 3D Model Retrieval from a Partial View
3D Model, accepted, Proc. ICCV 2009 workshop on Search in 3D and Video (S3DV) 2009, Sept. 27, Kyoto, Japan.

(4) P-BF-GSIFT: This method uses grid sampling only.
(5) P-BF-DSIFT (Even): This method uses dense
sampling and even weighting in scale space (W=4.0).
(6) P-BF-DSIFT (LFE): This method uses dense
sampling and low-frequency emphasis (W=1.5).
Figure 9 shows the recall-precision plots, and Table 1
shows the Mean First Tier (MFT) figures for the six
methods. The exact numbers plotted in Figure 9 andtabulated in Table 1 for the CMVD and the P-BF-IGSIFT
were obtained from the SHREC 2009 Partial View Model
Retrieval web page. The availability of detailed
performance evaluation results at the web site enabled us
these direct performance comparisons.
Clearly, P-BF-DSIFT(LFE) with its MFT=37.2%
performed the best. If we look at Figure 9,
P-BF-DSIFT(LFE) has significantly better precision at
low-recall region compared to the runner-up
P-BF-DSIFT(Even).
Three methods, the P-BF-IGSIFT (MFT=22.5%), theP-BF-GSIFT(MFT=23.6%),
and
the
CMVD
(MFT=21.7%) are about equal in terms of MFT. Our
proposedmethodP-BF-DSIFT(LFE)with
its
low-frequency emphasis performed about 15% better, at
MFT=37.2%, than these three methods.
Figure 10 shows retrieval examples for two queries fromthe class “potted plant” and “nonflying insects”. In theseexamples, the proposed method with low-frequency
emphasis P-BF-DSIFT (LFE) performed better than theother two methods shown, the CMVD and theP-BF-IGSIFT from the SHREC 2009.

Methods
CMVD (SH09)
P-BF-IGSIFT (SH09)
P-BF-ISIFT
P-BF-GSIFT
P-BF-DSIFT (Even)
P-BF-DSIFT (LFE)

Mean First Tier [%]
21.7
22.5
9.2
23.6
32.5
37.2

3.6. Computational cost
In this experiment, we look into the computational cost
breakdown for the proposed P-BF-DSIFT method.
Computational cost of the method can be split into thecodebook learning phase and query phase.
To learn a VQ codebook from 500k SIFT features, ourimplementation of the randomized decision tree algorithm
took 63.2s. This is tolerable considering it is a one-timecost spent during pre-processing of the database.
Our method took 1.47s to process a query for the SHREC
2009 Partial View Retrieval benchmark. Table 2 list thecost breakdown for various steps of the method. To produce
the table,
1,200 and
1.5 are used.
Talbe 2 shows that the cost of computing distance tosearch through the database containing 720 models
dominated the overall computation time. This is because
the number of comparison par 3D model is not 1 but the
number of views . The cost of distance computation
would increase further as the number of object in the
database increases.
Table 2: Computational cost in seconds at various steps during thequery processing phase of the proposed method.

1.0
0.9

Render
depth
maps
0.074

0.8
0.7
Precision

Table 1: Comparison of Mean First Tier among various methods.

Extract
SIFT
features
0.150

Quantize
SIFT
features0.037

Computedistance
1.209

Total
1.470

0.6

4. Conclusion

0.5
0.4
0.3
0.2
0.1
0.0
0.0

0.2

CMVD (SH09)
P-BF-SSIFT
P-BF-DSIFT (Even)

0.4
0.6
Recall0.8

1.0

P-BF-IGSIFT (SH09)
P-BF-GSIFT
P-BF-DSIFT (LFE)

Figure 9: Comparison of retrieval performance among various
methods using recall-precision plots.

In this paper, we proposed and experimentally evaluateda view-based algorithm for partial-view 3D model to full
3D model comparison named Partial view Bag-of-Features
Dense SIFT (P-BF-DSIFT). The method compares a viewof range image from the query model with multi-view
range images of a full 3D model. To deal with artifacts due
to range scan, such as cracks and jagged perimeter edges,
the method employed dense sampling and low-frequency
weighted importance sampling of local visual features.
Experimental evaluation showed that the proposed method
significantly outperformed our previous methods on which
the proposed method is based. The proposed method
outperformed the other methods we have compared againstby 15% in Mean First Tier.
Future work would include further exploration ofRyutarou Ohbuchi and Takahiko Furuya, Scale-Weighted Dense Bag of Visual Features for 3D Model Retrieval from a Partial View
3D Model, accepted, Proc. ICCV 2009 workshop on Search in 3D and Video (S3DV) 2009, Sept. 27, Kyoto, Japan.

[4] Petros Daras, Apostolos Axenopoulos, A Compact
Multi-view Descriptor for 3D Object Retrieval, Proc.
Seventh International Workshop on Content BasedMultimedia Indexing, 115-119, 2009.
[5] P. Guerts, D. Ernst, L. Wehenkel, Extremely randomized
trees, Machine Learning, 36(1):3-42, 2006.
[6] M. Iyer, S. Jayanti, K. Lou, Y. Kalyanaraman, K. Ramani,
Three Dimensional Shape Searching: State-of-the-art
Review and Future Trends, Computer Aided Design,
5(15):509-530, 2005.
[7] D. G. Lowe, Distinctive Image Features from Scale-Invariant
Keypoints, Int’l Journal of Computer Vision, 60(2):91-110,
2004.
[8] R. Ohbuchi, K. Osada, T. Furuya, T. Banno, Salient local
visual features for shape-based 3D model retrieval, Proc.
IEEE Shape Modeling International 2008 (SMI 2008),
93-102, 2008.
[9] J. Tangelder, R. C. Veltkamp, A Survey of Content Based 3D
Shape Retrieval Methods, Proc. SMI ’04, 145-156, 2004.
[10] C. Wu, SiftGPU: A GPU Implementation of David Lowe's
Scale
InvariantFeatureTransform(SIFT),
http://cs.unc.edu/~ccwu/siftgpu/

scale-space weighting and its effect on various shape
retrieval benchmarks, e.g., those with and without
articulation. For example, low frequency emphasis might
impact the performance for articulated models. We also
would like to improve computational efficiency of themethod, especially by improving the distance computation
step.

References[1] A. Axenopoulos, P. Daras, H. Dutagaci, T. Furuya, A. Godil,
R. Ohbuchi, SHREC 2009 - Shape Retrieval Contest ofPartial 3D Models, Eurographics Workshop on 3D object
retrieval, 2009.
[2] 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, 59-74, 2004
[3] D-Y. Chen, X.-P. Tian, Y-T. Shen, M. Ouh-young, On
Visual Similarity Based 3D Model Retrieval, Computer
Graphics Forum, 22(3):23-232, 2003.

✕

✕

✕

✕

(a)

CMVD (SH09)

✓

✕

(b)

✕

✕

✕

✕

potted plant

✓

✕

✓

✕

✓

✕

✓

✕

nonflying insect

✓

✕
✕

✕
✓

✕
✕

✕

✕

✕

✕

✕

✕

✓

✓

✓

✓

✕

✕

✕

✕

✕

✕

✕

✕

✓

✕

✓

✕

P-BF-IGSIFT (SH09)

✓

✕

(c)

P-BF-DSIFT (LFE)

✓

✓

(a)

CMVD (SH09)

✕

✓

(b)

✕

✕

✕

P-BF-IGSIFT (SH09)

✕

✓

(c)

P-BF-DSIFT (LFE)✕✓

Figure 10. Retrieval examples for the two classes “potted plant” and “nonflying insect”. The proposed method P-BF-DSIFT (LFE)
performed better than the others in these examples.