CN105387863B - 一种针对现有导航地图中未知的道路进行识别和导航的方法 - Google Patents

Abstract

本发明公开了一种针对现有导航地图中未知道路进行识别和导航的方法，该方法包括未知道路采集提取和未知道路导航步骤；未知道路采集提取步骤中，通过轨迹采集得到初始的行驶轨迹数据，对轨迹数据进行处理和分析提取出未知道路，将未知道路集成到已有道路中，供导航使用。未知道路导航步骤中，获取未知道路后，通过计算未知道路的导航信息包括拐弯方向和拐弯距离，结合实时定位，并将实时位置匹配到已有的未知道路上，实现实时导航。本发明方法可以通过历史轨迹提取到实际存在导航地图上未标识的道路，并且实现未知道路的导航方便使用，一定程度避免了因为导航地图道路更新缓慢导致绕路或者到不了目的地的现象，尤其利于物流配送领域。

Description

一种针对现有导航地图中未知的道路进行识别和导航的方法

技术领域

本发明涉及一种对未知道路进行识别和导航的方法，尤其在物流配送过程中的对导航地图中没有标识的未知道路进行采集、识别分析和导航的方法。

背景技术

GPS技术已经广泛应用于各领域，基于GPS技术开发的各类导航仪、导航地图、手机APP等应用也被广泛使用于工作和生活，但是这些地图应用只能在已识别的道路基础之上进行导航。在现实情况下很多道路实际存在，导航地图中却尚未采集到，导致无法直接导航到目的地或者绕远路，这种现象在农村地区特别普遍。

发明内容

本发明的目的在于针对现有技术的局限和不足，提供一种针对现有导航地图中未知道路进行识别和导航的方法。

本发明的目的是通过以下技术方案实现的：基于现有的导航地图和GPS、GIS技术，通过对车辆行驶的历史轨迹进行分析和计算，识别出未知的道路信息，再将未知道路集成到已知道路中，结合定位技术实现对未知道路的导航，从而能够将导航延伸到原先无法达到的地方。

具体包括以下步骤：

(1)未知道路采集提取：通过轨迹采集得到初始的行驶轨迹数据，对轨迹数据进行处理和分析，提取出未知道路，最后将未知道路集成到已有道路中，供导航使用。

(2)未知道路导航：获取未知道路后，在实际使用过程中通过计算未知道路的导航信息包括拐弯方向和拐弯距离，结合实时定位，并将实时位置匹配到已有的未知道路上，实现实时导航。

进一步地，所述步骤(1)包括以下子步骤：

(1.1)起点和终点之间的轨迹采集：基于GPS技术，在移动应用中集成定位功能，车辆运行过程中按照每秒一次的频率自动采集车辆当前实时的经度、纬度、时间、方位角和速度。到达目的地之后，移动端应用将采集到的数据通过网络上传到服务端。

(1.2)轨迹数据处理：对采集到的轨迹数据去除经纬度为0的点，并对路线进行滤波。

(1.3)未知道路分析：通过调用导航地图的规划功能，获取导航地图计算的从起点到终点之间的规划路线，采用空间分析方法将轨迹和规划路线进行对比，分析出候选的未知道路。

(1.4)未知道路提取：对待选的未知道路进行筛选去除零碎道路，零碎道路主要包括两个方面：一是两条待选未知道路之间间隔很近，即有很短的一部分轨迹包含于缓冲区中，另 一方面是待选的未知道路很短。对于第一种情况，需要将这两条未知道路进行拼接。对于第二种情况只需判断未知道路长度，如小于阈值，则去除该候选未知道路。

(1.5)未知道路连接到规划路线：通过轨迹路线与规划路线缓冲区分析生成了未知道路；未知道路分为两类：与规划路线没有连接和与规划路线连接。对于第二种类型，使用缓冲区分析得到的未知道路与规划路线并未衔接上，需要将未知道路延长，并找出其与规划路线的衔接点，将分析出的未知道路延长衔接到规划路线上。

