楊 偉,艾 廷 華

(武漢大學資源與環(huán)境科學學院，湖北 武漢 430079)

基于眾源軌跡數(shù)據(jù)的道路中心線提取

楊 偉,艾 廷 華*

(武漢大學資源與環(huán)境科學學院，湖北 武漢 430079)

從眾源軌跡數(shù)據(jù)中提取道路幾何數(shù)據(jù)相對于傳統(tǒng)的道路數(shù)據(jù)獲取方法具有低成本、高現(xiàn)勢性的優(yōu)點。然而，由于軌跡數(shù)據(jù)采樣稀疏、數(shù)據(jù)量大、高噪音等特征使得道路中心線提取仍顯困難。針對該問題，提出一種基于約束Delaunay三角網(wǎng)的道路中心線提取方法。首先對預處理后的車輛軌跡線構建約束Delaunay三角網(wǎng)，根據(jù)整體長邊約束準則刪除長邊以提取道路面域多邊形；然后對道路面多邊形二次構建Delaunay三角網(wǎng)，提取道路中心線。利用北京市一天時間的出租車軌跡數(shù)據(jù)進行算法實驗，將實驗結果與柵格化方法結果進行定性定量地評價分析。結果表明該方法提取的道路中心線數(shù)據(jù)在幾何、拓撲精度方面比柵格化方法提高約10%以上。另外，以復雜環(huán)形道路為例，證明了該方法比柵格化方法更適合于復雜道路結構、較大密度差異的軌跡數(shù)據(jù)。因此，該方法不僅適合大數(shù)據(jù)處理、結果精度高,且算法成熟、易于實現(xiàn)。

眾源軌跡數(shù)據(jù)；道路提??；道路中心線；Delaunay三角網(wǎng)

0 引言

道路地圖數(shù)據(jù)是國家基礎地理信息、智能交通的重要組成部分，在智慧城市建設、車輛智能導航、網(wǎng)絡地圖服務、地圖數(shù)據(jù)更新等方面起著關鍵作用。然而，傳統(tǒng)的道路網(wǎng)數(shù)據(jù)獲取主要是專業(yè)測繪部門的實地測量、遙感影像的矢量化制圖兩種方式,不僅技術、成本要求高，且數(shù)據(jù)獲取周期長、數(shù)據(jù)處理與維護工作量大，難以滿足當前人們對路網(wǎng)數(shù)據(jù)高實時性、低成本的要求。因此，迫切需要一種經(jīng)濟適用、快速自動獲取城市路網(wǎng)數(shù)據(jù)的新方法。

雖然道路提取取得了較多成果，但仍存在一些問題：1)算法相對復雜，面對海量的軌跡數(shù)據(jù)難以自動化、快速地提取道路中心線，并保證數(shù)據(jù)的幾何拓撲精度。2)已有算法大多處理采樣間隔1～4 s的高精度軌跡數(shù)據(jù)，并不適用于稀疏采樣(采用間隔40 s)、高噪音軌跡數(shù)據(jù)。因此，本文從圖論的角度引入Delaunay三角網(wǎng)模型，對加密軌跡線構建Delaunay三角網(wǎng)，利用Delaunay三角網(wǎng)的空間剖分特性、空間臨近關系自動提取道路中心線。運用北京市出租車軌跡數(shù)據(jù)進行實驗，提取了道路中心線幾何數(shù)據(jù)，證明了該方法的有效性。

1 道路中心線提取流程及軌跡數(shù)據(jù)預處理

1.1 道路中心線提取流程

Delaunay三角網(wǎng)作為一種構建數(shù)據(jù)集拓撲關系的方法，廣泛應用于模式識別、空間數(shù)據(jù)挖掘如數(shù)據(jù)聚類[20,21]、多邊形提取中軸線[17,18,22]等領域。利用Delaunay三角網(wǎng)能很好地識別車輛軌跡數(shù)據(jù)沿道路網(wǎng)分布的條帶狀空間分布模式，并根據(jù)三角形的鄰接關系快速提取道路中心線。故本文對加密軌跡線構建約束Delaunay三角網(wǎng)，利用約束Delaunay三角網(wǎng)特性提取道路中心線,提取方法流程如圖1所示。約束Delaunay三角網(wǎng)生成算法很多，這不是本文研究的重點，本文利用ArcGIS提供的開發(fā)接口構建三角網(wǎng)。

