4-21

MVA2011 IAPR Conference on Machine Vision Applications, June 13-15, 2011, Nara, JAPANAlignment of 3D Shape Data by Hashing Sets of Feature Points
Yuka Kohno Osamu Yamaguchi Toshio Sato Bunpei Irie
Toshiba Corporation
Power and Industrial Systems R&D Center{yuka.kohno, osamu1.yamaguchi, toshio4.sato, bunpei.irie}@toshiba.co.jp

information is consistent among different range data,
the occluded area differs due to different views.
Hence some surface areas in one data may have nocorresponding area in another data.
Wahl et al. introduced "surflet-pair-relation
histogram" representing a whole shape data [1]. It iscapable in classification of complete 3D shape model,
but is not suitable for incomplete singe-sided data. To
deal with such data, some methods have been
proposed such as representing shape data by local
shape features. Li et al. classified shape data bycomparing local surface descriptors using pyramid
matching [2][3]. Knopp et al. detected and describedlocal patches by 3D SURF, and classified shape databy voting approach [4]. For alignments of shape data,
Gelfand et al. presents an algorithm to pick small
number of potentially corresponding feature points
using uniqueness of descriptors [5]. Chen et al.
introduced local surface descriptor for object
recognition, using their correspondence to vote forcandidate models [6]. Their methods use small
number of potential correspondence, which requires
accurate local patch descriptors. However, singlesided data with loss of shape information in different
occlusion parts tends to show different behaviors incorresponding points.
Instead of using small number of feature points,
Shan et al. and Drost et al. used two-point pairfeatures to estimate object pose [7][8]. Their methods
perform well in matching shape data in same size, butlose scale invariance as they use absolute distances.
We also use feature points for the alignment, but
use combinations of potentially corresponding pairs of
three feature points, or pairs of triplets. Our method
obtains the alignment of single-sided shape data takenfrom different viewpoints, with loss of surface
information in different parts, and including objects indifferent sizes. We use hash table in making the pairs
to avoid combinatorial explosion of two triplets,
which contributes in process time reduction. To keep

Abstract
This paper presents a method to automaticallyalign a pose of 3D shape data to fit another shapedata taken from different viewpoints. One of the
difficult issues is to handle shape data which havesurface information in different sides due to thedifference in viewpoints, and to deal with objects indifferent scale. We detect local feature points on thetwo shape data, make potentially corresponding pairsof three feature points, calculate transformation
parameters to align the three points, and get optimalalignment parameters by the voting of parameters
obtained from the pairs of three points. We used hashtable to avoid combinatorial explosion in making thepairs, and used geometric invariants for its key which
are calculated from the positions of the points to keep
the scale invariance. The method was evaluated withsome public data and a set of laser-scanned data, andproved to be effective in alignment of shape data in
different angles or scales.

1. Introduction
3D shape data, such as range data and mesh data,
help to achieve higher performance of automatic
object detection, segmentation, and recognition
compared to independent use the conventional 2D
image. For the efficient use of 3D shape data, wedeveloped a method to automatically align two shapedata taken from different viewpoints. Our goal is tofind transformation parameters, composed ofrotation, translation, and scaling, which make thesurface of an object in one data overlap with thesurface of the same object in another data.
One of the difficulties in dealing with 3D shapedata taken from different viewpoints is handling lossof surface information in occluded surface or theback of objects. Although the visible surface120

points are detected at the local maximum of Mesh
DOG in both the scale space and the neighboring
points on the mesh surface. Then, for each featurepoint, a local coordinate system is defined, anddescriptor called “MeshHOG” is calculated which arehistograms of curvature gradient plot on the local
coordinate system. Figure 2 shows an example ofcurvature value and the detected feature points.

scale invariance, and to be able to handle objects indifferent sizes, we use as the key for the hashingangles and ratios of distance which are defined by thethree points, and are invariant under rotation,translation, and scaling transformation.

2. Proposed approach
In this section, we describe the overview of ourmethod. First we get two mesh data as inputs, target
data and query data. They are converted from range
data captured by stereo camera, range finder, or any
other device to capture depth data. To obtain thetransformation parameters which align the pose ofquery data to overlap with target data, we go throughthe process shown in figure 1.
Target data (input)

(a)
(b)
(c)
Fig.2 (a) Original object. (b) The curvature valueon the surface with light colored area representing
large value. (c) Detected feature points.

Query data (input)

2.2 Making of hash table (step 2)
Using the position and descriptor information offeature points, we make pairs of triplets and calculate
their transformation parameters.
To avoid
combinatorial explosion of two triplets, we use hashtable introduced in 2D image matching by Yamaguchi
et al. [10]. As the key, the hash table uses angles and ratios of distance R=a/b of two line segments, as
shown in figure 3, which are invariant under thesimilarity transformation.
In making of hash table, all triplets in target data
are added to hash table according to their key. Each
entry contains information about the three points(Pi, Pj, Pk) including their position (pi, pj, pk), normal
vectors (ni, nj, nk), and descriptors (Di, Dj, Dk).

