Road Key Point Connection Algorithm
To make true connections between predetermined road key
points and to construct road network topology, this section
describes a novel road vectorization algorithm. This algorithm
relies on the weighted graph theory to introduce geometrical
road characteristics to the vectorization strategy. The nodes of
the graph correspond to the road key points and the edges are
characterized by possible road segments. An
OWA
aggregation
strategy is used to transform the road geometric properties
into cost values previously defined .
Before the explanation of the proposed road connection
algorithm, it is necessary to specify the appropriate candi-
date pairs of road key points. For each point in the matrix of
predefined positions of road key points (
ORKP
), the possible
line segments around each road key point are considered. The
number of possible line segments should be restricted due to
two reasons: (a) Calculation of the cost values for all possible
line segments from the start road key point computationally
has a very poor efficiency, and (b) By increasing the length of
the line segments from the start road key point, the possibil-
ity of assigning them to the road segment set decreases. In this
paper,
K-Nearest Neighbor
(Cover and Hart, 1967) algorithm is
used to find the
K
nearest points to each road key point. In this
way only the
K
least cost line segments are investigated instead
of all the possible line segments. The value of
K
is determined
according to the maximum number of road legs involved in
the road junction in the image. Based on Garber and Hoel’s in-
tersections classification method (2010), there are three major
types of intersections: (a) three-leg intersection (like
T
and
Y
junctions), (b) four-leg or cross intersections, and (c) multi-leg
intersections, which consist of five or more approaches. In
general, multi-leg intersections are less common in order to
remove the conflicting movements from the major intersection
and thereby increase driving safety (Garber and Hoel, 2010).
The proposed road vectorization algorithm is considered
as follows (Figure 6):
• For each road key point in the
ORKP
matrix,
K
-nearest
least cost line segments are specified:
• The cost value for each of the
K
least cost line segments
-not included in the road segments set (
M
RS
)- is calculat-
ed based on the
OWA
aggregation algorithm (Figure 5).
• If the cost value is within an acceptable range (smaller
than predefined threshold, T
cost
) the line segment is
added to the
M
RS
. Otherwise, another nearest line seg-
ment is examined.
• This procedure should be repeated until the entire road
key points are examined and all the true road segments
have been assigned to the
M
RS
.
The final result of the proposed road vectorization technique
is a road network consisting of road centerlines and junctions.
Implementation and Experimental Results
The proposed road vectorization approach was implemented
on a
PC
environment using the professional MATLAB R2012a
computer language. The proposed method was implemented
on a simulated binary road image along with several different
high resolution images.
The quality measures as defined in Wiedemann (2003)
were determined based on comparing the vectorized road
network with a reference road image, which was manually
generated, by means of the “Buffer method in consideration
of direction differences.” The average width of five pixels
on each side of the roads, 10 m for the Ikonos, was selected
as buffer width to calculate the quality measures including
RMS
Error, completeness, and correctness. Besides, the junc-
tion
RMS
Error was calculated as another quality measure to
investigate the robustness of the proposed method in junction
vectorization. The junction evaluation buffer was set to ten
pixels on each road side. The junction evaluation buffer was
considered larger than the road evaluation buffer because the
inaccuracy in the road centerline is usually largest at the end
of the roads (Grote
et al
., 2012).
Evaluation of Line Segment Alternatives Using
OWA
Table 3 illustrates the criteria weights and the order weights
by selecting different decision strategies for the three criteria
previously defined. As it is shown in the table, the criteria
weights are the same as the order weights in the case of
OWA
aggregation with ORness = 0.5 (
α
= 1). In this situation the
conventional
WLC
is performed on the values of the criteria.
T
able
3. C
riteria
W
eights
and
O
rder
W
eights
for
T
hree
R
oad
S
egment
C
riteria
B
ased
on
D
ifferent
OR
ness
Criteria
weights
(
vj
)
N
= 3
ORness
Order
weights
(
wj
)
0 0.1 0.3 0.5 0.7 0.9 1
0.500 w1 0.000 0.000 0.250 0.500 0.758 0.895 1.000
0.333 w2 0.000 0.001 0.439 0.333 0.170 0.038 0.000
0.167 w3 1.000 0.999 0.311 0.167 0.072 0.067 0.000
Figure 7 shows an example of the cost calculation proce-
dure (see Figure 5) for a set of criteria values of
A
i
= [15, 10,
80] at the
i
th
line segment in the case of
WLC
.
In this research, different decision strategies (ORness val-
ues) were considered to calculate the
OWA
values for each line
Figure 6. The proposed road key point connection pseudo-code to
construct road topology.
Figure 7. An example of the OWA computation for the
i
th
line seg-
ment in the case of WLC.
112
February 2016
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
