Accelerating Bag-of-Features SIFT Algorithm
for 3D Model Retrieval
Ryutarou Ohbuchi, Takahiko Furuya
4-3-11 Takeda, Kofu-shi, Yamanashi-ken, 400-8511, Japanohbuchi@yamanashi.ac.jp, snc49925@gmail.com

We have previously proposed a shape-based 3D model retrieval algorithm thatcompares 3D shape based on local visual features. The method first computes a
set of multi-scale local visual features from a set of depth images rendered frommultiple view orientations about the 3D model. Thousands of visual features
per model are integrated into a feature vector for the model by using so-called
bag-of-features approach. The algorithm performed very well, especially formodels having articulation and/or global deformation. However, the method
was computationally expensive; retrieving a model from a 1,000 model
database took more than 10s. This because the costs of rendering depth images,
extracting local visual features, quantizing these features, and computing
distance among the pairs of integrated features can be quite expensive. In thispaper, we significantly accelerated the algorithm by using a Graphics
Processing Unit (GPU).
Keywords: 3D geometric modeling, content-based information retrieval, GPGPU algorithms.

1.

Introduction

We have previously proposed a shape-based 3D model retrieval algorithm thathandles both articulated and rigid models [7]. The algorithm, called Bag-of-Features
SIFT, is appearance based, so it accepts a diverse set of 3D shape representations sofar as it can be rendered as range images. To achieve invariance to articulation and/orglobal deformation, the algorithm employs a set of multi-scale, local, visual features
to describe a 3D model. We used a saliency-based multi-scale image feature called
Scale Invariant Feature Transform (SIFT) by David Lowe [5] to extract the visualfeatures. To reduce the cost of model-to-model similarity comparison, the set ofthousands of visual features for the model is combined into single feature vector byusing so-called bag-of-features approach (e.g., [2, 3, 9, 11]).
Our empirical evaluation showed that the algorithm performs very well, especiallyfor models having articulation and/or global deformation. For rigid models, such as
those found in the Princeton Shape Benchmark [6], the method performed as well assome of the best known 3D model retrieval methods, such as the Light Field
Descriptor (LFD) [2] and Spherical Harmonics Descriptor (SHD) [4]. For articulated
models, the BF-SIFT significantly outperformed the LFD and SHD.

2Ryutarou Ohbuchi, Takahiko Furuya

However, the BF-SIFT algorithm has a high computational cost in computing thefeature vector. Rendering depth images, extracting thousands of local visual features
per model, and quantizing these features, can be quite expensive.
In this paper, we propose a Graphics Processing Unit (GPU) based approach toaccelerate BF-SIFT algorithm. The proposed algorithm employs GPU-based
rendering and GPU-based SIFT feature extraction. Along with the use of table lookup
in the distance computation stage, the method achieved a query processing time of afew seconds for a hypothetical database having 100,000 models.

2.

The BF-SIFT Retrieval Algorithm

We will briefly review the original Bag-of-Features SIFT (BF-SIFT) algorithm [7],followed by the method we employed to accelerate the algorithms.
2.1 Original BF-SIFT algorithm
The BF-SIFT algorithm compares 3D models by following the steps below;
1.

2.
3.
4.

5.
6.

Pose normalization (position and scale): The BF-SIFT performs pose
normalization only for position and scale so that the model is rendered with anappropriate size in each of the multiple-view images. Pose normalization is not
performed for rotation.
Multi-view rendering: Render range images of the model from Ni viewpoints
placed uniformly on the view sphere surrounding the model.
SIFT feature extraction: From the range images, extract local, multi-scale,multi-orientation, visual features by using the SIFT [5] algorithm.
Vector quantization: Vector quantize a local feature into a visual word in a
vocabulary of size N v by using a visual codebook. Prior to the retrieval, thevisual codebook is learned, unsupervised, from thousands of features extracted
from a set of models, e.g., the models in the database to be retrieved.
Histogram generation: Quantized local features or “visual words” areaccumulated into a histogram having N v bins. The histogram becomes thefeature vector of the corresponding 3D model.
Distance computation: Dissimilarity among a pair of feature vectors (thehistograms) is computed by using Kullback-Leibler Divergence (KLD);
nD(x, y ) =yi∑ ( y − x ) ln xii =1i(1)iwhere x = ( xi ) and y = ( yi ) are the feature vectors and n is the dimension of thevectors. The KLD is sometimes referred to as information divergence, or relative
entropy, and is not a distance metric for it is not symmetric.

Accelerating Bag-of-Features SIFT Algorithm
for 3D Model Retrieval
3Renderimages
View 1

ExtractVector-quantize
GeneratefeatureshistogramfeaturesBags-ofBag-ofvisualfeatureswords
Histogram

