The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
465 
to derive hypotheses of building instances. The generated 
hypotheses are based on several point attributes as well as the 
spatial relationships among the non-ground points. More 
specifically, non-ground points are classified into points 
pertaining to planar or rough surfaces. Using an adaptive local 
neighborhood for each point, one can decide whether this 
neighborhood defines a planar surface or not. Then, a grouping 
technique is applied to collect neighboring points that belong to 
planar surfaces while considering proximity of them in 3D 
space. Finally, the derived groups are filtered to generate 
building hypotheses based on the size of the group and their 
height above the terrain. The generated hypotheses are based on 
the prior knowledge that buildings are usually large in size with 
a certain minimum height above the ground. Figure 5 shows the 
building hypotheses generated through these procedures. In the 
figure, the points with different colours belong to the different 
building hypotheses. One should note that the points belonging 
to the different hypotheses might be shown in the same color 
due to the limitation of the number of utilized colors. In 
addition, a single hypothesis might consist of points from 
several planes. This situation happens when a structure is 
formed by a series of connected planes with different slopes and 
aspects. 
Figure 5. Generated building hypotheses. 
2.3 Segmentation of Planar Patches and Intermediate 
Boundary Generation 
The following procedure segments the points that are in a single 
building hypothesis, but may come from physically different 
planes, into a group of planar patches. The proposed 
segmentation technique in this paper is a voting scheme that 
keeps track of the point attributes, as defined by an adaptive 
local plane through its neighboring points, in an accumulator 
array. More specifically, the procedure is composed of three 
sub-steps: neighborhood definition; attribute derivation; and 
clustering of neighboring points with similar attributes. First, a 
neighborhood definition which considers both the three- 
dimensional relationships between LiDAR points and the 
physical shapes of surfaces is introduced and employed (Filin 
and Pfeifer, 2006). The physical shapes of the surfaces on 
which associated points are located are incorporated into the 
neighborhood definition. This means that points located on the 
same surface are considered to be possible neighbors, while 
taking into account the proximity of the points. Points on 
different surfaces, on the other hand, are not considered to be 
neighbors, even if they are spatially close. This definition 
increases the homogeneity among neighbors. Neighbors are 
determined using a cylinder whose axis direction changes 
according to the physical shape of the object in question. It is 
for this reason that this neighborhood definition is referred to as 
the adaptive cylindrical neighborhood definition. In this 
research, point attributes are computed based on the 
neighboring points identified using the adaptive cylinder 
method. More specifically, each point has two attributes. These 
attributes are the normal distances between the local plane 
(which is defined by neighboring points through an adaptive 
cylindrical neighborhood definition) and two pre-defined points, 
shown as origin 1 and origin 2 in Figure 6. In addition, the 
figure illustrates the basic concept of point attributes 
computation. 
Figure 6. Basic concept of point attributes computation. 
Once the attributes for all the points are computed, they are 
stored in an accumulator array that keeps track of the frequency 
of such attributes. As might be expected, points with similar 
attributes will lead to peaks in the accumulator array. Figure 7 
and 8 shows the examples of the scanned LiDAR points and the 
produced accumulator array using their attributes, respectively. 
The LiDAR points in this area represent a gable roof, which 
consists of two planes with different slopes. The computed 
attributes from these points are voted in the accumulator array. 
Two groups of similar attributes, produced from the points on 
two different roof planes, construct two high peaks in the array. 
Figure 7. Scanned LiDAR points from the area including a 
gable roof.