Takahiro Matsuda, Takahiko Furuya, Ryutarou Ohbuchi, Lightweight binary voxel shape features for 3D data matching andretrieval, Accepted, Proc. First IEEE Int’l Conf. on Multimedia Big Data (BigMM) 2015, 20-22 April 2015, Beijing, China

Lightweight binary voxel shape features
for 3D data matching and retrieval
Takahiro Matsuda

Takahiko Furuya

Ryutarou Ohbuchi

Graduate School of Medicine andEngineering
University of Yamanashi
Kofu, Japan
g14mk016@yamanashi.ac.jp

Graduate School of Medicine andEngineering
University of Yamanashi
Kofu, Japan
g13dm003@yamanashi.ac.jp

Graduate School of Medicine andEngineering
University of Yamanashi
Kofu, Japan
ohbuchi@yamanashi.ac.jp

using Bag-of-Features (BF) [7, 29] approach. However, such is
not always the case.

Abstract— This paper proposes several lightweight local 3D shapefeatures for 3D voxel data that yield compact binary feature
vectors. These features are inspired by compact binary features for
2D image, namely, Local Binary Pattern (LBP) [22], BRIEF [6]and ORB [26]. In addition to being compact, extraction of
proposed 3D features is inexpensive. Furthermore, these binaryfeature vectors are very efficient to compare, as their distance in
Hamming space can be computed very efficiently. Our
experimental evaluation of these features in a shape-based 3Dmodel retrieval setting showed that some of these 3D binaryfeatures perform competitively to some of existing features.
Depending on benchmark database, proposed features are
somewhat less accurate than or about as accurate as the state-ofthe-art 3D shape features. However, memory footprint is much
more compact, at about 1/10 of the non-binary 3D shape features
having comparable retrieval accuracy.

Some of the recent applications of 3D shape comparison
demand a large number of local 3D features to be computed andthen stored without aggregation. An example is object
recognition in a scene, e.g., recognition of a tumor-like anatomy
in a volume data acquired by X-ray CT scanner. Or, one mayneed to find a part having specific shape (e.g., a rotor of anelectric motor) from an array of assembled mechanical apparatus(e.g., a dishwasher) in a database. In such a case, a large numberof local 3D features extracted from a complex 3D “scene” need
to be stored as they are, without aggregation, so that parts of thescene could be matched later with a query. Since location,orientation, and scale of the desired part in the scene are notknown, the local features need to be aggregated or compared
many times over for the search. Thus, costs of extracting, storing,and matching a large number of these local features, numbering
easily in thousands per 3D object, become very important. To
this end, traditional local features, such as the 2D image feature
SIFT [17] and the 3D shape feature LSF [20] have difficultysatisfying one or more of these requirements. A SIFT feature, forexample, is a 128 dimensional (D) floating point vector that
requires 512 Byte to store per feature. LSF, a derivative of SPRH
by Wahl [34], requires 2,500 Byte per feature for storage. An
FPFH [27] feature, a 125D vector, requires 500 Bytes forstorage. Furthermore, comparison among LSF or FPFH feature
may not be fast enough for repeated re-aggregation required forsearching through a large 3D scene for a queried partial shape.

Keywords- 3D geometric models, 3D shape comparison, local
feature, binary feature, local binary patterns, BRIEF, ORB.

I. INTRODUCTION
Increasing number of companies are offering their 3D CAD
models of parts, mechanical or electronic, on-line. And
increasing number of people are creating and using 3D models
for personalized manufacturing by using 3D printers. Kinect andother RGBD cameras are about to realize 3D geometry capture
for the masses, or for the industry. Medical scanners routinely
capture anatomy in 3D. With these trends in mind, effective andefficient methods to compare, recognize, or retrieve 3D shape
have become an important area of study [5, 9, 11, 12, 13, 15, 16,
20, 23, 27, 30, 33, 34].

In this paper, we propose and compare several local 3D
shape descriptors that are compact and very quick to compare.
For the study described in this paper, we assume that 3D shapes
are represented by using voxel representation. A voxel data may
be captured, for example, by X-ray CT scan or by confocal
microscopy. Alternatively, a voxel data can be rendered from asurface-based 3D model, which may or may not define a solid.
Our proposed features are inspired by local binary 2D image
features BRIEF [6] and ORB [26], whose feature vector arebinary bit strings. We experimentally evaluate retrieval accuracy
and computational cost of the proposed features by using a 3D
shape retrieval scenario. Contribution of this paper can besummarized as follows;

Initially, a predominant approach for 3D shape retrieval used
global shape feature per 3D model. That is, only one feature per
3D model is extracted (e.g., [30]), and the feature is used tocompare and retrieve 3D models. Recently, more and morealgorithms use a set of large number of local features to describe
shape of a 3D model. For example, [5, 9, 12, 20, 23, 31] extract
hundreds to tens of thousands of local features per 3D model for
3D model to 3D model comparison. In such a case, the cost ofcomputing and storing local features can be significant. One
could argue that storage cost is not an issue as these local features
are typically aggregated into a feature vector per 3D model by1

Takahiro Matsuda, Takahiko Furuya, Ryutarou Ohbuchi, Lightweight binary voxel shape features for 3D data matching andretrieval, Accepted, Proc. First IEEE Int’l Conf. on Multimedia Big Data (BigMM) 2015, 20-22 April 2015, Beijing, China
Proposal of multiple local 3D geometrical features that
produce binary feature vector. Binary features are very
compact. They are also very fast to compare in Hamming
space.



