一种基于滑动平均算法的车辆轨迹优化方法

摘要

本发明公开了一种基于滑动平均算法的车辆轨迹优化方法，提出一种解决方案：首先将接收到的GPS数据用滑动平均算法进行处理，对定位异常的噪点进行过滤；然后用道格拉斯‑普克算法对去噪之后的数据进行抽稀，在保证轨迹曲线大体不变的情况下将多余的数据剔除，不仅可以让轨迹曲线更平滑，而且可以节省存储空间。车辆在行驶过程中，由于多路径效应和其他复杂环境的影响，接收到的GPS数据都会含有噪点，导致形成的轨迹不能表达车辆的原始行驶路线。本发明在保证轨迹曲线大体不变的情况下将多余的数据剔除，不仅可以让轨迹曲线更平滑，而且可以节省存储空间。实验结果表明：该方法有效的去除了噪点和冗余节点，节约了存储空间，轨迹优化效果明显。

说明书

技术领域

本发明涉及导航定位技术领域，具体设计一种基于滑动平均算法的车辆轨迹优化方法。

背景技术

随着社会经济的发展和LBS(Location Based Services)服务的广泛应用，GPS(Global Positioning System)技术在车辆定位监测的应用已经十分成熟。而基于GPS定位的车辆轨迹显示是地图导航定位和交通管理决策的一项重要功能。其原理是利用GPS技术周期性的获取车辆定位信息，并通过无线网络技术将定位信息发送到远程服务器，服务器后台根据客户端的请求将存放的定位信息进行提取处理，并在电子地图中显示车辆的行驶轨迹。当我们处理GPS设备传过来的数据时，会产生由于设备定位异常所导致的噪点；如果噪点过多，轨迹线就会呈现出非常混乱的折线；同时我们没有必要将所有获取的定位信息都用来绘制轨迹，在保证曲线形状大体不变的情况下将多余的节点剔除。因此，如何保证轨迹曲线平滑的同时又能节省存储空间，成为车辆轨迹优化的关键。

对于此问题，国内外学者对其进行了深入的研究，提出了许多解决方案。Banerjee等人提出了一种基于分段圆弧拟合的平滑算法来对轨迹进行去噪，使用动态程序来寻找给定轨迹的最佳弧拟合。 Benjamin等人提出了一种轨迹优化算法，该方法在考虑各种时变系统约束的情况下以渐进的视界方式生成路径跟踪轨迹。樊庆富等人提出基于偏移量计算的在线GPS轨迹数据压缩算法，较好的保留了轨迹信息。张倩等人提出一种基于GPS和地图匹配的车辆配送路径轨迹弧长偏差可视化校正方法，进行路径偏差校正。

通常来说，设备所收集的GPS定位数据都是含有噪点的，车辆在弯道行驶过程中，由于速度过快，导致两点定位距离较远，用 Cesium的Entity.polyline()函数绘制的轨迹，比较僵硬，不能真实的反应车辆的运动轨迹；通常这些噪点是由于设备异常产生的，在硬件层面提升定位精度的成本太大，因此一般都是通过程序来过滤这些噪点。常用的去噪算法有：非局部均值去噪法、中值滤波法和滑动平均法。非局部均值去噪法需要采集的信息较多，实现过程较为复杂，不利于具体实施。中值滤波算法是把数字图像或数字序列中某一点的值用该点的一个邻域中各点值的中值代替，让周围的像素值更接近真实值，从而消除孤立的噪声点。但该算法过于依赖历史轨迹数据样本。

现有的车辆轨迹优化主要是将绝大部分运算都集中在车载智能终端上，对终端的性能提出了较高的要求。此外，利用专用短程无线通信频繁地传输地图和信号灯数据，也会占用原本就稀缺的信道资源，对存储空间占用量也大。

发明内容

本发明要解决的技术问题是提供一种基于滑动平均算法的车辆轨迹优化方法，以解决现有技术中车辆拐弯时的轨迹精度较低、存储空间占用量大、车辆行驶轨迹匹配路网的准确度低的技术问题。

