Christian Wiedemann 
  
2 GENERATION OF LINK HYPOTHESES 
The division of labor in our modern business world demands for a transport network which allows for fast, cheap, efficient, 
and secure transports. The same characteristics are expected by the people for their daily ride to work, for shopping and 
for their trips to recreation areas (Pietzsch, 1989). 
The first statement describes the more global requirements for the transport network and the second the more local ones. 
Besides, there are additional factors which influence the design of the transport network like, e.g., local topography, 
land use, and environmental conservation. All these requirements are taken into account for the development of the 
road network (as part of the whole transport network). Therefore they can and should be used for the extraction of road 
networks from images as well. 
In this section an approach for the determination of link hypotheses between points on the already extracted road network 
is described. Links will be proposed where they are most desirable due to the above requirements. 
2.1 Link hypotheses within connected components 
Figure 1a) shows a part of a sample network which consists of four nodes (A, B, C, D) and three edges (AB, BC, CD). 
In the first step, between all possible pairs of points which lie on the network (the nodes A, B, C, and D in the example) 
the distance along the shortest path within the existing network (network distance, nd) as well as the distance along a 
hypothetical optimal path (optimal distance, od) are calculated, where, e.g., ndgp is the sum of ndpc and nde p (see 
Fig. 1b)). These distances are intended to represent the requirements for fast and cheap transports as well as the additional 
factors influencing the road network design mentioned above. Therefore the network distance depends on the actual 
length and classes of the roads along which the shortest path has been found. The optimal distance depends, besides the 
Euclidian distance between the two points, on factors like topography, land use, and environmental conservation. 
In the second step, preliminary link hypotheses are defined between each possible pair of points. A so-called “detour 
factor” is calculated for each preliminary link hypothesis according to the following definition: 
network distance 
detour factor = ————————— 
optimal distance 
In Fig. 1c) the detour factors for all preliminary link hypotheses are shown. For simplicity reasons both, the network 
distance as well as the optimal distance are set to the Euclidean distance between the respective points. 
  
a) b) C) d) 
Figure 1: Hypothesis generation: a) Sample Network; b) Network distances and optimal distances; c) Detour factors for 
all preliminary link hypotheses; d) Link hypothesis 
The third step consist of a selection of potentially relevant link hypotheses. The selection is carried out based on the 
assumption that only links which have a locally maximal detour factor are of any interest and that there is no preferred 
direction within the road network. Based on these assumptions, a non-maximum suppression (NMS) is performed on the 
set of preliminary link hypotheses: a link hypothesis is only kept if there is no competing link hypothesis which has a 
higher detour factor, otherwise it is deleted. Competing link hypotheses are preliminary link hypotheses between one end 
point of the preliminary link hypothesis under investigation and a point neighboring the other end point. 
  
980 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.