高精度导航地图道路线形参数估计方法

王东波，赵 宁，黄 鹤，张会彬

高精度导航地图道路线形参数估计方法

王东波1，赵 宁1，黄 鹤2，张会彬3

（1. 星球地图出版社，北京 100088；2. 北京建筑大学 测绘与城市空间信息学院，北京 102616；3. 32017部队 拉萨 850000）

针对高精度导航中传统的道路车道线模型在道路曲率估计中很难实现，且相关曲线拟合计算量较大的问题，提出1种基于全球卫星导航系统（GNSS）数据计算道路曲率的“迭代圆拟合”曲率估计算法：在数据点附近增加一定数量的相邻点，并对选取的数据点进行拟合，直到达到最小拟合误差，从而得到道路边线的拟合曲线；然后以中心角大小为参数对拟合得到的曲线段进行识别分类；最后对识别得到的曲线进行曲率估算，且将得到的估算值与真实值对比进行精度验证。结果表明，该算法所提取的道路边线具有较高的准确性，且能保证边界点精度。

道路边线；曲线拟合；迭代圆拟合；曲线识别；精度验证

0 引言

未来的无人驾驶汽车能够在道路上安全行驶，需要依靠高精度的导航电子地图的参与，其中车道级别的高精度导航地图数据库尤其重要。车道级别的要素信息需要获取的前期数据包括道路形状[1]，车道的曲率、坡度、航向、高程以及侧倾等主要数据。道路要素数据中对无人驾驶汽车的路径规划和引导起到关键作用的当属道路曲率[2]，因为所有的道路施工方案不可能完全依照设计方案来执行，因地制宜的现象导致道路的真实曲率会发生很多偏差，这就给高精度导航地图数据的道路要素参数入库时带来困难。需要更高精度的无人驾驶汽车对车道级别的地图数据要求更高。无人驾驶汽车在行驶时需要获取前方道路的转弯趋势和方向，以提前调整变换车道和速度，就必须在地图数据库中录入精确的道路曲率，以保证车辆安全行驶[3-5]。因此，目前应用广泛的导航电子地图在定位检测精度和地图要素信息细致程度方面均不能满足未来无人驾驶汽车发展的需求。

针对传统的道路车道线模型在曲率估计中很难实现，且对车道线模型直接进行相关曲线拟合带来的计算量又很大的问题，本文提出1种基于全球卫星导航系统（global navigation satellite system, GNSS）数据估算道路曲率的“迭代圆拟合”算法。该算法主要是利用直线拟合的结果来定性估计车道线曲率的正负，以此可确定前方道路的弯曲方向，即道路的拐弯趋向。利用该方法对道路曲率进行估计时，首先需要采集道路边线的GNSS数据（沿着车道边线等距离采集）；然后根据视场的远近将实验区域的道路图像划分成为近视区和远视区2个区域；最后利用直线模型拟合上述2个区域的车道线，以分别获得2个场区的车道线中点。将获得的2个中点进行连线以计算其斜率，此斜率可近似描述实验道路的曲率，最终实现对道路曲率的相对定量估计。

1 迭代圆拟合算法

本文中所选的曲线段[6]是具有单一半径的最小单位，曲线段的半径为（曲率为-1，而切线段的半径为无穷大（曲率为零））。水平曲线由曲线段和曲线点（PC）及切线点（PT）描绘的切线段组成，如图1（a）所示。对于更复杂的水平曲线，则存在相邻的曲线段或由内切线段和分开的曲线段组成，例如反曲线，如图1（b）所示。本研究的目的是准确识别曲线和切线段，将相应线段可靠地聚类成不同的水平曲线类型，并沿着确定的曲线测量相应的半径。

图1 由PC和PT绘制的水平曲线图解

