一种适用于车道级导航定位的交叉路口路网模型[发明专利]

(12)发明专利申请

(10)申请公布号 CN 106886604 A(43)申请公布日 2017.06.23

(21)申请号 201710123423.6(22)申请日 2017.03.03

(71)申请人 东南大学

地址 210096 江苏省南京市玄武区四牌楼2

号(72)发明人 李旭　蒋荣　夏亮　蔡志祥　(74)专利代理机构 南京苏高专利商标事务所

(普通合伙) 32204

代理人 柏尚春(51)Int.Cl.

G06F 17/30(2006.01)

权利要求书2页 说明书7页 附图1页

(54)发明名称

一种适用于车道级导航定位的交叉路口路网模型(57)摘要

本发明提出了一种适用于车道级导航定位的交叉路口路网模型。该模型以现有地图的路网模型和数据结构为基础，针对车道级导航定位的应用需求设计了交叉路口的路网模型。其主要由基础属性集、虚拟车道线集两部分组成，并使用一种具有保形功能的分段三次埃尔米特插值算法来插值虚拟车道线。本发明所提出的交叉路口模型，具有结构简明完整、精度高、信息量全和适用性广等优点，能够很大程度上提高车道级数字地图的精度，改善车辆导航在交叉路口的连续性和可靠性。CN 106886604 ACN 106886604 A

权　利　要　求　书

1/2页

1.一种适用于车道级导航定位的交叉路口路网模型，其特征在于：本交叉路口模型以现有地图的路网模型和数据结构为基础，针对车道级导航定位的应用需求来设计，由基础属性集、虚拟车道线集两部分组成，并使用一种具有保形功能的分段三次埃尔米特插值算法来插值虚拟车道线；具有数据结构简明完整、精度高、信息量全和适用性广的优点。

2.根据权利要求1所述的适用于车道级导航定位的交叉路口路网模型，其特征在于该模型具体如下：

该模型M由两部分组成：基础属性集Q，虚拟车道线集V，即：M＝(Q,V)   (1)1)基础属性集QQ＝(Nc,p,b,bmax,U)   (2)

式(2)中N表示编号，c指交叉口，即Nc是交叉口编号；p是中心点坐标，该交叉路口相连的实际车道编号的集合，

是中

心点的纬度、λ是中心点的经度；b是中心建筑半径；bmax是交叉路口的最大范围半径；U是与

r表示实际的，即Nr表示相

连的实际车道的编号，d表示相连车道的总数；2)虚拟车道线集VV＝(L1,L2,L3,…,Lm)   (3)

式(3)中m表示该交叉路口的虚拟车道线总数，L指虚拟车道线，L可以表示为：L＝(Nv,Nr_out,Nr_in,G，A)   (4)式(4)中v表示虚拟的，即Nv是虚拟车道线编号；out和in表示驶出和驶入，即Nr_out和Nr_in分别指与虚拟车道线L相连的驶出车道和驶入车道的编号；G＝{(x0,y0),(x1,y1),…,(xn,yn)}是描述虚拟车道线几何特性的控制点集，n等于控制点的总数减一，x和y分别是控制点的纬度和经度；A是插值后所得曲线参数集合。

3.根据权利要求2所述的适用于车道级导航定位的交叉路口路网模型，其特征在于所述虚拟车道线L获取方法如下：

①选取控制点

考虑到交叉路口的两种交通情况，直行和拐弯所对应的行驶轨迹不同，该模型对这两种情况区分对待，式(4)中的控制点集G在拐弯和直行时的选取如下所示：

式(5)中{E′,E,S,S′}和{E′,E,T,S,S′}均是按行车轨迹有序排列，其中E是驶出车道的结束点，S是驶入车道的开始点；E′和S′分别为在驶出车道和驶入车道上沿着车道隔5m所取得的控制点；T是针对直行情况所选的特殊控制点，在存在中心建筑，即b≠0的特殊情形下，T是点E和S的连接线H向右平移与圆O相切所得到切点，其中圆O是以交叉路口中心p为圆心，b+2为半径所得的圆；在不存在中心建筑，即b＝0的一般情形下，则T为点E和点S连线的中点；如此便能够保持控制点所描述的几何特征与实际行车轨迹相符；

