lon, 
d in 
are 
ots. 
re- 
the 
est. 
t of 
tan- 
ists 
ons 
for 
cute 
sis 
the 
slot 
rgu- 
the 
ts a 
osi- 
) be 
 in- 
the 
> of 
sary 
‘the 
d in 
tion 
hre- 
yub- 
g to 
utes 
lots 
, an 
"ous 
ince 
t of 
1 be 
us 
)n is 
ions 
the 
tili- 
con- 
'eta- 
ogy 
td3 
ault 
1g a 
lefi- 
ina- 
ical 
fini- 
also 
tion 
for the case of a successful instantiation even if dot d3 is 
absent. If instantiation of several combinations of in- 
stances is possible, the one with the largest number of 
necessary parts will be prefered. 
  
Necessary Parts value: {(T, D1, D2, D3, D4, D5) OR 
(T, D1, D2, D4, D5)} 
Structure Relations value:  ((SR1, SR2, SR3, SR4, SR5) OR 
(SR1, SR2, SR4, SR5)} 
CF value: [(sri & sr2 & sr4 & sr5) 
ifFalse: [cf = 0] 
ifTrue: [sr3 isNil 
ifTrue: [cf = 100] 
ifFalse: [sr3 
ifTrue: [cf = 100] 
ifFalse: [cf - O]]]] 
arguments: ((SR1), (SR2), (SR3), (SR4), (SR5)) 
  
  
  
Fig.9: Section of concept definition coniferous tree that 
includes topological alternatives. 
6.3.2 Definition of Recursive Structures For analysis 
of recursive structures like contour lines, a special concept 
definition exists, which is based on exactly two necessary 
parts. The first part describes the non-recursive basic ele- 
ment. With its help, the recursive structure is defined. In 
the case of a dashed line, this concept describes an in- 
dividual line segment. The second part contains a reference 
to the concept itself and therefore represents the recursive 
structure. 
6.3.3 Introduction of Constraints So far an assump- 
tion was made during instantiation process that instances 
of concepts acting as necessary parts of the superior con- 
cept are already existing. To obtain flexibility in image 
analysis it is not always necessary and desirable to make 
this assumption. If, for example, an instance of the concept 
connection line is necessary to process the instantiation of 
à concept, it is normally not possible to generate all in- 
stances of connection line in advance for the current map 
scene. Trying to do this would result in an overflow of the 
instance base and an unacceptable long processing time. 
But in general, it is not necessary to generate all instances, 
because only one of them is of interest and this one de- 
pends normally on the other necessary parts concerned. To 
solve this problem constraints are introduced supplemen- 
tary to the restrictions of necessary parts. These con- 
straints describe properties which the necessary part has to 
possess for successful instantiation. These properties 
therefore depend on the other necessary parts concerned in 
contrast to the properties forced by the restrictions. If 
constraints are used, it must be guaranteed that the neces- 
sary parts determining the desired properties are inde- 
pendent of the corresponding parts. Otherwise consistency 
of the definition is violated. To distinguish between con- 
cepts that may be instantiated in a direct manner and those 
that are instantiated due to constraints, an additional slot 
has been introduced. This slot defines the type of the 
concept. The possible entries in the facette value of slot 
type are normal and goal driven. Fig. 10 shows an example 
of the definition of a constraint. 
In this example the instantiation of the concept connection 
line is based on the information given by the necessary 
parts NP1 and NP2. Therefore, only solutions satisfying 
the constraints CI and C2 are considered for instantiation. 
The constraint C1, for example, forces the start coordinate 
start given by facette variable of slot C1 to be identical 
with the center coordinate center of NP1 given by facette 
reference value. The identity of both values is enforced by 
the entry "=" of facette operator (also possible: <, >, 2, <). 
Analogously C2 specifies the end coordinate of the desired 
connection line. 
661 
  
Necessary Parts value: {(NP1, NP2, NP3)} 
NP1 value: Line Segment 
restriction: nil 
NP2 value: Line Segment 
restriction: nil 
NP3 value: Connection Line 
restriction: nil 
constraints: {C1, C2} 
C1 operator: = 
variable: Start 
reference value: (NP1 Center) 
C2 operator: = 
variable: End 
reference value: (NP2 Center) 
  
  
Fig.10: Example for the definition of a constraint. 
7. CONTROL MODULE FOR 
KNOWLEDGE-DIRECTED IMAGE ANALYSIS 
The control module supervises and controls instantiation 
of concepts. Two operation modes exist. In the interactive 
mode a concept of interest is given by the user as a goal. 
Thereupon, the control module determines the minimal set 
of necessary concepts at the lowest hierarchy level. Based 
on this set the instantiation of superior concepts is per- 
formed successively until the goal concept is reached. In 
the automatic mode the instantiation is obtained in a bot- 
tom-up manner using all instances at the lowest hierarchy 
level. Thus, all concepts of superior layers will be instan- 
tiated. In both modes the instantiation of a single concept 
is performed in accordance to the methods described in the 
previous sections. 
Normally instantiation of a concept results in several in- 
stances. Therefore, the control module is able to handle 
different alternatives during analysis. This feature is im- 
portant because normally a definite interpretation of a map 
scene requires consideration of the context of surround- 
ings. Existence of different alternatives leads to instances 
that are in competition with each other. For management 
of the interpretation hypotheses a graph controlled by a 
belief-revision-algorithm (Puppe, 1987) is used. This al- 
gorithm is based on aspects of truth-maintenance-systems 
(Doyle, 1979; deKleer 1986a, deKleer, 1986b; Dressler, 
1988; Petri, 1989). The instance that is relevant for further 
instantiations is selected by an evaluation algorithm. The 
selection depends on the type of concept. For all types the 
certainty factor cf is used. For recursive concepts the num- 
ber of non-recursive basic elements is considered. In case 
of recursive and simultaneous goal driven concepts the 
constraints satisfied by the actual instance are compared 
to those of the underlying preceded hypothesis. 
8. KNOWLEDGE-DIRECTED INTERPRETATION 
SUPPORT FOR HIGH COMPLEXITY MAP SCENES 
Problems in map interpretation may occur if the raster 
image is too complex for the context-independent raster 
processing methods presented so far. In such cases of 
conflicts, the instantiation of concepts of map objects may 
not be possible because of lack of appropriate structure 
primitives. A possible reason for complexity may be the 
overlapping of different map symbols. For the solution of 
this problem a hypothesis is generated, that states which 
map symbol is expected in the specific image region (refer 
to concept virtual continuation of a contour line in section 
6.1). Hereby, the actual situation of instantiation is the 
decisive criterion. Based on this hypothesis a more specific 
raster analysis method is used to detect the expected sym- 
bol in the corresponding color layer and image region of 
interest. Depending on this analysis the subsequent instan-