进一步地，所述步骤(1.2)具体为：首先对所有轨迹点数据进行遍历，检查经纬度是否同时为0，如是则将其删除；然后，采用卡尔曼滤波对轨迹进行平滑，将轨迹数据逐一地进行滤波计算。

进一步地，所述步骤(1.3)中，所述空间分析方法具体为：以规划路线为基准进行缓冲区分析(buffer)，得到规划路线的缓冲区，其类型不再是线而是多边形；然后将轨迹路线与规划路线缓冲区进行差异分析(difference)，会得到轨迹路线中不被包含在规划路线缓冲区的部分，这部分差异数据为一段路或者多段路，即为候选的未知道路集。

进一步地，所述步骤(1.4)中，对于第一种情况的拼接方法具体为：将轨迹路线与(1.3)的规划路线缓冲区进行交叉分析(intersection)，可得到包含在缓冲区中的轨迹路线，同样也是一段路或者多段路。这些路段与候选的未知道路存在前后相邻关系。遍历交叉分析得到的每一条路段，如果距离小于阈值，则将其前后相邻的候选未知道路以及该段路合并，形成一条未知道路。

进一步地，所述步骤(1.5)中，将未知道路延长衔接到规划路线上的方法具体为：未知道路的端点为历史轨迹与规划路线缓冲区的交点，并不在规划路线上，从此交点开始遍历轨迹路线的点，直到点与规划路线的距离在阈值N之内，选择出该点，称为待衔接点。将以该点为圆心，阈值N为半径的圆与规划路线进行相交(intersection)分析，得到一个交点集，点集中与待衔接点距离最近的点即选为未知道路与规划路线的衔接点；原未知道路延长直到该衔接点，即为完整的并且衔接到规划路线的未知道路。

进一步地，所述步骤(2)包括以下子步骤：

(2.1)导航信息计算：计算出路线的拐弯点以及距离信息，形成导航信息列表。

(2.2)实时导航：在行驶过程中，通过定位技术得到当前实时位置，对实时位置数据进行卡尔曼滤波，将实时位置匹配到使用的未知道路上，计算出当前车辆在未知道路的位置以及接下来多少距离需要拐弯的信息，实现导航。如果实时位置离未知道路的距离超过阈值，且持续一段时间，则判定当前车辆为偏航，不会将实时位置匹配到未知道路上，并通知使用者已处于偏航状态。

进一步地，所述步骤(2.1)具体为：从未知道路的第二个点开始遍历，每个点与前一个点形成向量1，每个点与后一个点形成向量2，向量1与向量2进行点乘与叉乘，分别得到角 度和方向，通过角度可以判断是向前走、调头还是左右转，通过方向可以判断具体是向左还是向右。所有点的信息计算完成之后，选择非直行的点为导航主要信息点，形成导航信息列表。

进一步地，所述步骤(2.2)中，所述将实时位置匹配到使用的未知道路上具体包括以下子步骤：

(2.2.1)确认在未知道路上实时位置的待匹配区域。对第一个实时位置进行匹配时，不进行这一步分析，默认待匹配区域为整段未知道路；从获取第二个实时位置开始，根据上一个点的匹配位置、定位时间间隔和车辆速度来计算。未知道路由很多线段组成，线段的端点即为结点，因此匹配点可以是某一结点或者落于某一线段中；逐个计算上一个匹配点与其后的道路结点的距离，超过阈值Q的结点即为车辆最快能到达的地方，阈值Q为间隔时间内以最大速度行驶的距离；同样计算匹配点与其之前的道路结点距离，超过阈值的结点即为车辆最快能倒退回的地方，位于这两个结点之间的区域即当前实时位置的大致匹配区域。依此类推，计算出之后每一个实时位置的大致匹配区域。

(2.2.2)在大致匹配区域内部找到最合适的点作为匹配点。计算实时位置与该区域内所有结点的距离，选择一定阈值内的距离最小的结点作为候选点；计算实时位置与该区域内所有道路线段的距离，距离最小的线段作为候选线段。如果存在最近的候选结点，则优先选择结点为匹配点，否则，计算实时位置在候选线段上的垂足，将垂足作为匹配点。