Experimental evaluation of proposed 3D features by usinga shape-based 3D model retrieval scenario. The evaluation
showed that the proposed features are very compact and fast
to compare, while retaining most of the accuracy of featuresthat have much larger memory footprint.

Convert tovoxelsExtractshapefeatures

Quantizefeatures=
Polygonmesh
model

II. RELATED WORK

Volume ofinterest(VOI)

Set of local
features(e.g., 5,000 per
3D model)

Code
words

A feature vector(histogram) per
3D modelFigure 1. A set of local, voxel-based 3D shape features is extracted from thevoxel representation of a 3D model. Local features are aggregated into afeature vector per 3D model for 3D-model-to-3D-model comparison.
Proposed binary features use Hamming distance for vector quantization.

In the domain of 2D image analysis, SIFT [17], SURF [4]and other feature descriptors have been used extensively, whichis invariant, to varying degrees, to geometrical transformations
including scaling, translation, and rotation. However, thesedescriptors are rather expensive to compute. In addition, theirfeature vectors have large memory footprints, as they use highdimensional floating point vectors. For example, a SIFT vector
having 128D has 512 Byte, or 4,096 bit, memory footprint. For
object localization or image retrieval, hundreds to thousands ofthese features per image are sampled, occupying megabytes ofmemory.

variations, 3DORB-PCA, 3DORB-CG, 3DORBL-CG, and
3DORBL-R-CG, depending on the way rotation normalizationis performed and the way features are computed. These features
are evaluated by using a 3D shape retrieval scenario explained
below.
A. Surface-based 3D Shape Model Retrieval Pipeline
The steps for 3D model to 3D model shape comparison are
as follows. Please refer to Figure 1 for block diagram of thepipeline. Our 3D shape retrieval scenario converts, for feature
extraction, input surface-based 3D models into one of two kindsof voxel-based 3D shape models; either volume voxel model orsurface voxel model. A volume voxel model represents volume
of a 3D model by voxels. A volume voxel model can only be
computed if the original surface-based 3D model defines a solid.
If the original surface based 3D model is not solid, e.g., if it is an
open mesh or a polygon soup, it can only be converted to asurface voxel model that uses voxels to represent surfaces. For abenchmark database consisting only of solids, retrieval
experiments are done using both volume voxel model andsurface voxel model of the database. On the other hand, if thedatabase contains non-solid 3D models, retrieval experiments
are done using surface voxel model only.

For 3D shape comparison and retrieval, the situation could
get worse. If the method is view-based, and performs multi-view
rendering to achieve 3DOF rotation invariance, a large numberof 2D features are produced. For example, in [9], about 10k SIFT
features are computed per 3D model. One may use a 3D shapefeature densely sampled on a 3D model or a 3D scene. 3D shapefeatures SPRH [34] and its localized derivatives LSF [20], FPFH
[27] are computed from oriented point set. The LSF has adimensionality of 625 and requires 2,500 Byte. FPFH feature,
which is very similar to SPRH above, occupies 500 Bytes. 3D
shape features VSIFT [23] and 3DSURF [11] are computed fromvoxel representation of 3D shape. Features of VSIFT and
3DSURF are floating vectors having 1,280D and 162D,
respectively.
If an entire 3D model is compared with the whole of the other3D model, one could aggregate a set of a large number of local
features into a feature vector per 3D model, e.g., by using Bagof-Features (BF) [7, 29] or Fisher Vector [24]. However, if thetask is to recognize a sub-part of a 3D model or a scene by usinga scheme similar to moving sub-window, local features are often
retained as they are for they need to be aggregated repeatedly foreach sub-part. In such a case, cost of storing and aggregating
thousands or tens of millions of local features becomes critical.

1.

Surface to voxel conversion: A surface-based 3D model iscentered at coordinate origin, and scaled to fit in a unit
sphere. It is then converted into a voxel representation
having size 1283 in a voxel buffer of size 1503. A non-solid
surface-based 3D model is converted to a surface-based
voxel model. A solid model is converted to either surface
voxel model or solid voxel model for comparison.
(a) Voxel pyramid generation (optional): For
3DBRIEF and 3DORB, a voxel scale space, or voxel
pyramid, is generated by repeated low-pass filteringand 2-to-1 down sampling for multi-scale feature
extraction.

Recently, a class of “compact binary” features are proposedthat are lightweight to compute, compact, and efficient tocompare. These features employ binary vector having tens tohundreds of bits for their feature. Binary Robust Independent
Elementary Features (BRIEF) [6], Oriented FAST and Rotated
Brief (ORB) [26] are two of the examples of this class of features.
In this paper, we try to extend these binary 2D image features
into the domain of 3D shape represented by voxels.

(b) Gaussian smoothing (optional): Surface voxel
model is blurred by using Gaussian filter prior tofeature computation so that voxelized surfaces havethicknesses more than one voxel. A feature works
better with these thicker surfaces. Final size of a 3D
voxel model after filtering becomes 1323.

III. LIGHTWEIGHT 3D SHAPE FEATURES FROM VOXELSIn this paper, we propose three voxel shape features 3D
Local Binary Pattern (3DLBP), 3DBRIEF, and 3DORB that
produce binary feature vectors. The last, 3DORB, includes four2.

2

Sample point selection: Features are extracted from M
sample points randomly and densely selected from non-zeroTakahiro Matsuda, Takahiko Furuya, Ryutarou Ohbuchi, Lightweight binary voxel shape features for 3D data matching andretrieval, Accepted, Proc. First IEEE Int’l Conf. on Multimedia Big Data (BigMM) 2015, 20-22 April 2015, Beijing, China
voxels within the voxel buffer. In the experiments describedlater, we use M=3,000 and 5,000.
3.