②插值曲线

对于上述的有序控制点集G＝{(x0,y0),(x1,y1),…,(xn,yn)}，节点x1,x2,…,xn-1将区间分为n个子区间，根据分段三次埃尔米特插值算法可得第k个区间段[xk-1,xk]的曲线函数如

2

CN 106886604 A

权　利　要　求　书

2/2页

下：

其中k＝1,2,…,n；ak,1、ak,2和ak,3表示曲线的参数；dk-1、dk为插值函数在区间[xk-1,xk]端点处的一阶导数，用相邻两个区段的一阶差商进行加权的方式来近似计算：

式中δδω1和ω2是加权权重，k和k+1分别指区间[xk-1,xk]和区间[xk,xk+1]的一阶差商，即：

对于虚拟车道线首尾端点处的两个控制点，设：

通过式(6)-(11)可得虚拟车道线的参数集合A＝{a1,1,a1,2,a1,3,…,ak,1,ak,2,ak,3,…,an,1,an,2,an,3}；其中{ak,1,ak,2,ak,3}表示该虚拟车道线在区间[xk-1,xk]之间曲线的参数；{an,1,an,2,an,3}表示该虚拟车道线在区间[xn-1,xn]之间曲线的参数。

3

CN 106886604 A

说　明　书

一种适用于车道级导航定位的交叉路口路网模型

1/7页

技术领域[0001]本发明涉及一种数字地图的路网模型，尤其是涉及一种适用于车道级导航定位的交叉路口路网模型，其目的在于为车道级数字地图的制作提供更加完善、更加精确的交叉路口路网模型，为车道级导航定位打下基础，属于车辆导航领域。背景技术[0002]近年来，高级驾驶辅助系统(Advanced Driver Assistant Systems,ADAS)及车辆自主驾驶系统等智能交通系统(Intelligent Transport System,ITS)受到了极大的关注。其旨在借助通信技术，车辆定位等现代高科技来改善交通状况，合理利用现有道路，充分发挥其效率，提高通行能力，综合解决交通运输目前存在的诸多问题。智能交通系统(ITS)的不断发展，对车辆导航定位的精度要求越来越高，只有在车辆准确、实时定位的前提下，才能确保ITS功能实现，改善交通，保证车辆安全行驶。[0003]现代车辆导航定位系统中涉及的地图匹配、路径规划等都依赖于数字地图对应的空间数据库。然而由于自身精度的，传统的道路级数字地图已经不能满足智能交通系统(ITS)对定位精度的需求。因此，精度能够达到亚米级的车道级数字地图正在被广泛研究。[0004]车道级数字地图是指相对于普通的数字地图具有更高的精度和更丰富数据信息的新型数字地图，不同的定位系统可以根据环境和需要的不同在一般的数字地图的基础上增加系统需要的信息(如车道数量、车道线种类、交通标识符等)，以达到车道级定位的需要。车道级数字地图相对于普通道路级数字地图具有更加复杂的路网结构。要构建完善的车道级数字地图，交叉路口的路网模型设计是不可忽视的关键问题。[0005]然而，目前大多数的交叉路口模型都不够详细完善，都存在信息量少、数据结构冗余、精度低和适用性差等问题，甚至有些数字地图中直接忽略交叉路口的建模问题。这些不足制约了数字地图精度的提高，进而会导致车辆在交叉路口无法准确进行地图匹配，影响定位精度。[0006]为了解决上述缺陷，本发明提出了一种适用于车道级导航定位的交叉路口路网模型。该发明以现有地图的数据结构和路网模型为基础，针对车道级导航定位的应用需求设计了交叉路口的路网模型。该交叉路口模型主要由基础属性集、虚拟车道线集两部分组成。该模型中使用一种分段三次埃尔米特(Hermite)插值算法来插值虚拟车道线，此插值方法具有保形性，能保持数据形状和单调性，能很好的避免龙格(Runge)现象，使虚拟车道线更加逼近现实行车轨迹。本发明所提出的交叉路口模型，具有结构简明、精度高、信息量全、适用性广等优点，能够很大程度上提高车道级数字地图的精度，进而改善车辆导航在交叉路口的连续性和可靠性。