(2.2.3)拿到匹配点之后，可以根据所在位置的索引从(2.1)的导航信息列表中获取到接下来的拐弯信息，从而计算出当前位置的导航信息，实现导航。

本发明的有益效果如下：可以通过历史轨迹提取到实际存在导航地图上未标识的道路，并且实现未知道路的导航方便使用，一定程度避免了因为导航地图道路更新缓慢导致绕路或者到不了目的地的现象，尤其利于物流配送领域。

附图说明

图1是未知道路采集提取的流程图；

图2是未知道路分析提取算法图，(a)中未知道路与规划路线没有连接，(b)中未知道路与规划路线有连接；

图3是未知道路与规划路线衔接的示意图；

图4是未知道路导航流程图；

图5是未知道路匹配算法图。

具体实施方式

下面结合附图详细描述本发明，本发明的目的和效果将变得更加明显。

本发明是通过以下技术方案实现的：基于现有的导航地图和GPS、GIS技术，通过对车辆行驶的历史轨迹进行分析和计算，识别出未知的道路信息，再将未知道路集成到已知道路中， 结合定位技术实现对未知道路的导航，从而能够将导航延伸到原先无法达到的地方。

具体包括以下步骤：

(1)未知道路采集提取：大致流程如图1所示，通过轨迹采集得到初始的行驶轨迹数据，对轨迹数据进行处理和分析，提取出未知道路，最后将未知道路集成到已有道路中，供导航使用。具体如下：

(1.1)起点和终点之间的轨迹采集：基于GPS技术，在移动应用中集成定位功能，车辆运行过程中按照每秒一次的频率自动采集车辆当前实时的经度、纬度、时间、方位角和速度。到达目的地之后，移动端应用会将采集到的数据通过网络(3G/4G信号或者WIFI)上传到服务端。

(1.2)轨迹数据处理：由于GPS定位的误差，采集到的轨迹数据可能存在偏差比较大的点，以及整体轨迹路线平滑度很低，需要对其进行处理。处理内容包括：去除经纬度为0的点和对路线进行滤波。首先对所有轨迹点数据进行遍历，检查经纬度是否同时为0，如是则将其删除；然后，采用卡尔曼滤波对轨迹进行平滑，将轨迹数据逐一地进行滤波计算，可达到去除噪声和还原真实的效果。

(1.3)未知道路分析：轨迹路线处理完毕之后，通过调用导航地图的规划功能，获取导航地图计算的从起点到终点之间的规划路线，采用空间分析方法将轨迹和规划路线进行对比，可分析出候选的未知道路。

具体空间分析方法为：以规划路线为基准进行缓冲区分析(buffer)，缓冲距离大致为30m，得到规划路线的缓冲区，其类型不再是线而是多边形，如图2中显示的缓冲区；然后将轨迹路线与规划路线缓冲区进行差异分析(difference)，会得到轨迹路线中不被包含在规划路线缓冲区的部分，这部分差异数据为一段路或者多段路，即为候选的未知道路集，如图2(a)中的整段未知道路以及图2(b)中标为1和2的道路。

(1.4)未知道路提取：基于GPS采集数据存在误差，需要对待选的未知道路进行筛选去除零碎道路，从而提取出真正的未知道路。零碎道路主要包括两个方面：一是可能存在两条待选未知道路之间间隔很近，即有很短的一部分轨迹包含于缓冲区中，另一方面是待选的未知道路很短。

对于第一种情况，需要将这两条未知道路进行拼接。具体做法为：将轨迹路线与(1.3)的规划路线缓冲区进行交叉分析(intersection)，可得到包含在缓冲区中的轨迹路线，同样也是一段路或者多段路。这些路段与候选的未知道路存在一定的前后相邻关系。遍历交叉分析得到的每一条路段，如果距离小于阈值，则将其前后相邻的候选未知道路以及该段路合并。在图2的下图中，如果包含在缓冲区内的轨迹距离很短，则需要将被包含的轨迹与路1和路2合并起来，形成一条未知道路。