View iView Nik clusters

Number ofviews Ni

Featurevector⎛5⎞⎜ ⎟⎜7⎟⎜ 4⎟⎝ ⎠Vocabulary
size kFig. 1. Range-images of the model are rendered from multiple view angles. Local, multi-scalevisual features are extracted from each one of the images using SIFT [4] algorithm.
Thousands of SIFT feature per model are vector quantized by using a pre-learned visualcodebook into visual words. Frequencies of visual words are accumulated into a histogram,which becomes an easy to compare and compact feature vector for the model.

2.2. GPU-accelerated BF-SIFT algorithm
The proposed algorithm employs parallelism of a Graphics Processing Unit (GPU) toaccelerate two steps, the multi-view rendering step and the SIFT feature extraction
step, of the six steps of the algorithm described above,. We keep the vector
quantization (VQ) step unchanged. The last step, distance computation step, runs on aCPU but it is accelerated by getting rid of costly calls to logarithmic function bymeans of table lookups.
1.
2.
3.

Pose normalization (position and scale): Pose normalization is performed onthe CPU.
Multi-view rendering: Render range images of the model using the GPU,
instead of the CPU.
SIFT feature extraction: As evident in Figure 2, the retrieval algorithm spends
the largest amount of time in computing thousands of SIFT features from 42
images of a 3D model. To accelerate the computation, we use the SiftGPU, aGPU implementation of the SIFT algorithm by Wu [12]. The SiftGPU does all
the work of the SIFT++, that are, construction of a multiresolution image
pyramid, detection of interest points, and extraction of features at the interestpoints, on a GPU.
While the SiftGPU borrows a lot from SIFT++ by Vedaldi [10], they are not thesame. For example, the SIFT++ uses 64bit double precision floating point, whilethe siftGPU uses 32bit single precision floating point number, for thecomputation. Thus we compared the retrieval performances of the two SIFT

4Ryutarou Ohbuchi, Takahiko Furuya

6.

feature extraction methods. So we experimentally compare the retrieval
performance as well as computational cost of the retrieval algorithm using theimplementations of the SIFT algorithm.
Vector quantization: The Vector Quantization (VQ) step is a nearest point
query in a very high dimensional (e.g., 1,000) space. It is implemented as a linear
search into a set of values whose size Nv is the size of the vocabulary, and runs onthe CPU.
Histogram generation: Quantized local features are accumulated into ahistogram having bins, which becomes the feature vector of the corresponding
3D model. This step runs on the CPU.
Distance computation: Computation of the KLD can be expensive for a highdimensional feature as the computation involves a logarithmic function ln( x )per element of the feature vector. As the computation is repeated as many times
as the number of models in the database, reducing the cost of the log function isquite important for a large database.
Fortunately, a feature vector produced by the BF-SIFT is a very sparsely
populated histogram, in which most of the bins have population zero, and theremaining no-zero elements are small (e.g., <512) positive integers. Thus, theln( x ) function call can be replaced by a lookup into a small table with no change
in performance. The KLD computation using table lookup is performed in theCPU in our current GPU-accelerated implementation.

3.

Experiments and Results

4.

5.

We experimentally compared the retrieval performance of our GPU-accelerated
algorithm with that of our previous CPU-based implementation by using two
benchmark databases: the McGill Shape Benchmark (MSB) [13] for articulated shapes
and Princeton Shape Benchmark (PSB) [8] for a set of diverse and rigid shapes. We
used the same database for learning a visual codebook and for performance
evaluation. That is, the codebook generated by using the MSB (PSB) is used to query
the MSB (PSB). For each database, the visual codebook is generated by using a set of
Nt = 50, 000 SIFT features, which is chosen pseudo-randomly from all the features
extracted from all the views rendered from all the models in the database.
For both SIFT++ (on CPU) and GPU-SIFT, we used parameters of; 42 equally
spaced (in solid angle) viewpoints per model, image size of 256 × 256 pixels perview, scale space having octaves=6, and DOG levels=3. Other parameters for theSIFT++ and the GPU-SIFT are set to their defaults.
We wrote and run the range-image rendering part and SiftGPU feature extraction
part using C++, OpenGL 2.1.2., and Cg 2.0. The vector quantizer and the KLD
distance computation parts are implemented by using C++ and run on the CPU. We
run the experiment under the Fedora Core Linux on a PC having an Intel Xeon 5440
quad-core CPU (Clock 2.83GHz). The code was single threaded. As for the GPU, weused a mid-range GPU, the Nvidia GeForce 9600GT with 512 MByte of memory,whose core clock is 650 MHz and memory clock is 1.8 GHz.

