GPS車輛監(jiān)控系統(tǒng)道路匹配算法研究與實(shí)現(xiàn)＊

吳 昊，劉 巖，吳北平

（1.中國地質(zhì)大學(xué)（武漢）信息工程學(xué)院，湖北 武漢430074；2.北京都宜環(huán)球科技發(fā)展有限公司，北京100081）

0 引 言

目前，隨著3S技術(shù)和無線通信技術(shù)的發(fā)展，GPS技術(shù)被廣泛地應(yīng)用到交通運(yùn)輸、物流配送、出租車服務(wù)、公交車調(diào)度、公共衛(wèi)生應(yīng)急、消防、安保等領(lǐng)域，為各行各業(yè)提供定位、跟蹤、導(dǎo)航等服務(wù)。GPS車輛監(jiān)控系統(tǒng)是一種結(jié)合了GPS技術(shù)、GIS技術(shù)和無線通信技術(shù)的新一代車輛管理調(diào)度系統(tǒng)，具有較好的經(jīng)濟(jì)和社會效益。其工作原理是根據(jù)接收到的車載GPS定位信息確定監(jiān)控車輛的實(shí)際運(yùn)行位置，再通過3G無線通信網(wǎng)絡(luò)將定位信息發(fā)送到監(jiān)控中心，監(jiān)控中心在后臺將信息解析、提取后，在電子地圖上實(shí)時地繪制、顯示出車輛的行駛軌跡，以便監(jiān)控中心清晰直觀地掌握監(jiān)控車輛的動態(tài)位置，實(shí)現(xiàn)對車輛的監(jiān)控[1－2]。但是，由于車載GPS定位信息和導(dǎo)航電子地圖本身都存在著一些誤差，這些誤差將導(dǎo)致監(jiān)控車輛的實(shí)際行駛軌跡偏離電子地圖上對應(yīng)道路的中心線。因此，如果要實(shí)現(xiàn)對車輛的監(jiān)控，首先需解決GPS定位信息與電子地圖數(shù)據(jù)匹配的問題，地圖匹配的效果將直接關(guān)系到車輛監(jiān)控效果。利用VB.NET語言設(shè)計了一種綜合考慮道路拓?fù)潢P(guān)系和連通性的直接投影匹配算法，糾正了道路匹配中產(chǎn)生的異常問題，提高了GPS車輛監(jiān)控系統(tǒng)道路匹配的精度。

1 GPS通訊協(xié)議解析

1.1 通訊協(xié)議語句說明

GPS接收機(jī)都遵守由美國國家海洋電子協(xié)會NMEA制定的一套通訊協(xié)議。該協(xié)議采用ASCII碼格式，規(guī)定了海用和陸用GPS接收機(jī)輸出的經(jīng)緯度、時間、衛(wèi)星狀態(tài)、接收機(jī)狀態(tài)等信息。協(xié)議有三種：0181、0182和0183，其中，NMEA－0183是目前使用最廣泛的行業(yè)標(biāo)準(zhǔn)[3]。

NMEA－0183協(xié)議定義了很多語句，常見的類型有：＄GPGGA、＄GPGSA、＄GPRMC、＄GPGSV以及＄GPGLL等。這些數(shù)據(jù)主要由幀頭、幀尾、幀內(nèi)數(shù)據(jù)組成，通過幀頭來識別幀內(nèi)數(shù)據(jù)的結(jié)構(gòu)，處理數(shù)據(jù)時可通過“＄”來判斷是否為幀頭，判定后則通過讀取逗號個數(shù)進(jìn)行判斷當(dāng)前處理的是哪一部分的導(dǎo)航參數(shù)，并做出相應(yīng)的提取處理。每幀數(shù)據(jù)均以回車符（＜CR＞）和換行符（＜LF＞）作為幀尾的結(jié)束，每行語句最多包含82個字符。車輛監(jiān)控系統(tǒng)中通常使用的經(jīng)緯度、速度、時間等信息均可以從＄GPRMC中提取，該幀的結(jié)構(gòu)如下：

其具體含義如表1所示。

表1 GPRMC數(shù)據(jù)結(jié)構(gòu)

以＄GPRMC解析算法為例，具體的導(dǎo)航信息提取代碼如下：