1) 3DLBPThis feature, called 3D Local Binary Pattern (3DLBP), is a
3D counterpart to a variation of Local Binary Pattern (LBP)
feature for 2D images [21, 22]. A 3DLBP feature is computedfrom a cubic Volume Of Interest (VOI) of size l×l×l=l3. Within
the VOI, multiple Sub-Local Binary Patterns (SLBPs) arecomputed at every (i.e., l3) voxel in the VOI. Each SLBP, a 6 bit
string, is computed by comparing the value of the SLBP center
voxel with the values of its 6 neighboring voxels using a fixedvoxel traversal order (Figure 2). The bit corresponding to aneighboring voxel becomes ‘1’ (‘0’) if its value is less than(greater or equal to) the center voxel. Total of l3 SLBP bit strings
are aggregated into a 3DLBP feature vector for the VOI having
64 dimensions by counting population of 64 (0~63) possible
values of the 6 bit SLBPs. A 3DLBP is thus not a binary feature
but a 64D integer-valued vector. This aggregation per VOI for
the 3DLBP may be considered as a very simple form of Bag-ofFeatures with a fixed 64 word vocabulary.

Feature extraction: A cubic Volume Of Interest (VOI) of
size lll is set around the sample point, and a feature iscomputed. For 3DBRIEF and 3DORB, this is done at eachresolution level of the pyramid. Details of the feature
extraction algorithms will be described later.
(a) VOI rotation normalization (optional): For
3DORB, each VOI is rotation normalized prior tofeature extraction. We compare two rotation
normalization algorithms that will be described later.
The other two features, 3DLBP and 3DBRIEF, do not
perform rotation normalization.

4.

Feature aggregation: A set of M local features areaggregated into a feature vector per 3D model by using Bagof-Features (BF) approach.

5.

Ranking: Database 3D models are ranked against the query
3D model based on the similarity between the aggregatedfeature vectors of the query and the target (DB) 3D models.

l3 SLBPsllB. Converting Polygonal Surface Model into Voxel Model
Features used in this paper are extracted from voxel, or 3D
pixel, representation of 3D shapes. Thus, prior to feature
extraction, our algorithm converts input 3D models represented
as polygonal mesh into their voxel representations. As describedabove, for a surface-based 3D model defining a solid, twovariations to voxel representations, surface voxel model andvolume voxel model, are generated. Models found in McGill
Shape Benchmark [19], for example, define solids. For a nonsolid surface-based 3D model, only a surface-based voxel model
is generated. A 3D model is converted into a cubic volume
having size n×n×n. Based on preliminary experiments, we chose
n=128, inset a voxel buffer of size 1503.

…

l…
A 3DLBP VOI
of size l3
contains l3 SLBP
features.

At l3 SLBP centers,compare values of avoxel and its 6
neighbors

l3 SLBP bit strings
1011012=4510
0010112=1110
1100012=4910…
Total of l3 SLBP
bit strings withvalue 0~63 areaggregated.

A 3DLBPhistogram(64D) forthe LBP

Figure 2. The 3D Local Binary Pattern (3DLBP) feature computes a binary
string based on comparison of local voxel values within the volume ofinterest about the feature center.

The number of SLBPs per 3DLBP feature, or the size of
VOI, l3 is a parameter that affects performance andcomputational cost of the 3DLBP feature. It is possible to useneighborhood size of SLBP larger than 6, e.g., 18, but thedimensionality of the aggregated 3DLBP feature per the VOI
quickly becomes too large (e.g., 218=262,144) with little or no
gain in accuracy.

To generate a surface voxel model, we use Out-Of-Core
Sparse Voxel Octree (OOC-SVO) algorithm by Baert et al [3]. It
exploits octree data structure for fast voxelization. As an option,a surface voxel model may be Gaussian smoothed using a kernel
having size 53 to produce a surface voxel model having surface
thickness more than 1 voxels. (The Gaussian smoothing makes
a voxel model to expand to the size 1323.) To generate a solid
voxel model, we use the algorithm by Abdellah et al [1]. The
algorithm first generates a voxel model of closed surface, thenrun a flood-fill to convert it into a filled, solid voxel model.

To gain certain degree of invariance to scale, we apply the
3DLBP to a multi-scale voxel pyramid. To form a multi-scale
pyramid of voxels, we simply down sample the object having
1283 resolution by half in each axis, producing 4 levels ofrepresentations having voxel size 1283, 643, 323, and 163(Figure 3), before applying 3DLBP at each resolution level.

C. Dense Local Voxel Feature Extraction
In case of 2D image features, features are often extracted atinterest points detected by such interest point detectors as FAST
[25] or Difference of Gaussian (DoG) detector in SIFT [17].
Interest point detection is a must if matching of local features
among images (or 3D models) is the objective. For object
recognition and retrieval, however, dense sampling of featuresoften outperforms interest-point based feature sampling. As our
objective is retrieval and recognition of 3D object, we assumedense sampling of 3D features on or near the 3D object. We
randomly and densely select voxels having non-zero value, anduse them as “forced” (v.s. detected) keypoints. Then, at each
keypoint, one of the following features is computed.

1283
643

323

163

Figure 3. Feature extraction from multi-scale (4 levels) voxel pyramid.

2) 3DBRIEF
3DBRIEF is a simple 3D binary feature based on the BRIEF
feature [6], and is very lightweight to extract. An N bit BRIEF
feature vector is produced by comparing values of N randomly
selected pairs of voxels. If a pair of voxels at locations a and b

3

