抽稀算法在工程機(jī)械定位監(jiān)測數(shù)據(jù)處理中的應(yīng)用研究

張 斌，劉 洋，朱建濤

（桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西桂林541004）

抽稀算法在工程機(jī)械定位監(jiān)測數(shù)據(jù)處理中的應(yīng)用研究

張 斌，劉 洋，朱建濤

（桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西桂林541004）

以物聯(lián)網(wǎng)技術(shù)實(shí)施對(duì)工程機(jī)械的遠(yuǎn)程監(jiān)控，需通過車載端智能控制器周期性采集GPS定位數(shù)據(jù)及其它參數(shù)信息，并通過GPRS無線網(wǎng)絡(luò)發(fā)送到監(jiān)控中心服務(wù)器。但由于車輛眾多，周期性采集會(huì)使數(shù)據(jù)量迅速增加，占用大量數(shù)據(jù)庫存儲(chǔ)空間，同時(shí)在Google Maps上顯示車輛歷史軌跡時(shí)，造成路徑生成速度緩慢。針對(duì)這一問題提出如下解決方案：控制器仍以較小時(shí)間間隔發(fā)送數(shù)據(jù)，但在服務(wù)器端通過使用曲線抽稀算法，去除冗余數(shù)據(jù)，保留關(guān)鍵點(diǎn)，這樣既能獲得精確的歷史軌跡曲線，又能節(jié)約數(shù)據(jù)庫存儲(chǔ)空間、加快系統(tǒng)處理速度，同時(shí)數(shù)據(jù)庫系統(tǒng)里仍保留了關(guān)鍵數(shù)據(jù)以供其它應(yīng)用。最后，給出了一個(gè)具體實(shí)現(xiàn)，對(duì)比說明了改進(jìn)后的系統(tǒng)處理速度加快，軌跡曲線顯示簡潔、準(zhǔn)確。

抽稀算法；Google Maps；遠(yuǎn)程監(jiān)控；歷史軌跡

0 引 言

