基于大規模浮動車軌跡點數據的道路網變化檢測與更新方法研究

趙 東 保,劉 雪 梅,張 弘 弢

(1.華北水利水電大學資源與環境學院,河南 鄭州 450011;2.華北水利水電大學信息工程學院,河南 鄭州 450011;3.四川省基礎地理信息中心,四川 成都 610041)

基于大規模浮動車軌跡點數據的道路網變化檢測與更新方法研究

趙 東 保1,劉 雪 梅2,張 弘 弢3

(1.華北水利水電大學資源與環境學院,河南 鄭州 450011;2.華北水利水電大學信息工程學院,河南 鄭州 450011;3.四川省基礎地理信息中心,四川 成都 610041)

針對矢量道路網的變化檢測與更新問題，提出一種基于大規模浮動車軌跡點數據的道路網快速變化發現與更新方法。首先對矢量道路網進行柵格化處理，并根據若干天內浮動車GPS軌跡點落在柵格內的個數對柵格賦值。經過對軌跡柵格圖像的低通濾波、邊界清理后，采用數學形態學方法提取軌跡柵格圖像的骨架線，通過判斷道路骨架線與更新前道路網緩沖區之間的位置關系，快速識別出變化道路，即新增道路和消失道路。最后，對更新道路的骨架線分別進行剪枝處理、斷線連接以及節點融合，實現對原有道路網道路數據的提示性更新。結果表明：與傳統方法相比，該方法能夠以更低的成本和更好的現勢性對現有道路網進行在線增量式快速變化檢測和更新。

道路網更新;變化檢測;浮動車技術;GPS軌跡點;志愿者地理信息

0 引言

矢量道路網是導航地圖的重要基礎性地理要素。伴隨著經濟社會的快速發展，我國城市道路的建設變化多、發展快，如果導航地圖無法做到及時快速更新，其現勢性將不能滿足應用需求[1]。為了實現電子地圖的快速更新，近年來涌現出的志愿者地理信息采集是一個切實可行的有效手段[2-4]，即每一個地理信息采集愛好者都可以對地圖的變化部分進行主動測量和修訂。對于矢量道路網而言，還存在一種寶貴的大眾地理數據源，這就是浮動車數據[5]。國內的大城市一般有上萬輛出租車(可作為浮動車)，其GPS采樣間隔多在30～300 s，它們覆蓋面廣，全天候行駛。通過在服務器端對大數據量出租車GPS軌跡的被動式分析，就可以繪制出道路網地圖，基于這種思路已經涌現出三類方法。一是K-means類算法[6-8]，將大規模出租車留下的軌跡點數據利用K-means類算法進行聚類，再從聚類中提取中心線作為道路要素。二是核密度估計算法[9-11]，首先將GPS軌跡點數據轉換成柵格圖像，每個像素值反映了軌跡點落入該像素的密度，設定閾值將柵格圖像轉換成二值圖像，再提取圖像骨架線，并將骨架線作為道路中心線。三是軌跡合成算法[12-15]，不但考慮單個軌跡點數據，還考慮軌跡點所連成的軌跡線，將這些軌跡線數據合成以生成道路。對上述三類方法對比發現，第二類方法效果最好[16]。

盡管上述三類方法利用大規模浮動車軌跡數據理論上足以生成道路網地圖。但實際上，受限于各種復雜因素的影響，所生成的道路網在準確性上仍然無法與專業的導航地圖相媲美。另一方面，道路數據也處于不斷發展變化中，沒有必要完全從頭開始生成道路網地圖。基于這種思路，本文將以核密度估計算法為基礎，基于對大規模浮動車軌跡點數據的分析，快速檢測道路網的幾何變化情況，并實現變化道路與原有道路網的數據融合，從而形成道路網的增量式提示性更新。通過將提示性更新內容反饋給現有導航地圖生產商，可服務于導航地圖的及時修補測繪。

1 基于浮動車軌跡點數據的道路網自動變化發現與更新