圖1 道路中心線提取流程Fig.1 The process of road centerline extraction

1.2 軌跡預處理及加密

由于車輛軌跡采樣間隔稀疏、建筑物遮擋、GPS信號漂移等原因，導致大量的噪音軌跡數(shù)據(jù)且對道路中心線提取產(chǎn)生干擾。軌跡點預處理包括經(jīng)緯度越界、時間格式不正確、軌跡點丟失等情況的處理；軌跡線預處理包括刪除短軌跡線、刪除軌跡線方向變化大且直接穿越不同道路的異常軌跡線。由于軌跡采樣稀疏，如果直接對原始軌跡線構建約束Delaunay三角網(wǎng)則會破壞三角網(wǎng)的最鄰近性特征，很難表征軌跡數(shù)據(jù)的空間分布模式并識別道路輪廓(圖2a)。故本文將軌跡線進行加密以保證道路中心線提取的精度。軌跡線加密的規(guī)則為：首先確定加密步長閾值w，當軌跡線上相鄰兩軌跡點的距離大于閾值w時，則進行加密，反之不加密。本研究加密步長默認為道路平均寬度，也可根據(jù)需要設定。假設pi、pi+1是軌跡線上相鄰的兩軌跡點，當|pipi+1|>w時，則加密點(Qk)的橫、縱坐標為：

(1)

圖2 加密軌跡線構建Delaunay三角網(wǎng)Fig.2 Constructing Delaunay triangulation after the trajectory interpolated

2 基本原理與方法

2.1 道路面域多邊形提取

作為一種新型復合調味品，雞精成功運用了鮮味相乘的原理，實現(xiàn)了鮮度在味精基礎上的成功翻倍。同時，由于添加了雞肉等物質，雞精嘗起來更醇厚自然，更為重要的是雞精只調鮮、不串味，能夠很好地保留菜肴原本的味道。一個以雞精為代表的鮮味時代也正式開啟。

從軌跡線構建的Delaunay三角網(wǎng)中可看出軌跡線聚集的內部區(qū)域三角形分布密集、邊長面積較小，而軌跡線簇外的三角形邊長面積都較大。因此，三角網(wǎng)中三角形的邊長可分為兩類，位于道路外空白區(qū)域的長邊和位于道路內部的短邊。故只需刪除Delaunay三角網(wǎng)的長三角形即可較好地識別道路面域輪廓，便于提取道路中心線。根據(jù)Delaunay三角網(wǎng)邊長的統(tǒng)計特征，得出一種整體長邊邊長約束準則。三角形長邊刪除閾值由以下幾個參數(shù)決定：

定義1 三角網(wǎng)整體邊長均值： 由軌跡線簇Traj構建的Delaunay三角網(wǎng)DT(Traj)中，其所有邊長的均值定義為整體邊長均值，記為Global_Mean，即有：

(2)

式中:n表示Delaunay三角網(wǎng)中邊的數(shù)量；|ei|表示第i條邊的長度。

定義2 三角網(wǎng)整體邊長變異： 給定一個圖G(三角網(wǎng))，所有邊長的標準差定義為整體邊長變異，記為Global_Variation，即有：

(3)

(4)

式中:n表示K階鄰域內邊的數(shù)目；|ej|表示第j條邊的長度。故在三角網(wǎng)中任意一個頂點pi(軌跡點)整體長邊約束準則Global_CutValue(pi)，公式表示為：

Global_CutValue(pi)=Global_Mean(DT)+

(5)

圖3 道路多邊形提取Fig.3 Raw road polygon extraction

2.2 道路中心線提取

2.2.1 三角形類型確定及中心線提取 對提取的道路面多邊形二次構建Delaunay三角網(wǎng)，并標記所有三角形的類型，目的是提取道路網(wǎng)中心線。根據(jù)三角形與道路多邊形的鄰接關系，可將三角形分為4類(圖4):第0類三角形是位于多邊形外部的三角形，是無效三角形，對于提取道路中心線沒有意義;將位于多邊形內部的三角形分為3類，第1類三角形只有1個鄰接三角形，第2類有兩個鄰接三角形，第3類是該三角形3條邊都有鄰接三角形。從圖4中可以看出不同類型三角形的分布規(guī)律，第1類三角形位于道路多邊形出口、第3類三角形位于道路交叉口處、第2類三角形位于道路干線上，這種分布利于提取道路中心線。

