AUTOMATIC CORRESPONDENCE AND GLOBAL REGISTRATION OF RANGE IMAGES FOR
3D MODELING
Ajmal S. Mian, Mohammed Bennamoun and Robyn A. Owens
School of Computer Science and Software Engineering
The University of Western Australia
35 Stirling Highway, Crawley, WA 6009, Australia
{ajmal, bennamou, robyn}@csse.uwa.edu.au
Working Group III/2
KEY WORDS: Three-dimensional, Modeling, Representation, Registration, Reconstruction.
ABSTRACT
A free-form object must be acquired from multiple viewpoints to make its complete 3D model. These views are then
registered by establishing correspondence between them. Pair wise registration of the views may result in a 3D model
with large seams due to the accumulation of registration errors. Global registration is therefore performed to register
the views simultaneously, distributing the registration errors evenly over the 3D model. In this paper we present an
automatic 3D modeling approach using our automatic correspondence algorithm combined with global registration. Our
algorithm takes an ordered set of views of an object, automatically finds pair wise correspondences between the views
and finally, registers the views with global registration. To show the accuracy of our technique, we perform a comparative
analysis of the pairwise registration, resulting from our automatic correspondence technique alone, and the resultant global
registration.
1 INTRODUCTION
A single view of a free-form object is generally not suffi-
cient to form its complete 3D model due to self occlusions.
Multiple views must be acquired to cover the entire sur-
face of the object. Correspondences are then established
between these views and based on these correspondences,
a rigid transformation is derived to register the views in
a common coordinate basis. There are two approaches to
registration. One is to register the views locally perform-
ing pair wise registration. In this approach the registra-
tion error may accumulate, resulting in a significant mis-
alignment between views that are not consecutive in the
pair wise correspondence sequence. The second approach
takes the correspondences and registers the views simulta-
neously distributing the registration error evenly over the
entire 3D model.
Various techniques have been proposed for the identifi-
cation of correspondences between two views of an ob-
ject. Examples include matching oriented points (Johnson
and Hebert, 1997), geometric histogram matching (Ash-
brook et al., 1998), RANSAC-based DARCES (Chen et al.,
1991), SAI matching (Higuchi et al., 1994), Roth's tech-
nique (Roth, 1999), 3-tuple matching (Chua and Jarvis,
1996), bitangent curve matching (Wyngaerd et al., 1999),
Iterative Closest Point (ICP) (Besl and McKay, 1992), Chen
and Medioni's algorithm (Chen and Medioni, 1991) and
the Rangarajan ef al. algorithm (Rangarajan et al., 1999).
However, these techniques are based on various unrealis-
tic assumptions and are not fully automatic. Moreover,
these techniques have been used for pairwise correspon-
dence and registration only. To the best of our knowledge
none of these techniques has been used in conjunction with
a global registration algorithm. On the other hand, multi-
view global registration techniques such as the Williams
and Bennamoun's technique (Williams and Bennamoun,
118
2001) and Benjemma and Schmitt's technique (Benjemma
and Schmitt, 1997) assume that correspondences have al-
ready been identified or the views are approximately reg-
istered. In this paper, we present an automatic 3D mod-
eling approach using our automatic pairwise correspon-
dence algorithm combined with global registration. Our
algorithm takes an ordered set of views of an object and
makes its complete 3D model. The algorithm proceeds
as follows. First, pairwise correspondences are identified
using our automatic correspondence algorithm. Second,
the views are registered locally (pair wise) and correspon-
dences are identified between all the views based on the
nearest neighbours. Finally, these correspondences are fed
to a global registration technique (Williams and Bennamoun,
2001) which registers the views globally. To estimate the
accuracy of our technique we perform a comparative anal-
ysis of the registration resulting from our pairwise corre-
spondence technique only and the resultant global regis-
tration.
The rest of this paper is organized as follows. Section 2
gives a brief description of our tensor-based automatic cor-
respondence algorithm. Section 3 explains the details of
our 3D modeling procedure. In Section 4 we report our 3D
modeling results. Section 5 contains an analysis of the 3D
models resulting from our technique. Finally, in Section 6
we present our conclusions.
2 AUTOMATIC CORRESPONDENCE
In this section, we shall briefly describe our automatic cor-
respondence algorithm. For details of the algorithm the
reader is referred to (Mian et al., 2004). Our correspon-
dence algorithm converts the views into a tensor-based rep-
resentation. The representation algorithm proceeds as fol-
lows. First, the 2.5D views (in the form of a cloud of
points) are converted into triangular meshes and normals
International Archiv,
Het ab AR REE,
are calculated for
all possible pairs «
apart are selected
with its normals, i
the middle of the li
normals defines tl
mals define the x-
with x-axis defines
to define a 10 x 1(
coordinate basis. '
multiple of the mes
case). The area ol
weighted normals
lated (using Suthe
in a 4th order tense
To find corresponc
a tensor is selectei
with all the tensor:
are only matched
greater than 0.6, w
of the occupied bir
the occupied bins
as follows. The cc
is calculated in the
coefficient is highe
namically), one of
2 tensor is transfor
the transformation
Here R and t are tl
respectively. By ar
basis of view 1 and
are the vectors of «
respectively.
If the distance bet
responding point (c
to one fourth of th
transformed using
points of view 1 ar
(set equal to the me
spondences. If this
half the total numl
transformation is a
and McKay, 1992)
3 GLOBAL RE(
Our3D modeling a
an object and finds
ping views accordi
2. The overlap info
der of the views o
