LASER 
uM 
‘ilsoe)@3dgi.dk 
IS 
canning and ortho 
inates), which are 
1gs, by processing 
ts) extracted from 
ell known Hough 
| if the clusters of 
allel to one of the 
ough Transform is 
mall variations of 
ecting planes are 
rule-based post- 
hms also work on 
is density is low, 
red for defining a 
. Furthermore, the 
ch has introduced 
considered, small 
cornices become 
ifficult to identify 
"a building roof. 
ng, a helicopter 
an acquire point 
veter [Baltsavias, 
ser scannings are 
and [Vosselman, 
| less than a Ixl 
eed for building 
> in low density 
h our progress in 
TION 
: models can be 
ns for building 
>s [Hoover et al., 
ms require the 
lem is that these 
osselman, 1999]. 
and thereby fail 
pective. 
ough Transform 
al, 2003]. The 
ely used in the 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
image analysis field for a large range of applications including 
primitive detection and object recognition. 
2.1 Hough Transform 
Given a point p(X, yp) and the general equation of a straight 
line in slope-intercept form, y, = ax, + b. Infinitely many lines 
pass through (xy, y), but they all satisfy the equation y, — ax, * 
b for varying values of a and b. If a 2D image contains several 
points on a straight line, the lines of these points in parameter 
space will intersect and the position of the intersection yields 
the parameters of the line in the image. 
A problem with describing a line in terms of a slope is that it 
approaches infinity as the line approaches the vertical. A way 
around this difficulty is to use the normal representation of a 
line: x, cos 0 t y, sin Ü - s. 
The general Hough Transform is easily extendable to planes in 
three dimensions. A plane IT € 9?? is uniquely defined by a 
triplet (0, ©, s), where 0 € (0, 2x} and o e (-1/2, 1/2) denote 
the two angles (azimuth and elevation) associated with the 
spherical representation of the plane's unit length normal vector 
n= (ny, ny, n,) and s > 0 denotes the distance from the origin of 
the coordinate system to plane II (Figure 1). The three 
components of n are expressed as follows: 
n, = cos(@) cos(0), n, = cos(@) sin(0), n. ^ sin(q) (1) 
The distance s from the origin of the coordinate system to plane 
[is expressed as s = | n, x + hoy c ng |, which yields: 
s(0, @) = cos(p) cos(0) x, + cos(g) sin(0) y, + sin(@) z, (2) 
z Zz 
  
Figure 1. Parameterization of planes in i". 
Each sampling point p yields a function s(0, @), and the points 
in parameter space where three or more functions intersect, are 
planes spanned by tree or more sampling points. 
The computational attractiveness of the Hough transform arises 
from subdividing the parameter space spanned by 0, ¢, and s 
into so-called accumulator cells (6, qj, s,), with / € {0,1,...,Ng- 
15 1610,15, Nt and £ 5 10,1, NU}, where No, N,, and 
N, are the number of samplings along the axes (0, @, 5). 
If s(0; @) is positive, it is quantified to its closest sampling 
value sy, and the accumulator (8; @. sp) is incremented with a 
weight. Negative values are not relevant, as any plane described 
by a normal vector » and a distance from the origin s, can be 
described by the negative pair -n and -s. 
The result is that cells with highest accumulation, give the 
parameters (0; à, s) of the planes spanned by laser scan points 
in cartesian space. 
2.2 Determining true 3d planes 
Processing the laser scan through the Hough Transform yields a 
huge amount of planes. As earlier mentioned, the method works 
globally on the data and thereby planes can be generated by 
points which in reality are present on different roof surfaces 
having completely different surface normals. 
The strategy that is used when extracting planes from parameter 
space is to start with the accumulator cell with most hits. This 
plane is then evaluated according to its corresponding point- 
cloud using the Projected Cluster-area Test (section 2.2.1). If it 
passes the test, the points representing it are removed from 
parameter space, and again the cell that has most hits will be 
evaluated. If it does not pass, evaluation just moves on to the 
cell with second most hits, and so on. In our case, extraction 
ends when the maximum number of hits is less than 5. 
The importance of removing the point cloud of an identified 
plane appears clearly from figure 3. Here the locations in 
parameter space which are in fact true real world planes are 
marked with arrows, and the numbers are the order in which 
these are identified. When removing the point cloud of a plane, 
the graph in parameter space will change and remaining planes 
will then be more obvious than their initial appearance. 
  
Figure 2. Surface scan in Cartesian Space. 
2: 
Figure 3. Surface of figure 2 Hough transformed to Parameter 
Space. The parameter space is sampled along the 
axes, and the accumulator cells are shown as 
spheres. For illustrational purposes, only cells with 
more than 30 hits are shown. The radius of each 
sphere is proportional to the corresponding number 
of hits in its accumulator.