圖4 道路中心線提取方法Fig.4 The method of road centerline extraction

對于道路中心線的提取，首先判斷三角形是否是有效三角形。對于有效三角形，如果是第1類三角形，提取橋接邊(有鄰接三角形的邊)的中點和另外兩邊中較長一邊的中點，如圖4中的點p5、p4；如果是第2類三角形提取兩個橋接邊的中點，如圖4中的點p3；如果是第3類三角形則需提取該三角形的重心和3條橋接邊的中點，如圖4中的點p1、Q1。故道路中心線提取算法：從任意一個1類或3類三角形出發(fā)依次按三角形的臨近關系逐次搜索、按中心線提取原則依次提取相應節(jié)點，終止于1類或3類三角形，則得到一條道路網(wǎng)中心線，當所有的1類三角形作為出發(fā)或終止搜索過一遍，所有的3類三角形作為出發(fā)或終止搜索過三遍，道路網(wǎng)中心線提取完畢。

2.2.2 道路中心線小毛刺剔除 由于軌跡線數(shù)據(jù)的特殊性(軌跡線的方向變化、軌跡點的疏密程度等)，往往使得提取的道路面多邊形邊界不平滑，本文稱為“多邊形突刺”。多邊形突刺則會導致出現(xiàn)圖5a中的異常1類三角形，這種異常1類三角形往往導致更多異常的2類、3類三角形，這些異常三角形對道路中心線提取產(chǎn)生嚴重干擾。如圖5b、圖5c中提取的道路中心線出現(xiàn)了許多短小的分支中心線，這些分支中心線并不是真實的道路，本文稱為“中心線小毛刺”,其是由道路多邊形突刺在道路干道邊界生成的1類異常三角形(1類三角形應分布在道路末端)所造成(圖5a、圖5c)。由于這種小毛刺的長度小于道路寬度,且這種線段起止點分別是第3類三角形和第1類三角形，故傳統(tǒng)的解決方法是利用路寬的閾值刪除小毛刺;但這種方法只適合于簡單的道路結構，如遇到圖5c中的復雜環(huán)形道路交叉口則會造成誤刪。故本文結合傳統(tǒng)的方法，提出了一種新的解決策略，即基于面積閾值刪除道路干道邊界1類異常三角形。

圖5 復雜道路交叉口處中心線提取Fig.5 Road centerline extraction in complex road intersection

通過統(tǒng)計分析發(fā)現(xiàn)，第1類三角形的面積大小呈兩個極端分布:1)面積較小的由于道路邊界突刺引起的異常1類三角形;2)面積較大的位于道路口末端的正常1類三角形。故根據(jù)面積大小閾值，結合三角網(wǎng)特性刪除這些由道路邊界突刺引起的三角形，最后只保留道路末端的正常1類三角形。面積閾值公式為：

AreaCutValue=MeanArea+α*StdDev

(6)

式中:AreaCutValue為面積刪除閾值，MeanArea為Delaunay三角網(wǎng)中所有三角形的平均面積、α為自適應系數(shù)(默認為1)、StdDev為三角網(wǎng)中三角形面積的標準差。根據(jù)面積閾值不斷刪除異常1類三角形，直到道路網(wǎng)干道邊界沒有異常1類三角形為止。

2.2.3 道路網(wǎng)數(shù)據(jù)后處理 提取的道路中心線在第3類三角形處往往出現(xiàn)節(jié)點接頭處斷開、道路中心線節(jié)點在面積較大的第2類三角形處出現(xiàn)角度突變(圖6)，這不符合常規(guī)電子地圖與矢量數(shù)據(jù)的標準，故須對提取的道路中心線幾何數(shù)據(jù)進行優(yōu)化處理,包括道路中心線的光滑處理與位于第3類三角形處的道路節(jié)點的合并優(yōu)化。道路中心線由一些列節(jié)點構成，故采用最小二乘法進行直線擬合，得到平滑的道路中心線：y=ax+b，其中:

(7)

由于第3類三角形的重心在道路網(wǎng)絡圖中始終連接3條道路網(wǎng)絡邊，故凡是十字道路交叉口都變成了兩個“V”字形連接(圖6a)。這種連接現(xiàn)象都發(fā)生在相鄰的兩個第3類三角形處，故本文通過找出起止點都為第3類三角形重心的線段，刪除該線段，用這兩個相鄰的第3類三角形的公共邊的中點代替，這樣就得到了正確路網(wǎng)數(shù)據(jù)(圖6b)。

