构建对象的目标运动轨迹的缺失部分的方法和设备

摘要

本发明公开了一种构建对象的目标运动轨迹的缺失部分的方法和设备。所述方法包括：确定对象的历史运动轨迹上出现次数大于第一阈值的频繁点；从所述历史运动轨迹上包括所述频繁点的轨迹区段中，选择可信度大于第二阈值的至少一个轨迹区段，其中所述可信度表示所述轨迹区段与所述对象的目标运动轨迹的缺失部分相同的可能性；以及利用所选择的至少一个轨迹区段，构建所述缺失部分。所述方法和设备不依赖于对象所在区域的地图和路网，并且能够较为准确地构建目标运动轨迹的缺失部分。

说明书

技术领域

本发明涉及运动轨迹数据处理，更具体地，涉及一种构建对象的目标运动 轨迹的缺失部分的方法和设备。

背景技术

在智能交通系统(ITS)和车联网(ConnectedVehicles)领域中，通过分析 对象(人或车辆等)的运动轨迹，可以确定对象的运动状态、检测对象的运动 轨迹是否异常、提取对象的兴趣点(POI)/兴趣区域(ROI)等。因此，获得准确 且完整的运动轨迹非常重要。目前，可以使用多种方法来获得对象的运动轨迹， 例如全球定位系统(GPS)定位法和报到(checkin)法等。在GPS定位法中， 在对象运动期间通过GPS定位来确定对象的位置，从而确定对象的运动轨迹。 在报到法中，在不同的地点预先设置传感器或摄像头等，当对象经过这些地点 时，通过传感器或摄像头记录该事件(即，“报到”)，从而可以确定对象的位置， 最终，可以通过将对象经过的各个地点用直线连接起来，确定对象的运动轨迹。

然而，使用上述方法获得的对象的运动轨迹往往是离散和不完整的。例如， 在GPS定位法中，当对象运动到GPS信号接收质量不佳或者接收不到GPS信 号的某个区域时，对象在该区域内的位置数据可能丢失，使得最终获得的该对 象的运动轨迹的一部分缺失。在报到法中，由于只能在离散的地点设置传感器 或摄像头，因此，基于这些传感器或摄像头获得的对象的位置数据也是离散的， 使得最终获得的对象的运动轨迹由连接各个地点的直线组成，即，不连续而存 在缺失部分。作为结果，在基于这样的运动轨迹进行各种分析和检测时，无法 获得准确的结果。

发明内容

本发明的一个目的是提供一种构建对象的运动轨迹(为便于描述，以下可 称为目标运动轨迹)的缺失部分的方法和设备，其能够较为准确地构建目标运 动轨迹的缺失部分，从而为后续的基于该目标运动轨迹的各种分析和检测提供 良好的基础。

根据本发明的一个方面，提供了一种构建对象的目标运动轨迹的缺失部分 的方法，包括：确定对象的历史运动轨迹上出现次数大于第一阈值的频繁点； 从所述历史运动轨迹上包括所述频繁点的轨迹区段中，选择可信度大于第二阈 值的至少一个轨迹区段，其中所述可信度表示所述轨迹区段与所述对象的目标 运动轨迹的缺失部分相同的可能性；以及利用所选择的至少一个轨迹区段，构 建所述缺失部分。

根据本发明的另一个方面，提供了一种构建对象的目标运动轨迹的缺失部 分的设备，包括：确定装置，被配置为确定对象的历史运动轨迹上出现次数大 于第一阈值的频繁点；选择装置，被配置为从所述历史运动轨迹上包括所述频 繁点的轨迹区段中，选择可信度大于第二阈值的至少一个轨迹区段，其中所述 可信度表示所述轨迹区段与所述对象的目标运动轨迹的缺失部分相同的可能 性；以及构建装置，被配置为利用所选择的至少一个轨迹区段，构建所述缺失 部分。

利用根据本发明上述方面的方法和设备，可以从对象的历史运动轨迹中提 取与该对象的目标运动轨迹相同的可能性高的轨迹区段，然后利用所提取的轨 迹区段来构建所述目标运动轨迹的缺失部分。这样的构建方法和设备不依赖于 对象所在区域的地图和路网，并且具有较高的准确性。

附图说明

通过结合附图对本公开示例性实施方式进行更详细的描述，本公开的上述 以及其它目的、特征和优势将变得更加明显，其中，在本公开示例性实施方式 中，相同的参考标号通常代表相同部件。

图1示出了适于用来实现本发明实施方式的示例性计算机系统/服务器12 的框图。

图2示出了具有缺失部分的目标运动轨迹的示例。

图3示出了根据本发明实施例的构建对象的运动轨迹的缺失部分的方法的 流程图。

图4示出了通过栅格(Grid-cell)法来生成表示运动轨迹的轨迹序列的示意 图。

图5示出了图3所示的步骤S302的详细操作的流程图。

图6示出了根据本发明实施例的构建对象的运动轨迹的缺失部分的设备的 框图。