Takahiro Matsuda, Takahiko Furuya, Ryutarou Ohbuchi, Lightweight binary voxel shape features for 3D data matching andretrieval, Accepted, Proc. First IEEE Int’l Conf. on Multimedia Big Data (BigMM) 2015, 20-22 April 2015, Beijing, China
bit descriptor. We did not employ this learning, as ourpreliminary experiments showed that the learning did not
improve accuracy. We simply select N randomly selected pairsof voxels for 3DORB signature.

is selected, their values vox(a) and vox(b) are comparedaccording to equation (1) to yield a bit of the N bit feature vector.
Typically, number of bits N of the descriptor is in the range tens
to hundreds of bits. In the experiments that follow in this paper,
we used N=256 based on the preliminary experiments.
1, if vox(a)  vox(b)otherwise0,( a,b)  a) 3DORB-CG
The 3DORB-CG employs the same strategy as 2D version of
the ORB for rotation normalization. We first compute 0th and1st order moment mpqr of the voxels in a cubic VOI, whose
length of an edge is n voxels. Moment m000 is 0th order, that is,sum of all the voxel values in the VOI [25]. Three 1st ordermoments m100, m010, m001 are 1st order moments along x, y, andz axes, respectively [10].



3DBRIEF does have invariance against translation, but itlacks invariances against rotation and scaling. We extract
3DBRIEF on a voxel image pyramid to provide for certain
invariance against scaling (but not rotation). All the features
extracted from multiple scales are later aggregated together intoa feature vector by using BF approach.

(2)

m 100 m 010 m 001,,)
m 000 m 000 m 000(3)x, y,z

3DBRIEF is very fast to compare, as it is a binary vector andthe comparison is made by computing Hamming distance.
Hamming distance between a pair of binary strings can becomputed very efficiently by using a combination of (SIMD) an
XOR instruction and a population count instruction.

( x, y, z )  (Then, we compute a vector from the CG to the center of VOI
as a rotational axis, and align the VOI along the direction. We
then find and compensate for the rotation about this axis, byfinding a farthest non-zero voxel (the green sphere in Figure 5),
and rotate the VOI about the axis. Note that the rotation
normalization is not effective if the estimated displacement
vector from the center of VOI to the CG is unreliable. In our
implementation, we forego the rotation normalization if thelength of computed displacement vector is less than 1/5 of thesize n of side of the VOI.

3) 3DORB
Adding rotation invariance to 3DBRIEF by 3DOF
orientation normalization produces 3D ORiented Brief or
3DORB. The rotation normalization is applied to each local VOI,
not for the entire voxel model.
We experimented with two approaches for orientation
normalization; one is called 3DORB-CG for its use of Center ofGravity (CG) for orientation normalization, and the other iscalled 3DORB-PCA for its use of Principal Component Analysis(PCA). There are two variants to feature computation method.
3DORB compares a pair of individual voxel values to derivefeature vector, as in 3DBRIEF. A variant, called 3DORBL with
suffix “L”, uses a smoothed (averaged) value computed from asmall (e.g, 3×3×3) Volume of Smoothing (VOS) of size k×k×k,
k<<l, for the comparison. 3DORBL with smoothing exhibits
higher accuracy than 3DORB, albeit at a higher computationalcost. 3DORBL-CG has a subtype called 3DORBL-R-CG. The
3DORBL-R-CG has less cost of rotation normalization than the
3DORBL-CG. Figure 4 illustrates these variants.

After the rotation normalization, a feature vector, in the formof a bit string, is extracted in the manner similar to 3DBRIEF.
As with the case of 3DBRIEF, for scale invariance, features are
extracted from multi-scale pyramid of voxels. Based on our
preliminary experiment, number of bits N=256 for the 3DBRIEF
is used in the following.
b) 3DORB-PCA
For rotation normalization, the 3DORB-PCA applies PCA to
the 3×3 covariance matrix of voxel values within the VOI.
Principal axes obtained from the PCA indicate orientation, but
directions of the vectors are left undefined. Direction of the axes
is disambiguated by comparing the center of gravity and the(geometric) center of the VOI. After the rotation normalization,
feature vector is extracted in the manner similar to 3DORB-CG(or 3DBRIEF). We use, in the following experiment, the feature
vector length N=256 bit.

2D image version of the ORB [26] employs a simple learning
strategy to determine most effective N pairs of pixels for its N

CG (Centroid)

3DORB compares apair of individual
voxels (red cubes)
within a cubic Voxelof Interest (VOI)(orange line).

m pqr   x p y q z r vox ( x , y , z )3DORBL compares a 3DORBL-R computes
pair of averaged voxel feature as in 3DORBL,
values. Each value isbut its rotation
computed from a small
normalization uses
Volume Of Smoothing voxels in a cubic region(VOS) indicated by(dotted blue line)
green cubes.
smaller than the VOI forfeature extraction.

Farthest nonzero voxel
from the CG

Center of VOIFigure 5. Rotation normalization of voxels for the 3DORB-CG feature. Thisrotation normalization is performed for each local VOI, not for the entire 3Dmodel. (Best viewed in color.)

4) 3DORBL-CG and 3DORBL-R-CG
Comparing a pair of individual voxels, as in BRIEF,
3DBRIEF and 3DORB, is somewhat prone to noise. To improve

Figure 4. Three variants to 3DORB.

4