圖6 道路中心線優(yōu)化處理Fig.6 The centerline optimization processing

3 實驗分析與結果評價

3.1 實驗數(shù)據(jù)集與實驗環(huán)境

出租車GPS軌跡數(shù)據(jù)來源于微軟研究院鄭宇團隊的TDriver數(shù)據(jù)[23]，為北京城區(qū)2008年2月3日一天的出租車軌跡數(shù)據(jù)。其中出租車軌跡數(shù)據(jù)包括車輛標識ID、GPS時間、GPS經(jīng)度、GPS緯度等信息。軌跡點采樣間隔為 5～60 s不等，共有軌跡點3 055 105個，生成軌跡線124 506條，預處理后為45 768條(圖7)。為驗證本文提出的道路中心線提取方法，本文在P4/2G/1G/Win7環(huán)境下，基于ArcGIS平臺采用C#編程語言開發(fā)了基于眾源時空軌跡數(shù)據(jù)的道路中心線提取實驗系統(tǒng)，在此系統(tǒng)的支持下從北京市一天的出租車GPS軌跡中提取道路中心線。

3.2 實驗結果分析

對預處理后的出租車軌跡線構建約束Delaunay三角網(wǎng)，根據(jù)整體長邊約束準則(式(5))刪除長邊，提取道路面粗輪廓多邊形；然后對道路面多邊形二次構建Delaunay三角網(wǎng)，提取道路中心線。以北京市五環(huán)內軌跡數(shù)據(jù)為例，提取的道路中心線如圖8所示，路名數(shù)據(jù)從微博簽到軌跡數(shù)據(jù)中提取。

圖7 研究區(qū)域及軌跡線Fig.7 Study area and trajectory line

3.2.1 實驗結果定性定量評價 本文借鑒文獻[19]中的方法，將提取的道路幾何數(shù)據(jù)與OSM電子地圖[24]、OSM道路網(wǎng)矢量數(shù)據(jù)[24]疊加比較，進行定性評價。圖8中提取的道路中心線幾何數(shù)據(jù)基本與實地道路相符合，尤其對于軌跡數(shù)據(jù)密度較高的道路區(qū)域，提取的道路中心線幾何拓撲精度較高。

為了定量評價實驗結果，將本方法實驗結果與文獻[5]中柵格化方法實驗結果對比分析。采用文獻[25]中提出的緩沖區(qū)檢測方法評價道路中心線數(shù)據(jù)的幾何精度。以OSM道路矢量數(shù)據(jù)為參考，分別建立2 m、5 m、7 m為半徑寬度的緩沖區(qū)，計算落入緩沖區(qū)的道路中心線長度并統(tǒng)計百分比。利用ArcGIS的拓撲檢查工具找出拓撲正確道路數(shù)量與拓撲錯誤道路數(shù)量，統(tǒng)計百分比。如表1所示，本文方法所提取的道路中心線數(shù)據(jù)在幾何精度、拓撲正確性方面都比柵格化方法有較大提高，特別在2 m緩沖區(qū)的高精度結果有約30%的提升。

圖8 道路網(wǎng)數(shù)據(jù)與OSM電子地圖疊加比較Fig.8 Road centreline extraction and the comparison with OSM map

表1 實驗結果評價Table 1 The evaluation of experiment results

3.2.2 復雜環(huán)形道路實驗結果評價 本文方法通過設置長邊約束準則中的調節(jié)系數(shù)α參數(shù)值，幫助識別不同路網(wǎng)結構、不同軌跡密度分布的道路面域輪廓。尤其對于復雜環(huán)形道路的中心線提取，能較好地區(qū)別路面與空白區(qū)域，從而保證道路中心線的拓撲正確性。如圖9所示，本文方法能正確區(qū)分環(huán)形道路中的小空白區(qū)域(圖9b)、距離較近的雙干道等復雜案例；反之，如圖9c所示，柵格化方法將環(huán)形道路空白區(qū)域錯誤識別為道路，從而導致道路中心線的拓撲錯誤。當然該方法對于不同的軌跡數(shù)據(jù)需要實驗找出不同的調節(jié)參數(shù)，另外該方法也不能對道路邊界進行精確識別，這是下一步的研究重點。從時間性能效率方面看，Delaunay三角網(wǎng)模型的實現(xiàn)算法已較成熟、穩(wěn)定，其時間復雜度為(nlogn)[20]，完全適用于大數(shù)據(jù)處理；并且可以在較多的開源軟件(如QGIS等)以及主流的GIS軟件(如ArcGIS等)平臺中實現(xiàn)，快速投入地圖數(shù)據(jù)生產(chǎn)，所以本方法與其他道路中心線提取算法相比更簡便、快速且易于實現(xiàn)。