图7示出了图6所示的确定装置601的框图。

图8示出了图6所示的选择装置602的框图。

具体实施方式

下面将参照附图更详细地描述本公开的优选实施方式。虽然附图中显示了 本公开的优选实施方式，然而应该理解，可以以各种形式实现本公开而不应被 这里阐述的实施方式所限制。相反，提供这些实施方式是为了使本公开更加透 彻和完整，并且能够将本公开的范围完整地传达给本领域的技术人员。

图1示出了适于用来实现本发明实施方式的示例性计算机系统/服务器12 的框图。图1显示的计算机系统/服务器12仅仅是一个示例，不应对本发明实 施例的功能和使用范围带来任何限制。

如图1所示，计算机系统/服务器12以通用计算设备的形式表现。计算机 系统/服务器12的组件可以包括但不限于：一个或者多个处理器或者处理单元 16，系统存储器28，连接不同系统组件(包括系统存储器28和处理单元16) 的总线18。

总线18表示几类总线结构中的一种或多种，包括存储器总线或者存储器 控制器，外围总线，图形加速端口，处理器或者使用多种总线结构中的任意总 线结构的局域总线。举例来说，这些体系结构包括但不限于工业标准体系结构 (ISA)总线，微通道体系结构(MAC)总线，增强型ISA总线、视频电子标 准协会(VESA)局域总线以及外围组件互连(PCI)总线。

计算机系统/服务器12典型地包括多种计算机系统可读介质。这些介质可 以是任何能够被计算机系统/服务器12访问的可用介质，包括易失性和非易失 性介质，可移动的和不可移动的介质。

系统存储器28可以包括易失性存储器形式的计算机系统可读介质，例如 随机存取存储器(RAM)30和/或高速缓存存储器32。计算机系统/服务器12 可以进一步包括其它可移动/不可移动的、易失性/非易失性计算机系统存储介 质。仅作为举例，存储系统34可以用于读写不可移动的、非易失性磁介质(图 1未显示，通常称为“硬盘驱动器”)。尽管图1中未示出，可以提供用于对可 移动非易失性磁盘(例如“软盘”)读写的磁盘驱动器，以及对可移动非易失性 光盘(例如CD-ROM,DVD-ROM或者其它光介质)读写的光盘驱动器。在这 些情况下，每个驱动器可以通过一个或者多个数据介质接口与总线18相连。 存储器28可以包括至少一个程序产品，该程序产品具有一组(例如至少一个) 程序模块，这些程序模块被配置以执行本发明各实施例的功能。

具有一组(至少一个)程序模块42的程序/实用工具40，可以存储在例如 存储器28中，这样的程序模块42包括——但不限于——操作系统、一个或者 多个应用程序、其它程序模块以及程序数据，这些示例中的每一个或某种组合 中可能包括网络环境的实现。程序模块42通常执行本发明所描述的实施例中 的功能和/或方法。

计算机系统/服务器12也可以与一个或多个外部设备14(例如键盘、指向 设备、显示器24等)通信，还可与一个或者多个使得用户能与该计算机系统/ 服务器12交互的设备通信，和/或与使得该计算机系统/服务器12能与一个或多 个其它计算设备进行通信的任何设备(例如网卡，调制解调器等等)通信。这 种通信可以通过输入/输出(I/O)接口22进行。并且，计算机系统/服务器12 还可以通过网络适配器20与一个或者多个网络(例如局域网(LAN)，广域网 (WAN)和/或公共网络，例如因特网)通信。如图所示，网络适配器20通过 总线18与计算机系统/服务器12的其它模块通信。应当明白，尽管图中未示 出，可以结合计算机系统/服务器12使用其它硬件和/或软件模块，包括但不限 于：微代码、设备驱动器、冗余处理单元、外部磁盘驱动阵列、RAID系统、 磁带驱动器以及数据备份存储系统等。

下面，将参照附图来描述根据本发明实施例的构建对象的目标运动轨迹的 缺失部分的方法和设备。所述对象可以是人、车辆或者其他可由人控制的物体。 在下文中，为便于描述，以人作为对象的示例来描述本发明的实施例。此外， 如上文所述，对象的目标运动轨迹的缺失部分可能由于各种原因而引起。图2 示出了具有缺失部分的目标运动轨迹的示例，其中，在目标运动轨迹a中，点 A和点B之间的部分(椭圆中的部分)缺失。可以利用根据本发明实施例的方 法和设备来构建该缺失部分。

根据本发明实施例的方法和设备是基于以下认识提出的：当人们从出发地 行进到目的地时，即使在出发地和目的地之间存在多条路线，人们也往往沿着 他们习惯的路线行进，因此，可以基于人们的历史运动轨迹，来估计其目标运 动轨迹的缺失部分，从而构建该缺失部分。

下面，将参照图3来描述根据本发明实施例的构建对象的目标运动轨迹的 缺失部分的方法。