发明内容[0007]技术问题：本发明的目的是提出一种适用于车道级导航定位的交叉路口路网模

4

CN 106886604 A

说　明　书

2/7页

型，所提出的交叉路口模型，具有结构简明、精度高、信息量全、适用性广等优点，该模型能够很大程度上提高车道级数字地图的精度，对于改善车辆导航在交叉路口的连续性、可靠性和精度有很大作用。[0008]技术方案：本交叉路口模型以现有地图的路网模型和数据结构为基础，针对车道级导航定位的应用需求来设计，主要由基础属性集、虚拟车道线集两部分组成，并使用一种具有保形功能的分段三次Hermit插值算法来插值虚拟车道线；具有结构简明完整、精度高、信息量全和适用性广等优点；本发明所提出的具体模型如下：[0009]该模型M由两部分组成：基础属性集Q，虚拟车道线集V，即：[0010]M＝(Q,V)  (1)[0011]1)基础属性集Q[0012]Q＝(Nc,p,b,bmax,U)  (2)[0013]式(2)中N表示编号，c指交叉口，即Nc是交叉口编号；p是中心点坐标，

是中心点的纬度、λ是中心点的经度；b是中心建筑半径；bmax是交叉路口的最

大范围半径；U是与该交叉路口相连的实际车道编号的集合，

r表示

实际的，即Nr表示相连的实际车道的编号，d表示相连车道的总数；[0014]2)虚拟车道线集V[0015]V＝(L1,L2,L3,…,Lm)  (3)[0016]式(3)中m表示该交叉路口的虚拟车道线总数，L指虚拟车道线，L可以表示为：[0017]L＝(Nv,Nr_out,Nr_in,G,A)  (4)[0018]式(4)中v表示虚拟的，即Nv是虚拟车道线编号；out和in表示驶出和驶入，即Nr_out和Nr_in分别指与虚拟车道线L相连的驶出车道和驶入车道的编号；G＝{(x0,y0),(x1,y1),…,(xn,yn)}是描述虚拟车道线几何特性的控制点集，n等于控制点的总数减一，x和y分别是控制点的纬度和经度；A是插值后所得曲线参数集合；[0019]3)虚拟车道线获取[0020]①选取控制点[0021]考虑到交叉路口的两种交通情况，直行和拐弯所对应的行驶轨迹不同，本发明所设计的模型对这两种情况区分对待，式(4)中的控制点集G在拐弯和直行时的选取如下所示：

[0022]

式(5)中{E′,E,S,S′}和{E′,E,T,S,S′}均是按行车轨迹有序排列，其中E是驶出车

道的结束点，S是驶入车道的开始点；E′和S′分别为在驶出车道和驶入车道上沿着车道隔5m所取得的控制点；T是针对直行情况所选的特殊控制点，在存在中心建筑，即b≠0的特殊情形下，T是点E和S的连接线H向右平移与圆O相切所得到切点，其中圆O是以交叉路口中心p为圆心，b+2为半径所得的圆；在不存在中心建筑，即b＝0的一般情形下，则T为点E和点S连线的中点；如此便能够保持控制点所描述的几何特征与实际行车轨迹相符；[0024]②插值曲线[0025]对于上述的有序控制点集G＝{(x0,y0),(x1,y1),…,(xn,yn)}，节点x1,x2,…,xn-1将

5

[0023]

CN 106886604 A

说　明　书

3/7页

区间分为n个子区间，根据分段三次埃尔米特插值算法可得第k个区间段[xk-1,xk]的曲线函数如下：

[0026]

其中k＝1,2,…,n；ak,1、ak,2和ak,3表示曲线的参数；dk-1、dk为插值函数在区间

[xk-1,xk]端点处的一阶导数，可以用相邻两个区段的一阶差商进行加权的方式来近似计算：

[0028][0029]

[0027]

式中δδω1和ω2是加权权k和k+1分别指区间[xk-1,xk]和区间[xk,xk+1]的一阶差商，

重，即：

[0030][0031][0032][0033][0034]

对于虚拟车道线首尾端点处的两个控制点，设：

