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