ADAS导航地图多源数据高程异常修正算法研究

黄 鹤，陈志锋，衣鹏军

(1.北京建筑大学测绘与城市空间信息学院，北京 102616；2.未来城市设计北京市高精尖创新中心，北京102616)

随着汽车导航技术的不断发展，自动驾驶技术成为研究热点,但就现阶段而言，自动驾驶处于试验研究阶段，技术上需要可靠性与稳定性的突破，政策上需要相关法律与标准的跟进，甚至基础设施也需要相应的投入。目前，ADAS(高级驾驶辅助系统)是汽车技术由机械化向智能化转变的重要条件。在最新的ADAS研究报告中，ADAS的功能方案和具体试验已经非常成熟。在《中国制造2025》中，也已经明确给出了ADAS相关内容标准和框架，说明目前国家在ADAS方面已经有了较为明确的方向、标准及术语定义。ADAS中最重要的是地图数据中高程信息的引入，ADAS导航地图作为ADAS重要的先验信息，除传统的平面坐标信息之外，同时为车辆提供道路的曲率、坡度等重要信息。高程作为ADAS数据中一个关键要素对ADAS决策和驾驶中的人机交互具有十分重要的辅助作用[1]。

目前ADAS高精度导航地图数据的采集基本依赖于移动道路测量系统，该系统集成了传感器集、GNSS、INS系统等，采集方式按照精度的不同主要分为3种，包括基于MMS(GPS/IMU+激光扫描仪，经验精度0.1～1.0 m)、基于MMS(GPS/IMU或第三方供应商，经验精度0.5～5.0 m)、基于SRTM3 DEM(栅格分辨率90 m)。其中实采数据采集的是具有一定距离间隔的点(形状点)的坐标和高程信息[2]。将这些点的信息扩展成彼此独立的线几何信息，一定数量的点构成的线几何就成为ADAS数据中LANE的基本单位LINK，LINK端点区别于形状点，定义为NODE。显然，符合实际的LINK之间的高程应该是连续的。但是由于数据采集的环境、采集设备的参数、人员、时间等一系列不可预知因素的存在，以及数据采集完成后内业人员对数据进行的后处理过程中不可避免的数据筛选和处理过程等，这些因素都造成ADAS数据中实际LINK间的节点(NODE点)在不同的LINK上具有不同的高程值。对整个ADAS数据而言，该问题的存在使整个ADAS数据中的道路线具有了高程突变现象。在传统导航地图主导的电子导航时代，由于地图数据中不存在高程信息，因此不存在该问题。但是在ADAS高精度导航地图领域，高程作为重要的决策和人机交互参考信息而存在，数据中的高程异常问题需进行后处理纠正。鉴于ADAS对地图信息有着极高的实际符合性要求，高程异常的纠正过程并非简单的LINK二次“搭接”，而是要在满足整体合理性的基础上做到高度的实际符合性，即调整后的数据应该符合实际道路信息。同时对原始数据改动应该限定在一定的阈值之内。

针对上述问题，基于水准网平差的基本思想，探索相应算法，修正ADAS高精度导航地图中的高程异常，以解决ADAS数据中的高程不连续问题。本文主要对如何一次统一ADAS高精度导航地图中的高程异常问题中的控制层处理问题进行论述。文中高程异常指LINK间同名NODE点的多值性问题。

由于高程信息涉及国家安全问题，因此本文中所涉及的高程数据均是算法加密后数据。

1 ADAS数据结构及高程异常问题

现实世界的道路是由线几何表示的，在ADAS数据中线几何是由各个独立的LINK连接而成。LINK表示现实道路的形状，每一条LINK都有一个唯一编号，并有1个起始NODE、1个终点NODE，以及数目不等的具有一定密度间隔(一般为5 m)的形状点。当几条LINK相交时，会共用同一个NODE。每一个NODE有一个唯一编号。LINK通过NODE点和形状点经度、纬度、绝对高程来表达三维特征，如图1所示。

图1 ADAS数据组织结构示意图

在地理信息产业领域，非等精度数据问题由来已久，目前行业内并没有数据质量评定的统一标准[3]。此外设备不同及测量单元和环境的影响还将会给每段LINK带来不同的系统误差。理论上，在一个LINK块内，数据中包含的系统误差是稳定的，精度也具有相同的性质。如图2所示，大量的实采数据已经证明上述结论。以上这些主要因素导致ADAS数据中LINK间高程不连续的问题，即同一区域高程存在差异且道路交叉点处的同一NODE高程存在多值性。由于该系统误差具有稳定性，且数据具有较好的相对精度[4]，因此LINK内的坡度变化与现实情况具有高度的符合性。

