Geometric Reasoning with
Uncertain Polygonal Faces
Jochen Meidow and Wolfgang Förstner
Abstract
The reconstruction of urban areas suffers from the dilemma
of modeling urban structures in a generic or specific way, thus
being too unspecific or too restrictive. One approach to over-
come this dilemma is to model and to instantiate buildings
as arbitrarily shaped polyhedra and to recognize man-made
structures in a subsequent stage by geometric reasoning.
Thus, the existence of unconstrained boundary representa-
tions for buildings is assumed. To stay generic and to avoid
the use of templates for pre-defined building primitives, no
assumptions for the buildings’ outlines and the planar roof
areas are made. Typically, roof areas are derived interactively
or in an automatic process based on given point clouds or
digital surface models. Due to the measurement process and
the assumption of planar boundaries, these planar faces are
uncertain. Thus, a stochastic geometric reasoning process
with statistical testing is appropriate to detected man-made
structures followed by an adjustment to enforce the deduced
geometric constraints. Unfortunately, city models usually do
not feature information about the uncertainty of geometric
entities. We present an approach to specify the uncertainty of
the planes corresponding to the planar patches, i.e., poly-
gons bounding a building, analytically. This paves the way to
conduct the reasoning process with just a few assumptions.
We describe and demonstrate the approach with real data.
Introduction
Motivation
For the representation of urban scenes specific or generic
models can be used, leading to the classical dilemma of being
too unspecific or too restrictive (Heuel and Kolbe, 2001). Spe-
cific models comprise object knowledge, for instance about
man-made structures, and can therefore directly be related to
buildings. Parametric models, for instance, are often utilized
for the representation of buildings, although they are unable
to represent objects of arbitrary shape. Therefore, the shape
of complex man-made solids should be described by generic
models, e.g., polyhedra utilizing boundary representations.
In the context of 3D city modeling such representations are
used, but actually often obtained by converting parametric
model instances.
Current research addresses the challenge of introducing
building shape knowledge without being too restrictive. In
Nguatem and Mayer (2017), for instance, contiguous patches
are derived from point clouds using a divide-and-conquer
based algorithm, and polygon sweeping is employed to fit
predefined building templates. The detection of global regu-
larities can be achieved by clustering or hierarchical decom-
position of planar elements, followed by a re-orientation and
re-positioning to align the patches with the cluster centers,
cf. (Zhou and Neumann, 2012; Verdie
et al
., 2015). Such ap-
proaches require specific thresholds and do not exploit the
uncertainty of the extracted elements. In Xiong
et al
. (2014
and 2015), the topological graph of identified roof areas is
analyzed to instantiate and to combine pre-defined low-level
shape primitives. Parametric models are avoided for the sake
of flexibility. The result is a boundary representation with ver-
tical walls and horizontal ground floor.
The instantiation of the building models is based on
observations which are inherently uncertain; this holds for
automatic and semiautomatic acquisitions. The uncertainty
results from the measurements, wrong model assumptions,
and wrong interpretations or inferences. In the context of
matching building models with images this issue is pointed
out in Iwaszczuk
et al
. (2012). Thus, a geometric reasoning
to detect and to enforce man-made structures should take
these uncertainties into account. In Meidow (2014) the use of
pre-defined primitives is replaced by the recognition of man-
made structures, i.e., geometric relations between adjacent
roof areas.
Geometric relations such as orthogonality or parallelism
are found by statistical hypothesis testing, and then enforced
by a subsequent adjustment of the roof planes.
An automatic reconstruction of buildings is most often
based on airborne laser scanning data or aerial images. This
offers the possibility to specify the uncertainty of roof areas:
The uncertainty of the planes corresponding to the roof areas
is a secondary result of the plane fitting procedure. However,
if the input for the reasoning process is already a generic
representation of the building, e.g., an arbitrary shaped poly-
hedron given in the CityGML data format, the information
about the acquisition and its uncertainty is lost since 3D city
models usually do not contain this information. In this case
the uncertainties of the planar patches bounding the building
have to be derived from the given boundary representation of
the polyhedra. This is the main contribution of this paper.
Contribution
We provide analytical expressions for the uncertainty of
planes corresponding to planar patches represented by 3D
polygons. These patches bound buildings as provided by 3D
city models. By doing so, we consider multiply-connected re-
gions, i.e., polygons or patches with holes, too. Examples are
roof areas with openings for dormer windows and buildings
with a flat roof around a courtyard.
The approach is based on closed form solutions for the
determination of moments for arbitrarily shaped 2D poly-
gons (Steger, 1996a; 1996b). The sums of point coordinates
occurring in the normal equation matrix for plane fitting are
Jochen Meidow is with the Fraunhofer Institute of Optronics,
System Technologies and Image Exploitation (IOSB)
(
)
Wolfgang Förstner is with Lyles School of Civil Engineering,
Hampton Hall, 4122, 550 Stadium Mall Drive, West Lafayette,
IN 47907-1284.
Photogrammetric Engineering & Remote Sensing
Vol. 84, No.6, June 2018, pp. 393–401.
0099-1112/18/393–401
© 2018 American Society for Photogrammetry
and Remote Sensing
doi: 10.14358/PERS.84.6.393
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
June 2018
393