本文提出1种迭代的圆形拟合算法[7-8]来获得初始的圆形拟合结果。该算法不是选择固定数量的相邻点进行拟合，而是尝试增加一定数量的相邻点，直到达到最小拟合误差；而产生最小拟合误差的数据将与这组GNSS点（即L）相关联。拟合误差是通过实际GNSS点与近似圆相比的适应度来度量的。如图2所示，对误差曲线进行单独监测和记录，直到在所有尝试的迭代中达到全局最小值。如果当前的1组GNSS点（即L）已经选择了相邻点的数量，则下1个圆形拟合将跳过当前点组重新开始。这样，通过迭代为每1组GNSS点（即曲线段）选择优化的GNSS点个数。图2中Ite为Iteration（迭代次数）的缩写，Error表示迭代的错误率。

图2 迭代圆拟合算法原理

圆形拟合方法定义了用于圆形拟合的采样点与近似圆之间的最小平方误差的最小化问题[9]。具体算法如下：

(2)

式中、、分别是误差函数的系数和常数项。

处理式（4）得

是点集中的点的个数，其中令

图3为从迭代圆拟合导出的合成分段的图示。图3中使用的替代颜色是突出描述。单个半径测量与同1段内的所有GNSS点相关联。在随后的步骤中将确定划定的线段是否弯曲或相切。

图3 细分割的1个小路段

2 曲线识别

