2 ROAD MAP UPDATING
Updating (road) maps is usually considered a two step proce-
dure: first it is verified whether the roads in the old database
are still present in the imagery and, second, the new roads are
mapped and roads that no longer exist are removed from the
database. Looking closer at each of these two steps, many
aspects can be discerned.
Verification involves the comparison of the representation of
a road in a database (GIS) with the road appearance in the
image. The common GIS is vector oriented and also may be
generalised. In order to make the two object representations
comparable, features are usually extracted from the image.
The hypothesis that the features of the image and the GIS
originate from the same road is subjected to a test. This
test will require information about the uncertainty of the two
object descriptions that may be obtained through error prop-
agation in the feature extraction (and generalisation) process.
Already this first updating step includes many aspects of un-
certainty. A further analysis will be given in section 4.
Mapping new roads is even more complex than the verifica-
tion step. If the hypothesis of the verification step is rejected,
we only conclude that something has changed. The kind of
change, e.g. a new road exit, a new fly-over, an extra lane,
a new pavement, or a removed road part, is yet unknown.
Using the features in the image, the context of the old GIS,
knowledge related to all processing steps of both the image
and GIS features, and generic knowledge about road net-
works, hypotheses have to be generated about the type of
change. Some of these hypotheses (new exit, new fly-over)
may, if accepted, lead to the detection of new parts of the
road network. After this detection the road sides will need to
be outlined and the consistency with the already known part
of the road network needs to be verified [Gunst and Hartog,
1994]. As with the initial verification, all data used in the
second step of the updating process can be erroneous and
affect the quality of the final interpretation result.
Although very complex, updating of road databases may still
be considered a little easier than updating maps with e.g.
houses. It seems fair to assume that new roads are always
connected to the roads in the old database. Therefore, junc-
tions of the new roads with the old network should be de-
tectable in the verification step. This gives a strong indication
about where to look for new roads.
3 UNCERTAINTY IN DATA
When photogrammetrists talk about uncertainties they usu-
ally do so in terms of standard deviations of Gaussian dis-
tributed variables. Yet, when dealing with image interpreta-
tion tasks it soon becomes clear that many aspects of uncer-
tainty cannot be described in those terms.
In this section we will first review the most popular ways of
representing uncertainty in data. Many of the newer concepts
have been developed in the Al literature and are related to
reasoning problems.
In the last part of this section quality descriptions of (GIS)
data are discussed. It shows that there is a variety of as-
pects of data quality that all affect the uncertainty about the
correctness of the data.
3.1 Representations of uncertainty
eo Probabilities
910
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
The best known representations of uncertainty are, of
course, probabilities (and probability densities). In the
Bayesian formalism, there are three basic axioms of
probability theory regarding the belief measure that is
attached to propositions [Pearl, 1988, Fine, 1973]:
0<P(A)<1
P(Sure proposition) = 1
P(AV B)=P(A)+P(B) if A and B
are mutually exclusive.
From these axioms it also follows that:
P(A)+P(HA) = P(AV-A)
= P(Sure proposition) — 1
l.e., a proposition and its negation must be assigned a
total belief of 1.
Bayes introduced the concept of conditionalisation of
the belief in a proposition A by the knowledge or con-
text B
P(A, B)
P(B)
These conditional probabilities play a very important
role in all kinds of reasoning processes.
P(A[B)
Probabilistic networks
Probabilistic networks [Pearl, 1988] also use the above
defined probabilities and are therefore not a different
way of expressing uncertainty. Instead they are use-
ful graphical representations of the dependencies be-
tween propositions. The nodes of these graphs are the
propositions and the links between the nodes show the
dependencies. Two basic network types are often en-
countered:
+ Markov networks: A Markov network is an undi-
rected graph. The links of this graph represent
symmetrical probabilistic dependencies.
+ Bayesian networks: A Bayesian network is a di-
rected graph. The arrows of this graph represent
causal influences between the propositions. The
Bayesian network may not contain cycles.
Bayesian networks are very attractive for reasoning
problems, since they directly show the lines along which
the reasoning has to take place.
Information theoretic measures
The information I(A) of a proposition A, on the one
hand is directly related to the above defined probability
P(A) by
I(A) = — log P(A)
and is interpreted as an amount (in bits) of surprise or
uncertainty. Hence, l(Sure proposition) = 0. On the
other hand, it is also motivated by research on com-
munication theory. The amount of information of a
proposition is the number of bits required to encode
the proposition with an optimal coding scheme [Shan-
non and Weaver, 1949, Blahut, 1987].
Popular concepts from this theory are the mutual in-
formation
P(A|B)
I(A; B) = log "PG. = log
P(B|A)
P(B)