ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision“, Graz, 2002 
  
attributes locally with the goal of finding points that share 
similar attributes, so the odds of finding a significant num- 
ber of points that share similar attributes but are not con- 
nected are low. The local computation of the attributes also 
suggests that this method is largely independent of the vol- 
ume of data that is analyzed, an increase in the size of 
the dataset has only little effect on the number of spuri- 
ous surfaces. In addition, as surface classes are identified 
by grouping points with similar surface parameters, the 
clustering algorithm can support the extraction of smooth 
surface and not only planar ones, a feature that cannot be 
achieved by the Hough representation. Comparing the fea- 
ture space based approach to region-growing based seg- 
mentation shows that there is no dependency here on the 
selection of seed-points in this implementation. This is an- 
other merit of this approach, structure is obtained directly 
from the parameter space. 
3 THE CLUSTERING ALGORITHM 
The clustering algorithm consists of three main processes — 
generation of cluster proposals, validation, and refinement. 
Based on the formation of the feature space the clustering 
algorithm can be described as follows 
1. initialize n,,;, the minimal number of points per clus- 
ter and Smaz an accuracy threshold 
2. compute attributes d; and 71,1 »;, p; V laser points 
3. generate a feature space 
4. propose a surface class and identify points associated 
with the class 
5. group points according to the neighborhood system 
6. for each group 
7. if group size € n,,;,, then dismiss group else 
compute surface attributes for the group in 
particular the estimated standard deviation s 
8. if $ > Smaz then 
9, Test for the existence of outliers 
10. Test for the existence of more than one class and 
split if needed 
11. endfor 
12. repeat steps 3-10 until no meaningful surfaces are 
proposed 
13. Extend each cluster based on its attributes until no 
further points can be added, or another cluster was 
reached 
14. Merge clusters that share similar attributes and test for 
surface model 
15. Analyze and group unclassified points based on height 
variation 
A- 122 
The computation of the features is governed in large by 
the existence of noise and outliers in the data, which may 
distort the feature values and thereby affect the analysis of 
the parameter space and the clusters. Outliers are identi- 
fied as points that statistically do not belong to their sur- 
rounding. Analysis is performed here by t-test. The term 
outlier may be misleading since some of these points are 
in fact reflected from physical objects (e.g., power lines or 
poles). Notice that by computing the attributes based on 
the point neighborhood the computation becomes a geo- 
metric implementation of a low-pass filter integrated into 
the computation of the first derivatives. 
Surface clusters are derived by the extraction surface classes 
and grouping the points in object space. Many unsuper- 
vised classification algorithms can suit for the extraction 
of surface classes; the one that was implemented here is 
based on a mode seeking algorithm, which does not re- 
quire predefining the number of clusters such as in many 
other unsupervised classification methods. A mode seek- 
ing algorithm is better suited for identifying planar surface 
elements, therefore planar surface fitting is used for val- 
idation of surface cluster. In case of a large cluster and 
inadequate plane fitting results a smooth surface model is 
tested as well; the determination of the actual surface shape 
(planar or smooth) is done at a later stage. The validation 
concerns testing whether the cluster is homogeneous and 
indeed composed of only one surface class; and if that is 
the case, validating that all points in the cluster belong to 
the same class. It is possible (and happens indeed) that 
due to smoothing, points that do not belong to the class (or 
that are marginal) obtain attributes similar to their neigh- 
bors. The algorithm handles the two scenarios as follows. 
The null-hypothesis assumes that the cluster represent only 
one class. Therefore, the existence of outliers is tested 
first. The implementation of outlier detection is carried out 
by an analysis of the normalized residuals. Instead of the 
standard deviation the median deviation, a measure that is 
more robust to the existence of outliers is used. Indeed, 
robust methods for detection of up to 50% outliers, like 
the least-median-of-squares (Rousseeuw and Leroy, 1987), 
exist. But as they are essentially greedy algorithms they are 
very slow. The current situation is by the nature of the pro- 
cess more controlled, and leads to the simplified algorithm 
to work well. Its failure is an indication that the cluster 
may be composed of more than on surface. Testing for the 
existence of more than one surface is implemented here by 
tuning the clustering to the given set of points. 
The cluster refinement phase involves extending the clus- 
ter by collecting points that were not identified first as part 
of the cluster, and then merging clusters that are part of the 
same surface. Extension of the cluster to neighbor points 
is only a natural step, usually the cluster constructed by 
the feature space will not include boundary points. Inclu- 
sion of points is done by testing whether the point is from 
the same distribution as the cluster is. Points along crease 
edges may be associated with several neighboring surfaces, 
they are marked as ambiguous points. The merging of clus- 
ters is decided upon testing whether the clusters share sim- 
ilar mean (which are the estimated surface parameters) and