GNSS轨迹数据由某地图公司自动导航研究中心开发的传感车辆采集。图4为采集车辆，图5为所收集的GNSS轨迹数据的示例。在本文中，原始的GNSS轨迹数据以5 Hz的频率以60 km/h的行驶速度获取。由于数据通过移动平台收集，因此许多因素将影响原始GNSS轨迹数据的准确性，例如，精度衰减因子(dilution of precision, DOP）、暂时的卫星丢失和有限的停留时间等[10]。因此，原始的GNSS轨迹数据需要通过差分调整和三角测量进行后处理，使用连续运行参考站（continuously operating reference stations, CORS）采集基站数据，以减少这些不利因素对精度的影响。虽然惯性导航系统（inertial navigation system, INS）数据在所提出的方法中不是必需的，但它可以用来补偿在卫星不可见的位置处GNSS数据的丢失，例如在隧道里。

图4 数据采集车

图5 GNSS轨迹数据样本

曲线识别的目的是根据上1步得出的划分线段的空间分布和邻接关系，自动识别水平曲线和相应的曲线类型[11]。

式中：为以弧度表示的第n段的中心角；Rn为由第n段的迭代圆形拟合计算的半径；Sn为第n段的弧长；m为包含在第n段中的GNSS点（即间隔）的数量；vi为GNSS在第i个点获取的瞬时车速；f为GNSS采集频率。图6中RC、RT分别表示C段和T段曲线的曲率半径，SC和ST分别表示其弧长，ΔC和ΔT分别表示其中心角。

图7 实验数据采集路段

图8 校准数据集中心角的分布

曲线分类：经过验证的曲线和切线段根据其邻接模式被分类为不同的曲线类型[14]。图9为不同曲线类型的典型模式。无论曲线类型如何，始终存在进入和离开中心曲线段（即在图9中横轴上投影曲率值为0所对应的曲线部分）的前后切线段。因此，中心曲线段（即图9中横轴投影曲率值不为0部分）的图案确定曲线类型：①非曲线（直线），供连续的切线段；②简单的曲线，呈现单个曲线段；③复合曲线，提供2个曲线方向相同的曲线段；④反向曲线，提供2个曲线方向相反的曲线段；⑤螺旋曲线，提供3个具有相同曲线方向和对称曲率测量的曲线段。

图9 不同曲线类型的段相邻模式的图示

曲线识别模拟实验的作用是验证本文提出的算法在各类型曲线识别效果和成功率，对于算法在道路真实数据的拟合精度方面还须进行实验验证。本文在实验路段利用GNSS实时动态载波相位差分(real time kinematic,RTK），以1 m间隔沿道路边线进行数据采集，将采集得到的坐标数据利用本文提出的算法进行拟合计算，然后将处理后的数据进行精度对比。为了更直观地通过数据和图像形式表达验证过程，现将本文所提出的方法以C#开发语言为工具将核心算法集成为1个通用的验证器。

在分段验证过程中选择2段道路数据进行逐点对比，如图10和图11所示，程序中设置的GNSS-RTK数据为“真值（图中放大圆圈中的左侧曲线）”，而采集车采集的数据设置为“产品（图中放大圆圈中的右侧曲线）”，程序自动读取之后计算出验证数据和图像数据。

图10 XOY平面投影

图11 XOY平面投影内插点

从图10中可以看出，道路边线的2种数据在该系统中的走势是完全一致的，而且契合度非常高，即使在比例尺很大的情况下也只能观察到细小的分离。图11中显示的是道路边线的“边线+节点”形式对比图，在显示比例为1∶10的情况下能够明显看到2种数据拟合的曲线点几乎在同一位置。图12中的坐标纵轴的单位为m，横轴为验证对比点号。从图12中可以明显看出，选取参加验证的数据点的估计点位误差平均为0.004 m（图表中加粗横线），该精度已经远高于高精度电子地图的需求精度，完全达到导航电子地图车道级精度要求。

图12 数据点坐标差对比

3 实验与结果分析

由于从现实世界中准备具有所有类型的曲线（尤其是复杂曲线）的综合数据集是比较困难的，因此通过插入具有已知几何公式的合成路段来顺序创建全面的合成数据集；然后合成数据被采样到离散的合成GNSS轨迹。为了与实际情况保持一致，根据现实的情况，对综合数据集曲线的尺度进行了标注，然后根据5 Hz的GNSS采集频率和60 km/h的默认驱动速度对GNSS轨迹进行离散化处理。为了测试所提方法的鲁棒性，在合成数据中模拟了几种从实际GNSS轨道观测到的GNSS干扰，包括随机GNSS误差和GNSS缺失点，这些干扰可以在GNSS信号中断时保持轨迹的连续性。模拟测试总共生成337条曲线，然后通过检测性能和分类性能评估模拟测试的准确性。

对于检测性能测试，使用1类误差（未检测到现有曲线）和2类误差（将直线部分错误识别为曲线）。当地面实况中的曲线完全错过或者检测到的曲线段重叠不到相应地面实况的75%时，将会报告1类错误；而当将地面实际的曲线段检测为直线段过程完成时，报告2类误差。最后的测试结果显示，只有38条曲线被检测为1类误差和27条曲线被检测为2类误差，达到了90.1%的正确检出率。还应该注意的是，在38个1类误差中，只有10条曲线完全错过了，而其余的28条曲线仍然被所提出的方法部分检测到。

表1显示了不同类型的混淆矩阵结果。从混合矩阵的对角单元可以看出，所提出的方法在区分4种曲线类型方面表现出总体良好的性能。总体而言，所提出的方法正确地分类了87.3%的检测曲线。即使对于具有挑战性的螺旋曲线，所提出的方法也能达到63.3%的正确分类率。然而，由于道路曲线与其对应的螺旋之间的错误描绘，36.7%的螺旋曲线被错误地归类为简单曲线或复合曲线。

表1 用于曲线分类测试的混淆矩阵

表2 曲率评估成果

4 结束语

本文提出的迭代圆拟合算法无论是在离散点均匀采集还是非均匀采集的情况下都具有良好的拟合效果，其精度并不低于目前在圆曲线拟合方法中普遍采用的最小二乘法，证明了该拟合方法的正确性与可行性。通过对该算法拟合估算的道路曲线曲率数据进行精度验证，发现道路边线曲率的准确性较高，且保证了边界点精度，算法整体完成较好，达到了在保证精度的同时减少数据量、提高运算效率的预期目标。

[1]JIA L, LUO J, LI S. Road curvature estimation based on linear lane model[J]. Journal of Jiangsu University, 2012, 33(4):373-378.

[2]BYUNG-HYUN L, JONG-HWA S, JUN-HYUCK I, et al. GNSS/DR error estimation for autonomous vehicle localization[J]. Sensors, 2015, 15(8): 20779-20798.

[3]GONZÁLEZ D, PÉREZ J, LATTARULO R, et al. Continuous curvature planning with obstacle avoidance capabilities in urban scenarios[C]//The Institute of Electrical and Electronic Engineers(IEEE). Proceedings of the 17th International IEEE Conference on Intelligent Transportation Systems (ITSC).Qingdao, China: IEEE, 2014:1430-1435.

[4]UPADHYAY S , RATNOO A . Continuous-curvature path planning with obstacle avoidance using four parameter logistic curves[J]. IEEE Robotics and Automation Letters, 2016, 1(2): 609-616.

[5] 张莉婷. 基于出租车GNSS轨迹的导航道路数据更新[D]. 昆明: 昆明理工大学, 2014.

[6] HONG C, KIM B W. Performance improvement of collision warning system on curved road based on intervehicle communication[J]. Mathematical Problems in Engineering, 2015, 2015(3): 1-7.

[7] 潘桂新, 邓德标. 圆曲线拟合方法及数据采集分析[J]. 城市勘测, 2014(5): 143-145.

[8] 陈明晶, 方源敏, 马波, 等. 一种迭代法的圆曲线拟合方法[J]. 测绘科学, 2016, 41(5): 133-136.

[9] 陈明晶, 方源敏, 陈杰. 最小二乘法和迭代法圆曲线拟合[J]. 测绘科学, 2016, 45(1): 194-197.

[10] 唐力明, 丁华祥, 朱紫阳. 应用车载DGNSS数据计算道路线形参数[J]. 测绘科学技术学报, 2008, 25(5): 321-323.

[11] HANS Z, SOULEYRETTE R, BOGENREIF C. Horizontal curve identification and evaluation[EB/OL].[2019-05-26].https://pdfs.semanticscholar.org/d000/7718259a60493e9c0991e001a5333e433fc1.pdf.

[12] AI Chengbo,TSAI Yichang.Automatic horizontal curve identification and measurement method using GPS data[EB/OL].[2019-05-26]. https://www.researchgate.net/profile/Chengbo_Ai/publication/266080116_Automatic_ Horizontal_Curve_Identification_and_Measurement_Method_Using_GPS_Data/links/579abe2e08ae425e491845a2/Automatic-Horizontal-Curve-Identification-and-Measurement-Method-Using-GPS-Data.pdf.

[13] LUO W, LIN L, WANG K C P. Automated pavement horizontal curve measurement methods based on inertial measurement unit and 3D profiling data[J]. Journal of Traffic & Transportation Engineering, 2016, 3(2): 137-145.

[14] AI Chengbo,TSAI Yichang.An automatic horizontal curve radii measurement method for roadway safety using GPS data[EB/OL].[2019-05-26].http://aichengbo.com/wp-content/uploads/2014/08/C-TRB-2014-LiDAR-Curve-Radii-Paper.pdf.

Road curvature estimation method for high precision navigation map

WANG Dongbo1, ZHAO Ning1, HUANG He2, ZHANG Huibin3

（1. Star Map Press, Beijing 100088, China; 2. School of Geomatics and Urban Spatial Information, Beijing University of Civil Engineering and Architecture, Beijing 102616, China; 3. Troops 32017, Lhasa 850000, China）

Aiming at the problems that it is difficult to realize the road curvature estimation for traditional lane line model, and the computation of related curve fitting is large in high-precise navigation, the paper proposed an iterative circle-fitting curvature estimation algorithm for calculating road curvature based on GNSS data: a certain number of adjacent points near the data points were added, and the selected data points were fitted until reaching the minimum fitting error, so that the curve of the road edge was gained; then the central angle was chosen as the parameter to identify the fitted curve segments; finally the curvature of the identified curves were estimated, and the true values were used to verify the accuracy of the estimation. Result showed that the road edges extracted by the proposed method would have high veracity and guarantee the accuracy of boundary points.

road edge; curve fitting; iterative circle fitting; curve recognition; accuracy verification

P228

A

2095-4999(2020)02-0049-06

王东波，赵宁，黄鹤，等. 高精度导航地图道路线形参数估计方法[J]. 导航定位学报,2020,8(2): 49-54.（WANG Dongbo, ZHAO Ning, HUANG He, et al. Road curvature estimation method for high precision navigation map[J]. Journal of Navigation and Positioning, 2020, 8(2): 49-54.）

10.16547/j.cnki.10-1096.20200209.

2019-07-17

王东波（1990—），男，安徽灵璧人，硕士，编辑，研究方向为高精度导航地图与智能驾驶。