4 結論與展望

圖9 復雜環(huán)形道路提取結果對比Fig.9 Comparison of the results extracted from complex ring road

為了快速準確地從眾源軌跡數(shù)據(jù)中提取道路幾何數(shù)據(jù)，本文提出了一種基于約束Delaunay三角網(wǎng)的道路中心線提取方法。首先對預處理后的車輛軌跡線構建約束Delaunay三角網(wǎng)，根據(jù)整體長邊約束準則刪除長邊提取道路面粗粒度輪廓多邊形；然后對道路面多邊形二次構建Delaunay三角形，提取道路中心線。利用北京市一天時間的出租車軌跡數(shù)據(jù)進行實驗分析，用OSM道路網(wǎng)矢量數(shù)據(jù)作為參考數(shù)據(jù)，與柵格化方法實驗結果進行定性定量的對比評價。結果證明本文方法提取的道路中心線數(shù)據(jù)在幾何、拓撲精度方面都比柵格化方法高，并且本方法在處理復雜道路結構、較大密度差異的軌跡數(shù)據(jù)時比柵格化方法更顯優(yōu)勢。另外，本方法算法易于實現(xiàn)且適合大數(shù)據(jù)處理。

本研究還需要深入完善的內容主要包括：1)更精確地提取道路面域數(shù)據(jù)。本研究中只識別了道路面域的粗輪廓，其結果并不精確；同時對于密度差異較大的軌跡數(shù)據(jù)，本文方法還需要改進，特別對于城市內部小區(qū)級別的道路提取需要深入研究。2)道路數(shù)據(jù)不僅包括道路中心線數(shù)據(jù)，還包括道路面、車道、路名等數(shù)據(jù)，故在后續(xù)工作中，將設計不同算法并融合不同類型的VGI軌跡數(shù)據(jù)以提取更豐富的道路幾何數(shù)據(jù)與屬性數(shù)據(jù)。

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

[2] ANMED M,KARAGIORGOU S,PFOSER D,et al.A comparison and evaluation of map construction algorithms using vehicle tracking data[J].GeoInformatica,2015,19(3):601-632.

[3] EDELKAMP S,SCHRODL S.Route planning and map inference with global positioning traces[A].Computer Science in Perspective[C].Springer Berlin Heidelberg,2003.128-151.

[4] GUO T,IWAMURA K,KOGA M.Towards high accuracy road maps generation from massive GPS traces data[A].2007 IEEE International Geoscience and Remote Sensing Symposium[C].2007.

[5] ZHANG L,THIEMANN F,SESTER M.Integration of GPS traces with road map[A].Proceedings of the Second International Workshop on Computational Transportation Science[C].ACM,2010.17-22.

[6] 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].ACM,2009.3-12.

[7] KARAGIORGOU S,PFOSER D.On vehicle tracking data-based road network generation[A].Proceedings of the 20th International Conference on Advances in Geographic Information Systems[C].ACM,2012.89-98.

[8] KARAGIORGOU S,PFOSER D,SKOUTAS D.Segmentation-based road network construction[A].Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].ACM,2013.460-463.

[9] LI J,QIN Q,XIE C,et al.Integrated use of spatial and semantic relationships for extracting road networks from floating car data[J].International Journal of Applied Earth Observation and Geoinformation,2012,19:238-247.

[10] 唐爐亮,劉章,楊雪,等.符合認知規(guī)律的時空軌跡融合與路網(wǎng)生成方法[J].測繪學報,2015,44(11):1271-1276.

[11] CHEN C,CHENG Y.Roads digital map generation with multi-track GPS data[A].Education Technology and Training,2008[C].2008 International Workshop on Geoscience and Remote Sensing,2008,1:508-511.

[12] XIE X,BING-YUNG W K,AGHAJAN H,et al.Inferring directed road networks from GPS traces by track alignment[J].ISPRS International Journal of Geo-Information,2015,4(4):2446-2471.

