In: Stilla U, Rottensteiner F, Paparoditis N (Eds) CMRT09. IAPRS, Vol. XXXVIII, Part 3/W4 — Paris, France, 3-4 September, 2009
both distance transforms within the road part have the same
values make up the centre line. Further details of the road part
extraction are explained in (Grote and Heipke, 2008).
min. elongation
70
width
3 m - 16 m
min. width constancy
1.7
min. intensity
40
max. NDVI
0
max std. deviation of colour
50
Table 1. Parameters for road part extraction.
2.3 Road Subgraph Generation and Evaluation
In many cases, a road is not completely covered by one road
part but by several different road parts because disturbances in
the appearance of the road interfered with the extraction.
Therefore, road parts that could belong to the same road are
assembled into road subgraphs (Fig. 1) by checking if the road
parts have neighbours to which they can be connected. The
subgraphs are assembled iteratively, starting with the road part
with the best quality measure from the road part extraction. The
criteria used to decide whether two road parts belong to the
same road are the distance between the segments, the direction
difference and the continuation smoothness. The reference
points for the measurement of the direction difference and the
continuation smoothness are the intersection points between the
centre line and the road part borders. The continuation
smoothness is measured by calculating the direction differences
between the directions of the road parts to the direction of their
connection (Fig. 2). The continuation smoothness is high if both
smoothness angles are small. However, if the distance between
the segments is short, the continuation smoothness criterion is
disregarded because at close distances the angles depend too
much on the exact positions where the angles are measured.
Figure 2. Continuation smoothness.
Two road parts are linked if empirically determined thresholds
for the distance, the direction difference and the continuation
smoothness are met. The distance and the direction difference
must be low and the continuation smoothness must be high; all
three conditions must be fulfilled for the road parts to be linked.
The parameters used for the experiments described in this paper
are shown in Table 2. One road part can be attached to more
than one other road part in the same direction, such that
branches in the subgraphs can occur. The search for
neighbouring road parts continues until no more road parts can
be added. Then, the search is resumed with the road part which
has the best quality measure among the remaining road parts
until all road parts have been examined.
max. distance
50 m
max. direction difference
40°
max. smoothness angle
40°
Table 2. Parameters for road subgraph generation.
In most cases the branches do not represent actual branches in
the road network but rather indicate false extractions of road
parts that are nearly parallel to the real road. Therefore, road
subgraphs containing branches are treated as including different
hypotheses for the course of the road. It is the goal of road
subgraph evaluation to determine the best hypotheses, i.e. the
hypotheses that are most likely to actually correspond to roads,
and to discard all the other hypotheses. This goal is achieved
via the formulation and solution of a linear programming
problem.
In linear programming a linear function (objective function)
whose variables are subject to linear constraints is maximised or
minimised (Dantzig, 1963). The constraints define a set of
feasible vectors; the vector for which the constraint set is
maximal or minimal is the optimal solution for the problem.
Linear programming can be used when the variables of the
linear function to be optimised are restricted by hard
constraints, which can be described by equations or by
inequalities. In our case the constraints are inequalities resulting
from the condition that no node of a subgraph should be
connected to more than one gap edge after the optimisation.
The objective function which is to be maximised is
W] Xj + ... + w„x„ —► max (1)
where w t ... w„ are weights of the gap edges that reflect the
plausibility that the two road parts belong to the same road. The
unknown variables are X/ ... x„. There is one such unknown for
each gap edge in the road subgraph. Each of these binary
variables indicates whether its corresponding edge should be
kept or discarded. A value of 1 indicates that the edge is kept; a
value of 0 indicates that it is discarded. These values are
determined by solving the maximisation under the constraints
that each node i can only be associated to one gap edge:
2>;S>- <2)
fe£,
Ei is the set of gap edges belonging to node i. The optimisation
is carried out using the simplex method (Dantzig, 1963). The
edge weights are determined using the following criteria:
• Distance: a shorter distance between the two
connected road parts gives a higher edge weight.
• Road part quality: the sum of the quality measures of
both road parts from the extraction. A higher value
gives a higher edge weight.
• Colour: a smaller difference between the mean colour
values of both road parts gives a higher edge weight.
• Width: a smaller width difference between both road
parts gives a higher edge weight.
• Continuation smoothness: smaller smoothness angles
(cf. Section 2.2) give a higher edge weight.
• Direction: a smaller direction difference between both
road parts gives a higher edge weight.
The weights for the different criteria are obtained after
calculating all criteria by mapping the respective values linearly
onto an interval between 0 and 1. For example, the maximum
possible distance between two connected road parts is
equivalent to a distance weight of 0. The other weights are
obtained accordingly. All weights are multiplied to obtain the
total weight for one edge. The edge weights that belong to the
same subgraph are normalised such that their sum equals 1.
