本发明涉及目标轨迹预测，具体而言，涉及一种利用n-gram统计模型的目标轨迹长时预测方法。
背景技术：
1、对于船舶目标，在交通密度大、情况繁杂的海域轨迹预测对保障海上交通安全具有重要意义，利用船舶交通服务系统准确、有效地对船舶的航行轨迹进行及时跟踪和预测是海上交通事故预警的重要技术支撑。对于空中目标，轨迹预测是空域交通管理中的一项重要技术，对飞行器的轨迹实现精准的预测，是实现空域交通管理智能化的一个必要条件。精准的轨迹预测可以提高空域交通管理的效率，而不准确的轨迹预测会造成空域交通管理的混乱，增加飞行器的飞行危险系数。
2、轨迹预测主要是基于目标历史运动轨迹，对未来可能的位置进行预测。传统的基于运动学模型的船舶目标轨迹预测算法，大都采用kalman滤波算法、改进kalman滤波算法以及自适应滤波等算法，通过对目标的位置、速度等剖面建立运动方程模型，实现对目标轨迹的预测，由于可以根据目标位置报文等数据不断对预测结果进行修正，往往容易达到实际应用所需的精度。由于运动学模型难以精确建模，因此，基于运动学模型的目标位置预测算法一般用于目标的短时(未来几分钟之内)预测，其预测误差会随着预测时间的变长而急剧增大，因此，该类方法不适用于完成对目标较长时间内轨迹进行预测的任务。
3、除卡尔曼滤波和灰度预测等传统预测算在船舶轨迹预测方面得到应用外，有学者使用简单的神经网络进行了船舶轨迹的探究，也有学者提出了一些基于深度学习模型的船舶轨迹预测模型，但预测时间都较短。
4、目标轨迹的长时预测一般预测时间较长，如30分钟～1小时，在实际中具有更多的应用场景。目前，主流的轨迹长时预测方法包括经典轨迹匹配法和航路模型构建法。经典轨迹匹配法需要首先进行目标经典轨迹的提取，然后将目标实时轨迹与目标经典轨迹数据库进行比对，进而实现对目标未来可能轨迹的预测，其研究重点有以下两点：一是目标经典轨迹的提取，目前已有很多方法，但是完整的、连续的经典轨迹提取还未完全突破；二是，目标实时轨迹与经典轨迹的匹配问题，主要转化为轨迹的相似性度量问题来研究，实时环境下的相似性度量准则设计是其关键。航路模型法则主要是通过建立目标性能模型、航路模型、环境模型来实现对目标全航路的预测，模型建立困难，主要用于航线规划领域，不适用于实时轨迹预测场景。
5、因此，在当前条件下，对于长时间目标轨迹的预测，通常利用目标历史轨迹数据来完成，并且采用两段式预测方法：首先基于目标历史轨迹的挖掘出的目标经典轨迹规律，然后通过相似性轨迹匹配，实现对目标长时间航线的预测，但是存在经典轨迹挖掘难、轨迹相似度实时匹配难等问题。
技术实现思路
1、为了更好的实现对目标轨迹的长时间预测，本发明旨在提供一种利用n-gram统计模型的目标轨迹长时预测方法，以解决现有经典轨迹挖掘—轨迹匹配两段式预测存在的规律挖掘难、轨迹匹配难等问题。
2、本发明提供的一种利用n-gram统计模型的目标轨迹长时预测方法，包括如下步骤：
3、步骤1，构建目标轨迹语料库；
4、步骤2，基于目标轨迹语料库，构建基于n-gram统计模型的预测模型；
5、步骤3，基于构建的预测模型和目标实时轨迹对设定预测时间之内的轨迹进行预测。
6、进一步的，步骤1包括如下子步骤：
7、步骤1.1，对于选定的目标历史轨迹，基于时间间隔进行轨迹分割，得到分割后的轨迹序列集合；
8、步骤1.2，针对轨迹序列集合，以geohash编码为基础，构建编码集合；
9、步骤1.3，重复执行步骤1.1～步骤1.2直到所有的目标历史轨迹均被处理，得到全部历史轨迹对应的编码集合，形成以geohash编码为表示方式的目标轨迹语料库。
10、进一步的，步骤1.1中，所述基于时间间隔进行轨迹分割包括：
11、计算目标历史轨迹中所有相邻观测点之间的时间间隔序列；
12、取时间间隔序列的一个分位数作为时间间隔分割门限；
13、将目标历史轨迹中所有相邻观测点之间的时间间隔序列中所有大于分割门限的位置作为分割点，实现对选定的目标历史轨迹的分割，得到相应的轨迹序列集合。
14、进一步的，步骤1.2中，所述构建编码集合包括：
15、针对轨迹序列集合中每条子轨迹序列，首先，基于geohash编码规则和指定的编码长度，对轨迹序列集合中的子轨迹序列进行编码，得到编码序列；然后，去除相邻编码之间的重复编码；接着，针对去重之后的编码序列，检测相邻编码之间是否连通，在不连通编码之间，基于最短原则补充缺失编码，最后，在编码序列末尾添加结束编码，得到geohash编码序列；记录所有子轨迹序列的geohash编码序列，形成编码集合。
16、进一步的，步骤2中，所述n-gram统计模型采用2元统计模型、三元统计模型或更高的统计模型。
17、进一步的，步骤2中，所述构建基于n-gram统计模型的预测模型包括：
18、统计目标轨迹语料库中1元编码出现的频率，形成1元编码频率表；
19、同理，统计目标轨迹语料库中2～n元编码出现的频率，形成2～n元编码频率表；
20、将1元编码频率表和2～n元编码频率表共同构成预测模型。
21、进一步的，步骤3包括如下子步骤：
22、步骤3.1，基于期望的预测时间、目标速度和网格大小，估计轨迹待预测步数lp：
23、lp＝ceil(v×tp/csize)
24、其中，v为目标速度，一般为目标前几个时刻的平均速度，tp为预测时间，csize为geohash编码长度对应的网格大小；
25、步骤3.2，计算目标实时轨迹的初始geohash编码；针对基于n-gram统计模型的预测模型，需要计算截止到最新时刻的n-1个初始geohash编码，且需要满足相邻编码不存在重复编码和缺失编码；
26、步骤3.3，基于目标实时轨迹的初始geohash编码和轨迹待预测步数，利用构建的基于n-gram统计模型的预测模型，结合地理拓扑和束搜索方法进行目标轨迹预测。
27、进一步的，步骤3.3包括如下子步骤：
28、步骤3.3.1，判断目标连续n-1个初始geohash编码是否存在于n-1元编码频率表中，若不存在，则直接中止预测，返回无法实施预测的消息；
29、步骤3.3.2，结合目标只能做上下左右运动的地理拓扑约束，根据目标实时或预测轨迹的最后1个编码值，提取计算目标下步可行动编码；
30、步骤3.3.3，基于n-1元编码频率表和n元编码频率表，计算由连续n-1个初始geohash编码转移到每个可行动编码的条件概率序列p；
31、步骤3.3.4，基于条件概率序列和设置的束搜索大小beam_size，提取条件概率序列中前beam_size个最大概率及其对应的可行动编码，将该可行动编码作为预测编码序列，并按照束搜索算法更新和保存预测编码序列和及其对应的概率，重复执行步骤3.3.2～步骤3.3.4，直到满足任一结束条件；
32、步骤3.3.5，针对beam_size条预测编码序列，根据预测编码序列对应的概率，提取最大概率对应的预测编码序列，并利用geohash解码算法，将geohash编码解码为经纬度坐标，形成预测经纬度序列。
33、进一步的，步骤3.3中，计算由连续n-1个初始geohash编码转移到每个可行动编码的条件概率序列p：
34、
35、其中，pi为由连续n-1个初始geohash编码转移到第i可行动编码的条件概率；gi为第i可行动编码，gn-1为目标实时轨迹连续n-1个初始geohash编码，fn-gram(gn-1,gi)表示(gn-1,gi)编码组合在n元编码频率表中出现的次数，fn-1-gram(gn-1)表示连续编码gn-1在n-1元编码频率表中出现的次数。
36、进一步的，步骤3.4中，所述结束条件包括：
37、条件一：在某次循环中，beam_size条预测编码序列的最新的连续n-1个初始geohash编码都不存在于n-1元编码频率表中；
38、条件二：在某次循环中，条件概率序列的前beam_size个最大概率均为0；
39、条件三：在某次循环中，beam_size条预测编码序列最后的编码均为结束标识符；
40、条件四：达到设定的轨迹待预测步数。
41、综上所述，由于采用了上述技术方案，本发明的有益效果是：
42、1、相比于现有的规律挖掘-轨迹匹配长时预测模式，本发明以一种更加容易的方式，直接利用目标历史轨迹，构建基于n-gram统计模型的预测模型，能够实现端到端长时预测；此外，在数据量少的情况下，本发明预测模型相比于基于深度学习模型的方法在实施长时预测时，具有更好的性能。
43、2、本发明利用geohash编码对目标轨迹进行序列化，可以有效降低轨迹观测误差对于预测模型的影响，提高预测模型的泛化性，从而提高目标轨迹预测的稳定性。
44、3、本发明预测模型在构建和预测时引入了地理拓扑知识约束，能够得到更加合理的预测结果。此外，由于充分考虑目标运动受地理拓扑的限制，在预测时可以大大减少下步位置的搜索范围，从而有效提高预测的效率。
45、4、本发明预测模型具有较强的可扩展性。在进行预测时，除考虑地理拓扑知识外，还可以极为方便的加入地理环境知识和实时气象水文信息，进一步约束目标的轨迹范围，实现更加合理的预测。
1.一种利用n-gram统计模型的目标轨迹长时预测方法，其特征在于，包括如下步骤：
2.根据权利要求1所述的利用n-gram统计模型的目标轨迹长时预测方法，其特征在于，步骤1包括如下子步骤：
3.根据权利要求2所述的利用n-gram统计模型的目标轨迹长时预测方法，其特征在于，步骤1.1中，所述基于时间间隔进行轨迹分割包括：
4.根据权利要求2所述的利用n-gram统计模型的目标轨迹长时预测方法，其特征在于，步骤1.2中，所述构建编码集合包括：
5.根据权利要求1所述的利用n-gram统计模型的目标轨迹长时预测方法，其特征在于，步骤2中，所述n-gram统计模型采用2元统计模型、三元统计模型或更高的统计模型。
6.根据权利要求5所述的利用n-gram统计模型的目标轨迹长时预测方法，其特征在于，步骤2中，所述构建基于n-gram统计模型的预测模型包括：
7.根据权利要求6所述的利用n-gram统计模型的目标轨迹长时预测方法，其特征在于，步骤3包括如下子步骤：
8.根据权利要求7所述的利用n-gram统计模型的目标轨迹长时预测方法，其特征在于，步骤3.3包括如下子步骤：
9.根据权利要求8所述的利用n-gram统计模型的目标轨迹长时预测方法，其特征在于，步骤3.3中，计算由连续n-1个初始geohash编码转移到每个可行动编码的条件概率序列p：
10.根据权利要求8所述的利用n-gram统计模型的目标轨迹长时预测方法，其特征在于，步骤3.4中，所述结束条件包括：