对于第二种情况只需判断未知道路长度，如小于一定阈值，则去除该候选未知道路。

(1.5)未知道路连接到规划路线：通过轨迹路线与规划路线缓冲区分析，生成了未知道路；未知道路大致分为两类：与规划路线没有连接，多见于某个村子内部，规划路线为绕村子外面的大路，未知道路为村子内部直接从起点到终点的小路，如图2中的上图；与规划路线连接，多见于从一个村子到另一村子，规划路线仅包括乡道或者县道，未知道路为从乡道或县道拐进去的某条小路，如图2中的下图。对于第二种类型，使用缓冲区分析得到的未知道路与规划路线并未衔接上，为了实际使用需要将分析出的未知道路延长衔接到规划路线上，因此需要将未知道路延长，并找出其与规划路线的衔接点。

具体方法为：未知道路的端点为历史轨迹与规划路线缓冲区的交点，并不在规划路线上(如图3路1的左端点A离规划路线还有一段距离)，从此交点开始遍历轨迹路线的点，直到点与规划路线的距离在一定阈值N之内，选择出该点，称为待衔接点(如图3中B点，为轨迹上与规划路线距离在一定阈值范围内的点)。将以该点为圆心，阈值N为半径的圆与规划路线进行相交(intersection)分析，得到一个交点集，点集中与待衔接点距离最近的点即选为未知道路与规划路线的衔接点；原未知道路延长直到该衔接点，即为完整的并且衔接到规划路线的未知道路。如图3中，以B点为圆心的圆与规划路线相交分析，计算出衔接点为C，最后得到的未知道路为路1再加上延长路段AB和BC。

(2)未知道路语音导航：大致流程如图4所示，获取未知道路后，在实际使用过程中通过计算未知道路的导航信息包括拐弯方向、拐弯距离等，结合实时定位，并将实时位置匹配到已有的未知道路上，实现实时导航。具体如下：

(2.1)导航信息计算：生成的未知道路只有位置信息，提供导航服务之前需要计算出路线的拐弯点以及距离信息。计算方法为：从未知道路的第二个点开始遍历，每个点与前一个点形成向量1，每个点与后一个点形成向量2，向量1与向量2进行点乘与叉乘，分别得到角度和方向，通过角度可以判断是向前走、调头还是左右转，通过方向可以判断具体是向左还是向右。所有点的信息计算完成之后，选择非直行的点为导航主要信息点，形成导航信息列表。

(2.2)实时导航：在行驶过程中，通过定位技术得到当前实时位置，并将实时位置匹配到使用的未知道路上，继而可以计算出当前车辆在未知道路的位置以及接下来多少距离需要拐弯等信息，实现导航。实时位置一般游离在未知道路附近，匹配可以将实时位置匹配到未知道路上。在匹配之前需要对实时位置数据进行卡尔曼滤波。具体匹配算法如下：

首先确认在未知道路上实时位置的待匹配区域。对第一个实时位置进行匹配时，不进行这一步分析，默认待匹配区域为整段未知道路；从获取第二个实时位置开始，根据上一个点的匹配位置、定位时间间隔和车辆速度来计算。未知道路由很多线段组成，线段的端点即为结点(如图5中的结点1、2、3、4、5)，因此匹配点可以是某一结点或者落于某一线段中；逐个计算上一个匹配点与其后的道路结点的距离，超过一定阈值(间隔时间内以最大速度行 驶的距离)的结点即为车辆最快能到达的地方，同样计算匹配点与其之前的道路结点距离，超过一定阈值的结点即为车辆最快能倒退回的地方，位于这两个结点之间的区域即当前实时位置的大致匹配区域。依此类推，计算出之后每一个实时位置的匹配区域。如在图5中，上一个匹配位置为B，以点B为基准，前后减去一定距离，计算出的大致匹配区域为点2到点5。