如图3所示，在步骤S301中，确定对象的各条历史运动轨迹上出现次数大 于第一阈值的点(为便于描述，以下称为频繁点)。

具体地，在过去的一段时间(例如一年)内，在预定的地理区域(例如城 市)中，对象可能在不同的点(即，地点)之间移动，使得在该地理区域中产 生对象的一条或多条运动轨迹，即历史运动轨迹，其中每条历史运动轨迹是通 过将每次对象移动时经过的点相连接而形成的。各条历史运动轨迹经过的点(包 括起点、终点和/或中间点)可能相同，也可能不同。此外，对象可能频繁地经 过该地理区域中的某些点，使得这些点在一条或多条历史运动轨迹上多次出现。 在本发明的实施例中，可以将出现次数大于第一阈值的点确定为对象频繁经过 的点，即所述频繁点。所述第一阈值可以根据实际需要灵活地设定，例如可以 设置为2。由于所述频繁点往往位于对象频繁行进的运动轨迹上，因此，可以 通过找出对象的历史运动轨迹上的频繁点，来找出对象频繁行进的运动轨迹。 在本发明的实施例中，例如，可以将所述历史运动轨迹的数据存储在历史运动 轨迹数据库中。

为了找出频繁点，可以确定对象的各条历史运动轨迹上的各个点在这些历 史运动轨迹上的出现次数，并且将该出现次数与所述第一阈值进行比较。如果 某个点的出现次数大于第一阈值，则可以将这个点确定为频繁点，反之则不将 这个点确定为频繁点。

具体地，对于每条历史运动轨迹，可以生成表示该历史运动轨迹的轨迹序 列Tr。该轨迹序列Tr可以包含多个元素，每个元素对应于该历史运动轨迹上的 一个点。例如，对于经过m个点的历史运动轨迹，其轨迹序列可表示为 Tr＝{E₁,E₂,...,E_m}或Tr＝E₁E₂...E_m，其中，E_i(1≤i≤m)表示轨迹序列Tr的第i元素， 该元素可以进一步表示为(Loc(i)，Time(i))，其中，Loc(i)表示在所述历史运动 轨迹上与元素E_i对应的点的位置，Time(i)表示对象沿着所述历史运动轨迹行进 时经过与元素E_i对应的点的时间。应当认识到，在本发明的其他实施例中，第 i元素也可以只包括Loc(i)，而不包括Time(i)。

可以使用多种方法来生成表示历史运动轨迹的轨迹序列。例如，可以通过 栅格(Grid-cell)法来生成所述轨迹序列。在这种方法中，可以将历史运动轨迹所 在的地理区域(例如城市)栅格化，如图4所示。然后，可以根据历史运动轨 迹上的各个点所处的栅格的位置，确定各个点的位置，即，通过各个点所处的 栅格的位置来表示各个点的位置，从而确定表示该历史运动轨迹的轨迹序列中 的各个元素的Loc的值。此外，在记录历史运动轨迹时，可以同时记录对象经 过该历史运动轨迹上的各个点的时间，从而可以确定表示该历史运动轨迹的轨 迹序列中的各个元素的Time的值。由此，可以确定所述轨迹序列中的各个元素。 应当注意，在栅格法中，将历史运动轨迹所在的区域栅格化而形成的各个栅格 的大小可以相同，也可以不同，并且各个栅格的形状也不限于图4所示的矩形 形状，而是可以是根据实际需要选择的任何形状，例如菱形等。除了栅格法以 外，也可以使用POI序列法来生成表示每条历史运动轨迹的轨迹序列。在这种 方法中，使所述轨迹序列中的各个元素分别对应于该历史运动轨迹经过的各个 POI，将各个元素的Loc的值设置为与所述元素对应的POI的名称(例如，在 POI是建筑物的情况下，建筑物的名称)，并且将各个元素的Time的值设置为 对象经过与所述元素对应的POI的时间，由此，可以确定所述轨迹序列中的各 个元素。当然，除了上述方法以外，还可以使用其他方法(例如道路分割法等) 来生成表示历史运动轨迹的轨迹序列。此外，可以用类似的方法生成表示对象 的目标运动轨迹的轨迹序列(以下可称为目标轨迹序列)，其中，该目标轨迹序 列中的元素表示目标运动轨迹上的对应点。

在生成表示各条历史运动轨迹的轨迹序列之后，可以确定各个轨迹序列中 的每个元素在所有轨迹序列中的出现次数。然后，可以将每个元素的出现次数 与所述第一阈值进行比较。如果某个元素的出现次数大于第一阈值，则可以将 该元素确定为频繁元素，并且将该元素对应的历史运动轨迹上的点确定为频繁 点。作为示例，假设存在三条历史运动轨迹，其轨迹序列分别可表示为 Tr1＝ABCDF、Tr2＝DAC和Tr3＝CDAE，并且第一阈值被设置为2，则可以确定 这三个轨迹序列中的元素A、C和D为频繁元素，并且它们对应的历史运动轨 迹上的点为频繁点。

