jer 
ter 
‚it 
out 
ner 
to 
)n- 
for 
ins 
the 
d y 
ice 
ler. 
ipe 
uc- 
to 
80- 
ers 
ine 
TO- 
the 
TO- 
put 
ip- 
lial 
irst 
ine 
ess 
ine 
ine 
les. 
| to 
els 
] in 
the 
the 
tly 
and 
ted 
| or 
age 
go- 
be 
ge. 
ved 
in a vector data refinement step. This can be obtained 
applying a set of rules. In a first step short branch vertices 
(cf. Fig. 4, vertice A) are removed. Subsequently corre- 
spondingV-shaped arrangements of vertices (node B) are 
straightened by deleting the center node. After refining the 
vector data, the nodes and vertices will be stored in the 
primitive base. 
  
  
  
  
  
Fig.4: Illustration of vector refinement. 
5. BASIC IDEA OF KNOWLEDGE-DIRECTED 
IMAGE ANALYSIS 
The attributed structure primitives extracted by the raster 
image processing methods described above are the data 
source for subsequent analysis strategy. The description 
level of the analysis is based on a hierarchical structuring 
of the map with map objects and relations between these 
objects. These relations may be of topological type as well 
as of thematical type. Associative nets (Quillian, 1969; 
Brachman, 1979; Minsky, 1979; Hayes, 1979) based on 
frames are used as a formalism for representation of knowl- 
edge which is characterized by these objects and their 
relations. 
For the following description of the system it is important 
to distinguish between map objects representing more or 
less complex cartographic facts (e.g. terrain area) and 
simple raster objects. The structure primitives are defined 
at the lowest hierarchy level. At higher levels a map object 
represents the composition of one or more map objects of 
the lower levels of abstraction. 
Knowledge-directed image analysis tries to attach a mean- 
ing to an image scene. One way of doing so is to use an 
explicit model of what the image can contain and then 
construct a mapping between the model and the image. 
Hereby the model represents the necessary a priori knowl- 
edge. Since a particular image scene is only an instance of 
the class of possible image scenes, the model must be in 
some sense larger than the image. That is, a useful model 
of the domain of the image typically contains a large 
amount of information on possible image contents. The 
mapping processed during analysis normally uses only a 
small part of the model. This surplus of knowledge 
guarantees a flexible image interpretation. 
  
Attributed dedos. 
structure primitives M 949 49 to eR 
Instances i { 
(low hierarchy level) A A A -N * $ i * 
0606». 960v». 0800 08000 errore eee e 
l -" 
  
Instances 
(high hierarchy level) 
  
  
  
  
Fig.5: Example of a hierarchical map description 
(coniferous forest). 
Fig. 5 shows the principle of the hierarchical map descrip- 
tion by example of a coniferous forest. The map object 
659 
coniferous forest consists of a combination of coniferous 
tree objects, forest border and the forest area signature. 
Each coniferous tree object is again described by a com- 
position of an inverted V symbol and several dots in a 
defined topology. The forest border is composed of a 
sequence of dots. Hereby, the area signature, the dots and 
the inverted V symbols are the attributed structure primi- 
tives. 
6. KNOWLEDGE REPRESENTATION 
6.1 Concepts and Instances 
  
The a priori knowledge necessary for map interpretation 
is provided by a model acting as long term memory. As 
mentioned previously, an associative net serves as knowl- 
edge representation scheme. The basic structure of the net 
is the data structure concept. A concept contains the inten- 
sional description (Sagerer, 1985) of a term which is nec- 
essary for the model of the given problem. The intension 
of a term is the abstract definition of its meaning. It in- 
cludes a characterization of properties which must be 
satisfied by a concrete fact to be valid for this term. On the 
other hand the extension encloses the set of all concrete 
facts of a case which satisfy the definition of meaning. The 
elements of the extensional set of a term are called in- 
stances of the corresponding concept. For applications of 
map interpretation, the concepts represent cartographic 
objects as well as abstract notions necessary for solving 
conflicts in interpretation. As an example the concept vir- 
tual continuation of a contour line may be considered. This 
clause characterizes connections of contour lines that can- 
not be derived from the existing attributed structure primi- 
tives in case of overlapping line segments. 
In the present state of our system the intensional descrip- 
tion of a concept is given completely by necessary parts, 
structure relations and attributes. For generation of an 
instance of a concept the following conditions have to be 
considered: 
- Instances of concepts have to be made available. These 
instances are related to the concept to be instantiated 
by the relation necessary part. 
- The defined structure relations have to be satisfied. 
If both conditions are met, the valuation of the possible 
instance is performed. This valuation is a measure for the 
similarity of the instance with the intensional description, 
i.e., the concept. The valuation represents the certainty 
factor (cf) for the membership of an instance to the set of 
realizations of the concept. Thus, the valuation depends on 
the actual problem and is therefore a part of the a priori 
knowledge given by the model. The procedure to obtain 
the valuation of an instance has to be defined within the 
concept. The instantiation is successful if the valuation is 
above a threshold cfth also defined within the concept. In 
this case, the attributes of the instance will be evaluated 
using information in the concept. The instance is then 
stored in the instance base, which acts as a short term 
memory. A reference to the instance is also made available 
within the concept. 
Concerning evaluation of the structure relations, attributes 
and valuations, the model encloses declarative knowledge 
as well as procedural knowledge, i.e., algorithms. Using 
the procedural knowledge, a quantitative characterization 
of the qualitative facts of a case represented by the asso- 
ciative net may be performed. For this purpose, the struc- 
turing of the instances is analogous to the one of the 
concepts. The procedures of the model correspond to con- 
crete values of the instances.