1.1 算法總體思路

本文算法共包括三大部分，首先是數據預處理階段；設定一定的格網尺寸，對大規模浮動車軌跡點數據進行柵格化處理，通過統計落在每個柵格內的軌跡點個數，將柵格轉換為二值化軌跡柵格圖像。然后是變化檢測階段，采用數學形態學方法提取軌跡柵格圖像的中心線，再通過判斷道路骨架線及其所在道路面狀柵格區域與原有道路中心線及其緩沖區面狀區域之間的空間位置關系來確定道路的變化情況。最后是更新道路與原有道路網的數據融合，在該階段，對新增道路數據進行剪枝、斷線連接、節點融合等，以確保在幾何與拓撲信息上與原有道路網數據融為一體，實現對原有道路網數據的自動更新。

1.2 數據預處理——軌跡柵格圖像的生成

海量GPS軌跡點大都位于道路兩側區域，具有明顯的聚集性質，將這些具有聚集性質的點數據相連成面，就可在一定程度上恢復出道路的路面。其方法是首先對矢量道路網進行柵格化處理，柵格尺寸可設定與車輛的大小基本一致，如5 m×5 m。接著判斷落入每個格網中GPS軌跡點的個數，若超過一定閾值(本文設為1個)，則該柵格賦值為1，反之賦值為0。經過柵格化賦值處理后，初步的二值化軌跡柵格圖像即可大致生成。為了確保軌跡柵格圖像的準確性，還須進行如下步驟：一是軌跡柵格圖像的低通濾波[17],目的在于對軌跡柵格圖像進行平滑操作。由于GPS信號的缺失，或者留下的GPS軌跡點數目較少，本是相連的道路區域可能會存在小中斷，低通濾波將有助于減弱這種情形的存在。圖1a中道路區域存在許多中斷現象，采用低通濾波后，中斷區域得以相連(圖1b)。二是軌跡柵格圖像的邊界清理，目的在于減弱軌跡柵格圖像中孤立噪音的干擾，并使得軌跡柵格圖像更為規整。邊界清理的方法是按照規定模板窗口(如5×5模板)將整個柵格區域均勻劃分為多個模板區域，且相互間無重疊。而后判斷每一個模板區域內出現次數最多的柵格值，并把該像元值作為該模板區域每一柵格的值。如圖1c所示，GPS測量誤差導致若干GPS軌跡點落在距離道路較遠的區域內，具有明顯的離群現象，是孤立點。采用邊界清理后，不但孤立點被刪除，且道路柵格集合的邊界也更為整齊(圖1d)。

圖1 道路柵格圖像的低通濾波和邊界清理Fig.1 Lowpass filter and boundary clean of road raster image

1.3 道路幾何信息的變化發現

道路幾何信息的變化主要借助于提取軌跡柵格圖像中心線完成，可采用文獻[18]所述的最大圓盤法提取軌跡柵格圖像中柵格區域的骨架線，而骨架線對應著實際的道路中心線，再對所有道路中心線構建緩沖區，根據GPS單點定位精度，緩沖區半徑可設為20～30 m。在構建完成骨架線后，可形成骨架線網絡，遍歷該網絡中的每一個骨架線弧段，設某一條骨架線弧段為S，所對應的軌跡柵格區域為AS，判斷S落在了哪一個道路中心線的緩沖區內部，假設落在了道路中心線L的緩沖區內部，其緩沖區域為AL，分別判斷S與AL的位置關系以及L與AS的位置關系，則有：1)若S落在區域AL之內，且L落在區域AS之內，則S與L二者匹配，即可認為原有道路L未發生變化;反之則認為L發生了變化，包括新增道路和消失道路兩方面。2)凡是S在原有道路網中找不到匹配對象，便可判定S為新增道路，例如若S沒有落在任何一條道路中心線的緩沖區內部，則S即是新增道路。3)凡是L在骨架線網絡中找不到匹配對象，便可判定L可能為消失道路，例如若L沒有落在任何骨架線柵格區域內部，則預示該道路可能為消失道路。

