CN113514072B - 一种面向导航数据与大比例尺制图数据的道路匹配方法 - Google Patents

Abstract

本发明公开了一种面向导航数据与大比例尺制图数据的道路匹配方法，以解决导航数据与制图道路数据的匹配问题。该方法从单、双线路的平行特征、相似性判断指标入手，顾及一对多匹配关系，按照构建候选集、获取最优匹配、匹配结果优化的流程，采用样本阈值约束确定道路匹配关系。实现了导航数据与大比例尺制图道路数据之间的匹配，很好地解决了两者由于尺度差异和表达差异引起的匹配困难问题，具备较低的时间复杂度和较高的准确率；该方法提出的以改进DTW距离阈值为匹配的距离约束参数具备稳定性，可扩展到其他数据源的匹配，尤其适用于一对多的匹配场景。保证了数据现势性，为政府决策、调研和应急保障提供了高质量的地图服务。

Description

一种面向导航数据与大比例尺制图数据的道路匹配方法

技术领域

本发明涉及导航电子地图数据领域，尤其涉及一种面向导航数据与大比例尺制图数据的道路匹配方法。

背景技术

基于双线道路多边形的匹配方法对于规范性数据的单线、双线道路匹配有较好的效果，但在导航数据与制图数据的匹配场景下匹配准确率不高，漏匹配和误匹配较多。此外该技术方法需要对道路数据进行拓扑预处理，生成结点－弧段型数据，增加了工作量。基于双线道路多边形的匹配方法过度依赖匹配数据的几何规范性，更适合于同类型不同时期的规范城市道路数据之间的匹配，其提出的双线道路多边形类型不能很好地描述导航数据双线道路特征：导航数据路网中的最小单元——路段被交叉口分割互相独立，故组成双线路的左右路段保持整体趋势平行但首尾不会对齐，且左右路段存在一对多、多对多的组成关系，存在较多不规则多边形，对匹配结果造成较大影响。导航电子地图数据经市场化运作使其数据保持着较高的现势性和一定的规范性。使用导航电子地图道路数据（以下简称导航道路数据）更新制图数据库成为可能，但是如何实现两者在表达形式、空间逻辑描述存在较大差异情况下的精准匹配是关键。

发明内容

本发明的目的就在于为了解决上述问题而提供一种面向导航数据与大比例尺制图数据的道路匹配方法。以解决导航数据与制图道路数据的匹配问题。该方法从单、双线路的平行特征、相似性判断指标入手，顾及一对多匹配关系，按照构建候选集、获取最优匹配、匹配结果优化的流程，采用样本阈值约束确定道路匹配关系。该方法分为双线路匹配、单线路匹配两部分内容。

本发明通过以下技术方案来实现上述目的：

本发明包括双线路匹配和单线路匹配，所述双线路匹配包括以下步骤：

S11：获取候选平行对集：对目标单线进行缓冲区搜索，获取候选路段集

，n为大于1的正整数，判断P _can 中每条路段与该集中其他路段是否平行并记录到n-1行n-1列矩阵

其中

取值为0或1，0表示不平行，1表示平行；

S12：获取最优匹配对：采用向量相似度作为指标从候选平行对集中获取最优匹配对；

S13：匹配结果整理：整理匹配结果，采用多对多描述方式解决路段首尾参差不齐的问题；

所述单线路匹配基于改进DTW（Dynamic Time Warping，动态时间归整）距离进行单线路匹配，包括以下步骤：

S21：获取候选匹配集：对目标单线P进行缓冲区搜索，获取候选路段集path；

S22：获取最优匹配路段：分别计算path中每条路段与P的DTW距离，取DTW距离最小值对应的路段为最优匹配路段；

S23：获取最优匹配集：以最优匹配路段为种子路段，分别从候选匹配集中查询与其起点、终点相接的路段，计算合并后的改进DTW距离，如果超出阈值则停止，如果改进DTW距离在阈值内则将此路段加入最优匹配集，并以合并后路段为新的种子路段继续判断，直到候选匹配集中再无相接路段迭代结束；如果查询出多个相接路段，取改进DTW距离最小的路段合并。

本发明的有益效果在于：

本发明是一种面向导航数据与大比例尺制图数据的道路匹配方法，与现有技术相比，本发明具有如下技术效果：

