一种自动发现新建桥梁的方法和装置

摘要

本发明提供了一种自动发现新建桥梁的方法和装置，其中方法包括：获取各用户的GPS轨迹，并将每条GPS轨迹与地图中的路段进行匹配；若一条GPS轨迹中存在连续N个以上的GPS点都无法匹配到路段上，则所述连续N个以上的GPS点组成未匹配到路段上的轨迹，所述N为预设正整数；从未匹配到路段上的轨迹中确定水域内的轨迹；针对每片水域分别执行：将水域内的轨迹进行聚类得到各轨迹集合；确定包含轨迹数量大于或等于预设阈值Th4的轨迹集合指示新建桥梁。本发明能够摆脱对情报收集的依赖，降低人力成本。

说明书

【技术领域】

本发明涉及计算机应用技术领域，特别涉及一种自动发现新建桥梁的方 法和装置。

【背景技术】

随着移动技术的迅速发展，近些年地图应用逐渐成为人们获取出行信息 的主要手段，通过地图应用用户能够进行定位、查询公交、查询路线等，地 图应用的覆盖面和准确程度主要依靠地图数据，提供更为精准和充实的地图 数据库并及时更新是地图应用一直致力解决的问题。

在地图应用中常常会存在这样的情况，即某桥梁新建后，在地图上无法 显示也无法导航。目前针对这种情况主要采用两种方法：一种是通过对用户 反馈的收集，例如很多用户反馈在某城市新开通了一个桥梁而在地图上没有 显示也没有导航。另一种是通过新闻媒体收集情报，比如新闻中报道某城市 搭桥开通剪彩，则确定地图数据中需要更新该新建桥梁的数据。然而上述两 种方法都必须依赖于情报的收集，需要比较大的人力投入。

【发明内容】

有鉴于此，本发明提供了一种自动发现新建桥梁的方法和装置，以便于 摆脱对情报收集的依赖，降低人力成本。

具体技术方案如下：

一种自动发现新建桥梁的方法，该方法包括：

S1、获取各用户的GPS轨迹，并将每条GPS轨迹与地图中的路段进行匹配；

S2、若一条GPS轨迹中存在连续N个以上的GPS点都无法匹配到路段上， 则所述连续N个以上的GPS点组成未匹配到路段上的轨迹，所述N为预设正整 数，从未匹配到路段上的轨迹中确定水域内的轨迹；

S3、针对每片水域分别执行：将水域内的轨迹进行聚类得到各轨迹集合；

S4、确定包含轨迹数量大于或等于预设阈值Th4的轨迹集合指示新建桥梁。

根据本发明一优选实时方式，步骤S2中所述从未匹配到路段上的轨迹中确 定水域内的轨迹具体包括：

针对每条未匹配到路段上的轨迹执行：确定当前轨迹中属于水域范围的 GPS点，判断当前轨迹中属于水域范围的GPS点的个数是否大于或等于预设的 阈值Th1且轨迹平均速度是否大于或等于预设阈值Th2，如果是，则确定当前 轨迹为水域内的轨迹。

根据本发明一优选实时方式，当前轨迹的轨迹平均速度为：当前轨迹中每 个GPS点的速度平均值，或者，当前轨迹中相邻GPS点的球面距离之和除以当 前轨迹中最末GPS点与最初GPS点的时间差所得到的值。

根据本发明一优选实时方式，在确定GPS点是否属于水域范围时，具体执 行：

若地图数据中某水域范围对应的封闭图形的端点P_i构成端点集合P，P中端 点个数为n，当前GPS点为P_t，为连接P_t和P_i的向量，为向量到的 夹角，若为±2π，则确定当前GPS点属于所述某水域范围。

根据本发明一优选实时方式，在所述步骤S3中仅针对包含轨迹数量大于或 等于预设阈值Th3的水域内的轨迹进行聚类。

根据本发明一优选实时方式，在对水域内的轨迹进行聚类时，将相似的轨 迹聚为一类，其中判断两个轨迹是否相似的方法为：

