%20-%20https://sketch.com%20--%3e%3ctitle%3e3ECBBF50-FD08-412A-943D-2CFC5E025A16%3c/title%3e%3cdesc%3eCreated%20with%20sketchtool.%3c/desc%3e%3cg%20id='Stylesheet'%20stroke='none'%20stroke-width='1'%20fill='none'%20fill-rule='evenodd'%3e%3cg%20transform='translate(-926.000000,%20-668.000000)'%20id='BUTTONS'%3e%3cg%20transform='translate(100.000000,%20597.000000)'%3e%3cg%20id='BTN-/-RIGHTS'%20transform='translate(816.000000,%2065.000000)'%3e%3cg%20id='ICON-/-Rights'%20transform='translate(10.000000,%206.000000)'%3e%3cpath%20d='M13.5752841,0%20L1.34943182,0%20C0.59375,0%200,0.586666667%200,1.33333333%20L0,22.6666667%20C0,23.4133333%200.620738636,24%201.34943182,24%20L17.6505682,24%20C18.40625,24%2019,23.3866667%2019,22.6666667%20L19,5.36%20L13.5752841,0%20Z%20M13.5752841,1.89333333%20L17.0838068,5.36%20L13.5752841,5.36%20L13.5752841,1.89333333%20Z%20M1.34943182,22.6666667%20L1.34943182,1.33333333%20L12.1988636,1.33333333%20L12.1988636,5.36%20C12.1988636,6.10666667%2012.7926136,6.69333333%2013.5482955,6.69333333%20L17.6235795,6.69333333%20L17.6505682,22.6666667%20L1.34943182,22.6666667%20Z'%20id='Shape'%20fill='%23595959'%20fill-rule='nonzero'%3e%3c/path%3e%3ccircle%20id='Oval'%20stroke='%23595959'%20stroke-width='1.5'%20fill='%23595959'%20cx='9.5'%20cy='13.5355339'%20r='5.5'%3e%3c/circle%3e%3cpolyline%20id='Path-2'%20stroke='%23FFFFFF'%20stroke-width='1.5'%20transform='translate(9.500000,%2013.035534)%20rotate(45.000000)%20translate(-9.500000,%20-13.035534)%20'%20points='8%2016.0355339%2011%2016.0355339%2011%2010.0355339'%3e%3c/polyline%3e%3c/g%3e%3c/g%3e%3c/g%3e%3c/g%3e%3c/g%3e%3c/svg%3e)
1. INTRODUCTION
In recent years, autonomous driving technology has drawn more and more attention. The autonomous vehicle comprises several systems, including perception and planning systems. Underlying these systems there is a public model: the map (Bender et al., Reference Bender, Ziegler and Stiller2014). However, current widely used commercial navigation maps cannot meet the demands of high level applications due to their serious lack of accuracy, contents and completeness (Tao et al., Reference Tao, Bonnifait, Fremont and Ibanez-Guzman2013), hence the necessity of developing detailed lane-level maps has been widely recognised (Naranjo et al., Reference Naranjo, Jiménez, Aparicio and Zato2009; Nedevschi et al., Reference Nedevschi, Popescu, Danescu, Marita and Oniga2013). In industry, lane-level maps have been deployed in autonomous vehicles, including by Google (Guizzo, Reference Guizzo2011) and Daimler (Ziegler et al., Reference Ziegler, Bender, Schreiber, Lategahn, Strauss, Stiller, Dang, Franke, Appenrodt and Keller2014).
A lane-level map (LLM) that represents the detailed lane information on a road is anticipated to provide higher resolution data to autonomous driving systems. Currently, there are some LLM models available, such as the route network definition file (RNDF, DARPA Urban Challenge, 2007), OpenDRIVE (Dupuis, Reference Dupuis2010), Lanelets (Bender et al., Reference Bender, Ziegler and Stiller2014), and the smart map (Liu et al., Reference Liu, Wu, Fang, Hu and Song2015). Meanwhile commercial navigation maps (CNM) are widely used in human driving navigation today. However, CNMs model roads as polylines, which causes loss of information about the road. Intuitively, CNM has ample global attributes that go beyond on-board sensor visibilities and LLM has highly defined local lane-level data. The autonomous driving system inevitably involves both global and local data. For example, the hierarchical planning system, which consists of mission planning and motion planning, has been employed in some autonomous vehicles (Leonard et al., Reference Leonard, How, Teller, Berger, Campbell, Fiore, Fletcher, Frazzoli, Huang, Karaman, Koch, Kuwata, Moore, Olson, Peters, Teo, Truax, Walter, Barrett, Epstein, Maheloni, Moyer, Jones, Buckley, Antone, Galejs, Krishnamurthy and Williams2008; Fan et al., Reference Fan, Zhu, Liu, Zhang, Zhuang, Li, Zhu, Hu, Li and Kong2018). Mission planning is performed over the road network to find a user-defined optimal route between origin and destination; motion planning generates an appropriate path to achieve local objectives (Pendleton et al., Reference Pendleton, Andersen, Du, Shen, Meghjani, Eng, Rus and Ang2017). CNM and LLM can offer global and local information to autonomous driving systems and the linking relations between CNM and LLM can greatly facilitate them, especially the hierarchical planning system. For instance, in order to guide an autonomous car, Alonso et al. (Reference Alonso, Milanés, Onieva, Pérez, González and de Pedro2011) proposed a two-level cartographic system to provide different linked map data. Analogously, in the well-known open source autonomous driving platform Autoware, CNM was used to search for a route, then the route was reflected onto a three-dimensional map to guide the autonomous vehicle (Kato et al., Reference Kato, Takeuchi, Ishiguro, Ninomiya, Takeda and Hamada2015). The linking relations between LLM and CNM are of great importance for mapping information between different applications using different map data among autonomous driving systems. They also facilitate data sharing and interoperation between LLM and CNM, such as CNM's error detection and correction via LLM. Unfortunately, due to the different data capturing and processing methods and rules for the different raw data that are used to generate CNM and LLM, it is impossible even for one map supplier to make explicit one-to-one mapping between CNM and LLM. In this paper, an approach is proposed to build the linking relations automatically.
The remainder of this paper is organised as follows. In Section 2, the literature on road networks matching is reviewed. Section 3 gives an introduction and comparison of LLM and CNM. In Section 4, the proposed road networks matching approach is elaborated. The linking relations are built in Section 5. In Section 6, the experiments are conducted and the results are discussed. Finally, Section 7 provides the conclusion and future works.
2. LITERATURE ON ROAD NETWORKS MATCHING
In GIS (geographic information systems), geographic data set integration is the process of establishing relations between corresponding object instances in different geographic data sets of a certain region (Uitermark and Cadastre, Reference Uitermark and Cadastre1996). Saalfeld (Reference Saalfeld1988) initially proposed an automatic method to consolidate two vector maps. Doytsher et al. (Reference Doytsher, Filin and Ezra2001) detected counterpart nodes and constructed paths between the nodes at first; then detected the corresponding paths by average distance. Similarly, Volz (Reference Volz2006) detected ‘seed nodes’ and then matched the emanating edges through a weighted sum function. Due to being governed by many fixed thresholds and weightings, the approach might fail when applied to other map databases; and it was a nontrivial work to determine the thresholds and weightings. Distance is commonly used to measure the similarity of geometric objects. Mustière and Devogele (Reference Mustière and Devogele2008) used Euclidean and Hausdorff distances to pre-match nodes and arcs. Devogele (Reference Devogele2002) cast the process of matching homologous objects as identifying homologous points using Frechet distance. Aiming to speed up the matching process, Safra et al. (Reference Safra, Kanza, Sagiv and Doytsher2006) detected homologous roads merely relying on the polyline's endpoint location. The distance based methods might be invalid if the maps were of great positional difference. Unlike these approaches, Zhang et al. (Reference Zhang, Shi and Meng2005) chained the line objects that shared the same attribute together to construct reference lines to match road networks. Following corresponding objects detection, some operations were performed to achieve particular goals, such as shifting one map to align with another (Doytsher et al., Reference Doytsher, Filin and Ezra2001), improving the positional accuracy (Devogele, Reference Devogele2002), detecting the difference between the datasets (Koukoletsos et al., Reference Koukoletsos, Haklay and Ellul2012; Abdolmajidi et al., Reference Abdolmajidi, Mansourian, Will and Harrie2015), and building the linking relations for homologous objects (Volz and Walter, Reference Volz and Walter2004; Volz, Reference Volz2006).
Although the above approaches matched the networks with different positional accuracy, date and details, etc., there was a common feature of the networks – using a polyline to represent a road. The road networks matching could be regarded as the process of detecting homologous one-dimensional linear objects. However, in LLM, the road is no longer treated as a one-dimensional linear object. To date, there are few available methods designed to cope with automatic networks matching for LLM and CNM.
3. LLM AND COMMERCIAL NAVIGATION MAP
3.1. LLM
LLMs have a prominent role not only in improved positional accuracy, but also in higher resolution. LLM represents many geometrical entities that are not present in CNM, such as lane centreline. An instance of LLM is shown in Figure 1 that includes detailed LLM models of the road.
An instance of LLM.
The LLM model is illustrated by Figure 2. Road is composed of a sequence of RoadSections. Within a RoadSection, some attributes of the road remain constant. For example, in Figure 2, Road1 consists of RoadSection1 and RoadSection2; the driver can change lanes freely in RoadSection2, but it is forbidden in RoadSection1. RoadSection contains all the lanes inside it. Lane boundaries and lane centreline form the lane. Lane centrelines are connected at lane node. Lane centreline and lane node form the lane-level network of LLM. The leftmost line of the road is named the road reference line, denoted as r. In order to maintain the continuity of the road, only one instance of r is defined between two adjacent junctions.
Model of LLM.
3.2. LLM's cartographic primitives and network
In LLM, lane node and lane centreline are the cartographic primitives and the atomic construction elements of the network. The lane-level network is a directed graph, denoted as TN LLM, where lane node is vertex and lane centreline is edge. The sets of lane nodes and lane centrelines are denoted as LN and LCL respectively, and TN LLM = (LN, LCL).
3.3. CNM
The node/link model has a significant advantage in supporting navigation and is the prevailing network model for navigation maps (Goodchild, Reference Goodchild2000). In CNM, the road is modelled as a link and represented by its centreline. The node is the topological junction of two or more links. The properties of the road network are inherently modelled as attributes of nodes and links. Various navigation oriented data are attached to the CNM network, such as guiding data, addresses and POI (points of interest). Using the centreline to represent the road causes the CNM to lose most lane information. The road section of Figure 2 is simplified in CNM, as Figure 3 shows.
Model of CNM.
3.4. CNM's cartographic primitives and network
The cartographic primitives and atomic construction elements of CNM are node and link, denoted as node and link; they form the road-level network TN CNM = (NODE, LINK), where NODE and LINK denote the set of nodes and links, respectively.
3.5. Comparison of LLM and CNM
Table 1 summarises the difference between LLM and CNM. It can be found that LLM and CNM mainly differ in purpose, resolution and precision; in data content and function aspects, LLM and CNM are complementary, which gives a strong reason to link them together. The most significant difference between LLM and CNM is their networks. Compared with the road-level network TN CNM, TN LLM is a more complicated lane-level network. Figure 4 illustrates the difference through real data, where the red is TN CNM and the black is TN LLM.
Comparison of LLM and CNM.
TN LLM (black) and TN CNM (red).
4. MATCHING THE NETWORKS OF LLM AND CNM
In this paper, a finite connected road sequence is called a path. The junction of LLM and CNM is respectively denoted as jun and cnmjun. It is hypothesised that there is one and only one path between two adjacent junctions. Based on the hypothesis, the principle of the approach is depicted in Figure 5. For network1 and network2, if the homologous junction pairs could be distinguished, e.g., 〈jun1, cnmjun1〉, then the paths between the two adjacent homologous junction pairs, e.g., 〈jun1, cnmjun1〉 and 〈jun2, cnmjun2〉, are seen as corresponding, e.g., 〈path1, path1′〉.
Principle of the proposed approach.
The overall process of the approach is shown in Figure 6, where the solid and dotted arrow indicate the process and the dependence of process, respectively. First, TN LLM and TN CNM are reconstructed into the graphs with common structure (Section 4.1), then corresponding junctions are detected using a strategy called multi-filter (Section 4.2). Following that, in stages 3 and 4, a so-called forward path exploring algorithm is developed to find and validate the corresponding paths (Section 4.3). Finally, the linking relations of networks of LLM and CNM are built automatically (Section 5).
The processes and their dependence.
4.1. Topology reconstruction for TN LLM and TN CNM
Generally, the networks to be matched are preprocessed to build specific structures to pave the way for network matching (Volz, Reference Volz2006; Mustière and Devogele, Reference Mustière and Devogele2008; Abdolmajidi et al., Reference Abdolmajidi, Mansourian, Will and Harrie2015; Zhang et al., Reference Zhang, Yao and Meng2016). In this paper, topology reconstruction is performed initially to eliminate the topological inconsistencies between CNM and LLM.
Physically, a junction connects at least three road segments. In this paper, junctions are classified into three broad families: diverging, merging and crossing. As shown in Figure 7, the diverging junction connects one incoming road segment and two outgoing road segments; the merging junction connects two incoming road segments and one outgoing road segment; and the crossing junction connects more than three road segments.
Types of junction.
For both TN LLM and TN CNM, road and junction are regarded as atomic construction elements to construct new networks. In TN LLM = (LN, LCL), a junction is defined as a set of lane nodes. As defined above, the diverging/merging junction owns the sole incoming/outgoing road (the crossing junction is regarded as several independent junctions; each junction uses an inside virtual road to connect the incoming and outgoing road). Therefore, Equation (1) is used to identify all the lane nodes of the same junction. Diverging, merging and crossing junctions are denoted by jun div, jun mer and jun cro, respectively. Lane node (denoted as ln) has a junction type attribute that is returned by function type (ln). For example, in Figure 2, based on our specification, type (ln 2) = Diverging, yet type (ln 1) = Null. For lane centreline set setLCL, the road set it belongs to is denoted as setRoad, namely setRoad = Belongto(setLCL). Function InLCLs(ln)/OutLCLs(ln) returns the lane centreline set incoming to/outgoing from ln; and ∅ represents the empty set. For example, in Figure 2, based on Equation (1), the lane nodes, ln 2 and ln 3, of Junction1 can be identified and collected from LN because type(ln 2) = type(ln 3) = Diverging and 
${\rm Belongto}( {\rm InLCLs}( {ln}_{2}) ) \cap {\rm Belongto}( {\rm InLCLs}( {ln}_{3} ) ) = {Road1}\ne \emptyset$.
$$\begin{split} \textit{jun}_{div} &=\lcub {\textit{ln}\vert {\rm type}(\textit{ln})=\textit{Diverging},\cap {\rm Belongto}({\rm InLCLs}(\textit{ln}))\ne \emptyset } \rcub \\ \textit{jun}_{mer} &=\lcub {\textit{ln}\vert {\rm type}(\textit{ln})=\textit{Merging},\cap {\rm Belongto}({\rm OutLCLs}(\textit{ln}))\ne \emptyset } \rcub \\ \textit{jun}_{cro} &=\left\{\textit{ln}\vert {\rm type}(\textit{ln})=\textit{Crossing},\bigcap\limits_{i\not= j} ({\rm Belongto}({\rm InLCLs}(\textit{ln}_i))\right.\\ &\quad\left.\vphantom{\bigcap\limits_{i\ne j}} \cap {\rm Belongto}({\rm OutLCLs}(\textit{ln}_j)))\ne \emptyset\right\} \\ \end{split}$$The topological connection of ln is the set of the incoming and outgoing lane centrelines, as expressed in Equation (2).
$${\rm TopoLN(ln)}={\rm InLCLs(ln)}\cup {\rm OutLCLs(ln)}$$Similarly, the topological connection of a junction is the set of the incoming and outgoing roads. For the lane centreline set TopoLN(ln), the road set it corresponds to can be obtained by Belongto(TopoLN(ln)). For a junction jun, all the connecting roads can be extracted by Equation (3), where x denotes the number of lane nodes of jun.
$${\rm TopoJun}(jun)=\bigcup\limits_i^x {\rm Belongto}({\rm TopoLN}(ln_i)),ln_i\in jun$$
Through Equations (1–3), the connection of the junction can be extracted; for instance, in Figure 2, it can be known that Junction1 connects Road1, Road2 and Road3, because 
$\{ Road1, \; Road2, \; Road3\} = \bigcup\limits_{i=1}^{2} {\rm Belongto}( {\rm TopoLN}( {ln}_{i} ) ) , \; {ln}_{i} \in \{ {ln}_{2}, \; {ln}_{3}\} $. Suppose JUN DIV, JUN MER and JUN CRO are the set of diverging, merging and crossing junctions respectively, namely jun div ∈ JUN DIV, jun mer ∈ JUN MER, jun cro ∈ JUN CRO, then 
${JUN}={JUN}_{DIV} \cup {JUN}_{MER} \cup {JUN}_{CRO}$, where JUN is the vertex set, jun ∈ JUN. Taking r as the edge (road reference line represents road, geometrically), R denotes the edge set. Consequently, the reconstructed network of TN LLM is 
${TN}_{LLM\_rec} =( {JUN}, \; R) $.
For the CNM network TN CNM = (NODE, LINK), the nodes are directly marked as different junctions according to Equation (4).
$$\begin{split} \textit{cnmJUN}_{DIV} &=\lcub {node\vert {\rm Indegree}(node)=1,{\rm Outdegree}(node)=2}\rcub ; \\ \textit{cnmJUN}_{MER} &=\lcub {node\vert {\rm Indegree}(node)=2,{\rm Outdegree}(node)=1}\rcub ; \\ \textit{cnmJUN}_{CRO} &=\lcub {node\vert {\rm Indegree}(node)+{\rm Outdegree}(node)>3}\rcub ; \\ \textit{cnmNODE} &= \lcub {node\vert node\notin cnmJUN_{DIV} ,node\notin cnmJUN_{MER},node \notin cnmJUN_{CRO} } \rcub . \\ \end{split}$$
Function Indegree(node) and Outdegree(node) return the in-degree and out-degree of node; cnmJUN DIV, cnmJUN MER, cnmJUN CRO and cnmNODE denote the set of diverging, merging, crossing and general nodes, respectively. Through Equation (4), TN CNM is reconstructed into 
${TN}_{CNM\_rec} =( {cnmJUN}, \; {LINK}) $, where 
${cnmJUN} = {cnmJUN}_{DIV} \cup {cnmJUN}_{MER} \cup {cnmJUN}_{CRO} \cup {cnmNODE}$.
4.2. Detecting the corresponding junctions in TN LLM_rec and TN CNM_rec
Most of the topological difference has been eliminated through topology reconstruction. Thus, the design of the corresponding junction detection algorithm should consider the geometric inconsistencies between LLM and CNM. There are two ways to make the algorithm stronger: (1) not using sensitive thresholds and (2) avoiding using weightings based on limited experience. Taking into account the principles, the so-called multi-filter algorithm is designed for homologous junction detection.
4.2.1. The filters
As Tobler's first law indicates: near things are more related than distant things. In reality, spatially close objects usually have similar spatial features. It is hard to distinguish the junctions if only spatial characteristics are considered because some spatial metrics are usually correlated, as two nearby road segments generally have a similar direction due to the limitation of terrain. Due to the geometric inconsistencies between LLM and CNM and the spatial features correlation between near objects, heterogeneous metrics selected from different aspects, like geometry, topology and semantics, should be utilised to distinguish the junctions. In this paper, the following five filters are used.
(1) Euclidean Distance (ED): ED is a geometric metric. For each jun ∈ JUN, the nearest 10 candidate junctions (denoted as cnmjun cd) in
${TN}_{CNM\_rec}$ are selected to initialise the candidate set, Setcandidates, where the corresponding junction of jun is anticipated to be picked out.(2) Topological Structure (TS): TS is a topological metric and characterised as diverging, merging and crossing as shown in Figure 7. The cnmjun cd with different TS against jun will be rejected from the candidate set.
(3) Type of Main Road (TMR): The road incoming to a diverging junction (r1 in Figure 7) or outgoing from a merging junction (r2 in Figure 7) is defined as the main road. Because the junction has a sole main road, the characteristics of the main road can be used to distinguish the junction efficiently. TMR is a semantic metric. In this paper, road is roughly classified as: highway and non-highway. The candidate with different TMR against jun will be kicked out. TMR is just applied to the junction whose degree is 3.
(4) Direction of Main Road (DMR): DMR is a geometric metric related to the main road. For the road incoming to a junction, its direction vector consists of the point at a distance of 10 m behind its end point (as initial point) and the end point (as terminal point). For the road outgoing from a junction, its direction vector consists of the start point (as initial point) and the point at a distance of 10 m front of its start point (as terminal point). The direction vectors of the main roads of jun and cnmjun cd are compared; the candidate that induces an angle greater than 30 degrees is rejected. DMR is also just applied to the 3-degree junction.
(5) Geometrical Shape (GS): Some inappropriate candidates can be kicked out via the above filters, however, it is hard to distinguish the junctions with the same TS, TMR and DMR, as shown in Figure 8. To cope with this situation, a junction shape similarity measurement function is proposed. GS is the third geometric metric. The junction's shape is formed by a set of vectors and the angles between vectors reflect its shape, as shown in Figure 8. Taking the direction vectors of the roads connecting to jun, the normalised direction vector set is
${\bf V}_{{\bf jun}} = {\rm \{ }{\bf v}_{\bf 1},\;{\bf v}_{\bf 2},\;\cdots ,\;{\bf v}_{\bf n}{\rm \} }$; and the normalised direction vector set of cnmjun cd is ${\bf V}_{{\bf cnmjun}} = {\rm \{ }{\bf v}_{\bf 1},\;{\bf v}_{\bf 2},\;\cdots ,\;{\bf v}_{\bf m}{\rm \} }$. Then ${\textbf{simM}}={\textbf{V}}_{{\textbf{jun}}}^{\textbf{T}} \times {\textbf{V}}_{{\textbf{cnmjun}}}$, and the similarity measure function is:
(5)In Equation (5), simM(j) returns j-th row of simM; d is the distance between jun and cnmjun cd, and a is the scaling parameter. In this paper, a = 50 m, the similarity of junctions within 50 m will be enhanced; otherwise, diminished.$${\rm Sim}(\textit{jun}_k, \textit{cnmjun}_{cd})=\frac{\sum_{j=1}^n {\max ({\rm simM}(j))} }{\max (m,n)\cdot (d/a)}$$
Different shapes of junctions.
4.2.2. Adaptive multi-filter algorithm for corresponding junction detection
In this algorithm, the five filters are employed to eliminate the inappropriate candidates, gradually.
The entire process of multi-filter algorithm is explained by Figure 9. First, the candidate set, Setcandidates, is initialised; then the conflict candidates are rejected by TS, TMR and DMP filters. The three filters are of distinguishable and error-free characteristics; for example, it is very easy to recognise two junctions of different TS; and whether LLM or CNM, it is almost impossible to assign wrong TS and TMR related attributes to the released maps. The DMR of 30 degrees threshold is relaxed enough to avoid misjudgement. After the screening process, if there are more than one candidates, the best matching will be directly determined by GS filter. In our experiments, most of the corresponding junctions were found by ED, TS, TMR and DMR filters and only four junctions were determined by GS. The final survival is considered as the corresponding junction of jun. If no one survives, new candidates will be pushed into Setcandidates. The pushing is not more than two times, otherwise the algorithm fails.
Flowchart of multi-filter algorithm.
4.3. Finding the corresponding paths in TN LLM_rec and TN CNM_rec
The strategy Figure 10 illustrates is used to find the corresponding paths between two adjacent corresponding junction pairs in 
${TN}_{LLM\_rec}$ and 
${TN}_{CNM\_rec}$.
(1) First, starting from any junction junS of TN LLM_rec, Pexplorer (forward path exploring algorithm, see Figure 11) walks along the road until reaching the matched adjacent junction junA. The road passed through is marked as an element of the path, e.g.
$path_{LLM} = {\rm \{ }r1,\;r3{\rm \} }$.(2) Based on the junction correspondence built in Section 4.2, it is easy to find the corresponding junction of junS in
${TN}_{CNM\_rec}$, namely cnmjunS.(3) Similarly, in
${TN}_{CNM\_rec}$, starting from cnmjunS, Pexplorer walks to the matched adjacent junction cnmjunA, and the passed path is path CNM = {link1, link3, link4}.(4) Finally, the correspondence of junA and cnmjunA will be validated. If they are corresponding, path LLM and path CNM are regarded as corresponding; otherwise, the algorithm fails.
Finding the corresponding paths in TN LLM_rec and TN CNM_rec.
Pseudocode of forward path exploring algorithm.
Pexplorer is explained through the pseudocode in Figure 11. Function OutR(jun)/InR(jun) is used to obtain the roads outgoing from/incoming to junction jun; JunRIn(r) is used to find the junction that road r is incoming to. If jun is matched, isMatched(jun) returns true, else false. In 
${TN}_{LLM\_rec}$, Pexplorer takes junS as input, and outputs the adjacent junction junA and the path between junS and junA, path LLM. And so it does for 
${TN}_{CNM\_rec}$.
5. BUILDING THE LINKING RELATIONS
The relationship of road correspondence is related to the element numbers of path LLM and path CNM. If both path LLM and path CNM contain only one element, it is 1:1 (1 to 1) relationship; if one or both of them contain more than one element, then they are 1:m (1 to m) or m:n (m to n) relationships. The 1:1 relationship is explicit; however, relationships of 1:m and m:n provoke ambiguities. For instance, for path LLM = {r1, r3} and path CNM = {link1, link3, link4}, it is hard to know which road section in LLM link3 corresponds to. In this section, a uniform and explicit method is proposed to describe the road correspondence.
5.1. Length proportion based projection
It is easy to know the corresponding road section if there is a locational referencing scheme, and one knows where the section starts and ends. The locational reference scheme in this paper is similar to the link and node locational reference proposed by Nyerges (Reference Nyerges1990).
Start and end positions are used to project each link of path CNM to path LLM. For the corresponding paths: path LLM = {r 1, r 2, · · · , r m}, m ≥ 1 and path CNM = {link 1, link 2, · · · , link n}, n ≥ 1, each link i ∈ path CNM can derive the locational referencing positions with respect to path LLM through Equation (6).
$$\begin{align}\label{eq6} Start\_S&=\frac{\sum_{j=1}^{i-1} {{\rm Length}(link_j )}}{\sum_{j=1}^n {{\rm Length}(link_j )} } \sum_{j=1}^m {{\rm Length}(r_j)},\nonumber\\ End\_S&=\frac{\sum_{j=1}^i {{\rm Length}(link_j )}}{\sum\nolimits_{j=1}^n {{\rm Length}(link_j )} }\sum_{j=1}^m {{\rm Length}(r_j)} \end{align}$$5.2. Physical data model for the linking relations
The linking relations' physical data model is given in Figure 12, where the junction relations table and road relations table store the junction and road correspondence, and the path table records the roads of path LLM.
Physical data model for the linking relations.
6. EXPERIMENTS AND RESULTS
6.1. Study areas and data
Two data sets were used to validate the approach. Test area A was a section of highway (mainly) in Beijing, northern China, with a total length of about 120 km. Test area B was a section of beltway (mainly) in Changsha, Hunan Province, southern China, with a total length of about 30 km. The LLM data of areas A and B were captured in 2015 and 2016. The CNM data of areas A and B were released in 2013 and 2016. It should be pointed out that the CNM and the LLM were made by two different map suppliers.
The LLM contained data of captured roads and the vicinities, whereas the CNM contained the whole city's data. For reducing unnecessary calculation, a 500 m buffer around the captured roads was created, and only the CNM data within the buffer was used. The experimental data sets are shown in Figure 13, where the red is TN LLM and the black is TN CNM. The microscopic views of where the blue arrows point are on the lower right. The statistics of the used TN LLM and TN CNM of each data set are summarised in Table 2. Quantitative differences of data sets A and B were caused by: (1) the lengths of the captured roads, (2) map specification change and (3) different cities.
Test data sets.
Statistics of data sets A and B.
6.2. Evaluation
The classical indicators of precision and recall defined in Equation (7) were used to assess the quality of the experimental results.
$$\begin{align} recall&=\frac{\vert {SC} \vert }{\vert {SA} \vert },\quad precision=\frac{\vert {SC} \vert }{\vert {SR} \vert },\nonumber\\ recall_{length} &=\frac{\sum\nolimits_{r\in SC} {length(r)} }{\sum\nolimits_{r\in SA} {length(r)} },\quad precision_{length} =\frac{\sum\nolimits_{r\in SC} {length(r)} }{\sum\nolimits_{r\in SR} {length(r)} }\label{eq7} \end{align}$$where SC denotes the set of correct pairs appearing in the results; SA denotes the set of all correct pairs among the whole data set; and SR is the set of results. Generally, the longer road is of greater importance than the shorter. Therefore, length-based recall and precision were employed as another two indicators.
6.3. Results
The approach in this study was coded in C ++ and run on a general personal computer. It was completed in an acceptable time (A = 114 s, B = 11 s). The results were checked manually and are summarised in Table 3.
Statistics of results.
In data set A, the reconstructed network 
${TN}_{LLM\_rec}$ consisted of 76 junctions and 172 roads, where 68 junctions and 69 roads were correctly matched. The length of correctly matched roads was nearly 113 km. In data set B, 11 junctions and 17 roads were correctly matched among the total 26 junctions and 40 roads. The total length of correctly matched roads was nearly 29 km. All the unmatched junctions were confirmed by the operator. In data set A, the eight unmatched junctions of LLM were built after 2013, thus they were not present in the CNM. They could not and should not be matched. Compared with the approach proposed by Mustière and Devogele (Reference Mustière and Devogele2008), our approach did not fail in this situation; the homologous parts of the roads had been matched. In data set B, where the LLM's specification had changed slightly against that of data set A, 15 pseudo junctions near the actual junctions were constructed to make 
${TN}_{LLM\_rec}$ connective. Matching pseudo junctions was also not necessary.
Most of the roads connecting with the unmatched junctions were matched successfully because Pexplorer could pass through the roads and mark them as elements of the path, which explains the high length-based recall undergoing low recall of junction matching in data set B, see Figure 14. In Table 3, the average lengths of unmatched roads of data set A and B are 74 m and 80 m, respectively; however, the average lengths of matched roads are 1,637 m and 1,703 m. This indicates most of the important roads were matched. It was found that most of the unmatched roads were located at the highway interchanges, where very few of them were captured because of the limited range of on-board sensors. These roads were represented as dead ends in TN LLM.
Recall and precision of the results.
As Figure 14 shows, regarding road matching, although the recall is below 50%, the length-based recall is nearly 94%, with precision of 100%. That means most of the roads in LLM have been matched correctly.
Compared with the methods that built linking relations semi-automatically (Volz and Walter, Reference Volz and Walter2004), in this paper, the linking relations were built automatically. Tables 4–6 give a short extract (incomplete) of the linking relations between LLM and CNM for data set A. Compared with the approaches that can only deal with 1:1 correspondence (Devogele, Reference Devogele2002) or 1:1 and 1:2 correspondence (Volz, Reference Volz2006), our approach is able to build the relationships of 1:1 (e.g., 
$\{ {r}\_{ID}\, {\colon } 101005\} \, {\colon }\{ {link{\_}ID}\, {\colon }318849\} $), 1:m (e.g., 
$\{ {r}\_{ID}\, {\colon }101003\} \, {\colon } \{ {link{\_}ID}\, {\colon }339012, \; 339009\} $), and m:n (e.g., 
$\{ {r{\_}ID}\, {\colon }301003, \; 901003, \; {\ldots}\} \colon \{ {link{\_}ID}\, {\colon }319607, \; 337679, \; \ldots\} $). With Tables 5 and 6, each link (e.g., link_ID: 339012) of CNM is linked to the corresponding road section of LLM (the road section from 0 m to 66·25 m of 
${r{\_}}{ID}\, {\colon } 101003$). Conversely, with the length of road (e.g., 
${r{\_}ID}\, {\colon }301003$, length 500 m), it is easy to derive the corresponding link section in CNM (whole of 
${link{\_}ID}\, {\colon }319607$ and section of 
${link{\_}ID}\, {\colon }337679$ from 0 m to 180·81 m).
Examples of junction relations.
Examples of paths.
Examples of road relations.
7. CONCLUSION
In this paper, an approach has been proposed to build linking relations automatically between LLM and CNM. In order to facilitate network matching, similarly-structured networks are built for LLM and CNM, initially. The adaptive multi-filter algorithm and forward path exploring algorithm are proposed to detect corresponding junctions and roads, respectively. The algorithms are able to match the greatly-differing networks of LLM and CNM and achieve high recall and precision. This approach can also build 1:1, 1:m and m:n linking relationships between LLM and CNM. With the linking relations, for the link in CNM it is easy to find the corresponding road section in LLM, and vice versa. The linking relations built in this paper can facilitate autonomous driving systems, especially the hierarchical planning system, and pave the way for interoperation and data sharing between LLM and CNM.
There are still some issues to be improved. As most map suppliers mainly focus on highway LLMs currently, this paper aims to build linking relations automatically for LLMs and CNMs of highway, primarily; in future, the approach should be enhanced to address urban road networks. The topology reconstruction targets eliminating topological inconsistencies to help with network matching; however, it may fail in topologically complex areas (like the tollgate in Figure 4(b)), complex intersections (like roundabouts), and areas with incomplete/wrong connections. The topology reconstruction logic needs to be enhanced and the non-topological matching methods, like geometric and semantic methods, should be explored. Finally, the spatial features were treated in a two-dimensional plane in this paper; in future, the altitude of the object should also be considered.
ACKNOWLEDGEMENTS
This work was supported by the National Key Research and Development Program: New Energy Vehicles Special Project ‘Research on Key Technologies and Legally Social Issues for Autonomous Driving Electric Vehicle Applications’ (2018YFB0105202).}
APPENDIX A. ABBREVIATIONS
The definitions of the abbreviations used in this paper are listed below.