1. Detect feature points from input data and computedescriptor at the feature points.
2. Make hash table and add all
triplets in target data.
3. Pick a triplet in query data, search in the hash tableto make a pair with a triplet in target data
4. Test if thepair matches, according to geometricconsistency and descriptor similarities.
Does the triplet pair match?

NOYES
5. Compute transformation parameters to make thetriplets of query data overlap with that of target data.

P1

target data

6. Vote for the bins in the parameter spacecorresponding to the calculated parameters.

bP5

7. Is the preset number of tripletsin query data processed ?

P0YES
8. Pick bins in parameter space with number of votes
being local maximum, take top N of them, and getparameters corresponding to the bins as output.

a

Fig.1 Flowchart of our method

P3

P2 ’

add

P0bbsearchp0’, p1’, p2’,n0’, n1’, n2’,
R=a/b D0’, D1’, D2’

aP2

P1 ’

aP0 ’


P1

bN sets of transformation parameters (output)

query dataaP3NO



p1 , p3 , p5 ,n1 , n3 , n5 ,D1, D3, D5
Hash table

P4

p0 , p3 , p4 ,n0 , n3 , n4 ,D0, D3, D4

p0, p1, p2,n0, n1, n2,D0, D1, D2

test match䎆Fig.3 Matching of triplets of points using hash table

2.1 Feature point detection (step 1)
For feature point detection and the computation ofdescriptors on mesh data, we used a method proposedby Zaharescu et al. [9]. Their method takes as an
input the curvature value on every point on mesh data.
The curvature value is then smoothed in various scales
to make difference of Gaussian images defined onmesh data, which they call “Mesh DOG”. Feature

2.3 Matching of triplets using hash table (step 3-5)
A triplet in query data is then picked to search fortriplets in target data at the corresponding key in hashtable. When the hit occurs, the matching of the pair oftriplets is tested, according to the similarity of121

corresponding feature point descriptors, and thesimilarity of corresponding inner products of two
normal vectors within a triplet. If the pair of triplets
matches, rotation, translation, and scale parameters arecomputed which make the total distance between thecorresponding points smallest.

together all thetransformations.

tzgetcandidate

3.1 Experiment with laser-scanned data
We tested our method using shape data of fiveobjects. The aim of the experiment is to evaluate thealignment of two shape data in different viewpoints.
The data are scanned by Minolta laser rangefinder
VIVID700, and consist of one of five objects in two
viewpoints, as shown in figure 5. Each object isscanned 5 times with its movable parts located indifferent positions to test the alignment of partiallymatching data. We made 125 trials for the experiment,each of them having two scan data of the same object,and in different viewpoints. The data contains
background noise, shape cut off at the edge of scanarea, noise caused by reflection, repeated shapepattern, and are very challenging.
We test our method with various numbers offeature points, 25, 50, and 75. The results wereevaluated by the cumulative success rate in top N
candidates and the execution time of matching process.
The criteria for the success is the error against groundtruth data being below 5mm in translation and 10
degrees in rotation, expected to be a good initial posefor iterative closest point (ICP) refinement. The
execution time of matching process was measured
with Intel® Core™ 2 CPU (2.66GHz) with 2GB
RAM and does not include the time for otherprocesses such as feature detection. The results areshown in table 1. The use of hash table reduces theprocess time dramatically, though the increase rate
becomes larger as the number of feature points
increases. The success rate was sufficient withenough number of feature points and candidates,
though there is a tradeoff between process time andthe number of feature points.
For comparison, we also tested alignment by ICPusing all surface points, with N initial poses. The firstinitial pose is the original laser-scanned data, and therest were set randomly within -30 to 30 degrees inangle and within half the length of object size intranslation. The result is shown in table 2. The
success rate is roughly equal to that of our methods
with 50 points, improving as the number of randomly
set initial pose increases. But the process time also
increases, in contrast to our method whose process
time does not depend on the number of candidates.
The success rate was worse for ICP with completely
random initial pose, due to the property of the method
which depends heavily on the initial pose.

Vote for translation
ty Parameter space& scale parameter(tx,ty,tz, s)SecondPhase

local max

to

3. Experiments(rx,ry,rz, tx,ty,tz, s) :b
Rotation, translation, andaab
scale parameters computedfrom three points pairs
Vote for rotation parameter
FirstPhaserx Parameter space(tx2,ty2,tz2,s2)(rx,ry,rz)(tx6,ty6,tz6,s6)
List oflocal max(tx7,ty7,tz7,s7)translation& scale(tx,ty,tz,s)11
11rz
parameters(tx3,ty3,tz3,s3)
attached
local max
(tx5,ty5,tz5,s5)
ryto the bins
(tx9,ty9,tz9,s9)
rotation parameters(tx12,ty12,tz12,s12)

sparameters