针对以上轨迹优化中存在的问题，提出一种解决方案如下：首先用滑动平均算法对获取的GPS定位数据进行去噪处理，消除异常轨迹点；然后再引入道格拉斯-普克算法对去噪之后的节点进行抽稀，进一步压缩轨迹节点，节省存储空间；最后将轨迹数据借助Cesium 提供的Entity.polyline进行绘制展示，对比前后的轨迹曲线和轨迹点数量，结果表明，优化后的轨迹平滑效果显著，节省了内存空间。

为解决上述技术问题，本发明采用如下技术方案：

设计一种基于滑动平均算法的车辆轨迹优化方法，包括如下步骤：

S1：获取车辆经纬度数据data；

S2：运用滑动平均算法对获取的经、纬度数据进行去噪处理，根据需要保留的数据节点特性选择合适的滑动窗口大小m；

S3：整理去噪后的数据，确定合适的阈值；

S4：为了去除冗余信息，用道格拉斯-普克算法进行数据抽稀；

S5：处理后的经纬度数据利用Entity.polyline函数标注在地图上进行绘制轨迹曲线，得到真实的车辆行驶路线。

1.根据权利要求1所述的基于滑动平均算法的车辆轨迹优化方法，其特征在于，在步骤S1中，所述滑动平均算法的表达式为：

y(s)＝f(s)+x(s) (2)

其中，f′(s)为平滑后的数据，y(s)为经纬度数据，f(s)为轨迹点中的正常数据，x(s)为轨迹点中的异常数据，m为离散化采集的数据个数，N为滑动窗口大小。

优选的，所述N个采样取值看成一个循环队列，每次采样得到一个新数据放入队尾，并扔掉原来队首的一个数据，遵循先进先出原则，把队列中的N个数据进行滑动平均运算，获得新的滤波结果。

优选的，所述滑动窗口大小N，其取值为6～15。

优选的，获取车辆GPS轨迹点的数据为经纬度数据。

优选的，在步骤S4中，所述道格拉斯-普克算法是将去噪之后的曲线的首末点连成一条直线，求所有中间点与直线的距离，并找出最大距离值max，用max与抽稀阈值value相比较：

若max

若max≥value，则以该点为界，把曲线分为两部分，对这两部分曲线重复上述过程，直至所有的点都被处理完成。

优选的，在步骤S5中，在Cesium上进行轨迹绘制是指在在 Cesium地图中标注出车辆的位置，采用了队列的存储结构对得到的数据信息进行存储，按照先进先出的原则对数据进行处理访问，然后在使用Cesium提供的线函数进行轨迹绘制，从而得到车辆轨迹。

与现有技术相比，本发明的有益技术效果在于：

1.本发明先用滑动平均算法对获取的GPS定位数据进行去噪处理，消除异常轨迹点；然后再引入道格拉斯-普克算法对去噪之后的节点进行抽稀，进一步压缩轨迹节点，节省存储空间；最后将轨迹数据借助Cesium提供的Entity.polyline函数进行绘制展示，对比前后的轨迹曲线和轨迹点数量，结果表明，优化后的轨迹平滑效果显著，节省了内存空间。

2.采用的滑动平均算法，响应快速，计算量小，能有效的消除数据节点中的随机波动。将连续取N个采样值看成一个循环队列，队列长度固定为N，每次采样得到一个新数据放入队尾，并扔掉原来队首的一个数据(先进先出原则)，把队列中的N个数据进行平均运算，就可以获得新的滤波结果。优化后的轨迹对车辆历史轨迹查询、运行状态监测、交通管控、实时交通信息发布、车辆定位与智能调度、轨迹规划、出行路径选择等多个方面具有重要意义。

3.本发明特别针对车辆拐弯时的轨迹偏移进行优化，得到的车辆行驶轨迹更为精确。

附图说明

图1滑动平均算法优化流程；

图2滑动平均滤波前后对比；

图3道格拉斯-普克算法过程图；

图4轨迹优化流程；

图5初始车辆轨迹；

图6去噪之后的轨迹；

图7抽稀之后的轨迹点。

具体实施方式

下面结合附图和实施例来说明本发明的具体实施方式，但以下实施例只是用来详细说明本发明，并不以任何方式限制本发明的范围。

