CN114664104B - 一种路网匹配方法和装置 - Google Patents

Abstract

本申请提供了一种路网匹配方法和装置，涉及地图领域。该方法包括：获取第一位置信息；基于第一位置信息，以及预存的映射关系，确定位于终端附近的一个或多个候选路段；基于候选路段和终端在第一时间窗内的轨迹，确定终端在当前时间点所处的目标路段；基于终端在当前时间点所处的目标路段，对轨迹中的第一位置信息进行纠偏，得到纠偏后的轨迹。基于本申请提供的路网匹配方法，可以实时地对移动轨迹进行纠偏，提高移动轨迹的准确度。并且，由于预存了区域与路段的映射关系，可以直接将位置信息转换到区域，进而查找出该位置附近的候选路段，不必在线地根据终端的位置信息实时计算候选路段，故可以减少计算量，提高实时纠偏的效率。

Description

一种路网匹配方法和装置

技术领域

本申请涉及地图领域，并且更具体地，涉及一种路网匹配方法和装置。

背景技术

随着社会的不断发展、城市的不断扩张，道路情况也变得越来越复杂，导航成为越来越多的用户出行时会使用到的功能。在导航的场景中，用户对移动轨迹的精度要求是非常高的。另外，在一些场景中，对移动轨迹的要求也是极其严苛的，如交通数字孪生、商用车的轨迹还原等。目前较为常用的定位数据主要来源于全球定位系统(global positioningsystem，GPS)数据。

然而，在实际应用中，GPS的的定位误差较大，而实际道路情况越来越复杂，这使得基于GPS数据所确定的移动轨迹与地图道路存在偏差，移动轨迹准确性不高。

发明内容

本申请提供了一种路网匹配方法和装置，以期能够实时对终端的移动轨迹进行纠偏，提高移动轨迹的准确性。

第一方面，本申请提供了一种路网匹配方法，应用于路网匹配装置中，该方法包括：获取第一位置信息，第一位置信息用于指示终端在当前时间点的位置；基于第一位置信息，以及预存的映射关系，确定位于终端附近的一个或多个候选路段，映射关系用于指示至少一个区域中每个区域附近的一个或多个路段；基于候选路段和终端在第一时间窗内的轨迹，确定终端在当前时间点所处的目标路段；其中，第一时间窗的结束时间点为当前时间点，且时长为第一预设值；基于终端在当前时间点所处的目标路段，对轨迹中的第一位置信息进行纠偏，得到纠偏后的轨迹。

第二方面，本申请提供了一种路网匹配装置，包括获取模块和处理模块；其中，获取模块用于获取第一位置信息，第一位置信息用于指示终端在当前时间点的位置；处理模块，用于基于第一位置信息，以及预存的映射关系，确定位于终端附近的一个或多个候选路段，映射关系用于指示至少一个区域中每个区域附近的一个或多个路段；基于候选路段和终端在第一时间窗内的轨迹，确定终端在当前时间点所处的目标路段；其中，第一时间窗的结束时间点为当前时间点，且时长为第一预设值；基于终端在当前时间点所处的目标路段，对轨迹中的第一位置信息进行纠偏，得到纠偏后的轨迹。

第三方面，本申请提供了一种路网匹配装置，包括处理器，处理器用于执行计算机程序，以实现第一方面所述的方法。

第四方面，本申请提供了一种计算机程序产品，该计算机程序产品包括：计算机程序(也可以称为代码，或指令)，当该计算机程序被运行时，使得计算机执行第一方面所述的方法。

第五方面，本申请提供了一种计算机可读存储介质，包括计算机程序，当该计算机程序在计算机上运行时，使得计算机执行第一方面所述的方法。

在本申请实施例中，基于终端的位置信息以及预存的区域与路段的映射关系，确定终端所处的区域，进而查找出终端可能位于的候选路段，再根据终端之前的移动轨迹，从这些候选路段中确定终端当前所处的路段，最后基于终端当前所处的路段对终端的移动轨迹进行纠偏，得到纠偏后的轨迹。通过将上一时间点的移动轨迹作为当前时间点的历史轨迹，进而对当前时间点的移动轨迹进行纠偏，纠偏后的移动轨迹又可以成为下一时间点的历史轨迹，如此迭代，可以实时地对移动轨迹进行纠偏，提高移动轨迹的准确度。并且，由于预存了区域与路段的映射关系，可以直接将位置信息转换到区域，进而查找出该位置附近的候选路段，不必在线地根据终端的位置信息实时计算候选路段，故可以减少计算量，提高实时纠偏的效率。

附图说明

图1是本申请实施例提供的路网匹配方法的场景示意图；

图2是本申请实施例提供的路网匹配方法的示意性流程图；

图3是判断路段与Geohash区域是否存在交点的方法示意图；

图4是判断第一位置信息正常或者异常的方法示意图；

图5本申请实施例提供的路网匹配方法的另一示意性流程图；

图6是本申请实施例提供的路网匹配装置的示意性框图；

图7是本申请实施例提供的路网匹配装置的另一示意性框图。

具体实施方式

使本申请实施例的目的、技术方案和优点更加清楚，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述。显然，所描述的实施例是本申请一部分实施例，而不是全部的实施例。