If nTemp＝5Then

dL＝StrToDeg（sCurstr）／／提取經(jīng)度信息

If nTemp＝6Then

dB＝StrToDeg（sCurstr）／／提取緯度信息

End If

……

If nTemp＝ 8Then

dSpeed ＝ Format（sCurstr ＊ 1.151 ＊1.609，"0.000"） ／／提取速度信息

End If

If nTemp＝ 9Then

nHeartRate＝sCurstr

dHeading＝sCurstr ／／提取方向信息

End If

1.2 GPS定位信息的接收與提取

基于對GPS定位語句結(jié)構(gòu)的分析，利用VB.NET語言進(jìn)行基本信息的提取，具體實(shí)現(xiàn)方法是利用VS2008中的MSComm控件進(jìn)行數(shù)據(jù)解析。由于GPS接收機(jī)每一秒鐘輸出一次數(shù)據(jù)，因此，只需要觸發(fā)MSComm控件的Timer事件就可以來接收GPS定位信息。根據(jù)GPS接收機(jī)傳輸數(shù)據(jù)的特點(diǎn)，需要將Timer事件的時間間隔設(shè)置為Timer1.Interval＝1 000，即每秒鐘接收一次數(shù)據(jù)，在接收數(shù)據(jù)的同時，需要將數(shù)據(jù)保存到數(shù)據(jù)存儲文件中[3]。利用MSComm控件提取GPS數(shù)據(jù)的算法流程圖如圖1所示。

圖1 GPS定位信息提取流程圖

2 道路匹配算法研究

2.1 道路匹配原理

道路匹配的基本思想是把某一時間內(nèi)車輛的位置或行駛軌跡同系統(tǒng)電子地圖中的道路網(wǎng)相比較，按照一定的算法判斷、推理，搜索出與行駛軌跡最相近的道路和車輛在道路中的可能位置，并把車輛定位到該道路的中心線上[4]。其基本原理是將接收到的GPS定位數(shù)據(jù)與系統(tǒng)數(shù)據(jù)庫中的電子地圖數(shù)據(jù)進(jìn)行比對，在電子地圖數(shù)據(jù)庫中搜索出對應(yīng)的道路線，并將其作為車輛軌跡曲線的待匹配樣本。依據(jù)一定的搜索法則，在匹配樣本附件搜索出滿足一定條件的道路，并將搜索出的路線作為最為匹配的模板。根據(jù)采用的道路匹配算法法則，依次計算出待匹配樣本和所有匹配模板之間的匹配相似度，最終選取匹配相似度最高的道路曲線模本作為該段道路的最終匹配結(jié)果，獲取車輛正確的行駛軌跡[5]。

2.2 相關(guān)算法研究

目前道路匹配的方法有很多種，如直接投影法、相關(guān)性法、半確定性法、概率統(tǒng)計法和基于拓?fù)潢P(guān)系的匹配法等，但是各個匹配算法都有一定的局限性。例如應(yīng)用較多的直接投影匹配算法，其匹配思想是根據(jù)點(diǎn)到線的最短垂直距離進(jìn)行道路匹配，這種方法計算方法簡單，匹配復(fù)雜度低，能較好地滿足道路匹配實(shí)時性的要求，但由于直接投影算法是將最短距離作為匹配因子，從而導(dǎo)致可靠性并不是很高[6－7]。因此，結(jié)合道路拓?fù)潢P(guān)系和連通性的直接投影算法更適合于GPS移動車輛的軌跡匹配。該算法的實(shí)現(xiàn)步驟為：

1）讀取GPS定位點(diǎn)數(shù)據(jù)，對每個定位點(diǎn)逐個進(jìn)行緩沖區(qū)分析，獲取每個定位點(diǎn)可能的匹配道路集。為每個GPS定位點(diǎn)建立圓形緩沖區(qū)，采用分級的方法將緩沖區(qū)半徑劃分成一系列特定的值，如5m、10m、15m等。按照設(shè)定的緩沖區(qū)半徑的大小，逐級建立緩沖區(qū)，最后依據(jù)道路匹配的約束條件查詢對應(yīng)的緩沖區(qū)內(nèi)的可能匹配道路，組成待匹配道路的集合；