图2 ADAS数据中的LINK高程趋势变化

2 解决思路

由于需要处理的道路数据属于多源、非等精度观测数据，因此将数据分为5个等级，按照分级布设、逐级控制，先整体、后局部的原则，分级控制，先全国、后分省分区域，如图3所示。由于高速公路在观测条件、连续性及数据的完整性方面较其他等级道路具有的优势，以高速公路作为控制的最高级。考虑ADAS中道路的曲率、坡度等信息是重要的基础信息，因此在进行数据整体调整的过程中，优先考虑坡度信息，将坡度的变化严格控制在一定的阈值之内。ADAS数据中的非实采低精度数据对坡度无要求。与一般测绘意义上的最优估计不同，ADAS数据处理整个过程并非为了提高精度，而是主要保证整体符合性与整体合理性，同时尽量降低对原始数据的改动。

图3 ADAS数据处理逐级控制

根据逐级控制的思路，首级控制为次级道路提供了必要的控制参考，建立了ADAS数据高程控制框架。对于首级控制借鉴大型水准网平差方法，结合本问题的特点，采用整体最优估计思想处理高速数据。考虑ADAS数据的具体特点，为将ADAS高精度导航地图中的线几何抽象为水准网中的水准线路，在数据处理前建立了3个新的概念，即VISCOSITY(量化NODE点与LINK关联度参数)、EFFECTIVE_NODE、EDGE，如图4所示。数据预处理过程的首要工作是计算ADAS导航数据中的点—线拓扑关系，基于该拓扑关系计算全部NODE点的黏度参数，基于VISCOSITY参数信息提取NODE点中VISCOSITY参数≥3的NODE点，并定义为EFFECTIVE_NODE，EFFECTIVE_NODE之间的连接关系为EDGE。

图4 EDGE与EFFECTIVE_NODE的定义

通过对问题的抽象，借鉴水准网平差中的整体最优估计基本思想，综合本文的实际需求综合处理ADAS数据中的高程异常问题。将方案基本过程模块化，主要过程如图5所示。

图5 ADAS顶层控制处理流程

2.1 数据预处理

提取作为控制的高等级数据，首先计算NODE点与LINK的完整拓扑关系，基于拓扑关系计算NODE点VISCOSITY参数，作为筛选EFFECTIVE_NODE的依据，EFFECTIVE_NODE筛选完成后，建立EFFECTIVE_NODE之间的全部连接(EDGE)。记录每条连接及连接内部的LINK集合，按照EDGE建立的方向记录EDGE的起点和重点NODE编号，同时按照树形生长方向计算EDGE的高差，高差计算算法如图6所示，将每个EDGE的第一条LINK作为基准LINK，其后的LINK依次接合到上一LINK的公共NODE点上，同时计算LINK内NODE点的新高程值，依次进行，直至访问到EFFECTIVE_NODE时结束。完成全部EDGE信息的计算后就将原始的ADAS数据抽象为准水准网的数据结构。

图6 EDGE高差计算算法

考虑建立EFFECTIVE_NODE与EDGE的过程中，可能会出现附和路线连接，如图7所示，在记录EDGE时以EDGE路线的距离作为判断依据，自动记录较短EDGE。

图7 局部附和线路示意图

2.2 独立闭合环高效搜索

对于独立闭合环的搜索，采用基于生成树-余树的闭合环搜索算法[5]，该算法能够稳定地搜索出全部独立闭合环，但是计算量会随着搜到的最小独立闭合环数量的增多而急剧增加，对于网结构不是非常复杂，网内闭合环数目不是十分庞大的对象其计算量是可以接受的。对于ADAS数据，由于形成闭合环的数目十分庞大，因此搜索效率是必须考虑的问题。在生成树-余树搜索算法的基础上，对算法进行优化，尽量减小搜索时间。利用网形信息构建最优树模型，同时得到余枝信息，然后以余枝为基础条件，可稳定地搜索出所有最小独立闭合环[6]。

闭合环数目个数的确定规则如下：所有的闭合环中边数最少的环是三边形，对于由n个点、m条独立观测边构成的网(附和路线和支路线在前期数据处理过程中已经剔除)，其必要观测数为n-1，多余观测数为n-m+1，因此对于任意网内的独立闭合环的个数为n-m+1[7]。

