. Istanbul 2004
etween 2D seg-
lidate matching
rrors and some
ecisely located.
re base primi-
mphasis is put
the generation
that all impor-
nes) be present
al non vertical
It on geometry.
ndition is met:
. Furthermore,
for non vertical
t of the volume
ing as well as
in figure 7.
> = zg and all
up a 3D graph
volume whose
ude. All facets
n (Figures 3(a)
mon edge s if,
(1
ntuitively, two
ts towards the
nains coherent
‘igure 2 shows
I surface made
[2 =z, CONl-
issible if either
cast two facets
if it is locally
dmissible if it
icets are com-
ssible surface.
nissible. Once
1erent normals
hat, given our
Is pointing up-
ce is a contin-
ible are recur-
lateral and top
1e virtual pris-
Ne X = zg Ale
nected sets of
one building
10dels derived
e surfaces. An
| one building
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
(a) Planes (b) Initial 3D Graph (c) Initial. simplifi-
cations
(f) After successive
simplifications
(e) Tolerance band
around mask
(d) Tolerance band
around DEM
Figure 3: Main Steps of graph simplification. Schematic view.
(b) some non coherent facets
(a) two coherent facets
Figure 2: facets coherence.
which may be interesüng to overcome focusing errors.
Before exhaustive search of all solutions, which will be shown to
be NP-hard, it is necessary to reduce the number of facets. All
facets of the 3D graph non included in a volume defined by a
tolerance band around a DEM are suppressed. In the same way,
some simplifications are made using a tolerance band around the
focusing mask. Main steps of graph simplifications are recalled
in Figure 3.
3.4 Solutions
In this section, one focuses on search of admissible surfaces,
which gives the solution to our problem as mentioned above. The
principle of maximal stable or independent set is used as in (Jib-
rini, 2002). Thus it is necessary to derive a compatibility graph
Ge from the filtered 3D graph G. The procedure used to derive
the graph C. on which all computations are made are described
in the next paragraphs and illustrated in Figure 4 but proofs are
not detailed for readability. However most of the demonstrations
rely on the property already mentioned that an admissible surface
is a polyhedral surface with no overhang.
For each non vertical facet f of C, all facets whose projection on
the plane of f intersects f are virtually recursively suppressed. if
the resulting virtual graph G is non empty. then it can be proven
that f is admissible and that all admissible facets remaining in G
are compatible with f.
Then for each vertical facet v, all non vertical facet non com-
patible with v as computed before are recursively and virtually
removed. One can thus determine whether v is admissible and
Which facets are compatible with v.
At the end of this process, on can derive a compatibility graph
Ge in which each node is an admissible facet of G and each edge
links two compatible facets. As in (Jibrini, 2002). the admissible
surfaces of G are the maximal cliques of Ge Or in an equivalent
way, the admissible surfaces of G are the maximal independent
sets of Q.. We recall that a clique is a set of nodes of a graph that
are all pairwise connected. A maximal clique defines a clique for
which no node can be added while keeping this property. Con-
Figure 4: Compatibility computations. All admissible facets in
hatched areas are compatible with the blue facet.
versely, an independent set is a set of nodes such that for any
pair of nodes, there is no edge between them. It is maximal if no
more node can be added and it still be an independent set. The
equivalence between admissible surfaces and maximal cliques is
therefore natural: each facet of an admissible surface X is com-
patible with all the other facets of 3 and no facet can be added
since an admissible surface, by definition, covers the whole sur-
face of Fs.
The search for admissible surfaces boils down to a search for
maximal cliques, which is unfortunately a NP-hard problem. One
can however find efficient algorithms to solve for these solutions
(Bron and Kerbosch, 1973) and enable a deep study in our pecu-
liar graphs. Figure 5 illustrates the relation between G, C. and the
search for admissible surfaces.
1-11-14-15-16-5-
Hu 7 13-2-6-9-10-3
- us A » v
4
12
en IIT ke 10
. a à 1-11-14-15-16-
| 1 5-1-8-9-10-3
1-11-14-15-16-
7-8-9-10-3
14 3 2 3
ia 1-11-12-13-2-
3 : à 6-9-10-3
12 9
5
15 7 10
5 = 1-11-12-4-8-
16 i s e 9103
Figure 5: 3D simplified graph G (top-left) and its incompatibility
graph Ge (bottom-left) along with all the solutions, as graphical
representation or as maximal independent set.
4. MODEL SELECTION AND GEOMETRIC REFINING
4.1 Bayesian Formulation
The preceding section exhibits a set of possible hypotheses of
surfaces M. Consider a set of observations D that will be used to
choose the “best” model for the focusing zone. Using a bayesian
formulation, one looks for the model A such that:
M = argmax P(M | D) (2)
MeM
