ficient, 
ng and 
| ones. 
raphy, 
of the 
f road 
'twork 
, CD). 
imple) 
long a 
p (see 
itional 
actual 
es the 
detour 
twork 
rs for 
jn the 
ferred 
on the 
has a 
ne end 
Christian Wiedemann 
  
In the above example only the link hypothesis AD passes the NMS (see Fig. 1d)). In general more than one link hypothesis 
will be kept. All these link hypotheses are sorted according to their detour factor and the one with the highest detour factor 
is send to a module which checks the link hypothesis based on the image data. If the link hypothesis is rejected, the next 
one (the one with the second highest detour factor) is sent to the checking module, and so on. If a link hypothesis is 
accepted (and geometrically improved according to the image data), it is inserted in the road network. This changes the 
whole topology of the road network. Therefore, the procedure of generating link hypotheses has to be started again from 
the beginning. Link hypotheses already rejected are not taken into account in the following iteration. The iterative process 
of determining link hypotheses with maximum detour factor and checking them has to be broken off if one can expect 
that no further link hypothesis will be accepted by the checking module. In general, this cannot be predicted reliably, but 
it can be estimated roughly, e.g., based on the highest detour factor which occurs in the current iteration. 
2.2 Link hypotheses between different connected components 
Using the method presented in Sect. 2.1, it is not possible to generate link hypotheses between different connected compo- 
nents of the existing road network, because the calculation of the detour factor requires the determination of the network 
distance. For the generation of link hypotheses between different connected components another criterion has to be used. 
Having in mind that the road network consists of long roads, the following method is proposed: 
In the first step, between all possible pairs of points (P;, P;) with P; and P; lying in different connected components (AB, 
AC, and AD in the sample network given in Fig. 2), the lengths /; and /; of the respective connected components as well 
as the optimal distance od;; between P; and P; are calculated. 
' 1 1 
I | | 
  
a) b) c) d) 
Figure 2: Hypothesis generation between different connected components: a) Sample Network; b) Optimal distances; c) 
Connection factors for all preliminary link hypotheses (with: [ = I; + /;); d) Link hypothesis 
In the second step, preliminary link hypotheses are defined between each possible pair of points. A so-called “connection 
factor" is calculated for each preliminary link hypothesis according to the following definition: 
; l; 4 lj 
connection factor = ————————— 
optimal distance 
with: 
ll; = length of the connected components i and j, respectively 
This connection factor is further processed similar to the detour factor defined in Sect. 2.1, i.e., a NMS is applied to 
select potentially relevant connection hypotheses from all preliminary connection hypotheses. The connection hypothesis 
having the highest connection factor is sent to the checking module, which again checks the link hypothesis based on the 
image data. If the link hypothesis is rejected, the next one is sent to the checking module. If a link hypothesis is accepted, 
it is inserted in the road network. 
2.3 Combination of the generation of link hypotheses within and between connected components 
Since the detour factor is more meaningful than the connection factor, the generation of link hypotheses within and 
between connected components is organized as follows: First, all relevant link hypotheses within connected components 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 981