XIX-B3, 2012
iere the detection
ably fail.
lane parameters,
| surface, and the
ces are supposed
ng parts. such as
uface normal ri
. For the reliable
^v, 7 in R? we
iogonal intersec-
xiginates. Thus,
stimated vertical
iraight 3D edges
s adjustment.
for a multi-step
the point cloud,
ch step. parallel
face outlines of
r, constructing a
nstructing à con-
jud.
ithm.
HM
iputation of the
| vectors n; for
uares sense to à
'und and includ-
t data assuming
potnts with less
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
Figure 3: Left view of a detached building. Right Part of the
derived point cloud with points of high curvature values marked
in red
than five neighbors within r. alternatively à five-nearest neighbor
search is performed. Follawing (Berkmann and Caelli, 19941. an
approximation for 11, is obtained from the eigenvalue analysis of
the covariance matrix C; of P, defined by
| Pie
i 1 : t ue
C == Purl N^ | — J LP; ze p 3 i)
iT Fes
with p; € P, and [its centroid. The eigenvector corresponding
to the smallest eigenvalue Ào o£ C is a reasonable esumate of
n,. According to (Pauly et al. 2002), an approximation of the
curvature of Pi- is given by
^o
n= Aa + Ar An
C
ka?
where Ao. A4. and Xs are the non-negative eigenvalues of. C;
(Fig. 31.
For the determination af the vertical direction v. we first per-
form a RANSAC-baæd search. Secondly, we evaluate. points
near straight 3D edpes to obtain additional evidence for the verti-
cal direction.
To compute a hypothesis of the vertical direction, we iteratively
select randomly two distinct points p; and p; and compute the
cross product of their normals vi; — mn; x nj. This random
point pair selection is repeated many times. Since most buildings
have roof areas smaller than the sum of the areas of all walls.
we assume to find more point pairs on orthogonal walls than in
any other combination. Thus, the biggest cluster of hypotheses
corresponds to the vertical direction vo, which is computed by à
least-square fit.
We found that for all major surface variations in architectural
scenes, Le. edges in the point clouds, the upper 3055-quantile
of points with respect to the curvature value 7; is usually a good
estimate, Le. we consider all points with =, > 0.7 + max(r:).
In each iteration of our RANSAC-based search for additional ev-
idence of the vertical direction, we randomly select two distinct
points of thís subset of P. and construct a straight line through
both points. If a sufficient number of points lie close to the line
and if the line goes towards the vertical direction vo determined
above within a tolerance of 20 degrees, we consider the line for
an improved determination of the vertical direction v. The latter
is obtained by applying a least-square fit to all accepted lines.
Detection of Vertical Planes: A major goal of our work is to
determine planar surfaces s, with surface normals n, approxi-
matively perpendicular to v. because these surfaces can be inter-
preted as walls of buildings or facade parts. We segment the planes
by means of a RANSAC-based search (Schnabel et aL. 20071.
1. Randomly select two distinct points p and q fram P.
2. Derive plane hi from p and «qq taking v into account by
iPolyanin and Manzhirov, 2007)
svp, yu—hn TP
hi:| 4 —P. d45-7P? $-—5|-0- 0.
Ur Uu P.
3. Compute the distance of all points in P to li;.
4. Score lis by counting the number of points whose distance
io the plane is smaller than a threshold which is derived from
the metric scale ot P.
The above steps correspond to a single iteration nf the algorithm.
They are repeated for a predefined number of times. The best
hypothesis is selected and refined by à least-squares fit over its
supporting points (Fig. 41. We then look for planes parallel to the
fitted plane by sweeping along its normal vector, Afterwards, we
repeat the RANSAC-based plane detection. to search for planes
with other orientations considering ouly the remainder of the
points of P. To account for that walls in architectural scenes may
not always be perfectly vertically oriented. a final validation step
ensures that ali the detected planes are perpendicular to v within
a tolerance.
xx
Figure 4: Three views on point cloud (blue) In red. the inlier
points of the best plane detected by our RANSAC formulation
(top and center), and inlier points of a detected plane with two
clusters far balcony fronts (bottom).
Determination of the Surface Outline: — While the detected
planes are infinite geometric entities, we are looking for surfaces
sa With finite well defined outlines. For this. we analyze the spa-
tial distribution af all points supporting a plane. First, we remove
147