基于生成树-余树的闭合环搜索算法的基本思路为：从网中某一结点开始，建立树型结构，余枝数为独立闭合环个数r。将每条余枝分别加到树上，即可生成一组闭合环，每个闭合环都至少包含一条不属于其他环的余枝(边)，因而这一组闭合环是相互独立的。但生成的闭合环因树型结构生成的方法和添加余枝的次序不同而不同，因而得到的闭合环不一定是最小闭合环。

为了保证每条余枝都能生成一个最小环，余枝加到树上的顺序及构成环的策略应该有所考虑。首先尝试把所有余枝加到树上，计算出每条余枝生成环的边数，选出其中边数最小的环为一个最小环，相应的余枝优先加到树上，树上添加余枝后生成的树称为当前树。然后，在其他余枝中分别找出每条余枝两个端点在当前树中的最短路径，计算构成环的边数，边数最少(距离最短)的环就是最小环，相应的余枝加到当前树中。经过有限次循环后即可找到一组r个独立的最小环。基于该算法的改进思路是将抽象形成的网(连通图)进行合理的碎化处理，由于在碎化过程中切割是沿着连通图连接关系进行的，因此在这个过程中避免了数据损失。

2.3 网调整参数的最优估计

ADAS高精度地图数据在经过抽象之后，形成了以EDGE连接EFFECTIVE_NODE的网络结构，此时数据的高程信息依然是离散的，相互关联的LINK之间不连续。此时的最优估计是直接针对EDGE高差的。通过对EDGE高差的整体微调，使整个网内的所有EFFECTIVE_NODE之间的相对高差完全合理，即给定一定数量的已知高程信息，通过不同的路径推算某个EFFECTIVE_NODE的高程不会出现冲突，即为整体合理性。此处的平差侧重点不再为了提高整个网的数据精度，而在于使ADAS一级路网首先满足整体合理性。这也是后续分配闭合差进行各级数据微调的前提和基础。

ADAS数据采集过程虽然在一定程度上排除了人为干扰，但是GNSS+INS的采集方式却不可避免地受到环境影响，如进出隧道附近的数据会明显产生一定程度的漂移。从采集到的数据所反映的实际来看，在极个别情况下这种误差会达到十米级。显然这样的误差将给纯粹依赖最小二乘的平差带来十分不利的影响，如何探测该误差或将该误差的影响降到最低是必须要考虑的问题。目前对于消除粗差的研究相对成熟[8-9]，对于粗差处理和最优估计理论已有很多成熟的研究[10-14]，已有消除或减弱误差的方法一般分为两种思路。一类是通过统计学原理对粗差进行探测定位并加以消除，这方面的研究以文献[15]的粗差探测法为代表。另一类是通过平衡数据来源的权重来最大限度地降低或减弱粗差对估值的影响，这种方法不对粗差进行定位和消除，因此估值方法选择尤为重要(如L1范数最小估计、M估计等)。李德仁院士于1984年提出的选权迭代法是该方向一种重要的方法[16]。

由本文讨论的问题出发，在获取已知数据的同时获得了道路的等级和道路形态信息，通过这些信息可以大致反映观测值的精度水平，也就是说，本问题在平差计算前一定程度上相当于获得了观测值的先验精度信息。因此，本问题更适合第二类抗粗差方法。

如何将道路形态信息通过一定的数学法则映射成为观测值的先验权问题需要进行多次试验，不断优化。

为控制调整后的整体网形与实际路网相符合，采用附有限制条件的约束平差，在有条件方程形成的方程组下，加入由一定量已知点所形成的附和路线约束方程作为约束整体解算，从而使解算后的网形尽量贴合实际情况。

关于定权问题，必须指出的是，ADAS的数据采集方式依赖移动道路测量系统，移动道路测量系统获取的ADAS地图数据的最小数据单位为点的位置信息，以GNSS方式获取的数据在单个点的位置上没有误差累计，因此，EDGE的长度与EDGE的高差没有直接联系。在当前不考虑GNSS采集环境差异的情况下，LINK与EDGE的高差信息均是独立的，因此建立在EDGE层级上的最优估计确立采用单位权处理。

2.4 数据重建