Takahiro Matsuda, Takahiko Furuya, Ryutarou Ohbuchi, Lightweight binary voxel shape features for 3D data matching andretrieval, Accepted, Proc. First IEEE Int’l Conf. on Multimedia Big Data (BigMM) 2015, 20-22 April 2015, Beijing, China
robustness against noise, we tried a variation of 3DORB thatuses an average of voxel values in a small cubic region called
Volume of Smoothing (VOS) for the comparison. It amounts tobox-filtering voxel values, and we employ the (3D) integral
image for fast computation of local sum of voxel values in a
VOS. We identify the smoothing by adding letter “L” to thename of the methods, as in 3DORBL-CG and 3DORBL-R-CG.

IV. EXPERIMENTS AND RESULTS
In this section, we evaluate accuracy, computational cost,and memory footprint of the proposed binary features by using
four benchmarks for shape-based 3D model retrieval. We used
MSB [19] for highly articulated but less detailed shapes defined
as solid. The MSB consists of 255 models in 10 classes. The
MSB includes such articulated shapes as “humans”,“octopuses”, “snakes”, “pliers”, and “spiders”. We used PSB[28] test set for a set of non-solid 3D models (many of them
polygon soup model) having quite diverse but mostly rigid
shapes. The PSB test-set contains 907 models partitioned into 92
classes. The PSB contains a very diverse, mostly rigid 3D
shapes, including cars, chairs, potted plants, airplanes, rangescanned (open-mesh) faces, insects, etc. For the MSB and PSB,
query models are drawn from the retrieval targets, and every pairof models in the database are queried to compute retrieval
accuracy. As the third benchmark, we used ESB [8] database,which consists of 867 mechanical CAD models of machineparts, including gears, pipes, screws, flanges, etc., divided into
45 classes. Fourth benchmark is SHREC 2011 Non-Rigid(SH11NR) [14], which contains 600 non-rigid, solid 3D models
in 30 classes extracted from MSB and other dataset. As with the
MSB, ESB and PSB, in SH11NR, query models are drawn fromthe retrieval targets, and every pair of models in the database are
queried to compute retrieval accuracy. Examples of 3D models
from these four benchmark databases are shown in Figure 6.

For 3DORBL-CG, rotation normalization is done by using
all the voxels in the VOI of size l×l×l for feature computation.
For a larger VOI size, this leads to a rather high cost of rotation
normalization. We thus created a variation of 3DORB-CG called
3DORBL-R-CG (“R” stands for “reduced cost”) that has
reduced cost of rotation normalization. In 3DORBL-R-CG, the(cubic) region used for rotation normalization is smaller than thatof the VOI for feature computation.
D. Local Feature Aggregation by using Bag-of-Features
Local features described above are aggregated into a feature
vector per 3D model by using the Bag-of-Feature (BF) approach[7, 29]. The BF approach learns, at its preprocessing stage, a setof vocabulary, or codebook, from the 3D shape descriptors
extracted from a set of 3D models either identical or similar to
the retrieval target. The codebook is typically learned byclustering the features, e.g., by using k-means clustering
algorithm. Since the features above are binary bit string, insteadof k-means in Euclidian space (i.e., using L2-norm), we run kmeans in Hamming space (i.e., Hamming distance.). We
modified the code of k-means++ [2], which performs clusteringin Euclidian space in its original form, so that the clustering in
Hamming space can be computed.

As performance indices, we use Mean Average Precision(MAP) [18].

After the dictionary is learned, a descriptor is vector
quantized, in Hamming space, into a word from the dictionary.
Histogram of words, whose dimension is the number of words
in the dictionary, becomes the descriptor for the 3D model. The
size of k, or the number of words in the codebook, significantly
affects retrieval accuracy. A feature vector per 3D model thus
created is a histogram whose element is an integer, and most of
the elements are zero.
E. 3D Model-to-3D Model Dsitance Computation
A distance among a pair of per-3D-model feature vectors(that is, features after aggregation) is computed, per database, byusing either L1-norm, L0.5-norm, or (symmetricized) KullbackLeibler Divergence (KLD). For each database, we try all thethree distances, and choose the best performing one to derive
retrieval accuracy indices for the database. (The KLD may face
divide-by-zero error as a BF-aggregated feature vector would
contain many elements with value zero. To circumvent the error,
we replace a zero with a very small non-zero value, e.g.,1  10 20 .)nd L1( x i , x j )   | x ia  x ja |











（c）ESB.

（d）SH11NR.

A. Retrieval accuracy of features
Figure 7 compares retrieval accuracy of 8 features as recallprecision plots. Bar graphs of Figure 8 compare retrieval
accuracy of 8 features measured as MAP [%] by using the fourbenchmarks. 3D models of MSB, ESB, and SH11NR definesolids. These models are converted to both solid voxel andsurface voxel representations in order to compare performancesof features among these two representations. Then, two of thefeatures, 3DORBL-CG and 3DORBL-R-CG, are tested on bothsolid voxel and surface voxel representations. (3D models in
PSB can only be converted to surface voxel representations.)
Consequently, there are 10 “algorithms” listed in the graph. Top
two algorithm, LSF [20], and BF-DSIFT [9], are used asbaseline.

(4)
2

n
 x 
d KLD xi , x j   xia  x ja log  ia  
 x ja a 1（b）PSB.

Figure 6. Example 3D models from the four benchmark databases, MSB,
PSB, ESB, and SH11NR.

a 1


 n
d L 0.5 ( xi , x j )    xia  x ja  a1（a）MSB.

(5)


5

1.0

1.0

0.8

0.8

0.8

0.8

0.6
0.4

0.6
0.4

0.0
0.2 0.4 0.6 0.8
RecallLSF

BF-DSIFT

0.4

0.0

1

0.2

3DLBP

0.4 0.6
Recall

0.8

3DBRIEF(a) MSB.