Accelerating Bag-of-Features SIFT Algorithm
for 3D Model Retrieval
5

3.1 SIFT implementations and retrieval performance
We first compare the retrieval performances of the two SIFT feature extractors, thesiftGPU [12] that runs on a GPU and the SIFT++ [10] that runs on a CPU. The
comparison is done to see the impact of implementation differences, for example, thedifference in the precisions of their floating number representations.
As the performance measure, we used R-precision [Baeza-Yates99], which is aratio, in percentile, of the models retrieved from the desired class Ck (i.e., the sameclass as the query) in the top R retrievals, in which R is the size of the class Ck .
Table 1 compares among the two SIFT implementation the average numbers ofinterest point (i.e., the number of features) per model. For both the PSB and MSB, thenumber of interest points is essentially the same. The models in the PSB produced
more interest points than the MSB, since the PSB models has more detailed shapefeatures than those in the MSB.
Each curve in Figure 2 shows the retrieval performance measured in R-precision asa function of vocabulary size Nv. For both of the PSB (Figure 2(a)) and the MSB(Figure 2(b)), retrieval performances are virtually the same for the two
implementations; the differences are less than a percentage point.
Table 1. Number of interest points, that are, features, per model for the two SIFT
implementations.
PSB

MSB

SiftGPU

1,989

1,529

SIFT++

1,967

1,570

80
R-Precision [%]R-Precision [%]5045
siftGPU
SIFT++
4075

70
siftGPU
SIFT++
6501000

2000

Vocabulary size Nv(a) Result using the PSB.

300001000

2000

3000

Vocabulary size Nv(b) Result using the MSB.

Figure 2. Vocabulary size versus retrieval performances for both CPU-based and GPU-based
implementation of SIFT feature extraction. (Note that the vertical scales are different among
the two graphs.)

6

Ryutarou Ohbuchi, Takahiko Furuya

3.2 Computational costs
Figure 3 shows the comparison of computational costs for the three variations of theBF-SIFT algorithm. In the figure, the notation X/X/X/X means that whether the CPU(“C”) or the GPU (“G”) is used at each of the four stages, that are, (1) depth image
rendering, (2) SIFT feature extraction, (3) vector quantization, and (4) distancecomputation. For the distance computation step, “Cf” denotes the implementation
using ln() function, while “Ct” denotes the implementation using table lookup. For
example, G/C/C/Cf indicates that the rendering is done on the GPU, while the otherstages, that are, the SIFT feature extraction, the vector quantization, and the distancecomputation using calls to ln() function, are performed on the CPU.
Note that, in this figure, the size of databases is artificially inflated to 100,000 incomputing the cost of distance computation. The database size mostly impacts thecost of distance computation. The cost of rendering, feature extraction, and vector
quantization are fixed, as they are averages computated from all the models of thedatabase (PSB or MSB). It should be noted that, in reality, the 100,000 model version(if existed) of the PSB (or MSB) will probably have slightly different values ofrendering, feature extracton, or vector quantization. But the impact on these values
will be small.
For the all-CPU case using the costly ln() function call, (the case C/C/C/Cf), thedistance computation step is dominant, followed closely by the SIFT computation
step, and then by the rendering step. Calling ln() function 1,000 times for the 1,000
dimensional feature vector turns out to be qute expensive.
After “modernizing” the implementation so it uses GPU-accelerated rendering, andemploying a table lookup to approximate ln() function in the distance computation
step running on a CPU (that is, the case G/C/C/Ct), the computational cost of theSIFT feature extraction step becomes dominant. (It is somewhat embarrassing that we
did not use GPU-rendering from the start.) Note that the MSB models have higherrendering cost than those in the PSB, since the MSB models have higher polygon
counts. The average polygon count of the MSB models is 13,613, compared to 4,373
for the PSB. This is because the models in the MSB are generated as iso-surface
meshes from voxel-based models.
If rendering and SIFT feature extraction steps are run on the GPU, and the distancecomputation on the CPU employs table lookup (that is, the case G/G/C/Ct), the total
computation time shrinks to 3.9s for the PSB and 2.9s for the MSB. Compared to theall-CPU implementation that uses table lookup for distance computation (the case
C/C/C/Ct), the proposed GPU-based implementation (G/G/C/Ct) is about 3 to 4 times
faster.
In the GPU-based implementation (G/G/C/Ct), the cost of VQ has now became thedominant factor. The VQ step for the PSB takes more time than that of the MSB. Thisis because, on average, a PSB model produces more features than a MSB model (seeTable 1.)
Our original algorithm would have taken 25s to query a 100,000 model databasestatistically identical to the PSB. The proposed accelerated implementation wouldhave performed the query in about 3.9s for the same 100,000 model database.

