基于曲線擬合和網(wǎng)絡(luò)拓?fù)涞木C合地圖匹配算法＊

畢 軍 朱 穎 程 勇

（1.北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 北京 100044；2.北京交通大學(xué)北京城市交通協(xié)同創(chuàng)新中心 北京 100044；3.山東濟(jì)寧市鴻翔公路勘察設(shè)計(jì)研究院 山東 濟(jì)寧 272000）

0 引言

現(xiàn)今的大多數(shù)車輛導(dǎo)航系統(tǒng)都采用全球定位系統(tǒng)（global position system，GPS）和航位推算法（dead reckoning，DR）來(lái)進(jìn)行定位。但是，定位傳感器都會(huì)存在著一定的誤差，使得車輛定位位置與其真實(shí)位置不一致［1］。因此，研究如何快速、準(zhǔn)確的減少這種誤差，可以使車輛導(dǎo)航系統(tǒng)更好的為人們服務(wù)［2］。地圖匹配是指載體上的GPS接收機(jī)采集載體當(dāng)前的有關(guān)位置信息后，并從電子地圖數(shù)據(jù)庫(kù)中獲取相關(guān)的道路信息，再將得到的載體的位置、速度、方向等信息，通過(guò)匹配算法對(duì)其進(jìn)行實(shí)時(shí)修正，從而顯示車輛在電子地圖的準(zhǔn)確位置的1種方法［3］?，F(xiàn)有的地圖匹配算法主要有基于權(quán)重、基于相關(guān)性、基于概率統(tǒng)計(jì)、基于曲線擬合，基于網(wǎng)絡(luò)拓?fù)潢P(guān)系等匹配算法［4－5］。其中基于曲線擬合的匹配算法具有較強(qiáng)的穩(wěn)定性，匹配精度高，但是對(duì)比較靠近的平行路段進(jìn)行匹配時(shí)，該算法容易出錯(cuò)；基于網(wǎng)絡(luò)拓?fù)涞牡貓D匹配算法會(huì)受到空間拓?fù)潢P(guān)系質(zhì)量的影響，空間拓?fù)湓酱螅ヅ湫Ч簿驮讲?，?yīng)和其他的匹配算法結(jié)合使用。也有采用模糊邏輯、卡爾曼濾波等方法的匹配算法，這些算法雖然匹配精度高，但實(shí)現(xiàn)較為復(fù)雜［6－7］。筆者提出1種基于曲線擬合和網(wǎng)絡(luò)拓?fù)涞木C合地圖匹配算法，可有效解決曲線擬合算法的缺陷。

1 基本地圖匹配算法的介紹

1.1 基于曲線擬合的地圖匹配算法

在很多情況下，由于測(cè)試點(diǎn)分散，所求的曲線無(wú)法通過(guò)所有的測(cè)試點(diǎn)，因此需要1條反映測(cè)試點(diǎn)趨勢(shì)的平滑曲線來(lái)近似測(cè)試結(jié)果，這就是曲線擬合［8］?；谇€擬合的地圖匹配算法以曲線擬合的原理為基礎(chǔ)，通過(guò)對(duì)若干個(gè)原始定位數(shù)據(jù)的累加，經(jīng)過(guò)曲線擬合計(jì)算，得出由這幾個(gè)原始數(shù)據(jù)所確定的擬合直線的斜率。預(yù)先設(shè)定1 個(gè)門限值，在計(jì)算擬合直線斜率與各匹配候選路段斜率之間的差值之后，將各差值與門限值比較，取得低于門限值并且是所有差值中最小的1個(gè)差值，則對(duì)應(yīng)這個(gè)最小差值的候選路段就是當(dāng)前的匹配路段［9］。

曲線擬合算法的原理如圖1，假設(shè)點(diǎn)1，2，3是已匹配點(diǎn)，點(diǎn)4是待匹配點(diǎn)，由圖可知擬合直線與路段1夾角較小，故點(diǎn)4 被匹配到路段1。由于基于曲線擬合的地圖匹配算法不是單個(gè)測(cè)試點(diǎn)獨(dú)立匹配，而是考慮了車輛軌跡的連續(xù)性，使得此算法具有較強(qiáng)的穩(wěn)定性，對(duì)于交叉點(diǎn)的匹配問(wèn)題也能很好地解決。