2）對在第一步中確定的待匹配道路的集合進(jìn)行處理，建立道路的拓?fù)潢P(guān)系，確定與對應(yīng)道路具有幾何拓?fù)潢P(guān)系的道路集合，選取兩個集合的交集，得到GPS定位點(diǎn)所有的備選道路集合；

3）根據(jù)直接投影算法，計算GPS定位點(diǎn)到所有備選道路的最短距離，選取所有最短距離中的最小值對應(yīng)的道路作為匹配道路。

算法流程圖如圖2所示。

圖2 道路匹配算法流程圖

3 道路匹配誤差處理

GPS接收機(jī)接收到的定位信息精度受外部環(huán)境影響較大，例如當(dāng)衛(wèi)星信號被遮擋會導(dǎo)致接收數(shù)據(jù)丟失，遇見高樓阻擋會出現(xiàn)跳點(diǎn)，車輛速度過小會產(chǎn)生靜態(tài)漂移等問題，這些都會影響GPS定位的精度，甚至出現(xiàn)不能定位的情況。因此，為了提高定位的精度，在進(jìn)行道路匹配前需對GPS數(shù)據(jù)進(jìn)行預(yù)處理。

3.1 信號中斷處理

當(dāng)車輛行駛到隧道、高樓間、或者橋下這些特殊環(huán)境中時會出現(xiàn)GPS接收機(jī)信號暫時中斷的現(xiàn)象，這樣會使車輛軌跡數(shù)據(jù)出現(xiàn)跳點(diǎn)，即當(dāng)前點(diǎn)與上一點(diǎn)的距離超過最大可能運(yùn)動距離。采用的處理方法是過濾掉跳點(diǎn)，不進(jìn)行匹配，并利用線性插值預(yù)測的方法模擬出下一個GPS定位點(diǎn)，當(dāng)前后兩點(diǎn)的相對距離在允許范圍內(nèi)，沒有速度異常時，即停止插值。線性插值模型為

式中：gx（n），gy（n）為預(yù)測點(diǎn)的坐標(biāo)；v（n－1）為車輛的瞬時速度；d（n－1）為前一個點(diǎn)的上一點(diǎn)的行駛方向。線性插值的方法可以較好地解決由信號中斷產(chǎn)生的問題，但是由于誤差的相關(guān)性，容易造成誤差的積累。這種方法適用低速行駛的情況，當(dāng)車輛行駛速度過快時，會使道路匹配變得復(fù)雜。

3.2 數(shù)據(jù)漂移處理

當(dāng)車輛行駛到道路交叉口或等紅燈時，會處于低速行駛或靜止?fàn)顟B(tài)，此時的GPS定位點(diǎn)不是沿著行駛軌跡緩慢移動或靜止不動，而是位于以車輛實(shí)際位置為中心的一個較大圓內(nèi)[8－9]。這將導(dǎo)致GPS定位信號產(chǎn)生漂移，使導(dǎo)航定位出現(xiàn)較大誤差。為了保證地圖匹配的精度，將發(fā)生漂移的定位數(shù)據(jù)視為無效數(shù)據(jù)，不進(jìn)行地圖匹配，直到接收到正常的定位點(diǎn)。

4 實(shí)驗(yàn)分析

2012年8月在湖北省武漢市進(jìn)行了部分道路數(shù)據(jù)采集實(shí)驗(yàn)，共采集了魯磨路、民族大道、珞瑜路和武珞路4條線路的實(shí)測數(shù)據(jù)，并對實(shí)測數(shù)據(jù)進(jìn)行了數(shù)據(jù)統(tǒng)計分析，結(jié)果如表2所示。

表2 實(shí)驗(yàn)道路地圖匹配結(jié)果

實(shí)驗(yàn)結(jié)果表明4條實(shí)驗(yàn)道路的地圖匹配率均大于97%，證明該算法的地圖匹配效果較好，道路軌跡生成和道路匹配準(zhǔn)確性較高。

