法律状态公告日
法律状态信息
法律状态
2018-02-27
未缴年费专利权终止 IPC(主分类):G06F19/00 授权公告日:20160817 终止日期:20170127 申请日:20150127
专利权的终止
2016-08-17
授权
授权
2015-05-27
实质审查的生效 IPC(主分类):G06F19/00 申请日:20150127
实质审查的生效
2015-04-29
公开
公开
技术领域
本发明涉及基于认知规律的时空轨迹融合方法及路网拓扑生成方法，属于地理信息系统与智能交通研究领域。
背景技术
随着城市交通的飞速发展与交通环境的日益恶化，人们出行时对精细程度高、现势性好的道路信息需求迫在眉睫，同时，人们每天穿行于城市道路网络中，会产生海量时空轨迹数据，是精细道路数据的产生者和感知者，如何从人们日常出行的海量时空轨迹中挖掘和提取出人们出行需求的道路信息，成为全世界科学家们面临的科学难题。
从时空GPS轨迹数据中提取道路网信息的研究已经开展了相关的探索性工作，主要分为二类方法，第一类研究主要采用栅格化方法将轨迹数据栅格化后提取道路的中心线，第二类研究主要是采用轨迹聚类的方法。
虽然研究人员已经提出了生成基于GPS数据的数字道路地图上面的方法，这些方法不适用于从大量GPS数据中提取路网的原因有两个：以上研究都没有考虑出租车司机择路的经验知识，没有从认知的角度分析轨迹之间的联系；都从GPS轨迹数据中对道路数据进行了一定程度的提取，但是对于目前如此复杂的城市道路网络拓扑关系的提取较为困难。
发明内容
为了便于从人们日常出行的海量时空轨迹中挖掘和提取出人们出行需求的道路图形和拓扑信息，本发明提出了基于认知规律的时空轨迹融合方法及路网拓扑生成方法。
本发明通过以下技术手段解决上述问题：
一种基于认知规律的时空轨迹融合方法，包括以下步骤，
步骤1，若当前的新轨迹与融合前轨迹之间存在部分重合，在轨迹分离处打断，得到待融合的两条相似轨迹段，新轨迹中重合轨迹部分以外的直接添加到融合前轨迹中，然后进入步骤2；若当前的新轨迹与融合前轨迹之间不存在部分重合，判断当前的新轨迹与融合前轨迹之间是否存在交点，若存在则在交点处打断并记录，将新轨迹添加到融合前轨迹中后进入步骤4，若不存在，则直接将新轨迹添加到融合前轨迹中后进入步骤4；
步骤2，进行基于两条相似轨迹段约束的Delaunay三角形构网，包括以下子步骤，步骤2.1，定义新添加的轨迹线上轨迹点的权重值为1，融合前轨迹线上轨迹点的权重值与生 成该轨迹线的轨迹线数目n相等；
步骤2.2，判断两条相似轨迹段是否存在相交部分，若存在，在交点处打断并记录交点，进入步骤2.3，若不存在则直接进入步骤2.3；
步骤2.3，依据Delaunay构网的准则，以两条相似轨迹段的轨迹点为基础构造Delaunay三角网；
步骤3，进行两条相似轨迹段的融合，包括分析Delaunay三角网中各三角形相互之间边与边的邻接关系，根据邻接关系分别生成各三角形的相应融合线段，依次连接各三角形的相应融合线段，并记录方向和经验权值，得到基于Delaunay三角网的融合后轨迹段；
所述根据邻接关系分别生成各三角形的相应融合线段实现方式为，对于与其他三角形有两条邻接边的三角形，相应融合线段是两条邻接边的权值比分割点的连线，对于与其他三角形只有一条邻接边的三角形，相应融合线段是邻接边的权值比分割点与其相对的端点的连线；所述权值比分割点求取方式如下，
权值比分割点P是由两端点A、B计算得出，
TP＝TA+TB
其中，XI、YI和TI分别代表点I的x坐标、y坐标和权重值，I取P、A和B；
步骤4，当还有未处理的新轨迹时，将当前的融合后轨迹线作为融合前轨迹线，返回步骤1继续融合，直到所有新轨迹参与融合为止，根据所有轨迹线参与融合的结果生成路网。
一种根据上述基于认知规律的时空轨迹融合方法实现的路网拓扑生成方法，每当在当前的新轨迹与融合前轨迹之间存在部分重合，在轨迹分离处打断时进行拓扑点提取，最后根据步骤4所得路网基于拓扑点提取结果生成道路拓扑图；所述拓扑点提取实现如下，
如果新轨迹上轨迹分离点与融合前轨迹上已存的拓扑点的位置相近，则直接计算该轨迹分离点与已存拓扑点所构成线段的权值比分割点为新的拓扑点，来替代已存的拓扑点；
否则，设两条轨迹上轨迹分离点分别是A1和A2，融合前轨迹上在轨迹分离点之后为非相似轨迹段1，新轨迹在轨迹分离点之后为非相似轨迹段2，取线段A1A1的权值比分割点M点为拓扑点，将非相似轨迹段1上的轨迹分离点的下一点N以及非相似轨迹段2上的轨迹分离点的下一点Q分别与M点相连。
本发明的基于认知规律的时空轨迹融合方法及路网拓扑生成方法，得到的实验结果图形上贴近于真实的道路网，并能准确提取城市道路网络的拓扑关系。
附图说明：
图1是本发明实施例的方法流程图；
图2是本发明实施例的相似轨迹分段示意图；
图3是本发明实施例的交点打断示意图；
图4是本发明实施例相似轨迹段基于线约束的Delaunay三角形构网示意图；
图5是本发明实施例拓扑点的提取示意图；
图6是本发明实施例拓扑关系的提取示意图；
图7是本发明实施例拓扑关系的生成示意图。
具体实施方式
本发明可利用出租车GPS实现，基于出租车时空GPS轨迹融合生成路网的本质是通过出租车GPS对城市路网的多次体验，形成城市路网空间格局的认知过程，所以当出租车GPS轨迹记录到初次城市路网的体验时，会感知城市路网的道路形状等特征，是对路网的一种局部的、抽象的特征感知，属于空间认知的第一个特征感知层次；当出租车进行多次体验时，越来越多局部的、低等级道路会被遍历到，城市路网图形和拓扑的细节层次进一步丰富，形成对城市道路实体的对象认知，这属于空间认知的第二个空间对象感知层次；随着出租车司机对路网体验次数的进一步增加，一方面越来越多的道路被发现，另一方面重复遍历的道路的特征轮廓会变得更加符合真实道路，最初探测到简略的、粗放的路网图形和拓扑信息会变得越来越丰富、越来越精细，通过对道路空间特征与道路实体对象进行简化、关联及综合加工，使得道路网的图形越来越逼真、拓扑信息越来越完善，形成对路网的精细化表达，最终实现道路网数据的生成，这是空间认知的第三个空间格局认知层次。
本发明提出基于Delaunay三角网的时空轨迹线融合方法，不断将新添加的轨迹线与之前融合生成的融合轨迹线进行再次融合，以便得到更加丰富细致的道路图。本发明技术方案可采用计算机软件方式支持自动运行流程。以下结合实施例和附图详细说明本发明技术方案。
参见图1，本发明实施例提供的一种基于认知规律的时空轨迹融合方法，包括如下步骤：
1)对当前的新轨迹与融合前轨迹之间存在部分重合的情况，进行轨迹分段，得到待融合的两条相似轨迹线，然后进入2)进行融合；对于当前的新轨迹与融合前轨迹之间不存在部分重合的情况，通过添加新轨迹实现融合，直接进入4)，这种情况不是本发明的重点，本领域技术人员可以简单地实现，不予赘述。
实施例的步骤1)具体实现如下，
第一次执行1)时将初次体验得到的轨迹作为融合前轨迹，将当前的新轨迹与融合前轨 迹进行融合。当两条轨迹之间存在部分重合时，在轨迹分离处打断并将重合轨迹部分标记为待融合的相似轨迹段，新轨迹中重合轨迹部分以外的直接添加到融合前轨迹中；当两条轨迹之间没有重合的轨迹段时，则不需进行轨迹分段(即在轨迹分离处打断)，而是判断其是否存在交点，若存在则在交点处打断并记录，然后将新轨迹添加到融合前轨迹中，若不存在则直接将新轨迹添加到融合前轨迹中。
如图2、3所示，图2中的a1-a2-a3和图3中的b1-b2-b3是两种不同的情况，a1中的融合前轨迹与新轨迹之间存在部分重合轨迹段，在轨迹分离的地方打断(如图2中a2部分所示)，将重合轨迹部分标记为待融合的相似轨迹，依据下文提出的轨迹融合的方法进行融合，得到融合后轨迹。(如图2中a3所示)。图3中b1中融合前轨迹和新轨迹相交，没有重合的轨迹段，在轨迹相交的部分将两条轨迹打断并记录交点(如图3中b2)，将交点插入到两条轨迹之中，生成融合后轨迹(如图3b3所示)。
2)基于两条相似轨迹段约束的Delaunay三角形构网：
Delaunay三角网在空间邻近分析上是一种较好的支持模型，在多边形群的合并、地图综合冲突关系探测与移位处理、地貌形态分析中，取得了令人满意的结果。本发明实施例针对相似轨迹段的融合，将两条相似轨迹作为约束线，采用基于线约束的Delaunay三角形构网(如图4所示)，具体的三角形构网方法如下：
2.1)在图4中，粗线为融合前轨迹上的相似轨迹段，细线为新轨迹上的相似轨迹段。注意轨迹点上带有权重值，定义新添加的轨迹线上轨迹点的权重值为1，融合前轨迹线上轨迹点的权重值与生成该轨迹线的轨迹线数目n(之前融合了n-1次)相等，参见图4的①部分；
2.2)参见图4的②部分，判断两条相似轨迹段是否存在相交部分，若存在，在交点处打断并记录交点，进入2.3)，若不存在则直接进入2.3)；
2.3)参见图4的③部分，依据Delaunay构网的准则——三角网中任何三角形的外接圆范围内不会有其它点存在并与其通视——以两条相似轨迹段的轨迹点为基础构造Delaunay三角网，实现构造约束Delaunay三角网。
3)进行两条相似轨迹段的融合
从上一步构造的Delaunay三角网中提取融合后轨迹，需要分析Delaunay三角网中各个三角形相互之间边与边的邻接关系，进行基于邻接关系的融合点生成，从而生成道路融合轨迹。
Delaunay三角网中各个三角形相互之间边与边的邻接关系主要存在两类邻接状态(如图4所示)，其融合后轨迹生成的方式分别为：
参见图4的④部分，
第I类三角形：与其他三角形有两条邻接边的三角形，相应融合线段是两条邻接边的权值比分割点的连线；
第II类三角形：与其他三角形只有一条邻接边的三角形，相应融合线段是邻接边权值比分割点与其相对的端点的连线。
在第I类、第II类三角形中，权值比分割点P是由邻接边的两端点A、B计算得出，见公式1、2，其中XI、YI和TI分别代表点I的x坐标、y坐标和权重值。(I本例中取P、A和B点)
TP＝TA+TB(公式2)
参见图4的⑤部分，根据邻接关系分别生成各三角形的相应融合线段后，依次连接各Delaunay三角形中所生成的融合线段，并记录方向和经验权值，融合后的轨迹点权值变为n+1，即可得到对两条相似轨迹段基于Delaunay三角网的融合后轨迹段，进入4)。
4)经步骤1)添加和步骤3)根据三角网的融合后，得到当前的融合后轨迹线。当还有未处理的新轨迹时，需要进一步进行轨迹融合，则将当前的融合后轨迹线作为融合前轨迹线，返回1)与新轨迹一起继续融合，直到所有新的轨迹线参与融合为止，进行路网生成，根据所有轨迹线参与融合的结果生成路网。
随着越来越多的轨迹线参与融合，生成的融合后轨迹线会越来越趋近于真实的道路线，这符合空间认知的规律——随着体验次数的增加，司机对于道路网的认知会越来越丰富，越来越完善。司机对路网的初次体验是司机首次对路网探测行为，从中可以获取到一条理论可行的行驶轨迹线，当对路网进行多次体验时，在路口处会产生各种不同的行驶选择，轨迹线相互之间存在部分重叠，首先对新加入的轨迹线进行轨迹分段，针对轨迹间重叠区域，利用上文所叙述的基于Delaunay三角网的轨迹线融合方法，依次将不同轨迹段中相似的轨迹线部分融合起来，来实现多次体验的路网图的生成。
基于上述融合过程，可以进行路网拓扑图的生成：本发明进一步提供一种路网拓扑生成方法，每当在当前的新轨迹与融合前轨迹之间存在部分重合，在轨迹分离处打断时进行拓扑点提取，最后根据步骤4所得路网基于拓扑点提取结果生成道路拓扑图。
1)拓扑点生成
拓扑点表达的是路段相互之间的拓扑连通信息，一般是在路段分叉的时候出现。跟踪司 机的驾驶行为，当新轨迹与旧轨迹发生轨迹分离的时候，说明此处有不同的拓扑连通关系，需要加拓扑点来表达路网的连通性。
道路网拓扑点提取可在每次出现相似轨迹分段的时候进行，首先分析新轨迹上轨迹分离点的位置：
如果新轨迹上轨迹分离点与融合前轨迹上已存的拓扑点的位置相近(具体实施时可以由本领域技术人员预设相近判断阈值，例如2m，当小于2m时为相近)，则直接计算该轨迹分离点与已存拓扑点所构成线段的权值比分割点为新的拓扑点，来替代已存的拓扑点，权值比分割点同样根据公式1、2定义。即以轨迹分离点与已存拓扑点分别为边的两端点A、B，计算权值比分割点P。
如果新轨迹上的轨迹分离点附近(例如2m内)没有已存的拓扑点，则需要依据轨迹分段的情况生成新的拓扑点。轨迹分段时两条轨迹线可分为三个部分：相似轨迹段、非相似轨迹段1和非相似轨迹段2，如图5所示，在当前的新轨迹与融合前轨迹之间存在部分重合，融合前轨迹上在轨迹分离点之后为非相似轨迹段1，新轨迹在轨迹分离点之后为非相似轨迹段2。设两条轨迹上轨迹分离点分别是A1和A2，取线段A1A1的权值比分割点M点为拓扑点，权值比分割点同样根据公式1、2定义，即以A1和A2分别为边的两端点A、B，计算权值比分割点P。两条轨迹的相似轨迹段经过轨迹融合后生成的融合线的端点恰好是M点，因此与M点存在必然的连通关系，再将非相似轨迹段1上的轨迹分离点的下一点N点以及非相似轨迹段2上的轨迹分离点的下一点Q点分别与M点相连，则在拓扑点M处实现了三个路段部分的连通，即完成了拓扑点的提取。
2)路网拓扑图的生成
在轨迹融合线的拓扑点提取基础上，根据基于认知规律的时空轨迹融合方法中步骤4)所得到的路网图，来进行城市道路网拓扑关系的提取。将道路网抽象表达为路口与路口之间的链接，可得交叉路口拓扑模型，从而获得道路拓扑图。具体实施时本领域技术人员可根据路口类型设定表达方式，进行拓扑关系提取。例如最常见的十字交叉路口和T字路口，如图6中白色的点为依据上文提到的方法得到的交叉路口范围内的拓扑点。计算各个交叉路口处所有已有拓扑点的重心，以该重心为圆心画圆，尽可能将所有的拓扑点包含在圆内，计算圆与各个道路段的交点，也记录为拓扑点。圆圈内表达的是交叉路口各路段的拓扑连通性，称之为拓扑圆。剔除多余的与拓扑表达无关的轨迹点，遍历轨迹线所经过的拓扑点的先后顺序，用带有方向的弧段来表达各个拓扑点之间的连通性，得到的交叉路口处的拓扑关系如图7所示。依据各路段上的连通性，将各个交叉路口的拓扑圆用道路抽象线连接起来，即实现了路 网拓扑图的生成。
基于本发明，可以方便地获取路网图形数据与拓扑数据。
本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并不会偏离本发明的精神或超越所附权利要求书所定义的范围。
机译： 时空轨迹融合的方法
机译： 基于ZMP的可穿戴机器人步态轨迹生成的ZMP方法及步态轨迹生成系统的控制方法
机译： 基于气溶胶光学深度的基于大气反射率的时空图像融合方法