[13] 蔣益娟,李響,李小杰,等.利用車輛軌跡數(shù)據(jù)提取道路網(wǎng)絡的幾何特征與精度分析[J].地球信息科學學報,2012,14(2):165-170.

[14] LIU X,BIAGIONI J,ERIKSSON J,et al.Mining large-scale,sparse GPS traces for map inference:Comparison of approaches[A].Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].ACM,2012.669-677.

[15] WU J,ZHU Y,KU T,et al.Detecting road intersections from coarse-gained GPS traces based on clustering[J].Journal of Computers,2013,8(11):2959-2965.

[16] WANG J,RUI X,SONG X,et al.A novel approach for generating routable road maps from vehicle GPS traces[J].International Journal of Geographical Information Science,2015,29(1):69-91.

[17] 艾廷華,郭仁忠.基于約束 Delaunay 結構的街道中軸線提取及網(wǎng)絡模型建立[J].測繪學報,2000,29(4):348-354.

[18] 李功權,蔡祥云.一種基于約束三角網(wǎng)的道路中心線的提取方法[J].長江大學學報(自然科學版:理工卷),2013(2):47-50.

[19] LI J,QIN Q,HAN J,et al.Mining trajectory data and geotagged data in social media for road map inference[J].Transactions in GIS,2015,19(1):1-18.

[20] ESTIVILL-CASTRO V,LEE I.Multi-level clustering and its visualization for exploratory spatial analysis[J].GeoInformatica,2002,6(2):123-152.

[21] 李光強,鄧敏,劉啟亮,等.一種適應局部密度變化的空間聚類方法[J].測繪學報,2009,38(3):255-263.

[22] 艾廷華,郭仁忠.支持地圖綜合的面狀目標約束Delaunay三角網(wǎng)剖分[J].武漢測繪科技大學學報,2000,25(1):35-41.

[23] YUAN J,ZHENG Y,ZHANG C,et al.T-drive:Driving directions based on taxi trajectories[A].Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].ACM,2010.99-108.

[24] http://www.openstreetmap.org.2015-10-31.

[25] GOODCHILD M F,HUNTER G J.A simple positional accuracy measure for linear features[J].International Journal of Geographical Information Science,1997,11(3):299-306.

Road Centerline Extraction from Crowdsourcing Trajectory Data

YANG Wei，AI Ting-hua

(SchoolofResourceandEnvironmentalSciences,WuhanUniversity,Wuhan430079,China)

Compared with traditional method,road centerline extraction from crowdsourcing trajectory data offers numerous advantages with respect to labor cost,real-time and data completeness.However,it is difficult to construct road network using big crowdsourcing trajectory data due to the trajectory data with sampling sparse and large data volume and high noise.For this issue,this study tries to explore the question of road centerline extraction by large volume of taxi GPS trajectory data,presenting a new method based on Delaunay triangulation model.The whole method includes three steps.The first one is to pre-process the vehicle trajectory data including the point anomaly removing and the conversion of trajectory point to track line.Secondly,construct Delaunay triangulation within the vehicle trajectory line to detect neighborhood relation.And then,the road coarse polygon is extracted by cutting long triangle edge and organizing the polygon topology.Considering the case that some of the trajectory segments are too long,a interpolation measure is used to add more points for the improved triangulation.Thirdly,construct Delaunay triangulation within the road polygon to extract the road centerline.The centerline is extracted by distinguishing three kinds of triangles and processing the road junction.The experiment is conducted using one day of taxi track in Beijing City.Compared with conventional methods(raster),experimental results demonstrate that the accuracy of road geometry and topology is improved above 10 percent through the use of the method in this paper.Moreover,the complex ring road is used as a case study to test the proposed method.Experimental results prove that the proposed method is more suitable for complex road structure and trajectory data with different density.As a result,the results achieved with the proposed method show that road centerline can be generated with low cost,high efficiency,good maneuverability,based on crowdsourcing trajectory data,and be very useful for mapping application.

crowdsourcing trajectory data；road extraction；road centerline；Delaunay triangulation

2015-12-17；

2016-02-15

國家自然科學基金資助項目(41531180)；國家高技術研究發(fā)展計劃(863計劃)資助項目(2015AA1239012)

楊偉(1987-)，男,博士研究生，研究方向為時空數(shù)據(jù)挖掘與可視化。*通訊作者E-mail：tinghua_ai@163.net

10.3969/j.issn.1672-0504.2016.03.001

U495;P208

A

1672-0504(2016)03-0001-07