Roland Geibel 
  
planar parts which are oriented in few directions. This assumption allowed to use orientation histograms for 
segmentation. 
If also objects shall be recognised which do not fulfil this assumption, then more general segmentations must be 
considered. Since in general an essential step in reconstructing objects from height data consists in a good segmentation 
of the height image into geometrically well matching surface parts, other procedures for the segmentation of range 
images known from literature were investigated. Yet it shows that the question of what is a good segmentation and what 
is a good segmentation procedure is too general in this wording. In the restricted area of the segmentation of laser 
altimeter images, we present a further development of the evaluation measure defined in [Hoover et al., 1996]. 
2 SEGMENTATION PROCEDURES 
In the contribution presented here, four procedures for the segmentation of range images, known from literature are 
investigated and compared. Three region growing based procedures which were available via the WWW were installed. 
Two procedures are based on an iterative region growing from seed regions. One procedure uses a clustering approach. 
An other procedure which serves for extracting straight lines yields as an intermediate result also a region segmentation. 
Furthermore an own simple region growing procedure was developed. It is regulated by only one parameter and in 
addition produces the neighbourhood graph of the segments. In each of the procedures the result of the segmentation is 
a label image and for each segment the description of the plane by a plane equation. 
2.1 Burns 
In the procedure of Burns et al [1986] straight lines are extracted from an intensity image by investigating the gradient. 
Straight edges have in their neighbourhood areas with similar gradient orientation, which is perpendicular to the edge. 
Thus first connected regions of equal gradient orientation are searched. In height images planar areas show gradients of 
equal size and direction. Applying the procedure of Burns to height data, the partitioning of the inspected image into 
connected areas of equal orientation can also be considered as a segmentation into regions. 
2.2 The UB-procedure (University of Bern) 
In the forefront of the procedure by Jiang and Bunke [1994], [Hoover et al., 1996] there is the line-like grouping of 
points in range images recorded in rows. For this purpose first each row of the image is recursively split into most 
possible straight line segments, then a region growing is performed on these line segments instead of the single pixels. 
As seed regions for the region growing process those triples of neighbouring line segments are used for which (1) all 
three line segments have at least a requested minimal length, (ii) the intersection of two adjacent line segments has a 
certain percentage of the total length of each of the three line segments and (iii) each pair of adjacent points on two line 
segments does not exceed a certain distance threshold. 
Among all of these possible seed regions the one with the highest total length is chosen as an optimal seed region. Then 
other line segments are added to this region if the distance of both of the endpoints of the line segment from the plane of 
the growing region remains inside a threshold. This process of adding a further line segment is repeated until no further 
line segments can be added. Then the next best seed region is used to start the same process. This is repeated until all 
seed regions are processed. In a post-processing step small regions are eliminated. 
2.3 The WSU-procedure (Washington State University) 
The procedure of [Flynn and Jain, 1991], [Hoffman and Jain, 1987] is not restricted to objects with planar surfaces, but 
can also describe elliptic surfaces (spheres, cylinders, cones). It proceeds in the following 9 steps: (i) First jump edge 
pixels are identified by z-coordinate differences in the 8-neighbourhood. (ii) For the pixels distant enough from these 
jump edge pixels the surface normal is estimated. (iii) For the set of pixels with surface normal a clustering is performed 
(hoffcluster). This clustering produces connected sets of similar orientation. (iv) The pixels belonging to the same 
cluster are labelled identically. (v) Investigating the labelled sets with respect to their local neighbourhood segments are 
produced. (vi) In order to counteract over-segmentation an edge-based method for joining regions is applied. Adjacent 
regions are joined together, if the difference in angle of all normals along the common border line is small enough. (vii) 
Each segment is checked for planarity by a regression procedure. This is the first time that plane equations are 
calculated for the segments. Non planar segments are taken out of further consideration. (viii) Neighbouring planar 
segments are merged if their parameters "angle of surface normal" and "distance term" of the plane equation are similar. 
(ix) Unlabeled pixels at the border of each segment are added to the segment if their distance to the plane lies inside a 
threshold. The steps (vii) to (ix) are repeated until the result is stable. In a following post-processing step small regions 
are deleted. 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 327