VW Xy
m m XV
Ansgar Brunn
symmetriced. We call the resulting graph a polymorphic graph (Fuchs and Fórstner, 1995). In figure 2(a) the polymorphic
graph of one side of a cube is shown. The graph of the complete cube consists of eight 0-cells, twelve 1-cells and six
2-cells.
2.2 Simplicial complexes
CW-complexes are a very general method to describe topology, esp. they are not limited to a number of cell types.
Simplicial complexes can be viewed as a specialization of the CW-complexes, where 2-cells are triangles. The basis
elements of this representation are called simplices. They are shown in figure 2(c) up to order two. On the one hand
the simplification of the complexity of the topological boundary polygon to just three sides limits the complexity of the
2-cells. On the other hand it provides an easy access to the shape of the 2-cells. Analogously to the CW-complex we
define a polymorphic graph on the simplices. Figure 2(b) shows the polymorphic graph of one side of a cube in simplex
representation. Simplicial complexes are widely used in the approximation of triangulated surfaces: e. g. Halmer et.
al. (Halmer et al., 1996) use simplicial complexes for the approximation of surface models, but they stick to geometric
triangles of a triangulation of the surface. In the following we focus on simplicial complexes.
3 INTERPRETATION
In our context interpretation means classification of the simplices of the building representation by complexes. In the two
step scenario of separate interpretation and reconstruction the interpretation links the observations with the reconstruction
(cf. fig. 3). Knowing the likelihood functions the classification can make use of the observations.
building
model
I | |
y M Y
observations > classification > reconstruction
LAS n
model
m
a e
o e
= 5
Q D
= e
= =
Figure 3: Principle of classification and reconstruction paradigm.
3. Principle
The interpretation is done by classification using statistical models, which need to be known a priori or automatically
learned (cf. sec. 3.3). To find a final classification means to search for a set of classes which have a maximal probability.
To reduce the complexity of this problem, which in general is exponential in the number of possible classes for each
random variable, we assume only local dependencies between neighboring random variables. Therefore we only need
local statistical models.
We establish a Coupled Markov-Random-Field (CRF) (Li, 1995), which consists of three random-fields, one for each
simplex type. This is equivalent to associate a random variable s to each node of the polymorphic graph, which represent
vertices, edges and triangles,
v,e,1 — 8
The classes for possible classifications are explained in the next section.
Inside the CRF each random variable s; is classified. This is achieved by finding that class which leads to the maximal
probability for the random variable s;.
$; — arg max P(s;)
Si
The probability distribution P(s;) is deduced using Bayes’ Theorem
P (si|y;) « P(y;|si) P(si)
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 119