本发明涉及信号处理，具体而言，涉及一种海量顶点的多段线简化的分布式并行方法和系统。
背景技术：
1、随着移动智能传感器、物联网等技术快速发展，带高精度、细粒度、大范围的空间轨迹数据呈爆炸式增长，广泛覆盖交通、地理、城市管理等领域。空间轨迹本质上可以看成由多个顶点组成的多段线，而物联感知设备所获取的空间位置信息可由多段线上的每一顶点表达。因此，如何通过多段线简化算法从轨迹中寻找关键顶点，删除对轨迹变化趋势影响不大的冗余顶点以有效减少数据量，从而进一步减轻存储和计算压力已成了一项关键技术问题。
2、为了解决这一技术问题，现有技术提出了一种名为道格拉斯-普克算法，该算法是一种多段线简化方法，主要流程如下：
3、步骤一、对多段线的首末顶点虚连一条直线，求多段线上所有顶点各自与该直线的距离，并找出最大距离值。
4、步骤二、用最大距离值与事先给定的阈值d相比，若最大距离小于阈值d，则将该多段线上除首末以外的顶点全部舍去，并将步骤一中该多段线首末顶点虚连的直线作为多段线的近似，该多段线处理完毕；若最大距离大于或等于阈值d，则保留该多段线中距离大于或等于该阈值d的所有顶点，并以这些坐标中距离最小的顶点为界，把多段线分为两部分，形成两条子多段线。
5、步骤三、对步骤二处理得到的这两条子多段线分别重复使用该方法的步骤一和二，直到所有最大距离均小于阈值d，即完成对多段线的简化。
6、然而，现有技术的多段线简化算法主要针对于顶点数较少的多段线简化，随着数据获取能力日益增强，轨迹多段线上顶点呈海量式，导致该类算法无法满足实际响应需求。
技术实现思路
1、本发明的目的在于克服现有技术缺陷，且提供了一种海量顶点的多段线简化的分布式并行方法和系统。
2、本发明提供的一种海量顶点的多段线简化的分布式并行方法，其技术方案如下：
3、一种海量顶点的多段线简化的分布式并行方法，所述分布式并行方法包括如下步骤：
4、s1、将由信号采集装置所获多段线按该多段线上所有顶点夹角的变化规律将该多段线割成若干子多段线，并分别进行特征标识后存储；
5、s2、分别将每个所述子多段线按其上各顶点同首末顶点虚连线段所成夹角所现分布规律对该所述子多段线进行化简，获得各自对应的化简结果；
6、s3、将所述步骤s2所获每个子多段线对应的化简结果按各自原先所处位置进行首尾相连，获得所述多段线的化简结果。
7、本发明中所提供的分布式并行方法，基于新的理念，通过步骤s1按多段线上所有顶点夹角的变化规律将该多段线割成若干子多段线，随后通过步骤s2将每个子多段线按其上各顶点同首末顶点虚连线段所成夹角所现分布规律对该子多段线进行化简，获得各自对应的化简结果，最后通过步骤s3进行合并，得到整个多段线的化简结果。
8、相比较现有技术的道格拉斯-普克算法，本发明中的分布式并行方法至少具备如下突出有益效果：
9、首先，本发明中的分布式并行方法在将多段线分割为若干子多段线时，基于的是多段线上所有顶点夹角的变化规律，进而计算量减小。对于一多段线，除首末顶点外，其余顶点均为该多段线相邻两边的交点，通常将多段线上相邻两边的夹角称为该多段线的顶点夹角。由背景技术可见，现有的算法，无论是初次分割还是化简，均需要结合多段线上所有顶点到首末顶点虚连线段的距离分布来进行，对于高维数据，该算法的计算量明显较大，本发明的方法与之相比，在处理高维数据量时，计算量明显减小。
10、其次，本发明中的分布式并行方法将子多段线进行化简时，基于每个子多段线按其上各顶点同首末顶点虚连线段所成夹角所现分布规律，由于计算角度的方式简便，无论是低维或高维数据，均具有统一的计算公式，不仅符合多段线的特性，确保不失真，而且化简速率加快，压缩率提高。
11、最后，本发明中的分布式并行方法的适用性广，不仅适用于顶点数较少的多段线简化，还适用于顶点数较多的多段线以及数据维度较高的多段线。
12、作为优选，所述步骤s1包括如下步骤：
13、s11、通过信号采集装置采集特定对象数据，形成该所述特定对象数据所对应的多段线；
14、s12、根据所述步骤s11中特定对象数据的数据特征设置第一阈值；
15、s13、将所述多段线作为当前多段线，通过计算设备分别计算所述当前多段线上各顶点夹角的补角；
16、s14、从所述当前多段线首顶点开始，沿所述当前多段线路径将该当前多段线的所述顶点夹角的补角进行依次累加，且在每次累加后将本次累加结果与所述第一阈值进行比较，若本次累加结果小于所述第一阈值，则判断本次累加是否到达沿所述当前多段线路径的最后一个所述顶点夹角，若已到达，则将所述当前多段线作为子多段线，至此结束分割；若未到达，则执行下一次累加；若本次累加结果不小于所述第一阈值，则执行下一步骤；
17、s15、以本次累加所到达的所述顶点夹角的顶点或边上的点为分割点，将所述当前多段线割成两个子多段线；
18、s16、将所述步骤s15所获两个子多段线分别作为当前多段线，回转执行所述步骤s13，最终获得若干子多段线；
19、通过分别计算多段线上各顶点夹角，并计算出各顶点夹角的补角，根据顶点夹角的补角的每次累加结果与第一阈值的比较情况，把握住该多段线上所有顶点夹角的变化规律，对该多段线进行逐次分割，最终将该多段线割成若干子多段线，整个过程逻辑清晰，过程简便合理。
20、作为优选，所述步骤s2包括如下步骤：
21、s21、通过计算设备分别获取每个所述子多段线上各顶点同本子多段线首末顶点虚连线段所成夹角，获得各自对应的所有夹角；
22、s22、分别根据每个所述子多段线的特征生成各自对应的第二阈值；
23、s23、分别将所述步骤s1所获的每个所述子多段线所对应的所有夹角进行大小排序，获得各自对应的最小夹角信息；
24、s24、分别将所述步骤s23所获的每个所述子多段线所对应的最小夹角数值同本子多段线对应的第二阈值进行比较，若某个所述子多段线所对应的最小夹角数值小于该所述子多段线对应的第二阈值，则将该所述子多段线割成两个子多段线，并作为新的子多段线回转执行所述步骤s21；若某个所述子多段线所对应的最小夹角数值不小于该所述子多段线对应的第二阈值，则将该所述子多段线的首末顶点连接线段作为该所述子多段线的化简结果；
25、通过分别获取每个子多段线上各顶点同本子多段线首末顶点虚连线段所成夹角，进而获得每个子多段线各自对应的所有夹角，随后分别进行排序，获得每个子多段线各自对应的最小夹角信息，把握住每个子多段线按上各顶点同首末顶点虚连线段所成夹角所现分布规律，对每个子多段线进行化简，获得各自对应的化简结果，算法复杂度小，压缩率高。
26、作为优选，所述分布式并行方法还包括：
27、s4、判断所述步骤s3所获多段线的化简结果是否达到精简标准，若已达到标准则结束化简；若未达到标准则回转执行所述步骤s1；
28、对于化简结果不够精简的，可再次化简，进而确保化简结果精简合理，为化简结果的进一步利用提供保障。
29、本发明提供的一种海量顶点的多段线简化的分布式并行系统，其技术方案如下：
30、一种海量顶点的多段线简化的分布式并行系统，基于本发明中所述的海量顶点的多段线简化的分布式并行方法，所述分布式并行系统包括建立通信关系的：
31、信号采集装置，用于采集特定对象数据，形成该所述特定对象数据所对应的多段线；
32、主节点模块，用于将由所述信号采集装置所获多段线按该多段线上所有顶点夹角的变化规律将该多段线割成若干子多段线，且分别输出；
33、标记存储模块，用于将所述主节点模块所输出的若干子多段线进行分别标记，形成各自对应的特征标识符，并根据各自对应的特征标识符对各自的特征信息进行存储，以供使用或处理；
34、至少一个从节点模块，每个所述从节点模块被设置为每次于所述标记存储模块获取一个所述子多段线，并将本次所获的子多段线按该子多段线上各顶点同首末顶点虚连线段所成夹角所现分布规律对该所述子多段线进行化简，获得本次所述子多段线对应的化简结果；
35、合并模块，用于将每个所述从节点模块所获子多段线对应的化简结果按各自原先所处位置进行首尾相连，获得所述多段线的化简结果。
36、本发明中的分布式并行系统，通过设置信号采集装置、主节点模块、标记存储模块、至少一个从节点模块和合并模块，在信号采集装置获取多段线后，可依次由主节点模块进行分割，标记存储模块进行标记和存储，从节点模块进行化简，最后再由合并模块进行合并，完成化简。本发明中的分布式并行系统的运行基于本发明中所述的海量顶点的多段线简化的分布式并行方法，能够解决海量轨迹数据压缩效率慢等问题，为轨迹数据进一步存储和计算奠定基础。
37、作为优选，所述主节点模块包括建立通信关系的：
38、标记单元，用于将由所述信号采集装置所获多段线按特征进行标记，获得该多段线所对应的特征标识符；
39、分割单元，用于将经所述标记单元标记过的多段线进行分割，获得所述若干子多段线，且分别输出；
40、其中，
41、所述标记单元与所述信号采集装置通信，所述分割单元与所述标记存储模块通信；
42、通过设置标记单元对多段线进行标记，可避免后期对子多段线化简结果合并时出现错误或混乱。
43、作为优选，所述标记存储模块包括建立通信关系的：
44、共享队列单元，用于将所述主节点模块所输出的若干子多段线进行分别标记，形成各自对应的特征标识符；
45、共享磁盘单元，用于根据每个所述子多段线所对应的特征标识符对该所述子多段线的特征信息进行存储，以供使用或处理；
46、其中，
47、所述共享队列单元与所述分割单元通信，所述共享磁盘单元与每个所述从节点模块通信；
48、进而可实现对分割形成的子多段线进行一一标记和存储，供使用或处理，而且为后期的化简后合并的合理性与有序性作保障。
49、作为优选，所述分布式并行系统还包括用于巡视每个所述从节点模块的工作状态，并根据巡视结果向特定所述从节点模块分发任务的巡视模块，所述巡视模块与每个所述从节点模块通信，进而可确保从节点模块运行可控。
50、作为优选，所述巡视模块包括：
51、询问单元，用于分别向每个所述从节点模块所在处发送工作询问信号，且在知悉某些所述从节点模块处于闲置状态后，形成对这些所述从节点模块的分别调用指令；
52、至少一个应答单元，与所述从节点模块一一对应通信，每个所述应答单元用于获取与之相应的所述从节点模块工作状态信息，并对所述询问单元所发信号做出应答，以将与之相应的所述从节点模块工作状态信号发送至所述询问单元；
53、执行单元，用于接收由所述询问单元形成的，对某些所述从节点模块的分别调用指令，并根据对这些所述从节点模块的分别调用指令从所述共享磁盘单元中按一对一方式取出待化简的所述子多段线的特征信息一一分发给这些所述从节点模块处理，在分发后将已被分发过的所述子多段线的特征信息于所述共享磁盘单元中删除；
54、其中，
55、所述询问单元与每个所述应答单元通信，所述执行单元与所述询问单元、所述共享磁盘单元通信；
56、进而，在确保从节点模块运行可控的基础上，可实现对从节点模块进行合理调用，确保对子多段线的化简高效有序。
57、作为优选，所述分布式并行系统还包括判断模块，所述判断模块用于接收由所述合并模块所获多段线的化简结果，并判断所述多段线的化简结果是否达到精简标准，若已达到标准则结束化简并输出；若未达到标准则将所述多段线的化简结果发送所述主节点模块，由所述主节点模块再次处理；
58、所述判断模块与所述合并模块通信；
59、进而可确保化简结果合理简洁，至少为多段线化简结果的使用提供范围和精确上的保障。
1.一种海量顶点的多段线简化的分布式并行方法，其特征在于：所述分布式并行方法包括如下步骤：
2.根据权利要求1所述的海量顶点的多段线简化的分布式并行方法，其特征在于：所述步骤s1包括如下步骤：
3.根据权利要求2所述的海量顶点的多段线简化的分布式并行方法，其特征在于：所述步骤s2包括如下步骤：
4.根据权利要求1-3任意一项所述的海量顶点的多段线简化的分布式并行方法，其特征在于：所述分布式并行方法还包括：
5.一种海量顶点的多段线简化的分布式并行系统，其特征在于：基于权利要求1-4任意一项所述的海量顶点的多段线简化的分布式并行方法，所述分布式并行系统包括建立通信关系的：
6.根据权利要求5所述的海量顶点的多段线简化的分布式并行系统，其特征在于：所述主节点模块(2)包括建立通信关系的：
7.根据权利要求6所述的海量顶点的多段线简化的分布式并行系统，其特征在于：所述标记存储模块(3)包括建立通信关系的：
8.根据权利要求7所述的海量顶点的多段线简化的分布式并行系统，其特征在于：所述分布式并行系统还包括用于巡视每个所述从节点模块(4)的工作状态，并根据巡视结果向特定所述从节点模块(4)分发任务的巡视模块(6)，所述巡视模块(6)与每个所述从节点模块(4)通信。
9.根据权利要求8所述的海量顶点的多段线简化的分布式并行系统，其特征在于：所述巡视模块(6)包括：
10.根据权利要求7-9任意一项所述的海量顶点的多段线简化的分布式并行系统，其特征在于：所述分布式并行系统还包括判断模块(7)，所述判断模块(7)用于接收由所述合并模块(5)所获多段线的化简结果，并判断所述多段线的化简结果是否达到精简标准，若已达到标准则结束化简并输出；若未达到标准则将所述多段线的化简结果发送所述主节点模块(2)，由所述主节点模块(2)再次处理；
