CN104462273A - 提取轨迹的方法及系统 - Google Patents

Abstract

本发明提供一种提取轨迹的方法及系统，所述方法包括：获取用户提供的时间段和用户根据地图数据确定的地理范围；根据所述时间段，筛选出属于所述时间段的轨迹点；在所述筛选出的轨迹点中，通过查找算法查找出所述地理范围内的轨迹点；对所述查找出的轨迹点进行收录；按照时间顺序将所述收录的轨迹点排列成轨迹。通过采用本发明可以实现从大量轨迹中快速、便捷地获取特定的部分轨迹。

Description

提取轨迹的方法及系统

技术领域

本发明涉及通信领域，更为具体而言，涉及提取轨迹的方法及系统。

背景技术

目前对于地图导航会出现轨迹偏移的情况，在复现问题时通常采用：实际路测的方式，然而其复现率低并且沟通成本高；或者从大量的用户中寻找反馈用户，并将用户轨迹全部上传再提取的方式，但其对用户和轨迹的筛选需要消耗大量人力并且对所有轨迹的采集消耗网络流量。

另外，目前还存在用户想分享自己的部分轨迹的情形，而在现有技术中对于分享轨迹，通常是通过整个全量的轨迹文件来进行分享，而如果是分享整个行程的部分轨迹，只能停止当前的记录，再重新记录轨迹，并通过记录完成后所产生的新的轨迹文件进行分享，而无法从大量轨迹中选取部分轨迹进行分享。

因此，当前需要一种能够实现从大量轨迹中快速、便捷地获取特定的部分轨迹的方式。

发明内容

为有效地解决上述技术问题，本发明提供了一种提取轨迹的方法及系统。

一方面，本发明的实施方式提供了一种提取轨迹的方法，所述方法包括：

获取用户提供的时间段和用户根据地图数据确定的地理范围；

根据所述时间段，筛选出属于所述时间段的轨迹点；

在所述筛选出的轨迹点中，通过查找算法查找出所述地理范围内的轨迹点；

对所述查找出的轨迹点进行收录；

按照时间顺序将所述收录的轨迹点排列成轨迹。

另一方面，本发明的实施方式提供了一种提取轨迹的系统，所述系统包括：

获取模块，用于获取用户提供的时间段和用户根据地图数据确定的地理范围；

筛选模块，用于根据所述获取模块所获取的时间段，筛选出属于所述时间段的轨迹点；

查找模块，用于在所述筛选模块所筛选出的轨迹点中，通过查找算法查找出所述获取模块所获取的地理范围内的轨迹点；

第一收录模块，用于对所述查找模块所查找出的轨迹点进行收录；

轨迹排列模块，用于按照时间顺序将所述第一收录模块所收录的轨迹点排列成轨迹。

实施本发明提供的提取轨迹的方法及系统可以从大量轨迹中快速、便捷地获取特定的部分轨迹。

附图说明

图1是根据本发明实施方式的提取轨迹的方法的流程图；

图2示出了图1所示的步骤S130的一种实施方式；

图3示出了图1所示的步骤S140的一种实施方式；

图4是本发明实施方式中用户限定方向及地理范围的一个示例；

图5是本发明实施方式中误差的一个示例；

图6是根据本发明实施方式的提取轨迹的系统的结构示意图；

图7示出了图6所示的查找模块130的一种实施方式；

图8示出了图6所示的第一收录模块140的一种实施方式。

具体实施方式

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

图1是根据本发明实施方式的提取轨迹的方法的流程图。参见图1，所述方法包括：

S110：获取用户提供的时间段和用户根据地图数据确定的地理范围。

其中，在本发明的实施方式中，用户可以在给定的面状地图数据上勾勒出其所要限定的地理范围。

S120：根据所述时间段，筛选出属于所述时间段的轨迹点。

其中，所述轨迹点具有定位信息，例如经纬度以及时间等。

S130：在所述筛选出的轨迹点中，通过查找算法查找出所述地理范围内的轨迹点。

通过上述过程可以从大量轨迹中快速、便捷地获取特定的部分轨迹。

在本发明的一种优选实施方式中，所述查找算法可以包括二分查找算法、顺序查找算法以及分块查找算法等。并且由于用户在其限定的地理范围内可能仅经过1次也可能经过2次以上，因此在本发明的实施方式中，用户可以提供区域经过信息，根据用户的区域经过信息(经过2次以上或经过1次)而调用不同的查找算法，例如，当经过2次以上时调用顺序查找算法，其可以将连续轨迹中的所有有效段落全部查找出来，避免了有效数据的丢失，而当经过1次时调用二分查找算法，以获得更高的查找效率。由此兼顾效率与可靠性。具体地，如图2所示，可以通过以下步骤实现：

