a
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
building. In our scheme, buildings are modeled, in a very generic
way, as polyhedral volumes with no overhang and it is shown
that maximal cliques in the compatibility graph supply all the hy-
potheses of buildings that can be deduced from the arrangement
of planes. It thus extends the work of H. Jibrini to the cases where
vertical planes may be present. Before effectively computing all
the solutions by brute force search, some simplifications in the
initial 3D and compatibility graphs are made, based on DEM and
focusing mask, in order to reduce the crippling combinatory that
arise from the maximal cliques problem. Finally, in the set of all
the hypotheses extracted from the compatibility graph, the choice
of the final model is done through a bayesian formulation that en-
ables different kinds of observations to be taken into account (for
instance 3D segments, images, focusing zone). Model complex-
ity and a priori constraints on base primitives such as orthogo-
nality, parallelism, symetry, horizontality are also naturally intro-
duced to balance caricature needs and data adequacy. Geometric
refinement and constraints enforcement are finally performed on
the reconstruction to provide the final result.
Oriented
Facades
i
Planar
>
D "777777 3 me Pate es
=
Arrangement of planes:
r
i
i
[
i
i
|
i 3D Graph
| DEM
i Simplifications «^
i 1
i
| Mask
i Hypotheses generation
+ (maximal cliques)
Constraints
Inferring mam
E
i = Hypotheses
E *
| : Constraints
EZ best model choice CE
Enforcing
cd
Mask 3D Segmenis Images
Figure 1: General overview.
2. 3D PRIMITIVES RECONSTRUCTION
As stated above, a focusing mask is provided to the algorithm
along with a horizontal "ground" facet Js that lies on a plane
z — zg (where z, defines the altitude of the ground) and whose
borders delineates the zone on which reconstruction takes place.
Non vertical Planar patches extraction is performed on a DEM
through a region growing algorithm whose details are given in
(Taillandier and al., 2003). The main characteristic of the algo-
rithm is its ability to integrate image constraints as well as 3D
segments to better delineate the patches.
Vertical planar patches (facades) detection is then performed
from the planar segmentation obtained at the previous step. Im-
age and 3D segments constraints enable indeed to obtain a much
better delineation of planar patches which is used as follows: each
border between two patches that represent an important altitude
gap is considered as a potential facade and polygonised. In the
same way, the borders close to the focusing mask are considered
as potential facades and polygonised. All facades are then ori-
ented, normals pointing towards the outer part of the building.
Whereas previous primitives are considered as base primitives,
3D segments are important in the final choice of the best repre-
sentation for the building thanks to their capabilities to enhance
the structure of the scene. The algorithm used is detailed in (Tail-
landier and Deriche, 2002). Its main characteristic lies in the
use of a true multi view technique for matching between 2D seg-
ments and the propagatation of uncertainty to validate matching
hypotheses. These 3D segments suffer from few errors and some
under-segmentation (roughly 30%) but are very precisely located.
Planar hypotheses (vertical and non vertical) are base primi-
tives for the following. For these primitives, emphasis is put
on exhaustivity and geometric precision. During the generation
of all building hypotheses, it is indeed essential that all impor-
tant planes equations (non vertical and vertical ones) be present
whereas planar delineation is of less importance.
3. MODELS GENERATION
3.1 Hypotheses
In the following, we will assume that all principal non vertical
and vertical planes are detected with emphasis put on geometry.
Erroneous planes are not critical insofar as this condition is met:
they will be filtered out in the model choice step. Furthermore,
all planes are oriented: normals pointing upward for non vertical
planes and normals pointing towards the outer part of the volume
for vertical planes.
Main steps of hypotheses generation and filtering as well as
model evaluation are illustrated on a real exmaple in figure 7.
3.2 3D Graph
A plane arrangement is deduced from the plane z — z, and all
detected non vertical planes and facades, it builds up a 3D graph
of facets. This graph is enclosed in a prismatic volume whose
base is Fs, delimited by z, and a maximum altitude. All facets
of the graph are oriented from the planes they lie on (Figures 3(a)
and 3(b)).
Two adjacent facets are coherent along their common edge s if,
with the notations of figure 2(a):
[s, v1. n1i].[s, va, n3] « 0 (1)
where [a, b, c] stand for the triple scalar product. Intuitively, two
facets are coherent if, assuming the normal points towards the
"exterior" of a volume, the normal direction remains coherent
when switching from one facet to the other one. Figure 2 shows
some counterexamples.
We call admissible surface a continuous polyhedral surface made
of coherent facets, whose horizontal projection on z — z, com-
pletely cover Fs. An edge is said to be locally admissible if either
it belongs to the borders of J£ either there are at least two facets
coherent along it. A facet is locally admissible if it is locally
admissible along its bordering edges. A facet is admissible if it
belongs to at least one admissible surface. Two facets are com-
patible if they belong to at least one common admissible surface.
It is obvious that admissible facets are locally admissible. Once
again, intuitively, an admissible surface keeps a coherent normals
direction along its facets. It can also be shown that, given our
context and especially normals orientations (normals pointing up-
wards for non vertical planes), an admissible surface is a contin-
uous polyhedral surface with no overhang.
3.3 Graph simplifications
In the 3D graph, facets that are locally non admissible are recur-
sively suppressed. These are facets hanging on the lateral and top
parts (not the base that is part of the 3D graph) of the virtual pris-
matic volume. Non vertical facets touching the plane z = z, are
then also recursively removed.
From this point, on any admissible surface, all connected sets of
facets that are not included in plane z = z, are one building
as defined previously. the search for all building models derived
from data boils down to the search for all admissible surfaces. An
admissible surface can however include more than one building
Internai
which n
Before «
be NP-I
facets o
toleranc
some si
focusing
in Figur
3.4 Sc
In this
which g
principl
rini, 20
G. fron
the gray
in the n
not deta
rely on |
is a poly
For eacl
the plan
the resu
that f is
are com
Then fo
patible |
removes
which f.
At the
Ge in wi
links tw
surfaces
way, th
sets of €
are all p
which n
