set 
ur 
TS 
ng 
ne 
|a 
jle 
sly 
he 
of 
ile 
is- 
les 
lly 
1S- 
in 
ht 
an 
al 
  
Huijing Zhao 
component analysis with missing data (PCAMD), where objective function is composed using the distance be- 
tween corresponding planar faces in different range frames. However, enough number of planar faces is difficult 
to extract in urban area as has been addressed in Zhao and Shibasaki, 1999, and since contributions from all 
the planar faces are treated equivalently, multiple registration might be degraded by several unreliable planar 
faces. In this research, we follows the formulism in B.Kamgar-Parsi et al. 1991, where assuming that pair-wise 
registration yields locally optimized transformation between neighboring range image, multiple registration is 
formulated as a minimization of violations to local matching achieved in pair-wise registration. It is proved to 
be the most appropriate starting point in our effort to achieve a well-balanced network of range image. 
2.2 Problem statement and outline of the method 
0 
tion from the coordinate system of range image V; to a neighboring range image V;, where R;; and Shi; are the 
rotation matrix and shift vector. Let px = (pk, Ypk, 2pk, 1]T, k = i, j be range points in V; and V; respectively. 
Then it has p; = t;;p;. Suppose V; has been registered to the global coordinate system with a transformation 
matrix 7;, the transformation matrix aligning V; to the global coordinate system can be calculated by T;t;;. 
This kind of registration is called "sequential registration". 
To simplify the problem, we use homogeneous coordinates. Let t; j= Sh ) be the relative transforma- 
Figure 2 shows a motivational example of measuring a building using a network of range images (Vi, V5, ..., Va 
}. Suppose all range images are to be aligned to the coordinate system of Vi. Va can find its transformation 
matrix by : 
Ts = tigtgrtzo (1) 
We define ” V,-Vs-V7” as the "registration path” of V5. The number of range images in registration path is defined 
as the "length" of registration path. It is easy to show that pair-wise registration error is accumulated and 
propagated along the registration path in sequential registration. Although aligning all range images using the 
shorted registration path can somehow mitigate the error accumulation problem, inconsistencies happen if range 
images compose a looped network. In the above motivational example, V5 has two optional registration paths. 
They are ”V,-V,-V3-V,” and "Vi-Va-V;-Vg". Suppose the previous path is selected, then the transformation 
matrix aligning V3 to the coordinate system of Vi can be calculated as 
T5 — t12t23t34t45 (2) 
V5 and Vg is said to be "independent in registration", since neither V5 nor Va appears in the other's registration 
path. According to Eq.1 and Eq.2, it has tes = T. T = tsatastaoto1tista7t7g. In real situation, £5g is not equal 
to ts, due to the accumulation of pair-wise registration errors. We define "violation" as the difference between 
ts and tta: It can be easily shown that by sequential registration, violation exists only between the neighboring 
range images, which are independent in registration. 
The multiple registration method developed in this research consists of two consecutive procedures. First, all 
range images are sequentially aligned to a global coordinate system by the shortest registration path. It is 
conducted in an iterative mode. In each iteration, a range image is registered to a global coordinate system, 
which has a shorter registration path than other unregistered range frames. Secondly, minimizing violations 
using a weight least square method. A quantitative definition to violation is given in next section. Arbitrarily 
specifying the global coordinate system as that of a reference range frame, by the above registration, a model 
of the spatial objects with respect to the reference frame is obtained. On the other hand, in urban outdoor 
environment, absolute locations of several range frames can be measured using GPS. When given the absolute 
locations as ground control points, a model of the spatial objects with respect to world coordinate system can 
be obtained. The additional work other than the above registration procedures is addressed in section 2.5. 
2.3 Registration cost function 
/ / 
Let t. ; = 7; = i Sh, ) be the relative transformation matrix obtained in multiple registration. 
Violation (Vio;j) in range image pair V; and Vj is evaluated by summing the violation in shift vector (Vio}?) 
and rotation matrix (Vioj;) as follows. 
Vio;j = Vio? + Vio}; (3) 
In this research, we evaluate the violation by its effect on the location of its nearby range frames. Figure 3 
shows the evaluation of violations in shift vector and rotation matrix. Due to the difference between and , the 
location of range frame is projected to (Figure 3(a)). Violation in shift vector is thus evaluated by the Euclidean 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 1035