S131：获取所述用户的区域经过信息。

S132：当所述区域经过信息为经过2次以上时，调用顺序查找算法查找属于所述地理范围内的轨迹点。

S133：当所述区域经过信息为经过1次时，调用二分查找算法查找属于所述地理范围内的轨迹点。

S140：对所述查找出的轨迹点进行收录。

其中，在本发明的实施方式中，用户可以限定轨迹的方向，将方向与用户所限定的方向匹配成功的轨迹中的轨迹点进行收录。具体地，如图3所示，可以通过以下步骤实现：

S141：在所述查找出的轨迹点中，确定出连续轨迹以及所述连续轨迹的方向；

S142：将所述连续轨迹的方向与所述用户给定的限定方向进行模糊匹配；

其中，对于该模糊匹配可以通过以下步骤实现：判断所述连续轨迹的方向与所述限定方向的偏离角度是否小于或等于预定角度，若所述偏离角度小于或等于预定角度(例如可以是45°，当然不限于此，根据实际需要可以设定预定角度为40°到60°范围内的任意角度)，则匹配成功；若所述偏离角度大于预定角度，则在地理或时间的维度上，判断所述连续轨迹中偏离的轨迹点与所述连续轨迹中全部轨迹点的数量比值是否小于预定阈值(例如可以是0.2，当然不限于此，根据实际需要可以设定预定阈值为0.1到0.3范围内的任意值)，若所述比值小于预定阈值则匹配成功。

S143：将匹配成功的连续轨迹中的轨迹点进行收录。

S150：按照时间顺序将所述收录的轨迹点排列成轨迹。

此外，由于地理范围的勾勒不当或者偏移打点会造成误差，因此在本发明的另一优选实施方式中，可以通过误差处理方法来减小由上述原因所带来的误差。具体地，可以通过以下方式实现：

在所述时间段内的未被收录的轨迹点中，确定出连续轨迹作为误差判定集合；

判断所述误差判定集合是否符合误差补录条件；

其中，该误差补录条件例如可以为，但不限于：在时间维度上，所述误差判定集合的前一个轨迹点以及后一个轨迹点均为已收录的轨迹点；或者，在地理或时间维度上，所述误差判定集合中的轨迹点的数量与已收录的轨迹点的数量比值小于预定阈值(例如可以是0.2，当然不限于此，根据实际需要可以设定预定阈值为0.1到0.3范围内的任意值)。

将符合所述误差补录条件的误差判定集合中的轨迹点进行补充收录。

另外，由于噪点的定位信息与实际不符，因此噪点是处理定位信息错误的重要依据，需要尽量收录。由此，在本发明的另一优选实施方式中，可以通过一定的方式将用户勾勒的地理范围以外的符合一定条件的噪点进行补充收录。具体地，可以通过以下步骤实现：

判断所述时间段内的未被收录的轨迹点中是否存在噪点；

若存在，则判断所述噪点是否符合噪点补录条件；

其中，该噪点补录条件可以为，但不限于：所述噪点与该噪点在时间上的前一个已收录的轨迹点之间的距离小于所述噪点在时间上的前三个已收录的轨迹点所构成的2段间隔之和。

将符合所述噪点补录条件的噪点进行补充收录。

下面给出具体的例子，对本发明所提供的方法进行具体说明。

在本发明的实施方式中，可以在地图端等给用户一个入口，而用户需要配合输入的内容有：日期(必填)；方向(可选)，对于同一道路可能会有往返，但是对于轨迹可能在单方向上才有意义，因此对于用户来说可能只想获取某一方向的轨迹，并且，如图4所示，可以引导用户在地图上勾勒地理范围的时候同时画出方向；是否多次路过(可选)；在给出的面状地图数据上勾勒出特定轨迹出现的地理范围。至此用户的操作完成。以下具体介绍提取轨迹的过程，并且需要说明的是，轨迹点的定位信息可以包括：经纬度、时间、时速、海拔等。

