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