返回图3，在步骤S302中，从各条历史运动轨迹上包括所述频繁点的轨迹 区段中，选择可信度大于第二阈值的至少一个轨迹区段，其中所述可信度表示 所述轨迹区段与目标运动轨迹的缺失部分相同的可能性。可信度越大，则所述 轨迹区段与目标运动轨迹的缺失部分相同的可能性越大。所述第二阈值可以是 根据实际需要选择的值。这一操作的目的在于找出历史运动轨迹上最有可能与 目标运动轨迹的缺失部分相同的轨迹区段，以便随后利用所找出的轨迹区段来 构建所述缺失部分。

在本发明的一个实施例中，包括所述频繁点的轨迹区段可以是以所述频繁 点为起点的区段。下面，将参照图5来详细描述在这种实现方式中步骤S302 的操作。

如图5所示，在步骤S3021中，从各条历史运动轨迹上以所述频繁点为起 点的轨迹区段中，选择至少一个长度(例如，经过的点的数量)大于第三阈值 的轨迹区段，作为参考轨迹区段。所述至少一个参考轨迹区段将用于后续的操 作。所述第三阈值可以是根据实际需要选择的值，例如可以将第三阈值设置为 2。具体地，在将各条历史运动轨迹表示为轨迹序列的情况下，可以从各个轨迹 序列中分别以与各个频繁点对应的频繁元素开头的子序列中，选择至少一个长 度(即，元素的数量)大于第三阈值的子序列，作为与以所述频繁点为起点的 参考轨迹区段对应的参考子序列，从而确定所述参考轨迹区段。例如，在上述 三条历史运动轨迹的示例中，假设第三阈值为2，由于频繁元素为A、C和D (假设对应的频繁点为A’、B’和C’)，因此，在表示这三条历史运动轨迹的轨 迹序列中以元素A开头的子序列为ABCDF、AC和AE，以元素C开头的子序 列为CDF、C和CDAE，以元素D开头的子序列为DF、DAC和DAE。可以从 这些子序列中，选择长度(即，元素数量)大于2的子序列ABCDF、CDF、 CDAE、DAC和DAE，作为分别与以频繁点A’、B’和C’为起点的轨迹区段对 应的参考子序列。在本发明的一个实施例中，可以将所选择的参考轨迹区段或 参考子序列的数据存储在参考数据库中。

可以看到，通过上述步骤S301和步骤S3021，可以从多条历史运动轨迹中， 仅提取以频繁点作为起点并且长度大于预定长度的轨迹区段来进行后续的分析 操作，从而减少要在后续的分析操作中分析的数据量，提高构建缺失部分的效 率。当历史运动轨迹数量较多或者在步骤S3021提取的参考子序列较多时，可 以适当地调整所述第一阈值和第三阈值，并且基于调整后的第一阈值和第三阈 值再次执行步骤S301和步骤S3021，以进一步减少在步骤S3021提取的参考子 序列的数量。上述调整第一阈值和第三阈值并且再次执行步骤S301和步骤 S3021的操作可以重复执行，直到在步骤S3021提取的参考子序列的数量小于 预设的阈值为止，或者直到达到预设的重复执行次数为止。

继续参照图5，在步骤S3022中，计算所述参考轨迹区段与目标运动轨迹 的相似度。

在本发明的实施例中，可以将目标运动轨迹划分为多个区段，其中至少一 个区段包含要构建的缺失部分，然后，计算所述参考轨迹区段与目标运动轨迹 的包含所述缺失部分的轨迹区段(为便于描述，以下可称为缺失轨迹区段)的 相似度，作为所述参考轨迹区段与目标运动轨迹的相似度。

具体地，首先，可以找出与每个参考轨迹区段对应的参考子序列和表示目 标运动轨迹的目标轨迹序列中与缺失轨迹区段对应的子序列(以下可称为缺失 子序列)之间的最长公共子序列(LCS)。可以使用多种方法来找出所述LCS。 例如，可以通过本领域公知的用于寻找两个序列之间的LCS的LCS算法来找 出所述参考子序列与缺失子序列之间的LCS。可替换地，可以从所述参考子序 列的元素中，找出与缺失子序列两端的元素距离最近的两个元素，并且将所述 参考子序列中所找出的这两个元素之间的子序列，作为所述LCS。例如，假设 参考子序列为ABCDF，缺失子序列为GHJ，并且在元素A、B、C、D和F中 距缺失子序列两端的元素G和J距离最近的两个元素分别为A和C，则所述参 考子序列ABCDF和缺失子序列GHJ之间的LCS为ABC。