1.2 基于網(wǎng)絡(luò)拓?fù)涞牡貓D匹配算法

使用路段連通性或路段的幾何形狀的地圖匹配算法是基于網(wǎng)絡(luò)拓?fù)涞牡貓D匹配算法。它通過(guò)對(duì)前1次匹配結(jié)果和車輛前進(jìn)方向的分析，利用道路層的空間網(wǎng)絡(luò)拓?fù)潢P(guān)系，確定當(dāng)前GPS定位點(diǎn)的候選路段的范圍，并計(jì)算出當(dāng)前GPS定位點(diǎn)的匹配點(diǎn)。該算法的依據(jù)是：車速有限，在一定時(shí)間范圍內(nèi)，車輛只能行駛在與上一匹配路段相連的道路上，不可能在其他路段［10］。

圖1 曲線擬合原理圖Fig.1 Principle diagram of curve fitting

2 綜合地圖匹配算法的實(shí)現(xiàn)

基于曲線擬合的地圖匹配算法充分利用了GPS歷史數(shù)據(jù)，使得該算法在匹配路段的選擇方面具有較強(qiáng)的穩(wěn)定性，但是它只考慮了擬合直線與候選路段的斜率，以及定位點(diǎn)與候選路段的距離關(guān)系，對(duì)于相互靠近的平行路段則無(wú)法準(zhǔn)確辨別，所以對(duì)于這類路段，僅僅依靠曲線擬合算法會(huì)造成匹配錯(cuò)誤。網(wǎng)絡(luò)拓?fù)浞从车氖堑缆分g的連通關(guān)系，在一定時(shí)間范圍內(nèi)，車輛只能行駛在與上一匹配路段相連的道路上，而平行路段中只可能有1條（即匹配路段）是與上一匹配路段相連的，因此，利用網(wǎng)絡(luò)拓?fù)潢P(guān)系可以排除平行路段的干擾。本文的地圖匹配算法基于曲線擬合并結(jié)合路網(wǎng)拓?fù)潢P(guān)系，不但能彌補(bǔ)基于曲線擬合的地圖匹配算法在距離較近的平行路段匹配率不佳的缺點(diǎn)，還能有效縮小候選路段的搜索范圍，減小算法復(fù)雜度。

2.1 數(shù)據(jù)預(yù)處理

城市道路路況復(fù)雜，隧道、立交橋和密集的高大建筑物的存在導(dǎo)致GPS信號(hào)盲區(qū)的產(chǎn)生，在傳輸過(guò)程中，因通信或建筑物、樹(shù)木、橋梁阻隔等原因?qū)е聰?shù)據(jù)缺失，經(jīng)緯度或速度突變，導(dǎo)致錯(cuò)誤數(shù)據(jù)和數(shù)據(jù)丟失［11］。為了提高地圖匹配的精度，有必要對(duì)GPS數(shù)據(jù)進(jìn)行預(yù)處理，剔除經(jīng)緯度或速度突變的數(shù)據(jù)并插值補(bǔ)全缺失的數(shù)據(jù)［12］。

2.2 候選路段的確定

