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 
performed clustering based on normal vectors by applying the 
k-Means algorithm and then extending the clusters to the edge 
points to form segments while Kim and Medioni (2011) used a 
hierarchical approach to cluster normals. Bae et al. (2007) used 
an edge detection approach for segmentation where local 
curvature was employed for detection of edges. Level set 
approaches have also been used for curve propagation and 
segmentation (Kim and Shan, 2011). 
Vertical wall extraction is attractive to some applications. Oude 
Elberink (2008) compared positional differences between roof 
outline and ground plans. The result showed that a 3D building 
model can generally not be correctly formed by simply 
projecting roof edges to the ground to form the vertical walls. 
However, very limited efforts have been made so far to 
explicitly derive building walls from airborne LIDAR data. 
Dorninger and Nothegger (2007) introduced data mining 
approach for clustering wall seeds in feature space. Rutzinger et 
al. (2009) used a Hough transform segmentation algorithm for 
extracting walls from both airborne and terrestrial mobile 
LIDAR data and compared the accuracy of the two dataset. 
Currently, mobile LIDAR data is being widely used for vertical 
walls reconstruction (Hammoudi et al., 2010; Rottensteiner, 
2010). 
3. METHODOLOGY 
The proposed approach for wall detection and reconstruction 
consists of three stages, as indicated in Figure 1. One of the 
main requirements of the developed method is automated 
identification and location of wall points via improved point 
cloud segmentation and classification. Following this stage, 
wall surfaces are formed. The walls are then reconstructed and 
their extents and corners are determined through geometrical 
and topological modelling that is constrained by roof structure. 
  
Airborne Region Segment Wall 
LIDAR Growing |—>| Classification Reconstruction 
Data (Section 3.1) (section 3.2) (section 3.3) 
  
  
  
  
  
  
  
Figure 1. Workflow of the proposed methodology. 
3.1 Segmentation 
The developed point cloud segmentation approach follows the 
region growing principle. The major contributions of the 
presented work include optimal determination of search range 
and robust selection of seed points. In the approaches of region 
growing, the selection of seed points and the determination of 
the search radius are critical (Brenner, 2000; Vosselman and 
Dijkman, 2001). Randomly selected seed points may result in 
incorrect results or too many unnecessary small segments. A 
larger search range may pick up points outside the segments 
under consideration. A smaller search range seems safe, but it 
may miss points, particularly when the density of the point 
cloud is low or the distribution of the points is irregular. To 
avoid such problems, an approach to adaptively determine the 
search neighbour from the point cloud has been developed. The 
search range varies according to the local density and 
distribution, and it increases with low density. In addition, the 
selection of seed points is determined via a Principle 
Component Analysis (PCA) process. Only the points that 
exhibit high planarity in a local area are selected. 
Adaptive neighbourhood searching. Either k-Nearest or Fixed 
Radius method, or combination of both, is generally employed 
for searching for neighbouring points. These methods work 
well when the point distribution is regular. However, their 
114 
performance can be poor when point density varies (Rutzinger 
et al., 2009). In this paper, adaptive method is developed to 
accommodate point distributions and decide suitable 
neighbourhoods. 
Let D = {p;li € [1, n]} be whole point cloud with n points and 
Pc € D be the point whose neighbourhood is to be decided. 
Firstly, a set of k-nearest points N, from p, is determined. Then, 
the largest distance d,,,, between p, and p; in N, can be 
determined among its k neighbours: 
dmax = arg max (distance(p; pc)) , i = 1,2,..,k (1) 
To optimal the neighbourhood selection scale, dynamically 
scale r is then decided as r — d,,4,/3 (Pauly 2002) and thus the 
neighbours of p, can be represented as 
Nz {p;lP; € Ne distance(p; p.) « r} (2) 
Thus, the neighbour N ensures the uniformly of neighbourhood 
distribution and optimal search range. Figure 2 shows four cases 
of neighbourhood determination. The dashed circles represent 
the range of the k-nearest points. The determined neighbours are 
shown in circles of solid circles. The LIDAR point densities on 
roofs and the ground are high and the distribution of the points 
demonstrates a quite regular pattern. Therefore, the search 
ranges on the roof and the ground are similar and small. Wall 
points are sparse and the distribution varies with the flight line 
and scanning directions, so a larger search ranges is adapted. An 
interesting performance is seen near the intersection of wall and 
ground, as shown in the lower right of Figure 2. The k-nearest 
or fixed radius methods may result in a large amount of ground 
points (see the dashed circle). This kind problem can be avoided 
by the proposed adaptive search range approach (see the solid 
circle). 
  
Figure 2. Neighbourhood determination. 
Local surface variation. A planar surface can be estimated 
within the determined neighbourhood and its planarity can be 
assessed by PCA. The PCA of a set of 3D LIDAR points yields 
the principal vectors describing an orthonormal frame (vo, vi, v2) 
and the principal values (Ao, 44, A7) with Ap<A4< Az. The PCA 
decomposition of a set of LIDAR points can be calculated by 
singular value decomposition of the 3 x 3 covariance matrix of 
the points. The covariance of X;and X; is defined as 
cov(X, Xj) = ZR) (3) 
Here, p; denote the mean of X;, and n is the number of LIDAR 
points in the neighbourhood. 
For planar points, the variances will appear only in two 
orthogonal directions after PCA transformation. That is, Ag is 
zero 
on t] 
Tak 
accc 
than 
The 
diffe 
data 
repo 
An 
con: 
The 
Figt 
relai 
Figt 
con: 
poin 
not. 
by tl 
See 
Hov 
inst: 
may 
veg: 
neig 
Reg 
poir 
PC/ 
of | 
neig 
poir 
plar 
Foll 
sear 
proc 
neig 
iterz 
regi 
segi 
poit 
segi 
3.2 
The 
feat