（1） 功能：本专利提出的一种面向导航数据与大比例尺制图数据的道路匹配方法，从导航数据与制图数据的差异性出发，采用双线路、单线路分别匹配的策略：双线路匹配以平行特征为主获取匹配对，然后首尾扩展整理多对多关系；针对较为普遍的一对多情况，以改进DTW距离为主要约束条件构建单线路匹配方法。实现了导航数据与制图数据的道路匹配，奠定了用导航数据更新制图数据的基础。

（2） 效果：实现了导航数据与大比例尺制图道路数据之间的匹配，很好地解决了两者由于尺度差异和表达差异引起的匹配困难问题，具备较低的时间复杂度和较高的准确率；该方法提出的以改进DTW距离阈值为匹配的距离约束参数具备稳定性，可扩展到其他数据源的匹配，尤其适用于一对多的匹配场景。

（3） 社会效益：应用本发明提出的匹配方法能够保证数据现势性，为政府决策、调研和应急保障提供了高质量的地图服务。

附图说明

图1是本发明的双线路匹配结果整理示意图；a为整理前，b为整理后。

图2是本发明的首尾点位置差异图；a为正位（起点）；b为正位（终点）；c为错位（起点超出）；d为错位（起点缩进）；e为包含。

图3是本发明的新序列对应关系图；a为正位（起点）；b为正位（终点）；c为错位（起点超出）；d为错位（起点缩进）；e为包含。

具体实施方式

下面结合附图对本发明作进一步说明：考虑到双线路较之单线路级等级高、重要性强，应优先保证双线路的配对，故将导航数据根据属性分为双线路与单线路两类，先进行双线路匹配，然后进行单线路与未匹配制图数据的匹配工作。

1）双线路匹配

（1）获取候选平行对集：对目标单线进行缓冲区搜索，获取候选路段集

，n为大于1的正整数，

表示第n条路段，

是n条路段的集合；判断P _can 中每条路段与该集中其他路段是否平行并记录到n-1行n-1列矩阵

是记录

中每条路段与集合中其他路段平行关系的矩阵，其中

表示第i条路段与第j条路段是否平行，

取值为0或1，0表示不平行，1表示平行。根据平行关系记录M _para 将离散的候选路段集P _can 按以下方法整理成平行对集

表示左路段，

表示右路段:

对所有路段进行合并处理构成一条线要素，此线要素必然由多个部件组成；将生成的线要素进行多部件转单部件处理，生成多条连续的线要素；根据平行且不共线原则，将生成的线要素进行两两组合并区分左右关系，构成候选平行对集。

（2）获取最优匹配对：采用向量相似度作为指标从候选平行对集中获取最优匹配对。其计算方法为：目标单线路P其节点从起点到终点依次为pt ₁ ,pt ₂ ,…,pt _n ，节点间长度为pl ₁ ,pl ₂ , …,pl _n-1 ,将平行对py左路段（右路段计算方法相同）合并为连续路段linepy并调整起始方向使之与P方向一致，其节点从起点到终点依次为pyt ₁ ,pyt ₂ , …,pyt _m ,从linepy起点出发走长为pl ₁ 的距离，截取此点记为c，记pt ₁ 到pt ₂ 向量为X, 记pyt ₁ 到c向量为Y,则向量相似度为：

式中：

表示X Y的向量相似度，X,表示pt ₁ 到pt ₂ 向量，Y表示pyt ₁ 到c点的向量；

）表示取X Y向量中长度较小的值，

表示取X Y向量中长度较大的值，

表示X Y向量的点积；

左路段总向量相似度为：

。总向量相似度为左右路段加权和，在本文环境下左右路段同等重要，故其权值均为0.5，则总向量相似度为：

。式中

表示左右路段向量相似度的总和，

、

分别表示左、右路段的向量相似度；

pt _n 表示目标单线P上的节点，命名规则为从起点到终点按顺序计数；

Pl _n-1 表示单线P上节点pt _n-1 与pt _n 间的长度；

Linepy是平行对py经过合并处理后得到的连续路段；

pyt _n 表示目标单线Linepy上的节点，命名规则为从起点到终点按顺序计数。

（3）匹配结果整理：整理匹配结果，采用多对多描述方式解决路段首尾参差不齐的问题。具体方法如下：

