1. bookAHEAD OF PRINT
Informacje o czasopiśmie
License
Format
Czasopismo
eISSN
2444-8656
Pierwsze wydanie
01 Jan 2016
Częstotliwość wydawania
2 razy w roku
Języki
Angielski
Otwarty dostęp

Studying a matching method combining distance proximity and buffer constraints

Data publikacji: 05 Sep 2022
Tom & Zeszyt: AHEAD OF PRINT
Zakres stron: -
Otrzymano: 23 Mar 2022
Przyjęty: 06 May 2022
Informacje o czasopiśmie
License
Format
Czasopismo
eISSN
2444-8656
Pierwsze wydanie
01 Jan 2016
Częstotliwość wydawania
2 razy w roku
Języki
Angielski
Introduction

The fast matching of road network data is very important for navigation map update, traffic planning and management, emergency response and so on [1]. With the continuous development of Web technology and the popularisation of intelligent mobile devices, the road network matching and updating technology based on volunteered geographic information (VGI) data has become a hot research topic in intelligent transportation system (ITS)- and geographic information system (GIS)-related industries.

Depending on the matching purposes, the road network matching methods based on VGI data can be divided into two categories [2, 3]: (1) road network improvement method; and (2) road network reconstruction method.

The former ones adopted track data to improve the existing road network data, such as extracting the node or centreline of the appointed road. In previous works [4], initial map and track data was used to improve the centreline of the designated roads in the road network. Tao et al. [5] used a spiral road network–updating strategy, which used a small amount of track data to update the road network locally. Zong-yao et al. [6] used the road mesh data to achieve incremental update of road network, which used the track point context distance information and hidden Markov model (HMM) to capture the mismatched track points. Li et al. [7] studied an urban road–updating method for low-sampling-rate floating vehicle data, which adopted an improved A* shortest path algorithm to improve the matching accuracy. Generally speaking, this kind of method relies on manual recognition and it is difficult to achieve automatic and batch processing.

The latter category of works directly extracted the geometric features of the entire road network from the track data and made a comprehensive comparison between the whole and local parts of the road network using the spatial scale and semantic features. Tian et al. [8] used a multi-level spreading algorithm to compare VGI data with old vector data to achieve incremental recognition of road network changes. In another paper [9], the characteristics of VGI data were fully utilised, a road segment distance similarity-matching algorithm and Delaunay triangulation fusion algorithm were adopted to achieve road network matching. Zhi-guo et al. [10] proposed a vehicle-track map-matching method based on Delaunay triangulation fusion algorithm (DST-MM), which was superior to existing algorithms in terms of low-sampling-frequency global positioning system (GPS) data-matching accuracy. To update and match the road network changes, Wang et al. [11] studied a new multi-scale dynamic method based on a hierarchical stroke mesh to detect matches between OpenStreetMap (OSM) data and professional surveying and mapping data. Zhang et al. [12] proposed a novel turning point-based offline map-matching method, which had the best efficiency at different sampling intervals. All in all, this kind of method needs to process massive track data with high computational complexity, so the matching accuracy is easily affected by data quality, road structure and other factors.

Global navigation satellite system (GNSS) track data is one of the main sources of VGI data, which can obtain mass travel trajectory data quickly and provide rich data resources for academic research [13]. However, GNSS track data has some problems, such as uncertain data quality, uneven spatial distribution and multi-source heterogeneity, which bring some difficulties and challenges to the road network-matching research using GNSS data.

This paper studies a road network-matching method based on GNSS track data, which can achieve road network data matching using the rough-to-fine strategy based on distance proximity and buffer constraints. The innovation of this paper can be summarised as follows. (1) The low-quality data in GNSS track data is removed by preprocessing and the deleted data is stored in vector form. (2) A distance proximity method is proposed for rough matching. (3) A rectangular or circular buffer is selected to achieve precise matching of road network data according to the buffer constraint criterion.

Proposed method

Figure 1 shows the structure diagram of this paper, which has two main processes: preprocessing and two-layer matching strategy.

