=Paper=
{{Paper
|id=Vol-1638/Paper29
|storemode=property
|title=Automatic checking of road network models
|pdfUrl=https://ceur-ws.org/Vol-1638/Paper29.pdf
|volume=Vol-1638
|authors=Ildar Abdulganiev,Anton Agafonov
}}
==Automatic checking of road network models ==
https://ceur-ws.org/Vol-1638/Paper29.pdf
Image Processing, Information Technology and Information Security
AUTOMATIC CHECKING OF ROAD NETWORK
MODELS
I. Abdulganiev, A. Agafonov
Samara National Research University, Samara, Russia
Abstract. This paper addresses the task of automatic checking of the road net-
work model. Under the road network model checking, we mean checking com-
pleteness and topology of the road network. We propose an original algorithm
based on a direction of movement criterion. The proposed algorithm is com-
pared with an existing algorithm based on an optimal distance criterion. The al-
gorithm was implemented and tested using the large transport network of Sama-
ra, Russia.
Keywords: transport network, topology correctness, shortest path, movement
direction.
Citation: Abdulganiev I, Agafonov A. Automatic checking of road network
models. CEUR Workshop Proceedings, 2016; 1638: 249-255. DOI:
10.18287/1613-0073-2016-1638-249-255
1 Introduction
Geoinformation systems are widely used in many areas of our life, including munici-
pal management, transport systems, economics, etc. The question about quality of
spatial data becomes more and more important because of increase in the intensity of
their usage. In this paper under quality we mean completeness and correctness of the
data.
Road network model is the basis for many transport problems, such as the optimal
network planning, optimization of the public transport routes, navigation problems
and so on. The paper deals with one of the possible formulations of the road network
checking tasks: checking connections between road links and correctness of turns
between links. The solution to this problem is necessary for the further use of the road
network in more complex problems, such as shortest path calculation and reliable
routing in stochastic networks [1], public transport arrival time prediction [2], traffic
flow forecasting [3], etc.
Completion of incompletely extracted road networks is an important part of road net-
work model with the use of digital imagery [4, 5, 6], including hyperspectral images
[7]. Road networks automatically extracted from digital imagery are often incomplete
and fragmented [8, 9]. This problem is especially important for the extraction from
low-resolution images. Mainly the operator, who compares the vector data and the
Information Technology and Nanotechnology (ITNT-2016) 249
Image Processing, Information Technology and Information Security Abdulganiev I, et al…
source images, carries out the network checking [10]. Completeness and topology of
the extracted network can be improved by the use of the global network structure
[11].
The article [4] proposes an approach to complement the fragmented road networks by
examining link hypotheses between nodes on the network, which are likely to be con-
nected, based on the characteristics of the network. In paper a detour factor, which
taking into account the distance of the road network and the optimal (Euclidean) dis-
tance between points, is checked. The shortest path algorithm A* is used to search for
the missing road links of the network in [5].
In this paper we use a complex road network graph, that includes the permitted / pro-
hibited turns between road links. We propose a road network checking algorithm
based on a direction of movement factor. The proposed algorithm is compared with
an existing algorithm based on detour factor and described in [4].
The paper is structured as follows. In the second section we introduce the basic nota-
tion, describe the graph structure and give a problem statement. Existing and pro-
posed algorithms are described in sections 3 and 4. In the fifth section we present the
experimental results. Finally, we make conclusions and provide recommendations for
further work.
2 Basic notations and problem statement
We consider a road network as an oriented graph G V , E , where V is a set of
nodes corresponding to the road intersections, E is a set of edges corresponding to
the road links. Direction of the edge is defined by the driving direction at the corre-
sponding road link.
We assume that the graph has a spatial reference, i.e. each node of the graph has the
coordinates ( x, y ) that are determined by the location of the corresponding road in-
tersection in the real road network.
In this paper we consider an oriented graph, each edge of which has two weight coef-
ficients:
─ t is the travel time on the edge;
─ l is the length of the edge.
Each intersection is converted into a set of geometrically coinciding graph nodes.
Each road link is presented by a pair of graph edges with different directions. We add
new edge between pair of nodes, if a turn between this nodes is allowed. Additional
edges do not have geometric characteristics, their weights are defined by average
travel time. Figure 1 shows a diagram of the intersection with the possibility of
movement in any direction.
The formal statement of the road network model checking problem can be defined as
follows: develop and implement algorithms for checking the topology of a large city
road network.
Information Technology and Nanotechnology (ITNT-2016) 250
Image Processing, Information Technology and Information Security Abdulganiev I, et al…
We check the connectivity of nodes of the road network and correctness of turns be-
tween road links. The following sections provide algorithms for checking link hy-
potheses between nodes in the network, based on a detour factor and a movement
direction factor.
Fig. 1. Graph structure inside the junction
3 Hypothesis based on a detour factor
In the paper [1] preliminary link hypotheses are defined between each pair of nodes.
A detour factor is calculated for each preliminary link hypothesis.
Let ks be the shortest path distance between nodes k and s. Shortest paths are calcu-
lated using Dijkstra algorithm [12];
ks be the optimal (Euclidian) distance between nodes k and s;
ks
dc be a detour factor.
ks
The detour factor shows the ratio of the distance between nodes in a road network to
the optimal distance between these nodes.
For each pair of nodes involved in checking we calculate distances ks and ks .
Then we check the following criterion:
dc max
dc (1)
where dc is predetermined threshold coefficient.
max
If the criterion (1) is satisfied, then all the links of the road network, included in the
shortest path between two nodes, is the candidates for additional check, further study
is needed for their analysis.
Information Technology and Nanotechnology (ITNT-2016) 251
Image Processing, Information Technology and Information Security Abdulganiev I, et al…
Experiments, how the road network checking results depend on the threshold coeffi-
cient dc , are presented in section 4.
max
4 Hypothesis based on a direction of movement factor
Algorithm based on the detour factor has a drawback. If the Euclidian distance be-
tween pair of nodes is large, then the distances ks and ks will be almost equal,
even if the connectivity of road links is broken. In this section we propose an algo-
rithm based on a different hypothesis, which eliminates this drawback.
Let d ks v1 , v 2 ,, vn be the shortest path from the node k to the node s, where
vi , i 0, N 1 is the node in the shortest path with index i.
N is a number of nodes in the shortest path.
The proposed algorithm consists of the following steps:
1. For pair of nodes k and s shortest path d ks is calculated.
2. For each node vi d ks , i 0, N 1 the optimal (Euclidian) distance vi s is calcu-
lated.
3. Direction of movement factors βi , i 0, N 2 are calculated using the following
expression:
vi 1s
i , vi d ks , i 0, N 2 .
vi s
4. The following criterion is checked:
i : βi 1, i 0, N 2 . (2)
If the criterion (2) is satisfied, then all the links of the road network, included in the
shortest path between two nodes, is the candidates to check. The criterion (2) means
that the Euclidian distance to the destination node should decrease during the trip.
Such criterion also has a drawback: it can gives false positive error if the optimal
distance is slightly increased. To avoid this, we introduce threshold coefficient
max
.
So the criterion is modified as follows:
i : i max , i 0, N 2 . (3)
The next section presents the conducted experiments.
Information Technology and Nanotechnology (ITNT-2016) 252
Image Processing, Information Technology and Information Security Abdulganiev I, et al…
5 Test results and analysis
We provide the following experiments.
Experiment 1. Study of the threshold coefficient dc impact on the results of the
max
algorithm based on the detour factor.
Experiment 2. Experimental study of the algorithm based on the direction of
movement factor.
The algorithms are tested on the road network of Samara, Russia. The network con-
sists of 52175 nodes and 76636 links. For experiments 400 graph edges e k E has
been artificially removed. The experiment results are presented below.
5.1 The impact of the threshold on the detour based algorithm results
For this experiment we choose 10 origin nodes ( k1 , k 2 ,..., k10 ) and 10 destination
nodes ( s1 , s 2 ,..., s10 ) , located in different areas of the city. We choose the following
threshold coefficient values θ dc 1.08, 1.15, 1.2, 1.3, 1.35, 1.4.
max
Firstly for each pair of nodes k, s we calculate the shortest path d ks in the original
graph (without removed edges). Next step is performed using the changed graph with
removed edges e k . For each pair of origin-destination nodes we calculate the short-
est path distance ks , the optimal distance ks and the detour factor ks .
If the shortest path d ks in the original graph contains some edges e e k , and the
criterion (1) for the changed graph is satisfied, then we suppose, that removed edges
is found. If the criterion (1) is satisfied, but the shortest paths in the original and
changed graphs are equal (i.e. the shortest path does not contain removed edges), then
road network check completed with error. The number of successfully found edges
and the errors number are shown on figure 2.
Fig. 2. The impact of the threshold on the detour based algorithm results
Information Technology and Nanotechnology (ITNT-2016) 253
Image Processing, Information Technology and Information Security Abdulganiev I, et al…
Chosen value of the threshold coefficient dc depends on the allowable number
max
false positive errors of the algorithm. Using the threshold value in the range
1.2, 1.35 , we detect about 75-85% of the road network topology errors. Level of
incorrectly defined edges is about 4-6%.
5.2 Experimental study of the algorithm based on the direction of movement
factor
In these experiments we use the same graph and pairs of origin-destination nodes,
defined in the previous section.
Again, for each pair of nodes k, s we calculate the shortest path d ks in the original
'
graph, the shortest path d ks in the changed graph and the direction of movement
factors βi , i 0, N 2 .
If the criterion (2) for the pair of origin-destination nodes k, s is satisfied and the
shortest path d ks contains removed edges e e k , then the algorithm completed
successfully. If the criterion (2) is satisfied, but the shortest path d ks does not contain
removed edges e e k , then the algorithm completed with false positive error. The
results of the experiment are shown in table 1.
Table 1. The results of the algorithm based on the direction of movement factor
Removed edges count Found edges False-positive errors
400 354 22
The proposed algorithm based on the direction of movement factor shows the similar
results with the algorithm based on the detour factor with the threshold coefficient
value dc 1.2 . We detect 88% of the removed edges with false-positive errors in
max
5.5%.
6 Conclusions
In this paper we propose the algorithm for road network checking based on the direc-
tion of movement factor. Under road network checking we mean checking the con-
nectivity of the road links and correctness of turns between links. The proposed algo-
rithms was compared with the base algorithm based on the detour factor. The con-
ducted experiments was performed using the road network of Samara, Russia. The
proposed algorithm showed similar results with the base algorithm with the threshold
coefficient value dc 1.2 . It should be noted, that the proposed algorithm showed
max
good results even in the case, when Euclidian distance between origin and destination
nodes are large enough.
Information Technology and Nanotechnology (ITNT-2016) 254
Image Processing, Information Technology and Information Security Abdulganiev I, et al…
We plan to conduct the experiments, how the threshold coefficient value max influ-
ence on the results of the algorithm based on the direction of movement factor.
Acknowledgements
This work was supported by the Russian Foundation for Basic Research (RFBR)
grant №16-37-00055-mol-a.
References
1. Agafonov A, Myasnikov V. Method for the reliable shortest path search in time-dependent
stochastic networks and its application to GIS-based traffic control. Computer Optics,
2016; 40(2): 275-283 [in Russian]. DOI: 10.18287/2412-6179-2016-40-2-275-283.
2. Agafonov A, Myasnikov V. An algorithm for city transport arrival time estimation using
adaptive elementary predictions composition. Computer Optics, 2014; 38 (2): 356-368. [in
Russian]
3. Agafonov A, Myasnikov V. An algorithm for traffic flow parameters estimation and pre-
diction using composition of machine learning methods and time series models. Computer
Optics, 2014; 38 (3): 539-549. [in Russian]
4. Wiedemann С, Ebner H. Automatic Completion and Evaluation of Road Networks. Inter-
national Archives of Photogrammetry and Remote Sensing, 2000; XXXIII, Part B3: 979-
986.
5. Gerke M, Butenuth M, Heipke C, Willrich W. Graph Supported Automated Verification of
Road Databases Using Aerial Imagery. Proc. 2nd International Symposium on Spatial Data
Quality, 2003: 421-430.
6. Grote A, Heipke C, Rottensteiner F. Road Network Extraction in Suburban Areas. Photo-
grammetric Record, 2012, 27 (137): 8-28.
7. Kuznetsov A, Myasnikov V. A comparison of algorithms for supervised classification us-
ing hyperspectral data. Computer Optics, 2014; 38 (3): 494-502.
8. Wiedemann C, Heipke C, Mayer H, Jamet O. Empirical Evaluation of Automatically Ex-
tracted Road Axes. Empirical Evaluation Methods in Computer Vision, 1998: 172-187.
9. Steger C, Mayer H, Radig B. The role of grouping for road extraction. Automatic Extrac-
tion of Man-Made Objects from Aerial and Space Images (II), Verlag, Basel, Switzerland,
1997: 245–256.
10. Willrich F. Quality Control and Updating of Road Data by GIS-driven Road Extraction
from Imagery. International Archives of Photogrammetry and Remote Sensing, 2002; 34:
761-767.
11. Mayer H, Laptev I, Baumgartner A, Steger C. Automatic road extraction based on mul-
tiscale modeling, context, and snakes. In: International Archives of Photogrammetry and
Remote Sensing, 1997; 2: 106–113.
12. Dijkstra EW. A note on two problems in connexion with graphs. Numer. Math – Springer
Science+Business Media, 1959; 1(1): 269-271.
Information Technology and Nanotechnology (ITNT-2016) 255