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