因此，以下对在附图中提供的本申请的实施例的详细描述并非旨在限制要求保护的本申请的范围，而是仅仅表示本申请的选定实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

在本申请实施例中，术语“第一”、“第二”等是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。此外，术语“包括”以及任何变形，意图在于覆盖不排他的包含。应理解，术语“连接”应做广义理解。例如，可以是固定连接，或者可拆卸连接；也可以是机械连接，或者通信连接。对于本领域普通技术人员而言，可以根据具体情况理解上述术语在本申请中的具体含义。

下面将结合附图，对本申请中的技术方案进行描述。

图1是本申请实施例提供的路网匹配方法的场景示意图。如图1所示，该场景示出了终端110和服务器120。其中，终端110是可以通过GPS或者基站信号等途径获取自身位置信息的设备，例如可以是如图1所示的手机，也可以是平板电脑、笔记本电脑或智能车载终端、车辆等设备，本申请对此不作任何限定。服务器120为具有数据收发和数据处理功能的设备。服务器120可以与终端110通过网络连接，从终端110接收位置信息，并计算得到终端110的移动轨迹。

如前所述，GPS的定位误差较大，导致移动轨迹的准确性不高，不能满足诸多场景的需求。鉴于此，本申请提供一种路网匹配方法，基于终端的位置信息以及预存的区域与路段的映射关系，确定终端所处的区域，进而查找出终端可能位于的候选路段，再根据终端之前的移动轨迹，从这些候选路段中确定终端当前所处的路段，最后基于终端当前所处的路段对终端的移动轨迹进行纠偏，得到纠偏后的轨迹。通过将上一时间点的移动轨迹作为当前时间点的历史轨迹，进而对当前时间点的移动轨迹进行纠偏，纠偏后的移动轨迹又可以成为下一时间点的历史轨迹，如此迭代，可以实时地对移动轨迹进行纠偏，提高移动轨迹的准确度。并且，由于预存了区域与路段的映射关系，可以直接将位置信息转换到区域，进而查找出该位置附近的候选路段，不必在线地根据终端的位置信息实时计算候选路段，故可以减少计算量，提高实时纠偏的效率。

图2是本申请实施例提供的路网匹配方法的示意性流程图。如图1所示，该方法200可以包括步骤210至240，可以由路网匹配装置来执行，例如可以是图1中的服务器120。下面对方法200中的各个步骤做详细说明。

在步骤210中，获取第一位置信息，该第一位置信息用于指示终端在当前时间点的位置。

该第一位置信息可以是该终端的GPS数据。可以理解，路网匹配装置可以实时地从导航系统、基站等获取到终端在各个时间点的GPS数据。每个GPS数据都可用于指示终端在各个时间点的位置。本文中为了便于区分和说明，将用于指示终端在当前时间点的位置的位置信息记为第一位置信息。

由于GPS数据的误差较大，路网匹配设备还可以对获取到的GPS数据进行优化，以得到优化后的GPS数据作为位置信息。换言之，上述第一位置信息也可以是对当前时间点的GPS数据进行优化后得到的数据。

其中，对GPS数据的优化可以是基于上一时间点的移动轨迹来优化，例如，可以通过平滑处理、卡尔曼(Kalman)滤波等来对GPS数据进行优化。由于下文中将结合具体的算法来对优化过程做详细说明，此处暂且不作详述。

可以理解的是，由于优化过程需要结合上一时间点的移动轨迹，故，若该第一位置信息是对该终端进行路网匹配时获取到的第一个位置信息，则该第一位置信息可以是终端的GPS数据；若该第一位置信息不是对该终端进行路网匹配时获取到的第一个位置信息，则该第一位置信息可以是对GPS数据优化后的数据。

在步骤220中，基于第一位置信息，以及预存的映射关系，确定位于终端附近的一个或多个候选路段。

其中，该映射关系可用于指示至少一个区域中每个区域附近的一个或多个路段。也就是说，可以将各个区域附近的路段预先确定出来，作为映射关系来存储。在获取到第一位置信息后，便可基于该第一位置信息，确定其所对应的区域，进而在该映射关系中查找该区域附近的路段。该区域附近的路段也即该终端附近的路段，或者说，该终端可能位于的路段。下文中为方便区分和说明，将该终端可能位于的路段记为候选路段。可以理解的是，随着道路环境越来越复杂，终端所处的位置附近可能存在一个或多个路段，故上述候选路段可能包括一个或多个路段。

这里，区域可以是预先划定的，每个区域可以对应一个区域标识，每个区域标识可用于唯一地确定一个区域。每个区域的区域标识可以是基于所标识的区域的位置进行编码得到的。

作为示例而非限定，该区域可以是Geohash区域，区域标识可以是Geohash值。

需要说明的是，Geohash是一种位置编码方法，可以将二维的经纬度数据编码成一个字符串。

地球的经度范围是东经180度到西经180度，维度范围是北纬90度到南纬90度。以本初子午线为界，设定西经为负，东经为正；以赤道为界，设定南纬为负，北纬为正。则地球的经度范围为-180度到180度，纬度范围为-90度到90度。将经度范围-180度到0度用二进制数0代表，经度范围0度到180度用二进制数1代表，将纬度范围-90度到0度用二进制数0代表，纬度范围0度到90度用二进制数1代表，可以将地球分为00、01、10、11四个区域。