3DORB-PCA(b) PSB.

0.4

0.0
0.0 0.2 0.4 0.6 0.8 1.0
Recall

1.0

0.6

0.2

0.0

0.0
0

0.6

0.2

0.2

0.2

Precision

1.0

Precision

1.0

Precision

Precision

Takahiro Matsuda, Takahiko Furuya, Ryutarou Ohbuchi, Lightweight binary voxel shape features for 3D data matching andretrieval, Accepted, Proc. First IEEE Int’l Conf. on Multimedia Big Data (BigMM) 2015, 20-22 April 2015, Beijing, China

3DORB-CG(c) ESB.

0.0 0.2 0.4 0.6 0.8 1.0
Recall3DORBL-CG

3DORBL-CG (solid)(d) SH11NR.

Figure 7. Recall-precision plots for four benchmark databases.

MSB

PSB

ESB

84.6

35.8

LSF

49.3

85.3
81.3

50.4
52.5

BF-DSIFT

53.8
67.5

33.2
30.9

3DBRIEF

52.0

79.0
78.8

40.1
41.1

3DORB-CG

45.1
46.5

3DORBL-R-CG

Our observations is that, at voxel resolution of 1283, solid
voxel and surface voxel models become nearly identical,
especially for ESB whose mechanical parts, e.g., flanges, panels,
gears, or tubes have thin walls. In the case of SH11NR, with its
solid models of animals etc. having thick body, solid voxel
representation worked for 3DORBL-CG and 3DORBL-R-CGfeatures.

77.7

45.6
47.1

3DORBL-CG

Figure 9 compares, using 3 benchmarks consisting of solid
3D models, 6 proposed algorithms for their retrieval accuracy on
solid voxel and surface voxel representations of 3D shapes.
Overall, for all the three benchmarks, there is only small
difference between solid voxel and surface voxel representations.

77.3

36.2
39.1

3DORB-PCA

3DORB-CG, with its rotation normalization, clearly
outperforms BRIEF and 3DLBP, as well as 3DORB-PCA. Of
rotation normalized 3DORB-CG variations, 3DORBL-CG,
which compares locally smoothed voxel values, did better.
3DORBL-R-CG, a variation of 3DORBL-CG with less stringent
but faster rotation normalization, did slightly worse than
3DORBL-CG for the ESB, but almost as well as on the othertwo benchmarks.

77.3
68.5

29.7
32.9

3DLBP

According to some SHREC tracks [15], the BF-DSIFT is oneof better performing features, especially for rigid polygon soupmodels of PSB as well as for non-rigid models of MSB. Overall,view-based BF-DSIFT performs the best for PSB containing
many polygon soup models. LSF, which captures 3D structureby sampling surface by points, does well for ESB, SH11NR andMSB.

SH11NR

78.6
75.2
78.1

B. Spatial and Temporal Costs
Table 1 shows execution timings, per query, of the features
for the 3D model retrieval task using PSB benchmark. The costof feature extraction includes Gaussian filtering and multi-scale
voxel pyramid construction. For each algorithm (row), timing
for voxelization (VX), feature extraction (FE), vector
quantization (VQ), distance computation (DC), and total time for
retrieval (RET) are shown in seconds [s]. Time for voxelization
includes Gaussian filtering, if applicable, and feature extraction
includes time for voxel pyramid construction

77.0
80.4

3DORBL-CG(Solid)

47.1

83.4
79.3

3DORBL-R-CG(Solid)

46.5
0.0

20.0

40.0

60.0

82.4
80.0

100.0

In terms of feature extraction, 3DBRIEF is very fast,
requiring only 0.12s per 3D model, while 3DORB-CG and
3DORBL-CG requires about 10s per 3D model. The latter two
spend most of their time performing rotation normalization. In

MAP [%]
Figure 8. Comparison of retrieval accuracy in MAP [%] by using fourbenchmarks, eight algorithms, and two voxelization methods.

6

Takahiro Matsuda, Takahiko Furuya, Ryutarou Ohbuchi, Lightweight binary voxel shape features for 3D data matching andretrieval, Accepted, Proc. First IEEE Int’l Conf. on Multimedia Big Data (BigMM) 2015, 20-22 April 2015, Beijing, China
3DLBP
3DBRIEF
3DORB-PCA
3DORB-CG
3DORBL-CG
3DORBL-R-CG

comparison, 3DORBL-R-CG is quite economical, requiring
only 0.76s for both rotation normalization and feature extraction.
Total execution time of 3DORBL-R-CG is also fast among thefeatures compared. Yet, as noted in the previous section,
retrieval accuracy of 3DORBL-R-CG is only slightly worse thanmuch slower 3DORBL-CG.

Surface
Solid

0.0

20.0

40.0
60.0
MAP [%](a) MSB.

3DLBP
3DBRIEF
3DORB-PCA
3DORB-CG
3DORBL-CG
3DORBL-R-CG

80.0

Table 2 compares memory footprints of the features. Herethe comparison is not as easy, since the best performing numberof features per 3D model varies depending on the benchmark
database, etc. Still, it is apparent that 3DBRIEF and 3DORB arecompact, requiring only 32 Bytes per feature. In terms ofmemory footprint per 3D model, which assumes all the local
features need to be retained, binary features of 3DORB and 3D
BRIEF require much less (1/10) space than floating point feature
vectors of LSF, etc.

100.0

Surface
Solid

0.0

20.0

40.0
60.0
MAP [%](b) ESB.

3DLBP
3DBRIEF
3DORB-PCA
3DORB-CG
3DORBL-CG
3DORBL-R-CG