然后，可以基于所述参考子序列和缺失子序列之间的LCS的长度、该参考 子序列的长度以及该缺失子序列的长度，计算所述参考子序列与该缺失子序列 的相似度，作为所述参考轨迹区段与目标运动轨迹的相似度。可以认识到，所 述LCS的长度越长，并且所述参考子序列和缺失子序列各自的长度越短，所述 LCS占参考子序列和缺失子序列的比例越大，所述参考子序列和所述缺失子序 列就越相似。基于这一认识，例如可以使用下式(1)来计算每个参考子序列与 该缺失子序列的相似度sim：

$\mathrm{sim}=\frac{\mathrm{lcslength}}{\sqrt{\mathrm{mlength}\times \mathrm{rlength}}}---\left(1\right)$

其中，lcslength是所述LCS的长度，mlength是缺失子序列的长度，rlength是 参考子序列的长度。在上文所述的例子中，由于参考子序列为ABCDF，缺失子 序列为GHJ，LCS为ABC，因此lcslength为3，mlength为3，rlength为5，则 该参考子序列与该缺失子序列的相似度sim为应当认识到，上式(1) 只是说明性的，而非限制性的，也可以使用其他公式(例如下式(2))来计算 所述相似度sim：

$\mathrm{sim}=\frac{\mathrm{lcslength}}{\mathrm{mlength}+\mathrm{rlength}}---\left(2\right)$

接下来，在步骤S3023中，基于所述参考轨迹区段与目标运动轨迹的相似 度以及所述参考轨迹区段的出现频率，计算所述参考轨迹区段的可信度。

具体地，可以计算所述参考轨迹区段的可信度，使得所述参考轨迹区段与 目标运动轨迹的相似度越大，则所述每个参考轨迹区段的可信度越大。或者， 可以计算所述参考轨迹区段的可信度，使得所述每个参考轨迹区段的出现频率 越大，则所述每个参考轨迹区段的可信度越大。这是因为：所述参考轨迹区段 与目标运动轨迹的相似度越大，目标运动轨迹的缺失部分与参考轨迹区段的对 应部分相同的可能性就越大；另一方面，对于相似度相同的两个参考轨迹区段， 如果一个参考轨迹区段出现频率更高，则说明对象更有可能沿着该参考轨迹区 段行进，因此，该参考轨迹区段与目标运动轨迹的缺失部分相同的可能性就越 大。基于此，例如可以使用下式(3)来计算每个参考轨迹区段的可信度Cre：

Cre＝rfrequency×sim(3)

其中，rfrequency表示该参考轨迹区段在过去一段时间内的出现频率，sim是该 参考轨迹区段与缺失轨迹区段的相似度(即，与该参考轨迹区段对应的参考子 序列与缺失子序列的相似度)。当然，除了上式(3)以外，也可以使用其他公 式(例如下式(4))来计算所述可信度：

Cre＝rfrequency+sim(4)。

然后，在步骤S3024中，选择可信度大于第二阈值的至少一个参考轨迹区 段，作为要在随后的步骤S303中用于构建缺失部分的至少一个轨迹区段。可替 换地，也可以按照可信度的降序选择预定数量的参考轨迹区段，作为要在随后 的步骤S303中用于构建缺失部分的至少一个轨迹区段。

在本发明的另一实施例中，包括所述频繁点的轨迹区段可以是以所述频繁 点为终点的区段，在这种情况下，只需要将针对上述实施例的描述中的“起点 ”简单地替换为“终点”，将“以…开头”简单地替换为“以…结尾”即可。换 言之，本说明书中所述的包括所述频繁点的轨迹区段可以是以所述频繁点为端 点的区段。

在本发明的再一实施例中，所述历史运动轨迹上包括所述频繁点的轨迹区段 是其端点与所述频繁点之间的距离小于预定值的轨迹区段。换言之，包括所述 频繁点的轨迹区段也可以是包含所述历史运动轨迹上以所述点为端点的轨迹区 段、并且比所述以所述点为端点的轨迹区段长预定值的轨迹区段。所述预定值 可以是根据实际需要设定的值。例如，可以设定所述预定值，使得包括所述频 繁点的轨迹区段也可以是包含所述历史运动轨迹上以所述点为端点的轨迹区 段、并且比所述以所述点为端点的轨迹区段略长的轨迹区段。在该实施例中， 可以按照与在上文中针对图5描述的方式类似的方式，从所述历史运动轨迹上 包括所述频繁点的轨迹区段中，选择至少一个长度大于第三阈值的轨迹区段， 作为参考轨迹区段，计算所述参考轨迹区段与目标运动轨迹的相似度，并且基 于所述参考轨迹区段与目标运动轨迹的相似度以及所述参考轨迹区段的出现频 率，计算所述参考轨迹区段的可信度，然后从所述至少一个参考轨迹区段中， 选择可信度大于第二阈值的至少一个轨迹区段，作为要在随后的步骤S303中用 于构建缺失部分的至少一个轨迹区段。