誤差區(qū)域是指包含車輛真實(shí)位置的區(qū)域，確定候選路段之前首先要確定誤差區(qū)域。圓概率誤差（R95＝2DRMS／1.2。其中：2DRMS 為GPS接收機(jī)的雙倍距離均方根差）是在以GPS接收機(jī)天線真實(shí)位置為圓心的圓內(nèi)、偏離圓心概率為95%的二維點(diǎn)位精度分布度量。也即是說(shuō)，GPS接收機(jī)接收到的測(cè)量值以95%的概率落在以GPS接收機(jī)天線真實(shí)位置為圓心、R95為半徑的圓內(nèi)。因此以GPS定位點(diǎn)為圓心，圓概率誤差為半徑的圓形區(qū)域可以確定1個(gè)誤差圓區(qū)域，并從電子地圖數(shù)據(jù)庫(kù)中提取出與該誤差圓相交的路段集L＝｛l1，l2，…，ln｝?？紤]路網(wǎng)拓?fù)潢P(guān)系，從路段集L中取出與上1 個(gè)匹配道路有鄰接關(guān)系的路段作為候選路段。如圖2，點(diǎn)O是待匹配的GPS定位點(diǎn)，圓O是誤差圓，則與該誤差圓相交的路段集為L(zhǎng)＝｛1，2，…，7｝，當(dāng)前時(shí)刻車輛行駛在道路1上，則下一時(shí)刻車輛只能出現(xiàn)在與道路1相連的道路2，道路3，道路4上，故候選路段為道路2，道路3，道路4。

圖2 候選路段的選擇Fig.2 Choice of the candidate roads

2.3 匹配路段的確定

綜合算法采用最小二乘法進(jìn)行曲線擬合，設(shè)觀測(cè)點(diǎn)的坐標(biāo)為Pi（xi，yi）（i＝1，2，…，n）。用1個(gè)m次多項(xiàng)式y(tǒng)＝a0＋a1x＋…＋amxm來(lái)擬合n個(gè)觀測(cè)點(diǎn)數(shù)據(jù)，使得偏差的平方和最小。偏差的平方和

為了求得符合條件的aj（j＝0，1，…，m），對(duì)等式右邊求aj偏導(dǎo)數(shù)，并令這些偏導(dǎo)數(shù)等于0。將等式化簡(jiǎn)并寫成矩陣形式，就可以得到下面的矩陣。

也就是說(shuō)XA＝Y(jié)，那么A＝（XTX）－1XTY，這樣就得到了系數(shù)矩陣。

電子地圖中的路段是用直線段或折線來(lái)近似的，由于車輛在道路上行駛的這個(gè)前提，在一定的行駛距離內(nèi)，可以用直線擬合車輛的行駛軌跡。根據(jù)道路本身的最短長(zhǎng)度，本文選取4個(gè)觀測(cè)點(diǎn)，作1次曲線擬合，即直線擬合。由上述的曲線擬合的原理求得軌跡擬合的直線斜率

式中：（xi，yi），i＝1，2，3，4為4個(gè)GPS定位點(diǎn)的坐標(biāo)。

k反映了車輛大致行駛方向，在測(cè)量誤差允許的范圍內(nèi)，認(rèn)為和軌跡夾角30°以內(nèi)的路段是可以接受的。從而列出綜合算法的評(píng)價(jià)函數(shù)z［13］為

式中：k0為候選路段的斜率；d為測(cè)量位置點(diǎn)到候選路段的垂直投影距離；R為誤差圓半徑，w1，w2為夾角和距離的權(quán)值。選取使評(píng)價(jià)函數(shù)最小的候選路段作為匹配路段。由于方向權(quán)重高于距離權(quán)重，本文取w1＝0.6，w2＝0.4。

2.4 匹配點(diǎn)的確定

選擇了匹配路段后，用垂直投影法確定匹配點(diǎn)，而且要保證匹配點(diǎn)在路段內(nèi)。設(shè)定位點(diǎn)為D（x，y），其匹配路段2 端點(diǎn)坐標(biāo)為S（x1，y1），E（x2，y2），投影點(diǎn)為N（x0，y0），x0，y0根據(jù)式（5）得出，d1為投影點(diǎn)N到S的距離，d2為N到E的距離。比較N與S，E的坐標(biāo)，若N在線段內(nèi)，N

即為匹配點(diǎn)，如圖3（a）；若N 不在線段內(nèi)，且d1＞d2，匹配點(diǎn)為E；否則匹配點(diǎn)為S，見(jiàn)圖3（b），（c）。

3 綜合算法的實(shí)驗(yàn)驗(yàn)證

