Modeling the special intersections for enhanced digital map

Ni Peizhou Li Xu Xia Liang Huang Liang

(1School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China)(2NavInfo Co., Ltd, Beijing 100083, China)(3China Satellite Navigation Communication Co., Ltd, Beijing 100094, China)

Abstract：A new lane-level road modeling method based on cardinal spline is proposed for the special intersections which are covered by vegetation or artificial landscape in their central regions. First, cardinal spline curves are used to fit the virtual lanes inside special intersections, and an initial road model is established using a series of control points and tension parameters. Then, the progressive optimization algorithm is proposed to determine the final road model based on the initial model. The algorithm determines reasonable control points and optimal tension parameters according to the degree of road curvature changes, so as to achieve a balance between the efficiency and reliability of the road model. Finally, the proposed intersection model is verified and evaluated through experiments. The results show that this method can effectively describe the lane-level topological relationship and geometric details of this kind of special intersection where the central area is covered by vegetation or artificial landscape, and can achieve a good balance between the efficiency and reliability of the road model.

Key words：enhanced digital map; lane-level; intersection model; cardinal spline

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)

whereQis the set of the basic attributes of the special intersection;Vis 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 intersectionQis defined as

Q=(Nc,O,b,bmax,U)

(2)

Fig.1 The schematic diagram of the lane-level road model for the special intersection

The set of the virtual lanes inside the intersectionVis defined as

V=(L1,L2,L3,…,Lm)

(3)

whereLmis the set of basic attributes of them-th virtual lane.

Additionally,Lcan be further expressed as

(4)

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 pointsPi-1,Pi,Pi+1,Pi+2, with the curve drawn only fromPitoPi+1. The tangent vector at each control pointPiis 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 thatPi-1,Pi,Pi+1,Pi+2are four given consecutive control points (each of them hasxandyvalues) andP(u) is a parametric cubic polynomial between control pointsPiandPi+1. Hence, the boundary condition for establishing a single cardinal spline segment using four pointsPi-1toPi+2is

(5)

whereP(0) andP(1) are the position vectors ofP(u) at the two endpoints of the spline segment betweenPiandPi+1, respectively.uis the parameter of the spline segment and ranges from 0 to 1 betweenPiandPi+1(see Fig.2).

Fig.2 The spline segment when u ranges from 0 to 1 between Pi and Pi+1

Fig.3 The two slope values of the spline segment at Pi and Pi+1

The parametertis a tension parameter which affects the tightness of the cardinal spline. Whent>0, the cardinal spline curve is called a tight curve. Whent<0, the cardinal spline curve is called a loose curve (see Fig.4). Whent=0, the cardinal spline curve is called a Catmull Rom spline curve.

(a)

The four equations in the solution (5) are converted into a matrix form as follows:

(6)

where the cardinal matrix is as follows:

(7)

wheres=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 thexandydirections on the two-dimensional plane, and obtain the following expression of the cubic polynomial of the spline segment between control pointsPiandPi+1in thexandydirections:

0≤u≤1

(9)

Then, after the expansion of Eq.(9), the cardinal spline segment between control pointsPiandPi+1is 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 thatP1andPnare the starting point and the ending point of a given series of control points, respectively. Then, the spline segment drawn fromP1toP2is specified byP1,P1,P2,P3and the spline segment drawn fromPn-1toPnis specified byPn-2,Pn-1,Pn,Pnsimilarly. Fig.5 shows a cardinal spline that hasn-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 parametertis 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,Gcan be further expressed as

(11)

whereEis the endpoint of the lane which enters the intersection;E′ is the control point of 10 m apart from pointEon the enter lane;Dis the starting point of the lane which exits the intersection;D′ is the control point of 10 m apart from pointDon 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,Gcan be specifically expressed as

G={E′,E,Trig,D,D′}

(12)

whereTrigis 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 pointOas a center point and a radius of (b+10) m. As shown in Fig.7(a),G={E′,E,Trig,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)

2.1.2 The situation of go-straight

For the go-straight situation,Gcan be specifically expressed as

(13)

(a)

2.1.3 The situation of left-turn

For the left-turn situation,Gcan be specifically expressed as

(14)

(a)

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

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)

(a)

(a)

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)

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

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.