通过式(6)-(11)可得虚拟车道线的参数集合A＝{a1,1,a1,2,a1,3,…,ak,1,ak,2,

ak,3,…,an,1,an,2,an,3}；其中{ak,1,ak,2,ak,3}表示该虚拟车道线在区间[xk-1,xk]之间曲线的参数；{an,1,an,2,an,3}表示该虚拟车道线在区间[xn-1,xn]之间曲线的参数；[0036]综上，便是本发明所提出的适用于车道级导航定位的交叉路口路网模型。[0037]有益效果：[0038]1、本发明所提模型中的控制点选取方法，考虑了特殊情形的交叉路口，提高了模型的适用性和精度。[0039]2、本发明将一种具有保形功能的分段三次埃尔米特插值算法运用到虚拟车道线建模中，很好的避免了高次插值产生的龙格震荡现象，能保证曲线连续光滑，同时具有保形功能，使插值曲线更加逼近实际行车轨迹，有效的提高了交叉路口路网模型精度。[0040]3、本发明所提出的交叉路口模型，具有结构简明、精度高、信息量全、适用性广等优点，该模型能够很大程度上提高车道级数字地图的精度，对于改善车辆导航在交叉路口的连续性、可靠性和精度有很大作用。附图说明[0041]图1为拐弯虚拟车道线插值示意图，[0042]图2为直行虚拟车道线插值示意图。

6

[0035]

CN 106886604 A

说　明　书

4/7页

具体实施方式[0043]近年来，高级驾驶辅助系统(Advanced Driver Assistant Systems,ADAS)及车辆自主驾驶系统等智能交通系统(Intelligent Transport System,ITS)受到了极大的关注。其旨在借助通信技术，车辆定位等现代高科技来改善交通状况，合理利用现有道路，充分发挥其效率，提高通行能力，综合解决交通运输目前存在的诸多问题。智能交通系统(ITS)的不断发展，对车辆导航定位的精度的要求越来越高，只有在车辆准确、实时定位的前提下，才能确保ITS功能实现，改善交通，保证车辆安全行驶。[0044]现代车辆导航定位系统中涉及的地图匹配、路径规划等都依赖于数字地图及其对应的空间数据库。然而由于自身精度的，传统的道路级数字地图已经不能满足智能交通系统(ITS)对定位精度的需求。因此，精度能够达到亚米级的车道级数字地图正在被广泛研究。[0045]车道级数字地图是指相对于普通的数字地图具有更高的精度和更丰富数据信息的新型数字地图，不同的定位系统可以根据环境和需要的不同在一般的数字地图的基础上增加系统需要的信息(如车道数量、车道线种类、交通标识符等)，以达到车道级定位的需要。车道级数字地图相对于普通道路级数字地图具有更加复杂的路网结构。要构建完善的车道级数字地图，交叉路口的路网模型设计是不可忽视的关键问题。[0046]然而，目前大多数的交叉路口模型都不够详细完善，都存在信息量少、数据结构冗余、精度低和适应性差等问题，甚至有些数字地图中直接忽略交叉路口的建模问题。这些不足制约了数字地图精度的提高，进而会导致车辆在交叉路口无法准确进行地图匹配，影响定位精度。[0047]为了解决上述缺陷，本发明提出了一种适用于车道级导航定位的交叉路口路网模型。该发明以现有地图的数据结构和路网模型为基础，针对车道级导航定位的应用需求设计了交叉路口的路网模型。该交叉路口模型主要由基础属性集、虚拟车道线集两部分组成。该模型中使用一种分段三次埃尔米特(Hermite)插值算法来插值虚拟车道线，该插值方法具有保形性，能保持数据形状和单调性，避免龙格(Runge)现象，使虚拟车道线更加逼近现实行车轨迹。本发明所提出的交叉路口模型，具有结构简明、精度高、信息量全和适用性广等优点。该模型能够很大程度上提高车道级数字地图的精度，有效的改善车辆导航在交叉路口的精度和可靠性。[0048]下面结合附图对本发明进行进一步说明：[0049]一个交叉路口模型不仅仅要考虑其几何特性，例如位置、范围、形状等；还要考虑该交叉路口的交通特性，例如与相连车道间的拓扑结构、车辆的行车轨迹等等。因此，本发明所提出的交叉路口路网模型如下：[0050]该模型M由两部分组成：基础属性集Q，虚拟车道线集V。即M可以表示为：[0051]M＝(Q,V)  (1)[0052]1、基础属性集Q[0053]基础属性集Q主要包含交叉口编号Nc、中心点坐标p、与交叉路口相连的实际车道的编号的集合U以及几何特性。因为考虑到国内许多交叉路口中间存在中心花坛等建筑的特殊情况，所以该模型将中心建筑半径b也引入作为一种几何特性，此外几何特性还应该包

