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
dense 3D data. E.g.. Vosselman (2009) discusses recent meth-
ods which rely on LiDAR point clouds with densities of 20 to
30 points per m from airborne scanners or a ceuple of thousand
points per m^ from terrestrial scanners. For such very dense point
clouds typically 3D information ef each point's neighborhood can
be found by clustering the points or by determining planar surface
patches. Yet, it is not suited for noisy and not very dense point
clouds derived from image matching.
Vosselman and Klein (2010) review point cloud segmentation,
Le, the detection of subsets of points which form geometric prim-
tives, such as planes, cones, cylinders, or tori. They group the
methods for point cloud segmentation into three different types:
The first type is based on the Hough transform (Hart, 2009),
where the hest hypothesis is detected in a derived parameter
space. It is often used wheu searching for planes and other ge-
ometrie primitives with a low-dimensional parameter space (Vas-
selman and Klein. 2010) The second type consists of all ap-
proaches which reconstruct surfaces based on edge detection or
region growing (Vieira and Shimada, 2005). Again. neighbor-
hood information is used to determine normal vectors at each
point. which are used to estimate surface curvature values. Also
the recent work by Schindler and Fórstner (2041? falls into this
category. It suffers from gaps in the data and too much noise.
Thus, the algorithms often converge showing errors caused by Lo-
cal inconsistencies in the data. The last group contains all ap-
proaches based on variants of RANSAC (Fischler and Bolles,
1981). where minimal subsets of points are randomly drawn to
generate a primitive, After several iterations, the best model is
selected. An efficient approach which successively detects vari-
ous primitives in large point clouds has been proposed by Schn-
abel etal. (2007). This approach does not rely on dense data, and.
therefore, seems to be adaptable to our problem.
If the vertical direction of a scene is known, the detection of verti-
cal planes can be enforced. The determination of vanishing points
from images has been an active topic of research in photogram-
metry and computer vision (Rother. 2000; Almansa et al., 2003;
Schmitt and Priese, 2009: Fürstner, 2010). The main idea is that.
on the image plane. line segments, which are projections of par-
allel lines in object space. intersect in unique points. Yet these
above algorithms will probably fail for less regular data, such as
old timber-framed buildings (Fig. 1). Additionally. the accuracy
of the vertical direction derived in image space is limited when
projected in 3D by the accuracy of the camera calibration. Op-
posed to the work above, Hansen (2007) directly detects the ver-
tical direction on 3D point clouds yet the approach only works
on Legoland scenes without any less regular objects such as. e.g.,
tees, cars, and people. Furthermore, the approach by Hansen
(2007) assumes a ground plane, which is often not valid. For
our application, the detection of the vertical direction should be
invariant to architectural imperfections, such as when doors, or
the timber-frame and windows are not perfectly aligned with the
vertical direction.
Several approaches make use of LiDAR point clouds to derive
detailed facade models for downtown areas (Becker and Haala.
2008; Hernandez and Marcotegui. 2009; Hohmann et al. 2009).
The LiDAR points are used to detect the principal plane which
is interpreted as the facade and facade components such as win-
dows, stairs. or oriels are segmented. All these approaches are
not directly applicable to the detection of detached buildings, but
will be considered, when we will refine the building models.
3 OVERVIEW OF THE ALGORITHM
The input to our system is an unstructured 3D point cloud P with
points p; from image matching (or LIDAR) Ets output is a set
146
Figure 1: Image of a timber-framed building, where the detection
of the vertical direction in image space will probably fail.
of connected rectangular surfaces sg, Le. the plane parameters,
the description of the rectangular outline of each surface, and the
adjacency graph between the surfaces. The surfaces are supposed
to represent building walls and dominant building parts. such as
balconies and oriels.
In our workflow (Fig. 2) we first estimate the surface normal ny,
and the surface curvature value r; forevery point. For the reliable
computation of the vertical direction v — (v,, vy, v. )? in 8? we
suppose à prevalence of vertical walls and orthogonal intersec-
tions in the architectural scenes from which P originates. Thus,
v is derived from the biggest cluster of locally estimated vertical
directions, improved by an analysis of points on straight 3D edges
in the point cloud, and refined using least-squares adjustment.
The vertical direction is used as a constraint for a multi-step
RANSAC-based detection of vertical planes in the point cloud,
assuming a known metric scale over P. In each step. parallel
planes are detected by plane sweeping and the surface outlines of
these planes are estimated by line sweeping.
Finally, the surfaces are connected to each other, constructing a
surface adjacency graph. This is necessary for constructing a con-
sistent geometric polyhedron within the point cloud.
3D point claud
| normal vectors |
| curvature values |
direction
vertical planes
surface outlines |
surface adiaceney graph
Figure 22 Workflow of proposed algorithm.
4 DETAILS OF THEALGORITHM
Vertical Direction Computation: For the computation of the
vertical direction, we first determine the normal vectors n; for
each point p; by fitting the best plane in least-squares sense to a
local neighborhood P, with radius r centered around and includ-
ing pi. The value of r is derived from the input data assuming
à known metric scale of the point cloud P. For points with less
Intern.
Figure X
derived p
in red
than five :
search is
approxim
the covar:
with p; €
to the sm
D. AC
curvature
whe Ie, (
(Fig. 3.
For the «
form a RE
near strai
cal direct
To compl
select rai
cross PIC
point pai
have roo
we assu
any othe
Corm spo:
least-squ
We foun
scenes, I
of points
estimate.
In each il
idence ©
points ol
both poit
and if the
above wi
ian impr
is nhtain
Detectio
determin
matively
preted as
by mean
1. Ra