1.4 更新道路與原有道路網的融合

在提取出道路網變化信息后，還須對變化信息做進一步處理，以使其融入到原有道路網數據中，包括對變化部分軌跡柵格圖像骨架線的剪枝、斷線連接與節點融合。1)骨架線剪枝：在提取軌跡柵格圖像骨架線的過程中會存在一些細小分支，其并不代表真實的道路中心線，因此可設定一定閾值，將長度較短的骨架線細小分支予以刪除。2)斷線連接：從軌跡柵格圖像中提取的骨架線并不總能保持連續，有時一條道路中心線對應著多條距離較長的骨架線,其端點間存在著較小的距離。且延伸方向也保持大體一致。因此可設定一定的距離閾值和角度閾值，將那些延伸方向大致相同且端點距離較小的骨架線予以連接。3)節點融合：節點融合類似于斷線連接，不過此處特指更新道路與原有道路網數據的融合操作，對于那些新增的道路或修改的道路，其道路中心線的端點并不能恰好捕捉在原有道路數據上，需要對新生成的道路中心線進行延伸或打斷等處理，本文將這些操作統稱為節點融合。

圖2列舉了上述3種情況，圖2a中黑色粗線為原始道路網數據，細線為新增道路骨架線，分別經過剪枝處理、斷線連接和節點融合，轉變為圖2b，其中新增的道路骨架線數據經過了數據清理后與原有道路網數據融為一體。

圖2 更新道路與原有道路網數據的融合Fig.2 Fusion of new road and original road network

2 算法步驟與實例驗證

2.1 算法步驟

本文具體算法步驟：1)選取一定時間段內所有浮動車的軌跡點數據，并對矢量道路網進行柵格化處理，判斷每個柵格中落入的GPS軌跡點個數，若大于閾值，則該處柵格賦值為1，反之賦值為0，從而生成軌跡柵格圖像。2)按照對初步的二值化軌跡柵格圖像先進行低通濾波，將濾波后柵格屬性值大于0的柵格賦值為1，其余仍為0。而后進行邊界清理，消除孤立噪音。3)借助數學形態學提取軌跡柵格圖像中道路柵格區域的骨架線，其對應道路柵格集合的道路中心線，再生成原有道路網數據的緩沖區。4)通過對比判斷骨架線與原有道路緩沖區區域之間的空間位置關系，可判定該骨架線所代表的道路是否為新增道路、修改道路或被刪除道路，實現道路網幾何變化信息的提取。5) 對那些被確定為新增道路的道路骨架線做進一步處理，包括剪枝、斷線連接、節點融合等，實現新增道路與原有道路網的融合。

2.2 實例驗證

以下結合具體實例進行驗證，數據實例為2006年深圳市1∶5 000矢量道路網數據，2008年5月10日1 800輛采樣間隔為3～5 min的深圳市出租車GPS軌跡數據。圖3為深圳市福田區局部區域矢量道路網，圖4為全天所有出租車在該區域留下的GPS軌跡點，共計31 641個。經過步驟1)后可生成初步的二值化軌跡柵格圖像(圖5)，其中柵格尺寸設置為5 m×5 m。圖6和圖7為步驟2)運行結果，其中邊界清理模板窗口取5×5。圖8和圖9為步驟3)運行結果，其中緩沖區半寬度為30 m。圖10為提取道路網幾何變化信息，其中新增道路為實線。圖11則為步驟5)的運行結果，其中剪枝閾值設為100 m，即某短小分支不超過100 m，即可刪除。斷線連接中相鄰端點的距離閾值設為不超過50 m，延伸方向角度之差不應超過20°。節點融合中相鄰節點距離閾值可設為不超過50 m。重疊相似度閾值設為0.8，在步驟5)完成后，圖11中的新增道路最終與原有道路網進行了融合處理。