基于同样的方法，可以将每个区域继续分为更小的四个区域。例如在11这个区域中，将经度范围0度到90度用二进制数0代表，经度范围90度到180度用二进制数1代表，纬度范围0度到45度用二进制数0代表，纬度范围45度到90度用二进制数1代表，可以将11这个区域继续分为1100、1101、1110、1111四个更小的区域。当然也可以基于同样的方法将每个区域继续划分下去，划分的区域越精细，区域的编码位数就越多，此后不再赘述。

接下来用Base32编码的方法，将上述得到的用“0”、“1”表示的二进制数进一步编码，转换为用0到9这10个数字以及26个英文字母中去掉“a”、“i”、“l”、“o”这4个字母以外的剩余22个字母，总共32个字符表示的编码。最终得到的就是该区域的Geohash值。

路段可以基于路网数据而确定。该路网数据例如可以是从导航系统获取，也可以通过测绘获取，等等，本申请对此不作限定。

基于路网数据可以得到各个路段的信息。为了便于区分，每个路段可对应一个路段标识。每个路段标识用于唯一地确定一个路段。

示例性地，路段可以为链路(link)型或者导航数据标准(navigation datastandard，NDS)型。其中，link型路段的路边标识对路段的位置做了标识，包括该路段的名称和该路段以经纬度表示的函数；NDS型路段的路段标识对路段的车道做了进一步地划分，包括该路段的名称、该路段各个车道的标识和该路段以经纬度表示的函数。

基于上文对区域标识和路段标识的列举，上述的映射关系的一种可能的形式是，至少一个Geohash值与至少一个路段标识的对应关系。

下面结合图3详细说明生成该映射关系的过程。

可选地，建立上述映射关系的步骤包括：在路网数据中的每个路段中确定多个位置点；确定多个位置点中每个位置点所对应的区域与Geohash值中的每个Geohash值所标识的Geohash区域是否存在交点，其中，每个位置点所对应的区域是以每个位置点为圆心，以第二预设值为半径得到的圆形区域；基于存在交点的位置点和Geohash区域，生成映射关系。

一示例，如图3中的(a)所示，在道路1中每隔25米确定一个位置点，以每个位置点为圆心，以50米为半径，可以得到与每个位置点对应的圆形区域，与每个位置点对应的圆形区域即每个位置点所对应的区域。道路1中每个位置点所对应的区域与Geohash值分别为wx4g0ec1和wx4g0ec3的Geohash区域存在交点。因此可以得到道路1和Geohash值为wx4g0ec1的Geohash区域的映射关系，以及道路1和Geohash值为wx4g0ec3的Geohash区域的映射关系。

另一示例，如图3中的(b)所示，在盘道1中每隔25米确定一个位置点，以每个位置点为圆心，以50米为半径得到的圆形区域即每个位置点所对应的区域。盘道1中每个位置点所对应的区域与Geohash值分别为wx4g0ec0、wx4g0ec2和wx4g0ec3的Geohash区域存在交点。因此可以得到盘道1和Geohash值为wx4g0ec0的Geohash区域的映射关系，以及盘道1和Geohash值为wx4g0ec2的Geohash区域的映射关系，以及盘道1和Geohash值为wx4g0ec3的Geohash区域的映射关系。

由上文示例，可以得到Geohash值为wx4g0ec1的Geohash区域与道路1、道路3和道路4的映射关系。路网匹配装置可以生成Geohash值为wx4g0ec1的Geohash区域与道路1、道路3和道路4的映射关系。

应理解，此处的25米间隔以及50米半径仅作示例，间隔与半径也可以为其他长度，位置点之间的间隔也可以是不同的，不同位置点所对应的半径也可以是不同的，本申请对此不作限定。

在生成映射关系之后，路网匹配设备可以将其保存在数据库中，以便在获取到新的位置信息时，从该映射关系中查找对应的候选路段。示例性地，该路网匹配设备可以将映射关系保存在键-值(key-value，KV)数据库中，例如，以Geohash值为键，以路段标识为值，来存储上述映射关系。路网匹配设备在获取到第一位置信息后，便可基于该映射关系来确定位于终端附近的候选路段。可选地，步骤220具体包括：基于第一位置信息，确定所对应的第一Geohash区域的Geohash值；基于预存的映射关系，确定第一Geohash区域的Geohash值所对应的一个或多个路段。应理解，该第一Geohash区域的Geohash值所对应的一个或多个路段为位于终端附近的候选路段。

示例性地，路网匹配装置在得到终端的第一位置信息后，就可以根据Geohash编码方法确定该终端所处的Geohash区域的Geohash值。

一示例，终端的第一位置信息为(北纬39.923201度，东经116.390705度)。

首先将经纬度分别用二进制数表示，北纬39.923201度转换为二进制数的过程如下表1所示：

表1

最终得到北纬39.923201度转换为二进制数为10111000110001111001，精确到第20位。应理解，Geohash区域划分得越精细，精确到的位数就越多，此处以精确到第20位为例。在实际应用中可以根据Geohash区域划分的精细程度自行决定精确到的位数。

