Stefan Growe 
  
ty represents the number of optional relations between objects. In this way, it can be easily modelled that for example 
a crossroad consists of three up to five intersecting roads. An example for a concept net representing a knowledge base 
is given later. 
2.2 Control of the Analysis 
To make use of the knowledge represented in the semantic net control knowledge is required that states how and in which 
order scene analysis has to proceed. The control knowledge is represented explicitly by a set of rules. The rules for 
instantiation for example change the state of an instance from hypothesis via partial instance to complete instance, if all 
subnodes, which are defined as obligatory in the concept net, have been instantiated completely. If an obligatory subnode 
could not be detected, the parent node becomes a missing instance. Other rules generate hypotheses in a model-driven 
or data-driven way. 
An inference engine determines the sequence of rule execution according to a given strategy. A strategy contains a set 
of rules out of the rule base. For each valid rule a priority is defined to determine in which order the rules are tested. The 
first matching rule is fired. The user can modify the interpretation strategy by changing the priorities and by removing 
or inserting rules to the current strategy. The default strategy prefers a model-driven interpretation with a data—driven 
verification of hypotheses: Starting at the root node of the concept net, the system generates model-driven hypotheses 
for scene objects and verifies them consecutively in the data. Expectations about scene objects are translated into expected 
properties of the corresponding image primitives to be extracted from the sensor data. Suitable image processing algo- 
rithms are activated and the semantic net assigns a semantic meaning to the returned primitives in a data-driven way. 
Interpretation stops, if a given goal concept is instantiated completely or no further rule of the current strategy can be fired. 
Whenever ambiguous interpretations occur, for example if more than one suitable image primitive is found for a hypothe- 
sis, they are treated as competing alternatives and are stored in a search tree. Each node of the search tree (called search 
node) represents a consistent symbolic scene description in form of an instantiated semantic net. To avoid a full search 
a graph search algorithm (here: a modified A* algorithm (Tónjes et al., 1999)) is used which optimizes the search path 
through the tree. The algorithm decides in which order the competing alternatives are investigated. Therefore a quality 
measure is needed that describes the degree of compatibility between the measured object properties and the expectations. 
Tónjes suggests a possibilistic approach for the judgement of a scene description which considers uncertainty and impreci- 
sion of measurements and expectations. 
2.21  Possibilistic Judgement Calculus. A hypothesis that has not yet been tested in the sensor data is neither right 
nor wrong. To model this ignorance a proposition e is judged by two measures of belief: the necessity N(e) describes a 
pessimistic estimation of the belief while the possibility P(e) represents the optimistic value which can be computed from 
the necessity of the contrary proposition N( ^ e) by Eq. (1). The difference between possibility and necessity is called the 
ignorance O(e) (Eq. (2)). In the beginning the ignorance is 1, it is reduced consecutively during the interpretation process. 
P(e) = 1 — N(^0) (1) 
P(e) = N(e) + @(e) (2) 
  
  
N(^e)1 
  
P(e) 
Figure 1: Necessity N(e) and Possibility P(e) 
Imprecision of a proposition, like an imprecise specification of a road width, is modelled by fuzzy sets. Both, the expected 
range of an attribute value, called the hypothesis H, and the imprecise measurement itself, called the evidence E, are repre- 
sented by trapezoidal membership functions p, and p, respectively as depicted in Fig. 2. In order to judge the compatibil- 
ity of hypothesis and evidence, the possibility and necessity are determined according to the combination rules defined 
for fuzzy sets (visualized in Fig. 2). Each attribute of the semantic net is valued in this way. 
A 
4 PH pr 7) PH 1—pE 
PRAE) N(HIE) 
  
  
  
  
  
  
X 
x 
Figure 2: Computation of possibility P and necessity N given the hypothesis H and the evidence E 
The judgement of a node, i.e. an instance, is derived by fusing the judgements of its attributes and its current subnodes. 
The necessity and possibility values of complementary information, like attributes and object parts, are combined by a 
weighted geometric mean. Redundant information, like evidence from multiple sensors regarding the same object, are 
  
344 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.