隨著經(jīng)濟(jì)高速發(fā)展，我國已迅速發(fā)展成為工程機(jī)械生產(chǎn)大國。然而，由于工程機(jī)械的結(jié)構(gòu)復(fù)雜，施工載荷不穩(wěn)定，工作環(huán)境惡劣及銷售與售后管理等多方面原因，國內(nèi)外制造企業(yè)、用戶單位對(duì)機(jī)械設(shè)備的狀態(tài)、位置監(jiān)測及故障診斷越來越重視。融合了GPS全球衛(wèi)星定位技術(shù)、GIS地理信息技術(shù)和GPRS無線網(wǎng)絡(luò)通信技術(shù)于一體的遠(yuǎn)程工程機(jī)械監(jiān)控系統(tǒng)已經(jīng)成為解決上述問題的有效手段。其中關(guān)于遠(yuǎn)程定位監(jiān)測服務(wù)，其工作原理是車載控制器周期性地采集GPS定位信息及其他信息，并通過GPRS無線通信網(wǎng)絡(luò)將信息發(fā)送給監(jiān)控中心；監(jiān)控中心在后臺(tái)將信息解析、提取并存入數(shù)據(jù)庫；當(dāng)用戶請(qǐng)求查詢時(shí)，服務(wù)器讀取數(shù)據(jù)庫并在電子地圖上顯示出車輛的位置、行駛軌跡及車輛運(yùn)行參數(shù)[1］。定位監(jiān)測服務(wù)是基于GIS的，然而以傳統(tǒng)方式開發(fā)相關(guān)模塊，需要花錢購買GIS開發(fā)平臺(tái)和地圖數(shù)據(jù)，費(fèi)用開銷很大，Google提供了免費(fèi)的數(shù)據(jù)和平臺(tái)，并發(fā)布了開源的Google Map API[2］。因此，當(dāng)前相關(guān)監(jiān)控系統(tǒng)的研究多是基于Google Maps的，例如文獻(xiàn)[3］～[5］所研究的監(jiān)控系統(tǒng)。但是這些監(jiān)控系統(tǒng)還存在進(jìn)一步完善的地方，本文正是在此基礎(chǔ)上進(jìn)行了關(guān)于車輛歷史軌跡查詢功能的優(yōu)化，并實(shí)際應(yīng)用在工程機(jī)械監(jiān)控系統(tǒng)設(shè)計(jì)當(dāng)中，優(yōu)化了存儲(chǔ)空間、提高了服務(wù)質(zhì)量。

歷史軌跡信息查詢是工程機(jī)械監(jiān)控的一項(xiàng)基本功能。要想獲得以上信息，服務(wù)器端就必須獲取移動(dòng)車輛每隔一定時(shí)間的定位信息，然后利用Google Map API提供的Polyline（）函數(shù)和上述所提供的數(shù)據(jù)信息就可以方便地繪制出機(jī)械車輛的歷史軌跡信息。但是上述方法中存在如下問題：如果將間隔時(shí)間設(shè)置的過大，獲取的軌跡曲線就不夠精確；如果將間隔時(shí)間設(shè)置的過小，冗余信息過多，影響服務(wù)質(zhì)量。為此本文針對(duì)上述問題提供了如下的解決方案：為了獲取精確的歷史軌跡曲線，車輛仍選擇以較小的時(shí)間間隔發(fā)送定位信息給監(jiān)控服務(wù)器，然后在服務(wù)器端通過曲線抽稀算法對(duì)接收到的定位信息進(jìn)行抽稀處理，去除冗余信息，提高服務(wù)質(zhì)量。

1 抽稀算法

曲線抽稀是指在保證曲線形狀變化不大的情況下，最大限度減少曲線點(diǎn)的數(shù)量。曲線抽稀的關(guān)鍵是定義抽稀因子，抽稀因子的不同決定了抽稀算法的多樣性，常見的曲線抽稀算法有步長法、線段過濾法、圓柱法、道格拉斯－普克法、垂矩限值法等等[6］。本文重點(diǎn)介紹道格拉斯－普克法和垂矩限值法。

1.1道格拉斯－普克法

Douglas－Poiker法是矢量曲線數(shù)據(jù)壓縮中的成熟算法，它是從整體的角度來考慮一條完整的曲線，選取曲線的兩端點(diǎn)，計(jì)算線段內(nèi)各點(diǎn)到連接兩端點(diǎn)的直線的距離，如果這些點(diǎn)到直線的垂直距離中最大者仍小于規(guī)定的閥值，則所有這些點(diǎn)都被舍去，若最大距離大于閥值，則保留此點(diǎn)，并以此點(diǎn)將線段分為兩段，對(duì)這兩段曲線分別重復(fù)上述步驟，直到?jīng)]有多余的點(diǎn)需要被舍去為止[7］。其閾值一般取相應(yīng)地物最大允許誤差。該算法即能充分減少點(diǎn)的數(shù)量，又能盡量保留特征點(diǎn)。但是從編程的難易程度和計(jì)算機(jī)處理效率考慮，由于其循環(huán)計(jì)算每個(gè)點(diǎn)的距離和逐段遞歸計(jì)算，當(dāng)點(diǎn)數(shù)量很大時(shí)計(jì)算機(jī)運(yùn)行效率會(huì)大受影響。

1.2 垂距限值法

垂矩限值法與Douglas－Poiker法的基本原理是一樣的，但它不是從整體角度考慮，而是從曲線起點(diǎn)開始依次逐個(gè)篩選各中間點(diǎn)，排除冗余點(diǎn)。具體做法如圖1所示，以A為起點(diǎn)，計(jì)算B其到AC連線的垂直距離，如果該值大于規(guī)定的閥值，則保留第B點(diǎn)，并以該點(diǎn)為起點(diǎn)，計(jì)算C到BD連線的垂矩；否則，去掉B點(diǎn)，仍以A為起點(diǎn)，計(jì)算原曲線上C到AD連線的垂矩，以此類推，直至曲線上最后一點(diǎn)，該方法的閥值一般取相應(yīng)地最大允許誤差或更小的值。

圖1 垂矩限值法示意

垂矩限值法在抽稀結(jié)果的精度方面可以取得與Douglas－Poiker法一樣的效果，并且因其簡單的循環(huán)算法而易于編程和計(jì)算機(jī)處理。因此本文采用垂距限值法。

由以上對(duì)矢量曲線抽稀算法的描述易知，抽稀算法的實(shí)現(xiàn)須在二維坐標(biāo)系下進(jìn)行數(shù)據(jù)計(jì)算處理，但是服務(wù)器獲得的GPS定位信息是以三維坐標(biāo)表示的，即（地球半徑，經(jīng)度，緯度）表示一個(gè)定位坐標(biāo)。通過分析Google Maps數(shù)學(xué)模型，使用墨卡托投影將三維定位坐標(biāo)轉(zhuǎn)換成二維坐標(biāo)。

2 Google Map數(shù)學(xué)模型

2.1 地球橢球體數(shù)學(xué)模型

地圖投影就是指在平面上建立與地球曲面上相對(duì)應(yīng)的經(jīng)緯網(wǎng)。地圖投影的擬定和計(jì)算一般均假定地球表面為旋轉(zhuǎn)橢球面，并稱其為地球橢球面或參考橢球面，如圖2所示，地球橢球體的形狀和大小是由其長半徑（赤道半徑）和短半徑（極軸半徑）決定的，通常ae取值為6 378 137m，be為6 356 752.3m[8］.

圖2 地球橢球體示意圖

另外，用于描述地球橢球形狀的參數(shù)還有橢圓扁率fe、第一偏心率e1和第二偏心率e2，如公式（1）所示。

2.2 墨卡托投影

墨卡托投影是正軸等角圓柱投影，由荷蘭地圖學(xué)家墨卡托在1569年創(chuàng)擬。假設(shè)地球被圍在一中空的圓柱里，其基準(zhǔn)嘉誠（赤道）與圓柱相切接觸，再假想地球中心有一盞燈，把球面上的圖形投影到圓柱體上，再把圓柱體展開，這就是一幅選定基準(zhǔn)緯線上的墨卡托投影繪制出的地圖[9］。

以赤道作x軸，根據(jù)等角條件推算出投影公式

式中：λ為經(jīng)度；φ為緯度。在實(shí)際計(jì)算中，可將上述公式簡化，將地球作為球體處理，球體的半徑取地球幾何平均半徑Re＝6 371 004m，則

本文通過式（3）將三維定位坐標(biāo)轉(zhuǎn)換成二維坐標(biāo)。然而，在實(shí)現(xiàn)曲線抽稀算法時(shí)，還需要計(jì)算點(diǎn)到另外兩點(diǎn)所在的直線的距離，具體為

式中，h即為點(diǎn)（x2，y2）到點(diǎn)（x1，y1）（x3，y3）所在的直線的距離。

3 算法實(shí)現(xiàn)及結(jié)果對(duì)比

采用垂距限值法，利用C＃面向?qū)ο笳Z言的Visual Studio 2010編程開發(fā)工具實(shí)現(xiàn)了算法，并對(duì)模擬軌跡曲線的定位信息進(jìn)行了抽稀處理，達(dá)到了預(yù)期效果，有效地去除了冗余信息，并精確地保留了軌跡曲線信息。程序抽稀算法實(shí)現(xiàn)部分流程圖如圖3所示.

抽稀算法的優(yōu)劣可以用抽稀率和曲線精度衡量，抽稀率是指過濾冗余信息的百分比，曲線精度是指抽稀后的曲線與原曲線誤差程度。然而抽稀算法的抽稀程度與精度均受到的閥值的控制，閥值越大則抽稀程度越大而精度則越小，閥值越小則相反。因此，設(shè)置合理的閥值是一項(xiàng)非常重要的工作。

圖3 部分算法實(shí)現(xiàn)流程圖

關(guān)于閥值的合理范圍，由于本文對(duì)實(shí)際獲得的定位坐標(biāo)進(jìn)行了墨卡托投影運(yùn)算，所以閥值不能想當(dāng)然的從實(shí)際生活中去考慮。本文將會(huì)通過分析實(shí)驗(yàn)數(shù)據(jù)確定合理的閥值范圍，在實(shí)驗(yàn)中的原始軌跡曲線定位點(diǎn)數(shù)為83，通過分析實(shí)驗(yàn)中獲取的距離值，發(fā)現(xiàn)其在5.137～2 096.810范圍內(nèi)呈現(xiàn)從小到大密集度越來越小的分布形式，因此本文采用了50、100、200、300、500、700、900、1 100、1 400，這些關(guān)鍵點(diǎn)作為數(shù)據(jù)分析的參考依據(jù)，得到如表1所示的數(shù)據(jù)結(jié)果。

表1 數(shù)據(jù)結(jié)果

當(dāng)閥值設(shè)定為200時(shí)，歷史軌跡抽稀前后對(duì)比圖如圖4所示。

可以看出抽稀算法對(duì)原軌跡曲線進(jìn)行了很好的處理，并精確保留了原軌跡曲線線路，大大去除了冗余數(shù)據(jù)，節(jié)約了服務(wù)器存儲(chǔ)空間，優(yōu)化了數(shù)據(jù)存取效率，提高了服務(wù)質(zhì)量。

圖4 軌跡曲線對(duì)比圖 （a）抽稀前軌跡；（b）抽稀后軌跡；（c）前后抽稀軌跡對(duì)比

4 結(jié)束語

目前基于Google Maps的移動(dòng)目標(biāo)監(jiān)控應(yīng)用服務(wù)被越來越多的應(yīng)用到各行各業(yè)，相關(guān)的研究也越來越受到重視。本文在已有的相關(guān)研究工作基礎(chǔ)之上，進(jìn)行了工程機(jī)械歷史軌跡查詢功能的優(yōu)化，在傳統(tǒng)的歷史軌跡繪制基礎(chǔ)之上，通過使用曲線抽稀算法，大大去除了冗余信息，并精確的保留了歷史軌跡信息，節(jié)約了服務(wù)器存儲(chǔ)空間，提高了服務(wù)質(zhì)量，進(jìn)一步完善了基于Google Maps的移動(dòng)目標(biāo)監(jiān)控應(yīng)用服務(wù)。

[1]吳 昊，劉 巖，吳北平.GPS車輛監(jiān)控系統(tǒng)道路匹配算法研究與實(shí)現(xiàn)[J］.全球定位系，2013，38（4）：83－87.

[2]丁 毅，彭 宏.Google Maps API在WebGIS定位中的應(yīng)用研究[J］.杭州電子科技大學(xué)學(xué)報(bào)，2012，32（5）：96－99.

[3]陳夢(mèng)娜，曹衛(wèi)彬，李江全.采棉機(jī)地理位置信息服務(wù)系統(tǒng)設(shè)計(jì)[J］.農(nóng)機(jī)化研究，2013（12）：170－173.

[4]王 序，夏曉玲，李 霞.基于Google Maps的車輛路徑問題可視化系統(tǒng)[J］.計(jì)算機(jī)工程，2011（37）：341－343.

[5]杜 娟，尹文慶，等.基于GPS和Goolge Eatrh的車輛遠(yuǎn)程定位監(jiān)測系統(tǒng)的設(shè)計(jì)[J］.測控技術(shù)，2012，32（7）：23－26.

[6]李 俊，趙娜娜.曲線抽稀算法在剛果（布）國家1號(hào)公路數(shù)模處理中的應(yīng)用[J］.施工技術(shù)與測量技術(shù)，2012，32（2）：209－210.

[7]陳 莉，喬小艷，毛 建.等高線抽稀算法研究[J］.工程地質(zhì)計(jì)算機(jī)應(yīng)用，2009（4）：39－42.

[8]崔金紅，王 旭.Google地圖算法研究及實(shí)現(xiàn)[J］.計(jì)算機(jī)科學(xué)，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－），男，副教授，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與應(yīng)用技術(shù)、計(jì)算機(jī)控制技術(shù)、網(wǎng)絡(luò)安全。

劉 洋（1987－），男，碩士生，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與應(yīng)用技術(shù)、軟件工程。

朱建濤（1989－），男，碩士生，主要研究方向?yàn)槲锫?lián)網(wǎng)應(yīng)用。

2014－10－28

廣西科學(xué)研究與技術(shù)開發(fā)計(jì)劃項(xiàng)目（編號(hào)：桂科攻1348014－6）；廣西2014年工業(yè)創(chuàng)新發(fā)展項(xiàng)目（編號(hào)：2014－276）

聯(lián)系人：劉洋E－mail：827294841＠qq.com