A设定目标单线p _old 起点为出发点pt _start ，判定左路段端点py _start 与pt _start 距离是否在阈值（此值根据数据情况设定，记为双线扩展阈值）内，超出阈值则以pt _start 为中心搜索相邻单线，若有且仅有一条相邻单线p _merge 具有双线路匹配对（保证兼并路段同为双线路且不是交叉口）则连接p _merge 构成新单线p _new 并继承其双线匹配对，再以p _new 的非pt _sart 端点为出发点继续判定蔓延，直到满足阈值条件或无兼并对象。当起点左路段处理完毕，判定p _new 对应右路段（为p _old 与p _merge 右路段合并而成）与p _new 起点是否在阈值内，若在阈值内则停止，否则以相同方式继续处理。如图1中（a）所示, p _old 与p _merge 满足条件，将其兼并为p _new ，匹配对兼并为l _new 和r _new ，处理结果如图1（b）所示。

B 以同样的方式处理终点。当兼并操作结束后，多条一对一描述就转化为多对多描述方式。

2）单线路匹配

制图道路数据做过平滑、化简操作，导致即使在匹配程度最好的情况下两者几何位置也会存在差异，从几何特征上看，同一路段存在点密度差别和点位置偏移的普遍特性，在匹配中表现为点的一对多关系。本方法基于改进DTW（动态时间规整）距离进行单线路匹配。

改进DTW距离

首尾点位置差异分析。如图2所示，约定两路段方向为从左到右，并以上方较短路段起点（图2中空心点）终点（图2中实心点）进行命名描述，首尾点差异可以归纳为：①图2（a）正位（起点），指两路段起点对齐；②图2（b）正位（终点），指两路段终点对齐；③图2（c）错位（起点超出），指短路段起点位置在路段延伸趋势方向上超过长路段；④图2（d）错位（起点缩进），指长路段起点位置在路段延伸趋势方向上超过短路段；⑤图2（e）包含，指长路段起点位置在路段延伸趋势方向上超过短路段且长路段终点位置在路段延伸趋势方向上超过短路段， 这种类型是错位（起点缩进）的特殊情况，也是短线匹配长线较常见的情况，故特别列出。

在短线匹配长线时，为取得较为准确的DTW距离，可将超出或者不足部分剪去，使两路段起点终点均为正位，计算此部分的DTW距离。采用“掐头去尾”，两次计算方法计算DTW距离，其主要步骤如下（设有两个二维空间序列

和

,A是长度为n的一系列点序列的集合，

表示A中第n个点，B是长度为m的一系列点序列的集合，

表示B中第m个点）：

步骤2：判断A、B序列起点欧式距离是否大于阈值（此值与数据最大偏移程度相当），排除正常的位置偏移情况；剪去P _match 中起点一对多的部分，即P _match 中不允许存在以下情况：

A序列的第一个点与B序列多个点对应：

B序列的第一个点与A序列多个点对应：

步骤3：判断A、B序列终点欧式距离是否大于阈值，排除正常的位置偏移情况；剪去P _match 中终点一对多的部分，即P _match 中不允许存在以下情况：

A序列的最后一个点与B序列多个点对应：

B序列的最后一个点与A序列多个点对应：

步骤4：根据新P _match 构造新A、B序列，计算DTW距离。针对归纳的首尾点差异五种情况的“剪枝”操作和新序列点位对应关系如图3所示：①图3（a）正位（起点），剪去下方路段终点超出部分；②图3（b）正位（终点），剪去下方路段起点超出部分；③图3（c）错位（起点超出），剪去上方路段起点超出部分和下方路段终点超出部分；④图3（d）错位（起点缩进），剪去上方路段终点超出部分和下方路段起点超出部分；⑤图3（e）包含，剪去下方路段起点和终点超出部分。

改进DTW距离阈值确定。从数据中选取部分匹配样本t组，计算改进DTW距离

，同时考虑路段长度

与DTW距离大小的关系，并根据正太分布3原理，取阈值为DTW距离与长度比值的平均值与3倍标准差之和：

（1）单线路匹配步骤

1）获取候选匹配集。对目标单线P进行缓冲区搜索，获取候选路段集path。

2）获取最优匹配路段。分别计算path中每条路段与P的DTW距离，取DTW距离最小值对应的路段为最优匹配路段。

