XXIX-B3, 2012 
  
  
  
ixels) 
  
1at 
ANSAC 
  
  
| 
extraction. 
nage is interpolated 
ends on the density 
fies neighbourhood 
zes algorithm time 
ied out by region 
els associated with 
ocess we obtain not 
erformed in other 
stituting individual 
on about buildings 
e performance of 
sification errors that 
. As the output, the 
building clusters 
, a building cluster 
which are adjacent 
ve outliers, detected 
oud, which is then 
rmal vectors and 
' image, they can be 
constitute building 
cels are detected by 
utation is executed 
ision of extracted 
erpolation. 
provided by laser 
he original LIDAR 
nore than one point 
oints (projected on 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XXXIX-B3, 2012 
XXII ISPRS Congress, 25 August — 01 September 2012, Melbourne, Australia 
the plane) that make up the outline contaminated by outliers. 
Thus, similar to Neidhart and Sester (2008), straight lines 
detection is performed by Random Sample Consensus 
(RANSAC) (Fischer and Bolles, 1981). The algorithm enables 
to estimate the parameters of a model in a noise data set. Each 
set of building boundary points is processed separately. First, 
the hypothesis is advanced based on the line equation computed 
from the two randomly chosen points. The hypothesis is tested 
by checking all the points from the data set. If they nearly lye on 
the candidate line, the points are added to the consensus set. 
The accepted distance from the point to the line is equal to the 
double point spacing. The hypothesis is accepted when the size 
of the consensus set exceeds predefined threshold. The line 
equation is updated using all the points that fit to the line. They 
are stored as a boundary line segment and excluded from the 
data. Then, the whole process is repeated in order to detect the 
next line segment. The algorithms stops when there is no line 
composed of required number of points. 
The boundary lines are detected based on their equations. 
Therefore, non-adjacent segments on the both sides of 
buildings’ protrusions or insets are merged together. According 
to above, modifications of the algorithm are required in order to 
disjoint non-adjacent segments that feature the same line 
equation. Depending on the connectivity threshold (the 
accepted distance between the subsequent points within one line 
segment) erroneous connections are eliminated and the line is 
divided into new, shorter intervals. The line parameters are 
updated based on the new set of points. The result of boundary 
lines detection algorithm is presented in Fig. 2c. 
2.3 Outline improvement 
The outlines provided in the previous step are composed of 
unstructured line intervals. In order to produce realistic building 
shapes, the boundaries have to be simplified, appropriately 
merged and ultimately, adjusted. The first task — line 
simplification — starts with determination of the sequence of line 
intervals within the building boundary. Each interval is assigned 
to a set of points, hence, we can easily determine the two 
opposite points with the maximum distance from the interval 
gravity centre. In order to establish topology relation between 
all such points, a binary search tree is generated. Based on the 
closets neighbours of their end points, line intervals are ordered 
clockwise and enumerated. Once the line topology is 
established, consecutive lines are investigated for their mutual 
orientation. Nearly parallel segments are joined, thus, reducing 
the number of lines that determine building outlines. According 
to the settled threshold (depended on the desired generalization 
level), generalization process reduces unwanted small details in 
the boundary and maintains the basic essentials of shape. 
The next part consists of segments merging and lines 
adjustment. The process is based on the main orientation, which 
is determined by the mean direction calculated from the longest 
building segments. Each segment gets parallel or rectangular 
label with respect to the difference between its own direction 
and the main orientation. The consecutive lines are investigated 
in order to find potential gaps within the contour. The gaps are 
detected when the two following lines get the same label. With 
respect to the distance between their end points, the lines are 
either merged or separated by the new, perpendicular interval. 
The interval is inserted halfway between their ends. In the next 
step line equations are adjusted in order to form regular 
building outlines. According to the segments’ label, 
rectangularity or parallelism constraint is enforced. The 
adjusted lines shorter than assumed generalization threshold are 
121 
removed from the contour. The final results of boundary 
regularization is illustrated in Fig.2d. 
Each line of a contour is either parallel or rectangular to the 
main direction. This assumption is motivated by the fact that 
buildings mainly consist of parallel and rectangular facades. 
Although the presented algorithm gives very precise results in 
the most cases, it fails when adjacent buildings create the 
boundary shape with any possible variety of angles. Thus, in 
order to improve the implementation additional research on that 
task will be necessary. 
  
  
  
  
  
Figure 2c. Set of refined straight lines resulting from the 
modified RANSAC algorithm 
  
  
  
ae 
Figure 2d. Building boundaries after regularization.