抽稀算法在工程機械定位監測數據處理中的應用研究

張 斌，劉 洋，朱建濤

（桂林電子科技大學計算機科學與工程學院，廣西桂林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