实施例1：一种基于滑动平均算法的车辆轨迹优化方法，包括如下步骤：

S1：获取车辆经纬度数据data；

S2：运用滑动平均算法对获取的经、纬度数据进行去噪处理，根据需要保留的数据节点特性选择合适的滑动窗口大小m；

S3：整理去噪后的数据，确定合适的阈值；

S4：为了去除冗余信息，用道格拉斯-普克算法进行数据抽稀；

S5：处理后的经纬度数据利用Entity.polyline函数标注在地图上进行绘制轨迹曲线，得到真实的车辆行驶路线。

其中，具体为步骤为：

1.基于滑动平均算法对数据去噪

采用的滑动平均算法，响应快速，计算量小，能有效的消除数据节点中的随机波动。其基本思想是：连续取N个采样值看成一个循环队列，队列长度固定为N，每次采样得到一个新数据放入队尾，并扔掉原来队首的一个数据(先进先出原则)，把队列中的N个数据进行平均运算，就可以获得新的滤波结果。滑动平均算法的表达式为：

y(s)＝f(s)+x(s) (2)

其中，f′(s)为平滑后的数据，y(s)为经纬度数据，f(s)为轨迹点中的正常数据，x(s)为轨迹点中的异常数据，m为离散化采集的数据个数，N为滑动窗口大小。

为了更加准确地表示y(s)，减小噪点x(s)的影响，对含有噪声的数据在合适的区间上做局部平均平滑，之后对所有的离散化数据做滑动平滑处理，从而过滤掉噪点。

2.滑动平均算法优化流程

在实际应用中，针对需要保留的数据节点特性选择合适的滤波参数，以达到保留有效数据去除噪点信息的目的。滑动平均滤波参数N 值决定了曲线的平滑程度，N值越大，滤波后的数据越平滑。

在实际应用中，我们通常会加以改进，以当前点为中点，左右各 N/2点进行滑动平均滤波。首先输入原始数据的经纬度信息和滑动窗口的大小，然后初始化参数sum、j、size均为0，再读入经纬度数据点以后，对数据进行滑动平滑处理，最后将处理后的经纬度数据用 Cesium的Entity.polyline函数标注在地图上，绘制轨迹曲线，使优化后的轨迹曲线更能真实的反映车辆的行驶路线。滑动平均算法优化流程如图1所示：

取了30个测试数据对滑动平均算法进行模拟，平滑效果如图2所示：

由图2可以明显看出，N值取4时，滤波效果不是很好，N值取8时，滤波效果已经十分明显。因此，在轨迹去噪的应用中需要根据具体的数据特性进行参数N的选取。

3.道格拉斯-普克算法

道格拉斯-普克算法是线状要素抽稀的经典算法，用它可以处理大量冗余的几何节点，不仅可以达到精简数据的目的，而且能够在很大程度上保留曲线的几何形状不变。算法基本思想是：将待处理曲线的首末点连成一条直线，求所有中间点与直线的距离，并找出最大距离值max，用max与抽稀阈值value相比较：

若max

若max≥value，则以该点为界，把曲线分为两部分，对这两部分曲线重复上述过程，直至所有的点都被处理完成。数据抽稀过程如图3所示：

在曲线首尾两点间连一条直线，求出其余各点到该直线的距离，选其最大者与阈值相比較，若大于阈值，则离该直线距离最大的点保留，否则将直线两端点间所有的点舍去，根据所保留的点，将已知曲线分成两部分，反复进行迭代操作，依次取舍，直到无点可选，最后得到满足给定精度限差的坐标。对去噪之后的数据进行抽稀，可以去除冗余数据，同时保留关键节点，不仅可以获得精准的轨迹曲线，而且能够节约内存，加快系统处理速度，提高效率。

效果例及效果分析

1轨迹优化流程

首先采用滑动平均法对采集的GPS轨迹点进行去噪，有效的消除了由于定位误差产生的噪点；其次用道格拉斯-普克算法对去噪之后的节点进行抽稀，去除了冗余信息，精确的保留了轨迹曲线信息；最后将处理好的轨迹点信息在Cesium上绘制出来；轨迹优化流程如图4所示：