使用相同的方法也可以将东经116.390705度转换为二进制数11010010110001000100。

然后按照先经度后纬度、经度纬度交替占位的原则将表示经度的二进制数和表示纬度的二进制数合并展示，得到1110011101001000111100000011010101100001。

最后将上述合并展示的二进制数用Base32编码的方法进行编码，每5位用一个字符表示，如果不足5位就用“0”占位，得到Geohash值为wx4g0ec1。

然后根据预存的映射关系，确定Geohash值为wx4g0ec1的Geohash区域所对应的路段。

结合上文示例的映射关系，可以确定Geohash值为wx4g0ec1的Geohash区域所对应的路段为道路1、道路3和道路4。即，位于终端附近的候选路段为道路1、道路3和道路4。

应理解，除了Geohash之外，本申请并不排除采用其他的方式来进行区域划分并予以标识的可能，例如，还可能存在基于位置进行编码得到各个区域的区域标识的其他算法，Geohash仅为一种可能的实现方式，不应对本申请构成任何限定。

在步骤230中，基于候选路段和终端在第一时间窗内的轨迹，确定终端在当前时间点所处的目标路段。

其中，第一时间窗的结束时间点为当前时间点，且时长为第一预设值。在本申请实施例中，时间窗可以随着时间的推进而滑动。比如，该第一时间窗是以当前时间点为结束时间点的窗口，随着时间的推进，在下一个时间点又可以得到以下一个时间点为结束时间点的窗口。

可以理解的是，第一时间窗包含了多个时间点，除了当前时间点之外，其他时间点为历史时间点。换言之，第一时间窗内的轨迹包含了至少一个历史时间点的位置信息。也就是说，路网匹配装置可以基于候选路段、终端在至少一个历史时间点的位置信息以及当前时间点的位置信息，确定终端在当前时间点所处的目标路段。

这里，目标路段是为了便于与候选路段区分而命名。目标路段是从候选路段中确定的，终端最有可能所处的路段。

由于GPS定位可能会出现误差，而GPS定位出现误差就会影响终端的位置信息的准确性，且可能对后续时间点的位置信息的确定也有影响。因此，在确定终端所处的目标路段之前，可以先对终端第一位置信息进行分析，以确定其是否为正常的位置信息。可选地，在步骤230之前，该路网匹配方法还包括：基于终端在第二时间窗内的轨迹，确定第一位置信息是否为正常的位置信息；在确定第一位置信息为正常的位置信息的情况下，基于第一位置信息对终端的轨迹进行更新，得到终端在第一时间窗内的轨迹。

第二时间窗是以上一个时间点为结束时间点的窗口。在本实施例中，第二时间窗是在第一时间窗之前的一个时间窗。

换言之，路网匹配设备可以基于历史的移动轨迹来对第一位置信息进行分析，如果第一位置信息所指示的位置偏离历史的移动轨迹较远，则可认为该第一位置信息是不正常的；如果第一位置信息所指示的位置偏离历史的移动轨迹较近，则可认为该第一位置信息是正常的。在一种可能的实现方式中，路网匹配设备可以基于第二时间窗内的位置信息构造K维(k-dimensional，K-D)树，在K-D树中寻找第一位置信息的K(K为整数)个距离该第一位置信息较近的位置点(为便于区分和说明，这里将该K个位置点记为K个邻近点)，并基于该K个邻近点与第一位置信息所指示的位置之间的距离来确定该第一位置信息是否为正常的位置信息。

应理解，K-D树是一种数据结构，可以应用于多维键值搜索，比如范围搜寻和最邻近搜索等，在本申请实施例中可用于确定第一位置信息在轨迹上的临近点。

具体地，上述K个邻近点在第二时间窗内的轨迹中较其他位置信息所对应的位置点更接近第一位置信息所对应的位置点，K为第三预设值且为整数。

示例性地，在K个邻近点与第一位置信息所指示的位置点之间的距离的均值属于预设范围的情况下，可确定第一位置信息为正常的位置信息；在K个邻近点与第一位置信息所指示的位置点之间的距离的均值不属于预设范围的情况下，可确定第一位置信息为异常的位置信息。

可选地，预设范围可以包括小于第一预设门限。也即，在K个邻近点与第一位置信息所指示的位置点之间的距离的均值小于第一预设门限的情况下，可确定第一位置信息为正常的位置信息；在K个邻近点与第一位置信息所指示的位置点之间的距离的均值大于或等于第一预设门限的情况下，可确定第一位置信息为异常的位置信息。

应理解，第一预设门限可用于将偏离K-D树较远的位置点识别出来，也即，将该位置点所对应的指示信息确定为异常的位置信息。

进一步地，预设范围还可以包括大于第二预设门限，该第二预设门限小于第一预设门限。也即，在K个邻近点与第一位置信息所指示的位置点之间的距离的均值小于第一预设门限且大于第二预设门限的情况下，可确定第一位置信息为正常的位置信息；在K个邻近点与第一位置信息所指示的位置点之间的距离的均值大于或等于第一预设门限，或小于或等于第二预设门限的情况下，可确定第一位置信息为异常的位置信息。