若轨迹B上的GPS点P_Bi到轨迹A上的各GPS点之间的距离中最小距离小 于预设距离阈值，则确定GPS点P_Bi在轨迹A的周围，若轨迹B中预设比例以上 的GPS点在轨迹A的周围，则确定轨迹A和轨迹B相似。

根据本发明一优选实时方式，在所述步骤S4中还包括：输出新建桥梁的信 息；

所述新建桥梁的信息包括：所属的水域信息和指示新建桥梁的轨迹集合中 的GPS点序列。

一种自动发现新建桥梁的装置，该装置包括：

轨迹获取单元，用于获取各用户的GPS轨迹；

地图匹配单元，用于将每条GPS轨迹与地图中的路段进行匹配；

水域识别单元，用于从未匹配到路段上的轨迹中确定水域内的轨迹，其中 若一条GPS轨迹中存在连续N个以上的GPS点都无法匹配到路段上，则所述连 续N个以上的GPS点组成未匹配到路段上的轨迹，所述N为预设正整数；

轨迹聚类单元，用于针对每片水域分别执行：将水域内的轨迹进行聚类得 到各轨迹集合；

桥梁发现单元，用于确定包含轨迹数量大于或等于预设阈值Th4的轨迹集 合指示新建桥梁。

根据本发明一优选实时方式，所述水域识别单元在从未匹配到路段上的轨 迹中确定水域内的轨迹时，具体针对每条未匹配到路段上的轨迹执行：判断当 前轨迹中属于水域范围的GPS点的个数是否大于或等于预设的阈值Th1且轨迹 平均速度是否大于或等于预设阈值Th2，如果是，则确定当前轨迹为水域内的轨 迹。

根据本发明一优选实时方式，当前轨迹的轨迹平均速度为：当前轨迹中每 个GPS点的速度平均值，或者，当前轨迹中相邻GPS点的球面距离之和除以当 前轨迹中最末GPS点与最初GPS点的时间差所得到的值。

根据本发明一优选实时方式，所述水域识别单元在确定GPS点是否属于水 域范围时，具体执行：

若地图数据中某水域范围对应的封闭图形的端点P_i构成端点集合P，P中端 点个数为n，当前GPS点为P_t，为连接P_t和P_i的向量，为向量到的 夹角，若为±2π，则确定当前GPS点属于所述某水域范围。

根据本发明一优选实时方式，所述轨迹聚类单元仅针对包含轨迹数量大于 或等于预设阈值Th3的水域内的轨迹进行聚类。

根据本发明一优选实时方式，所述轨迹聚类单元在对水域内的轨迹进行聚 类时，将相似的轨迹聚为一类，其中判断两个轨迹是否相似的方法为：

若轨迹B上的GPS点P_Bi到轨迹A上的各GPS点之间的距离中最小距离小 于预设距离阈值，则确定GPS点P_Bi在轨迹A的周围，若轨迹B中预设比例以上 的GPS点在轨迹A的周围，则确定轨迹A和轨迹B相似。

根据本发明一优选实时方式，所述桥梁发现单元，还用于输出新建桥梁 的信息，所述新建桥梁的信息包括：所属的水域信息和指示新建桥梁的轨迹 集合中的GPS点序列。

由以上技术方案可以看出，本发明利用GPS数据就能够自动发现新建桥 梁，GPS数据是很多移动设备本身就会上报的数据，无需额外耗费人力去进 行信息反馈或情报收集，降低了人力成本，也摆脱了对情报收集的依赖。

【附图说明】

图1为本发明实施例一提供的自动发现新建桥梁的方法流程图；

图2为本发明实施例一提供的地图匹配结果示意图；

图3为本发明实施例一提供的地图匹配结果的细节图；

图4为本发明实施例一提供的水域内GPS点的示意图；

图5为本发明实施例二提供的自动发现新建桥梁的装置结构图。

【具体实施方式】

为了使本发明的目的、技术方案和优点更加清楚，下面结合附图和具体 实施例对本发明进行详细描述。

目前很多移动设备都能够获得GPS数据并上传到数据中心，比如出租车 的GPS设备上报GPS数据至出租车调度中心，以便出租车调度中心进行调 度管理和安全监控，再比如自驾用户的导航设备上传GPS数据至服务中心获 得导航服务等车联网服务。这些GPS数据是无需额外投入人力获取的，本发 明就是通过这些GPS数据来进行新建桥梁的自动发现。下面通过实施例一对 本发明提供的方法进行详细描述。

