ISPRS Commission III, Vol.34, Part 3A ,,Photogrammetric Computer Vision“, Graz, 2002 
  
terrain points as seen in Figure 3(a), in which two neighbouring 
on-terrain points are connected with each other, and then 
measure an angle difference & between the terrain surface 
on-—on 
model ÿ , and “on-on” paired observation. Similar to this, an 
inter-relationship of “on-off” paired observation can be also 
defined and its angle difference 9, is measured from ¢ as 
seen in Figure 3(b). 
In our research, these two different angle measurements are 
used to test the hypotheses of planar terrain surface models 
generated by assumption of the flat terrain. If a planar terrain 
surface model hypothesized correctly reconstructs real terrain 
surface as being "flat", on one hand, the slope angle of the 
model used reflects real terrain slope. On the other hand, two 
angles 9 and 8 which are relatively measured from 
on—on on—off ? 
the planar terrain surface model, show the characteristics of 
plane terrain surface; i) 6 gets closer to 0? since the 
labelling error that on-terrain points are misclassified as off- 
terrain, becomes smaller and thus, intra-relationships of on- 
terrain points follow the tendency of plane terrain slope; ii) 
6 gets closer to 90° in which off-terrain points show 
on-off 
obvious discontinuity from plane terrain slope. These 
characteristics can be augmented when the underlying real 
terrain surface is more flattened by a hypothesized planar 
surface model; otherwise, the labelling error becomes larger and 
thus, it degenerates these characteristics of a plane terrain 
surface. 
Based upon previous observations, we assume that a 
characteristic of plane terrain surface can be given by the 
observation of “bi-polarity”, in which the smoothness and 
discontinuity polarity are defined as a distribution of 9 of 
on—on 
“on-on” paired observations and a distribution of 9 of “on- 
on-off 
off” ones respectively. Figure 3(c) shows a desirable 
distribution of plane terrain surface in terms of the terrain 
polarity measurement, in which two peaks of “bi-polarity” 
distribution appear close to 0° and 90° respectively when given 
¢ , correctly reconstructs the real terrain surface as being plane; 
otherwise, it shows a Gaussian distribution. 
    
0. 
(a) f 
O 
/ 
A 
SSSSSS 9, i 
(b) (c) 
Q on-terrain point smoothness polarity 
O offterrainpoint — — 
polarity 
discontinuity polarity 
Figure 3. Illustration of terrain polarity measurement. 
Hence, the terrain polarity measurement serves as a criterion for 
the selection of “best fitt” planar surface model out of the model 
candidates hypothesized; a surface model to show the strongest 
polarity, where two peaks get much closer to the polarity 
boundaries 0° and 90° is selected as an optimized model 
solution. In our framework, this terrain polarity measurement is 
converted into the conditional probability density function used 
in Eq. (5) and finally described in the form of Minimum 
Description Length (MDL). This will be discussed in a later 
section. 
3.3 Two-step Divide-and-Conquer Triangulation 
Let us discuss how to determine the dimension Kk of the terrain 
surface model space y' in Eq. (4). As discussed previously in 
Eq. (4), the determination of & is related the ability to find an 
on-terrain point out of a point cloud; Æ increases as on-terrain 
points are iteratively obtained. This recursive process terminates 
when any on-terrain point cannot be found, and results in a set 
of planar surface models (o; P. satisfying Eq. (4). 
We adopt the divide-and-conquer triangulation approach, in 
which the original problem domain is recursively decomposed 
into sub-problems and represented by means of a Delaunay 
Triangulation. This  divide-and-conquer  triangulation is 
implemented as two parts in our framework, namely downward 
and upward divide-and-conquer triangulation, depending on the 
criteria of triggering and terminating this process. In the 
downward process, the dimension k of the terrain surface 
model space y is initialized as 1, so that an initial terrain 
surface model is approximated with only one planar surface 
model; y — (9,)^,, where k —1. Then, on-terrain points are 
recursively obtained by the use of pre-specified propositions of 
the terrain surface model so that the initialized y is fragmented 
into a number of planar surface models represented in a form of 
TIN. This terrain segmentation process continues until any 
negative LIDAR point located underneath the reconstructed 
terrain surface model cannot be found. 
The upward divide-and-conquer triangulation is the core part of 
our terrain surface reconstruction technique, in which the afore- 
mentioned “plane terrain prior” and “terrain polarity 
measurement” are used. The process investigates the triggering 
condition for terrain fragmentation over all planar surface 
models generated by the downward divide-and-conquer 
triangulation. Once the terrain fragmentation process is 
triggered over a planar surface model ¢ , a number of 
tetrahedral models are hypothesized as planar surface models in 
a sense that three lateral facets of a tetrahedron are used as 
plane terrain surface model candidates. Then, distributions of 
terrain polarity are measured over all tetrahedral models. Thus, 
the most optimized tetrahedral model satisfying with the 
optimality criterion of Eq. (5) is selected and the on-terrain 
point newly found by this model contributes to refining y . 
This process continues until the terminating condition for the 
terrain fragmentation process is found over the entire terrain 
surface model. The process of downward and upward divide- 
and-conquer triangulation will be discussed in detail in the 
following section. 
4. TERRAIN SURFACE MODEL RECONSTRUCTION 
Fig. 4 shows an overall process used for reconstructing the 
terrain surface model. In this section, we discuss the fore- 
mentioned overall strategy in more detail according to the 
blocks depicted in Fig 4. 
A - 339