之所以引入第二预设门限，是因为在有些场景下，比如采集一些移动速度较快的终端轨迹时，如在飞机降落时采集其移动轨迹，则可能存在排布密集的位置点，这些位置点是不合理的，可通过引入第二预设门限将其排除。

一示例，如图4中的(a)所示。第一位置信息所对应的位置点记为p_n+1，第二时间窗为1分钟，路网匹配装置在当前时间点之前1分钟的轨迹数据记为(p₁，p₂，...，p_n)，针对该轨迹数据构造K-D树，遍历(p₁，p₂，...，p_n)上每个轨迹点。K为第三预设值5，使用K-D树获取离点p_n+1最近的5个点，记为q₁、q₂、q₃、q₄、q₅，与点p_n+1的地理信息系统(geographicinformation system，GIS)距离分别为20米、40米、50米、60米、70米，距离的均值为48米。取预设范围为大于2米(即，第二预设门限的一例)，且小于100米(即，第一预设门限的一例)，则5个邻近点与第一位置信息的距离的均值属于预设范围内，确定第一位置信息为正常的位置信息。

另一示例，如图4中的(b)所示。第一位置信息所对应的位置点记为p_n+1，第二时间窗为1分钟，路网匹配装置在当前时间点之前1分钟的轨迹数据记为(p₁，p₂，...，p_n)，针对该轨迹数据构造K-D树，遍历(p₁，p₂，...，p_n)上每个轨迹点。K为第三预设值5，使用K-D树获取离点p_n+1最近的5个点，记为q₁、q₂、q₃、q₄、q₅，与点p_n+1的GIS距离分别为90米、110米、120米、130米、140米，距离的均值为118米。取预设范围为大于2米，且小于100米，则5个邻近点与第一位置信息的距离的均值不属于预设范围内，确定第一位置信息为异常的位置信息。

应理解，上文所列举的对预设范围的定义，以及第一预设门限及第二预设门限的具体取值仅为示例，不应对本申请构成任何限定。

在确定第一位置信息为异常的位置信息的情况下，路网匹配装置可以将该第一位置信息剔除，继续获取下一个位置信息作为第一位置信息来处理，例如，确定该第一位置信息是否为正常的位置信息，并在正常的情况下，继续执行下述流程。

在确定第一位置信息为正常的位置信息的情况下，路网匹配装置可以基于该第一位置信息对终端的轨迹进行更新，得到终端在第一时间窗内的轨迹，记为(p₁，p₂，...，p_n，p_n+1)。

可选地，在得到终端在第一时间窗内的轨迹之后，该路网匹配方法还包括：

对终端在第一时间窗内的轨迹进行平滑，得到平滑后的轨迹；

基于平滑后的轨迹，采用优化算法对第一位置信息进行优化，得到优化后的第一位置信息；基于优化后的第一位置信息，得到优化后的轨迹。轨迹是由多个位置点按照时间顺序依次相连得到的，未经处理的轨迹形状是一条折线。为了使轨迹看起来更加美观，可以对轨迹进行平滑处理。例如可以使用Savitzky-Golay滤波器对上述第一时间窗内的轨迹进行平滑处理。该第一时间窗内的轨迹可以是未经过异常点检测的轨迹，也可以是经过了异常点检测后的轨迹，本申请对此不作限定。

应理解，Savitzky-Golay滤波器是一种滤波算法，可以用于数据流平滑除噪。轨迹进行平滑处理除了Savitzky-Golay滤波器之外还可以使用其他算法，本申请对此不作任何限定。

为了使第一位置信息更加准确，采用优化算法对第一位置信息进行优化。例如可以使用Kalman滤波算法对第一位置信息进行优化。Kalman滤波算法是根据最小均方误差准则建立起来的估计方法。它用线性递推的方法，对多个测量数据和多个信号参数进行处理，给出无偏差的最小均方误差估计。在本实施例中，路网匹配装置可以结合第一时间窗内的轨迹中的历史时间点(如上一个时间点)的位置和速度，使用Kalman滤波对当前时间点的位置和速度进行估计，可以得到第一位置信息的解。其中，第一时间窗内的轨迹可以是平滑处理后的轨迹，也可以是未经平滑处理的轨迹，比如可以是经过异常点检测后得到的轨迹，或者是基于原始的GPS数据得到的轨迹，本申请对此不作限定。

应理解，使用Kalman滤波算法对第一位置信息进行优化的具体过程可参看已有技术，此处不做详述。还应理解，对第一位置信息进行优化处理除了Kalman滤波算法之外还可以使用其他算法，如粒子群优化算法等，本申请对此不作任何限定。

在经过轨迹平滑和对第一位置信息进行优化之后，就可以获得优化后的轨迹。

应理解，上述的轨迹平滑和第一位置信息的优化这两个步骤可以结合实施，也可以单独实施，比如只做轨迹平滑或只做第一位置信息的优化，本申请对此不作限定。可以理解的是，对轨迹进行平滑处理，对第一位置信息进行优化，可以使得轨迹更加接近真实的轨迹，有利于提高路网匹配的准确度。

进一步地，步骤230具体可以包括：基于候选路段和优化后的轨迹，确定终端在当前时间点所处的目标路段。