返回图3，在步骤S303中，可以利用所选择的至少一个轨迹区段(即，上 述参考轨迹区段)，构建所述目标运动轨迹的缺失部分。具体地，可以使用所选 择的至少一个轨迹区段之一(例如可信度最高的轨迹区段)，作为目标运动轨迹 的缺失部分，从而构建该缺失部分。在上文所述的例子中，假设在所选择的至 少一个轨迹区段中，与参考子序列ABCDF对应的参考轨迹区段的可信度最高， 则可以使用该参考轨迹区段作为目标运动轨迹中的缺失部分(即，将目标轨迹 序列中的缺失子序列GHJ替换为参考子序列ABCDF)，从而构建所述缺失部分。 可替换地，可以使用所选择的至少一个轨迹区段的组合(例如以加权平均的方 式组合所述至少一个轨迹区段)，作为目标运动轨迹的缺失部分，从而构建该缺 失部分。例如，在使用所选择的两个轨迹区段的组合来构建所述缺失部分的情 况下，可以计算这两个轨迹区段上的各个点的位置坐标的平均值，从而获得由 具有所计算的平均位置坐标的点形成的组合轨迹区段，然后使用该组合轨迹区 段作为目标运动轨迹的所述缺失部分。当然，除了上述方法以外，也可以使用 其他方法来构建所述缺失部分。

这样，利用根据本发明实施例的上述方法，可以从对象的历史运动轨迹中 提取与该对象的目标运动轨迹中的缺失部分相同的可能性高的轨迹区段，然后 利用所提取的轨迹区段来构建所述目标运动轨迹的缺失部分。由于这种方法不 依赖于具体的地图或路网，并且考虑了对象的习惯以根据对象频繁行进的轨迹 来构建缺失部分，因此具有较高的准确性。

前面已经参考附图描述了实现本发明的方法的实施例。本领域技术人员 可以理解的是，上述方法既可以以软件方式实现，也可以以硬件方式实现，或 者通过软件与硬件相结合的方式实现。并且，本领域技术人员可以理解，通过 以软件、硬件或者软硬件相结合的方式实现上述方法中的各个步骤，可以提供 一种基于相同发明构思的用于构建对象的目标运动轨迹的缺失部分的设备。即 使该设备在硬件结构上与通用处理设备相同，由于其中所包含的软件的作用， 使得该设备表现出区别于通用处理设备的特性，从而形成本发明的各个实施例 的设备。本发明中所述设备包括若干单元或模块，所述单元或模块被配置为执 行相应步骤。本领域的所述技术人员通过阅读本说明书可以理解如何编写程序 实现所述单元或模块执行的动作。

下面将参考图6具体描述根据本发明实施例的构建对象的目标运动轨迹的 缺失部分的设备。由于所述设备与上述方法基于相同的发明构思，因此其中相 同或相应的实现细节同样适用于与上述方法对应的设备，由于其在上文中已经 进行了详细和完整的描述，因此在下文中可能不再进行赘述。

如图6所示，根据本发明实施例的构建对象的目标运动轨迹的缺失部分的 设备(以下称为构建设备)600可以包括确定装置601、选择装置602和构建装 置603。可选地，所述构建设备600还可以包括存储装置604，以用于存储上文 所述的数据库。

确定装置601可以确定对象的历史运动轨迹上出现次数大于第一阈值的 点。具体地，如图7所示，确定装置601可以包括序列生成单元6011和确定单 元6012。序列生成单元6011可以对于每条历史运动轨迹，生成表示该历史运 动轨迹的轨迹序列。该轨迹序列可以包含多个元素，每个元素对应于该历史运 动轨迹上的一个点，并且每个元素可以包括在历史运动轨迹上与该元素对应的 点的位置(即上文所述的Loc)，并且可选地，还可以包括对象沿着所述历史运 动轨迹行进时经过与该元素对应的点的时间(即上文所述的Time)。序列生成 单元6011可以按照上文所述的各种方法来生成表示历史运动轨迹的轨迹序列， 在这里省略其详细描述。此外，序列生成单元6011可以用类似的方法生成表示 对象的目标运动轨迹的轨迹序列(即，目标轨迹序列)，其中，该目标轨迹序列 中的元素表示目标运动轨迹上的对应点。确定单元6012可以确定序列生成单元 601生成的各个轨迹序列中的每个元素在所有轨迹序列中的出现次数，然后可 以将每个元素的出现次数与所述第一阈值进行比较，将出现次数大于第一阈值 的元素确定为频繁元素，并且将该元素对应的历史运动轨迹上的点确定为频繁 点。

