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