通过给定的日期筛选出该日期内的轨迹，如果用户没有选择【多次路过】则通过二分查找算法，当有轨迹点命中用户所勾勒的地理范围后，通过前后逐一匹配，最终快速得到一个在用户勾勒的地理范围内的轨迹。其中，通过二分查找(折半查找)算法进行查找的具体过程为：

1)在用户给定的时间段(日期)内的轨迹中，通过二分法查找出一个在所述地理范围内的轨迹点；

2)将该轨迹点在时间上的前后轨迹点逐一与所述地理范围匹配，从而查找出用户给定的地理范围内的轨迹。

如果用户选择【多次路过】，则由于多次路过会涉及连续轨迹中几个有效的段落(落入用户所勾勒的地理范围内的一段连续轨迹)，为了满足不丢失而采用顺序查找算法，将有效段落逐段地提取出来。其中，通过顺序查找算法进行查找的具体过程为：

按照时间顺序，从用户给定的时间段内的轨迹的起始轨迹点开始到终止轨迹点结束，对该时间段内的轨迹的各轨迹点逐一判断是否在所述地理范围内，从而查找出所有落入所述地理范围内的轨迹。

如果用户限定了方向，则将该方向与实际轨迹的方向做模糊匹配，例如如果偏离的角度在预定角度(例如可以是45°)的范围以内都认为是匹配成功，若偏离的角度超过预定角度，则进一步判断是否是小范围的偏离，例如可以计算出轨迹中偏离的轨迹点与该轨迹中全部轨迹点的数量比值，并与预定阈值(例如可以是0.2)进行比较，若小于预定阈值则认为匹配成功。若轨迹的方向与限定的方向匹配成功则将该轨迹提取出来，若不匹配则将该轨迹中的轨迹点剔除。其中，由于轨迹点的定位信息中包含经纬度，通过2个轨迹点就可以确定一条直线，加上根据定位信息中的时间，可以确定上述2个轨迹点的先后顺序，就可以确定出运动的方向。

如图5所示，由于地理范围的选取不当或者偏移打点会产生误差，导致一些轨迹点没有包含在用户所勾勒的地理范围内。如果这些轨迹点所构成的点集合满足一定的误差补录条件则认为是应当包含在所述地理范围内的，并将其补充收录，其中所述误差补录条件包括：1)点集合在时间上的前后轨迹点均被收录；或2)在地理或者时间的维度上，所述点集合中的轨迹点的数量与已收录的轨迹点的数量比值小于预定阈值(例如可以是0.2)。

由于噪点的收录是处理定位信息错误的重要依据，所以如果噪点没有包含到用户勾勒的区域内，则对该噪点进行一定的判定，若符合判定条件则将其补充收录。其中，噪点指定位错误导致定位信息和实际不符的轨迹点。并且该判定条件为：所述噪点与该噪点在时间上的前一个已收录的轨迹点之间的距离小于所述噪点在时间上的前三个已收录的轨迹点所构成的2段间隔之和。

图6是根据本发明实施方式的提取轨迹的系统的结构示意图。参见图6，所述系统100包括：

获取模块110，用于获取用户提供的时间段和用户根据地图数据确定的地理范围。

其中，在本发明的实施方式中，用户可以在给定的面状地图数据上勾勒出其所要限定的地理范围。

筛选模块120，用于根据所述获取模块110所获取的时间段，筛选出属于所述时间段的轨迹点。

其中，所述轨迹点具有定位信息，例如经纬度以及时间等。

查找模块130，用于在所述筛选模块120所筛选出的轨迹点中，通过查找算法查找出所述获取模块110所获取的地理范围内的轨迹点。

其中，所述查找算法可以包括二分查找算法、顺序查找算法以及分块查找算法等。并且如图7所示，查找模块130可以包括：

获取单元131，用于获取所述用户的区域经过信息；

顺序查找单元132，用于当所述获取单元131所获取的区域经过信息为经过2次以上时，调用顺序查找算法查找属于所述地理范围内的轨迹点；

二分查找单元133，用于当所述获取单元131所获取的区域经过信息为经过1次时，调用二分查找算法查找属于所述地理范围内的轨迹点。

第一收录模块140，用于对所述查找模块130所查找出的轨迹点进行收录。

其中，在本发明的实施方式中，用户可以限定轨迹的方向，将方向与用户所限定的方向匹配成功的轨迹中的轨迹点进行收录。具体地，如图8所示，第一收录模块140包括：

方向确定单元141，用于在所述查找出的轨迹点中，确定出连续轨迹以及所述连续轨迹的方向。

