r
mn oo
3 A
wv vu
OOV ct (DL.
(D She cto
171
2. REGISTRATION
Registration of a set of range images is defined as the process of recovering for each image the 3-D rigid transformation
(rotation and translation) that brings it into one common Cartesian coordinate system. The transformation for each
image must be discovered, or at least refined, from the sensed data itself. This is usually accomplished by setting
the problem as the optimization of a cost function based on a metric estimating the relative distance between the
common portions of a surface from different views. This optimization problem is generally non-convex, and the various
methods that have been proposed in the computer vision literature differ in the formulation of the inter-surface metric
as well as the techniques attempting to converge to the global minimum (for surveys see [2. 3. 13. 16]).
The full problem at hand deals with the registration of a set of range images. This paper will reduce the case to
the one of a pair of images. In general it cannot be considered that one image is a subset of the other, contrary
to the image-to-model registration problem in [2]. Thus there is usually no obvious reason to consider one image
as a reference for the other: the algorithm should therefore be commutative, that is, it should yield the same result
independent of the order in which the images in a pair are considered. The commutativity requirement is also
discussed in [7, 16].
The use of computed curvatures as a matching constraint introduces possible errors in the registration. Accurate
registration of the image should rely only on the raw measurement, in order to avoid the noise introduced by surface
differentiation. Given that fact, the algorithm proposed here operates at the point level, that is it does not interpolate
the surface from the image data. Instead, the distance metric will be defined as the closest point in the other range
image. For this reason the resolution of the registration will be limited by the surface sampling density. The idea
behind this approach is that the method proposed here is used to bring images very close to one another, in the
order of one pixel. A final close-up step can then be performed by applying traditional methods that uses surface
interpolation, and no derived features.
Other registration techniques using curvature estimation have been proposed. In [11], a curvature sign map is
computed and regions of similar categories are organized in an attributed graph. À subgraph matching algorithm is
then applied to recover the correspondence and the 3-D transformation. In another approach [15], local estimates
of the Darboux frames are used to find consistent motion estimates between surface patches. In a method which is
related to the one described here [7], invariant reflectance parameters, derived from the intensities that are measured
simultaneously by the range sensor, are used in a similar manner to constrain points matches.
3. COMPUTING CURVATURE ESTIMATES
In the field of range image analysis, Besl and Jain [1] have proposed an invariant surface characterization method
based on differential geometry. In theory, mean (H) and Gaussian (K) curvatures are invariant under viewpoint
transformations. Smooth surfaces are then locally classified into one of eight surface types according to the signs
of H and K: However, the stability of this representation crucially depends upon the ability to accurately compute
local surface curvatures. Since differential geometry is a theory of smooth differentiable surfaces, one must take into
account the fact that real range images contain, in addition to noise, depth and orientation discontinuities which
will affect the computation of the curvatures. Most of the methods found in the literature estimate the derivatives
necessary to compute the curvatures by using a local surface model of at least second order. The problem with these
methods is two-fold. First, since in most cases the norm used to compute the local model is not truly invariant, there
is a residual dependence of the Gaussian and mean curvatures on viewpoint and parameterization. Secondly, there is
usually no test performed to determine the geometrical compatibility of the center point with its neighbors, there is a
strong possibility that the estimate of the local curvature will be biased by the presence of geometrical discontinuities
in the neighborhood.
In order to solve these problems, a new method for the computation of Gaussian and mean curvatures was introduced
in [5]. This method, which is invariant to parameterization and viewpoint, determines the first and second partial
derivatives by the weighted least-square fit of a parametric biquadratic polynomial within a local moving window.
This method assigns small weights for the points which are not geometrically compatible with the center point of
the window. Thus, the derivatives are estimated based primarily on the points which are compatible with the center
point. Since the distances across a discontinuity are large, small weights are assigned to points which are on the other
side of that discontinuity. Surface curvatures are then computed from these derivatives. The viewpoint invariance of
the estimate arises from the fact that the surface estimation process minimizes the distance between the surface and
the data points in the direction perpendicular to the tangent plane of the surface at this point. The original surface
parameterization, which is extrinsic to the surface, can also be transformed into an intrinsic one corresponding to the
minimal norm between the data points and the local surface model.
In each point of the range image, a local second-order model, which is invariant to viewpoint and parameterization, is
estimated. From this local model, the first and second order partial derivatives are computed. An invariant estimates
of these derivatives is essential in order for the computed Gaussian and mean curvatures to be truly invariant. Let
Q be a neighborhood of size N x N where f(u,v)-— (x(u, v), y(u, v), z(u, v)) are the measurements produced by
IAPRS, Vol. 30, Part 5W1, ISPRS Intercommission Workshop “From Pixels to Sequences", Zurich, March 22-24 1995