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

楊 偉,艾 廷 華

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

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

楊 偉,艾 廷 華*

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

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

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

0 引言

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

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

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

1.1 道路中心線提取流程

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

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

1.2 軌跡預(yù)處理及加密

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

(1)

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

2 基本原理與方法

2.1 道路面域多邊形提取

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

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

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

(2)

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

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

(3)

(4)

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

Global_CutValue(pi)=Global_Mean(DT)+

(5)

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

2.2 道路中心線提取

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

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

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

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

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

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

AreaCutValue=MeanArea+α*StdDev

(6)

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

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

(7)

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

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

3 實(shí)驗(yàn)分析與結(jié)果評(píng)價(jià)

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

為了定量評(píng)價(jià)實(shí)驗(yàn)結(jié)果，將本方法實(shí)驗(yàn)結(jié)果與文獻(xiàn)[5]中柵格化方法實(shí)驗(yàn)結(jié)果對(duì)比分析。采用文獻(xiàn)[25]中提出的緩沖區(qū)檢測(cè)方法評(píng)價(jià)道路中心線數(shù)據(jù)的幾何精度。以O(shè)SM道路矢量數(shù)據(jù)為參考，分別建立2 m、5 m、7 m為半徑寬度的緩沖區(qū)，計(jì)算落入緩沖區(qū)的道路中心線長(zhǎng)度并統(tǒng)計(jì)百分比。利用ArcGIS的拓?fù)錂z查工具找出拓?fù)湔_道路數(shù)量與拓?fù)溴e(cuò)誤道路數(shù)量，統(tǒng)計(jì)百分比。如表1所示，本文方法所提取的道路中心線數(shù)據(jù)在幾何精度、拓?fù)湔_性方面都比柵格化方法有較大提高，特別在2 m緩沖區(qū)的高精度結(jié)果有約30%的提升。

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

表1 實(shí)驗(yàn)結(jié)果評(píng)價(jià)Table 1 The evaluation of experiment results

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

4 結(jié)論與展望

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

為了快速準(zhǔn)確地從眾源軌跡數(shù)據(jù)中提取道路幾何數(shù)據(jù)，本文提出了一種基于約束Delaunay三角網(wǎng)的道路中心線提取方法。首先對(duì)預(yù)處理后的車輛軌跡線構(gòu)建約束Delaunay三角網(wǎng)，根據(jù)整體長(zhǎng)邊約束準(zhǔn)則刪除長(zhǎng)邊提取道路面粗粒度輪廓多邊形；然后對(duì)道路面多邊形二次構(gòu)建Delaunay三角形，提取道路中心線。利用北京市一天時(shí)間的出租車軌跡數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析，用OSM道路網(wǎng)矢量數(shù)據(jù)作為參考數(shù)據(jù)，與柵格化方法實(shí)驗(yàn)結(jié)果進(jìn)行定性定量的對(duì)比評(píng)價(jià)。結(jié)果證明本文方法提取的道路中心線數(shù)據(jù)在幾何、拓?fù)渚确矫娑急葨鸥窕椒ǜ撸⑶冶痉椒ㄔ谔幚韽?fù)雜道路結(jié)構(gòu)、較大密度差異的軌跡數(shù)據(jù)時(shí)比柵格化方法更顯優(yōu)勢(shì)。另外，本方法算法易于實(shí)現(xiàn)且適合大數(shù)據(jù)處理。

本研究還需要深入完善的內(nèi)容主要包括：1)更精確地提取道路面域數(shù)據(jù)。本研究中只識(shí)別了道路面域的粗輪廓，其結(jié)果并不精確；同時(shí)對(duì)于密度差異較大的軌跡數(shù)據(jù)，本文方法還需要改進(jìn)，特別對(duì)于城市內(nèi)部小區(qū)級(jí)別的道路提取需要深入研究。2)道路數(shù)據(jù)不僅包括道路中心線數(shù)據(jù)，還包括道路面、車道、路名等數(shù)據(jù)，故在后續(xù)工作中，將設(shè)計(jì)不同算法并融合不同類型的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] 唐爐亮,劉章,楊雪,等.符合認(rèn)知規(guī)律的時(shí)空軌跡融合與路網(wǎng)生成方法[J].測(cè)繪學(xué)報(bào),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)絡(luò)的幾何特征與精度分析[J].地球信息科學(xué)學(xué)報(bào),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 結(jié)構(gòu)的街道中軸線提取及網(wǎng)絡(luò)模型建立[J].測(cè)繪學(xué)報(bào),2000,29(4):348-354.

[18] 李功權(quán),蔡祥云.一種基于約束三角網(wǎng)的道路中心線的提取方法[J].長(zhǎng)江大學(xué)學(xué)報(bào)(自然科學(xué)版:理工卷),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] 李光強(qiáng),鄧敏,劉啟亮,等.一種適應(yīng)局部密度變化的空間聚類方法[J].測(cè)繪學(xué)報(bào),2009,38(3):255-263.

[22] 艾廷華,郭仁忠.支持地圖綜合的面狀目標(biāo)約束Delaunay三角網(wǎng)剖分[J].武漢測(cè)繪科技大學(xué)學(xué)報(bào),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

國(guó)家自然科學(xué)基金資助項(xiàng)目(41531180)；國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃)資助項(xiàng)目(2015AA1239012)

楊偉(1987-)，男,博士研究生，研究方向?yàn)闀r(shí)空數(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