在绘制轨迹的过程中，由于要处理大量的实时定位数据并在 Cesium地图中标注出车辆的位置，所以需要设计合理的数据结构来进行存储这些数据信息，以防造成内存泄露。因此，我们采用了队列的存储结构，按照先进先出的原则对数据进行处理访问，然后在使用Cesium提供的线函数进行轨迹绘制，从而保证车辆轨迹绘制的真实性。

去噪算法的优劣主要根据曲线精度来衡量，曲线精度指的是去噪之后和原始曲线的误差程度。而滑动平均算法中的轨迹曲线平滑精度主要受到滑动窗口大小N值的影响。通常来讲，N值越大则平化程度越大从而曲线精度越小，N值越小则相反，但是具体N值的设置，还应考虑原始曲线和道路线之间的位置关系，因此，N值的设置是十分重要得多，需要多次测试。

关于滑动窗口大小N值的确定，通过分析实验数据来确定合理的窗口范围。本次测试的轨迹点数为241个，通过多次试验发现N 值在6～15的范围内轨迹曲线的去噪效果较好，表1是滑动平滑算法取不同N值时的均值、标准差对比。

表1 数据对比

由表1可以看出，滑动窗口N越大，算法去噪效果的越明显。但在实际应用中，如果一味的增大N值，可能导致曲线与真实道路线不匹配，因此考虑到所测试的轨迹曲线与真实道路线的偏差，我们这里取N值为8来进行轨迹去噪。

2结果分析

针对上述的方案和功能要求，对车辆轨迹优化进行了相关性能测试，测试的数据是佛山某段高速公路的经纬度信息。为了验证去噪算法的可行性，我们选择了中值滤波算法与其进行对比，表2是两种算法的参数对比。

表2 参数对比

表2中的参数值越小，轨迹曲线与道路线就越贴合，误差就越小。由表2可以看出，滑动平均算法的轨迹优化效果要优于中值滤波算法，滤波效果对比如图5和图6所示。

图5是含有噪声的一段轨迹，红线是去噪之前的曲线，可以看到轨迹数据中含有的噪点导致车辆轨迹与实际道路线出现偏差，不能准确描述车辆行驶轨迹。

图6中粉色线是中值滤波去噪之后的轨迹，蓝色线是滑动平均去噪之后的轨迹，可以看到滑动平均滤波算法对轨迹的优化效果更佳。

通过引入滑动平均滤波算法，对初始的经纬度数据点进行去噪处理，去除由于定位误差导致的偏移道路线的数据点，同时对折线轨迹进行平滑处理，优化车辆行驶轨迹，使得轨迹与道路线基本贴合，较为真实的反应了车辆的运动轨迹，有效的解决了车辆轨迹的噪声问题。

最后，对去噪之后的数据点进行抽稀处理，用道格拉斯-普克算法对经纬度信息进行处理，原始数据点是241个，处理之后为170个，有效的减少了轨迹节点的个数，保证曲线轨迹整体不受影响的同时，又减少了内存的消耗。佛山高速路段抽稀效果如图7所示。

实验结果表明，通过滑动平均算法去噪之后的数据，能够在 Cesium地图上精确的绘制车辆的轨迹曲线，同时保证轨迹曲线与道路线基本贴合，去噪效果较好；最后再对去噪之后的轨迹进行抽稀处理，减少系统内存消耗的同时又保证整体轨迹曲线不变，优化服务质量。

结论：

提出一种车辆轨迹的优化方法，通过滑动平均算法和道格拉斯- 普克算法相结合，对轨迹点的经纬度信息进行去噪和抽稀处理，在一定程度上消除了影响轨迹曲线的噪点和冗余节点，精准的保留了轨迹信息，节省了服务器的内存消耗；并将处理后的结果在Cesium上进行绘制展示，通过多次测试验证该方法的可行性。优化后的轨迹可用在车辆历史轨迹查询、交通管控、轨迹规划等多个方面。

以上内容通过附图和实施例对本发明作了详细的说明，所属技术领域的技术人员能够理解，在不脱离本发明宗旨的前提下，还可以对上述实施例中的各个具体参数进行变更，形成多个具体的实施例，均为本发明的常见变化范围，在此不再一一详述。