实施例一、

图1为本发明实施例一提供的自动发现新建桥梁的方法流程图，如图1 所示，该方法可以具体包括以下步骤：

步骤101：获取各用户的GPS轨迹，并将每条GPS轨迹与地图中的路段 进行匹配。

在本发明实施例中直接利用已有的各用户上传的GPS数据，GPS数据被 划分成GPS轨迹，每条GPS轨迹由同一个用户的按时间排序的多个GPS点 组成，每个GPS点的信息包含用户ID、时间和位置信息，也就是说，一条 GPS轨迹包含一个用户在一段时间内的GPS数据，其中一条GPS轨迹内相 邻GPS点的时间间隔通常小于或等于预设时间间隔，例如小于1或等于分钟。

划分GPS轨迹可以采用现有技术中的多种方式，在此列举一种：首先获 取同一用户的所有GPS数据，并将各GPS点按照时间进行排序；比较相邻 两个GPS点A和B之间的时间间隔，若时间间隔大于一定的时间间隔 Thr_time，则以A作为当前GPS轨迹的终点，B作为后一条GPS轨迹的起点； 遍历并比较完同一用户GPS数据的所有相邻GPS点，就能够得到同一用户 的各GPS轨迹。其中Thr_time的范围通常选取在3至10分钟，优选5分钟。

在将GPS轨迹与地图中的路段进行匹配时，是将GPS轨迹中的各GPS 点投影到连续的路段上，地图匹配是已有技术，在此仅列举其中一种匹配方 法：将每个GPS点分别投影到若干个候选路段上，而后将相邻GPS点的候 选路段分别进行组合，选择组合路线中长度最短的组合作为匹配的路段。在 确定GPS的候选路段时，确定GPS点周围一定范围内的所有路段，比如500 米范围内的所有路段，逐个计算GPS点到确定出的每条路段的最短距离，将 最短距离小于设定阈值例如50米的路段作为该GPS点的候选路段。

匹配结果如图2所示，图2中线段表示路段，实心的圆点表示GPS点， 空心的圆点表示GPS点投影到路段上的点，即在路段上的匹配点，两点之间 的虚线表示GPS点与匹配点之间的投影关系。进行匹配获得的地图匹配结果 中包括：GPS点的信息（例如时间和位置信息）、路段ID、GPS点到对应匹 配点的距离（可以称为匹配距离误差），其对应的细节图如图3所示。

步骤102：若一条GPS轨迹中存在连续N个以上的GPS点都无法匹配 到路段上，则该连续N个GPS点组成未匹配到路段上的轨迹，其中N为预 设的正整数。

在地图匹配的过程中，会存在有些GPS点由于周围一定范围内都没有路 段，因此无法匹配到路段上。若某条GPS轨迹中存在诸如连续5个以上的 GPS点都无法匹配到路段上，则这连续5个以上的无法匹配到路段上的GPS 点就组成未匹配到路段上的轨迹，这部分轨迹由可能是在新建桥梁上，因此 继续进行后续分析。

步骤103：针对每条未匹配到路段上的轨迹执行：确定当前轨迹中属于 水域范围的GPS点，判断当前轨迹中属于水域范围的GPS点的个数是否大 于或等于预设的阈值Th1且轨迹平均速度是否大于或等于预设阈值Th2，如 果是，则确定当前轨迹为水域内的轨迹。

在确定当前轨迹中属于水域范围的GPS点时，实际上就是判断轨迹中的 GPS点是否属于一个封闭的图形，如图4中所示，如果是，则该GPS点就属 于水域范围，然后统计当前轨迹中属于水域范围的GPS点的个数。

在判断GPS点是否属于一个封闭的图形时，可以采用现有技术中任一方 式，在此仅列举其中一种：若地图数据中某封闭的图形的端点P_i构成端点集 合P，即P={P₁,P₂,…,P_n}，若当前GPS点为P_t，为连接P_t和P_i的向量，为向量到的夹角，若为±2π，则确定当前GPS点在该封闭的图形 内部，属于该封闭的图形。