在获得优化后的轨迹后，路网匹配装置可以基于上述候选路段和该优化后的轨迹，确定终端在当前时间点所处的目标路段。

路网匹配装置可以基于马尔可夫模型来确定终端在当前时间点所处的目标路段。由于该目标路段是从候选路段中确定的，故可以计算终端从上一个时间点所在的路段转移至各候选路段的转移概率。在本实施例中，每个候选路段被表示为马尔可夫链中的隐藏状态，并具有观测状态概率，这是观察第一位置信息与候选路段匹配的可能性。为马尔可夫链中连接每一对相邻定点的边计算权重，即状态转移概率。最终在马尔可夫链中找到具有最高观测状态概率和状态转移概率的最大似然路径，例如可使用维特比算法进行求解，实际上是用一个动态规划算法解决隐马尔可夫模型预测问题，即用动态规划在道路网络中快速找到使观测概率和转移概率的乘积最大化的解。如此，可以从一个或多个候选路段中确定终端在当前时间点所处的目标路段。

应理解，使用马尔可夫模型从候选路段中确定目标路段的具体过程可参看已有技术，此处不再赘述。

在步骤240中，基于终端在当前时间点所处的目标路段，对轨迹中的第一位置信息进行纠偏，得到纠偏后的轨迹。

在对第一位置信息进行纠偏后，路网匹配装置便可将纠偏后的第一位置信息用于对第一时间窗内的轨迹进行更新，得到纠偏后的轨迹。可以理解，该轨迹可用于下一个时间点的轨迹纠偏。

基于上述方法，可以基于终端的位置信息以及预存的区域与路段的映射关系，确定终端所处的区域，进而查找出终端可能位于的候选路段，再根据终端之前的移动轨迹，从这些候选路段中确定终端当前所处的路段，最后基于终端当前所处的路段对终端的移动轨迹进行纠偏，得到纠偏后的轨迹。通过将上一时间点的移动轨迹作为当前时间点的历史轨迹，进而对当前时间点的移动轨迹进行纠偏，纠偏后的移动轨迹又可以成为下一时间点的历史轨迹，如此迭代，可以实时地对移动轨迹进行纠偏，提高移动轨迹的准确度。并且，由于预存了区域与路段的映射关系，可以直接将位置信息转换到区域，进而查找出该位置附近的候选路段，不必在线地根据终端的位置信息实时计算候选路段，故可以减少计算量，提高实时纠偏的效率。

图5是本申请实施例提供的路网匹配方法的另一示意性流程图。

从图5中可以看出，本申请实施例提供的路网匹配方法需要获取的源数据有两个：GPS轨迹和路网数据。其中，GPS轨迹包括终端在当前时间点之前的轨迹以及终端在当前时间点的位置。路网数据包括路网中每一个路段的名称以及该路段以经纬度表示的函数。

路网数据首先会做Geohash预计算，即，确定路网中的每一个路段与Geohash区域的映射关系，并将该映射关系预存起来。便于后续的路网匹配，即根据位置信息确定终端在当前时间点所处的目标路段。

GPS轨迹数据首先会做异常点检测。根据终端在当前时间点之前一段预设时长(即第二时间窗)内的轨迹，在轨迹上确定K个邻近点，在本申请实施例中例如为5个。再计算这5个邻近点与终端在当前时间点的位置之间的距离的均值。如果这个均值在预设范围内，则终端在当前时间点的位置信息是正常的位置信息；如果这个均值不在预设范围内，则终端在当前时间点的位置信息是异常的位置信息。在确定终端在当前时间点的位置信息是正常的位置信息之后，就可以对GPS轨迹进行更新，得到更新后的GPS轨迹。

接下来对更新后的GPS轨迹做轨迹平滑处理，例如可以使用Savitzky-Golay滤波器滤除GPS轨迹中的噪声数据。

接下来使用Kalman滤波算法进行优化，对平滑后的GPS轨迹做估计，使GPS轨迹更加准确。

最后基于优化过的GPS轨迹和上述路段与Geohash区域的映射关系，做路网匹配。从该终端附近的一个或多个候选路段中，确定目标路段，进而对轨迹中的第一位置信息进行纠偏，得到纠偏后的轨迹。

图6是本申请实施例提供的路网匹配装置的示意性框图。该装置可以对应于上文方法实施例中的路网匹配装置，用于实现其相应的功能。该装置例如为图1中的服务器120，如图6所示，该路网匹配装置600可以包括获取模块610和处理模块620。

其中，获取模块610可用于获取第一位置信息，第一位置信息用于指示终端在当前时间点的位置；处理模块620可用于基于第一位置信息，以及预存的映射关系，确定位于终端附近的一个或多个候选路段，映射关系用于指示至少一个区域中每个区域附近的一个或多个路段；基于候选路段和终端在第一时间窗内的轨迹，确定终端在当前时间点所处的目标路段；其中，第一时间窗的结束时间点为当前时间点，且时长为第一预设值；基于终端在当前时间点所处的目标路段，对轨迹中的第一位置信息进行纠偏，得到纠偏后的轨迹。

具体地，映射关系包括至少一个Geohash值与至少一个路段标识的对应关系；每个Geohash值用于标识一个Geohash区域，Geohash值基于所标识的Geohash区域的经纬度编码得到，每个路段标识用于标识一个路段。

