Optimal Registration of Object Views Using Range Data.
AbstractThis paper deals with robust registration of object views in the presence of uncertainties and noise in depth data. Errors in registration of multiple views of a 3D object severely affect view integration during automatic construction of object models. We derive a minimum variance estimator (MVE) for computing the view transformation parameters accurately from range data of two views of a 3D object. The results of our experiments show that view transformation estimates obtained using MVE are significantly more accurate than those computed with an unweighted error criterion for registration.
Introduction
An important issue in the design of 3D object recognition systems is building models of physical
objects. Object models are extensively used for synthesizing and predicting object appearances from
desired viewpoints and also for recognizing them in many applications such as robot navigation and
industrial inspection. It becomes necessary on many occasions to construct models from multiple
measurements of 3D objects, especially when a precise geometric model such as a CAD description
is not available and cannot be easily obtained. This need is felt particularly with 3D free-form
objects, such as sculptures and human faces that may not possess simple analytical shapes for
representation. With growing interest in creating virtual museums and virtual reality functions
such as walk throughs, creating computer images corresponding to arbitrary views of 3D scenes
and objects remains a challenge.
Automatic construction of 3D object models typically involves three steps: (i) data acquisition
from multiple viewpoints, (ii) registration of views, and (iii) integration. Data acquisition involves
obtaining either intensity or depth data of multiple views of an object. Integration of multiple views
is dependent on the representation chosen for the model and requires knowledge of the transformation
relating the data obtained from different viewpoints. The intermediate step, registration,
is also known as the correspondence problem [1] and its goal is to find the transformations that
relate the views. Inaccurate registration leads to greater difficulty in seamlessly integrating the
data. It ultimately affects surface classification since surface patches from different views may be
erroneously merged, resulting in holes and discontinuities in the merged surface. For smooth merging
of data, accurate estimates of transformations are vital. In this paper we focus on the issue of
pairwise registration of noisy range images of an object obtained from multiple viewpoints using a
laser range scanner.
We derive a minimum variance estimator to compute the transformation parameters accurately
from range data. We investigate the effect of surface measurement noise on the registration of a pair
of views and propose a new method that improves upon the approach of Chen and Medioni [1]. We
have not seen any work that reports to date, establishing the dependencies between the orientation
of a surface, noise in the sensed surface data, and the accuracy of surface normal estimation and
how these dependencies can affect the estimation of 3D transformation parameters that relate a
pair of object views. We present a detailed analysis of this "orientation effect" with geometrical
arguments and experimental results.
Previous Work
There have been several research efforts directed at solving the registration problem. While the
first category of approaches relies on precisely calibrated data acquisition device to determine the
transformations that relate the views, the second kind involves techniques to estimate the transformations
from the data directly. The calibration-based techniques are inadequate for constructing
a complete description of complex shaped objects as views are restricted to rotations or to some
known viewpoints only and therefore, the object surface geometry cannot be exploited in the selection
of vantage views to obtain measurements.
With the second kind, inter-image correspondence has been established by matching the data
or the surface features derived from the data [2]. The accuracy of the feature detection method
employed determines the accuracy of feature correspondences. Potmesil [3] matched multiple range
views using a heuristic search in the view transformation space. Though quite general, this technique
involves searching a huge parameter space, and even with good heuristics, it may be computationally
very expensive. Chen and Medioni avoid the search by assuming an initial approximate
transformation for the registration, which is improved with an iterative algorithm [1] that minimizes
the distance from points in a view to tangential planes at corresponding points in other views. Besl
and McKay [4], Turk and Levoy [5], Zhang [6] employ variants of the iterated closest-point algo-
rithm. Blais and Levine [7] propose a reverse calibration of the range-finder to determine the point
correspondences between the views directly and use stochastic search to estimate the transforma-
tion. These approaches, however, do not take into account the presence of noise or inaccuracies in
the data and its effect on the estimated view-transformation. Our registration technique also uses a
distance minimization algorithm to register a pair of views, but we do not impose the requirement
that one surface has to be strictly a subset of the other. While our approach studies in detail
the effect of noise on the objective function [1] that is being minimized and proposes an improved
function to register a pair of views, Bergevin et al. [8, 9] propose to register all views simultaneously
to avoid error accumulation due to sequential registration. Haralick et al. [10] have also showed
that a weighted least-squares technique is robust under noisy conditions under various scenarios
such as 2D-2D, 3D-3D image registration.
3 A Non-Optimal Algorithm for Registration
Two views, P and Q of a surface are said to be registered when any pair of points, p and q from
the two views representing the same object surface point can be related to each other by a single
rigid 3D spatial transformation T , so that 8p 2
obtained by applying the transformation T to p, and T is expressed in homogeneous coordinates
as a function of three rotation angles, ff, fi and fl about the x, y and z axes respectively, and three
translation parameters, t x , t y and t z . The terms "view" and "image" are used interchangeably in
this paper. The approach of [1] is based on the assumption that an approximate transformation
between two views is already known and the goal is to refine the initial estimate to obtain more
accurate global registration. The following objective function was used to minimize the distances
from surface points in one view to another iteratively:
where T k is the 3D transformation applied to a control point at the kth iteration,
0g is the line normal to P at
is the intersection point of
surface Q with the transformed line T k l i , n k
is the normal to Q at q k
is the tangent plane to Q at q k
i and d s is the signed distance from a point to a plane as given
in Eq. (2). Note that '\Delta' stands for the scalar product and `\Theta' for the vector product. Figure 1
illustrates the distance measure d s between surfaces P and Q.
This registration algorithm thus finds a T that minimizes e k , using a least squares method
iteratively. The tangent plane S k
serves as a local linear approximation to the surface Q at a point.
The intersection point q k
i is an approximation to the actual corresponding point q i that is unknown
at each iteration k. An initial T 0 that approximately registers the two views is used to start the
iterative process. The signed distance d s , from a transformed point T to a tangential
(b)
(a)

Figure

1: Point-to-plane distance: (a) Surfaces P and Q before the transformation T k at iteration
k is applied; (b) distance from the point p i to the tangent plane S k
i of Q.
define the transformed point and the tangential
plane respectively. Note that (x; is the transpose of the vector (x; z). By minimizing
the distance from a point to a plane, only the direction in which the distance can be reduced is
constrained. The convergence of the process can be tested by verifying that the difference between
the errors e k at any two consecutive iterations is less than a pre-specified threshold. The line-surface
intersection given by the intersection of the normal line l i and Q is found using an iterative search
near the neighborhood of prospective intersection points.
4 Registration and Surface Error Modeling
Range data are often corrupted by measurement errors and sometimes lack of data. The errors in
surface measurements of an object include scanner errors, camera distortion, and spatial quanti-
zation, and the missing data can be due to self-occlusion or sensor shadows. Due to noise, it is
generally impossible to obtain a solution for a rigid transformation that fits two sets of noisy three-dimensional
points exactly. The least-squares solution in [1] is non-optimal as it does not handle the
errors in z measurements and it treats all surface measurements with different reliabilities equally.
Our objective is to derive a transformation that globally registers the noisy data in some optimal
sense. With range sensors that provide measurements in the form of a graph surface z = f(x; y), it
is assumed that the error is present along the z axis only, as the x and y measurements are usually
laid out in a grid. There are different uncertainties along different surface orientations and they
need to be handled appropriately during view registration. Furthermore, the measurement error is
not uniformly distributed over the entire image. The error may depend on the position of a point,
relative to the object surface. A measurement error model dealing with the sensor's viewpoint has
been previously proposed [11] for surface reconstruction where the emphasis was to recover straight
line segments from noisy single scan 3D surface profiles.
In this paper, we show that the noise in z values affects the estimation of the tangential plane
parameters differently depending on how the surface is oriented. Since the estimated tangential
plane parameters play a crucial role in determining the distance d s which is being minimized to
estimate T , we study the effect of noise on the estimation of the parameters of the plane fitted
and on the minimization of d s . The error in the iterative estimation of T is a combined result
of errors in each control point (x; z) T from view 1 and errors in fitting tangential planes at the
corresponding control points in view 2.
4.1 Fitting Planes to Surface Data with Noise
Surface normal to the plane
uncertainty region in Z
Horizontal plane
Surface normal to the plane
uncertainty region in Z
Effective uncertainty region affecting the normal
Inclined plane
(a) (b)

Figure

2: Effect of noise in z measurements on the fitted normal: (a) when the plane is horizontal;
(b) when it is inclined. The double-headed arrows indicate the uncertainty in depth measurements.

Figure

2 illustrates the effect of noise in the values of z on the estimated plane parameters. For
the horizontal plane shown in Figure 2(a), an error in z (the uncertainty region around z) directly
affects the estimated surface normal. In the case of an inclined plane, the effect of errors in z on
the surface normal to the plane is much less pronounced as shown in Figure 2(b). Here, even if
the error in z is large, only its projected error along the normal to the plane affects the normal
estimation. This projected error becomes smaller than the actual error in z as the normal becomes
more and more inclined with respect to the vertical axis. Therefore, our hypothesis is that as the
angle between the vertical (Z) axis and the normal to the plane increases, the difference between
the fitted plane parameters and the actual plane parameters should decrease.
We carried out simulations to study the actual effect of the noise in the z measurements on
estimating the plane parameters and to verify our hypothesis. The conventional method for fitting
planes to a set of 3D points uses a linear least squares algorithm. This linear regression method
implicitly assumes that two of the three coordinates are measured without errors. However, it
is possible that in general, surface points can have errors in all three coordinates, and surfaces
can be in any orientation. Hence, we used a classical eigenvector method (principal components
analysis) [12] that allows us to extract all linear dependencies.
Let the plane equation be Ax +By
set of surface measurements used in fitting a plane at a point on a surface. Let
and be the vector containing the plane parameters. We solve for the vector h such
that kAhk is minimized. The solution of h is a unit eigenvector of A T A associated with the smallest
eigenvalue. We renormalize h such that (A; B; C) T is the unit normal to the fitted plane and D is
the distance of the plane from the origin of the coordinate system. This planar fit minimizes the
sum of the squared perpendicular distances between the data points and the fitted plane and is
independent of the choice of the coordinate frame.
In our computer simulations, we used synthetic planar patches as test surfaces. The simulation
data consisted of surface measurements from planar surfaces at various orientations with respect to
the vertical axis. Independent and identically distributed (i.i.d.) Gaussian and uniform noise with
zero mean and different variances were added to the z values of the synthetic planar data. The
standard deviation of the noise used was in the range 0.001-0.005 in. as this realistically models
the error in z introduced by a Technical Arts 100X range scanner [13] that was employed to obtain
the range data for our experiments. The planar parameters were estimated using the eigenvector
method at different surface points with a neighborhood of size 5 \Theta 5. The error E fit in fitting the
plane was defined as the norm of the difference between the actual normal to the plane and the
normal of the fitted plane estimated with the eigenvector method. Figure 3(a) shows the plot of
versus the orientation (with respect to the vertical axis) of the normal to the simulated plane
at different noise variances. The plot shows E fit averaged over 1,000 trials at each orientation.
It can be seen from Figure 3(a) that in accordance with our hypothesis, the error in fitting a
plane decreases with an increase in the angle between the vertical axis and the normal to the plane.
When the plane is nearly horizontal (i.e., the angle is small), the error in z entirely contributes to
fit as indicated by Figure 2(a). The error plots for varying amounts of variance were observed
Squared
difference
between
the
actual
and
estimated
normals
Angle between the normal to the plane and vertical axis
"std_dev_of_noise=0.0"
"std_dev_of_noise=0.001"
"std_dev_of_noise=0.002"
"std_dev_of_noise=0.003"
"std_dev_of_noise=0.004"
Squared
Difference
betweeb
the
estimated
and
actual
normals
Angle between the normal to the plane and vertical axis
"std_dev_of_noise=0.0"
"std_dev_of_noise=0.001"
"std_dev_of_noise=0.002"
"std_dev_of_noise=0.003"
"std_dev_of_noise=0.004"
"std_dev_of_noise=0.005"
(a) (b)

Figure

3: Effect of i.i.d. Gaussian noise in z measurements on the plane: (a) estimated using
eigenvector approach; (b) estimated using linear regression.
to have the same behavior with orientation as shown in Figure 3(a). Similar curves were obtained
with a uniform noise model also [14]. These simulations confirm our hypothesis about the effect of
noise in z on the fitted plane parameters as the surface orientation changes.
We repeated the simulations using the linear regression method to fit planes to surface data.
We refer the reader to [14] for details. Figure 3(b) shows the error E fit between the fitted and
actual normals to the plane at various surface orientations when i.i.d. Gaussian noise was added
to the z values. Our hypothesis is well supported by this error plot also.
4.2 Proposed Optimal Registration Algorithm
Since the estimated tangential plane parameters are affected by the noise in z measurements, any
inaccuracies in the estimates in turn, influence the accuracy of the estimates of d s , thus affecting
the error function being minimized during the registration. Further, errors in z themselves affect d s
estimates (see Eq. 2). Therefore, we characterize the error in the estimates of d s by modeling the
uncertainties associated with them using weights. Our approach is inspired by the Gauss-Markov
theorem [15] which states that an unbiased linear minimum variance estimator of a parameter
vector m when is the one that minimizes (y
y
is a random noise vector with zero mean and covariance matrix \Gamma y . Based on this theorem, we
formulate an optimal error function for registration of two object views as
ds
ds is the estimated variance of the distance d s . When the reliability of a z value is low,
the variance of the distance oe 2
ds is large and the contribution of d s to the error function is small,
and when the reliability of the z measurement is high, oe 2
ds is small, and the contribution of d s is
large; d s with a minimum variance affects the error function more. One of the advantages of this
minimum variance criterion is that we do not need the exact noise distribution. What we require
only is that the noise distribution be well-behaved and have short tails. In our simulations, we
employ both Gaussian and uniform noise distributions to illustrate the effectiveness of our method.
We need to know only the second-order statistics of the noise distribution, which in practice can
often be estimated.
4.3 Estimation of the Variance oeds
We need to estimate oe 2
ds to model the reliability of the computed d s at each control point, which
can then be used in our optimal error function in Eq. (4). Let the set of all the surface points be
denoted by P and the errors in the measurements of these points be denoted by a random vector ffl.
The error e ds in the distance computed is due to the error in the estimated plane parameters and
the error in the z measurement, and therefore is a function of P and ffl. Since we do not know ffl, if
we can estimate the standard deviation of e ds (with ffl as a random vector) from the noise-corrupted
surface measurements P , we can use it in Eq. (4).
4.3.1 Estimation of oe 2
ds Based on Perturbation Analysis
Perturbation analysis is a general method for analyzing the effect of noise in data on the eigenvectors
obtained from the data. It is general in the sense that errors in x, y and z can all be handled. This
analysis is also related to the general eigenvector method that we studied for plane estimation. The
analysis for estimating oe 2
ds is simpler if we use linear regression method to do plane fitting [14].
Since we fit a plane with the eigenvector method that uses the symmetric matrix
computed from the (x; measurements in the neighborhood of a surface point, we need to
analyze how a small perturbation in the matrix C caused by the noise in the measurements can
affect the eigenvectors. Recall that these eigenvectors determine the plane parameters (A; B; C; D) T
which in turn determine the distance d s . We assume that the noise in the measurements has zero
mean and some variance and that the latter can be estimated empirically. The correlation in noise
at different points is assumed to be negligible. Estimation of correlation in noise is very difficult
but even if we estimate it, its impact may turn out to be insignificant. We estimate the standard
deviation of errors in the plane parameters and in d s on the basis of the first-order perturbations,
i.e., we estimate the "linear terms" of the errors.
Before we proceed, we discuss some of the notational conventions that are used: I m is an m \Theta m
identity matrix; diag(a; b) is a 2 \Theta 2 diagonal matrix with a and b as its diagonal elements. Given
a noise-free matrix A, its noise-matrix is denoted by \Delta A and the noise-corrupted version of A is
denoted by . The vector ffi is used to indicate the noise vector, We
use \Gamma with a corresponding subscript to specify the covariance matrix of the noise vector/matrix.
For a given matrix vector A can be associated with it as
A thus consists of the column vectors of A that are lined up together.
As proved in [16], if C is a symmetrical matrix formed from the measurements and h
is the parameter vector (A; B; C; D) T given by the eigenvector of C associated with the smallest
eigenvalue, say - then the first-order perturbation in the parameter vector h is given by
where
and H is an orthonormal matrix such that
A is a 4 \Theta 4 noise or perturbation matrix associated with A T A. If \Delta A T A can be estimated, then
the perturbation ffi h in h can be estimated by a first-order approximation as in Eq. (5).
We estimate \Delta A T A from the perturbation in the surface measurements. We assume for the sake
of simplicity of analysis that only the z component of a surface measurement
errors, with this general model. This analysis is easily and directly extended to include errors in x
and y if their noise variances are known.
Let z i have additive errors ffi z i
We then get
If the errors in z at different points on the surface have the same variance oe 2 , we get the covariance
matrix
where
Now, consider the error in h. As stated before, we have
In the above equation, we have rewritten the matrix \Delta A T A as a vector ffi A T A and moved the perturbation
to the extreme right of the expression. Then the perturbation of the eigenvector is the
linear transformation (by matrix G h ) of the perturbation vector ffi A T A . Since we have \Gamma A T
A ),
we need to relate ffi A T A to ffi A T . Using a first-order approximation [16], we get
A A: (12)
Letting A
where G A T A is easily determined from the equation G A T are
matrices with 4 \Theta n submatrices F ij and G ij a ji I 4 , and G ij is a 4 \Theta 4 matrix
with the ith column being the column vector A j and all other columns being zero. Thus, we get
Then the covariance matrix of h is given by
The distance d s is affected by the errors in the estimation of the plane parameters,
and the z measurement in Therefore, the error variance in d s is
ds
@ds
@A
@ds
@ds
@ds
@D
@ds
@z
\Theta [\Gamma hz
@ds
@A
@ds
@ds
@ds
@D
@ds
The covariance matrix \Gamma hz is given by
Once the variance of d s , oe 2
ds is estimated, we employ it in our optimal error function:
ds
4.3.2 Simulation Results

Figure

4(a) shows the plot of the actual standard deviation of the distance d s versus the orientation
of the plane with respect to the vertical axis. Note that the mean of d s is zero when the
Actual
standard
deviation
of
distance
d_s
Angle between the normal to the plane and vertical axis
"std_dev_of_noise=0.0"
"std_dev_of_noise=0.001"
"std_dev_of_noise=0.002"
"std_dev_of_noise=0.003"
"std_dev_of_noise=0.004"
Actual
standard
deviation
of
distance
d_s
Angle between the normal to the plane and vertical axis
"std_dev_of_noise=0.0"
"std_dev_of_noise=0.001"
"std_dev_of_noise=0.002"
"std_dev_of_noise=0.003"
"std_dev_of_noise=0.004"
Estimated
standard
deviation
of
distance
d_s
Angle between the normal to the plane and vertical axis
"std_dev_of_noise=0.0"
"std_dev_of_noise=0.001"
"std_dev_of_noise=0.002"
"std_dev_of_noise=0.003"
"std_dev_of_noise=0.004"
"std_dev_of_noise=0.005"
(a) (b)

Figure

4: Standard deviation of d s versus the planar orientation with a Gaussian noise model:
(a) actual oe ds ; (b) estimated oe ds using the perturbation analysis.
points are in complete registration and when there is no noise. We generated two views of synthetic
planar surfaces with the view transformation between them being an identity transformation. We
experimented with the planar patches at various orientations. We added uncorrelated Gaussian
noise independently to the two views. Then we estimated the distance d s at different control points
using Eq. (2) and computed its standard deviation. The plot shows the values averaged over 1,000
trials. As indicated by our hypothesis, the actual standard deviation of d s decreases as the planar
orientation goes from being horizontal to vertical. As the variance of the added Gaussian noise
to the z measurements increases, oe ds also increases. Similar results were obtained when we added
uniform noise to the data [14].
We compared the actual variance with the estimated variance of the distance (Eq. (16)) in
order to verify whether our modeling of errors in z values at various surface orientations is correct.
We computed the estimated variance of the distance d s using our error model using Eq. (16)
with the same experimental setup as described above. Figure 4(b) illustrates the behavior of
the estimated standard deviation of d s as the inclination of the plane (the surface orientation)
changes. A comparison of Figures 4(a) and 4(b) shows that both the actual and the estimated
standard deviation plots have similar behavior with varying planar orientation and their values are
proportional to the amount of noise added. This proves the correctness of our error model of z and
its effect on the distance d s . Simulation results, when we repeated the experiments to compute both
the actual and the estimated oe ds using the planar parameters estimated with the linear regression
method, were similar to those shown in Figure 4. This also demonstrates the important fact that
the method used for planar fitting does not bias our results.
5 View Registration Experiments
In this section we demonstrate the improvements in the estimation of view transformation parameters
on real range images using our MVE. We will henceforth refer to Chen and Medioni's
technique [1] as C-M method. We obtained range images of complex objects using a Technical Arts
laser range scanner. We performed uniform subsampling of the depth data to locate the control
points in view 1 that were to be used in the registration. From these subsampled points we chose a
fixed number of points that were present on smooth surface patches. The local smoothness of the
surface was verified using the value of residual standard deviation resulting from the least-squares
fitting of a plane in the neighborhood of a point. A good initial guess for the view transformation
was determined automatically when the range images contained the entire object surface and the
rotations of the object in the views were primarily in the plane. Our method is based on estimating
an approximate rotation and translation by aligning the major (principal) axes of the object
views [14].

Figures

5(a) and 5(c) depict the two major axes of the objects. We used this estimated
transformation as an initial guess for the iterative procedure in our experiments, so that no prior
knowledge of the sensor placement was needed. Experimental results show the effectiveness of our
method in refining such rough estimates. The same initial guess was used with the C-M method and
the proposed MVE. We employed Newton's method for minimizing the error function iteratively.
In order to measure the error in the estimated rotation parameters, we utilize an error measure
that does not depend on the actual rotation parameters. The relative error of rotation matrix R, ER
is defined [16] to be
R is an estimate of R. Since R, the geometric
sense of ER is the square root of the mean squared distance between the three unit vectors of the
rotated orthonormal frames. Since the frames are orthonormal,
3.
The error in translation, E t is defined as the square root of the sum of the squared differences
between the estimated and actual t x , t y and t z values.
5.1 Results

Figure

5 shows the range data of a cobra head and a Big-Y pipe. The figure renders depth as pseudo
intensity and points almost vertically oriented are shown darker. View 2 of the cobra head was
obtained by rotating the surface by 5 ffi about the X axis and 10 ffi about the Z axis. Table 1 shows
(a) (b) (c) (d)

Figure

5: Range images and their principal axes: (a) View 1 of a Cobra head; (b) View 2 of the
cobra head; (c) Big-Y pipe data generated from its CAD model; (d) View 2 of Big-Y pipe.
the values of ER and E t for the cobra views estimated using only as few as 25 control points. It can
be seen that the transformation parameters obtained with the MVE are closer to the ground truth
than those estimated using the unweighted objective function of C-M method. Even when more
control points (about 156) were used, the estimates using our method were closer to the ground
truth than those obtained with the C-M method [14].
We also show the performance of our method when the two viewpoints are substantially different
and the depth values are very noisy. Figure 5 shows two views of the Big-Y pipe generated from
the CAD model. The second view was generated by rotating the object about the Z axis by 45 ffi .
We also added Gaussian noise with mean zero and standard deviation of 0:5 mm to the z values of
the surfaces in view 2. Table 2 shows ER and E t computed with 154 control points. It can be seen
from these tables that the transformation matrix, especially the rotation matrix obtained with the
MVE is closer to the ground truth than that obtained using C-M method. The errors in translation
components of the final transformation estimates are mainly due to the approximate initial guess.
Parameters Actual C-M MVE
value method
Parameters Actual C-M MVE
value method

Table

1: Estimated transformation for Table 2: Estimated transformation for
the cobra views. the Big-Y views.
Our method refined these initial values to provide a final solution very close to the actual values.
Our method also handled large transformations between views robustly. With experiments on
range images of facial masks, we found that even when the depth data were quite noisy owing to
the roughness of the surface texture of the objects and also due to self-occlusion, more accurate
estimates of the transformation were obtained with the MVE. When the overlapping object surface
between the views is quite small, the number of control points available for registration tends to
be small and in such situations also the MVE has been found to have substantial improvement in
the accuracy of the transformation estimate. Note that measurement errors are random and we
minimize the expected error in the estimated solution. However, our method does not guarantee
that every component in the solution will have a smaller error in every single case.
We also used the MVE for refining the pose estimated using cosmos-based recognition system
for free-form objects [14]. The rotational component of the transformation of a test view
of Vase2 (View 1 shown in Figure 6(a)) relative to its best-matched model view (View 2 shown
in

Figure

was estimated using surface normals of corresponding surface patch-groups determined
by the recognition system. A total of 10 pairs of corresponding surface patch-groups was
used to estimate the average rotation axis and the angle of rotation. These rotation parameters
were used to compute the 3 \Theta 3
rotation matrix which was then used as an initial guess to register the model view (View 2) with
the test view (View 1) of Vase2 using the MVE. We note here that the computational procedure
for MVE was augmented using a verification mechanism for checking the validity of the control
points during its implementation [17]. We derived the results presented in this section using this
augmented procedure. Figures 6(c)-(g) show the iterative registration of the model view with the
scene view. It can be seen that the views are in complete registration with one another at the end
of seven iterations.

Figure

7 shows the registration of a model view with a scene view of Phone through several
iterations of the algorithm. The registration scheme converged with the lowest error value at the
(a) (b)
(c) (d) (e) (f) (g)

Figure

Pose estimation: (a) View1 of a vase; (b) view2; (c)-(f) model view registered with the
test view of Vase2 at the end of the first, third, fourth and fifth iterations; (g) registered views at
the convergence of the algorithm.
(a) (b)
(c) (d) (e) (f) (g)

Figure

7: Registration of views of Phone: (a) View 1; (b) view 2; (c)-(f) model view registered with
the test view of Phone at the end of first, second, third and fourth iterations; (g) registered views
at the convergence of the algorithm.
sixth iteration. It can be seen that even with a coarse initial estimate of the rotation, the registration
technique can align the two views successfully within a few iterations. Given a coarse correct initial
guess, registration, on the average, takes about seconds to register two range images whose sizes
are 640 \Theta 480 on a SPARCstation 10 with 32MB RAM.
5.2 Discussion
In general, all the orientation parameters of an object will be improved by the proposed MVE
method if the object surface covers a wide variety of orientations which is true with many natural
objects. This is because each locally flat surface patch constrains the global orientation estimate
of the object via its surface normal direction. For example, if the object is a flat surface, then only
the global orientation component that corresponds to the surface normal can be improved, but not
the other two components that are orthogonal to it. For the same reason, the surface normal of
a cylindrical surface (without end surfaces) covers only a great circle of the Gaussian sphere, and
thus, only two components of its global orientation can be improved. The more surface orientations
that an object covers, the more complete the improvement in its global orientation can be, by the
proposed MVE method. An analysis of the performance of the MVE and unweighted registration
algorithms with surfaces of various geometries can be found in [14].
When more than two views have to be registered, our algorithm for registering a pair of object
views can be used either sequentially (with the risk of error accumulation) or in parallel, e.g., with
the star-network scheme [9]. Note however, that we have not extended our weighted approach
to the problem of computing the transformation between n views simultaneously. When there
is a significant change in the object depth the errors in z at different points on the surface may
no longer have the same variance; the variance typically increases with greater depth. In such
situations our perturbation analysis still holds, except for the covariance matrix \Gamma A T in Eq. 9. The
diagonal elements of this matrix will no longer be identical as we assumed. Each element, which is a
summary of the noise variance at the corresponding point in the image, must reflect the combined
effect of variation due to depth, measurement unreliability due to surface inclination, etc., and
therefore a suitable noise model must be assumed or experimentally created.
6

Summary

Noise in surface data is a serious problem in registering object views. The transformation that
relates two views should be estimated robustly in the presence of errors in surface measurements
for seamless view integration. We established the dependency between the surface orientation and
the accuracy of surface normal estimation in the presence of error in range data, and its effect on
the estimation of transformation parameters with geometrical analysis and experimental results.
We proposed a new error model to handle uncertainties in z measurements at different orientations
of the surface being registered. We presented a first-order perturbation analysis of the estimation
of planar parameters from surface data. We derived the variance of the point-to-plane distance to
be minimized to update the view transformation during registration. We employed this variance
as a measure of the uncertainty in the distance resulting from noise in the z value and proposed
a minimum variance estimator to estimate transformation parameters reliably. The results of our
experiments on real range images have shown that the estimates obtained using our MVE generally
are significantly more reliable than those computed with an unweighted distance criterion.

Acknowledgments

This work was supported by a grant from Northrop Corporation. We thank the reviewers for their
helpful suggestions for improvement.



--R

"Object modelling by registration of multiple range images,"
"Integrating information from multiple views,"
"Generating models for solid objects by matching 3D surface segments,"
"A method for registration of 3-D shapes,"
"Zippered polygon meshes from range images,"
"Iterative point matching for registration of free-form curves and surfaces,"
"Registering multiview range data to create 3D computer graphics,"
"Registering range views of multipart objects,"
"Towards a general multi-view registration technique,"
"Pose estimation from corresponding point data,"
"Scene reconstruction and description: Geometric primitive extraction from multiple view scattered data,"
"Surface classification: Hypothesis testing and parameter estima- tion,"
Experiments in 3D CAD-based Inpection using Range Images
cosmos: A Framework for Representation and Recognition of 3D Free-Form Objects
"Motion and structure estimation from stereo image sequences,"
"Motion and structure from two perspective views: Algorithms, error analysis, and error estimation,"
"From images to models: Automatic 3D object model construction from multiple views,"
--TR

--CTR
Alberto Borghese , Giancarlo Ferrigno , Guido Baroni , Antonio Pedotti , Stefano Ferrari , Riccardo Savar, Autoscan: A Flexible and Portable 3D Scanner, IEEE Computer Graphics and Applications, v.18 n.3, p.38-41, May 1998
Byung-Uk Lee , Chul-Min Kim , Rae-Hong Park, An Orientation Reliability Matrix for the Iterative Closest Point Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.10, p.1205-1208, October 2000
Gregory C. Sharp , Sang W. Lee , David K. Wehe, ICP Registration Using Invariant Features, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.1, p.90-102, January 2002
Xianfeng Wu , Dehua Li, Range image registration by neural network, Machine Graphics & Vision International Journal, v.12 n.2, p.257-266, February
Zonghua Zhang , Xiang Peng , David Zhang, Transformation image into graphics, Integrated image and graphics technologies, Kluwer Academic Publishers, Norwell, MA, 2004
Ross T. Whitaker , Jens Gregor, A Maximum-Likelihood Surface Estimator for Dense Range Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.10, p.1372-1387, October 2002
Luca Lucchese , Gianfranco Doretto , Guido Maria Cortelazzo, A Frequency Domain Technique for Range Data Registration, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.11, p.1468-1484, November 2002
3D free-form objects;automatic object modeling;view transformation estimation;image registration;range data;view integration