上述轨迹平均速度的确定方法可以采用以下两种：

第一种方法：计算当前轨迹中每个GPS点的速度平均值，GPS点的速度 可以采用相邻GPS点的位移差和时间差来计算。

第二种方法：计算当前轨迹中相邻GPS点的球面距离（地球表面上的球 面距离）之和除以当前轨迹中最末GPS点与最初GPS点的时间差所得到的 值。

如果当前轨迹中属于水域范围内的GPS点足够多，例如Th1取5，并且 当前轨迹平均速度足够大，例如Th2取30km/h，则确定当前轨迹为水域内的 轨迹。

在执行完步骤103之后，就得到所有水域内的轨迹，记录水域内的轨迹 的水域ID和轨迹列表，在轨迹列表中记录该水域内的轨迹的GPS点、每个 GPS的信息包含轨迹ID、位置信息和时间。

步骤104：针对每片水域分别执行：将水域内的轨迹进行聚类得到各轨 迹集合。

在聚类时，可以仅对包含轨迹数量大于或等于预设阈值Th3的水域进行 聚类，而对于包含轨迹数量较少的，例如Th3取10时，包含低于10条轨迹 的水域鉴于一些偶然性因素和准确性较低的问题，则不进行聚类和后续判别。

对轨迹进行聚类可以采用多种方式，在此举一个聚类方法的例子：基于 轨迹之间的相似性对轨迹进行聚类，即将相似的轨迹聚为一类。在确定两个 轨迹是否相似时，可以采用这样的方法，若轨迹B上的某GPS点P_Bi到轨迹A 上的各GPS点之间的距离中，最小距离小于预设阈值，例如50米，则可以 认为该GPS点P_Bi在轨迹A的周围，如果轨迹B中预设比例以上的GPS点都 在轨迹A的周围，则认为轨迹A和轨迹B相似，其中预设比例可以取60% 以上的值，优选80%。

步骤105：若轨迹集合中的轨迹数量大于或等于预设阈值Th4（例如10）， 则该轨迹集合指示新建桥梁。

可以输出新建桥梁的信息，说明这些新建桥梁需要进行测绘并更新地图 数据。输出的新建桥梁的信息可以包含：所属的水域信息和指示新建桥梁的 轨迹集合中的GPS点序列，其中水域信息可以是水域的名称或具体位置等。 新建桥梁信息可以以文本的形式输出，或者以方便在GIS工具（例如MapInfo 或ArcGIS等工具）中查看的格式（例如MID或MIF格式）输出。

以上是对本发明所提供的方法进行的详细描述，下面结合实施例二对本 发明提供的装置进行详细描述。

实施例二、

图5为本发明实施例二提供的自动发现新建桥梁的装置结构图，如图5 所示，该装置可以包括：轨迹获取单元01、地图匹配单元02、水域识别单元 03、轨迹聚类单元04和桥梁发现单元05。

首先轨迹获取单元01获取各用户的GPS轨迹，直接利用已有的各用户上传 的GPS数据，将GPS数据划分成轨迹，每条GPS轨迹由同一个用户的按时间 排序的多个GPS点组成，每个GPS点的信息包含用户ID、时间和位置信息， 也就是说，一条GPS轨迹包含一个用户在一段时间内的GPS数据，其中一条 GPS轨迹内相邻GPS点的时间间隔通常小于或等于预设时间间隔，例如小于1 或等于分钟。

轨迹获取单元01划分GPS轨迹可以采用现有技术中的多种方式，在此列举 一种：首先获取同一用户的所有GPS数据，并将各GPS点按照时间进行排序； 比较相邻两个GPS点A和B之间的时间间隔，若时间间隔大于一定的时间间隔 Thr_time，则以A作为当前GPS轨迹的终点，B作为后一条GPS轨迹的起点； 遍历并比较完同一用户GPS数据的所有相邻GPS点，就能够得到同一用户的各 GPS轨迹。其中Thr_time的范围通常选取在3至10分钟，优选5分钟。