可选地，处理模块620可用于，基于第一位置信息，确定所对应的第一Geohash区域的Geohash值；基于预存的映射关系，确定第一Geohash区域的Geohash值所对应的一个或多个路段，第一Geohash区域的Geohash值所对应的一个或多个路段为位于终端附近的一个或多个候选路段。

可选地，处理模块620还可用于，在路网数据中的每个路段中确定多个位置点；确定多个位置点中每个位置点所对应的区域与预定义的多个Geohash值中的每个Geohash值所标识的Geohash区域是否存在交点，其中，每个位置点所对应的区域是以所述每个位置点为圆心，以第二预设值为半径得到的圆形区域；基于存在交点的位置点和Geohash区域，生成映射关系。

具体地，第一位置信息基于上一时间点的路网匹配结果对在当前时间点获取到的GPS数据优化得到，上一时间点的路网匹配结果包括：终端在第二时间窗内的轨迹，第二时间窗的结束时间点为上一时间点，且时长为第一预设值，终端在所述第二时间窗内的轨迹包括终端在第二时间窗内的多个时间点的位置信息，每个时间点的位置信息基于前一时间点的路网匹配结果对新获取到的GPS数据优化得到。

可选地，处理模块620还可用于，基于终端在所述第二时间窗内的轨迹，确定第一位置信息是否为正常的位置信息；在确定第一位置信息为正常的位置信息的情况下，基于第一位置信息对终端的轨迹进行更新，得到终端在第一时间窗内的轨迹。

可选地，处理模块620可用于，基于终端在第二时间窗内的轨迹中所包含的多个位置信息，构造K-D树；在K-D树中寻找第一位置信息的K个邻近点，K个邻近点在多个位置信息中较其他位置信息所对应的位置点更接近第一位置信息所对应的位置点，K为第三预设值且为整数；以及在K个邻近点与第一位置信息的距离的均值属于预设范围的情况下，确定第一位置信息为正常的位置信息；或在K个邻近点与第一位置信息的距离的均值不属于预设范围的情况下，确定第一位置信息为异常的位置信息。

可选地，处理模块620还可用于，对终端在第一时间窗内的轨迹进行平滑，得到平滑后的轨迹；基于平滑后的轨迹，采用优化算法对第一位置信息进行优化，得到优化后的第一位置信息；基于优化后的第一位置信息，得到优化后的轨迹；以及基于候选路段和优化后的轨迹，确定终端在当前时间点所处的目标路段。

图7是本申请实施例提供的路网匹配装置的另一示意性框图。如图7所示，该装置700可以包括至少一个处理器710，可用于实现上述方法实施例中路网匹配装置的功能。具体参见方法示例中的详细描述，此处不做赘述。

该装置700还可以包括一个存储器720，用于存储程序指令和/或数据。存储器720和处理器710耦合。本申请中的耦合是装置、单元或模块之间的间接耦合或通信连接，可以是电性，机械或其它的形式，用于装置、单元或模块之间的信息交互。处理器710可能和存储器720协同操作。处理器710可能执行存储器720中存储的程序指令。所述至少一个存储器中的至少一个可以包括于处理器中。

该装置700还可以包括一个通信接口730，用于通过传输介质和其它设备进行通信，从而用于装置700中的装置可以和其它设备进行通信。所述通信接口730例如可以是收发器、接口、总线、电路或者能够实现收发功能的装置。处理器710可利用通信接口730收发数据和/或信息，并用于实现图2对应的实施例中所述的路网匹配方法。

本申请中不限定上述处理器710、存储器720以及通信接口730之间的具体连接介质。本申请在图7中以处理器710、存储器720以及通信接口730之间通过总线740连接。总线740在图7中以粗线表示，其它部件之间的连接方式，仅是进行示意性说明，并不引以为限。所述总线可以分为地址总线、数据总线、控制总线等。为便于表示，图7中仅用一条粗线表示，但并不表示仅有一根总线或一种类型的总线。

在本申请实施例中，处理器可以是通用处理器、数字信号处理器、专用集成电路、现场可编程门阵列或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件，可以实现或者执行本申请中的公开的各方法、步骤及逻辑框图。通用处理器可以是微处理器或者任何常规的处理器等。结合本申请所公开的方法的步骤可以直接体现为硬件处理器执行完成，或者用处理器中的硬件及软件模块组合执行完成。

根据本申请提供的方法，本申请还提供一种计算机可读存储介质，该计算机可读存储介质存储有程序代码，当该程序代码在计算机上运行时，使得该计算机执行图2所示实施例中的路网匹配方法。

根据本申请提供的方法，本申请还提供一种计算机程序产品，该计算机程序产品包括：计算机程序代码。当该计算机程序代码在计算机上运行时，使得该计算机执行图2所示实施例中的路网匹配方法。

本申请提供的技术方案可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。所述计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行所述计算机程序指令时，全部或部分地产生按照本申请所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、网络设备、终端设备或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一个计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线，例如同轴电缆、光纤、数字用户线(digital subscriber line，DSL)或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。所述计算机可读存储介质可以是计算机可以存取的任何可用介质或者是包含一个或多个可用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质(例如，软盘、硬盘、磁带)、光介质例如，数字视频光盘(digital video disc，DVD)、或者半导体介质等。