模糊匹配单元142，用于将所述方向确定单元141所确定出的连续轨迹的方向与所述用户给定的限定方向进行模糊匹配。

其中，具体地，该模糊匹配单元142可以包括：偏离角度判断组件，用于执行下述操作：判断所述连续轨迹的方向与所述限定方向的偏离角度是否小于或等于预定角度，若所述偏离角度小于或等于预定角度，则匹配成功；

偏离范围判断组件，用于执行下述操作：当所述偏离角度判断组件判断所述偏离角度大于预定角度时，在地理或时间的维度上，判断所述连续轨迹中偏离的轨迹点与所述连续轨迹中全部轨迹点的数量比值是否小于预定阈值，若所述比值小于预定阈值则匹配成功。

收录单元143，用于将所述模糊匹配单元142中匹配成功的连续轨迹中的轨迹点进行收录。

轨迹排列模块150，用于按照时间顺序将所述第一收录模块140所收录的轨迹点排列成轨迹。

此外，由于地理范围的勾勒不当或者偏移打点会造成误差，因此在本发明的实施方式中，可以通过误差处理方法来减小由上述原因所带来的误差。具体地，系统100还可以包括：

误差判定集合确定模块，用于在所述时间段内的未被收录的轨迹点中，确定出连续轨迹作为误差判定集合；

第一判断模块，用于判断所述误差判定集合确定模块所确定的误差判定集合是否符合误差补录条件；

其中，该误差补录条件例如可以为，但不限于：在时间维度上，所述误差判定集合的前一个轨迹点以及后一个轨迹点均为已收录的轨迹点；或者，在地理或时间维度上，所述误差判定集合中的轨迹点的数量与已收录的轨迹点的数量比值小于预定阈值(例如可以是0.2，当然不限于此，根据实际需要可以设定预定阈值为0.1到0.3范围内的任意值)。

第二收录模块，用于将符合所述误差补录条件的误差判定集合中的轨迹点进行补充收录。

另外，由于噪点的定位信息与实际不符，因此噪点是处理定位信息错误的重要依据，需要尽量收录。由此，在本发明的实施方式中，可以通过一定的方式将用户勾勒的地理范围以外的符合一定条件的噪点进行补充收录。具体地，系统100还可以包括：

第二判断模块，用于判断所述时间段内的未被收录的轨迹点中是否存在噪点。

第三判断模块，用于当所述第二判断模块判断存在噪点时，判断所述噪点是否符合噪点补录条件。

其中，该噪点补录条件可以为，但不限于：所述噪点与该噪点在时间上的前一个已收录的轨迹点之间的距离小于所述噪点在时间上的前三个已收录的轨迹点所构成的2段间隔之和。

第三收录模块，用于将符合所述噪点补录条件的噪点进行补充收录。

实施本发明提供的提取轨迹的方法及系统可以从大量轨迹中快速、便捷地获取特定的部分轨迹。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到本发明可借助软件结合硬件平台的方式来实现，当然也可以全部通过硬件来实施。基于这样的理解，本发明的技术方案对背景技术做出贡献的全部或者部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，智能手机或者网络设备等)执行本发明各个实施例或者实施例的某些部分所述的方法。

本发明说明书中使用的术语和措辞仅仅为了举例说明，并不意味构成限定。本领域技术人员应当理解，在不脱离所公开的实施方式的基本原理的前提下，对上述实施方式中的各细节可进行各种变化。因此，本发明的范围只由权利要求确定，在权利要求中，除非另有说明，所有的术语应按最宽泛合理的意思进行理解。

Claims (12)

1.一种提取轨迹的方法，其特征在于，所述方法包括：

获取用户提供的时间段和用户根据地图数据确定的地理范围；

根据所述时间段，筛选出属于所述时间段的轨迹点；

在所述筛选出的轨迹点中，通过查找算法查找出所述地理范围内的轨迹点；

对所述查找出的轨迹点进行收录；

按照时间顺序将所述收录的轨迹点排列成轨迹。

2.如权利要求1所述的方法，其特征在于，通过查找算法查找出所述地理范围内的轨迹点包括：

获取所述用户的区域经过信息；

当所述区域经过信息为经过2次以上时，调用顺序查找算法查找属于所述地理范围内的轨迹点；

当所述区域经过信息为经过1次时，调用二分查找算法查找属于所述地理范围内的轨迹点。

3.如权利要求2所述的方法，其特征在于，对所述查找出的轨迹点进行收录包括：

