In recent years, there has been a significant amount of progress in developing intelligent transportation system (ITS) applications and services such as automated vehicle navigation systems, advanced driver assistance systems and fleet management systems[15]. These applications and services require accurate and reliable position information of vehicles in different road traffic scenarios. An enhanced digital map is usually regarded as an additional measurement that can provide various information on the local environment of the vehicles for these applications and services[67]. Therefore, accurate and reliable enhanced digital maps are vital to the further development of intelligent transportation system applications and services[89]. In order to obtain high-performance solutions to handle the challenges of the complex road traffic scenario, a specific research interest aiming at improving the accuracy of both the vehicle positioning and enhanced digital maps to reach the lane-level is attracting more attention. Therefore,the vehicle positioning resolution has made significant progress with local differential station (DGPS) to reach the accuracy at the lane-level[6]. However, there is still considerable room for improvement in terms of the accuracy of most of the existing enhanced digital maps.
It is a consensus that road modeling is the crucial part of generating enhanced digital maps. The model of an enhanced digital map is used to abstract and simplify the real road network. As an important element of road network representation, the intersection plays a significant role in describing the connectivity and turn restrictions of all the lanes. However, most of conventional research concentrated much more on the information about the representation of road geometry with curve elements, which do not greatly concern the intersections. In the general road models that are adopted by commercial digital maps, the intersection is always omitted or simplified. For example, the Kiwi model defined the intersection as a logical component to help describe the connectivity and turn restrictions of an intersection in the real word, whereas the geometrical description of its internal part was ignored[1011]. The defects of this road model may cause poor performance of ITS applications and services at intersections. In order to overcome this limitation and enrich the road model for the intersection, some researchers developed the track road to approximate the real vehicle turning trajectory and describe the geometric details of an intersection[1015]. However, these road models only provide alternative methods for the topological and geometrical structure of general intersections at the lane-level and they cannot be applied to the special intersection which is covered by vegetation or artificial landscape in their central regions.
Furthermore, similar conceptions are applied in these recently developed lane-level intersection models, where the virtual lanes are generated using various types of spline curves. It is better to select an appropriate spline curve to represent the geometrical structure of the virtual lanes in order to maintain a good balance between the accuracy and data storage of the intersection model. Currently, the B-spline curve and the Hermite spline curve were widely selected to build road models in previous literature[1,1620]. A B-spline-based road model has the advantage that the change of local control points does not affect the entire shape of lanes, which makes local modification possible. However, it is difficult to extract the geometrical information (the curvature and the tangent angle) from the function of the B-spline curve. Therefore, the availability of the B-spline model is poor. Moreover, the Hermite spline-based road model also has some disadvantages,for example, the interpolation polynomial can only be used when the function value and derivative value of the interpolation polynomial at all interpolation points are known, which results in large amounts of data to be stored and processed. Therefore, it is difficult for the Hermite spline model to balance the accuracy and data storage of the road model well.
In this paper, we propose a lane-level road model for the special intersections which are covered by vegetation or artificial landscape in their central regions. The proposed intersection model can be divided into two levels: the topological structure and the geometrical structure. The topological structure helps describe the connectivity, turn restrictions and other attributes of the special intersection in the real world. The geometrical structure helps describe the virtual lanes of the internal part of the special intersection using cardinal spline, which can better approximate the real vehicle trajectory at the intersection. The cardinal spline is specified by a series of control points and tension parameters. An optimization algorithm is proposed to determine reasonable control points and optimal tension parameters under different traffic situations at the special intersection. The selection of reasonable control points can improve the data storage efficiency and the optimal tension parameters can satisfy a desired accuracy. Accordingly, the lane-level intersection model proposed in this paper realizes a near-optimal balance between the accuracy and data storage of the special intersections.
1 Lane-Level Road Model for the Special Intersections
1.1 Topological structure of the model
Under various considerations, the lane-level road model for the special intersection is defined as
M=(Q,V)
(1)
where Q is the set of the basic attributes of the special intersection; V is the set of the virtual lanes inside the intersection.
Fig.1 shows the schematic diagram of the lane-level road model for the special intersection.The set of the basic attributes of the special intersection Q is defined as
Q=(Nc,O,b,bmax,U)
(2)
where Nc is the serial number of the intersection; O is the coordinate of the center point of the intersection; O=(φ,λ), in which φ is the latitude of the center point and λ is the longitude of the center point; b is the radius of the vegetation or artificial landscape area in the middle of the intersection. Specially, it is a general intersection when vegetation or artificial landscape is not included (b=0). bmax is the maximum radius of this intersection. U is the set of actual lanes which are connected to the intersection, 
is the serial number of the d-th connected actual lane.
Fig.1 The schematic diagram of the lane-level road model for the special intersection
The set of the virtual lanes inside the intersection V is defined as
V=(L1,L2,L3,…,Lm)
(3)
where Lm is the set of basic attributes of the m-th virtual lane.
Additionally, L can be further expressed as
(4)
where Nv is the serial number of the virtual lane inside the intersection; 
are the serial number of the actual departure lane and actual enter lane which are connected to the virtual lane, respectively. G is the set of control points that describe the geometrical structure of the virtual lane, G={(x1,y1),(x2,y2),…,(xn,yn)}, in which xn,yn are the latitude and longitude of the n-th control point, respectively. A is the parameter set of the spline curve fitting the virtual lane.
1.2 Geometrical structure of the model
In this paper, we choose the cardinal spline to represent the geometrical structure of the model. The cardinal spline is specified by a series of control points and tension parameters. A gradual optimization algorithm will be introduced in detail in the next section which determines reasonable control points and optimal tension parameters under different traffic situations at the special intersection.
Currently,the spline curve can generally be divided into two categories: approximating spline and interpolating spline. The cardinal spline is a family of interpolating splines[2021]. To the best of the authors’ knowledge, the cardinal spline has been studied for a long time in the field of the CAD/CAM industry and the cardinal spline representation of the road geometry structure was rarely applied in the field of road modeling in the previous literature.
The cardinal spline is specified by a series of control points and tension parameters. A cardinal spline passes smoothly through each control point. It is a sequence of individual piecewise cubic curves joined to form a larger curve, and each cardinal spline segment is defined by four control points Pi-1, Pi, Pi+1, Pi+2, with the curve drawn only from Pi to Pi+1. The tangent vector at each control point Pi is calculated using the previous and next control point on the spline. A single cardinal spline segment can be completely determined by four consecutive control points, in which the middle two control points are the endpoints of the cardinal spline segment and the other two control points are used to calculate the tangents at the endpoints of the cardinal spline segment. Assume that Pi-1, Pi, Pi+1, Pi+2 are four given consecutive control points (each of them has x and y values) and P(u) is a parametric cubic polynomial between control points Pi and Pi+1. Hence, the boundary condition for establishing a single cardinal spline segment using four points Pi-1 to Pi+2 is
(5)
where P(0) and P(1) are the position vectors of P(u) at the two endpoints of the spline segment between Pi and Pi+1, respectively. u is the parameter of the spline segment and ranges from 0 to 1 between Pi and Pi+1 (see Fig.2).
Fig.2 The spline segment when u ranges from 0 to 1 between Pi and Pi+1
P′(0) and P′(1) are the tangent vectors of P(u) at the two endpoints of the spline segment between Pi and Pi+1, respectively.The two slope values of the spline segment at Pi and Pi+1 are proportional to chord 
respectively (see Fig.3).
Fig.3 The two slope values of the spline segment at Pi and Pi+1
The parameter t is a tension parameter which affects the tightness of the cardinal spline. When t>0, the cardinal spline curve is called a tight curve. When t<0, the cardinal spline curve is called a loose curve (see Fig.4). When t=0, the cardinal spline curve is called a Catmull Rom spline curve.
(a)
(b)
Fig.4 The tightness of the cardinal spline road model. (a) Loose curve; (b) Tight curve
The four equations in the solution (5) are converted into a matrix form as follows:
(6)
where the cardinal matrix is as follows:
(7)
where s=1-t/2.
In Eq.(6), the matrix equation is expanded into a polynomial form:
P(u)=Pi-1(-su3+2su2-su)+
Pi[(2-s)u3+(s-3)u2+1]+
Pi+1[(s-2)u3+(3-2s)u2+su]+
Pi+2(su3-su2)
(8)
Now, we can decompose Eq.(8) into the components of the x and y directions on the two-dimensional plane, and obtain the following expression of the cubic polynomial of the spline segment between control points Pi and Pi+1 in the x and y directions:
0≤u≤1
(9)
Then, after the expansion of Eq.(9), the cardinal spline segment between control points Pi and Pi+1 is given as
0≤u≤1
(10)
where
Thus, it can be seen that each cardinal spline segment is specified by the four given consecutive control points and a tension parameter which is determined according to the control requirements and accuracy requirements of the actual application scenarios. Generally, we suppose that P1 and Pn are the starting point and the ending point of a given series of control points, respectively. Then, the spline segment drawn from P1 to P2 is specified by P1, P1, P2, P3 and the spline segment drawn from Pn-1 to Pn is specified by Pn-2, Pn-1, Pn, Pn similarly. Fig.5 shows a cardinal spline that has n-1 individual spline segments with the same value for the tension parameter.
Fig.5 A cardinal spline that has n-1 individual spline segments with the same value for the tension parameter
The cardinal spline with different values for the tension parameter will produce different curves through a given series of control points. As shown in Fig.6, the cardinal spline with six different values for the tension parameter passes through the same series of control points. The tension parameter t is shown in Fig.6 for different values.
Fig.6 The cardinal spline with six different values for the tension parameter pass through the same series of control points
Note that the cardinal splines in Fig.6 share the same tangent line at the starting point which is the line drawn from the starting point to the next point along the curve. Likewise, the shared tangent at the ending point is the line drawn from the ending point to the previous point on the curve. The tangent line at other points is parallel to the line drawn from the previous point to the next point along the curve.
2 Optimization of the Intersection Model
An optimization algorithm of the intersection model is proposed to determine reasonable control points and optimal tension parameters under different traffic situations at the special intersection. We select reasonable control points for the cardinal spline according to different traffic situations, which can improve the data storage efficiency of the intersection model. Additionally, the value of the tension parameter for each individual cardinal spline segment will be adjusted to satisfy the desired accuracy until the error between the roadway data points and the cardinal spline reaches an acceptable range, which can better approximate the real vehicle trajectory at the special intersection. In this paper, a probe vehicle equipped with a single-enclosure GPS+INS positioning system measures the roadway data points of the special intersection and the acquired data will be processed manually to remove the outliers.
2.1 Selection of control points
In general circumstances, traffic situations at the special intersection can be divided into the following three categories: turn right, turn left and go straight. For these three different traffic situations, we separately select different points as the control points of the cardinal spline which can represent the geometrical structure of the intersection model.
Therefore, G can be further expressed as
(11)
where E is the endpoint of the lane which enters the intersection; E′ is the control point of 10 m apart from point E on the enter lane; D is the starting point of the lane which exits the intersection; D′ is the control point of 10 m apart from point D on the departure lane.
Then, we use the above series of points as the control points of the cardinal spline and gradually adjust the value of the tension parameter for each individual cardinal spline segment until the error between the given roadway data points and the cardinal spline meets an acceptable range. This can better approximate the real right-turn trajectory of the vehicle at the intersection.
Next, the selection process of the control points under different traffic situations at the intersection is described in detail.
2.1.1 The situation of right-turn
For the right-turn situation, G can be specifically expressed as
G={E′,E,T rig,D,D′}
(12)
where T rig is a special control point selected for the right-turn situation, and it is the point at which a straight line with a 45° angle to the centerline is intersected by a circle with point O as a center point and a radius of (b+10) m. As shown in Fig.7(a), G={E′,E,T rig,D,D′} is a set of control points arranged in order by the right-turn trajectory of the vehicle at the special intersection.The specific details are shown in Fig.7(b).
(a)
(b)
Fig.7 The schematic diagram of the right-turn situation. (a) Sketch map; (b) Specific details
2.1.2 The situation of go-straight
For the go-straight situation, G can be specifically expressed as
(13)
where 
are the special control points selected for the go-straight situation; 
is the point at which a straight line with a 45° angle to the centerline is intersected by a circle with point O as a center point and a radius of 
is the point at which a straight line with a 90° angle to the centerline is intersected by this circle; 
is the point at which a straight line with a 135° angle to the centerline is intersected by this circle.
As shown in Fig.8(a), 
is a set of control points arranged in order by the go-straight trajectory of the vehicle at the special intersection. The specific details are as shown in Fig.8(b).
(a)
(b)
Fig.8 The schematic diagram of the go-straight situation. (a) Sketch map; (b) Specific details
2.1.3 The situation of left-turn
For the left-turn situation, G can be specifically expressed as
(14)
where 
are the special control points selected for the left-turn situation; 
is the point at which a straight line with a 45° angle to the centerline is intersected by a circle with point O as a center point and a radius of 
is the point at which a straight line with a 135° angle to the centerline is intersected by this circle; 
is the point at which a straight line with a 225° angle to the centerline is intersected by this circle.As shown in Fig.9(a), 
is a set of control points arranged in order by the left-turn trajectory of the vehicle at the special intersection.The specific details are as shown in Fig.9(b).
(a)
(b)
Fig.9 The schematic diagram of the left-turn situation. (a) Sketch map; (b) Specific details
2.2 Adjustment of tension parameters
In the previous step, reasonable data points were selected as the control points of the cardinal spline curve. The selection of the optimal threshold value needs to take the efficiency and reliability of the road model into consideration. Therefore, the tension parameter is first set to be -1 for each cardinal spline segment determined by a series of control points obtained in the previous step. Then, the tension parameters of each cardinal spline are adjusted step by step independently by comparing the error between the cardinal spline and reference. Each adjustment increases by 0.1 until the cardinal spline has the smallest error to the reference.Generally speaking, the adjustment range of tension parameters is between -1 and 2.
3 Experimental Results
3.1 Experiment setup
To evaluate the performance of the proposed lane-level road model for the special intersection, experiments were carried out on a Chery TIGGO5 SUV vehicle. The raw roadway data points of the special intersection were collected using the probe vehicle equipped with a GPS+INS vehicle positioning system (NovAtel SPAN-CPT system). The NovAtel SPAN-CPT system is an accurate and reliable GPS+INS vehicle positioning system, which can provide accurate and reliable positioning information via post-processing even under adverse environments. The specifications of the NovAtel SPAN-CPT system are summarized in Tab.1. In this paper, the probe vehicle was driven at a stationary driving speed of 30 to 50 km/h along the centerline of the lane.
Tab.1 The specifications of the NovAtel SPAN-CPT system
MeasurementRMSPosition/m0.02Roll/(°)0.05Pitch/(°)0.05Azimuth/(°)0.10
The experiments were executed at the intersections of the Software Avenue Subway Station of Nanjing City and Nanjing Olympic Sports Center. These intersections are typical special intersections which are covered by vegetation in their central regions. Fig.10 shows the experimental sites. Figs.11 to 13 show the trajectories of the probe vehicle at the intersections under three traffic situations (right-turn, go-straight, left-turn).
(a)
(b)
Fig.10 The experimental sites. (a) The intersection of the Software Avenue Subway Station of Nanjing City (site 1); (b) The intersection of Nanjing Olympic Sports Center (site 2)
(a)
(b)
Fig.11 The result of the cardinal spline road modeling based on the gradual optimization algorithm under the right-turn situation. (a) Site 1; (b) Site 2
(a)
(b)
Fig.12 The result of the cardinal spline road modeling based on the gradual optimization algorithm under the go-straight situation. (a) Site 1; (b) Site 2
3.2 Road modeling
We use the gradual optimization algorithm mentioned above to determine reasonable control points and optimal tension parameters for the cardinal spline at this intersection under three traffic situations.Reasonable control points for the cardinal spline can improve the data storage efficiency of the model. Additionally, the value of the tension parameter for each individual cardinal spline segment will be gradually adjusted to satisfy a desired accuracy until the error between the roadway data points and the cardinal spline meets an acceptable range. Fig.11 shows the result of the cardinal spline road modeling based on the gradual optimization algorithm under the right-turn situation. Fig.12 shows the result of the cardinal spline road modeling based on the gradual optimization algorithm under the go-straight situation. Fig.13 shows the result of the cardinal spline road modeling based on the gradual optimization algorithm under the left-turn situation.
(a)
(b)
Fig.13 The result of the cardinal spline road modeling based on the gradual optimization algorithm under the left-turn situation. (a) Site 1; (b) Site 2
3.3 Performance evaluation of road modeling
As can be seen from Figs.11 to 13, there are five control points and four individual cardinal spline segments under the right-turn situation, seven control points and six individual cardinal spline segments under the go-straight situation, seven control points and six individual cardinal spline segments under the left-turn situation. The final optimal values of the tension parameter for each individual cardinal spline under different traffic situations are shown in Tab.2.
Meanwhile,the final right-turn virtual lane with cardinal spline fitting achieves the global accuracy of 1.05 m at Site 1 and 1.24 m at Site 2 by using five control points.The final go-straight virtual lane with cardinal spline fitting achieves the global accuracy of 1.24 m at Site 1 and 1.31 m at Site 2 by using seven control points. The final left-turn virtual lane with cardinal spline fitting achieves the global accuracy of 1.35 m at Site 1 and 1.36 m at Site 2 by using the seven control points.
Tab.2 The final optimal tension parameter values for each individual cardinal spline under different traffic situations
ExperimentalsiteCardinal splinesegmentRightturnGostraightLeftturnSite 111.11.21.120.60.80.930.50.50.441.30.60.550.91.261.11.3Site 211.21.21.120.60.90.930.50.50.341.40.70.451.11.261.21.3
From the experimental results above, we can see that the cardinal spline road modeling based on the gradual optimization algorithm uses a small number of control points to meet a desired lane-level accuracy under three traffic situations. It is clear that the topological structure of the model can effectively describe the connectivity, turn restrictions and other attributes of this kind of intersection in the real world, and the geometrical structure of the model can effectively describe the virtual lanes of the internal part of this kind of intersection. In general, this method can balance the efficiency and reliability requirements of the special intersection.
4 Conclusions
1) A lane-level road model is proposed for the special intersections which are covered by vegetation or artificial landscape in their central regions.
2) The main contribution of this paper is to adopt the cardinal spline road modeling based on the optimization algorithm to represent the geometrical structure of the special intersections, which can better approximate the real vehicle trajectory at the intersections. Also, a gradual optimization algorithm is presented to determine reasonable control points and optimal tension parameters for the cardinal spline under different traffic situations at the special intersections.
3) The experiments on two different sites are conducted to demonstrate that the lane-level special intersection model proposed in this paper occupies less data storage and achieves considerable accuracy.
[1] Jo K, Sunwoo M. Generation of a precise roadway map for autonomous cars[J].IEEE Transactions on Intelligent Transportation Systems, 2014, 15(3): 925937. DOI:10.1109/TITS.2013.2291395.
[2] Ress C, Etemad A, Kuck D, et al. Electronic horizon-providing digital map data for ADAS applications[C]//2nd International Workshop on Intelligent Vehicle Control Systems. Funchal-Madeira, Portugal, 2008: 4049.
[3] Kim S W, Liu W, Ang M H, et al. The impact of cooperative perception on decision making and planning of autonomous vehicles[J].IEEE Intelligent Transportation Systems Magazine, 2015, 7(3): 3950. DOI:10.1109/MITS.2015.2409883.
[4] Gwon G P, Hur W S, Kim S W, et al. Generation of a precise and efficient lane-level road map for intelligent vehicle systems[J].IEEE Transactions on Vehicular Technology, 2017, 66(6): 45174533. DOI:10.1109/tvt.2016.2535210.
[5] Durekovic S, Smith N. Architectures of map-supported ADAS[C]//2011 IEEE Intelligent Vehicles Symposium. Baden-Baden, Germany, 2011: 207211. DOI:10.1109/IVS.2011.5940402.
[6] Du J, Barth M J. Next-generation automated vehicle location systems: Positioning at the lane level[J].IEEE Transactions on Intelligent Transportation Systems, 2008, 9(1): 4857. DOI:10.1109/TITS.2007.908141.
[7] Ziegler J, Bender P, Schreiber M, et al. Making bertha drive: An autonomous journey on a historic route[J].IEEE Intelligent Transportation Systems Magazine, 2014, 6(2): 820. DOI:10.1109/MITS.2014.2306552.
[8] Betaille D, Toledo-Moreo R. Creating enhanced maps for lane-level vehicle navigation[J].IEEE Transactions on Intelligent Transportation Systems, 2010, 11(4): 786798. DOI:10.1109/tits.2010.2050689.
[9] Naumann M, Hellmund A M. Multi-drive road map generation on standardized high-velocity roads using low-cost sensor data[C]//19th International IEEE Conference on Intelligent Transportation Systems (ITSC 2016). Rio de Janeiro, Brazil, 2016: 113120. DOI:10.1109/ITSC.2016.7795540.
[10] Zhang T, Yang D G, Li T, et al. An improved virtual intersection model for vehicle navigation at intersections[J].Transportation Research Part C: Emerging Technologies, 2011, 19(3): 413423. DOI:10.1016/j.trc.2010.06.001.
[11] Zhang T, Arrigoni S, Garozzo M, et al. A lane-level road network model with global continuity[J].Transportation Research Part C: Emerging Technologies, 2016, 71(10): 3250. DOI:10.1016/j.trc.2016.07.003.
[12] Chen A N, Ramanandan A, Farrell J A. High-precision lane-level road map building for vehicle navigation[C]//IEEE/ION Position, Location and Navigation Symposium. Indian Wells, CA, USA, 2010: 10351042. DOI:10.1109/PLANS.2010.5507331.
[13] Gikas V, Stratakos J. A novel geodetic engineering method for accurate and automated road/railway centerline geometry extraction based on the bearing diagram and fractal behavior[J].IEEE Transactions on Intelligent Transportation Systems, 2012, 13(1): 115126. DOI:10.1109/TITS.2011.2163186.
[14] Brummer S, Janda F, Maier G, et al. Evaluation of a mapping strategy based on smooth arc splines for different road types[C]//16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013). Hague, The Netherlands, 2013: 160165. DOI:10.1109/ITSC.2013.6728227.
[15] Schindler A, Maier G, Janda F. Generation of high precision digital maps using circular arc splines[C]// 2012 IEEE Intelligent Vehicles Symposium. Madrid, Spain, 2012: 246251. DOI:10.1109/IVS.2012.6232124.
[16] Ben-Arieh D, Chang S, Rys M, et al. Geometric modeling of highways using global positioning system data and B-spline approximation[J].Journal of Transportation Engineering, 2004, 130(5): 632636. DOI:10.1061/(asce)0733-947x(2004)130:5(632).
[17] Schindler A, Maier G, Pangerl S. Exploiting arc splines for digital maps[C]// 14th International IEEE Conference on Intelligent Transportation Systems (ITSC 2011). Washington, DC, USA, 2011: 16. DOI:10.1109/ITSC.2011.6082800.
[18] Wedel A, Badino H, Rabe C, et al. B-spline modeling of road surfaces with an application to free-space estimation[J].IEEE Transactions on Intelligent Transportation Systems, 2009, 10(4): 572583. DOI:10.1109/TITS.2009.2027223.
[19] Loose H, Franke U. B-spline-based road model for 3d lane recognition[C]//13th International IEEE Conference on Intelligent Transportation Systems (ITSC 2010). Funchal, Madeira, Portugal, 2010: 9198. DOI:10.1109/ITSC.2010.5624968.
[20] Zhao K, Meuter M, Nunn C, et al. A novel multi-lane detection and tracking system[C]// 2012 IEEE Intelligent Vehicles Symposium. Madrid, Spain, 2012: 10841089.
[21] Bodduna K, Siddavatam R. A novel algorithm for detection and removal of random valued impulse noise using cardinal splines[C]//2012 Annual IEEE India Conference (INDICON). Kochi, India, 2012: 10031008. DOI:10.1109/INDCON.2012.6420763.