返回图6，选择装置602可以从各条历史运动轨迹上包括所述频繁点的轨 迹区段中，选择可信度大于第二阈值的至少一个轨迹区段，其中所述可信度表 示所述轨迹区段与目标运动轨迹的缺失部分相同的可能性。可信度越大，则所 述轨迹区段与目标运动轨迹的缺失部分相同的可能性越大。所述第二阈值可以 是根据实际需要选择的值。如上文所述，在本发明的实施例中，历史运动轨迹 上包括所述频繁点的轨迹区段可以是以下三种中的至少一种：所述历史运动轨 迹上以所述点为起点的轨迹区段；所述历史运动轨迹上以所述点为终点的轨迹 区段；所述历史运动轨迹上包括所述频繁点的轨迹区段是其端点与所述频繁点 之间的距离小于预定值的轨迹区段，换言之，包含所述历史运动轨迹上以所述 点为端点的轨迹区段、并且比所述以所述点为端点的轨迹区段长预定值的轨迹 区段。在下文中，为简单起见，以包括所述频繁点的轨迹区段是以所述点为起 点的轨迹区段为例来进行描述，该描述在经过必要的调整之后可以适用于其他 两种情况。

具体地，如图8所示，选择装置602可以包括第一选择单元6021、相似度 计算单元6022、可信度计算单元6023和第二选择单元6024。

第一选择单元6021可以从各条历史运动轨迹上以所述频繁点为起点的轨 迹区段中，选择至少一个长度大于第三阈值的轨迹区段，作为参考轨迹区段。 所述至少一个参考轨迹区段将用于后续的操作。所述第三阈值可以是根据实际 需要选择的值。具体地，在将各条历史运动轨迹表示为轨迹序列的情况下，第 一选择单元6021可以从各个轨迹序列中分别以与各个频繁点对应的频繁元素 开头的子序列中，选择至少一个长度大于第三阈值的子序列，作为与参考轨迹 区段对应的参考子序列，从而确定所述参考轨迹区段。

相似度计算单元6022可以计算所述参考轨迹区段与目标运动轨迹的相似 度。具体地，在本发明的实施例中，相似度计算单元6022可以将目标运动轨迹 划分为多个区段，其中至少一个区段包含要构建的缺失部分，然后计算所述参 考轨迹区段与目标运动轨迹的包含所述缺失部分的轨迹区段(即上述缺失轨迹 区段)的相似度，作为所述参考轨迹区段与目标运动轨迹的相似度。具体地， 首先，相似度计算单元6022可以找出与每个参考轨迹区段对应的参考子序列和 表示目标运动轨迹的目标轨迹序列中与缺失轨迹区段对应的子序列(即，上述 缺失子序列)之间的LCS。然后，相似度计算单元6022可以基于每个参考子序 列和缺失子序列之间的LCS的长度、该参考子序列的长度以及该缺失子序列的 长度，计算每个参考子序列与该缺失子序列的相似度，作为每个参考轨迹区段 与目标运动轨迹的相似度。

可信度计算单元6023可以基于所述参考轨迹区段与目标运动轨迹的相似 度以及所述参考轨迹区段的出现频率，计算所述参考轨迹区段的可信度。具体 地，可信度计算单元6023可以计算所述参考轨迹区段的可信度，使得所述参考 轨迹区段与目标运动轨迹的相似度越大，则所述参考轨迹区段的可信度越大， 或者，使得所述参考轨迹区段的出现频率越大，则所述参考轨迹区段的可信度 越大。

第二选择单元6024可以选择可信度大于第二阈值的至少一个参考轨迹区 段，作为要在随后的构建操作中用于构建缺失部分的至少一个轨迹区段。可替 换地，第二选择单元6024也可以按照可信度的降序选择预定数量的参考轨迹区 段，作为要在随后的构建操作中用于构建缺失部分的至少一个轨迹区段。

返回图6，构建装置603可以利用所选择的至少一个轨迹区段(即，上述 参考轨迹区段)，构建所述目标运动轨迹的缺失部分。如上文所述，构建装置 603可以使用所选择的至少一个轨迹区段之一，作为目标运动轨迹的缺失部分， 从而构建该缺失部分。可替换地，可以使用所选择的至少一个轨迹区段的组合， 作为目标运动轨迹的缺失部分，从而构建该缺失部分。

这样，利用根据本发明实施例的上述构建设备，可以从对象的历史运动轨 迹中提取与该对象的目标运动轨迹相同的可能性高的轨迹区段，然后利用所提 取的轨迹区段来构建所述目标运动轨迹的缺失部分。这样的构建设备不依赖于 对象所在区域的地图和路网，并且具有较高的准确性。

应当认识到，上文所述的根据本发明实施例的方法和设备只是说明性的， 而非限制性的，本领域技术人员可以对其做出各种改变，而不背离本发明的范 围。例如，尽管在上文中提到使用对象的历史轨迹来构建该对象的目标运动轨 迹的缺失部分，但这不是限制性的。在其他实施例中，所述对象可以包括多个 主体，为了构建主体的目标运动轨迹的缺失部分，也可以使用另一个主体的历 史运动轨迹，只要可以根据所述另一个主体的历史运动轨迹确定所述一个主体 的历史运动轨迹即可。此外，在计算可信度时，除了考虑相似度和出现频率以 外，还可以考虑每条轨迹对应的时间。具体地，当从出发地行进到目的地时， 人们在不同的时间(例如白天和晚上)可能采用不行的轨迹，因此，在按照上 式(3)计算的可信度上可以附加与时间有关的系数，使得与目标运动轨迹处于 相同时段的参考轨迹区段的可信度比与目标运动轨迹处于不同时段的参考轨迹 区段更高。此外，尽管在上文中参照图5描述的根据本发明实施例的方法的步 骤S302包括步骤S3021-S3024，但这不是限制性的，也可以省略步骤S3021， 并且在步骤S3022中计算以所述频繁点为起点的轨迹区段与目标运动轨迹的相 似度；可选地，还可以修改步骤S3023，使得在该步骤中直接使用在步骤S3022 中计算的相似度作为所述可信度。上述变化也同样适用于根据本发明实施例的 构建设备600中的选择装置602。