其次，在大致区域内部找到最合适的点作为匹配点。计算实时位置与该区域内所有结点的距离，选择一定阈值内的距离最小的结点作为候选点；计算实时位置与该区域内所有道路线段的距离，距离最小的线段作为候选线段。如果存在最近的候选结点，则优先选择结点为匹配点，否则，计算实时位置在候选线段上的垂足，将垂足作为匹配点。如在图5中，计算当前位置A与结点2、3、4、5的距离以及中间三个线段的距离，在与结点距离都超过阈值的情况下，会选择结点4和5之间的线段为候选线段，因此A到该线段的垂足C则为实时位置的匹配点。

最后拿到匹配点之后，可以根据所在位置的索引从(2.1)的导航信息列表中获取到接下来的拐弯信息，从而计算出当前位置的导航信息，如接下来200米左拐。调用语音接口即可进行语音播报，实现语音导航的效果。

如果实时位置离未知道路的距离超过一定阈值，且持续一段时间，则判定当前车辆为偏航，不会将实时位置匹配到未知道路上，并语音通知使用者已处于偏航状态。

Claims (6)

1.一种针对现有导航地图中未知道路进行识别和导航的方法，其特征在于，包括以下步骤：

(1)未知道路采集提取：通过轨迹采集得到初始的行驶轨迹数据，对轨迹数据进行处理和分析，提取出未知道路，最后将未知道路集成到已有道路中，供导航使用；该步骤具体包括以下子步骤：

(1.1)起点和终点之间的轨迹采集：基于GPS技术，在移动应用中集成定位功能，车辆运行过程中按照每秒一次的频率自动采集车辆当前实时的经度、纬度、时间、方位角和速度；到达目的地之后，移动端应用将采集到的数据通过网络上传到服务端；

(1.2)轨迹数据处理：对采集到的轨迹数据去除经纬度为0的点，并对路线进行滤波；

(1.3)未知道路分析：通过调用导航地图的规划功能，获取导航地图计算的从起点到终点之间的规划路线，采用空间分析方法将轨迹和规划路线进行对比，分析出候选的未知道路；

(1.4)未知道路提取：对待选的未知道路进行筛选去除零碎道路，零碎道路主要包括两个方面：一是两条待选未知道路之间间隔很近，即有很短的一部分轨迹包含于缓冲区中，另一方面是待选的未知道路很短；对于第一种情况，需要将这两条未知道路进行拼接；对于第二种情况只需判断未知道路长度，如小于阈值，则去除该候选未知道路；

(1.5)未知道路连接到规划路线：通过轨迹路线与规划路线缓冲区分析生成了未知道路；未知道路分为两类：与规划路线没有连接和与规划路线连接；对于第二种类型，使用缓冲区分析得到的未知道路与规划路线并未衔接上，需要将未知道路延长，并找出其与规划路线的衔接点，将分析出的未知道路延长衔接到规划路线上；

(2)未知道路导航：获取未知道路后，在实际使用过程中通过计算未知道路的导航信息包括拐弯方向和拐弯距离，结合实时定位，并将实时位置匹配到已有的未知道路上，实现实时导航；该步骤具体包括以下子步骤：

(2.1)导航信息计算：计算出路线的拐弯点以及距离信息，形成导航信息列表；

(2.2)实时导航：在行驶过程中，通过定位技术得到当前实时位置，对实时位置数据进行卡尔曼滤波，将实时位置匹配到使用的未知道路上，计算出当前车辆在未知道路的位置以及接下来多少距离需要拐弯的信息，实现导航；如果实时位置离未知道路的距离超过阈值，且持续一段时间，则判定当前车辆为偏航，不会将实时位置匹配到未知道路上，并通知使用者已处于偏航状态；所述将实时位置匹配到使用的未知道路上具体包括以下子步骤：