80.0

V. SUMMARY AND CONCLUSION

100.0

With increasing popularity of 3D shape models, shapesimilarity search of such 3D models is about to become an
important tool. In this paper, we have proposed local,
lightweight, binary 3D shape features. We have experimentally
evaluated their retrieval accuracy, computational cost, andstorage cost. Our evaluation experiments are set in the context
of 3D shape retrieval. According to the experiments, one of the
proposed features, 3DORBL-CG, produced very compact
feature and performs only slightly worse than some of the stateof-the-art 3D model retrieval algorithms. An appearance based
retrieval algorithm, BF-DSIFT [9], outperforms proposed
3DORBL-CG for retrieval accuracy for the PSB benchmark.
However, BF-DSIFT feature requires memory footprint of
6.4 MByte, while that of 3DORBL-CG is only 1/10 at 160
Kbyte.

Surface
Solid

0.0

20.0

40.0
60.0
MAP [%](c) SH11NR.

80.0

100.0

Figure 9. Retrieval accuracy in MAP for 3D model benchmark databases thatconsists only of solid models.
Table 1. Execution timings for processing a query. Timings are measurefor PSB benchmark by using surface voxel representation. Retrieval
accuracy in MAP [%] for PSB is also shown.
Algorithm
LSF
BF-DSIFT (CPU)BF-DSIFT (GPU)
3DLBP
3DBRIEF
3DORB-PCA
3DORB-CG
3DORBL-CG
3DORBL-R-CG

VX
[s]

0.05
0.05
0.05
0.05
0.05
0.05

FE
[s]
1.54
33.06
1.12
0.60
0.12
2.49
9.36
10.35
0.76

VQ
[s]
6.11
0.02
0.02
0.78
0.24
0.24
0.24
0.24
0.24

DC
[s]
0.002
0.030
0.030
0.002
0.002
0.002
0.002
0.002
0.002

RET
[s]
7.65
33.11
1.17
1.43
0.41
2.78
9.65
10.64
1.05

In the future, we intend to improve the proposed binaryfeatures both in terms of computational cost and retrieval
accuracy. For example, we plan to explore a faster rotation
normalization algorithm and GPU implementation. We also
would like to try Fisher Vector for binary features [32] for an
aggregation method better than Bag-of-Features.

MAP
[%]
35.8
50.4
50.4
29.7
33.2
36.2
40.1
45.6
45.1

REFERENCES
[1]
[2]

[3]
Table2. Memory footprints of features in typical usage.
Features
LSF
BF-DSIFT (CPU)BF-DSIFT (GPU)
3DLBP
3DBRIEF
3DORB-PCA
3DORB-CG
3DORBL-CG
3DORBL-R-CG

Size perfeature [Byte]# features /3D model

2,500
512
512
256
32
32
32
32
32

2,048
12,60012,600
3,000
5,000
5,000
5,000
5,000
5,000

Memoryfootprint per 3Dmodel [Byte]
5,120k
6,451k
6,451k
768k
160k
160k
160k
160k
160k

[4]
[5]

[6]
[7]

[8]

7

M. Abdellah, voxelizer2. https://github.com/marwan-abdellah/ voxelizer2/, (accessed 2015-02-21).
D. Arthur, S. Vassilvitskii, “k-means++: The Advantages of Careful
Seeding,” Proc. ACM-SIAM Symp. on Discrete Algorithms 2007,
pp.1027-1035, (2007).
J. Baert, A. Lagae, P. Dutr´e, “Out-of-core construction of sparse voxel
octrees,” Proceedings of the 5th High-Performance Graphics Conference.
ACM, 2013. pp. 27-32. (2013).
H. Bay, T. Tuytelaars, L. Van Gool, “SURF: Speeded Up Robust.
Features,” Proc. ECCV‘06, pp. 404-417, (2006).
A.M. Bronstein, M.M.Bronstein, L.J. Guibas, M. Ovsjanikof, Shapegoogle: Geometric words and expressions for invariant shape retrieval,
ACM TOG, 30(1), pp.1-20, (2011).
M. Calonder, V. Lepetit, C. Strecha, P. Fua, “BRIEF: Binary robust
independent elementary features,” Proc. ECCV 2010, 778-792, (2010).
G. Csurka, C.R. Dance, L Fan, J Willamowski, C. Bray, “Visual
Categorization with Bags of Keypoints,” Proc. European Conference on
Computer Vision ’04 workshop on Statistical Learning in Computer
Vision, pp. 59-74, (2004).
Engineering Shape Benchmark, <http://shapelab.ecn.purdue.edu/.>Takahiro Matsuda, Takahiko Furuya, Ryutarou Ohbuchi, Lightweight binary voxel shape features for 3D data matching andretrieval, Accepted, Proc. First IEEE Int’l Conf. on Multimedia Big Data (BigMM) 2015, 20-22 April 2015, Beijing, China[22] T. Ojala, M. Pietikäinen, and D. Harwood, “A Comparative Study of
Texture Measures with Classification Based on Feature Distributions”,
Pattern Recognition, vol. 29, pp. 51-59 (1996).
[23] K. Osada, T. Furuya, R. Ohbuchi, “SHREC’08 entry: Local volumetricfeatures for 3D model retrieval,” Proc. IEEE Shape Modeling andApplications (SMI 2008), IEEE International Conference on, pp. 245 –
246, (2008).
[24] F. Perronnin, J. Sánchez, and T. Mensink. “Improving the fisher kernel
for large-scale image classification”, In Proc. ECCV, 2010, pp.143-156.
(2010).
[25] E. Rosten, T. Drummond, “Fusing points and lines for high performancetracking,” Proc. ICCV 2005, Vol. 2: 1508–1511, (2005).
[26] E. Rublee, V. Rabaud, K. Konolige, G. Bradski, “ORB: an efficient
alternative to SIFT or SURF,” Proc. ICCV ’11, pp. 2564–2571, (2011).
[27] R. B. Rusu, N. Blodow, M. Beetz, Fast point feature histograms (FPFH)
for 3D registration, Proc. IEEE International Conference on Robotics andAutomation (ICRA) 2009, pp. 1848-1853, (2009).
[28] P. Shilane, P. Min, M. Kazhdan, and T. Funkhouser, “The Princeton
Shape Benchmark,” Proc. SMI ’04, 2004, pp. 167-178,<http://shape.cs.princeton.edu/benchmark/.>[29] J. Sivic, B. Russell, A. Efros, A. Zisserman, and W. Freeman,“Discovering objects and their location in images,” Proc. IEEE ICCV2005, Vol. 1, pp. 370-377, Oct. (2005).
[30] J.W.H. Tangelder, R.C.Veltkamp, “A survey of content based 3d shape
retrieval methods,” Multimedia Tools and Applications, vol. 39, pp. 441–
471, (2008).
[31] R. Toldo, U. Castellani, A. Fusiello, “Visual vocabulary signature for 3D
object retrieval and partial matching,” Proc. EG Workshop on 3D Object
Retrieval 2009 (3DOR 2009), pp.21-28, (2009).
[32] Y. Uchida, S. Sakazawa, “Image Retrieval with Fisher Vectors of Binary
Features,” Proc. 2nd IAPR Asian Conference on Pattern Recog ition(ACPR) 2013, pp. 23-28, (2014).
[33] R.C. Veltkamp, F.B. ter Harr, “SHREC 2007 3D Shape Retrieval Contest,”
Dept. of Info. and Comp. Sci., Utrecht University, Technical Report UUCS-2007-015, (2007).
[34] E. Wahl, U. Hillenbrand, G. Hirzinger, “Surflet-Pair- Relation
Histograms: A Statistical 3D-Shape Represen- tation for Rapid
Classification,” Proc. of the Fourth Intern’l Conf. on 3-D Digital Imagingand Modeling (3DIM 2003), 474-481, Banff, Canada, (2003).

