Least Squares 3D Surface Matching. (= Institut für Geodäsie und Photogrammetrie (.). Mitteilungen 92).

Laser scanners can measure directly 3D coordinates of huge amounts of points in a short time period.
Most of them also provide an intensity value for every point. This abundant data can be efficiently
used to model the scene. In many cases, the object has to be scanned from different viewpoints in
order to completely reconstruct it. Because each scan has its own local coordinate system, all the
different pointclouds must be transformed into a common system. This procedure is usually referred to
as co-registration. Actually, the co-registration is not a problem specific to the laser scanner domain.
Also in photogrammetry, we face many similar problems.

The automatic co-registration of pointclouds, representing 3D surfaces, is a relevant problem in 3D
modeling. This multiple registration problem can be defined as a surface matching task. In
photogrammetry, surface matching was first touched by Gruen (1985a) as a straight extension of the
Least Squares image matching. This thesis work gives a generalization of this 2D technique to the 3D
surface matching problem. The proposed method estimates the transformation parameters of one or
more fully 3D search surfaces with respect to a template one, using the Generalized Gauss-Markoff
model, minimizing the sum of squares of the Euclidean distances between the surfaces. It fully
considers 3D geometry.

An observation equation is written for each surface element on the template surface patch, i.e. for each
sampled point. Each equation functionally relates the observations of the template to the parameters of
search surface. The constant term of the adjustment is given by the observation vector whose elements
are the Euclidean distances between the template and search surface elements. The matching is
achieved by Least Squares minimization of a goal function, which measures the Euclidean distances
between the surfaces. The final location of the search surface is estimated with respect to an initial
state. The geometric relationship between the conjugate surface patches is defined as a 7-parameter 3D
similarity transformation. This parameter space can be extended or reduced, as the situation demands
it. Since the functional model is non-linear, the system is linearized by Taylor expansion. The
numerical derivative terms are defined as surface normals. The unknown transformation parameters
are treated as stochastic quantities using proper a priori weights. This extension of the mathematical
model gives control over the estimation parameters. The solution is iterative. After the joint system is
solved, the search surface is transformed to a new state using the updated set of transformation
parameters, and the design matrix and the discrepancies vector are re-evaluated. The iteration stops if
each element of the alteration vector falls below a certain limit.

Besides the mathematical model of the procedure, a comprehensive discussion is given about the
implementation details, precision and reliability issues, and convergence behavior. Special attention is
paid to the computational aspects. Two strategies in order to decrease the computation time were
implemented. The main portion of the computational complexity is to search the correspondent
elements between the surfaces, whereas the adjustment part is a small system, and is quickly solved
using Cholesky decomposition followed by back-substitution. A rapid space partitioning method is
given for searching the correspondences. It is a 3D boxing structure combined with a hierarchical local
and adaptive nearest neighborhood search. The local neighborhood is hierarchically updated during
the iteration.

The second acceleration strategy is simultaneous matching of sub-surface patches, which are selected
in cooperative surface areas. They are joined to the system by the same 3D transformation parameters.
The individual patches may not include sufficient information for the matching of whole surfaces, but
together they provide a computationally effective solution, since they consist of only relevant
information rather than using the full data set.

In case of lack of sufficient geometric information the procedure may fail, e.g. in case of matching of
two planes or spherical objects. An object surface may have some attribute information attached to it.
Temperature, intensity, and color are well known examples. Most of the laser scanners can supply
intensity information in addition to Cartesian coordinates for each point. We propose an extension that
can simultaneously match intensity information and geometry under a combined estimation model. In
this approach the intensity image of the pointcloud also contributes observation equations to the
system, considering the intensities as supplementary information to the range image.

The mathematical model is flexible. Further conceptual extensions are given as the Least Squares
matching of 3D curves and matching of 3D curves or 3D sparse points (e.g. ground control points)
with a 3D surface. Additionally, a general framework for the simultaneous matching and
georeferencing of multiple 3D surfaces with their intensity information is formulated.

The method derives its mathematical strength from the Least Squares matching concept and offers a
high level of flexibility for many kinds of 3D surface correspondence problems. The experiments
demonstrate the capabilities of the basic method and the extensions.