Fig. 1

Structure diagram. GNSS, global navigation satellite system.

On the one hand, a rasterisation method is applied to eliminate low-quality track data, and then the track data is converted into vector format by binarisation, refinement and boundary-tracking operations. On the other hand, to achieve the matching of the unchanged road arc, disappearing road arc and the global and local new road arcs, different buffer constraint schemes are selected depending on the proposed distance proximity.

Preprocessing
Data screening

The GNSS track data simplifies the data acquisition method, enriches the data source and reduces the acquisition cost. In practice, the sampling point is sampled at a certain distance interval or time. The GNSS track data can be denoted as follows: T=(pk|k=1,2,,L) T = ({p_k}|k = 1,2, \ldots ,L) where pk contains the location and time information of the moving object at the sampling point.

GNSS track data has a distinct aggregation nature, i.e. most of them are located in the area on both sides of the road. However, due to the influencing factors, such as uncertainty of driving routes or speeds, sampling intervals or non-standard sampling methods, there are low-quality track data with inconsistent spatial distribution and data redundancy problems [14].

In order to reduce the complexity of the matching algorithm effectively, we adopt a rasterisation method to eliminate low-quality track data using the aggregation property of track data. The proposed rasterisation method is as follows. (1) Set the grid size in the original road network data, which is consistent with the vehicles’ size; (2) judge whether the track data falls into the grid; if it falls into the grid, the track data will be retained; otherwise, the track data will be removed.

For ease of identification, the original road network data is denoted by R(N, A), where N = (ni|i = 1, 2, ..., M) and A = (aj| j = 1, 2, ..., H) represent the road node and road arc, respectively.

Data format conversion

Data format conversion is to convert the GNSS track data into vector data. The process is as follows: the raster data is binarised to get the binary image; a skeleton extraction method [15] is used to refine the road centreline; a boundary tracking method [16] is adopted to change the obtained road centreline data into line segments starting from nodes or closed lines and then store them in vector form.

The converted GNSS track data is denoted by R′(N′, A′) for ease of representation, where N′ = (no|o = 1, 2, ..., Q) and A′ = (as|s = 1, 2, ..., G) represent the road node and road arc, respectively.

Two-layer matching strategy
Rough matching based on distance proximity

According to whether there is a relative change of road arc, the state of change of the road network can be divided into three situations: (1) unchanged road arc, i.e. R(N, A) completely matches with R′(N′, A′); (2) missing road arc, i.e. the road arc exists in R(N,A), but not in R′(N′, A′); (3) the newly added road arc, i.e. the road arc exists in R′(N′, A′), but not in R(N, A). In addition, the newly added road sections are divided into global sections and local sections.

Due to different data collection methods and time, the spatial location of the same road section is quite different. Direct road network data matching will not only lead to large errors but also reduce the running speed of the algorithm [17, 18]. Hence, a rough matching strategy is carried out to estimate the changing state of R′(N′, A′), and then different fine-matching strategies are selected to improve the matching efficiency.

The rough matching strategy is a distance proximity criterion, which is the ratio of the Euclidean distance between the beginning and the end nodes for R(N, A) and R′(N′, A′); the expression is as follows [19]: Sdis=D(NB,NC)D(NB,NC) {S_{dis}} = {{({{DN}_B^\prime},{\kern 1pt} {{N}_C^\prime})} \over {D({N_B},{\kern 1pt} {N_C})}} where D(NB,NC)=(xBxC)2+(yByC)2 D({N_B^\prime},{\kern 1pt} {N_C^\prime}) = \sqrt {{{({x_{B^\prime}} - {x_{C^\prime}})}^2} + {{({y_{B^\prime}} - {y_{C^\prime}})}^2}} represents the Euclidean distance of the beginning node and end node of R(N,A),D(NB,NC)=(xBxC)2+(yByC)2 R^\prime(N^\prime,{\kern 1pt} A^\prime),D({N_B},{\kern 1pt} {N_C}) = \sqrt {{{({x_B} - {x_C})}^2} + {{({y_B} - {y_C})}^2}} represent the Euclidean distance of the beginning node and end node of R(N, A).