数据重建过程分为4个部分，分别为闭合差分配、LINK重建、EDGE重建和网重建，各部分之间依次进行。参数估计后获得的改正数是对EDGE的改正数。已经论证，ADAS的数据采集方式所获取数据的最小单位为形状点。由于ADAS数据中的LINK长度不一，为避免在分配改正数时，某一LINK上形状点的高程改动幅度过大，影响实采的坡度信息，在闭合差分配时采用按长度定权的分配方式。根据式(1)计算同一LINK上各点的改正数，将改正数合理分配到每一个形状点上，如图8所示，从而保证坡度信息的准确性，同时将数据调整的幅度控制在一定的阈值之内。

图8 LINK重建

将各个EDGE上的改正数按照以上规则分配后得到每段LINK的改正参数，对每一段LINK进行数据微调，微调方向基于数据预处理中的EDGE生长方向。各形状点的微调计算公式如下

vvi=(n-1)·vi

(1)

在完成对LINK数据的重建后，需要以EDGE为单位对EDGE进行重建，目的是将EDGE连接成为连续的线几何曲线，从而为后续对全部的EDGE赋予绝对高程信息作数据准备。

EDGE重建的过程与求EDGE高差的过程类似，对于所有的EDGE逐条处理，按照EDGE生长方向依次将LINK接合在相邻LINK的同名NODE点上，在此过程中对LINK内的形状点的高程作二次校正。

EDGE重建完成后，结合给定的起算数据进行网重建，网重建的已知起算数据为约束平差中具有实际高程值的已知NODE点。此时选取一个起算点，向四周扩展，即可将具有准确相对高程关系的EDGE数据赋值以绝对高程。此时已经完成了对控制层的高程异常处理。

3 试验及结果分析

数据处理结果中，本文抽取北京地区的数据为例进行试验结果的介绍。北京地区FC=1(Function Class)总计396 606条数据记录，经过数据预处理获取有效EDGE记录412条，筛选得到的关键NODE节点282个，相关LINK总计6874条。基于抽象形成的EDGE总计搜索计算得到闭合环131个，闭合环边数最大为13。在整体最优化估计处理结果中，EDGE改正数最大为2.156 m，最小为0.000 724 813 9 m，EDGE改正数均方差为0.147 5 m，平均单个形状点的改正幅度为毫米级。

高差验证方面，本文随机抽取了京津冀地区的S10线河北易县至涞源县段，该段线路在数据预处理后对应的EDGE编号及直线总计82.533 km，线路总计101.135 km。编号为1490和925的EDGE分别为该线路的上行线和下行线。EDGE信息和程序计算得到的线路高差见表1。

表1 相关EGDE信息表 m

在谷歌地球中标记该线路的端点坐标，如图9所示。记录线路和对应大地坐标，计算两端点的相对大地高差为813.278 m，证明本文方案中的高差计算算法严谨可靠。

图9 线路示意图

由于大区域范围数据量庞大，难以直观展示，因此截取数据中天津北部的处理结果进行展示。经过验证，该算法可以快速进行数据处理，实现对数据中高程异常的修正，如图10—图12所示。

图10 试验数据区块(天津北部)

图11 处理前数据

图12 处理后数据

对单个闭合环进行随机取样抽检可以优先检测整体合理性与实际符合性。通过随机提取闭合环号，提取了部分闭合环进行单环展示，闭合环号编号为6的闭合环数据处理前的LINK在空间内的展示如图13所示，处理后效果如图14所示。

图13 处理前单个闭合环空间展示

图14 处理后单个闭合环空间展示

该方法对原始坡度信息的改动是微小的。图15所示为随机完整闭合环线路，通过处理前后的剖面图可以明显地反映坡度的变化情况，这一点在坡面图上也可以得到很好的反映。

图15 处理前后符合度与改动幅度展示

4 结 语

在ADAS高精度导航地图数据高程异常优化改正运算结果中随机选取其中任意闭合环进行质量检查，结果符合预期，证明该算法可以实现对ADAS高精度导航地图中的高程异常问题的处理，具有整体符合性好、数据改动幅度小、整体合理的优点。通过逐级控制完成控制层的数据处理后，基于各级控制形成的控制网络，按照具体数据等级的处理要求将非控制数据按照一定的算法规则接合在控制网内，从而实现对ADAS高精度导航地图的全面高程异常修正。

在下一步的工作中，笔者将对ADAS数据中可能存在的其他问题进行进一步分析，如基于DEM数据附加实采数据约束的拟合方法、道路双线的约束方法、独立异常网络的探测、大型复杂三维网络的连通图表达、大型连通图的闭合环高速搜索算法等。