ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision‘, Graz, 2002 
  
TERRAIN SURFACE RECONSTRUCTION 
BY THE USE OF TETRAHEDRON MODEL WITH THE MDL CRITERION 
G. Sohn, I. Dowman 
Dept. of Geomatic Engineering, University College London, Gower Street, London, WCIE 6BT UK - (gsohn 
idowman)@ge.ucl.ac.uk 
? 
Commission III, WG III/3 
KEY WORDS: LIDAR, Automation, DEM/DTM, Filtering 
ABSTRACT: 
A LIDAR filtering technique is used to differentiate on-terrain points and off-terrain points from a cloud of 3-D point data collected 
by a LIDAR system. A major issue of concern in this low-level filter is to design a methodology to have a continual adaptation to 
terrain surface variations. To this end, several essential observations are discussed in this paper: i) the terrain surface can be 
fragmented into a set of piecewise “homogeneous” plane surfaces, in which terrain surface variations are smoothed out, il) a criterion 
for differentiating on- and off-terrain point from plane terrain surface can be equivalently applied to these terrain segments assumed 
as being plane, and iii) an inter- and intra-relationship of on- and off-terrain points can be as verifying the a priori taken assumption 
of the plane terrain surface. The main strategy implemented in our LIDAR filtering technique is to iteratively generate a number of 
terrain surface models in order to hypothesize and test a plane terrain surface over a local area. Finally, the most reliable plane terrain 
surface model is selected as an optimised solution and thus the terrain surface model is refined. To this end, we devise a two-step 
divide-and-conquer triangulation in terms of downward and upward model refinement; in this framework, a tetrahedron is used in 
order to hypothesize a plane terrain surface and the Minimum Description Length (MDL) criterion is employed for the selection of 
an optimized plane terrain surface model. The useful characteristics of this method are discussed with results derived from real 
  
LIDAR data. 
1. INTRODUCTION 
Recently, LIDAR technology has been getting much more 
attention from the photogrammetry, remote sensing, surveying 
and mapping community as an important new data source for a 
wide range of applications; topographic mapping, bathymetry, 
forest mapping, crop height measurement, flood modelling and 
3-D building modelling (Cobby et al., 2001). Among the many 
algorithmic methodologies used to generate the above value- 
added products, a filtering technique to differentiate on-terrain 
points from off-terrain points has been emphasized as an 
efficient focusing strategy to understand complex scenes. 
Although various types of filtering techniques have been 
introduced (Pfeifer & Kraus, 1998; Axelsson, 2000; Vosselman, 
2000), Flood (2001) reported that 60% - 80% of LIDAR data 
processing lines running in private firms is allocated to manual 
classification and final quality control, due to the lack of 
efficient algorithms for extracting the bare earth surface. 
2. PROBLEM DESCRIPTION 
2.1 Labelling Problem 
A LIDAR filtering technique to differentiate on- and off-terrain 
points from a point cloud can be considered as a low-level 
vision problem. Such a low-level filtering technique is often 
posed as a labelling problem in which predefined semantic 
labels are assigned to data (Li, 2001). 
Suppose that we have a set of discrete LIDAR points S and a 
labelling function F which assigns pre-designed semantic labels, 
namely (on, off) to the data domain S. The labelling function F 
A - 336 
generates a set of new labelling observations f, which can be 
described as follows: 
S 2 (s, 
(1) 
f Ua f F(s); fe tonoff) 
where ; is the index of discrete point s; N is the dimension of 
the domain S; f; is a label assigned to the point s; from a label 
set (on, off]. 
In order to give the labelling function F of Eq. (1) an actual 
method to populate wanted terrain labels, a criterion J to 
differentiate on- and off-terrain points is needed. A major issue 
concerned in the selection of ó is how to make ó robust under 
the circumstances where background knowledge about 
underlying terrain slope has changed; when terrain slope 
changes gently or abruptly. This scale issue governs the overall 
performance of the filter. Figure 1 illustrates a simple example 
where a criterion óis selected to differentiate on- and off-terrain 
points from a flat terrain surface; a point with slope angle larger 
than óis labelled as an off-terrain point; otherwise, it is labelled 
as an on-terrain point (see Figure 1(a)). However, when a point 
is located in a different background, this criterion ó is not valid 
any more since the background knowledge that the terrain 
surface is flat has been altered (see Figure 1(b)). 
There may be two ways to tackle this problem. One is to make ó 
adaptive to underlying terrain slope; J is trained with the 
analysis of background knowledge about terrain slope collected