used to extract geometry primitives from 3D point clouds in 
computer version. In this section, we introduce the classical 
RANSAC algorithm for plane extraction and give a short 
overview of related work in roof facets extraction. 
2.1 RANSAC 
RANSAC algorithm is an iterative method to estimate the 
parameters of a certain model from a set of observed data. With 
application to plane model, classical RANSAC can be described 
as follows: 
1) Randomly select 3 points from data, which will define 
a plane p. 
2) Find the distances of the remaining points from the 
plane p. The points with distance smaller than a 
critical distance / are called "inliers" and belong to 
plane p. Record the three points and the number of 
the inliers, this record is called *best model". 
3) Repeat process of 1) and 2) Æ times or until no planes 
with point number bigger than d can be found. In 
each time, if the number of inliers is greater than 
those in the best model, replace best model 
maintained earlier with the new one. In the end, the 
parameters of plane model are determined from the 
final best model. 
As above, it’s clearly that RANSAC can only estimate one 
plane for a particular data set. To detect all planes, RANSAC 
algorithm is repeated until no more planes can be found. In each 
time, points that belong to a plane will be excluded from the 
original data. 
2.2 Related work 
Generally, previous work about RANSAC for roof facets 
extraction from LIDAR can be divided into the following 
categories: approach based on position of point (x, y and z); 
approach based on surface normal. 
(Brenner, 2000) introduces RANSAC algorithm to detect planes 
for roof segmentation from a laser scanner DSM with a ground 
resolution of one meter. Results show that RANSAC-based 
approach generates more planar regions than the other two 
algorithms such as normal vector compatibility and contour 
based segmentations. Then, regions are filtered based on a set 
of rules which define several relationships between the normal 
vectors of planes and ground plane edges. However, RANSAC 
algorithm is just taken as a method, and there is less discussion 
on the planar regions extracted by RANSAC. 
A ND-RANSAC (Normal Driven RANSAC) approach was 
proposed by Bretar and Roux (Bretar, 2005) to extract planar 
primitives from raw LIDAR data. Instead of randomly selecting 
points from all data points on roof, initial points (3 points) that 
define a plane are randomly selected from the point sets sharing 
the same orientation of normal vectors. It reduces the number of 
draws and improves the efficiency of RANSAC algorithm. 
Besides, the parameters k and ¢ of RANSAC algorithm can be 
automatically determined by analyzing the distribution of 
normal vectors. A lot of work is done to improve the efficiency 
of RANSAC. 
(Forlani, 2006) introduces a method with a combination of 
RANSAC and region growing to extract roof facets from raw 
LIDAR data. A region growing algorithm based on gradient 
orientation is firstly used to determine roof planar segments, 
     
    
and points within each region are determined whether they 
belong to a single plane by RANSAC. In this paper, RANSAC 
algorithm is used as a robust method to further subdivide the 
sub-regions, while quality on the sub-regions is less discussed. 
RANSAC algorithm tends to detect the best mathematical plane 
among 3D building point cloud even if this plane does not 
always represent a roof plane. In order to overcome this 
limitation, an extended RANSAC algorithm is proposed 
(Tarsha-Kurdi, 2007, Tarsha-Kurdi, 2008). The process of 
RANSAC is improved by adding a limit to the minimum 
number of points and a standard deviation in the final fitted 
plane. Besides, in order to extend the capacities of RANSAC 
algorithm and obtain exact roof planes, the raw LIDAR data is 
converted into DSM. Then DSM generates a point set after a 
simple low-pass filter. This approach can reduce the errors and 
noise of point clouds. In the end, a region growing algorithm is 
used to decide whether the remaining set of points represents 
noise or roof details. 
As mentioned above, RANSAC algorithm is more as a process 
for plane extraction from data set. Besides, as explained in 
Section 1, the estimation of local surface normal is sensitive to 
noise. There is no clear conclusion whether the unstable 
parameters have impact on the reliability of RANSAC. What's 
more, the problems on the planes extracted by classical 
RANSAC algorithm, which have important implications for 
improving quality on roof facets extraction, are less discussed. 
3. EXPERIMENT AND ANALYSIS 
3.1 Test data 
The test data set was captured over Vaihingen in Germany and 
belongs to part of “ISPRS Test Project on Urban Classification 
and 3D Building Reconstruction”. It consists of three areas 
(Figure.1) with various building classes available. 
  
Figure 1. Images of Vaihingen test areas from Google earth. (a) 
Area l. (2) Area 2. 
Area 3 in Vaihingen is purely residential area with small 
detached houses, but most of the architectural features in this 
region can be found in area 1 and area 2. Therefore, area 1 and 
area 2 are selected as the test areas. As shown in Figure 1, area 
1 (Figure 1(a)) is located in the centre of the city of Vaihingen, 
characterized by dense historic buildings with complex shapes. 
Area 2 (Figure 1(b)) is located by the river, featuring with a few 
high-rising residential buildings. 
Digital aerial images, DSM and Airborne LIDAR data are 
available in the test areas. In this experiment, LIDAR data is 
taken as input data, and the others are used as reference. For 
  
   
    
    
   
   
    
   
     
    
   
     
   
   
  
       
      
   
   
   
     
    
    
    
   
     
   
  
  
  
  
   
   
    
   
    
    
   
    
    
   
   
  
fur 
refi 
Inz 
cla