Incremental Updating Information Extraction and Topology Conflict Detection Method for Updating Road Network

Abstract. In recent years, Located Based Service (LBS) has become one of the hotspots on the application of geographic information to the government and the public. Providing a good performance map to the users is an important part of the location service system. Compared with the traditional web spatial information service system, service system of map information also put forward higher requirements of real time and veracity. The problem of updating electronic map in real-time cannot be effectively solved, hindering the updating of multi-scale electronic map and restricting the development of location service market. As a very important branch for the updating data field of geographic information science, incremental update has become a hot issue in the current international GIS research field. The extraction of incremental information includes two key technologies, namely road network matching and road network selection. After incremental updating roads were inserted into the database, coordinating topological conflicts caused by these inserted roads was the mainly task. However, the accuracy and algorithm efficiency of each technology need further improvement to provide the users with the latest and the most accurate basic geographic data. As the "skeleton" element of a map, the road network rapidly changes, carrying out more urgent requires for the incremental road update. Aiming at key technology problems of the updated road network, the paper focused on the following three parts:

(1) To address the problems that the traditional probabilistic relaxation method only adopted geometric constraints as one of road matching criterions and could not respond to M: N matching pattern, an improved probabilistic relaxation method was proposed from the combined views of local optimization and global one, integrating geometric indicators with topology ones to achieve an effect with local optimization, as well as identifying M: N matching pattern by inserting virtual nodes to achieve a globally optimal effect. Then the matching strategies and corresponding implement algorisms were designed for different matching patterns. The case test showed that the overall matching accuracy of each evaluation indictor reached over 90%, increasing by 6%–12%; the evaluation indicators on both spatial and attribute properties increased by 4%–6%; the proper buffer threshold could be defined as twice the average value of the closest distances from all nodes in the candidate matching dataset.

(2) Aiming at the low accuracy and irrational structural selection caused by only using linear pattern or areal pattern, an improved method was proposed combining linear method as well as areal ones. The proposed method improves the Stroke generation algorithm of linear pattern using OLS model taking the overall information from the roads to be connected. Meanwhile, it partitioned road network by weighted Voronoi diagrams. The roads were selected under the process of calculating the importance of Stroke and its road density threshold. The test demonstrated that the improved method added the accuracy of Stroke generation results, and the results of road selection could maintain the overall characteristics of the road network as well as its spatial distribution information. Compared with method only using one pattern, the combined method had a better accuracy of road selection.

(3) According to the characteristics of detection topology for an updated road network, this paper proposed a topology conflict detection algorithm considering the incremental update of multi-scale network. The algorithm designed K-level topological neighbourhood to identify incremental neighbourhood road segments, built a topological refinement model based on geometric metrics, proposed checking rules based on comprehensive operation operator, and detected the conflict topology by using improved topological distance. The experimental results showed that 1) the accuracy and recall of the proposed method were more than 90%; 2) considering conflict topology caused by the generalization, the accuracy increased by 29.2%; 3) the average path length of a road network could be used as the reference of the best K-value in the K order incremental neighbourhood method.