rain pipe, bushes etc., give additional fluctuation to laser
range measurement. Thirdly, planar face far from the
viewpoint is difficult to be extracted since the resolution of
laser range points on the planar face is low. Fourthly, there
are a lot of occlusions and wide variations from one view
to another. On the other hand, Z-axis of the sensor’s
coordinate system is always vertical to the ground, and
the ground is usually flat between two successively
measured views. With this as assumption, laser range
image can be tessellated into a two-dimensional image
called “Z-lmage” within a given resolution (Figure 1). Z-
Image has its origin, X-axis, Y-axis consistent with those in
sensor’s coordinate system. Value of each pixel in Z-
Image is the number of laser range points fall into the
tessellating cell. Registration of two views of laser range
image can be solved in two steps. First, Z-lmages are
matched to track the horizontal rotation angle and
translation parameters along X and Y axes. Secondly,
ground points in laser range images are matched to track
the translation of Z-axis of sensor’s coordinate system.
Another problem faced in registering multiple overlapping
laser range images is the accumulation and propagation
of estimation error from pair-wise registration. To solve the
problem, a least square error measure is defined and
minimized by an iterative process.
Figure 1 Tessellating laser range image into Z-lmage
In the following sections, we will discuss the issues
involved in registering multiple overlapping laser range
images by pair-wise registering successive views using Z-
Image. Focus of the paper will be cast on the method for
robustly matching Z-lmages, since it is the core of the
registration process. We present two sets of experiment
results in this paper. In the first experiment, two views of
laser range images are registered to testify the
methodological framework for pair-wise registration. In the
second experiment, 29 views of laser range images are
measured and registered to construct a 3D model for the
buildings in IIS, Univ. of Tokyo. The objective of the
experiment is to examine the robustness of the pair-wise
registration method, and testify the accuracy and
efficiency in solving the error accumulation problem in
multiple view’s registration.
2 PAIR-WISE REGISTRATION
2.1 Matching Z-lmages
Matching Z-lmages is quite a two-dimensional problem.
There has been a substantial body of work performed on
the registration of two-dimensional images. Since the
linear structures in Z-lmage is rather clear, which
represent the surfaces of vertical objects, and can be
extracted by doing linear regression on the group of points
surrounded. A searching method using linear feature will
have better efficiency. On the other hand, accuracy in
feature-based matching is very dependant on the features
extracted. In order to prevent misled by poor feature
extractions, evaluation function working both on linear
feature and image points is demanded. Quantitatively
evaluating the likelihood of correspondence candidates
has been at the core of many previous research efforts.
Sanfeliu and Fu, 1983 suggested a distance measure
using the weighed sum of costs when transforming one
graph into another. Since there lack a theoretic method to
evaluate the costs between different primitives and
relations, it required an extensive number of training
values for weight parameters. Boyer and Kak, 1988;
Vosselman, 1992 extended the matching theory by
introducing information theory to account simultaneously
the statistical behaviors of primitives and relations in
matching procedure. Boyer and Kak calculated conditional
information to measure distance between two structural
descriptions, while Vosselman suggested the use of
mutual information as merit function. In both researches,
matching cost from different types of primitives and