然后地图匹配单元02将每条GPS轨迹与地图中的路段进行匹配，即将GPS 轨迹中的各GPS点投影到连续的路段上，地图匹配是已有技术，在此仅列举其 中一种匹配方法：将每个GPS点分别投影到若干个候选路段上，而后将相邻GPS 点的候选路段分别进行组合，选择组合路线中长度最短的组合作为匹配的路段。 在确定GPS的候选路段时，确定GPS点周围一定范围内的所有路段，比如500 米范围内的所有路段，逐个计算GPS点到确定出的每条路段的最短距离，将最 短距离小于设定阈值例如50米的路段作为该GPS点的候选路段。

水域识别单元03从未匹配到路段上的轨迹中确定水域内的轨迹，其中若一 条GPS轨迹中存在连续N个以上的GPS点都无法匹配到路段上，则连续N个 以上的GPS点组成未匹配到路段上的轨迹，N为预设正整数；

水域识别单元03在从未匹配到路段上的轨迹中确定水域内的轨迹时，具体 针对每条未匹配到路段上的轨迹执行：判断当前轨迹中属于水域范围的GPS点 的个数是否大于或等于预设的阈值Th1且轨迹平均速度是否大于或等于预设阈 值Th2，如果是，则确定当前轨迹为水域内的轨迹。

其中当前轨迹的轨迹平均速度可以为但不限于以下两种：当前轨迹中每个 GPS点的速度平均值，或者，当前轨迹中相邻GPS点的球面距离之和除以当前 轨迹中最末GPS点与最初GPS点的时间差所得到的值。

更具体地，水域识别单元03在确定GPS点是否属于水域范围时，可以具体 采用如下方式：若地图数据中某水域范围对应的封闭图形的端点P_i构成端点集合 P，P中端点个数为n，当前GPS点为P_t，为连接P_t和P_i的向量，为向量到的夹角，若为±2π，则确定当前GPS点属于某水域范围。

然后轨迹聚类单元04针对每片水域分别执行：将水域内的轨迹进行聚类得 到各轨迹集合。轨迹聚类单元04在对水域内的轨迹进行聚类时，将相似的轨迹 聚为一类，其中判断两个轨迹是否相似的方法为：若轨迹B上的GPS点P_Bi到轨 迹A上的各GPS点之间的距离中最小距离小于预设距离阈值，则确定GPS点P_Bi在轨迹A的周围，若轨迹B中预设比例以上的GPS点在轨迹A的周围，则确 定轨迹A和轨迹B相似。

优选地，轨迹聚类单元04可以仅针对包含轨迹数量大于或等于预设阈值 Th3的水域内的轨迹进行聚类，而对于包含轨迹数量较少的，例如Th3取10时， 包含低于10条轨迹的水域鉴于一些偶然性因素和准确性较低的问题，则不进行 聚类和后续判别。

最后桥梁发现单元05确定包含轨迹数量大于或等于预设阈值Th4的轨迹集 合指示新建桥梁。还可以进一步输出新建桥梁的信息，新建桥梁的信息包括： 所属的水域信息和指示新建桥梁的轨迹集合中的GPS点序列，其中水域信息可 以是水域的名称或具体位置等。新建桥梁信息可以以文本的形式输出，或者以 方便在GIS工具（例如MapInfo或ArcGIS等工具）中查看的格式（例如MID 或MIF格式）输出。

在本发明所提供的几个实施例中，应该理解到，所揭露的装置和方法， 可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的， 例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外 的划分方式。另外，在本发明各个实施例中的各功能单元可以集成在一个处 理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集 成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用 硬件加软件功能单元的形式实现。

上述以软件功能单元的形式实现的集成的单元，可以存储在一个计算机 可读取存储介质中。上述软件功能单元存储在一个存储介质中，包括若干指 令用以使得一台计算机设备（可以是个人计算机，服务器，或者网络设备等） 或处理器（processor）执行本发明各个实施例所述方法的部分步骤。而前述 的存储介质包括：U盘、移动硬盘、只读存储器（Read-Only Memory，ROM）、 随机存取存储器（Random Access Memory，RAM）、磁碟或者光盘等各种可 以存储程序代码的介质。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本 发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在 本发明保护的范围之内。