Ideally, when the value of Sdis > 1, there is likely to be a newly added road arc; when the value of Sdis = 1, the position of the road nodes remains unchanged, but there may also be newly added arcs with these two nodes as the beginning node and end node; when the value of Sdis < 1, it is likely that there are missing road arcs.

Fine matching based on buffer constraint
Rectangular buffer constraint

The fine matching method based on rectangular buffer constraint is proposed to determine whether there are unchanged road arcs and global newly added road arcs.

As shown in Figure 2, aj and as are both road arcs; to determine the change state of aj relative to as, we should construct an external rectangle Lj for aj. The coordinate points of Lj are (xj min, yj min)(xj max, yj max); and then, we add a value l to Lj and get its boundary, so that the buffer region is within the boundary. The proposed rectangular buffer boundary is as follows: {Left=xjminlRight=xjmax+lBottom=yjminlTop=yjmax+l \left\{ {\matrix{ {Left = {x_{j{\kern 1pt} min}} - l} \hfill \cr {Right = {x_{j{\kern 1pt} max}} + l} \hfill \cr {Bottom = {y_{j{\kern 1pt} min}} - l} \hfill \cr {Top = {y_{j{\kern 1pt} max}} + l} \hfill \cr } } \right.

To determine whether as passes through the constructed rectangular buffer, its constraint conditions are as follows: {LeftxRightBottomyTop \left\{ {\matrix{ {Left \le x^\prime \le Right} \hfill \cr {Bottom \le y^\prime \le Top} \hfill \cr } } \right.

It can be concluded that if as passes through the constructed rectangular buffer, the road arc is considered unchanged; if as does not pass through the constructed rectangular buffer, as is marked as a newly added road arc, and aj is considered as a missing road arc.

Fig. 2

Rectangular buffer constraints.

Circular buffer constraint

The fine matching method based on circular buffer constraint is established to judge whether there are newly added local road arcs or missing road arcs. The proposed circular buffer constraint is shown in Figure 3.

Fig. 3

Circular buffer constraints.

Firstly, n nodes (including the beginning and end nodes) are selected on average in aj based on the horizontal direction, and the circular buffer is established respectively with radius r for these n nodes; secondly, n nodes (including the beginning and end nodes) are selected on average in as and the number of these n nodes that falls into the constructed circular buffer is counted and denote as m.

The relationship between the two road arcs is measured by the ratio of n and m. When m/n = 1, it is proved that there is no change, and the output is the reference road arc. Otherwise, the output has two cases: one is the road arc that crosses the buffer zone and is marked as an unchanged road arc, another is the arc that does not cross the buffer zone and is marked as a newly added local road arc. Hence, from Figure 3, the matching result is as follows: 6-7-8 is the unchanged road segment; 8-9-10 is the locally newly added road segment; and 3-4-5 is the missing road segment.

Algorithm execution process

To sum up, the execution process of the proposed method is shown in Figure 4.

Step 1: Input aj and as respectively, calculate the distance proximity of the road arc according to Formula (2). When Sdis = 1, go to next step; otherwise, go to Step 4;

Step 2: Establish the minimum enclosing rectangle Lj of aj, and the rectangular buffer constraint region is constructed according to Formula (3);

Step 3: Judge whether as passes through the buffer according to Formula (4). If Formula (4) is satisfied, it is considered that the road arc has no change; otherwise, mark as as the newly added road arc, and then go to Step 6;

Step 4: aj is divided into N − 1 sections on average in the horizontal direction, and the circular buffer is established for these n nodes; Similarly, as is divided into n − 1 sections on average in the horizontal direction.

Step 5: Count the number of n nodes of as falling into the circular buffer m. When m/n > 0.9, it is proved that there is no change, and the output is aj. Otherwise, the output is the road arc that crosses the buffer zone and is marked as an unchanged section, or the output is the section that does not cross the buffer zone and is marked as a newly added local road arc;

Step 6: Check whether the input of as and aj is complete. If the input is complete, go to next step; otherwise, go to Step 1;

Step 7: When the road arc cannot be searched or the specified number of iterations is reached, exit the iteration and end of the algorithm.

Fig. 4

Flowchart of the proposed method.

Experimental results and analysis

In this paper, the experiment takes Visual Studio 2019 as the development environment and is written with ArcGIS10.3 and C++. The GNSS track data is first preprocessed, and then the distance proximity criterion is used to judge the changing state of the road arc so as to select different fine-matching strategies. In the process of matching, it is necessary to construct a rectangular buffer for the reference road network data, and the size of the buffer distance is critical to the matching result [8]. The buffer distance is related to the average width of the road, the errors in data conversion and calculation; so, the average width of the actual road prevails in the experiment.

The experimental data is a public dataset [20], including 1:500 vector road network data and GNSS track data in Chicago. There are 543 track data and 83,542 sampling points in total. Figure 5 shows the proposed road network data matching process, Figure 5(A) is the original road network data, and Figure 5(B) is the GNSS track data.

Fig. 5

The process of road network matching.

As shown in Figure 5(C), after rasterisation of the GNSS track data, the low-quality track data is eliminated, and the grid size is basically the same as the vehicle size with 5 m × 5 m. The grid data is binarised, as shown in Figure 5(D), where the grey value of the track data that falls into the grid is set to zero; otherwise, it is set to one. The thinning result is shown in Figure 5(E). There exists deviation in the actual matching process; so, the value of the distance proximity that is close to 1.0 (1.05 ≥ Sdis ≥ 0.95) is viewed as the evaluation standard. The radius of the circular buffer is r = 10 m and the rectangular buffer is of l = 10 m. As shown in Figure 5(F), the original road network data and GNSS track data have good coincidence.

In order to verify the effectiveness of the road network matching method proposed in this paper, a set of comparative tests are given, as shown in Figure 6. To display the matching results more intuitively, the original road network data is marked as blue and the vectorised GNSS track data is marked as red.

Fig. 6

Matching result. GNSS, global navigation satellite system.

Figure 6 shows the matching result of road network data with more nodes and arcs. Figure 6(A) is the original road network, including 187 road nodes and 232 road arcs. Figure 6(B) is the vectorised GNSS track data, including 225 road nodes and 254 road arcs. As can be seen from the matching results in Figure 6(C) (blue represents the unchanged road area, red represents the newly added road area, and green represents the lost road area), although effective matching cannot be achieved for some small and curved road arcs for the relatively complex road data, the proposed matching algorithm has ideal matching effect in general.

Conclusion

The proposed matching method based on distance proximity and buffer constraints comprehensively considers the spatial geometric information of road arcs and nodes and takes into account the overall and local matching scheme, which lays a feasible foundation for road network data fusion. How to improve the applicability of the proposed method to road arcs with less track data needs to be further verified. In addition, the current matching methods are mainly aimed at the road network data of the same scale; there are relatively few mature technologies for data on different scales. We will pay more attention to matching of different-scale data in future work.

Fig. 1

Structure diagram. GNSS, global navigation satellite system.
Structure diagram. GNSS, global navigation satellite system.

Fig. 2

Rectangular buffer constraints.
Rectangular buffer constraints.

Fig. 3

Circular buffer constraints.
Circular buffer constraints.

Fig. 4

Flowchart of the proposed method.
Flowchart of the proposed method.

Fig. 5

The process of road network matching.
The process of road network matching.

Fig. 6

Matching result. GNSS, global navigation satellite system.
Matching result. GNSS, global navigation satellite system.

Arvind K, Suchi J, Deepak P, et al. A tree based approach for data pre-processing and pattern matching for accident mapping on road networks [C]. Proceedings of the National Academy of Sciences, India Section A: Physical Sciences, 2019, 89(3):453–466. ArvindK SuchiJ DeepakP A tree based approach for data pre-processing and pattern matching for accident mapping on road networks [C] Proceedings of the National Academy of Sciences, India Section A: Physical Sciences 2019 89 3 453 466 10.1007/s40010-018-0495-5 Search in Google Scholar

Lu Hai-Yang. Research on road network construction and augmentation based on GNSS vehicle trajectories [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(02):268–270. LuHai-Yang Research on road network construction and augmentation based on GNSS vehicle trajectories [J] Acta Geodaetica et Cartographica Sinica 2019 48 02 268 270 Search in Google Scholar

Xu D W, Wang Y D, Peng P, et al. Real-time road traffic state prediction based on kernel-KNN [J]. Transportmetrica A-Transport Science, 2020, 16(1):104–118. XuD W WangY D PengP Real-time road traffic state prediction based on kernel-KNN [J] Transportmetrica A-Transport Science 2020 16 1 104 118 10.1080/23249935.2018.1491073 Search in Google Scholar

Kasemsuppakorn P, Karimi H A. A pedestrian network construction algorithm based on multiple GPS traces [J]. Transportation Research Part C: Emerging Technologies, 2013, 26:285–300. KasemsuppakornP KarimiH A A pedestrian network construction algorithm based on multiple GPS traces [J] Transportation Research Part C: Emerging Technologies 2013 26 285 300 10.1016/j.trc.2012.09.007 Search in Google Scholar

Wu Tao, Xiang Long-Gang, Gong Jian-Ya. Renewal of road networks using map-matching technique of trajectories [J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(04):507–515. WuTao XiangLong-Gang GongJian-Ya Renewal of road networks using map-matching technique of trajectories [J] Acta Geodaetica et Cartographica Sinica 2017 46 04 507 515 Search in Google Scholar

Sha Zong-Yao, Wang An, Wang Xin-Yi, An incremental road network update based on road network meshes [J], Geomatics and Information Science of Wuhan University, 2019, 44(8):1107–1114. ShaZong-Yao WangAn WangXin-Yi An incremental road network update based on road network meshes [J], Geomatics and Information Science of Wuhan University 2019 44 8 1107 1114 Search in Google Scholar

Li B Z, Cai Z L, Kang M J, et al. A trajectory restoration algorithm for low-sampling-rate floating car data and complex urban road networks [J], 2020, 35(4):717–740. LiB Z CaiZ L KangM J A trajectory restoration algorithm for low-sampling-rate floating car data and complex urban road networks [J], 2020 35 4 717 740 10.1080/13658816.2020.1825721 Search in Google Scholar

Tian Wen-wen, Zhu Xin-yan, Guo Wei. A VGI vector road data increment distinguishing research based on multilevel spreading algorithm [J]. Geomatics and Information Science of Wuhan University, 2014, 39(08):963–967+973. TianWen-wen ZhuXin-yan GuoWei A VGI vector road data increment distinguishing research based on multilevel spreading algorithm [J] Geomatics and Information Science of Wuhan University 2014 39 08 963 967+973 Search in Google Scholar

Zhou Z J, Yang L, An X Y, et al. A hierarchical matching method for vectorial road networks using Delaunay triangulation [J]. ISPRS International Journal of Geo-Information, 2020, 9(9):509. ZhouZ J YangL AnX Y A hierarchical matching method for vectorial road networks using Delaunay triangulation [J] ISPRS International Journal of Geo-Information 2020 9 9 509 10.3390/ijgi9090509 Search in Google Scholar

Wang Zhi-Guo, Sheng Ye-Hua, Huang Yi, et al. Matching and fusion methods for VGI data of road network [J]. Engineering of Surveying and Mapping, 2018, 27(06):64–68+76. WangZhi-Guo ShengYe-Hua HuangYi Matching and fusion methods for VGI data of road network [J] Engineering of Surveying and Mapping 2018 27 06 64 68+76 Search in Google Scholar

Wang Y, Yu B, Zhu F, et al. Hierarchical stroke mesh: a new progressive matching method for detecting multi-scale road network changes using OpenStreetMap [J]. Soft Computing, 2021, 25(4):1–19. WangY YuB ZhuF Hierarchical stroke mesh: a new progressive matching method for detecting multi-scale road network changes using OpenStreetMap [J] Soft Computing 2021 25 4 1 19 10.1007/s00500-020-05371-z Search in Google Scholar

Zhang D, Dong Y, Guo Z. A turning point-based offline map matching algorithm for urban road networks [J]. Information Sciences, 2021, 565(2). ZhangD DongY GuoZ A turning point-based offline map matching algorithm for urban road networks [J] Information Sciences 2021 565 2 10.1016/j.ins.2021.02.052 Search in Google Scholar

Yozevitch R, Moshe B B. A robust shadow matching algorithm for GNSS positioning [J]. Navigation Journal of the Institute of Navigation, 2015, 62(2):95–109. YozevitchR MosheB B A robust shadow matching algorithm for GNSS positioning [J] Navigation Journal of the Institute of Navigation 2015 62 2 95 109 10.1002/navi.85 Search in Google Scholar

Wang Y H, Yu B B, Zhu F X, Hierarchical stroke mesh: a new progressive matching method for detecting multi-scale road network changes using Open Street Map [J]. Soft Computing, 2021, 25(4):3155–3173. WangY H YuB B ZhuF X Hierarchical stroke mesh: a new progressive matching method for detecting multi-scale road network changes using Open Street Map [J]. Soft Computing 2021 25 4 3155 3173 10.1007/s00500-020-05371-z Search in Google Scholar

Han L, Chu B, Gao X. Gaussian curvature constrained skeleton extraction method based on MRG [J]. Journal of Computer-Aided Design & Computer Graphics, 2009, 21(9):1227–1231. HanL ChuB GaoX Gaussian curvature constrained skeleton extraction method based on MRG [J] Journal of Computer-Aided Design & Computer Graphics 2009 21 9 1227 1231 Search in Google Scholar

Wang Wei, Hua Xue-Dong, Zheng Yong-Tao, Multi-network integrated traffic analysis model and algorithm of comprehensive transportation system [J]. Journal of Traffic and Transportation Engineering, 2021, 21(2):159–172. WangWei HuaXue-Dong ZhengYong-Tao Multi-network integrated traffic analysis model and algorithm of comprehensive transportation system [J]. Journal of Traffic and Transportation Engineering 2021 21 2 159 172 10.1117/12.2619899 Search in Google Scholar

Bian W T, Cui G, Wang X. A trajectory collaboration based map matching approach for low-sampling-rate GPS trajectories [J]. Sensors, 2020, 20(7):2057. BianW T CuiG WangX A trajectory collaboration based map matching approach for low-sampling-rate GPS trajectories [J] Sensors 2020 20 7 2057 10.3390/s20072057718057132268569 Search in Google Scholar

Wang F P, Li Y. Mapping road based on multiple features and B-GVF snake. International Journal of Pattern Recognition and Artificial Intelligence, 2020, 34(14):2050035. WangF P LiY Mapping road based on multiple features and B-GVF snake International Journal of Pattern Recognition and Artificial Intelligence 2020 34 14 2050035 10.1142/S0218001420500354 Search in Google Scholar

Liu Z J, Fang J, Tong, Y F, et al., Deep learning enabled vehicle trajectory map-matching method with advanced spatial-temporal analysis [J]. IET Intelligent Transport Systems, 2020, 14(14):2052–2063. LiuZ J FangJ TongY F Deep learning enabled vehicle trajectory map-matching method with advanced spatial-temporal analysis [J]. IET Intelligent Transport Systems 2020 14 14 2052 2063 10.1049/iet-its.2020.0486 Search in Google Scholar

https://www.cs.uic.edu/bin/view/Bits/Software [DB], [2020-7-28]. https://www.cs.uic.edu/bin/view/Bits/Software [DB], [2020-7-28]. Search in Google Scholar

Polecane artykuły z Trend MD

Zaplanuj zdalną konferencję ze Sciendo