7

CN 106886604 A

说　明　书

5/7页

括该交叉路口的最大范围半径bmax，所以：[0054]Q＝(Nc,p,b,bmax,U)  (2)

[0055]

其中和λ分别是中心点的纬度和经度；Nr表示

与该交叉路口相连的实际车道编号，d表示相连车道的总数。[0056]2、虚拟车道线集V[0057]所谓虚拟车道，是指用于连接交叉口任意两条可以通行的车道，表示车辆行驶轨迹的车道线。本发明中所提出的虚拟车道线虽然在真实路面不存在，但是在模型设计的时候，是以交叉路口的物理特性为基础的，充分考虑了路口的几何特性和交通特性，例如车道间的交通等。[0058]虚拟车道线集指交叉路口虚拟车道线的集合，作为交叉路口模型中的关键部分，其除了表示行车轨迹，同时也包含了交叉路口各个车道间的拓扑结构信息，V可以表示为：[0059]V＝(L1,L2,L3,…,Lm)  (3)[0060]其中m表示该交叉路口的虚拟车道总数；L表示虚拟车道线。[0061]与实际存在的车道线一样，虚拟车道线也有属于自己的编号Nv；每条虚拟车道线L的数据结构中都该包含与其相连接的驶出车道的编号Nr_out、驶入车道的编号Nr_in；虚拟车道线的几何特性是由一系列的控制点的集合G＝{(x0,y0),(x1,y1),…,(xn,yn)}来描述的，x和y分别是是控制点的纬度和经度，n等于控制点总数减一，通过这些控制点插值虚拟车道线来近似表示行车轨迹；插值后的曲线的参数集合为A；因此，L可以表示为：[0062]L＝(Nv,Nr_out,Nr_in,G,A)  (4)[0063]3、虚拟车道线的生成：[00](1)选取控制点[0065]虚拟车道线用于连接两个可连通的车道，其从驶出车道的结束点E驶出，从驶入车道的开始点S驶入，所以E和S首先选做两个控制点；同时考虑到现实中的交通情形，车辆都是沿着车道的方向驶出和驶入的，所以为了确保所选的控制点插值得到的曲线能够与现实情形相符，本发明在驶出车道和驶入车道上沿着车道隔5m分别取点E′和S′作为另两个控制点。[0066]此外，考虑到交叉路口的两种交通情况，直行和拐弯所对应的行驶轨迹不同，本发明所设计的模型对这两种情况要区分对待。[0067]如图1所示，对于拐弯的虚拟车道，通过实验可以知，只需上诉四个控制点便能插值出虚拟车道，图1中的黑色加粗曲线即表示拐弯时的虚拟车道线。然而，直行时的情况却有所不同。在前人的研究中，往往认为直行情况比较简单，用上诉四个控制点插值出曲线便可。然而这却忽略了现实交通环境中许多交叉路口存在中心花坛的特殊情形，特殊情形下如果只是选取上诉四个控制点，所得的虚拟道路会与现实情况偏差较大。由此，本发明所设计的模型中提出一种选点方法，可使直行时的虚拟车道线更加适用于大多数交叉路口。[0068]如图2所示，在交叉路口模型的属性层中我们已经引入了中心建筑半径b的几何特征。在存在中心建筑，即b≠0的特殊情形下，汽车直行时必须绕过中心建筑才能穿过交叉路口驶入车道，因此本发明根据这种情形下的行车轨迹特点提出了第五个控制点的选取方法，即：先以交叉路口中心p为圆心，b+2为半径做圆O，再连接点E和S得直线H，向右平移H至与圆O相切，得到切点T，并将此点作为第五个控制点。因为在中国车辆是靠右行驶，车辆穿