圖4為終端號(hào)為22的北京市物流電動(dòng)出租車的部分行駛軌跡，行駛方向?yàn)槿f(wàn)紅路→酒仙橋東路→酒仙橋北路。由于GPS定位誤差的存在，使得部分定位點(diǎn)之間間隔過(guò)大且定位點(diǎn)與道路偏離。采用本文提出的綜合算法解決這些問(wèn)題，主要完成3個(gè)任務(wù)。

圖3 匹配點(diǎn)的確定Fig.3 Confirmation of the matching point

1）預(yù)處理GPS 數(shù)據(jù)，使其符合車輛行駛規(guī)律。

2）匹配車輛定位點(diǎn)到正確的路段上。3）確定車輛在路段上的位置。

圖4 GPS定位點(diǎn)Fig.4 Locating points

GPS接收機(jī)每5s接收1次數(shù)據(jù)，因此以5s為間隔插值補(bǔ)全GPS 數(shù)據(jù)，由物流電動(dòng)車內(nèi)的GPS接收機(jī)的雙倍距離均方根差得到誤差圓半徑為66.7 m，然后按綜合算法流程進(jìn)行候選路段、匹配路段和匹配點(diǎn)的確定。圖5顯示利用本文算法的匹配結(jié)果。圖6是基于曲線擬合算法得到的匹配結(jié)果，由于圖中上下2條平行路段距離比較近且部分定位點(diǎn)偏離路段的距離相對(duì)較大，所以這2條路段都被包含在誤差圓內(nèi)，基于曲線擬合的地圖匹配算法又有其自身的局限性，故出現(xiàn)了圖6所示的錯(cuò)誤匹配。

將綜合算法應(yīng)用到多個(gè)樣本進(jìn)行實(shí)驗(yàn)驗(yàn)證，匹配率都在95%以上，單點(diǎn)匹配時(shí)間均在5 ms以內(nèi)。由于綜合算法顯著地縮小了候選路段的范圍，而影響地圖匹配算法實(shí)時(shí)性的主要因素就是候選路段的確定，故其減少了匹配時(shí)間。表1所示為綜合算法與基于曲線擬合的算法之間匹配率和單點(diǎn)匹配時(shí)間的對(duì)比。

圖5 綜合算法匹配結(jié)果Fig.5 The matching result of comprehensive algorithm

圖6 基于曲線擬合算法匹配結(jié)果Fig.6 The matching result of curve fitting algorithm

表1 實(shí)驗(yàn)結(jié)果Tab.1 Experimental results

實(shí)驗(yàn)結(jié)果表明：本文提出的綜合算法能比較精確的把定位點(diǎn)匹配到道路上，能解決基于曲線擬合匹配算法對(duì)比較靠近的平行路段進(jìn)行匹配時(shí)容易出錯(cuò)的問(wèn)題，因此，綜合算法能應(yīng)用到地圖匹配的實(shí)踐中。

4 結(jié)束語(yǔ)

筆者提出1種基于曲線擬合和網(wǎng)絡(luò)拓?fù)涞木C合地圖匹配算法，詳細(xì)描述了匹配的4個(gè)步驟：數(shù)據(jù)預(yù)處理、候選路段的確定、匹配路段的確定和匹配點(diǎn)的確定。最后將該算法應(yīng)用到實(shí)際的匹配工作中，運(yùn)行結(jié)果表明：該算法精度高、效率好，能解決基于曲線擬合算法在靠近的平行路段匹配率不佳的問(wèn)題，具有很好的實(shí)用價(jià)值。

筆者所指的算法沒(méi)有考慮立交橋區(qū)域內(nèi)的地圖匹配，可在此方面做進(jìn)一步的研究。

［1］White C E，Bernstein D，Komhauser A L.Some map matching algorithms for personal navigation assistants［J］.Transportation Research Part C，2000（8）：91－108.

