Christian Wiedemann 
  
are generated, checked, and — if verified — inserted into the road network (see Sect. 2.1). Then, link hypotheses are 
searched for between connected components. Again, these link hypotheses are checked based on the image data. The 
insertion of an accepted link hypothesis connecting two different connected components of the extracted road network 
changes the topology of the network. Therefore, if such a link hypothesis has been inserted, the search for link hypotheses 
is repeated within the resulting new connected component. If no further link can be inserted within this connected 
component, again, link hypotheses are generated and checked between different connected components. This is done 
iteratively, until no further link — neither within connected components nor between them — can be inserted. 
2.4 Implementation Issues 
In order to achieve better link hypotheses, equally spaced auxiliary nodes are inserted along the edges of the road network 
graph. 
The calculation of the detour factor for all possible preliminary link hypotheses is computationally expensive due to the 
search for the best path between their endpoints in the network. In general, it is not necessary to check links between 
points which are far away from each other. Therefore, preliminary link hypotheses are only generated if the optimal 
distance between their endpoints does not exceed a given threshold (maximum optimal distance). 
3 CHECK OF LINK HYPOTHESES 
The check of the link hypotheses should be done based on the image data. It should provide the information whether the 
link hypothesis can be accepted or not, and, in the case of acceptance, it should return the exact geometry of the connecting 
road. Due to the modular design of the approach every road extraction tool can be used which is able to extract a road 
between two given points — the end points of the link hypotheses — and which provides some kind of self-diagnosis in 
order to decide whether the connection can be accepted or has to be rejected. 
3.1 Road extraction 
In this work, the extraction algorithm described in (Wiedemann and Hinz, 1999, Wiedemann, 1999) was used. This 
approach has been designed for the extraction of road networks from satellite imagery. Nevertheless, it can also be 
applied to aerial imagery which is down-sampled to a ground pixel size of, e.g., 2 m. Due to the limited ground resolution 
of traditional satellite images a road model purely based on local characteristics is rather weak. For this reason, network 
characteristics of the roads are also taken into account, and regional and global properties are incorporated into the road 
model: 
Locally, radiometric properties play the major role. The road is modeled as a line of a certain width. It can have a 
higher or lower reflectance than its surroundings. On the regional level, geometric and radiometric characteristics of 
roads are introduced. These incorporate the assumption that roads mostly are composed of long and straight segments 
having constant width and reflectance. Globally, roads are described in terms of functionality and topology: The intrinsic 
function of roads is to connect different — even far distant — places. 
3.2 Insertion of verified link hypotheses into the road network 
If a road has been found which connects the two end points of the link hypothesis, this new link has to be inserted into the 
whole road network. 
First, all parts of the new link which are redundant with respect to the already extracted road network are eliminated. In 
most cases, one large part of the new link will remain. This part is then inserted into the network by connecting its two 
end points directly with the respective nearest points of the road network. If this point is not an end point of a road, a new 
junction is inserted into the road network. In cases where more than one remaining part of the new link exist, all these 
parts are inserted into the network as described above. If the whole new link has been eliminated no part can be inserted 
into the road network, i.e., the respective link hypothesis is rejected. 
4 EVALUATION 
Besides the intuitive measures completeness, correctness, and RMS (Wiedemann et al., 1998), an evaluation of the topol- 
ogy of the extracted network is carried out. To this end, two new measures are introduced: mean detour factor and 
connectivity. 
For the evaluation of the topological correctness within connected components of the extracted network, the mean detour 
factor with respect to the reference network is calculated: the distance along the reference network (network distance’) 
  
982 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.