圖3 原始道路網數據 圖4 浮動車GPS軌跡點數據 圖5 初步生成二值化道路柵格圖像Fig.3 Origin road network Fig.4 Float car GPS track points Fig.5 Preliminary construction of binarized road network image

圖6 低通濾波 圖7 邊界清理 圖8 骨架線生成

Fig.6 Lowpass filter Fig.7 Boundary clean Fig.8 Construction of skeleton lines

圖9 原有道路網緩沖區與骨架線疊加顯示 圖10 新增道路發現 圖11 新增道路與原有道路網的融合

2.3 實例分析

為驗證本文方法對道路網變化檢測及更新的準確性，特將算法結果與深圳市福田區局部區域最新版導航電子地圖(圖12，來自于最新訪問的主流導航電子地圖——“天地圖”網站[19])進行比對，道路網的變化部分包括新增道路和消失道路。圖11給出了本文方法自動發現的新增道路，圖12中黑色粗實線所在道路則是這些新增道路在最新版電子地圖中的對應情況，可以看出，圖11中的新增道路在現實世界中均有對應道路實體，這就驗證了發現新增道路的準確性。

圖12 深圳市福田區某區域最新道路網電子地圖Fig.12 Newest road network electronic map of Futian District in Shenzhen City

對于消失或封閉道路，一個簡單的判斷標準是：當某條道路較長時間未有GPS軌跡點落入其緩沖區范圍內，則提示該道路可能已消失或封閉。如圖11中的道路b，在一天內鮮有浮動車在其緩沖區范圍內留下軌跡點(圖4)，由此預示道路b為消失道路，但實際生活中，也有一些小路出租車很少行駛，如圖11的道路c是公園內一條道路，因此，即使某條道路長時間內無浮動車在緩沖區范圍內留下軌跡點，也不能完全說明該條道路已經消失或者封閉，有必要進行實地測量以確保其現勢性。

3 結論與展望

本文通過對浮動車軌跡進行數據分析，給出了一種利用大規模浮動車數據發現和更新舊版本道路網數據的有效方法，其意義在于快速發現道路變化，并給出發生變化道路較為準確的位置和形狀，而后，導航地圖生產商仍可采用原有測量技術，僅對變化信息實地測繪,從而加快更新效率。該技術既具有充分的現勢性，且成本較低。事實上，利用浮動車軌跡數據除了可以檢測矢量道路網幾何信息的變化外，還可從浮動車的運行軌跡推理出道路屬性信息的變化，諸如道路車道、單雙向限行、轉彎限制等的變化。未來隨著個人智能手機的進一步普及，大數據的日益充分，通過對這些大眾地理數據源的充分和有效分析，將會促進導航地圖的持久更新以及挖掘背后所隱藏的數據規律。

[1] 崔鐵軍,李宏利,郭鵬,等 .導航電子地圖增量更新服務及關鍵技術研究[J].地理信息世界，2011,9(4):36-39.

[2] 王釗.車輛導航電子地圖的自增量更新[D].北京:清華大學,2012.

[3] GOODCHILD M F.Citizens as sensors:The world of volunteered geography[J].Geojournal,2007,69(4):211-221.

[4] ELWOOD S,GOODCHILD M F,SUI D Z.Researching volunteered geographic information:Spatial data,geographic research,and new social practice[J].Annals of the Association of American Geographers,2012,102(3):571-590.

[5] 王美玲，程林.浮動車地圖匹配算法研究[J].測繪學報，2012,41(1):133-138.

[6] SCHRODL S,WAGSTAFF K,ROGERS S,et al.Mining GPS traces for map refinement[J].Data Mining and Knowledge Discovery,2004,9(1):59-87.

[7] WORRALL S,NEBOT E.Automated process for generating digitised maps through GPS data compression[A].Australasian Conference on Robotics and Automation[C].Brisbane:ACRA,2007.1-6.

[8] AGAMENNONI G,NIETO J I,NEBOT E M.Robust inference of principal road paths for intelligent transportation systems[J].IEEE Trans.on Intelligent Transportation Systems,2011,12(1):298-308.