在所述查找出的轨迹点中，确定出连续轨迹以及所述连续轨迹的方向；

将所述连续轨迹的方向与所述用户给定的限定方向进行模糊匹配；

将匹配成功的连续轨迹中的轨迹点进行收录。

4.如权利要求3所述的方法，其特征在于，将所述连续轨迹的方向与所述用户给定的限定方向进行模糊匹配包括：

判断所述连续轨迹的方向与所述限定方向的偏离角度是否小于或等于预定角度，若所述偏离角度小于或等于预定角度，则匹配成功；

若所述偏离角度大于预定角度，则在地理或时间的维度上，判断所述连续轨迹中偏离的轨迹点与所述连续轨迹中全部轨迹点的数量比值是否小于预定阈值，若所述比值小于预定阈值，则匹配成功。

5.如权利要求1～4中任意一项所述的方法，其特征在于，所述方法还包括：

在所述时间段内的未被收录的轨迹点中，确定出连续轨迹作为误差判定集合；

判断所述误差判定集合是否符合误差补录条件；

将符合所述误差补录条件的误差判定集合中的轨迹点进行补充收录。

6.如权利要求1～4中任意一项所述的方法，其特征在于，所述方法还包括：

判断所述时间段内的未被收录的轨迹点中是否存在噪点；

若存在，则判断所述噪点是否符合噪点补录条件；

将符合所述噪点补录条件的噪点进行补充收录。

7.一种提取轨迹的系统，其特征在于，所述系统包括：

获取模块，用于获取用户提供的时间段和用户根据地图数据确定的地理范围；

筛选模块，用于根据所述获取模块所获取的时间段，筛选出属于所述时间段的轨迹点；

查找模块，用于在所述筛选模块所筛选出的轨迹点中，通过查找算法查找出所述获取模块所获取的地理范围内的轨迹点；

第一收录模块，用于对所述查找模块所查找出的轨迹点进行收录；

轨迹排列模块，用于按照时间顺序将所述第一收录模块所收录的轨迹点排列成轨迹。

8.如权利要求7所述的系统，其特征在于，所述查找模块包括：

获取单元，用于获取所述用户的区域经过信息；

顺序查找单元，用于当所述获取单元所获取的区域经过信息为经过2次以上时，调用顺序查找算法查找属于所述地理范围内的轨迹点；

二分查找单元，用于当所述获取单元所获取的区域经过信息为经过1次时，调用二分查找算法查找属于所述地理范围内的轨迹点。

9.如权利要求8所述的系统，其特征在于，所述第一收录模块包括：

方向确定单元，用于在所述查找出的轨迹点中，确定出连续轨迹以及所述连续轨迹的方向；

模糊匹配单元，用于将所述方向确定单元所确定出的连续轨迹的方向与所述用户给定的限定方向进行模糊匹配；

收录单元，用于将所述模糊匹配单元中匹配成功的连续轨迹中的轨迹点进行收录。

10.如权利要求9所述的系统，其特征在于，所述模糊匹配单元包括：

偏离角度判断组件，用于执行下述操作：判断所述连续轨迹的方向与所述限定方向的偏离角度是否小于或等于预定角度，若所述偏离角度小于或等于预定角度，则匹配成功；

偏离范围判断组件，用于执行下述操作：当所述偏离角度判断组件判断出所述偏离角度大于预定角度时，在地理或时间的维度上，判断所述连续轨迹中偏离的轨迹点与所述连续轨迹中全部轨迹点的数量比值是否小于预定阈值，若所述比值小于预定阈值，则匹配成功。

11.如权利要求7～10中任意一项所述的系统，其特征在于，所述系统还包括：

误差判定集合确定模块，用于在所述时间段内的未被收录的轨迹点中，确定出连续轨迹作为误差判定集合；

第一判断模块，用于判断所述误差判定集合确定模块所确定的误差判定集合是否符合误差补录条件；

第二收录模块，用于将符合所述误差补录条件的误差判定集合中的轨迹点进行补充收录。

12.如权利要求7～10中任意一项所述的系统，其特征在于，所述系统还包括：

第二判断模块，用于判断所述时间段内的未被收录的轨迹点中是否存在噪点；

第三判断模块，用于当所述第二判断模块判断存在噪点时，判断所述噪点是否符合噪点补录条件；

第三收录模块，用于将符合所述噪点补录条件的噪点进行补充收录。