本发明可以是系统、方法和/或计算机程序产品。计算机程序产品可以包 括计算机可读存储介质，其上载有用于使处理器实现本发明的各个方面的计算 机可读程序指令。

计算机可读存储介质可以是可以保持和存储由指令执行设备使用的指令 的有形设备。计算机可读存储介质例如可以是――但不限于――电存储设备、 磁存储设备、光存储设备、电磁存储设备、半导体存储设备或者上述的任意合 适的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：便携 式计算机盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦式 可编程只读存储器(EPROM或闪存)、静态随机存取存储器(SRAM)、便携 式压缩盘只读存储器(CD-ROM)、数字多功能盘(DVD)、记忆棒、软盘、 机械编码设备、例如其上存储有指令的打孔卡或凹槽内凸起结构、以及上述的 任意合适的组合。这里所使用的计算机可读存储介质不被解释为瞬时信号本 身，诸如无线电波或者其他自由传播的电磁波、通过波导或其他传输媒介传播 的电磁波(例如，通过光纤电缆的光脉冲)、或者通过电线传输的电信号。

这里所描述的计算机可读程序指令可以从计算机可读存储介质下载到各个 计算/处理设备，或者通过网络、例如因特网、局域网、广域网和/或无线网下 载到外部计算机或外部存储设备。网络可以包括铜传输电缆、光纤传输、无线 传输、路由器、防火墙、交换机、网关计算机和/或边缘服务器。每个计算/处 理设备中的网络适配卡或者网络接口从网络接收计算机可读程序指令，并转发 该计算机可读程序指令，以供存储在各个计算/处理设备中的计算机可读存储 介质中。

用于执行本发明操作的计算机程序指令可以是汇编指令、指令集架构 (ISA)指令、机器指令、机器相关指令、微代码、固件指令、状态设置数 据、或者以一种或多种编程语言的任意组合编写的源代码或目标代码，所述编 程语言包括面向对象的编程语言—诸如Smalltalk、C++等，以及常规的过程式 编程语言—诸如“C”语言或类似的编程语言。计算机可读程序指令可以完全地 在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执 行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或 服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的 网络—包括局域网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连 接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。在一些实 施例中，通过利用计算机可读程序指令的状态信息来个性化定制电子电路，例 如可编程逻辑电路、现场可编程门阵列(FPGA)或可编程逻辑阵列(PLA)， 该电子电路可以执行计算机可读程序指令，从而实现本发明的各个方面。

这里参照根据本发明实施例的方法、装置(系统)和计算机程序产品的流 程图和/或框图描述了本发明的各个方面。应当理解，流程图和/或框图的每个 方框以及流程图和/或框图中各方框的组合，都可以由计算机可读程序指令实 现。

这些计算机可读程序指令可以提供给通用计算机、专用计算机或其它可 编程数据处理装置的处理器，从而生产出一种机器，使得这些指令在通过计算 机或其它可编程数据处理装置的处理器执行时，产生了实现流程图和/或框图 中的一个或多个方框中规定的功能/动作的装置。也可以把这些计算机可读程 序指令存储在计算机可读存储介质中，这些指令使得计算机、可编程数据处理 装置和/或其他设备以特定方式工作，从而，存储有指令的计算机可读介质则 包括一个制造品，其包括实现流程图和/或框图中的一个或多个方框中规定的 功能/动作的各个方面的指令。

也可以把计算机可读程序指令加载到计算机、其它可编程数据处理装置、 或其它设备上，使得在计算机、其它可编程数据处理装置或其它设备上执行一 系列操作步骤，以产生计算机实现的过程，从而使得在计算机、其它可编程数 据处理装置、或其它设备上执行的指令实现流程图和/或框图中的一个或多个 方框中规定的功能/动作。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计 算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图 中的每个方框可以代表一个模块、程序段或指令的一部分，所述模块、程序段 或指令的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。在有 些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺 序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以 按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程 图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的 功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指 令的组合来实现。

以上已经描述了本发明的各实施例，上述说明是示例性的，并非穷尽性 的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精 神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易 见的。本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或 对市场中的技术的技术改进，或者使本技术领域的其它普通技术人员能理解本 文披露的各实施例。