Object matching is a key technology for map conflation, data updating, and data quality assessment. This article proposed a new Voronoi diagram-based approach for matching multi-scale road networks (VAMRN). Using this method, we first created Voronoi diagrams of the road network using the strategy of discretizing road lines into points and adding dense points to special road intersection segments. Then, we used the Voronoi diagram of road segment to find matching candidates. Finally, we obtained matching results by judging the geometric similarity metrics we designed and a heuristic combination optimization strategy. The experimental results demonstrated that the VAMRN outperformed two existing methods in generality and matching quality. The F-measures of VAMRN were 18.4, 29.6, 3.8, and 7.6% higher than the buffer growing method, and 4.5, 2.8, 1.8, and 6.1% higher than the probabilistic relaxation method. And the time performance is improved by more than 90% over the probabilistic relaxation method.
Notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
The road network is the connecting framework of cities and regions, and it plays a key strategic role in promoting regional economic development and improving people’s living standards. At the same time, road network data are also the indispensable core data for emerging fields such as Location-based Services (LBS), Smart Navigation, and Social Networking Services (SNS) (Luan 2013). With the rapid advancement of the technologies like Geographic Information System (GIS), Remote Sensing (RS), Global Navigation Satellite System (GNSS), and social media, it is much easier to produce, distribute, and utilize digital geospatial information.
However, the spatial data collected by different departments have different application purposes, leading to duplicate collection of spatial data in the same area. And these data possibly exist large geometric difference due to map scale, image resolution, time, compilation standards, data accuracy, alignment, sensor characteristics, or error (Guo 2008). In order to keep the spatial data current and eliminate the differences between spatial data, it is necessary to update and fuse the spatial data in a reasonable way. While object matching is a basic and key step in the process of data updating and fusion. Object matching means that, through a series of similarity measures, to distinguish identical objects from different data sources, and then built the corresponding relations for related spatial objects (Fu et al. 2008). It usually includes match types of 1:1, 1:N, M:1, M:N, 1:0, and 0:1. M:N match type means that M objects in one dataset match N objects in another dataset. Table 1 shows the examples of the matching pair categories.
Table 1
The examples of the matching pair categories
Advertisement
Therefore, it is of great research value and application significance to study road network matching. For example, Fig. 1 shows that two overlaid road datasets covering the same area with different map scales have obvious positional discrepancies. If you want to conduct the conflation of geometry or attribute information of the identical roads from two datasets, you must use object matching technology to recognize the identical objects.
Fig. 1
The non-systematic discrepancies between road dataset at 1:10,000 map scale and road dataset at 1:50,000 map scale
×
However, due to the multi-source, multi-scale, multi-temporal of road network data, as well as relatively complex structure itself, it is relatively difficult to match multi-scale road network. The existing road network matching algorithms still have the problems of low matching automation or low computational efficiency. For example, the existing buffer-based method for searching matching candidates needs manually setting the buffer radius and can cause missing matches or computation workload. Therefore, there still exist challenges to implement a generic, automatic, and efficient matching of multi-source and multi-scale road networks.
In this paper, we present a novel multi-scale road network matching method based on Voronoi diagram (VAMRN). Our matching method can handle geographic datasets without attributes or having significant attribute differences (e.g., the difference in schemas, naming, or coding conventions), even the road networks that have large non-consistent positional discrepancies, and have higher matching accuracy. The VAMRN method innovatively uses Voronoi diagrams of road segments to find candidate matching road segments. Voronoi diagram has more advantages in spatial analysis and partitioning. It can establish the correlation between multi-source spatial data based on spatial location. When applied to object matching, it can effectively avoid manually setting the buffer radius used for searching candidates and prune the matching searching space. By combining geometric similarity metrics, such as length, shape, and direction, as well as a heuristic combination optimization strategy, which can effectively achieve identical road matching and improve the algorithm generality and matching quality. This method is conducive to solving the problem of integrating and updating multi-source road data.
2 Related work
The purpose of road network matching is to find out corresponding objects from different source datasets and to establish their association relationships. In general, two important factors that determine the merits of road network matching algorithms are similarity characteristic and matching model. Both of them have a significant impact on the matching accuracy of the overall matching algorithm. Many researchers have conducted related studies on road network matching.
Advertisement
In the aspect of study on similarity metric, the geometric similarity metric of line objects can be roughly judged and filtered in terms of characteristics such as distance, direction, length, and shape. Distance similarity characteristic is often used to measure correlation between corresponding objects. Gabay and Doytsher (1994) proposed a method for matching linear objects by using the distance between the points (vertices or nodes) and the angle between the line segments to be matched as a spatial constraint. Zhang (2002) proposed a method for calculating the distance using the middle area of two line objects, and designed a shape similarity of line objects using the change of direction of each line segment in each line object. By extending the Hausdorff distance algorithm, Deng et al. (2007) proposed a line object matching method based on the extended Hausdorff distance. Yang (2016) proposed a mixed-median Hausdorff distance to achieve a reasonable distance measure between line entities of varying length and shape. The directional similarity characteristic is usually used to determine the difference in the overall orientation of the objects. Walter and Fritsch (1999) proposed a probabilistic statistical matching method based on “buffer growing” to obtain the candidate matching set, specifically it uses the statistical properties of angles, lengths, shapes, and topological characteristics between line objects to determine the threshold value of confirming corresponding objects, and uses the dominance function in information theory to calculate the optimal matching results. The length similarity metric of line objects is mainly used to detect the size difference between two objects by calculating the length ratio of the two objects. The shape characteristics of line objects mainly include curvature, tightness, orthogonality, etc. Shape similarity metric of two objects is used to determine the deformation difference between two objects. Zhang et al. (2002) proposed a method for determining object shape difference by the comprehensive change in the directional variation of each line object for each road segment. Topological similarity metric is a mathematical method used to determine the spatial structure relationship between neighboring line objects (Wu 2008). The semantic similarity characteristics of line objects refer to the attribute information of each spatial object, such as naming, encoding, usage, and type. It is the most accurate and efficient matching similarity metric in matching, mainly by analyzing the difference of attribute information of line objects to measure the semantic difference.
In terms of automatic matching algorithm models of road networks, many scholars have tried to introduce models from other domains into the matching algorithm. The most widely used buffer growth method was proposed by Walter et al. (Walter and Fritsch 1999). By setting a reasonable buffer radius for the dataset, the line objects that meet the distance, length, and direction similarity indexes are marked as candidate matching roads as the buffer continues to grow, and then the optimal matching pair is obtained by a probabilistic calculation method. Volz (2006) extended the Walter’s algorithm by proposing an iterative node and edge matching algorithm applying relaxed constraints based on detection of similarity measures. Tong et al. (2007) proposed a probabilistic theory-based spatial data matching algorithm. The algorithm combined multiple similarity characteristics and determined whether two objects match by the matching probability. Li and Goodchild (2011) developed a new optimization model to improve linear feature matching. The model takes into account all potentially matched pairs simultaneously by maximizing the total similarity of all matched features, nevertheless, the matching efficiency is low. Zhang et al. (2012) proposed an automatic matching method for urban road networks based on a probabilistic relaxation method, which first estimates the initial probability of candidate road sections by the geometric difference among road segments; then, it continuously updates the original probability matrix until it converges to a certain minimal value based on the compatibility of neighboring candidate matching road segments; finally, it calculates the structural similarity of each candidate road segment based on the converged probability matrix, and selects and refines matching pairs by setting the corresponding rules. Chehreghan and Abbaspour (2017) used real coding genetic algorithm (RCGA) and sensitivity analysis for target identification based on consideration of geometric criteria. Their method eliminates the initial dependency on empirical parameters such as buffer distance, spatial similarity threshold, and weights of criteria; instead, the optimal values of these parameters are calculated based on input dataset. However, the method is time-consuming and there is biased in the training data. Zou et al. (2020) proposed a hierarchical matching method based on Delaunay triangulation for solving road network matching under different or unknown coordinate systems. Lei (2021) proposed a feature matching framework based on optimization and divide-and-conquer. His research was mainly conducive to improving the computational efficiency; however, he paid little attention to the matching accuracy, and the matching datasets used were also less complex.
To sum up the above methods, we find that (1) many methods require an empirically setting buffer distance for searching candidate matching elements. However, a small buffer distance causes missing the identical objects, and a large buffer distance increases computation time while reducing the matching efficiency; (2) many heuristic methods, such as probabilistic relaxation methods and genetic algorithms, have complex and massive calculation process that results in much lower efficiency in complex road network matching. Therefore, the practicability of these algorithms needs to be improved; (3) many of the previous studies are efficient in datasets with small geometric differences or consistent positional discrepancies, while they cannot be applied to matching datasets with significant inconsistent positional discrepancies. And they rarely simultaneously meet the requirements of urban road matching and mountain road matching.
Because Voronoi diagram has the unique properties in spatial proximity and spatial segmentation, it is widely used to describe spatial proximity, closest operation, and scope of spatial influence (Hao 2010), and build the spatial corresponding relationship for multi-scale objects (Wu et al. 2018). So we can utilize the Voronoi diagram to query the candidate matching roads of different scales. In the study of the spatial analysis of Voronoi diagrams, Chen et al. (2003) noted that digital map synthesis and update is a direction for further research on Voronoi diagrams. In recent years, Voronoi diagrams have been applied preliminarily in point matching (Wu and Wan 2015; Ma 2020), line matching (Hu and Mao 2011; Yu 2017), and polygon matching (Wu et al. 2018). However, there is relatively little literature on road network matching using Voronoi diagrams. Compared with the buffer searching method used in many studies like Walter and Fritsch (1999) and Yang et al. (2013), Voronoi diagram has the advantages of establishing the relationship of corresponding objects from multi-source and multi-scale spatial data based on spatial location and controlling the selection range of the candidate matching set within a reasonable neighborhood area, thereby avoiding the matching error caused by the manually unreasonable selection of the buffer radius threshold. Therefore, we proposed a new multi-scale road network matching method based on Voronoi diagram (VAMRN).
3 Methodology
VAMRN consists of three processes: Voronoi creation, candidates acquisition, and matching pair selection. Figure 2 preliminarily illustrates the VAMRN process.
Voronoi creation: Includes discretizing each road segment of the road network into a point set, creating Voronoi diagrams of the point set, and merging Voronoi diagrams by point set of each road segment.
Candidates acquisition: Includes obtaining potential candidate matching road segments and obtaining the candidate matching set after removing the anomalous road segments.
Matching pair selection: Includes geometric similarity metrics calculation, simple matching, and combinatorial matching.
Fig. 2
Schematic diagram of VAMRN process
×
As shown in Fig. 2, let the two datasets to be matched be Road1 = {Ri | i = 1, 2, …, m} and Road2 = {Tj | j = 1, 2, …, n}, in which Ri represents each road segment in the source dataset and Tj represents each road segment in the target dataset. Based on the idea of occurrence element discretization, the Voronoi diagrams of points are firstly constructed by the point family Pset = {Pi | i = 1, 2, …, m} into which VAMRN discretizes the road network, where Pi is a point of Ri discretization. Then, the Voronoi diagrams of Pset are merged into the Voronoi diagrams of Vset = {Vi | i = 1, 2, …, m}, where Vi is the Voronoi diagram of Ri (Sects. 3.1). The initial candidate matching road set (C) of Ri is then obtained by the intersection relationship between Vi and Road2, and the candidate matching road set (C1) of Ri is obtained after the operation of eliminating the anomalous roads (Sect. 3.2). Finally, depending on the number of elements in C1, simple matching and combinatorial matching are performed, and the geometric similarity metrics are calculated to determine whether a pair is a match or not (Sects. 3.3).
3.1 Voronoi creation
Because VAMRN requires the use of Voronoi diagrams of road segments to obtain the candidate matching set, the first step is to create Voronoi diagrams of the road network. We designed an algorithm for creating Voronoi diagrams of road network based on the idea of occurrence element discretization. This involved first breaking road network data at intersections; discretizing each road segment into a set of points that can replace the road segment; creating Voronoi diagrams of point sets for all road segments; and finally obtaining a Voronoi diagram for each road segment by merging the Voronoi diagrams generated by the corresponding point set of each road segment.
3.1.1 Discrete point set construction method for road network
Discretizing road network into point set means that using a finite number of discrete points with equally spaced distance to replace each road segment in road network. Its main steps are as follows.
First, interrupting road polylines at intersections. VAMRN automatically interrupts all road polylines in two road network datasets at road intersections to obtain Road1 = {Ri | i = 1, 2, …, m} and Road2 = {Tj | j = 1, 2, …, n} (m and n denote the FID (unique identification number of the feature that is an object including geometry and attribute information) of each feature in Road1 and Road2, respectively). Meanwhile, using the attribute field FID_O of Ri (or Tj) to record the FID value of its original road segment.
Second, endpoint offset processing. To avoid an error in creating the Voronoi diagram of road segment caused by the overlap of adjacent road endpoints, the endpoints need to undergo slightly offset processing. As shown in Fig. 3(a), R1, R2, R3, and R4 are intersect at the point O, and then, the intersection O of each road is offset at a distance d (such as 1 m (meter)) along the Oqn(n = 1,2,3,…) direction of each road. The schematic effect of the road segments after the endpoint offset is shown in Fig. 3(b). The red circle shows the effect of the intersection after the offset of the end points of each road segment.
Fig. 3
Discrete processing of road network (Ri is a road segment; O is the intersection; qi is the offset point; d is the offset distance): a Insert the offset point; b Intersection point processing; and c The discrete point set P
×
Last, creating discrete points. First, creating a new discrete point layer for storing the discrete points of each road segment. Second, using any endpoint of each road segment in Road1 as the starting point, then adding new points along road segment Ri at intervals of distance g(λ) which is obtained by the calculation of Eq. (1) to the discrete point layer. In Eq. (1), MapScale (S) is the denominator value of the map scale of the dataset S, MapScale (S) divided by 1000 indicates the actual length of the surface corresponding to 1 mm on the map, 1/10 indicates the ratio at which 1 mm distance on the drawing can be recognized by the human eye (Pan 2004), and λ (1 ≤ λ ≤ 10) indicates the distance tolerance factor.
$$g(\lambda ){\text{ }} = {\text{ }}\lambda *\frac{{{\text{MapScale}}\left( S \right)}}{{1000}}*\frac{1}{{10}}$$
(1)
Meanwhile, the two endpoints and turning points of road segment Ri are added to the discrete point layer. At the same time, using attribute field FID_O of each discrete points to store the FID of the road segment where the point is located in preparation for Voronoi diagram merging. Referring to the triple standard deviation principle, normally, λ takes the value of 1 ≤ λ ≤ 3. Theoretically, the smaller the value of λ, the smaller the spacing of the discrete points, and the more discrete points are generated. We take into account the data error limit and the efficiency of creating Voronoi diagram, λ is set as 4 in this paper. Now we can obtain the point sets Pi of each road segment and the number of inserted points Ni of each road segment, where i denotes the FID of each road segment. Finally, all Pi are combined into Pset, as shown in Fig. 3(c).
3.1.2 Special intersection identification and addition of dense point processing
In a preliminary study of creating Voronoi diagrams of a road network, we found that when the angle size between two road segments was too small, the Voronoi diagrams of road segments generated at the intersection points were easy to cross and deform. As shown in Fig. 4(a), R1, R2, R3 and R4, .., R7, R8 denote several road segments to be matched in the source road set, V1, V2, V3, …, V7, V8 denote the Voronoi diagrams created by each road segment to be matched, the intersection O selected by the green box is a special intersection, and V5 is the Voronoi diagram with crossing and deformation. To solve the noted problems, we proposed a method for the identification of special intersections and the addition of dense points in the nearby road segments. When the angle between the two line segments, respectively, of two road segments that intersect at a point was less than 45° (this angle threshold is independent of map scale), the Voronoi diagrams of road segments generated at the angle were likely to experience these problems. Therefore, such intersections were marked as special intersections, and the road segments connected to such intersections were further processed by adding dense points to the original discrete point set. The distance of increasing the dense points is g(λ) (λ = 1), and the effect of the Voronoi diagram of road segment generated after adding the dense points processing is shown in Fig. 4(b).
Fig. 4
Identification and processing of special intersections (Ri represents a road segment in the dataset; Vi represents the Voronoi diagram of a road segment; O is the intersection): a Error Voronoi diagram of road segment before adding dense points; and b Voronoi diagram of road segment after adding dense points
×
3.1.3 Building Voronoi diagrams of road networks
First, we created Voronoi diagrams of points using discrete point set P, as shown in Fig. 5(a). Next, we transformed Voronoi diagrams of the point set into Voronoi diagrams of road segments, that is, merging Voronoi diagrams generated by points belonging to the same point set into a Voronoi diagram of road segment. The result of the merging is the Voronoi diagram of all road segments in the road network is shown in Fig. 5(b).
Fig. 5
Process of creating a Voronoi diagram of a road network: a Voronoi diagram of the point set; and b Voronoi diagram of the road network
×
3.2 Candidates acquisition
Initially, we obtained the candidate matching road segments set C by traversing Vi in Vset and finding the road segments intersecting with Vi in Road2. Then, some of the anomalous candidate matching road segments were eliminated by judging the size of θProj, (0 < θProj < 90) (Zhang 2002), and disH, where θProj is the angular difference between the line connecting the first and last endpoints of each road segment in C and the line connecting the projection points of its two endpoints on Ri, and disH is the mixed-median Hausdorff distance between each road segment in C and Ri, which are marked as anomalous candidate matching road segments when θProj is greater than 35° or disH > g(λ)(λ = 10). However, 35° and 10 are empirical values in spatial cognition that do not depend on map scale. As shown in Fig. 6, V1 is the Voronoi diagram generated by R1, C = {T1, T2, T3, …, T9}; L1, L2, and L3 are the lines connecting the first and last endpoints of T1, T4, and T7 segments, respectively; and Pr1, Pr2, and Pr3 are the lines connecting the endpoints of T1, T4, and T7 on R1, respectively. The projection point is the point on source road closest to the target road endpoint. As shown in Fig. 6, although L1 and Pr1 satisfy θProj < 35, the disH between them is greater than g(10), T1 is marked as an abnormal candidate matching road segment. θProj > 35 between L2 and Pr2, as well as L3 and Pr3, respectively, so T4 and T7 are also marked as abnormal matching road segments. After eliminating all the abnormal road segments, C = {T3, T5, T6} significantly reduced the amount of computation in the matching process, improved matching efficiency, and reduced the number of false matches. Finally, we put the remaining road segments in C into the set C1, and C1 = {T3, T5, T6} was the candidate matching set of R1.
Fig. 6
Process of obtaining candidate matching set (Ri represents a road segment in the source dataset; Ti represents a road segment in the target dataset; V1 represents the Voronoi diagram of R1; Li represents the line connecting the start point and end point of Ti; Pri is the line connecting the projection points on R1 of the start point and end point of Li)
×
3.3 Matching pair selection
After obtaining the candidate matching set C1 of Ri, we selected the corresponding objects of Ri from the candidate matching set, that is, the process of building road matching pairs. To select the final matching pairs, such as 1:0 (or 0:1), 1:1, 1: N, and M:N from the entire dataset, we divided the matching process into two cases (simple matching and combination matching) according to the number of road segments contained in C1, and determined whether they were identical objects by calculating the geometric similarity metrics between two road segments or combinators.
3.3.1 Geometric similarity calculation and identification method of corresponding objects
Whether or not two road segments or road combinations are corresponding objects can be determined after calculating the geometric similarity metrics between the two road segments or road combinations. The metrics for evaluating the difference of two linear features are typically distance, length, shape, direction, semantics, and topology. Distance metrics are usually not suitable for matching data from road networks that are too dense and have large geometric discrepancies. Since road network datasets from multiple sources, especially for the VGI (Volunteered Geographic Information) data, usually have incomplete attributes or have different descriptions for the same attribute of corresponding objects, the semantic information is also difficult to be adopted. For multi-scale road network data matching, the topological characteristics of road with the same name may change due to the different levels of detail of data at different scales, so the topological similarity metric is not chosen in this paper. Therefore, considering the adaptability of similarity metrics, we designed length (Yang 2016), shape, and direction (Tong, et al. 2007) similarity metrics to measure the geometric difference characteristics among road segments. As shown in Fig. 7, Tj is a road segment in the Ri candidate matching set, Ri and Tj can be represented as a series of sequential nodes Ri = {ri(1), ri(2), ri(3), …, ri(m)}, Tj = {tj(1), tj(2), tj(3), …, tj(n)}, the two endpoints of Ri are ri(1), ri(m), and the two endpoints of Tj are tj(1), tj(n). The length, shape, and direction similarity metrics of the candidate matching roads Ri and Tj are calculated according to Eqs. (2), (3), and (4), respectively.
where \(\left|{\text{r}}_{\text{i}}\left({\text{h}}\right){\text{r}}_{\text{i}}\left({\text{h}}+ \text{1} \right)\right|\), \(\left|{\text{t}}_{\text{j}}\left({\text{h}}\right){\text{t}}_{\text{j}}\left({\text{h}}+ \text{1} \right)\right|\), \(\left|{\text{r}}_{\text{i}}{\left({1}\right){\text{r}}}_{\text{i}}\left({\text{m}}\right)\right|\), and \(\left|{\text{t}}_{\text{j}}{\left({1}\right){\text{t}}}_{\text{j}}\left({\text{n}}\right)\right|\) all denote the Euclidean distance between two nodes; dA\(\left({\text{r}}_{\text{i}}{\left({1}\right){\text{r}}}_{\text{i}}\left({\text{m}}\right)\text{, }{\text{t}}_{\text{j}}{\left({1}\right){\text{t}}}_{\text{j}}\left({\text{n}}\right)\right)\) denotes the angle (0° to 90°) size of the line connecting Ri and Tj endpoints of the corresponding road segment; and \({\text{sim}}_{\text{len}}\), \({\text{sim}}_{\text{shp}}\), and \({\text{sim}}_{\text{dir}}\) are the geometric similarity metrics of length, shape, and direction between candidate matching roads, respectively. Suppose their thresholds are ρlen, ρshp, and ρdir. When \({\text{sim}}_{{{\text{len}}}} {\text{ = }}\rho _{{{\text{len}}}}\), \({\text{sim}}_{{{\text{shp}}}} {\text{ = }}\rho _{{{\text{shp}}}}\), and \({\text{sim}}_{{{\text{dir}}}} {\text{ = }}{\mkern 1mu} \rho _{{{\text{dir}}}}\) are satisfied at the same time, Ri and Tj are the identical roads.
Fig. 7
Geometric similarity between candidate matching road segments (Ri represents a road segment in the source dataset; Tj represents a road segment in the target dataset; ri(m) is the mth node on Ri; tj(n) is the nth node on Tj)
×
3.3.2 Simple matching
When 0 ≤|C1|≤ 1 (| * | denotes the number of features in the set *), the \({\text{sim}}_{\text{len}}\), \({\text{sim}}_{\text{shp}}\), and \({\text{sim}}_{\text{dir}}\) of the candidate matching road segments in C1 and Ri are calculated, and if the threshold of each geometric similarity metric is satisfied at the same time, obtain a 1:1 matching pair; otherwise, obtain a 1:0 matching pair, and insert the matching result into the queue Final.
3.3.3 Combination matching
When the candidate matching set C1 of Ri contains multiple road segments, screening the road segments for combination is required. By determining the constraints of UT and Ri, where UT denotes the combination of road segments in C1, if the constraints are met and the threshold of each geometric similarity metric is satisfied, the corresponding object of Ri is obtained. When combining candidate matching segments, the best combination is found under multiple constraints, based on the mixed-median Hausdorff distance between the candidate matching road segment and the source road segment, in order from near to far. Hausdorff distance is used for measuring the distance between two point sets, which is widely applied to describe the distance between various objects such as vector points, polylines, and polygons. However, it may have outliers when the shapes or lengths of two polylines that are used for calculating Hausdorff distance are different greatly. Nevertheless, the mixed-median Hausdorff distance can avoid the above problem. Since multi-scale road network datasets possibly have large differences in shape and length, we choose the mixed-median Hausdorff distance to calculate the distance between two road segments.
According to the first law of geography, everything is related to everything else, but near things are more related to each other, the VAMRN algorithm prioritizes the combination of candidate elements with small distances in combination matching. Table 2 shows the basic procedure of combining candidate matching elements in pseudocode.
Table 2
The basic steps of the combination of candidates
We calculated the disH(Tj, Ri) of each candidate matching road segment Tj in C1 with Ri using the mixed-median Hausdorff distance, and combined results in the order of disH from the smallest to the largest. As shown in Fig. 8, R1 is a road segment in the source dataset; V1 is the Voronoi diagram created by R1; T1, T2, T3, T4, T5, T6 are the candidate matching set of R1; H1 is the Hausdorff distance between T1 and R1; H2 is the Hausdorff distance between T2, T3, and R1; H3 is the Hausdorff distance between T4 and R1; H4 is the Hausdorff distance between T6 and R1; and H5 is the Hausdorff distance between T5 and R1. Where H1 < H2 < H3 < H4 < H5, T1 is the starting road segment of UT. According to Hausdorff distance in order of smallest to largest, query the candidate matching road segment intersecting with UT, and the intersecting road segment shown in Fig. 8 is T2. Therefore, UT and T2 will be merged to obtain the new UT. The next candidate matching road segment intersecting with UT is T3, which is merged with UT in the order of Hausdorff distance from smallest to largest. The next queries are T4, T6, and T5, which do not intersect with UT, that is, {T1,T2,T3} may match with R1.
Fig. 8
Combined order based on the mixed-median Hausdorff distance from smallest to largest (Ri represents a road segment in the source dataset; Ti represents a road segment in the target dataset; V1 represents the Voronoi diagram of R1; Hi is the Hausdorff distance between Tj and R1)
×
To ensure the correct growth of the combination of road segments, the following three constraints must be satisfied for the combination of road segments UT.
1.
The length similarity metric value of UT and Ri is greater than the length similarity metric value of UTB and Ri, where UTB denotes the previous combination of UT.
2.
The value of the shape similarity metric between UT and Ri is greater than the value of the shape similarity metric between UTB and Ri.
3.
θProj < 10 of UT and Ri to ensure that the directions of UT and Ri are similar.
If these three constraints are satisfied simultaneously, it is proved that this is a set of further optimized combinations. The combined matching process is as follows: First, select the road segment with the smallest disH as the starting road segment of UT and find its neighboring road segments in order, and combine them to obtain UT. Then, determine whether it meets the constraints, and if it does, add the combined road segments of UT to the temporary queue Temp, and repeat the combination and determination process until UT and Ri meet the geometric similarity metrics at the same time, and the values of simlen and simshp reach the maximum at the same time. Finally, add the matched pairs in Temp to the queue Final. If the selected UT starting road segment fails to find a matching pair that satisfies the geometric similarity metric with Ri after an attempted combination, then remove the starting road segment from the candidate set. The road segment with the smallest disH in the candidate set is continued so as to be selected as the starting road segment for an attempted combination until the best combination is found. As shown in Fig. 9, V1 is the Voronoi diagram corresponding to R1, and T1, T2, T3, ..., T7, and T8 are the candidate matching road segments after R1 eliminates the anomalous road segments, where the smallest disH is T6. The result of the first attempted combination is {T6, T7, T8}. Because UT cannot meet the geometric similarity metric threshold with R1, T6 is excluded and the second attempted combination is continued, with the result as {T1, T2, T4, T7, T8}, UT meets the geometric similarity metric threshold with R1, and the result is inserted into the queue Final. If no matching pair is obtained after eliminating all road segments in the candidate matching set, the selection of the next set of matching pairs is continued. By traversing all Vi, the obtained result is inserted into the queue Final.
Fig. 9
1:N road segments combination matching (Ri represents a road segment in the source dataset; Ti represents a road segment in the target dataset; V1 represents the Voronoi diagram of R1)
×
So far, all the identical roads in 1:0, 1:1, and 1:N cases have been selected, and the identical roads in M:N cases still need to be selected. First, put the Ri segments that failed to find a matching pair into the set C2, assume that the combination of the neighboring road segments in C2 is UR, select the first Ri in the set C2 as the starting road segment of UR, query the road segments adjacent to UR, and combine them by traversing the road segments in C2 until there are no road segments adjacent to UR. The UV is obtained by combining the Vi of all the Ri segments that make up the UR. Then, the candidate matching set C3 of UR is obtained by querying the road segments intersecting with UV in Road2, and M:N matching pairs are obtained through the process of disH calculation, elimination of outliers, and screening road segments of combination. Finally, the obtained result is inserted into the queue Final. As shown in Fig. 10, V1 and V2 are the Voronoi diagrams corresponding to R1 and R2, respectively, R1 and R2 are combined to form UR, and T1, T2, T3, T4, T5, and T6 are the candidate matching road segments after UR eliminates the abnormal road segments. The identical roads of R1 and R2 are obtained as T4 and T6 by attempted combinatorial matching. Once the matching result is obtained, all the road segments Ri that form UR need to be eliminated from C2, and then the next set of identical roads is selected. If a road segment Ri fails to find a neighboring road segment, it needs to be added to the 1:0 matching pair and eliminated from C2 to avoid affecting the selection of the remaining matching pairs. When |C2|= 0, the matching of all identical roads is completed, and the final queue is the final matching result.
Fig. 10
M:N road segment combination matching (Ri represents a road segment in the source dataset; Ti represents a road segment in the target dataset; Vi represents the Voronoi diagram of Ri)
×
4 Experiment and analysis
4.1 Experimental data
To verify the effectiveness and practicality of the VAMRN algorithm, we selected the experimental data in this study from the road networks in Nanchang, China; Zhejiang, China; and Buffalo, New York, in the USA. For Nanchang, we selected the road network data of 1:10,000 and 1:50,000, 1:50,000, and 1:250,000 map scales (hereafter referred to as 1WNCRoad, 5WNCRoad1, 5WNCRoad2, and 25WNCRoad, respectively) for the urban area. For Zhejiang, we selected 1:250,000 mixed urban and mountainous road network data and OpenStreetMap road network data (hereafter referred to as 25WZJRoad and ZJOSMRoad, respectively). For the city of Buffalo, we selected road network data from the city’s official website ((https://data.buffalony.gov/Infrastructure/Roads/33ss-qmvk) on August 13, 2021) and OpenStreetMap road network data (referred to as BuffaloRoad and BuffaloOSMRoad, respectively). The map scales of two datasets of Buffalo are unknown but they are similar, and their map scales are estimated approximately in the range of 1:2,000 to 1:10,000 according to the content details of road data. Four groups of experimental data are shown in Fig. 11a, b, c, and d. The road segment count, node count, total length, and coverage area statistics of each group of experimental data are given in Table 3.
Fig. 11
Experimental data of matching road network: a Group 1 dataset; b Group 2 dataset; c Group 3 dataset; and d Group 4 dataset
Table 3
Road network statistics
Group
Road network name
Source (S) and target (T)
Number of segments
Number of nodes
Total road length (km)
Coverage area (km2)
1
1WNCRoad
T
402
3,924
90.00
16.86
5WNCRoad1
S
171
1,091
59.25
2
5WNCRoad2
T
405
2,583
136.64
30.11
25WNCRoad
S
56
691
45.64
3
25WZJRoad
T
122
1,402
84.80
40.97
ZJOSMRoad
S
114
1,209
78.17
4
BuffaloRoad
T
572
1,610
62.48
4.90
BuffaloOSMRoad
S
206
1,371
64.47
×
4.2 Experiments and analysis of results
We conducted four sets of experiments using these four sets of road network experimental data. The hardware configuration of the experiment’s computer was an Intel Core i7-9750H CPU, 16 GB RAM, and an Nvidia GeForce GTX 1660 Ti graphics card. The software environment consisted of 64-bit Windows 10, Microsoft Visual Studio 2019 (C#), and the ArcGIS Engine 10.2. VAMRN, the classic buffer growing method (BG) (Walter and Fritsch 1999) and the classic probabilistic relaxation method (PR) (Yang et al. 2013) that were published in high quality journals were used for the relevant experiments and algorithm comparison analysis.
In the VAMRN experiments, ρlen = 0.85, ρshp = 0.85, and ρdir = 10. These parameters are obtained by analyzing the results of preliminary matching experiments and experts’ cognitive experiences of graphic similarity and experiences in cartographic synthesis. If the length or shape threshold is greater than threshold 0.85, missing matches may occur, while if the threshold is less than 0.85, matching errors may occur. The same applies to direction threshold. In the BG experiments, the buffer radius values were 38, 134, 90, and 14 m in four experiments. The method of setting buffer radius refers to the literature (Walter and Fritsch 1999). Namely the maximum value of Euclidean distances between corresponding objects recognized manually from two road datasets is selected as the buffer radius. In the PR experiments, the probability matrix iteration termination threshold was set to 0.0005, which is same to the threshold in the literature (Yang et al. 2013).
To quantitatively evaluate the matching quality and efficiency of each algorithm, we calculated and compared the Precision, Recall, F-measure, and the running time of the algorithms. Equations (5), (6), and (7) calculate the Precision, Recall, and F-measure of the matching results, respectively:
where TP denotes the number of correct matching pairs; FP denotes the number of wrong matching pairs; FN denotes the number of wrong matches or missed matches, and the sum of TP and FN is the actual number of matching pairs of manual matching results; α is the relative weight of precision; and when α = 1, then Precision in F-measure is considered equally important as Recall, and when α > 1, then Recall in F-measure is considered more important, and, vice versa, Precision is considered more important. We used the most commonly used value of F-measure at α = 1.
The results are shown in Table 4. All four groups of experimental results of VAMRN showed the largest values of Precision, Recall, and F-measure, with maximum values of 99.1, 97.4, and 98.2%, respectively. Compared with the BG method, the F-measure of VAMRN improved by 18.4, 29.6, 3.8, and 7.6%, respectively; compared with the PR method, the F-measure of VAMRN improved by 4.5, 2.8, 1.8, and 6.1%, respectively.
Table 4
Matching result statistics of the three algorithms (TP denotes the number of correct matching pairs; FP denotes the number of wrong matching pairs; and FN denotes the number of wrong matches or missed matches)
Group
Algorithm name
TP
FP
FN
Precision (%)
Recall (%)
F-measure (%)
1
VAMRN
147
3
4
98
97.4
97.7
BG
117
27
34
81.3
77.5
79.3
PR
138
7
13
95.2
91.4
93.2
2
VAMRN
49
1
4
98
92.5
95.1
BG
27
5
26
84.4
50.9
65.5
PR
48
3
5
94.1
90.6
92.3
3
VAMRN
111
1
3
99.1
97.4
98.2
BG
103
1
11
99.0
90.4
94.4
PR
108
2
6
98.2
94.7
96.4
4
VAMRN
159
15
30
91.4
84.1
87.6
BG
138
18
51
88.5
73.0
80.0
PR
150
29
39
83.8
79.4
81.5
The VAMRN algorithm also demonstrated good matching results for road networks with large positional discrepancies. As shown in Fig. 12, this part of the road network data came from the Group 2 dataset, the geometric structure of 25WNCRoad differed greatly from that of 5WNCRoad2, and the overall offset distance of 25WNCRoad was too great. The distance between R19 and T80 and R19 and T105 was too far to query the matching pairs by the buffer with an unreasonable radius in the buffer-based data matching. In the road network matching based on the PR method, the structural similarity of road segments at R26 was significantly different from that of T56, which could easily cause the false matching. In the VAMRN-based road network matching, the Voronoi diagram corresponding to each road segment in the source dataset successfully selected the correct matching road segments in the target dataset as the matching candidates, and the correct and complete matching pairs were finally obtained through the selection of matching pairs.
Fig. 12
Road network data with large positional discrepancies (Ri represents a road segment in the source dataset; Ti represents a road segment in the target dataset)
×
VAMRN, however, also had limitations similar to the BG and PR methods, which may have resulted in false matches or missed matches in cases in which the source dataset was too offset from the target dataset and the roads were relatively dense. As shown in Fig. 13, R45 was a segment of the source dataset, T179,T150, T161, and T170 were the candidate matching sets of R45, and the correct matching pairs of corresponding objects were R45 with T150 and T179. However, the offset of the dataset resulted in a smaller Hausdorff distance between T161 and T170, and the combination satisfied the constraints and geometric similarity metrics, resulting in a match between T161 and T170.
Fig. 13
Mismatching (R45 represents a road segment in the source dataset; Ti represents a road segment in the target dataset)
×
To analyze the efficiency of VAMRN, we counted the times of matching four datasets of different quantitative sizes with VAMRN, BG, and PR.
As shown in Table 5, the computation time of the VAMRN algorithm was slightly longer than that of the BG method, but much smaller than that of the PR method. The reason for the steep increase in time of the fourth group of VAMRN experiment is that there are too many intersections in the fourth dataset. Due to much intersections in the fourth dataset, the excessive number of road segments is obtained after interrupting the roads at the intersections, which leads to an increase in the number of combinations in the combination matching phase, thus it takes more time. Compared with PR, VAMRN has significant performance advantages. There are two mains reason for the long computation time of the PR method. The first is that it used a large buffer to obtain the candidate matching set, which resulted in a large amount of computation during the iteration and selection of matching results. The second is the complexity of the algorithmic process, which involved the steps of initial probability matrix acquisition, probability matrix iteration (including the calculation of compatibility coefficients and support coefficients of neighboring candidate matching pairs), and matching pair selection (including the calculation of structural similarity of matching pairs, matching growth process, and selection of robust matching pairs).
Table 5
Time comparison of the three algorithms
Dataset size
Time consumption (seconds)
Number of source road segments
Number of target road segments
VAMRN
BG
PR
171
402
9
6
783
56
405
5
1
412
122
114
3
1
187
206
572
217
3
1068
5 Conclusions
Object matching is the crucial technology of road data conflation. We proposed an innovative Voronoi diagram-based approach for matching multi-scale road networks (VAMRN). (1) VAMRN innovatively constructs Voronoi diagrams of road segments that can effectively avoid the intersection of Voronoi polygon and several road segments by the strategy of adding dense points at special intersections. Using Voronoi diagram to filter the candidate matching set of each road segment can effectively avoid manually setting the buffer radius used for searching candidate matching set, and prune the matching searching space, which avoids searching a large number of irrelevant candidates. It improved the universality and efficiency of object matching method. (2) Meanwhile, we designed the geometric similarity metrics including length, shape and direction, and a heuristic combinatorial growth strategy that are helpful for accurately matching multi-scale road data by using Voronoi diagrams. Our method only uses the geometric similarity metrics, which reduces the dependency on object attributes. However, the matching accuracy is still high. Moreover, the proposed approach has the ability to detect all matching pair types including 1:1, 1:N, M:1, M:N, 1:0, and 0:1.
In general, VAMRN demonstrated higher quality and good performance in overall matching results compared with the BG and PR methods, and offered a more universal and practical approach for matching multi-scale and complex road network data. However, VAMRN also had two shortcomings: (1) the threshold values for determining corresponding objects were set by expert experience, while when the map scales of identical objects span a large scale, some corresponding objects with large differences in shape may fail to match because of the threshold selection problem. The next work will investigate adaptively thresholds setting of geometric similarity metrics to reduce manual intervention; (2) when the positional discrepancies between the two road networks are great or the local regional roads are relatively dense, the Voronoi diagram of the source road segment may not query all matching candidates, which leads to false matches or missed matches. These two shortcomings need to be further investigated in depth. In addition, in future research, more multi-source and multi-scale road network data will be acquired for validation and optimization of our method.
Acknowledgements
We thank the anonymous reviewers for their constructive comments.
Declarations
Conflict of Interest
The authors declare no conflicts of interest.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