3）获取最优匹配集。以最优匹配路段为种子路段，分别从候选匹配集中查询与其起点、终点相接的路段，计算合并后的改进DTW距离，如果超出阈值则停止，如果改进DTW距离在阈值内则将此路段加入最优匹配集，并以合并后路段为新的种子路段继续判断，直到候选匹配集中再无相接路段迭代结束。如果查询出多个相接路段，取改进DTW距离最小的路段合并。

以上显示和描述了本发明的基本原理和主要特征及本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。

Claims (3)

1.一种面向导航数据与大比例尺制图数据的道路匹配方法，其特征在于：包括双线路匹配和单线路匹配，所述双线路匹配包括以下步骤：

S11：获取候选平行对集：对目标单线进行缓冲区搜索，获取候选路段集，

判断每条路段与候选路段集中其他路段是否平行并将结果记录到平行关系矩阵中；

S12：获取最优匹配对：采用向量相似度作为指标从候选平行对集中获取最优匹配对；

S13：匹配结果整理：整理匹配结果，采用多对多描述方式解决路段首尾参差不齐的问题；

所述步骤S13具体方法如下：

S131：以目标单线起点为出发点，判定左路段端点与出发点距离是否在阈值内，超出阈值则以出发点为中心搜索相邻单线，若有且仅有一条相邻单线具有双线路匹配对则连接构成新单线并继承其双线匹配对，再以新单线的端点为出发点继续判定蔓延，直到满足阈值条件或无兼并对象；当起点左路段处理完毕，判定新单线对应右路段端点与其起点是否在阈值内，若在阈值内则停止，否则以相同方式继续处理；

S132：以所述步骤S131的方式处理终点，当兼并操作结束后，多条一对一描述就转化为多对多描述方式；

所述单线路匹配基于改进DTW距离进行单线路匹配，包括以下步骤：

S21：获取候选匹配集：对目标单线进行缓冲区搜索，获取候选路段集；

S22：获取最优匹配路段：分别计算候选路段集中每条路段与目标单线的DTW距离，标记DTW距离最小值对应的路段为最优匹配路段；

S23：获取最优匹配集：以最优匹配路段为种子路段，分别从候选匹配集中查询与其起点、终点相接的路段，计算合并后的改进DTW距离，如果超出阈值则停止，如果改进DTW距离在阈值内则将此路段加入最优匹配集，并以合并后路段为新的种子路段继续判断，直到候选匹配集中再无相接路段迭代结束；如果查询出多个相接路段，取改进DTW距离最小的路段合并；

所述改进DTW距离具体为：设有两个二维空间序列

和

，A是长度为n的一系列点序列的集合，

表示A中第n个点，B是长度为m的一系列点序列的集合，

表示B中第m个点：

步骤1：使用常规DTW计算方法取得最优规整路径，获得A、B序列点位对应关系：

,

表示A序列第i个点与B序列第j个点是对应关系；

步骤2：判断A、B序列起点欧式距离是否大于阈值，排除正常的位置偏移情况；剪去P _match 中起点一对多的部分，即P _match 中不允许存在以下情况：

A序列的第一个点与B序列多个点对应：

B序列的第一个点与A序列多个点对应：

步骤3：判断A、B序列终点欧式距离是否大于阈值，排除正常的位置偏移情况；剪去P _match 中终点一对多的部分，即P _match 中不允许存在以下情况：

A序列的最后一个点与B序列多个点对应：

B序列的最后一个点与A序列多个点对应：

步骤4：根据新P _match 构造新A、B序列，计算DTW距离。

2.根据权利要求1所述的面向导航数据与大比例尺制图数据的道路匹配方法，其特征在于：所述步骤S11根据平行关系记录矩阵将离散的候选路段集按以下方法整理成平行对集：

S111：对所有路段进行合并处理构成一条线要素，此线要素必然由多个部件组成；

S112 ：将S111中生成的线要素进行多部件转单部件处理，生成多条连续的线要素；

S113：根据平行且不共线原则，将S112中生成的线要素进行两两组合并区分左右关系，构成候选平行对集。

3.根据权利要求1所述的面向导航数据与大比例尺制图数据的道路匹配方法，其特征在于：所述步骤S12计算方法为：使用向量相似度衡量平行对集中路段与目标单线的匹配程度，总相似度为左右路段之和，以此获取最优匹配对。

Images