在異常情況處理方面，當(dāng)車輛在行駛過程中遇到了紅燈，如圖3圓圈部分所示，車輛靜止時定位點(diǎn)并不是固定不變，而是在以車輛實(shí)際位置為圓心的范圍內(nèi)不斷跳動，呈不規(guī)則分布，這就是GPS信號漂移現(xiàn)象。經(jīng)過系統(tǒng)道路匹配算法處理后，生成了連續(xù)、光滑的軌跡曲線（深色曲線），與實(shí)際道路基本吻合。圖4中，車輛經(jīng)過環(huán)島區(qū)域，由于路況較復(fù)雜，可以看出車輛實(shí)際定位點(diǎn)（淺色部分）呈不規(guī)則分布，與道路實(shí)際位置存在一定的偏差。在經(jīng)過系統(tǒng)道路匹配算法處理后，生成的車輛軌跡（深色曲線）與實(shí)際路線吻合較好。

圖3 道路匹配效果圖

圖4 環(huán)島路況匹配效果圖

由以上兩個實(shí)驗(yàn)可以明顯看出：車輛行駛過程中，由于GPS信號受城市環(huán)境的影響，GPS定位點(diǎn)與車輛的實(shí)際位置存在著一定的偏差，在遇到特殊路況時，偏差會變大。經(jīng)過系統(tǒng)道路匹配算法處理后形成的軌跡與車輛實(shí)際的道路曲線能很好的保持一致，由圖中淺色和深色曲線可以看出。因此，以上兩個實(shí)驗(yàn)均證實(shí)了使用的道路匹配算法在數(shù)據(jù)處理方面具有很好的效果，保證了GPS車載監(jiān)控系統(tǒng)定位的準(zhǔn)確性。

5 結(jié) 論

本文提出的道路匹配算法通過創(chuàng)建緩沖區(qū)，利用最短距離分析獲取匹配道路的辦法進(jìn)行道路匹配。這種方法不僅綜合考慮了道路的拓?fù)潢P(guān)系和連通性，還增加了道路匹配的約束條件，更有利于匹配結(jié)果的優(yōu)化改進(jìn)，是一種全局匹配的算法。實(shí)驗(yàn)證明：結(jié)合道路拓?fù)潢P(guān)系和連通性的直接投影算法能夠?qū)ζヅ浣Y(jié)果進(jìn)行優(yōu)化改正，消除信號中斷、跳點(diǎn)、漂移等誤差帶來的不良影響，能夠?qū)PS定位點(diǎn)準(zhǔn)確地匹配到電子地圖上，具有較好的匹配精度和可靠性。

[1]李東江，李繼遠(yuǎn)，蔡建業(yè)，等.基于 GPS／GPRS／GIS的車輛監(jiān)控系統(tǒng)[J].全球定位系統(tǒng)，2007，33（01）：42－46.

[2]姚新春.GPS車輛導(dǎo)航系統(tǒng)的數(shù)據(jù)組織[J].現(xiàn)代測繪，2006，29（4）：34－36.

[3]劉巖，汪劍云，吳北平，等.基于 VB.NET的GPS接收機(jī)串口通信的實(shí)現(xiàn)[J].地理空間信息，2012，4（2）：34－37.

[4]張振輝.車輛導(dǎo)航中地圖匹配算法與應(yīng)用研究[D].鄭州：信息工程大學(xué)，2006.

[5]夏 州.GPS車輛導(dǎo)航中的數(shù)據(jù)處理和地圖匹配研究[D].北京：北京交通大學(xué)，2009.

[6]QUDDUS M A，OCHIENG W Y，NOLAND R B.Current map－matching algorithms for transport applications：State－of－the art and future research directions[J].Transportation Research Part C：Emerging Technologies，2007，15（5）：312－328.

[7]VELAGA N R，QUDDUS M A，BRISTOW A L.Developing an enhanced weight－based topological Map－matching algorithm for intelligent transport systems[J].Transportation Research Part C：Emerging Technologies，2009，17（6）：672－683.

[8]陳永剛，王更生，陳 斌.車載地圖匹配技術(shù)中GPS定位數(shù)據(jù)的研究[J].工業(yè)控制計算機(jī)，2006（1）：61－62.

[9]雷東升，諸彤宇.一種基于實(shí)時路況信息的動態(tài)路徑規(guī)劃算法[C]／／2008中國信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（一），2008.