以上所述，仅为本申请的具体实施方式，但本申请的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本申请揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本申请的保护范围之内。因此，本申请的保护范围应以所述权利要求的保护范围为准。

Claims (10)

1.一种路网匹配方法，其特征在于，包括：

获取第一位置信息，所述第一位置信息用于指示终端在当前时间点的位置，所述第一位置信息基于上一时间点的路网匹配结果对在所述当前时间点获取到的全球定位系统GPS数据优化得到，所述上一时间点的路网匹配结果包括：所述终端在第二时间窗内的轨迹，所述第二时间窗的结束时间点为所述上一时间点，且时长为所述第一预设值，所述终端在所述第二时间窗内的轨迹包括所述终端在所述第二时间窗内的多个时间点的位置信息，每个时间点的位置信息基于前一时间点的路网匹配结果对新获取到的GPS数据优化得到；

基于所述第一位置信息，以及预存的映射关系，确定位于所述终端附近的一个或多个候选路段，所述映射关系用于指示至少一个区域中每个区域附近的一个或多个路段；

基于所述候选路段和所述终端在第一时间窗内的轨迹，确定所述终端在所述当前时间点所处的目标路段；其中，所述第一时间窗的结束时间点为所述当前时间点，且时长为第一预设值；

基于所述终端在当前时间点所处的目标路段，对所述第一时间窗内的轨迹中的第一位置信息进行纠偏，得到纠偏后的轨迹。

2.如权利要求1所述的方法，其特征在于，所述映射关系包括至少一个区域标识与至少一个路段标识的对应关系；每个区域标识用于标识一个区域，所述区域标识基于所标识的区域的位置编码得到，每个路段标识用于标识一个路段。

3.如权利要求2所述的方法，其特征在于，所述基于所述第一位置信息，以及预存的映射关系，确定位于所述终端附近的一个或多个候选路段，包括：

基于所述第一位置信息，确定所对应的第一区域的区域标识；

基于所述预存的映射关系，确定所述第一区域的区域标识所对应的一个或多个路段，所述第一区域的区域标识所对应的一个或多个路段为位于所述终端附近的一个或多个候选路段。

4.如权利要求2或3所述的方法，其特征在于，在所述基于所述第一位置信息，以及预存的映射关系，确定位于所述终端附近的一个或多个候选路段之前，所述方法还包括：

在路网数据中的每个路段中确定多个位置点；

确定所述多个位置点中每个位置点所对应的区域与预定义的多个区域标识中的每个区域标识所标识的区域是否存在交点，其中，所述每个位置点所对应的区域是以所述每个位置点为圆心，以第二预设值为半径得到的圆形区域；

基于存在交点的位置点和区域，生成所述映射关系。

5.如权利要求1所述的方法，其特征在于，在所述基于所述候选路段和所述终端在第一时间窗内的轨迹，确定所述终端在当前时间点所处的目标路段之前，所述方法还包括：

基于所述终端在所述第二时间窗内的轨迹，确定所述第一位置信息是否为正常的位置信息；

在确定所述第一位置信息为正常的位置信息的情况下，基于所述第一位置信息对所述终端的轨迹进行更新，得到所述终端在所述第一时间窗内的轨迹。

6.如权利要求5所述的方法，其特征在于，所述基于所述终端在所述第二时间窗内的轨迹，确定所述第一位置信息是否为正常的位置信息，包括：

基于所述终端在所述第二时间窗内的轨迹中所包含的多个位置信息，构造K维K-D树；

在所述K-D树中寻找所述第一位置信息的K个邻近点，所述K个邻近点在所述多个位置信息中较其他位置信息所对应的位置点更接近所述第一位置信息所对应的位置点，K为第三预设值且为整数；以及

在所述K个邻近点与所述第一位置信息的距离的均值属于预设范围的情况下，确定所述第一位置信息为正常的位置信息；或

在所述K个邻近点与所述第一位置信息的距离的均值不属于所述预设范围的情况下，确定所述第一位置信息为异常的位置信息。

7.如权利要求5或6所述的方法，其特征在于，在所述得到所述终端在所述第一时间窗内的轨迹之后，所述方法还包括：

对所述终端在所述第一时间窗内的轨迹进行平滑，得到平滑后的轨迹；

基于所述平滑后的轨迹，采用优化算法对所述第一位置信息进行优化，得到优化后的第一位置信息；

基于所述优化后的第一位置信息，得到优化后的轨迹；以及

所述基于所述候选路段和所述终端在第一时间窗内的轨迹，确定所述终端在所述当前时间点所处的目标路段，包括：

基于所述候选路段和所述优化后的轨迹，确定所述终端在所述当前时间点所处的目标路段。

8.一种路网匹配装置，其特征在于，包括用于执行如权利要求1至7中任一项所述的方法的模块。

9.一种路网匹配装置，其特征在于，包括处理器，处理器用于执行计算机程序，以实现如权利要求1至7中任一项所述的方法。

10.一种计算机可读存储介质，其特征在于，包括计算机程序，当所述计算机程序被运行时，使得所述计算机执行如权利要求1至7中任一项所述的方法。