一种应用于浮动车轨迹融合的高速道路形状修复方法

1.一种应用于浮动车轨迹融合的高速道路形状修复方法，导航地图中用于表示道路连通网络，虚拟出来的节点对象定义为NODE，近似的理解为现实道路的一个路口；导航地图中用于表示NODE与NODE之间通路的曲线型对象定义为LINK，近似的理解为现实道路连接两个路口的一段道路；以浮动车的轨迹TRACK和由TRACK融合生成的电子地图中LINK为对象进行处理和判定，每条TRACK和LINK上具有多个用来表示道路或轨迹形状的形状点，两个形状点之间的路段为形状点段，其特征在于包括以下步骤：
步骤一、删除短LINK：对于是同一个路口但由于轨迹处理而产生两个或者两个以上的NODE，对于满足相应条件NODE以及NODE之间的短LINK进行删除和合并操作；
步骤二、删除多余NODE点：根据NODE所连接的LINK，以及LINK与TRACK之间的对应关系，来判断LINK与LINK间是否有通行关系，无通行关系则删除该NODE，合并相关两条LINK；
步骤三、调整NODE点位置：根据进入LINK与退出LINK之间的角度判断，如果角度大于某一阀值，则将NODE点在相应范围内调整，使进入LINK与退出LINK的夹角趋于一个平滑的角度；
步骤四、调整形状点位置：根据高速道路在短距离内不会有急转弯和在短距离内不会有连续转弯的特点，对LINK形状点角度变化率的分析删除部分异常形状点，使LINK的形状变得平滑。
2.根据权利要求1所述的应用于浮动车轨迹融合的高速道路形状修复方法，其特征在于：所述步骤一具体包括以下步骤:
1.1)查找满足下列条件的NODE和LINK：
1.1.1)NODE_A关联多条高速道路LINK，LINK_A,LINK_B……LINK_N，N为大于1的自然数；
1.1.2)NODE_B关联多条高速道路LINK，LINK_A,LINK_B1,LINK_C1……LINK_N1，N1为大于1的自然数；
1.1.3)LINK_A的长度不大于某一阈值d；
1.2)判断是否可以删除LINK_A，如果LINK_B、LINK_C……LINK_N，除LINK_D外的对应TRACK全部包含在LINK_B1、LINK_C1……LINK_N1的对应TRACK中，则删除LINK_A,合并NODE_A、NODE_B。
3.根据权利要求1所述的应用于浮动车轨迹融合的高速道路形状修复方法，其特征在于：所述步骤二具体操作如下:
2.1)将某NODE_A所连接的高速LINK按照进入LINK与退出LINK进行分类；
2.2)判断某一条进入LINK_A与退出LINK_B的对应TRACK是否满足：LINK_B所对应的TRACK是LINK_A所对应TRACK的子集，如果满足LINK_A与LINK_B合并，消除NODE_A；
2.3)继续判断除LINK_A和LINK_B以外的进入和退出LINK所对应的TRACK是否满足条件。
4.根据权利要求1所述的应用于浮动车轨迹融合的高速道路形状修复方法，其特征在于：所述步骤三具体操作如下:
3.1)将NODE所连接的3条LINK，经过上述步骤二后所有的高速路口为三叉路口，按照与NODE的关系分为进入LINK和退出LINK；
3.2)判断进入LINK与退出LINK的夹角是不是大于阀值，如果大于阀值就调整NODE点，使进入LINK与退出LINK的夹角比较平滑。
5.根据权利要求1所述的应用于浮动车轨迹融合的高速道路形状修复方法，其特征在于：所述步骤四具体操作如下:
4.1)依次取出高速LINK上的连续4个形状点，分析该连续形状点的角度变化率，如果该变化率超过阀值，则认为该4个形状点中间两个点有一个是异常点；
4.2)结合后续的形状点，判断那一个点是异常点，并删除该异常点。

