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.