［2］張 攀，朱敦堯.車載導(dǎo)航地圖服務(wù)發(fā)展探討［J］.交通信息與安全，2013，31（5）：127－130.Zhang Pan，Zhu Dunyao.Development of car navigation map service［J］.Jounal of Transport Information and safety，2013，31（5）：127－130.（in Chinese）

［3］曾吉全.GPS車輛自導(dǎo)航系統(tǒng)關(guān)鍵技術(shù)研究［D］.西安：西安電子科技大學(xué)通信工程學(xué)院，2004.Zeng Jiquan.The study of key technology of vehicle navigation system［D］.Xi′an：School of Telecommunications Engineering of Xidian University，2004.（in Chinese）

［4］Quddusma，Washingtonyo，Robertbn.Current map－matching algorithms for transport applications：state of the art and future research directions［J］.Transportation Research Part C，2007（15）：312－328.

［5］盧文濤，周銀東，梅順良，等.基于拓?fù)浣Y(jié)構(gòu)的地圖匹配算法研究［J］.測(cè)控技術(shù)，2010，29（6）：73－76.Lu Wentao，Zhou Yindong，Mei Shunliang，et al.The research of map matching algorithm based on topology structure［J］.Measurement and Control Technology，2010，29（6）：73－76.（in Chinese）

［6］胡 林，谷正氣，楊 易.基于權(quán)值D－S證據(jù)理論的車輛導(dǎo)航地圖匹配［J］.中國(guó)公路學(xué)報(bào)，2008，21（2）：116－120.Hu Lin，Gu Zhengqi，Yang Yi.The vehicle navigation system map matching based on D－S theory［J］.China Journal of Highway and Transport，2008，21（2）：116－120.（in Chinese）

［7］蘇海濱，王光政，王繼東.基于模糊神經(jīng)網(wǎng)絡(luò)的地圖匹配算法［J］.北京科技大學(xué)學(xué)報(bào)，2012，34（1）：43－47.Su Haibin，Wang Guangzheng，Wang Jidong.The map matching algorithm based on fuzzy nerve network［J］.Journal of Beijing Science and Technology University，2012，34（1）：43－47.（in Chinese）

［8］Velaga Nagendra R，Quddus Mohammed A，Bristow Abigail L.Improving the performance of a topological map－matching algorithm through error detection and correction［J］.Intelligent Transportation System，2012，16（3）：147－158.

［9］鐘海麗，童瑞華，李 軍.GPS定位與地圖匹配方法的研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2003，24（1）：109－113.Zhong Haili，Tong Ruihua，Li Jun.The research of GPS localization and map－matching method［J］.Small Microcomputer System，2003，24（1）：109－113.（in Chinese）

［10］Li Liang，Quddus Mohammed，Zhao Lin.High accuracy tightly－coupled integrity monitoring algorithm for map－matching［J］.Transportation Research Part C，2013（36）：13－26.

［11］王志建，王 力，汪 健.基于拓?fù)渑袛嗟暮Ａ縂PS 數(shù)據(jù)延時(shí)地圖匹配算法［J］.西南交通大學(xué)學(xué)報(bào)，2012，47（5）：861－866.Wang Zhijian，Wang Li，Wang Jian.Delay map matching algorithm of mass gps data based on topological judgment［J］.Journal of Southwest Jiantong University，2012，47（5）：861－866.（in Chinese）

［12］張達(dá)夫，張昕明.基于時(shí)空特性的GPS軌跡數(shù)據(jù)壓縮算法［J］.交通信息與安全，2013，31（3）：6－9.Zhang Dafu，Zhang Xinming.A spatiotemporal compression algorithm for GPS trajectory data［J］.Jounal of Transport Information and Safety，2013，31（3）：6－9.（in Chinese）

［13］周 穎，程蔭杭.基于曲線擬合的地圖匹配算法［J］.交通運(yùn)輸系統(tǒng)工程與信息，2004，4（2）：68－70.Zhou Ying，Cheng Yinhang.Map－matching algorithm based on curve－fitting model［J］.Journal of Transportation Systems Engineering and Information Technology，2004，4（2）：68－70.（in Chinese）