[9]T. Furuya, R. Ohbuchi, “Dense sampling and fast encoding for 3D model
retrieval using bag-of-visual features,” Proc. ACM CIVR 2009, Article No.
26, (2009).
[10] M. K. Hu. “Visual pattern recognition by moment invariants,” IRE Trans.
Information Theory, 8(2), pp. 179–187, (1962).
[11] J. Knopp, M. Prasad, G. Willems, R. Timofte, L. Van Gool, “Houghtransform and 3D SURF for robust three dimensional classification,” Proc.
ECCV‘10, 589-602, (2010).
[12] G. Lavoué, “Bag of Words and Local Spectral Descriptor for 3D Partial
Shape Retrieval,” Proc. EG Workshop on 3D Object Retrieval 2011
(3DOR 2011), pp.41-48, (2011).
[13] B. Li, Y. Lu, C. Li, A. Godil, T. Schreck, M. Aono, Q. Chen, N.K.
Chowdhury, B. Fang, T. Furuya, H. Johan, R. Kosaka, H. Koyanagi, R.
Ohbuchi, A. Tatsuma, “SHREC'14 Track: Large Scale Comprehensive 3D
Shape Retrieval”, Proc. EG Workshop on 3D Object Retrieval 2014
(3DOR 2014), pp.131-140, (2014).
[14] Z. Lian, A. Godil, B, Bustos, M, Daoudi, J. Hermans, S. Kawamura, D.
Vandermeulen, SHREC'11 Track: Shape Retrieval on Non-rigid 3D
Watertight Meshes. 3DOR, 11, 79-88, (2011).
[15] Z. Lian, A. Godil, B. Bustos, M. Daoudi, J. Hermans, S. Kawamura, Y.
Kurita, G. Lavoué, H. V. Nguyen, R. Ohbuchi, Y. Ohkita, Y. Ohishi, F.
Porikli, M. Reuter, I. Sipiran, D. Smeets, P. Suetens, H. Tabia, D.
Vandermeulen, “A comparison of methods for non-rigid 3D shape
retrieval,” Pattern Recognition, 46(1), January, (2013).
[16] Y. Liu, Z. Zha, H. Qin, Shape Topics, “A Compact Representation and
New Algorithms for 3D Partial Shape Retrieval,” Proc. IEEE CVPR,
Vol.2, pp.2025-2032, (2006).
[17] D.G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,”
IJCV, 60(2), (2004).
[18] D. Manning, P. Raghavan, H. Schutze, "Introduction to Information
Retrieval, Cambridge University Press (2008).
[19] McGill 3D Shape Benchmark,<http://www.cim.mcgill.ca/~shape/benchMark/.>[20] Y. Ohkita,Y. Ohishi,T. Furuya, R. Ohbuchi, “Non-rigid 3D Model
Retrieval Using Set of Locasl Statistical Features,” Proc. IEEE ICME
2012 Workshop on Hot 3D, pp. 593-598, (2012).
[21] T. Ojala, M. Pietikäinen, and D. Harwood, “Performance evaluation of
texture measures with classification based on Kullback discrimination of
distributions”, Proceedings of the 12th IAPR International Conference on
Pattern Recognition (ICPR 1994), vol. 1, pp. 582 - 585 (1994).

8