ISPRS Commission III, Vol.34, Part 3A ,,Photogrammetric Computer Vision", Graz, 2002 
  
introduce unnecessary distortions. So, in addition to the 
algorithmic concerns, an adaptation of image-processing 
concepts to the irregular pattern becomes necessary. With 
the aim of identifying structure in the data in mind, the pro- 
posed algorithm is general and can be applied in a variety 
of applications. 
2 SURFACE CLUSTERING 
Similar to data segmentation, the goal of data clustering 
is to subdivide the data into disjoint regions each with a 
homogeneous property that distinguishes it from its sur- 
rounding. The regions are defined by the set of points in- 
cluded within each segment, where different regions can- 
not share points. The proposed algorithm considers the 
surface clusters an instantiations of more generic processes 
defined here as surface categories. The algorithm aims at 
distinguishing among four different surface categories, i) 
forested/wooded area, ii) low vegetation areas and rough 
surfaces iii) smoothly varying topography, and iv) planar 
surfaces. Surfaces refer here to the interpretation of the 
data obtained by laser scanning system, and the categories 
present one interpretation of the laser data surface. The 
surface classes are not aimed at providing a topographic 
structure of the terrain, mainly since the acquired data is 
not the terrain itself. Yet the clusters provide a separation 
of the surface into homogeneous parts. The distinction be- 
tween smoothly varying topography and planar surfaces is 
made here because of the tendency of man-made object 
to have planar facets, and the value of this information to 
other applications. 
2.1 The feature vector 
By nature, laser data attributes will be derived from surface 
texture measurement.! The measures should be sufficient 
to differentiate among surface categories and among sur- 
faces within each category. Several measures have been 
proposed for segmentation of range data, among them are 
the analysis of the height differences in a window via his- 
togram followed by segmentation based on thresholding. 
Axelsson (1999) uses the second derivatives to find varia- 
tions, and Maas (1999) uses a feature vector including the 
Laplace operator, maximum slope measures and the origi- 
nal height data in order to classify the data. 
In this implementation clustering is performed based on 
an attribute vector consisting of the following measures — 
the point position, the parameters of the tangent plane to 
that point, and the relative height difference between the 
point and its neighbors. Together they form a 7-tuple vec- 
tor vj :— (zi, yi, Zi Tí 1,230 pi, di] for each point, with 
Ti, Yi, Zi, the laser point coordinates, 7/, »3;, Pi, the sur- 
face parameters (normal measured by two parameters and 
a constant), and d; the height difference of the point to its 
neighbors. 
The inclusion of the point position as an attribute is es- 
sential for measuring proximity to other points that share 
  
1]f reflectance measurements are available, information can also be 
derived from these values. 
A - 120 
  
  
  
  
  
Figure 1: Potential inseparability of surfaces based on 
height differences 
similar properties. Height differences are perhaps the most 
commonly used measures as they measure local variation 
and are expected to be reliable up to the level of noise in 
the data. They provide an adequate indication for the exis- 
tence of high vegetation but they are insufficient for surface 
separation as the example in Figure 1 demonstrates. From 
an analytical standpoint height differences capture the ex- 
istence of step edges in the data, and emulate the effect of 
an edge operator in raster data. Their main contribution is 
in enhancing the separation of clusters from one another. 
The tangent plane parameters consist of the normal direc- 
tion and the constant. The slope parameters capture first- 
order discontinuities, thereby enhancing the separation of 
surface elements with different trend such as the ones in 
Figure 1. Slopes capture no positional information, but the 
constant value positions the plane in space and enables sep- 
arating surfaces with similar slopes. Surface parameters 
and the height differences share some similarity; consider 
for example two horizontal planes for which the difference 
in the surface constant is in-fact the height difference. Yet, 
the plane constant refers to an infinite plane and is a rather 
global measure while the latter measures difference to a 
neighboring points, and is rather local. 
  
  
  
Category Surface Height 
Slopes Difference 
High vegetation | Rapidly varying Large 
Low vegetation | Rapidly varying | Medium 
Smooth surface | Locally constant Small 
Planar surface Fixed Small 
  
  
  
  
  
Table 1: Surface categories vs. attributes 
Table 1 lists the expected characteristics of these attributes 
for each of the four surface categories. The measures are 
qualitative and not strict, but they are sufficient to indicate 
that the chosen features make the identification of these 
four categories possible. Translating these measures into 
quantitative values is partially the essence of the algorithm. 
2.2 Metrics to measure the attributes 
Successful clustering of the data depends on the features 
representation. While height differences consist of a sin- 
gle measure and have a natural metric unit, planar surfaces 
can be described in various ways. It is common to use 
the explicit three parameters representation consisting of 
the slopes in the x and y direction, s,, s, and the intercept 
point. However, this representation breaks down with ver- 
tical or near vertical structures (e.g., walls.) The represen- 
tation of the surface slopes by their tangents also offers