一种应用于浮动车轨迹融合的高速道路形状修复方法\n技术领域\n[0001] 本发明涉及一种应用于浮动车轨迹融合的高速道路形状修复方法，特别是涉及一种对从浮动车走行所获得的轨迹进行融合处理后的形状进行处理的过程，属于导航、电子地图、智能交通系统和数据挖掘的交叉领域。\n背景技术\n[0002] 为了获得实际路况信息，提供更精准、更有针对性的导航服务，对浮动车走行轨迹的收集以及分析是一种比较实用的方法。然而，由于浮动车采集的行车轨迹只是在离散时间点上采集的位置信息，因此会导致采集的行车轨迹产生不确定的形状损失(形状损失程度与采集的时间间隔、车速以及原始道路的形状有关)，尤其在高速道路(车速较快，采样点间距离较大)和弯道部分(短距离内形状变化较大)，将带来非常严重的失真。由这种严重失真的轨迹融合切割后生成的电子地图会出现与真实道路有较大偏差。另外，浮动车轨迹信息没有包含高度信息，在高架桥、立交、匝道立体交叉式道路上与平面道路采集的轨迹一样，因此，利用轨迹信息生成的电子地图会在立体交叉式道路上产生多余的NODE点,并且在这些区域生成的电子地图形状比较凌乱，与实际道路有很严重的偏差。这些严重偏差直接影响电子地图道路的匹配以及对浮动车信息的有效归类、数据挖掘，并严重影响基于浮动车采集信息对电子地图数据进行修正等高级应用。\n[0003] 相关名词解释：\n[0004] 1.浮动车\n[0005] 带有各种传感器、能采集相关信息的在道路上实际行驶的汽车。\n[0006] 2.形状损失\n[0007] 带有一定形状损失的道路形状信息，如图2，虚线所示为真实的道路形状，实线所示为形损失道路形状。\n[0008] 3.形状点\n[0009] 用来表示道路或行车轨迹形状的坐标点。\n[0010] 4.行车轨迹\n[0011] 浮动车在走行过程中采集的、用一系列形状点表示的轨迹形状。\n[0012] 5.融合\n[0013] 对符合一定条件的浮动车轨迹按照一定的规则生成电子地图的过程。参见图3。\n[0014] 6.NODE\n[0015] 导航地图中用于表示道路连通网络，虚拟出来的节点对象。可以近似的理解为现实道路的一个路口\n[0016] 7.LINK\n[0017] 导航地图中用于表示NODE与NODE之间通路的曲线型对象，由两个NODE——起始点NODE和终止点NODE，和若干形状点组成。可以近似的理解为现实道路连接两个路口的一段道路。\n[0018] 8.进入LINK\n[0019] 相对于NODE而言，沿着LINK的形状点顺序能到达该NODE的LINK。\n[0020] 9.退出LINK\n[0021] 相对于NODE而言，沿着LINK的形状点顺序能离开该NODE的LINK。\n[0022] 10.LINK与轨迹对应关系\n[0023] LINK与轨迹对应关系记录的是LINK由哪些轨迹融合而来，是一对多的关系。参见图3，LINK对应轨迹关系为：TRACK A，TRACK B，TRACKC，TRACK D，TRACK E。\n[0024] 11.角度变化\n[0025] 角度变化描述的是相邻形状点间的角度变化趋势，如图4所示，逆时针方向为正，顺时针方向为负。\n发明内容\n[0026] 本发明所要解决的问题是：根据高速道路上不会有十字路口以及短距离内不会有急转弯或者连续转弯的这种道路特性，提出一种应用于浮动车轨迹融合的高速道路形状修复方法，该方法可以较好的修复高速道路特别是匝道、高架、立交桥等立体式道路的形状，提高有损形状的道路轨迹信息与实地图数据道路形状信息或者有损形状的道路轨迹信息的相互比较的准确性，为轨迹形状处理、轨迹形状与实际地图的匹配以及进一步的数据挖掘打下良好的基础。\n[0027] 本发明所采用的技术方案为：\n[0028] 一种应用于浮动车轨迹融合的高速道路形状修复方法，导航地图中用于表示道路连通网络，虚拟出来的节点对象定义为NODE，近似的理解为现实道路的一个路口；导航地图中用于表示NODE与NODE之间通路的曲线型对象定义为LINK，近似的理解为现实道路连接两个路口的一段道路；以浮动车的轨迹TRACK和由TRACK融合生成的电子地图中LINK为对象进行处理和判定，每条TRACK和LINK上具有多个用来表示道路或轨迹形状的形状点，两个形状点之间的路段为形状点段，其特征在于包括以下步骤：\n[0029] 步骤一、删除短LINK：对于是同一个路口但由于轨迹处理而产生两个或者两个以上的NODE，对于满足相应条件的NODE以及NODE之间的短LINK进行删除和合并操作；\n[0030] 步骤二、删除多余NODE点：根据NODE所连接的LINK，以及LINK与TRACK之间的对应关系，来判断LINK与LINK间是否有通行关系，无通行关系则删除该NODE，合并相关两条LINK；\n[0031] 步骤三、调整NODE点位置：根据进入LINK与退出LINK之间的角度判断，如果角度大于某一阀值，则将NODE点在相应范围内调整，使进入LINK与退出LINK的夹角趋于一个平滑的角度；\n[0032] 步骤四、根据高速道路在短距离内不会有急转弯和在短距离内不会有连续转弯的特点，对LINK的形状点角度变化率的分析删除部分异常形状点，使LINK的形状变得平滑。\n[0033] 上述步骤一具体分为两个步骤：\n[0034] 1.1)查找满足下列条件的NODE和LINK，如图5所示：\n[0035] 1.1.1)NODE_A关联多条高速道路LINK，LINK_A,LINK_B……LINK_N，N为大于1的自然数；\n[0036] 1.1.2)NODE_B关联多条高速道路LINK，LINK_A,LINK_B1,LINK_C1……LINK_N1，N1为大于1的自然数；\n[0037] 1.1.3)LINK_A的长度不大于某一阈值d；\n[0038] 1.2)判断是否可以删除LINK_A\n[0039] 如果LINK_B,LINK_C……LINK_N(除LINK_D外)的对应TRACK全部包含在LINK_B1,LINK_C1……LINK_N1的对应TRACK中，则删除LINK_A,合并NODE_A,NODE_B。\n[0040] 步骤二删除多余NODE点具体步骤为：\n[0041] 2.1)将某NODE_A所连接的高速LINK按照进入LINK与退出LINK进行分类；\n[0042] 2.2)判断某一条进入LINK_A与退出LINK_B的对应TRACK是否满足：LINK_B所对应的TRACK是LINK_A所对应TRACK的子集，如果满足LINK_A与LINK_B合并，消除NODE_A；\n[0043] 2.3)继续判断除LINK_A和LINK_B以外的进入和退出LINK所对应的TRACK是否满足条件。\n[0044] 查找连接大于3条高速LINK的NODE_A，本文中以两条进入LINK，两条退出LINK为例进行说明，如图6，LINK_A,LINK_B为进入LINK，LINK_C,LINK_D为退出LINK，判断LINK_A所对应的TRACK是全部包含在LINK_C或者LINK_D对应的TRACK中，并且，LINK_B所对应的TRACK是全部包含在LINK_D或者LINK_C对应的TRACK中。如果是，删除NODE_A,合并LINK_A与LINK_C或者LINK_D，合并LINK_B与LINK_D或者LINK_C。此处以NODE_A连接4条LINK为例，大于4条LINK连接的原理相同。\n[0045] 上述步骤三调整NODE点位置，具体包括以下步骤：\n[0046] 3.1)将NODE所连接的3条LINK，经过上述步骤二后所有的高速路口为三叉路口，按照与NODE的关系分为进入LINK和退出LINK；\n[0047] 3.2)判断进入LINK与退出LINK的夹角是不是大于阀值，如果大于阀值就调整NODE点，使进入LINK与退出LINK的夹角比较平滑。\n[0048] 假设进入LINK为2条，退出LINK为一条(进入LINK为1条，退出LINK为2条的情况类似处理)，取每条进入LINK倒数第二个形状点、NODE点、退出LINK的第二个形状点组成两条折线段LINE_A,LINE_B，分析LINE_A,LINE_B的角度变化，如果LINE_A或者LINE_B变化大于某一阀值，则在相应范围内调整NODE点的位置，使LINE_A,LINE_B的角度变化都趋于平缓。\n[0049] 步骤四调整形状点位置，过程处理如下：\n[0050] 4.1)依次取出高速LINK上的连续4个形状点，分析该连续形状点的角度变化率，如果该变化率超过阀值，则认为该4个形状点中间两个点有一个是异常点；\n[0051] 4.2)结合后续的形状点，判断那一个点是异常点，并删除该异常点。\n[0052] 依据高速和匝道上不会存在急转弯或者小范围内连续转弯的特点来分析LINK的形状点的角度变化，对LINK上导致出现角度变化超过阀值的点进行删除，使整条LINK的形状在整体上趋于平滑，如图9，依次连续的取LINK上的形状点POINT A、POINT B、POINT C、POINT D、POINT E、POINT F，取POINT A、POINT B、POINT C的角度变化率为α，取POINT B、POINT C、POINT D的角度变化率β，取POINT D、POINT E、POINT F的角度变化率为γ，取POINT A、POINT B、POINT D的角度变化率为δ，取POINT A、POINT C、POINT D的角度变化率为ε；\n[0053] 如果|α-β|>θ，θ为阀值，则认为POINT B或者POINT C是异常点；记α1＝|γ-δ|，记α2＝|γ-ε|，如果α1>α2，并且POINT A与POINT B的距离小于阀值d或者POINT B与POINT C的距离小于阀值d，则认为POINT B是异常点，删除POINT B；如果α1<α2，并且POINT B与POINT C的距离小于阀值d或者POINT C与POINT D的距离小于阀值d，认为POINT C是异常点，删除POINT C；如果|α-β|<θ，则认为POINT B、POINT C都是正常点。\n[0054] 本发明的优点是：将浮动车采集所得的轨迹信息生成电子地图后，能对高速、匝道、高架立体式道路和形状损失较严重的地方有一定的修复，使电子地图的品质有较大的提升，为之后基于此电子地图其他方面的数据挖掘打下基础。\n附图说明\n[0055] 图1是本发明的流程图；\n[0056] 图2是有损道路形状概念示意图；\n[0057] 图3是LINK与TRACK对应关系概念示意图；\n[0058] 图4是角度变化概念的示意图；\n[0059] 图5是本发明删除NODE点中删除短LINK示意图；\n[0060] 图6是本发明删除NODE点示意图；\n[0061] 图7是本发明NODE点调整的示意图；\n[0062] 图8是本发明NODE点调整后的示意图；\n[0063] 图9是本发明形状点调整示意图；\n具体实施方式\n[0064] 为了便于本领域普通技术人员理解和实施本发明，下面结合附图及具体实施方式对本发明作进一步的详细描述。\n[0065] 如图5所示，本发明的实现方式，在开始之后包括以下步骤：\n[0066] 1)删除短LINK\n[0067] 对于是同一个路口但是由于轨迹处理而产生两个或者两个以上的NODE，对于满足相应条件NODE以及NODE之间的短LINK进行删除和合并操作；\n[0068] 具体方法分为以下三步：\n[0069] 1.1)查找满足下列条件的NODE和LINK，如图5所示：\n[0070] 1.1.1)NODE_A关联多条高速道路LINK，LINK_A,LINK_B……LINK_N，N为大于1的自然数；\n[0071] 1.1.2)NODE_B关联多条高速道路LINK，LINK_A,LINK_B1,LINK_C1……LINK_N1，N1为大于1的自然数；\n[0072] 1.1.3)LINK_A的长度不大于某一阈值d，例如本处实施中d设置为20米；\n[0073] 1.2)判断是否可以删除LINK_A\n[0074] 如果LINK_B,LINK_C……LINK_N(除LINK_D外)的对应TRACK全部包含在LINK_B1,LINK_C1……LINK_N1的对应TRACK中，则删除LINK_A,合并NODE_A,NODE_B。\n[0075] 2)删除多余NODE点具体步骤为：\n[0076] 在高速公路上不会存在十字路口，电子地图中有许多十字路口甚至N叉路口(N大于3)都是由于立体式的道路不能被识别造成的，删除多余NODE的目的在于恢复立体式道路的形状、修正电子地图不正确的拓扑关系。\n[0077] 查找连接LINK数大于3的NODE A，此处以NODE A连接2条进入LINK，两条退出LINK为例进行说明，如图6，其它情况类似处理。取进入LINK，LINK A，将LINK A对应的TRACK记作为：\n[0078] R1：TRACK 1，TRACK 2，……TRACK N\n[0079] 分别将退出LINK C，退出LINK D对应TRACK记作为：\n[0080] R2：TRACK a，TRACK b，……TRACK m\n[0081] R3：TRACK k，TRACK l，……TRACK S\n[0082] 判断，如果R3是R1的子集，并且R2与R1没有交叉部分，则LINK A与LINK D中间不存在路口，合并LINK A、LINK D为一条LINK。同样，如果R2是R1的子集，并且R3与R1没有交叉部分，则LINK A与LINK C之间是直行的关系，中间不存在路口，合并LINK A、LINK C为一条LINK。\n[0083] NODE连接大于2条退出LINK的情况同样处理，判断某条进入LINK的对应TRACK包含一条退出LINK的对应TRACK，并且该进入LINK的对应TRACK不包含其它退出LINK的对应TRACK，则该条进入LINK与该退出LINK可以合并为一条LINK。\n[0084] 3)调整NODE点位置\n[0085] 由于浮动车轨迹形状损失较大，生成的LINK形状点也较少，LINK靠近NODE点附近的形状较差，往往较大程度的偏离了真实的位置，调整NODE点的位置可以使LINK的形状变得更为合理。\n[0086] 具体方法如下：\n[0087] 依次处理所有连接三条LINK的NODE点，将NODE所连接的3条LINK(经过上述步骤后所有的高速路口为三叉路口)按照与NODE的关系分为进入LINK和退出LINK，此处以图7为例，1条进入LINK，2条退出LINK(2条进入LINK，1条退出LINK同理)，进入LINK：\nLINK A，退出LINK：LINK B，LINK C。取进入LINK A倒数第二个形状点POINT A、NODE点、退出LINK的第二个形状点POINT B组成LINE_A,POINT A、NODE点与LINK C的第二个形状点POINT C组成LINE_B,分析LINE_A,LINE_B的角度变化率η(η为一个比较大的角度，越大表示连续角度变化越剧烈，例如本实施中设置η为120度)，LINE_A的角度变化大于η,LINE_B角度变化小于η，在相应范围内调整NODE点的位置，使LINE_A,LINE_B的角度变化比较平缓。\n[0088] 调整后的效果如图8所示。\n[0089] 4)调整形状点位置\n[0090] 依据高速和匝道上不会存在急转弯或者小范围内连续转弯的特点来分析角度变化率，对LINK上导致出现角度变化率超过阀值的点进行删除，使整条LINK的形状在整体上趋于平滑。具体步骤如下：\n[0091] 4.1)取LINK的前4个形状点，如图9，分别命名为POINT A、POINT B、POINT C、POINT D，将POINT A放入已处理点集合；\n[0092] 4.2)首先，取POINT A，POINT B，POINT C的角度变化率为α，取POINT B，POINT C，POINT D的角度变化率β，取POINT D，POINT E，POINT F的角度变化率为γ，取POINT A，POINT B，POINT D的角度变化率为δ，取POINT A，POINT C，POINT D的角度变化率为ε；\n[0093] 如果|α-β|>θ(θ为阀值，θ越大表示连续角度变化越剧烈，一般设置为一个比较大的角度，本实施中设置为120度)，则认为POINT B或者POINT C是异常点。记α1＝|γ-δ|，记α2＝|γ-ε|；如果α1>α2，并且POINT A与POINT B的距离小于阀值d或者POINT B与POINT C的距离小于阀值d,则认为POINT B是异常点，并将异常点POINT B删除，将POINT C放入已处理点集合；如果α1<α2，并且POINT B与POINT C的距离小于阀值d或者POINT C与POINT D的距离小于阀值d,则认为POINT C是异常点，并将异常点POINT C删除，将POINT B放入已处理点集合；\n[0094] 如果|α-β|<θ，则认为POINT B、POINT C都是正常点，将POINT B、POINT C都放入已处理点集合。\n[0095] 将待处理点位置移到POINT D，如果POINT D不是本条LINK的最后一个形状点，则返回步骤4.1)，否则，将POINT D放入已处理点集合，转入步骤4.3)\n[0096] 4.3)用已处理集合中的点代替原LINK的形状点，结束。\n[0097] 以上所述，仅是用以说明本发明的具体实施案例而已，并非用以限定本发明的可实施范围，举凡本领域熟练技术人员在未脱离本发明所指示的精神与原理下所完成的一切等效改变或修饰，仍应由本发明权利要求的范围所覆盖。