Accelerating Bag-of-Features SIFT Algorithm
for 3D Model Retrieval
7

C/C/C/Cf

C/C/C/Cf

G/C/C/Cf

G/C/C/Cf

G/G/C/Cf

G/G/C/Cf

C/C/C/Ct

C/C/C/Ct

G/C/C/Ct

G/C/C/Ct

G/G/C/Ct

G/G/C/Ct
010Rendering

SIFT

20VQ

30
Distance(a) Cost breakdown for the PSB databasequeries.

0Rendering

10SIFT

20VQ

30
Distance(b) Cost breakdown for the MSB databasequeries.

Figure 3. Breakdown of computational cost for querying PSB and MSB database. Note that thesize of database is artificially inflated to 100,000 in computing the cost of distance computation.

4.

Conclusion and Future Work

We have previously published a 3D model retrieval method called Bag-of-Features
SIFT (BF-SIFT) that employs a set of thousands of SIFT features [5] to describe a 3D
shape. The SIFT is 2D image based, local, multi-scale, and rotation invariant. Our
previous experimental evaluation showed that the method is adept at retrieving both
articulated and rigid models [7]. However, the method required significant amount ofcomputation, especially for feature extraction.
In this paper, we proposed a GPU-based algorithm that performs multi-view range
image rendering and SIFT feature extraction of the BF-SIFT algorithm on the GPU.
We also replaced logarithmic functions in the distance computation step with tablelookups. Due to these improvements, the method achieved 3 to 4 times speedup withvirtually no impact on the retrieval performance. On a hypothetical database similar tothe PSB [8] but having 100,000 models, the proposed algorithm would achieve thequery processing time of a few seconds.
An analysis of the accelerated implementation indicated a new target for
acceleration, the vector quantization and distance computation steps. In the future, weintend to investigate better algorithms for both CPU-based and GPU-based
approaches to accelerate these two steps. For example, to vector quantize more
efficiently, we we intend to investigate various approximate nearest neighboralgorithms for higher dimensions, e.g., ANN [6].

8

Ryutarou Ohbuchi, Takahiko Furuya

Reference
1. R. Baeza-Yates, B. Ribiero-Neto, Modern information retrieval, Addison-Wesley (1999).
2. D-Y. Chen, X.-P. Tian, Y-T. Shen, M. Ouh-young, On Visual Similarity Based 3D ModelRetrieval, Computer Graphics Forum, 22(3), 223-232, (2003).
2. G. Csurka, C.R. Dance, L. Fan, J. Willamowski, C. Bray, Visual Categorization with Bagsof Keypoints, Proc. ECCV ’04 workshop on Statistical Learning in Computer Vision, 59-74,(2004)
3. R. Fergus, L. Fei-Fei, P. Perona, A. Zisserman, Learning object categories from Google’s
image search, Proc. ICCV’05, Vol. II, pp.1816-1823, (2005)
4. M. Kazhdan, T. Funkhouser, S. Rusinkiewicz, Rotation Invariant Spherical Harmonics
Representation of 3D Shape Descriptors, Proc. Symposium of Geometry Processing 2003,
167-175 (2003)
5. D.G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, Int’l Journal ofComputer Vision, 60(2), November 2004.
6. D. Mount, S. Arya, ANN: A Library for Approximate Nearest Neighbor Searching,
http://www.cs.umd.edu/~mount/ANN/
7. R. Ohbuchi, K. Osada, T. Furuya, T. Banno, Salient local visual features for shape-based 3Dmodel retrieval, 93-102, Proc. IEEE Shape Modeling International (SMI) 2008, (2008).
8. P. Shilane, P. Min, M. Kazhdan, T. Funkhouser, The Princeton Shape Benchmark, Proc.
SMI 2004, 167-178, (2004).
http://shape.cs.princeton.edu/search.html
9. J. Sivic, A. Zisserman, Video Google: A text retrieval approach to object matching inVideos, Proc. ICCV 2003, Vol. 2, pp. 1470-1477, (2003)
10. A. Vedaldi, SIFT++ A lightweight C++ implementation of SIFT.
http://vision.ucla.edu/~vedaldi/code/siftpp/siftpp.html
11. J. Winn, A. Criminisi, T. Minka, Object categorization by learned universal visual
dictionary, Proc. ICCV05, Vol. II, pp.1800-1807, (2005)
12. C. Wu, SiftGPU: A GPU Implementation of David Lowe's Scale Invariant Feature
Transform (SIFT) , http://cs.unc.edu/~ccwu/siftgpu/
13. J. Zhang, R. Kaplow, R. Chen, K. Siddiqi, The McGill Shape Benchmark, (2005).
http://www.cim.mcgill.ca/shape/benchMark/