616 
The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B5. Beijing 2008 
based on a planar feature extraction algorithm. Using the Princi 
pal Component Analysis, the planar parameters of each segments 
are estimated. Each segments are then subdivided into smaller 
areas, which are called in this paper patches. The quality of each 
patch is described using a Least Square Estimation. 
2.1 Segmentation 
Segmentation algorithms group points that have similar proper 
ties under a given homogeneity criterion. Although architecture 
uses many surface types, planar surfaces are prominent in most 
of human made objects. In this paper, the planar surfaces are ex 
tracted using a gradient based range image (Gorte, 2007). This 
method estimates, for each measurement, two angles (9, ip) and 
the distance (p) between the plane the measurement belongs to 
and the origin. This estimation is based on the scan parameters 
and horizontal and vertical gradient images. Regions with similar 
planar parameters {9, <p, p) are considered to be part of the same 
plane, i.e. segment. For the experiments presented in this paper, 
small segments are filtered out from the analysis. Note that this 
segmentation is based on the range image and therefore does not 
take into account the intensity measurements. 
2.2 Patch subdivision 
To have a better insight into the local error behavior and the local 
quality of points of similar scanning geometry, each segment is 
subdivided into small patches of 20 x 20 cm. 
2.3 Data representation 
3D laser scans can be seen as panoramic images, such as the one 
depicted in Fig. 1(a). In this study, planar features of the area are 
extracted and studied. In order to have a better and easier visual 
ization of the experimental results, the point cloud is represented 
as a net view. Fig. 1(c) shows a model of a net view. This type of 
view allows a real 2.5D visualization of the scene in such a way 
that the relative scale is maintained. In the rest of the paper, signal 
variations are considered perpendicular to the planar segments. 
2.4 Point density 
A point cloud consists of a spherical representation of the sur 
roundings, the center of the laser scanner for origin. It provides 
a horizontal angular position a, a vertical angular position /3 and 
a range measurement 7. The point cloud density depends on the 
scan parameters, i.e. the angular resolution, but also on the scan 
ning geometry, i.e. the incidence angle and the distance of the 
object. The point density decreases with increasing range and in 
creasing incidence angle (Lindenbergh et al., 2005). In this paper, 
the local point density is incorporated in the description of the lo 
cal point cloud quality by considering the relative redundancy in 
determining local patch parameters. 
2.5 Incidence angle 
The incidence angle i is defined as the angle between the laser 
beam and the normal of the considered surface. It is known that 
the object surface orientation influences the quality of the point 
cloud data, e.g. (Soudarissanane et al., 2007). In this paper, the 
influence of the incidence angle on the local point cloud quality is 
indirectly incorporated by considering the local noise levels when 
determining local patch parameters. 
2.6 Principal Component Analysis 
A commonly used planar fitting algorithm is the ordinary Least- 
Squares analysis. However, for an important amount of dataset, 
the main drawback of the Least-Squares analysis lies on the amount 
of memory needed. Instead, the Principal Component Analysis 
(PCA) is used on the segments. The linear regression determined 
by a PCA minimizes the perpendicular distances from the point 
cloud to the fitted model (Lay, 2002). The PCA is comparable 
to a Total Least-Squares method (Teunissen, 1991), known to be 
robust to outliers and fast computing. The PCA method deter 
mines the optimum basis, in terms of Least-Mean-Squares-Error, 
in which the data set can be re-expressed, using orthogonal linear 
transformations. 
Principle Consider the set of n points X — [x z ,yi, zt]i= 
that belong to measurements of a planar surface. As described 
in Eq.l, the aim is to find the basis B that transforms the orig 
inal data X into Y. The basis B estimates the best plane that 
minimizes the perpendicular distances from the data to the fitted 
model. 
Y = B ■ X (1) 
Step 1 - The point cloud is first centered around its center of grav 
ity M so that the data set has a zero empirical mean. 
Step 2 - The covariance matrix Cx of the centered data is com 
puted as defined in Eq.2. 
Cx = ~^—XX T (2) 
n — 1 
Step 3 - The eigenvectors V of the covariance matrix Cx and the 
diagonal matrix of the eigenvalues of the covariance matrix Cx 
are computed as in Eq.3 
V~ 1 C X V = D (3) 
Step 4 - The two eigenvectors corresponding to the two highest 
eigenvalues represent the two 2D axes of the fitted model. The 
third eigenvector, which corresponds to the lowest eigenvalue, is 
orthogonal to the first two and defines the normal vector of the 
plane. 
2.7 Error Modeling and quality of the planar patch 
In ordinary Least-Squares analysis (Teunissen, 1991), the linear 
model that fits the best the expérimental dataset is computed. The 
model minimizes the Euclidian norm of the residuals. The error 
is measured as the squared distance from the data to the fitted 
function, along a particular axis of direction. This modeling tech 
nique is not robust for noisy data and the solution provided is not 
necessarily the optimal one. Instead, the solution provided by an 
orthogonal optimization is more suitable to noisy data. 
Let M = (M x , M y , M z ) the center of gravity of the dataset. The 
error ê modeled in Eq.4 for each individual point (xi,yi,Zi) is the 
orthogonal squared distance from the point to the fitted function. 
ê I( x i M x , y% My, Zi Mz) • Âf| i= i,...,n (4) 
For each patch, the Root Mean Squared Error (RMSE) is com 
puted as described in Eq.5, from which the matrix of observa 
tional variances Qÿ is derived as shown in Eq.6 
Qÿ — (Të ■ In (6) 
Incorporating the ae means that the local noise level is used to 
express confidence in how well the local patch points determine