8

CN 106886604 A

说　明　书

6/7页

过交叉路口都是从中心建筑右侧通过，所以是向右平移直线H；又考虑到现实的行车间距和车宽，所以设圈O为半径的为b+2。在不存在中心建筑，即b＝0的一般情形下，则T为点E和点S连线的中点。图2中的黑色粗曲线即表示直行时的虚拟车道线。如此便能够保证控制点所描述的几何特征与实际行车轨迹相符。[0069]综上，可得出直行和拐弯虚拟车道线的控制点集合，即：

[0070]

式中{E′,E,S,S′}和{E′,E,T,S,S′}均是按行车轨迹有序排列。[0072](2)插值曲线[0073]目前常见的插值方法分为线性插值和非线性插值，线性插值简便易行，虽然不会出现区间内的插值函数图像超出以区间端点连线为对角线的矩形范围的“越界”现象，但是曲线不光滑，精度不高。非线性插值虽然曲线光滑，但是会出现龙格(Runge)震荡现象，造成“越界”。在车道级数字地图的模型设计中，比较常用的是三次样条差值，该方法所得的曲线整体光滑程度高，但是在实际运用中会发现，使用三次样条差值算法很难控制曲线形状与实际行车轨迹相符，尤其在控制点较少，点的间隔较大的时候，所绘曲线会出现明显的Runge震荡现象，导致曲线失真。因此，这并不适用于交叉路口情形。[0074]针对以上问题，本发明所提出的模型中运用了一种具有保形功能的分段三次埃尔米特(Hermite)插值法来插值虚拟车道线。该插值方法很好的避免了高次插值产生的Runge震荡现象，具有稳定性好，保证收敛等优点，而且具有保形功能，能够确保曲线的单调性与控制点体现的单调性一致，保证插值曲线更加逼近实际行车轨迹；同时与线性插值相比，能保证曲线连续光滑。该方法在保形性和平滑度之间取得了很好的平衡，适用于数字地图中对车道线的处理。[0075]对于有序控制点集G＝{(x0,y0),(x1,y1),…,(xn,yn)}。节点x1,x2,…,xn-1将区间分为n个子区间，其中第k个子区间记为[xk-1,xk]，区间所对应的函数值区间为[yk-1,yk]，k＝1,2,…n。根据分段三次Hermite插值算法，可得区间上的三次Hermite插值函数fk(x)如下：

[0071]

[0076]

式(6)中dk-1、dk为插值函数在子区间端点处的一阶导数；ak,1、ak,2和ak,3表示曲线的参数。[0078]为确保每个区间的单调性不变，该分段三次Hermite插值算法中对于所有中间节点的导数，可以用相邻两个区段的一阶差商进行加权的方式来近似计算：

[0077][0079][0080][0081]

9

CN 106886604 A

说　明　书

7/7页

[0082]

其中δδω1和ω2是加权权k和k+1分别指区间[xk-1,xk]和区间[xk,xk+1]的一阶差商；

重。与中间节点不同，虚拟车道线首尾端点处只能获得一侧的一阶差商数据，其导数取值存在较大的不确定性，在本发明所使用的插值算法中令其与已知的相邻区间的一阶差商相等，即：

[0084]

[0083]

可以证明该插值函数在区间[x0,xn]上满足C1连续，且在子区间内保持单调。通过以上方法可得虚拟车道线的参数集合A＝{a1,1,a1,2,a1,3,…,ak,1,ak,2,ak,3,…,an,1,an,2,an,3}，其中{ak,1,ak,2,ak,3}表示该虚拟车道线在区间[xk-1,xk]之间曲线的参数，即第k-1和第k控制点之间曲线的参数；{an,1,an,2,an,3}表示该虚拟车道线在区间[xn-1,xn]之间曲线的参数，即第n-1和第n控制点之间曲线的参数。[0086]综上，便是本发明所提出的适用于车道级导航定位的交叉路口路网模型。

[0085]

10

CN 106886604 A

说　明　书　附　图

1/1页

图1

图2

11