抽稀算法在工程机械定位监测数据处理中的应用研究

张 斌，刘 洋，朱建涛

（桂林电子科技大学计算机科学与工程学院，广西桂林541004）

抽稀算法在工程机械定位监测数据处理中的应用研究

张 斌，刘 洋，朱建涛

（桂林电子科技大学计算机科学与工程学院，广西桂林541004）

以物联网技术实施对工程机械的远程监控，需通过车载端智能控制器周期性采集GPS定位数据及其它参数信息，并通过GPRS无线网络发送到监控中心服务器。但由于车辆众多，周期性采集会使数据量迅速增加，占用大量数据库存储空间，同时在Google Maps上显示车辆历史轨迹时，造成路径生成速度缓慢。针对这一问题提出如下解决方案：控制器仍以较小时间间隔发送数据，但在服务器端通过使用曲线抽稀算法，去除冗余数据，保留关键点，这样既能获得精确的历史轨迹曲线，又能节约数据库存储空间、加快系统处理速度，同时数据库系统里仍保留了关键数据以供其它应用。最后，给出了一个具体实现，对比说明了改进后的系统处理速度加快，轨迹曲线显示简洁、准确。

抽稀算法；Google Maps；远程监控；历史轨迹

0 引 言

随着经济高速发展，我国已迅速发展成为工程机械生产大国。然而，由于工程机械的结构复杂，施工载荷不稳定，工作环境恶劣及销售与售后管理等多方面原因，国内外制造企业、用户单位对机械设备的状态、位置监测及故障诊断越来越重视。融合了GPS全球卫星定位技术、GIS地理信息技术和GPRS无线网络通信技术于一体的远程工程机械监控系统已经成为解决上述问题的有效手段。其中关于远程定位监测服务，其工作原理是车载控制器周期性地采集GPS定位信息及其他信息，并通过GPRS无线通信网络将信息发送给监控中心；监控中心在后台将信息解析、提取并存入数据库；当用户请求查询时，服务器读取数据库并在电子地图上显示出车辆的位置、行驶轨迹及车辆运行参数[1］。定位监测服务是基于GIS的，然而以传统方式开发相关模块，需要花钱购买GIS开发平台和地图数据，费用开销很大，Google提供了免费的数据和平台，并发布了开源的Google Map API[2］。因此，当前相关监控系统的研究多是基于Google Maps的，例如文献[3］～[5］所研究的监控系统。但是这些监控系统还存在进一步完善的地方，本文正是在此基础上进行了关于车辆历史轨迹查询功能的优化，并实际应用在工程机械监控系统设计当中，优化了存储空间、提高了服务质量。

历史轨迹信息查询是工程机械监控的一项基本功能。要想获得以上信息，服务器端就必须获取移动车辆每隔一定时间的定位信息，然后利用Google Map API提供的Polyline（）函数和上述所提供的数据信息就可以方便地绘制出机械车辆的历史轨迹信息。但是上述方法中存在如下问题：如果将间隔时间设置的过大，获取的轨迹曲线就不够精确；如果将间隔时间设置的过小，冗余信息过多，影响服务质量。为此本文针对上述问题提供了如下的解决方案：为了获取精确的历史轨迹曲线，车辆仍选择以较小的时间间隔发送定位信息给监控服务器，然后在服务器端通过曲线抽稀算法对接收到的定位信息进行抽稀处理，去除冗余信息，提高服务质量。

1 抽稀算法

曲线抽稀是指在保证曲线形状变化不大的情况下，最大限度减少曲线点的数量。曲线抽稀的关键是定义抽稀因子，抽稀因子的不同决定了抽稀算法的多样性，常见的曲线抽稀算法有步长法、线段过滤法、圆柱法、道格拉斯－普克法、垂矩限值法等等[6］。本文重点介绍道格拉斯－普克法和垂矩限值法。

1.1道格拉斯－普克法

Douglas－Poiker法是矢量曲线数据压缩中的成熟算法，它是从整体的角度来考虑一条完整的曲线，选取曲线的两端点，计算线段内各点到连接两端点的直线的距离，如果这些点到直线的垂直距离中最大者仍小于规定的阀值，则所有这些点都被舍去，若最大距离大于阀值，则保留此点，并以此点将线段分为两段，对这两段曲线分别重复上述步骤，直到没有多余的点需要被舍去为止[7］。其阈值一般取相应地物最大允许误差。该算法即能充分减少点的数量，又能尽量保留特征点。但是从编程的难易程度和计算机处理效率考虑，由于其循环计算每个点的距离和逐段递归计算，当点数量很大时计算机运行效率会大受影响。

1.2 垂距限值法

垂矩限值法与Douglas－Poiker法的基本原理是一样的，但它不是从整体角度考虑，而是从曲线起点开始依次逐个筛选各中间点，排除冗余点。具体做法如图1所示，以A为起点，计算B其到AC连线的垂直距离，如果该值大于规定的阀值，则保留第B点，并以该点为起点，计算C到BD连线的垂矩；否则，去掉B点，仍以A为起点，计算原曲线上C到AD连线的垂矩，以此类推，直至曲线上最后一点，该方法的阀值一般取相应地最大允许误差或更小的值。

图1 垂矩限值法示意

垂矩限值法在抽稀结果的精度方面可以取得与Douglas－Poiker法一样的效果，并且因其简单的循环算法而易于编程和计算机处理。因此本文采用垂距限值法。

由以上对矢量曲线抽稀算法的描述易知，抽稀算法的实现须在二维坐标系下进行数据计算处理，但是服务器获得的GPS定位信息是以三维坐标表示的，即（地球半径，经度，纬度）表示一个定位坐标。通过分析Google Maps数学模型，使用墨卡托投影将三维定位坐标转换成二维坐标。

2 Google Map数学模型

2.1 地球椭球体数学模型

地图投影就是指在平面上建立与地球曲面上相对应的经纬网。地图投影的拟定和计算一般均假定地球表面为旋转椭球面，并称其为地球椭球面或参考椭球面，如图2所示，地球椭球体的形状和大小是由其长半径（赤道半径）和短半径（极轴半径）决定的，通常ae取值为6 378 137m，be为6 356 752.3m[8］.

图2 地球椭球体示意图

另外，用于描述地球椭球形状的参数还有椭圆扁率fe、第一偏心率e1和第二偏心率e2，如公式（1）所示。

2.2 墨卡托投影

墨卡托投影是正轴等角圆柱投影，由荷兰地图学家墨卡托在1569年创拟。假设地球被围在一中空的圆柱里，其基准嘉诚（赤道）与圆柱相切接触，再假想地球中心有一盏灯，把球面上的图形投影到圆柱体上，再把圆柱体展开，这就是一幅选定基准纬线上的墨卡托投影绘制出的地图[9］。

以赤道作x轴，根据等角条件推算出投影公式

式中：λ为经度；φ为纬度。在实际计算中，可将上述公式简化，将地球作为球体处理，球体的半径取地球几何平均半径Re＝6 371 004m，则

本文通过式（3）将三维定位坐标转换成二维坐标。然而，在实现曲线抽稀算法时，还需要计算点到另外两点所在的直线的距离，具体为

式中，h即为点（x2，y2）到点（x1，y1）（x3，y3）所在的直线的距离。

3 算法实现及结果对比

采用垂距限值法，利用C＃面向对象语言的Visual Studio 2010编程开发工具实现了算法，并对模拟轨迹曲线的定位信息进行了抽稀处理，达到了预期效果，有效地去除了冗余信息，并精确地保留了轨迹曲线信息。程序抽稀算法实现部分流程图如图3所示.

抽稀算法的优劣可以用抽稀率和曲线精度衡量，抽稀率是指过滤冗余信息的百分比，曲线精度是指抽稀后的曲线与原曲线误差程度。然而抽稀算法的抽稀程度与精度均受到的阀值的控制，阀值越大则抽稀程度越大而精度则越小，阀值越小则相反。因此，设置合理的阀值是一项非常重要的工作。

图3 部分算法实现流程图

关于阀值的合理范围，由于本文对实际获得的定位坐标进行了墨卡托投影运算，所以阀值不能想当然的从实际生活中去考虑。本文将会通过分析实验数据确定合理的阀值范围，在实验中的原始轨迹曲线定位点数为83，通过分析实验中获取的距离值，发现其在5.137～2 096.810范围内呈现从小到大密集度越来越小的分布形式，因此本文采用了50、100、200、300、500、700、900、1 100、1 400，这些关键点作为数据分析的参考依据，得到如表1所示的数据结果。

表1 数据结果

当阀值设定为200时，历史轨迹抽稀前后对比图如图4所示。

可以看出抽稀算法对原轨迹曲线进行了很好的处理，并精确保留了原轨迹曲线线路，大大去除了冗余数据，节约了服务器存储空间，优化了数据存取效率，提高了服务质量。

图4 轨迹曲线对比图 （a）抽稀前轨迹；（b）抽稀后轨迹；（c）前后抽稀轨迹对比

4 结束语

目前基于Google Maps的移动目标监控应用服务被越来越多的应用到各行各业，相关的研究也越来越受到重视。本文在已有的相关研究工作基础之上，进行了工程机械历史轨迹查询功能的优化，在传统的历史轨迹绘制基础之上，通过使用曲线抽稀算法，大大去除了冗余信息，并精确的保留了历史轨迹信息，节约了服务器存储空间，提高了服务质量，进一步完善了基于Google Maps的移动目标监控应用服务。

[1]吴 昊，刘 岩，吴北平.GPS车辆监控系统道路匹配算法研究与实现[J］.全球定位系，2013，38（4）：83－87.

[2]丁 毅，彭 宏.Google Maps API在WebGIS定位中的应用研究[J］.杭州电子科技大学学报，2012，32（5）：96－99.

[3]陈梦娜，曹卫彬，李江全.采棉机地理位置信息服务系统设计[J］.农机化研究，2013（12）：170－173.

[4]王 序，夏晓玲，李 霞.基于Google Maps的车辆路径问题可视化系统[J］.计算机工程，2011（37）：341－343.

[5]杜 娟，尹文庆，等.基于GPS和Goolge Eatrh的车辆远程定位监测系统的设计[J］.测控技术，2012，32（7）：23－26.

[6]李 俊，赵娜娜.曲线抽稀算法在刚果（布）国家1号公路数模处理中的应用[J］.施工技术与测量技术，2012，32（2）：209－210.

[7]陈 莉，乔小艳，毛 建.等高线抽稀算法研究[J］.工程地质计算机应用，2009（4）：39－42.

[8]崔金红，王 旭.Google地图算法研究及实现[J］.计算机科学，2007，34（11）：193－195.

[9]Baidu.墨卡托投影[EB/OL］.（2014－02－26）[2014－05－22］.http：//baike.baidu.com/link？url＝sf4RQAm4dgNw30GZ－SfvkJwFXbNTGHsl1v5 N9zMDBgLBYGh1Ehe2PZ－6rogQ0vK1.

Application of Thinning Algorithm based on Processing in Positioning Data of Construction Machinery

ZHANG Bin，LIU Yang，ZHU Jiantao
（School of Computer Science and Engineering，Guilin University of Electronic Technology，Guilin541004，China）

Based on the technology of internet of things，the principle of remote monitoring of construction machinery is as follows.The intelligent controller of mobile terminal periodically collects the GPS data and other information and sends to the monitoring center server over a wireless network.However，because of amounts of vehicles，periodic collection will make the amount of data increasing rapidly，so as to occupy a large number of storage spaces of database.At the same time，the historical track displayed in the Google Map will generate slowly.This paper proposes the following solutions to this problem：the controller still sends the data in a small time interval；The server will removal of redundant data and retain key points by using the curve thinning algorithm，so as to obtain the historical track accurately，save the storage space and accelerate the speed of data processing.Meanwhile the database system still retains the key data for other applications.This paper finally gives a concrete realization of the system.Compared with the original system，the processing speed is faster and displaying of historical track is more concise.

Thinning algorithm；Google maps；remote monitoring；historical track

P228.4

A

1008－9268（2015）01－0057－05

10.13442/j.gnss.1008－9268.2015.01.012

张 斌（1970－），男，副教授，主要研究方向为计算机网络与应用技术、计算机控制技术、网络安全。

刘 洋（1987－），男，硕士生，主要研究方向为计算机网络与应用技术、软件工程。

朱建涛（1989－），男，硕士生，主要研究方向为物联网应用。

2014－10－28

广西科学研究与技术开发计划项目（编号：桂科攻1348014－6）；广西2014年工业创新发展项目（编号：2014－276）

联系人：刘洋E－mail：827294841＠qq.com