(2.2.1)确认在未知道路上实时位置的待匹配区域；对第一个实时位置进行匹配时，不进行这一步分析，默认待匹配区域为整段未知道路；从获取第二个实时位置开始，根据上一个点的匹配位置、定位时间间隔和车辆速度来计算；未知道路由很多线段组成，线段的端点即为结点，因此匹配点是某一结点或者落于某一线段中；逐个计算上一个匹配点与其后的道路结点的距离，超过阈值Q的结点即为车辆最快能到达的地方，阈值Q为间隔时间内以最大速度行驶的距离；同样计算匹配点与其之前的道路结点距离，超过阈值的结点即为车辆最快能倒退回的地方，位于这两个结点之间的区域即当前实时位置的大致匹配区域；依此类推，计算出之后每一个实时位置的大致匹配区域；

(2.2.2)在大致匹配区域内部找到最合适的点作为匹配点；计算实时位置与该区域内所有结点的距离，选择一定阈值内的距离最小的结点作为候选点；计算实时位置与该区域内所有道路线段的距离，距离最小的线段作为候选线段；如果存在最近的候选结点，则优先选择结点为匹配点，否则，计算实时位置在候选线段上的垂足，将垂足作为匹配点；

(2.2.3)拿到匹配点之后，根据所在位置的索引从(2.1)的导航信息列表中获取到接下来的拐弯信息，从而计算出当前位置的导航信息，实现导航。

2.根据权利要求1所述一种针对现有导航地图中未知道路进行识别和导航的方法，其特征在于，所述步骤(1.2)具体为：首先对所有轨迹点数据进行遍历，检查经纬度是否同时为0，如是则将其删除；然后，采用卡尔曼滤波对轨迹进行平滑，将轨迹数据逐一地进行滤波计算。

3.根据权利要求1所述一种针对现有导航地图中未知道路进行识别和导航的方法，其特征在于，所述步骤(1.3)中，所述空间分析方法具体为：以规划路线为基准进行缓冲区分析，得到规划路线的缓冲区，其类型不再是线而是多边形；然后将轨迹路线与规划路线缓冲区进行差异分析，会得到轨迹路线中不被包含在规划路线缓冲区的部分，这部分差异数据为一段路或者多段路，即为候选的未知道路集。

4.根据权利要求1所述一种针对现有导航地图中未知道路进行识别和导航的方法，其特征在于，所述步骤(1.4)中，对于第一种情况的拼接方法具体为：将轨迹路线与(1.3)的规划路线缓冲区进行交叉分析，可得到包含在缓冲区中的轨迹路线，同样也是一段路或者多段路；这些路段与候选的未知道路存在前后相邻关系；遍历交叉分析得到的每一条路段，如果距离小于阈值，则将其前后相邻的候选未知道路以及该段路合并，形成一条未知道路。

5.根据权利要求1所述一种针对现有导航地图中未知道路进行识别和导航的方法，其特征在于，所述步骤(1.5)中，将未知道路延长衔接到规划路线上的方法具体为：未知道路的端点为历史轨迹与规划路线缓冲区的交点，并不在规划路线上，从此交点开始遍历轨迹路线的点，直到点与规划路线的距离在阈值N之内，选择出该点，称为待衔接点；将以该点为圆心，阈值N为半径的圆与规划路线进行相交分析，得到一个交点集，点集中与待衔接点距离最近的点即选为未知道路与规划路线的衔接点；原未知道路延长直到该衔接点，即为完整的并且衔接到规划路线的未知道路。

6.根据权利要求1所述一种针对现有导航地图中未知道路进行识别和导航的方法，其特征在于，所述步骤(2.1)具体为：从未知道路的第二个点开始遍历，每个点与前一个点形成向量1，每个点与后一个点形成向量2，向量1与向量2进行点乘与叉乘，分别得到角度和方向，通过角度可以判断是向前走、调头还是左右转，通过方向可以判断具体是向左还是向右；所有点的信息计算完成之后，选择非直行的点为导航主要信息点，形成导航信息列表。