local maxtx
Translation and scale parameters
Candidate transformations (rotation, translation, and scale)Fig.4 Estimation of pose parameters by voting
2.4 Acquisition of transformation (step 6-8)
The computed parameters are then voted for in thecorresponding bins of the parameter space. Theseprocesses, including steps 3-6, are done for preset
number of three points in mesh data 2. After thevoting process is finished, we pick the bins with thenumber of votes being the local maximum and top N
within them, to get the corresponding parameters.
In actual implementation, it is not realistic toallocate parameter space of 7-dimensional array,
which would be more than 11TB on the computer
memory with our design for range and step size.
Instead, we divide the process into two phases,
estimation of rotation parameters which requires
750KB, and estimation of translation and scaleparameters which requires 5MB. Figure 4 shows theoverall process of parameter acquisition. In the firstphase, we vote for the rotation parameters and make alist of translation and scale parameters for each bin.
Then for the bins in the rotation parameter space with
top N local maximum votes, we get the list oftranslation and scale parameters and vote for them toget the parameters with the most votes. Finally we put

122shows the method is valid for the alignment of facedata in different angles.

4. Conclusion
In this paper, we have introduced a method for 3D
shape data alignment.
By using potentiallycorresponding pairs of three feature points, ourmethod is applicable to single-sided shape data
including objects of different sizes.
To avoid
combinatorial explosion, we used hash table forpicking the pairs of triplets. By using angle anddistance ratio as the key, the matching is tolerant toscale variability of objects.
The result of the experiment shows that our method
is effective with enough number of feature points, andis superior to naive ICP method with initial pose set
randomly. The alignment algorithm is expected to be
used for object recognition, identification of shapedata, understandings of object structures, or 3Dmodeling, and to contribute for application such as
robot vision, facility inspection, and biometrics.

Fig.5 (Top) Five objects used for the experiment.
(Middle) Two viewpoints. (Bottom) Movableparts and their range of movement.
Table 1. Cumulative success rate of top N candidates
#ofFP
25
50
75

N=1[%]
30.4
62.4
79.2

N=3[%]
48.8
80.0
89.6

N=5[%]
53.6
84.8
90.4

N=10[%]
59.2
91.2
96.8

time w/hashing
0.72s
1.1s
6.8s

time w/ohashing
21s
23min> 4hrs

Table 2. Result of ICP method with N initial pose.
ICP
time

N=168.8%
2.72s

N=376.8%
5.31s

N=580.8%
7.96s

N=1091.2%
15.2s

References[1] E. Wahl, et. al: "A statistical 3d-shape representation for
rapid classification," In 3-D Digital Imaging and Modeling,
2003.
[2] X. Li and I. Guskov: "Multi-scale Features for
Approximate Alignment of Point-based Surfaces,"
Eurographics Symposium on Geometry Processing, 2005.
[3] X. Li and I. Guskov: "3D object recognition from range
images using pyramid matching," Proc.ICCV, 2007.
[4] J. Knopp, et. al.: "Hough Transform and 3D SURF forrobust three dimensional classification, Proc. ECCV, 2010.
[5] N. Gelfand, et. al.: "Robust global registration," In
Proceedings of the third Eurographics symposium onGeometry processing, p. 197. 2005.
[6] H. Chen and B. Bhanu: "3D free-form object recognition
in range images using local surface patches," Pattern
Recognition Letters, vol.28, no.10, pp.1252-1262, 2007.
[7] Y. Shan, et. al.: "Linear model hashing and batch ransac
for rapid and accurate object recognition." Proc.CVPR, 2004.
[8] B. Drost, et. al: "Match Locally: Efficient and Robust 3D
Object Recognition, Proc. CVPR, 2010.
[9] A. Zaharescu, et. al.: "Surface Feature Detection andDescription with Applications to Mesh Matching," Proc.
CVPR, 2009.
[10] O. Yamaguchi and K. Fukui: "Pattern Hashing - Object
recognition based on a distributed local appearance model,"Proc. ICIP, vol.3, pp.329-332, 2002.
[11] G. Hetzel, et. al.: "3D Object Recognition from Range
Images using Local Feature Histograms," Proc. CVPR, 2001.
[12] A.B. Morenom et. al.: "A 3D Face Database," Proc.
2nd COST Workshop on Biometrics on the Internet:Fundamentals, Advances and Applications, pp. 77-82, 2004.
Intel, and Core are trademarks of Intel Corporation.

3.2 Experiment with public data
We evaluated our method using public data. The
results are shown in Figure 6. We picked two Bunny
data with different viewpoints from Stuttgart Range
Image Database [11] and re-sampled to make them in
different scale. The query data is aligned successfullyto fit target data in different view and scale. Anotherdata we used is face data looking down and looking
up, obtained from GabavDB face database [12]. Theresult(a) Target data (b)Query data (c) View1(d) Vew2(e) Target data (f)Query data(h) View2(g) View1

Fig. 6 (a),(e) Target data and (b),(f) Query datawith feature points. (c),(g) The result of posealignment, target data drawn in black mesh, andquery data in gray surface. (d),(h) The result seenfrom another direction.

123