ISPRS Commission III, Vol.34, Part 3A ,,Photogrammetric Computer Vision", Graz, 2002 
  
Triangulation. However, if no new on-terrain point can be 
found from the “on-terrain point stack” after the upward divide- 
and-conquer triangulation is completed over the entire current 
model space, our terrain reconstruction process is terminated 
(see Figure 4). 
4.3.1 Observation Model 
Once the upward divide-and-conquer triangulation process is 
triggered for certain areas reconstructed by a planar terrain 
surface model ¢. , the remaining problem is to look for “the 
most reliable” on-terrain point from LIDAR dataset S; located 
over @, so that this local area is fragmented into more planar 
terrain surface models. To this end, a tetrahedron model I is 
adopted for terrain fragmentation of 9, , in which the base 
triangle of T corresponds to 9, and the remaining three lateral 
facets of T; are hypothesized as planar surface models where i is 
the index of the tetrahedron model candidates generated over 
@, and k is the index of facets which comprise a tetrahedron 
model T; (see Figure 6(a)). 
  
on-terrain point 
LIDAR point 
on-terrain candidate ——: 
real terrain surface 
current model 
model candidate 
Hoe 
Figure. 6 Illustration of the generation of tetrahedron model 
candidates. (a) Tetrahedron model 7 , where H is the height 
I! . (b) The generation of two different tetrahedron model 
candidates. 
Since three vertices of 9, are labelled as on-terrain points at the 
previous iteration step of our terrain reconstruction process, the 
remaining vertex of the tetrahedron r is used to hypothesize 
an on-terrain point out of S;. Thus, a set of tetrahedron model 
candidates (77) is generated, sharing its base triangle with 9, 
and using each point of S; as the remaining vertex of I (see 
Figure 6(b)) However, during the generation of {T; s ri 
satisfying the following ^ condition is rejected; 
Vke(L2,3) 's* «0, where @* is one of three lateral facets 
of T; and s! is vector of LIDAR dataset belonging to the 
model candidate 6) : 
For simplifying mathematical notations, let us consider one of 
three lateral facets 9; as ¢. Suppose then LIDAR dataset S is 
located over ¢ as seen in Figure 7(a). Since the underlying area 
is hypothesized as a plane terrain surface by ¢ , the vertical 
height of each point of S is recomputed relative to ¢ so that z 
values of LIDAR points S, are projected into a flat horizontal 
plane. Then, a set of labelling observations f for S is generated 
by Eq. (6) when 6, is given (see Figure 7(b)). 
  
  
(XY) 
© (d) 
Bl ons [] bus [J offs @ onterrainpoint © off-terrain point 
Figure. 7 Illustration of observation model used for the 
polarity measurement. 
In order to make inter- and intra-relationships for on- and off- 
terrain points, a TIN is constructed over f as seen in Figure 6(c). 
Now, let us introduce a new observation variable y, for the 
terrain polarity measurement using this TIN. Suppose that we 
have a labelling function R which assigns a new labelling 
observation y, to each triangle A, of TIN from a semantic label 
set {ons, bufs, offs} (see Figure 7(d)); a “ons” is assigned to A, 
when all the three vertices of A, are labelled as on-terrain 
points by Eq. (6); similarly to this, *bufs" is assigned when A, 
is comprised of the mixture of on- and off-terrain points; 
otherwise, *offs" when all the vertices of A, are labelled as off- 
terrain points. This labelling function R can be described as 
follows: 
y={y}; Vs,eS, 7, =R(A;); 7, € {ons,bufs, offs} (7) 
ons if F({s;,8,,5,}|9,0,) = {on} 
R(A,)=jbufs if F({s,,s,,5,}19,6,)={on,aff} (8) 
off — if F((s.s,,5,3]6.0,) - (off) 
Where in Eq. (8), (s,,5,,5,,) are three vertices of A, and F is the 
labelling function for a single LIDAR point. Now, we can 
measure the closeness between ¢ and y in terms of terrain 
polarity measurement, in which A0 serves as a parameter to 
determine a degree of the smoothness and discontinuity polarity 
depending on a label assigned to A,. This AO is defined as 
follows: 
A6 -le, -e,| (9) 
where AG is the angle difference between the slope of a 
triangle A, and the one of a planar surface model ¢, namely 
0, and 8, respectively. 
A - 34]