[9] DAVIES J J,BERESFORD A R,HOPPER A.Scalable,distributed,real-time map generation[J].IEEE Pervasive Computing,2006,5(4):47-54.

[10] CHEN C,CHENG Y.Roads digital map generation with multi-track GPS data[A].International Workshop on Geoscience and Remote Sensing,ETT and GRS[C].Shanghai:IEEE,2008.508-511.

[11] SHEN S,LIU Y.Automatic generation of road network map from massive GPS,vehicle trajectories[A].12th International IEEE Conference on Intelligent Transportation Systems[C].St.Louis:IEEE,2009.1-6.

[12] BIAGIONI J,ERIKSSON J.Map inference in the face of noise and disparity[A].The ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].Redondo Beach:ACM,2012.79-88.

[13] CAO L,KRUMM J.From GPS traces to a routable road map[A].Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].New York:ACM,2009.3-12

[14] NIEHOEFER B,BURDA R,WIETFELD C,et al.GPS community map generation for enhanced routing methods based on trace-collection by mobile phones[A].1st International Conference on Advances in Satellite and Space Communications[C].Colmar:IEEE,2009.156-161.

[15] ZHANG L,THIEMANN F,SESTER M.Integration of GPS traces with road map[A].2nd International Workshop on Computational Transportation Science[C].San Jose:ACM,2010.17-22.

[16] BIAGIONI J,ERIKSSON J.Inferring road maps from global positioning system traces:Survey and comparative evaluation[J].Transportation Research Record:Journal of the Transportation Research Board,2012,2291:61-71.

[17] 岡薩雷斯，伍茲(著).阮秋琦(譯).數字圖像處理(第二版)[M].北京：電子工業出版社，2007.

[18] 鄒修明.柵格地圖矢量化關鍵技術研究[D].南京:南京理工大學,2012.

[19] http://www.tianditu.cn/map/index.html[EB/OL].2013-02-15.

Automated Change Detection and Update of Vector Road Network Based on Large Scale Floating Car Data

ZHAO Dong-bao1,LIU Xue-mei2,ZHANG Hong-tao3

(1.InstituteofResourcesandEnvironment,NorthChinaUniversityofWaterConservancyandElectricPower，Zhengzhou450011;2.InstituteofInformationEngineering,NorthChinaUniversityofWaterConservancyandElectricPower，Zhengzhou450011;3.GeomaticsCenterofSichuanProvince,Chengdu610041,China)

Aiming at continued and timely map update of vector road network,this paper realizes an automated change detection and suggestive update of vector road network by analyzing crowdsourcing spatial data-large scale floating car GPS data.The method proposed in this paper firstly rasterize vector road network map by setting a proper grid size,and then assign a value to every pixel according to the count which several days of GPS track points are fall within grid,and final binarized road image can be obtained by further low pass filtering and boundary cleaning.Secondly,skeleton lines of road raster collection which correspond to vector road centerlines can be extracted by means of Mathematical Morphology,and road change including new roads,modified roads and missing roads can be quickly detected by comparing the spatial relationship between road raster area where road skeleton line lie in and buffer area of the existing road centerline.At last,after trimming,merging and connecting the broken skeleton line,skeleton lines,as the updated road centerlines,can be merged into the existing road network finally.

road network update;change detection;floating car technology;GPS track points;volunteer geographic information

2015-08-27；

2015-10-28

四川省地理國情監測工程技術研究中心開放基金項目(GC201510);衛星測繪與應用國家測繪地理信息局重點實驗室開放基金項目(KLSMTA-201510);河南省高校科技創新團隊支持計劃項目(13IRTSTHN023);國家自然科學青年基金項目(41201467)

趙東保(1979-)，男，博士，副教授，主要研究方向為空間數據融合與集成。E-mail:zdongbao@126.com

10.3969/j.issn.1672-0504.2016.02.001

P208;P228.4;U491.116

A

1672-0504(2016)02-0001-05