楊 偉，艾廷華

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

運(yùn)用約束Delaunay三角網(wǎng)從眾源軌跡線提取道路邊界

楊 偉，艾廷華

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

運(yùn)用眾源車輛軌跡數(shù)據(jù)提取道路信息需要解決軌跡點(diǎn)采樣稀疏、高噪音、密度差異大等問(wèn)題。為此，本文提出一種運(yùn)用約束Delaunay三角網(wǎng)從車輛軌跡線集中提取道路邊界的方法。首先，通過(guò)三角形邊長(zhǎng)度和Voronoi面積等幾何特征表達(dá)軌跡點(diǎn)分布的聚集性差異，并將這兩種不同幾何維數(shù)的控制條件集成建立道路邊界識(shí)別模型，運(yùn)用“種子點(diǎn)”區(qū)域擴(kuò)展方法實(shí)現(xiàn)道路邊界的精確提取。最后，運(yùn)用北京市出租車GPS軌跡進(jìn)行試驗(yàn)，結(jié)果表明該方法適于車輛分布頻率懸殊、時(shí)間跨度不同、道路網(wǎng)結(jié)構(gòu)復(fù)雜的軌跡線數(shù)據(jù)處理。

眾源軌跡；道路更新；約束Delaunay三角網(wǎng)；空間聚類

由于城鄉(xiāng)道路建設(shè)飛速發(fā)展，道路信息快速獲取與更新成為亟待解決的問(wèn)題。傳統(tǒng)道路數(shù)據(jù)采集方式包括野外測(cè)量、高分遙感影像等，其中高分影像以其高分辨率特征成為主要技術(shù)手段。然而，高分影像價(jià)格昂貴，難以開(kāi)源獲取，影像中的噪聲干擾使得提取算法復(fù)雜。盡管高分影像提高了時(shí)間分辨率，但仍不能實(shí)時(shí)獲取，難以滿足人們對(duì)道路數(shù)據(jù)低成本、高實(shí)時(shí)性的要求[1]。隨著移動(dòng)傳感技術(shù)的發(fā)展和眾源地理信息的出現(xiàn)，產(chǎn)生了海量的時(shí)空軌跡大數(shù)據(jù)。其中，車輛軌跡蘊(yùn)含了豐富的道路信息，直接反映了道路網(wǎng)絡(luò)的幾何特征和運(yùn)動(dòng)狀態(tài)[2]，其實(shí)時(shí)、低廉、眾源特性相比遙感影像等傳統(tǒng)數(shù)據(jù)源更具優(yōu)勢(shì)。如何從海量、高噪音的軌跡數(shù)據(jù)中快速提取道路信息，成為交通地理信息領(lǐng)域感興趣的問(wèn)題。

目前，學(xué)者們圍繞眾源軌跡提取道路數(shù)據(jù)集中在道路中心線提取[1-3]。依據(jù)幾何模型和數(shù)學(xué)統(tǒng)計(jì)方法的差異，可分為4類：一是軌跡聚類方法，包括軌跡點(diǎn)、軌跡線聚類，如文獻(xiàn)[4—5]運(yùn)用K-Means聚類算法并結(jié)合高斯模型從車輛軌跡中提取道路中心線；文獻(xiàn)[6]通過(guò)路口轉(zhuǎn)向判斷模型對(duì)軌跡分類，然后聚類軌跡提取路網(wǎng)；文獻(xiàn)[7]根據(jù)軌跡線的空間鄰近與方向關(guān)系聚類，提取路網(wǎng)數(shù)據(jù)。聚類方法適合高精度、低噪音軌跡數(shù)據(jù)。二是軌跡增量提取方法，如文獻(xiàn)[8]基于力學(xué)思想，根據(jù)軌跡運(yùn)動(dòng)方向增量融合提取道路網(wǎng)；文獻(xiàn)[9]基于軌跡點(diǎn)與候選路網(wǎng)之間的空間、語(yǔ)義關(guān)系來(lái)實(shí)現(xiàn)路網(wǎng)增量化生成；文獻(xiàn)[10]提出了符合人類空間認(rèn)知規(guī)律的軌跡線增量融合生成路網(wǎng)方法。三是基于圖論的方法，文獻(xiàn)[11—12]分別從GPS軌跡中提取道路交叉點(diǎn)、道路邊，并基于圖論的方法構(gòu)建道路地圖。四是柵格化方法，如文獻(xiàn)[13—14]將軌跡數(shù)據(jù)柵格化，利用圖像形態(tài)學(xué)方法提取道路面與骨架線；文獻(xiàn)[15—16]將柵格化方法與聚類、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)等方法相結(jié)合提取道路數(shù)據(jù)。以上模型方法適于道路中心線提取，難以識(shí)別道路邊界。當(dāng)前，道路邊界提取仍以高分遙感影像[17]、點(diǎn)云數(shù)據(jù)[18]為主，但高分影像與眾源軌跡相比成本高、實(shí)時(shí)性差，且提取算法復(fù)雜、專業(yè)要求較高，難以滿足生產(chǎn)需求。從眾源軌跡線集中提取道路邊界的研究相對(duì)較少，其主要有兩類方法：一是將軌跡數(shù)據(jù)柵格化[13-14]，利用矢量化算法、自動(dòng)矢量化工具如ArcScan提取道路面。二是圖論方法，如文獻(xiàn)[19]運(yùn)用約束Delaunay三角網(wǎng)提取道路面域粗輪廓。以上方法都受軌跡密度差異影響大、難以精確提取道路邊界，尤其對(duì)軌跡密度差異顯著、道路結(jié)構(gòu)復(fù)雜、不同時(shí)間跨度等特殊情形的道路邊界提取適應(yīng)性不強(qiáng)。

已有研究多運(yùn)用高精度(采樣間隔1～5 s)軌跡數(shù)據(jù)提取道路中心線，對(duì)于提取道路邊界研究較少。其原因在于：①軌跡采樣稀疏與高噪音問(wèn)題對(duì)道路邊界識(shí)別增加難度；②軌跡密度懸殊問(wèn)題，導(dǎo)致軌跡高密度區(qū)域道路邊界被拓寬，軌跡低密度區(qū)域道路難以提取。如何基于軌跡點(diǎn)(線)幾何特征差異建立高效的道路邊界識(shí)別模型成為該問(wèn)題研究的關(guān)鍵。本文引入約束Delaunay三角網(wǎng)及其對(duì)偶Voronoi圖表征軌跡密度變化差異，針對(duì)不同路面車輛分布頻率懸殊、復(fù)雜道路網(wǎng)結(jié)構(gòu)、多時(shí)間跨度等困難情形下的軌跡線數(shù)據(jù)處理建立針對(duì)性方法。

1 眾源軌跡線幾何特征分析

道路邊界作為道路面內(nèi)外的分界線，其兩邊的軌跡點(diǎn)密度差異顯著，這種密度差異是識(shí)別道路邊界的重要特征。要分析軌跡密度差異、識(shí)別道路邊界需要解決以下3個(gè)難點(diǎn)問(wèn)題。①高噪音特征。由于GPS信號(hào)漂移、采樣間隔稀疏、道路彎曲復(fù)雜度[6]等導(dǎo)致軌跡數(shù)據(jù)高噪音、缺失等問(wèn)題[19]，使得無(wú)法直接從原始軌跡中提取道路數(shù)據(jù)。②不同道路結(jié)構(gòu)下的密度差異。在城市主干道、交通樞紐區(qū)域軌跡點(diǎn)密集，而支干路軌跡點(diǎn)稀疏,這種密度差異導(dǎo)致提取的主干道邊界被拓寬，支路無(wú)法完整提取。特別對(duì)于復(fù)雜道路結(jié)構(gòu)，如環(huán)形道路交叉口、平行道路結(jié)構(gòu)，道路間間隔越小，道路邊界越模糊，道路與非道路區(qū)域難以區(qū)分，有效處理復(fù)雜道路結(jié)構(gòu)下的軌跡密度差異性問(wèn)題是本文研究的目標(biāo)之一。③不同時(shí)間尺度下的密度差異。軌跡作為時(shí)間序列數(shù)據(jù)，不同時(shí)間長(zhǎng)度下的數(shù)據(jù)量具有質(zhì)的變化。時(shí)間尺度過(guò)小，軌跡數(shù)據(jù)量小，則提取的道路面域小于真實(shí)道路面；時(shí)間尺度過(guò)大，軌跡數(shù)據(jù)量大，提取的道路面大于真實(shí)道路面。顧及行車頻率小的低等級(jí)道路，需要選取時(shí)間跨度長(zhǎng)的軌跡，然而對(duì)于高等級(jí)道路會(huì)造成軌跡點(diǎn)過(guò)于密集以至于鄰近道路混為一團(tuán)，難以區(qū)分其間的邊界，選取多長(zhǎng)時(shí)間段的軌跡線作為道路提取的數(shù)據(jù)對(duì)象是一個(gè)難點(diǎn)問(wèn)題。

針對(duì)眾源軌跡線提取道路信息的難點(diǎn)問(wèn)題，本文重點(diǎn)關(guān)注軌跡密度變化差異，引入約束Delaunay三角網(wǎng)及其對(duì)偶Voronoi圖模型，計(jì)算三角形邊長(zhǎng)度與Voronoi面域大小等幾何特征表達(dá)軌跡點(diǎn)密度變化差異，建立眾源軌跡點(diǎn)(線)邊界識(shí)別模型和道路邊界提取方法。

2 Delaunay三角網(wǎng)支持下的軌跡數(shù)據(jù)提取道路邊界

從軌跡線中提取道路邊界的核心是識(shí)別軌跡點(diǎn)集分布的邊界[20]，本質(zhì)上是一個(gè)空間鄰近分析問(wèn)題。Delaunay三角網(wǎng)是空間鄰近分析的有力工具，廣泛用于空間數(shù)據(jù)聚類[21]、空間鄰近關(guān)系探測(cè)[22-23]。故本文運(yùn)用約束Delaunay三角網(wǎng)(constrained Delaunay triangulation，CDT)計(jì)算軌跡密度變化率、邊長(zhǎng)距離，建立道路邊界識(shí)別模型，提取道路邊界。

2.1 道路邊界識(shí)別指標(biāo)計(jì)算

(1) 密度變化率指數(shù)。道路邊界作為道路面內(nèi)外的分界線，兩邊的軌跡點(diǎn)密度差異顯著，密度變化率成為道路邊界識(shí)別的重要指標(biāo)。文獻(xiàn)[23]認(rèn)為每個(gè)點(diǎn)目標(biāo)的存在都要獲取其生存空間，相鄰點(diǎn)目標(biāo)對(duì)分布空間的競(jìng)爭(zhēng)結(jié)果相當(dāng)于對(duì)空間做等分式劃分(不考慮點(diǎn)性質(zhì)差異)，并用點(diǎn)的Voronoi圖面積的倒數(shù)表示該點(diǎn)的密度。在由軌跡線生成的Voronoi圖中(圖1(a))，道路內(nèi)部Voronoi圖面積小，非道路區(qū)域Voronoi圖面積大，道路邊界兩側(cè)的軌跡點(diǎn)密度差異大。由于Delaunay三角網(wǎng)與Voronoi圖互為對(duì)偶，故將軌跡密度變化差異融入Delaunay三角形邊中。三角形邊將空間分為左右區(qū)域，如果三角形邊的左右兩側(cè)軌跡點(diǎn)密度差異大，則為道路邊界區(qū)域。因此，三角形邊相對(duì)左右兩點(diǎn)的密度之比即是該邊的密度變化率，該比值稱為密度變化率指數(shù)(density change rate index，DCRI)，計(jì)算公式為

(1)

式中，D(pleft)、D(pright)分別表示三角形邊Ei相對(duì)的左、右兩點(diǎn)的密度，DCRI的值域?yàn)?0,1]。根據(jù)軌跡點(diǎn)的密度(圖1(a))和DCRI值分布特征(圖1(c))，在道路內(nèi)部和非道路區(qū)域軌跡密度差異小，三角形邊DCRI值大；道路邊界區(qū)域軌跡密度差異大，DCRI值小；DCRI值越小，軌跡密度差異越大，是道路邊界的可能性越大。設(shè)定DCRI閾值(用DCRI_Value表示)，將三角形邊分為兩類(圖1(c))，如果三角形邊DCRI≤DCRI_Value，則該邊位于道路邊界區(qū)域，可作為道路邊界，簡(jiǎn)稱突變邊，用De表示；反之稱為普通邊，用Pe表示。

(2) 邊長(zhǎng)距離。Delaunay三角網(wǎng)中邊的長(zhǎng)度表達(dá)了點(diǎn)目標(biāo)間在空間分布上的遠(yuǎn)近關(guān)系，邊越長(zhǎng)軌跡稀疏，密度低；反之軌跡密集，密度高(圖1(b))。由于車輛軌跡沿道路網(wǎng)聚集分布，在由軌跡線構(gòu)建的Delaunay三角網(wǎng)中(圖1(b))，道路內(nèi)部區(qū)域三角形邊長(zhǎng)度小，非道路區(qū)域邊長(zhǎng)度大。設(shè)定邊長(zhǎng)閾值，將三角形邊分為兩級(jí)(圖1(b))，即可區(qū)分道路與非道路區(qū)域，識(shí)別道路邊界。根據(jù)Delaunay三角網(wǎng)中邊長(zhǎng)的統(tǒng)計(jì)特征[22]，計(jì)算公式如下

圖1 道路邊界識(shí)別指標(biāo)及特征Fig.1 The characteristics of identification index of road boundary

Len_Value=Len_Mean(DT)+α× Len_Variation(DT)

(2)

式中，Len_Mean(DT)表示三角網(wǎng)DT平均邊長(zhǎng)；Len_Variation(DT)表示三角網(wǎng)邊長(zhǎng)變異；α表示調(diào)節(jié)系數(shù)。α值越大(默認(rèn)為1)，整體約束越寬松，反之則越嚴(yán)格。根據(jù)邊長(zhǎng)度分布特征(圖1(b))，如果邊長(zhǎng)度Len≥Len_Value，可作為道路邊界(圖1(e))，簡(jiǎn)稱長(zhǎng)邊，用Le表示；反之，稱為短邊，用Se表示。

上述兩個(gè)指標(biāo)從不同側(cè)面反映軌跡數(shù)據(jù)的密度變化差異和道路邊界特征，但由于道路網(wǎng)的復(fù)雜性與軌跡數(shù)據(jù)分布差異性，使得單一指標(biāo)具有不同的控制領(lǐng)域與適應(yīng)條件。如圖1(d)所示，DCRI指標(biāo)確定的突變邊界在空間分布上具有混合性、不均勻性、不連續(xù)性，使得突變邊識(shí)別的道路邊界不完整、道路邊界拓?fù)鋽嚅_(kāi)。尤其對(duì)于軌跡點(diǎn)稀疏的支干道路邊界識(shí)別不完整(圖1(d)中A)。DCRI指標(biāo)適合于軌跡數(shù)據(jù)密集、密度變化差較大的情形，如主干道(圖1(d)中B)、道路交叉口(環(huán)形道路、轉(zhuǎn)盤)等復(fù)雜道路結(jié)構(gòu)。邊長(zhǎng)指標(biāo)適于軌跡稀疏的支干路(圖1(e)中A)、道路結(jié)構(gòu)簡(jiǎn)單下的軌跡數(shù)據(jù)，這能解決DCRI指標(biāo)提取道路邊界不完整的問(wèn)題。但對(duì)于軌跡密集、道路結(jié)構(gòu)復(fù)雜的情形，用單一邊長(zhǎng)指標(biāo)難以顧及全局與局部的密度差異，提取的邊界會(huì)出現(xiàn)道路面被拓寬(圖1(e)中D)、環(huán)形閘道與空白區(qū)域無(wú)法區(qū)分的問(wèn)題，而DCRI指標(biāo)可解決該問(wèn)題。故本文將兩個(gè)識(shí)別指標(biāo)融合集成構(gòu)建道路邊界識(shí)別模型，用于道路邊界提取。

2.2 基于Delaunay三角網(wǎng)的道路邊界提取

2.2.1 軌跡數(shù)據(jù)預(yù)處理

運(yùn)用文獻(xiàn)[18]中方法對(duì)原始軌跡進(jìn)行常規(guī)(包括時(shí)間錯(cuò)誤、越界等)清洗并生成軌跡線。由于軌跡稀疏采樣，直接對(duì)原始軌跡線構(gòu)建約束Delaunay三角網(wǎng)，則破壞三角網(wǎng)鄰近特性。故本文根據(jù)軌跡轉(zhuǎn)向角與軌跡段長(zhǎng)度自適應(yīng)加密軌跡線解決該問(wèn)題。按照文獻(xiàn)[24]中方法計(jì)算每個(gè)軌跡點(diǎn)的轉(zhuǎn)角θ和該軌跡點(diǎn)相鄰軌跡段的長(zhǎng)度L。通過(guò)試驗(yàn)表明，如果θ為(30°,90°)且L>300 m，則該點(diǎn)相鄰軌跡段加密多、加密步長(zhǎng)較小，反之加密少、加密步長(zhǎng)較大。

2.2.2 道路邊界提取方法

根據(jù)2.1中所述，本文集成邊界識(shí)別指標(biāo)構(gòu)建道路邊界識(shí)別模型，如圖2(a)所示，對(duì)于每一條三角形邊，如果是長(zhǎng)邊(Le)或者突變邊(De)，該邊為道路邊界，稱為“障礙邊”。根據(jù)“障礙邊”的數(shù)目將Delaunay三角形分為4類：只有1條障礙邊的為Ⅰ類三角形；有兩條障礙邊的為Ⅱ類三角形；有3條障礙邊的為Ⅲ類三角形；沒(méi)有障礙邊的為Ⅳ類三角形(圖2(b))。道路邊界提取算法思想為：在保持拓?fù)溥B通性的前提下，將任意Ⅳ類三角形作為“種子點(diǎn)”，運(yùn)用“種子點(diǎn)”區(qū)域增長(zhǎng)算法尋找多邊形范圍。由與種子點(diǎn)相連的任意一個(gè)三角形出發(fā)，向3方向擴(kuò)展，對(duì)于一個(gè)三角形來(lái)說(shuō)，搜索路徑為一邊進(jìn)入、兩邊輸出，因此采用二叉樹廣度優(yōu)先遍歷的方法遍歷三角網(wǎng)，一旦輸出邊為障礙邊,則停止該障礙邊方向上的搜索。Ⅱ類三角形可看作葉子節(jié)點(diǎn)，只有一邊進(jìn)入，沒(méi)有輸出；Ⅰ類三角形是擁有一個(gè)孩子節(jié)點(diǎn)的非葉子節(jié)點(diǎn)；Ⅳ類三角形是擁有兩個(gè)孩子節(jié)點(diǎn)的非葉子節(jié)點(diǎn)；Ⅲ類三角形為障礙區(qū)，不搜索。

圖2 道路邊界提取算法及決策模型Fig.2 The algorithm of the road boundary extraction and decision model

根據(jù)邊與三角形的鄰接關(guān)系持續(xù)擴(kuò)展直到擴(kuò)展邊均到達(dá)障礙邊,所有三角形范圍構(gòu)成了封閉區(qū)域,完成道路多邊形生成(圖2(c))。由于真實(shí)環(huán)境中路網(wǎng)結(jié)構(gòu)復(fù)雜、軌跡密度差異顯著，在算法實(shí)際應(yīng)用時(shí)還需要根據(jù)三角形類型、上下文關(guān)系來(lái)決策確定道路邊界(障礙邊)。

(1) 孤立障礙邊與障礙區(qū)。由于道路內(nèi)部、不同等級(jí)道路連接處的軌跡密度差異，在搜索擴(kuò)展中出現(xiàn)零散分布的孤立障礙邊、障礙區(qū)(圖3(a)中C)。障礙區(qū)由少量Ⅱ類三角形、Ⅲ類三角形組成，形成了道路多邊形區(qū)域內(nèi)的障礙區(qū)“空洞”。這些孤立障礙邊、障礙區(qū)的鄰接區(qū)域都已擴(kuò)展搜索，處于活躍狀態(tài)。對(duì)于該情形，把障礙邊當(dāng)作非障礙邊繼續(xù)擴(kuò)展。對(duì)于障礙區(qū)還需要設(shè)定面積閾值與環(huán)形道路中的非道路區(qū)域區(qū)分開(kāi)。

圖3 復(fù)雜情形下的道路邊界提取決策Fig.3 The decision model of road boundary extraction

(2) 擴(kuò)展“瓶頸”與邊界平滑。在搜索過(guò)程中出現(xiàn)單一障礙邊(圖3(b)中A)、單一Ⅲ類三角形(圖3(b)中B)阻斷擴(kuò)展路徑，無(wú)法完成搜索。對(duì)于單一障礙邊，如果障礙邊左右鄰接的三角形都處于擴(kuò)展活躍狀態(tài)，需跨越該障礙邊繼續(xù)擴(kuò)展。對(duì)于Ⅲ類三角形，如果該Ⅲ類三角形的3個(gè)鄰接三角形中有兩個(gè)以上三角形處于擴(kuò)展活躍狀態(tài)，將與活躍狀態(tài)三角形鄰接的邊作為非障礙邊繼續(xù)擴(kuò)展。另外，城市支路上出現(xiàn)障礙邊與非障礙邊間隔分布(圖3(c))情形。針對(duì)該情形，判斷每個(gè)Ⅱ類三角形障礙邊的鄰接三角形類型。如果是Ⅱ類、Ⅰ類、Ⅳ類，則跨越障礙邊繼續(xù)擴(kuò)展；如果是Ⅲ類三角形，則以障礙邊為邊界終止擴(kuò)展。擴(kuò)展完成后的道路邊界凹凸不平(圖3(b))，需對(duì)道路邊界平滑化簡(jiǎn)，最后完成道路多邊形提取。

2.3 指標(biāo)參數(shù)取值及探討

在道路邊界提取過(guò)程中，選擇合適的Len_Value(調(diào)節(jié)系數(shù)α值)與DCRI_Value閾值顯得尤為關(guān)鍵。根據(jù)2.1節(jié)中對(duì)參數(shù)值分布規(guī)律的分析，參數(shù)取值即是找出那些數(shù)量少的長(zhǎng)邊Le和突變邊De。本文根據(jù)參數(shù)值分布規(guī)律，利用ArcGIS自然間斷點(diǎn)分級(jí)法進(jìn)行取值試驗(yàn)。分析不同參數(shù)取值的試驗(yàn)結(jié)果精度，發(fā)現(xiàn)DCRI最佳取值范圍為(0.2,0.6)，邊長(zhǎng)調(diào)節(jié)系數(shù)α最佳取值范圍為(0.5,2)。在各自指標(biāo)的最佳取值范圍內(nèi)，取不同的組合值進(jìn)行試驗(yàn)，分析組合取值對(duì)道路提取結(jié)果精度的影響，即參數(shù)取值的敏感度分析(圖(4))，其敏感度變化符合正態(tài)分布曲線，如圖4(c)所示。在圖4(c)中，當(dāng)兩個(gè)參數(shù)組合取值時(shí)，其最佳取值區(qū)間有微小的變化，DCRI變?yōu)閇0.3,0.5]，α為[0.5,2]，在該范圍內(nèi)的結(jié)果精度達(dá)可到60%左右。當(dāng)指標(biāo)取值位于(DCRI=0.4,α=1)附近時(shí)，結(jié)果精度到達(dá)80%以上。在最佳取值范圍內(nèi)，通過(guò)調(diào)節(jié)、組合參數(shù)取值使其適應(yīng)不同情形下的道路邊界提取。

圖4 參數(shù)取值范圍及敏感度分析Fig.4 Range of parameter values and sensitivity analysis

3 試驗(yàn)與分析

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

車輛軌跡數(shù)據(jù)為北京市2012年11月3日(星期日)一天的出租車軌跡。出租車軌跡數(shù)據(jù)包括車輛ID、GPS時(shí)間、GPS經(jīng)緯度等信息。軌跡點(diǎn)采樣間隔為10～120 s不等，共有軌跡點(diǎn)32 882 436個(gè)，生成軌跡線為144 205條，預(yù)處理后為45 768條，本試驗(yàn)選取北京市望京社區(qū)一定范圍內(nèi)作為試驗(yàn)區(qū)域(圖5)。本試驗(yàn)在P4/8GB/2GB/Win7環(huán)境下，基于ArcGIS平臺(tái)、C#編程語(yǔ)言進(jìn)行道路面、線數(shù)據(jù)提取的算法實(shí)現(xiàn)。

3.2 試驗(yàn)結(jié)果分析

對(duì)預(yù)處理加密的軌跡線構(gòu)建約束Delaunay三角網(wǎng)，計(jì)算DCRI與邊長(zhǎng)閾值，根據(jù)道路邊界識(shí)別模型，運(yùn)用“種子”點(diǎn)區(qū)域增長(zhǎng)算法提取道路邊界，生成道路面域數(shù)據(jù)(圖5)。道路面域二次構(gòu)建Delaunay三角網(wǎng)，提取道路中心線(圖5)。將提取的道路數(shù)據(jù)與影像地圖、OSM電子地圖疊加進(jìn)行定性評(píng)價(jià)。如圖5所示，道路面、道路線數(shù)據(jù)的整體結(jié)果基本覆蓋試驗(yàn)區(qū)的道路，并且準(zhǔn)確度較高。如圖5(b)、(e)，本方法對(duì)于復(fù)雜道路交叉口(樣區(qū)A)區(qū)域能較好區(qū)分環(huán)形閘道中的空白區(qū)域。如圖5(c)、(f)，本方法能夠處理不同道路等級(jí)(樣區(qū)B)下的軌跡密度差異，區(qū)分空間上鄰近道路的道路邊界。但在城市內(nèi)部的部分低等級(jí)道路面無(wú)法提取或提取精度低(圖5(c))，原因在于軌跡線太少。

圖5 道路數(shù)據(jù)結(jié)果及定性評(píng)價(jià)Fig.5 The results of experiment and qualitative evaluation of road data

以北京市標(biāo)準(zhǔn)道路矢量數(shù)據(jù)為參考，將本文結(jié)果與軌跡數(shù)據(jù)柵格化后利用ArcGIS矢量化的結(jié)果對(duì)比分析。采用多邊形疊置方法評(píng)價(jià)道路面提取的有效性，并借鑒文獻(xiàn)[3]中方法計(jì)算兩種常用評(píng)價(jià)指標(biāo)，即準(zhǔn)確率(precision)和召回率(recall)來(lái)評(píng)價(jià)疊置結(jié)果。準(zhǔn)確率反映試驗(yàn)結(jié)果的準(zhǔn)確度，召回率反映試驗(yàn)結(jié)果的完整度。對(duì)于道路線數(shù)據(jù)，采用文獻(xiàn)[25]中提出的緩沖區(qū)檢測(cè)方法與文獻(xiàn)[4]中方法得到的試驗(yàn)果對(duì)比評(píng)價(jià)，即分別建立2 m、5 m、8 m半徑的緩沖區(qū)進(jìn)行道路長(zhǎng)度的準(zhǔn)確率、召回率統(tǒng)計(jì)比較。結(jié)果統(tǒng)計(jì)評(píng)價(jià)如表1。

表1中P表示準(zhǔn)確率，R表示召回率。從表中可看出，本文方法提取的面域數(shù)據(jù)在準(zhǔn)確率、完整度上比柵格化方法提高10%以上。其主要原因在于柵格化方法對(duì)軌跡密度差異適應(yīng)差，低密度區(qū)域道路無(wú)法提取(圖6(a)中A、B處)；高密度區(qū)域的結(jié)果大于真實(shí)道路面、鄰近道路邊界區(qū)分度不高(圖6(a)中C、D處)。由于GPS定位誤差，不論哪種方法的提取結(jié)果都存在誤差，難以與真實(shí)邊界完全重合(圖6(a)、(b))。基于道路面生成的道路線數(shù)據(jù)在2 m緩沖區(qū)的精確度比柵格化方法有約40%的提高，完整度有約35%的提高。在拓?fù)湔_性方面，柵格化方法出現(xiàn)較多孤立的道路面、線拓?fù)鋽嚅_(kāi)、道路邊界z字形問(wèn)題(圖6(a))，而本文的“種子點(diǎn)”擴(kuò)展方法解決了該問(wèn)題。

表1 試驗(yàn)結(jié)果評(píng)價(jià)

圖6 兩種方法試驗(yàn)結(jié)果對(duì)比評(píng)價(jià)Fig.6 Comparative evaluation of experimental results of two methods

本文針對(duì)不同等級(jí)道路(不同行車頻率)、復(fù)雜道路交叉口、不同時(shí)間跨度等3種特殊情形下的軌跡數(shù)據(jù)進(jìn)行試驗(yàn)分析：

(1)不同道路等級(jí)。城市區(qū)域不同等級(jí)道路具有不同交通流量、不同行車頻率，導(dǎo)致軌跡密度懸殊。如圖7(a)所示，本文方法相比柵格化方法對(duì)于空間上鄰近的雙干道(圖7(a)中A)、低等級(jí)道路(圖7(a)中C)識(shí)別更完整。柵格化方法對(duì)密度低值區(qū)域無(wú)法提取或提取不完整(圖7(a)中C)，導(dǎo)致邊界不平滑或拓?fù)鋽嚅_(kāi)，對(duì)高密度區(qū)域如雙干道邊界、環(huán)形匝道區(qū)域(圖7(a)中A、B)識(shí)別不如本文方法。

(2) 復(fù)雜道路結(jié)構(gòu)。道路交叉口區(qū)域軌跡密集、數(shù)據(jù)量大，環(huán)形匝道、主干道等不同等級(jí)道路在空間上鄰近，導(dǎo)致柵格化方法難以完整提取環(huán)形匝道內(nèi)空白區(qū)域邊界(圖7(b)中A、B處)。本文方法在邊界提取中顧及了軌跡密度差異性，對(duì)于環(huán)形閘道與空白區(qū)域的區(qū)分較好(圖7(b)中邊界)、邊界提取更完整。

(3) 不同時(shí)間長(zhǎng)度。分別選取1小時(shí)、1天、1周不同時(shí)間長(zhǎng)度的軌跡線進(jìn)行試驗(yàn)分析(圖7(c))。當(dāng)處理1周軌跡數(shù)據(jù)量時(shí)(圖7(c)中D)，柵格化方法已經(jīng)無(wú)法區(qū)分出環(huán)形道路中的空白區(qū)域，將空間上鄰近的多條道路識(shí)別為一條道路。本方法對(duì)于1周數(shù)據(jù)量不進(jìn)行軌跡線加密、選取約束性嚴(yán)格的參數(shù)值(DCRI=0.58，α=0.4)，提取的邊界精度可達(dá)到73.1%，道路中的環(huán)形空白區(qū)也能較好識(shí)別(圖7(c)中D)。對(duì)于一條道路，軌跡量太少或太大(時(shí)間跨度過(guò)長(zhǎng))，即使通過(guò)調(diào)節(jié)參數(shù)也難以達(dá)到理想結(jié)果。

綜上，本方法相比柵格化方法更適于從不同行車頻率、不同時(shí)間跨度、復(fù)雜道路結(jié)構(gòu)下的軌跡線集中提取道路邊界。

圖7 特殊情形下的道路邊界提取結(jié)果對(duì)比分析Fig.7 Comparison and analysis of road boundary extraction results under special circumstances

4 結(jié) 論

本文針對(duì)眾源軌跡線集提取道路邊界問(wèn)題，引入約束Delaunay三角網(wǎng)及其對(duì)偶Voronoi圖幾何模型，通過(guò)DCRI和邊長(zhǎng)距離表征軌跡密度變化差異，將兩種不同幾何維數(shù)的控制條件集成構(gòu)建決策模型，運(yùn)用“種子點(diǎn)”區(qū)域擴(kuò)展方法實(shí)現(xiàn)道路邊界的精確提取。通過(guò)北京市出租車GPS軌跡數(shù)據(jù)試驗(yàn)分析，證明了該方法的有效性。本研究貢獻(xiàn)包括：運(yùn)用Delaunay三角網(wǎng)及Voronoi圖幾何模型建立了基于軌跡點(diǎn)(線)幾何特征差異的道路邊界識(shí)別模型，運(yùn)用決策模型、“種子點(diǎn)”區(qū)域擴(kuò)展算法實(shí)現(xiàn)道路邊界提取。該方法更適于軌跡密度差異懸殊情形下的道路邊界提取，解決了從眾源軌跡中提取道路邊界問(wèn)題。

同時(shí)，仍還有諸多內(nèi)容需深入完善：①本文僅提取了道路幾何數(shù)據(jù)，還需要提取道路屬性數(shù)據(jù)如路名、車道、交通規(guī)則等，如何將多源異構(gòu)的時(shí)空軌跡數(shù)據(jù)融合提取道路基礎(chǔ)設(shè)施，感知城市交通動(dòng)態(tài)將是下一步的研究重點(diǎn)。②本文方法對(duì)于復(fù)雜道路交叉口、立交橋等具有立體三維層次的道路面、線識(shí)別提取還需要作進(jìn)一步研究。

[1] AHMED 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.

[2] 楊偉, 艾廷華. 基于車輛軌跡大數(shù)據(jù)的道路網(wǎng)更新方法研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(12): 2681-2693. YANG Wei, AI Tinghua. A Method for Road Network Updating Based on Vehicle Trajectory Big Data[J]. Journal of Computer Research and Development, 2016, 53(12): 2681-2693.

[3] WANG Jing, RUI Xiaoping, SONG Xianfeng, 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.

[4] ZHANG Lijuan,THIEMANN F,SESTER M. Integration of GPS Traces with Road Map[C]∥Proceedings of the Third International Workshop on Computational Transportation Science. New York: ACM, 2010: 17-22.

[5] GUO Tao, IWAMURA K, KOGA M. Towards High Accuracy Road Maps Generation from Massive GPS Traces Data[C]∥Proceedings of the 2007 IEEE International Geoscience and Remote Sensing Symposium. Barcelona: IEEE, 2007: 667-670.

[6] LIU Xuemei, BIAGIONI J, ERIKSSON J, et al. Mining Large-scale, Sparse GPS Traces for Map Inference: Comparison of Approaches[C]∥Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 669-677.

[7] CAO Lili, KRUMM J. From GPS Traces to a Routable Road Map[C]∥Proceedings of the 17th ACM SIGSP-ATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2009: 3-12.

[8] LI Jun, QIN Qiming, XIE Chao, 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.

[9] 唐爐亮, 劉章, 楊雪, 等. 符合認(rèn)知規(guī)律的時(shí)空軌跡融合與路網(wǎng)生成方法[J]. 測(cè)繪學(xué)報(bào), 2015, 44(11): 1271-1276. DOI: 10.11947/j.AGCS.2015.20140591. TANG Luliang, LIU Zhang, YANG Xue, et al. A Method of Spatio-temporal Trajectory Fusion and Road Network Generation Based on Cognitive Law[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(11): 1271-1276. DOI: 10.11947/j.AGCS.2015.20140591.

[10] WU Junwei, ZHU Yunlong, KU Tao, et al. Detecting Road Intersections from Coarse-gained GPS Traces Based on Clustering[J]. Journal of Computers, 2013, 8(11): 2959-2965.

[11] XIE Xingzhe,BING-YUNGWONG 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.

[12] SHI Wenhuan, SHEN Shuhan, LIU Yuncai. Automatic Generation of Road Network Map from Massive GPS, Vehicle Trajectories[C]∥Proceedings of the 12th International IEEE Conference on Intelligent Transportation Systems. St. Louis, MO: IEEE, 2009: 1-6.

[13] 蔣益娟, 李響, 李小杰, 等. 利用車輛軌跡數(shù)據(jù)提取道路網(wǎng)絡(luò)的幾何特征與精度分析[J]. 地球信息科學(xué)學(xué)報(bào), 2012, 14(2): 165-170. JIANG Yijuan, LI Xiang, LI Xiaojie, et al. Geometrical Characteristics Extraction and Accuracy Analysis of Road Network Based on Vehicle Trajectory Data[J]. Journal of Geo-Information Science, 2012, 14(2): 165-170.

[14] KUNTZSCH C, SESTER M, BRENNER C. Generative Models for Road Network Reconstruction[J]. International Journal of Geographical Information Science, 2016, 30(5): 1012-1039.

[15] WANG Yin,LIU Xuemei,WEI Hong, et al. Crowd Atlas: Self-updating Maps for Cloud and Personal Use[C]∥Proceedings of the 11th Annual International Conference on Mobile Systems, Applications, and Services. New York: ACM, 2013: 27-40.

[16] 李怡靜, 胡翔云, 張劍清, 等. 影像與LiDAR數(shù)據(jù)信息融合復(fù)雜場(chǎng)景下的道路自動(dòng)提取[J]. 測(cè)繪學(xué)報(bào), 2012, 41(6): 870-876. LI Yijing,HU Xiangyun,ZHANG Jianqing,et al. Automatic Road Extraction in Complex Scenes Based on Information Fusion from LiDAR Data and Remote Sensing Imagery[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6): 870-876.

[17] 方莉娜, 楊必勝. 車載激光掃描數(shù)據(jù)的結(jié)構(gòu)化道路自動(dòng)提取方法[J]. 測(cè)繪學(xué)報(bào), 2013, 42(2): 260-267. FANG Lina, YANG Bisheng. Automated Extracting Structural Roads from Mobile Laser Scanning Point Clouds[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2): 260-267.

[18] 楊偉, 艾廷華. 基于眾源軌跡數(shù)據(jù)的道路中心線提取[J]. 地理與地理信息科學(xué), 2016, 32(3): 1-7. YANG Wei, AI Tinghua. Road Centerline Extraction from Crowdsourcing Trajectory Data[J]. Geography and Geo-Information Science, 2016, 32(3): 1-7.

[19] 李清泉, 李德仁. 大數(shù)據(jù)GIS[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2014, 39(6): 641-644. LI Qingquan, LI Deren. Big Data GIS[J]. Geomatics and Information Science of Wuhan University, 2014, 39(6): 641-644.

[20] DUCKHAM M,KULIK L,WORBOYS M, et al. Efficient Generation of Simple Polygons for Characterizing the Shape of a Set of Points in the Plane[J]. Pattern Recognition, 2008, 41(10): 3224-3236.

[21] LIU Qiliang, TANG Jianbo, DENG Min, et al. An Iterative Detection and Removal Method for Detecting Spatial Clusters of Different Densities[J]. Transactions in GIS, 2015, 19(1): 82-106.

[22] 艾廷華, 郭仁忠. 基于約束Delaunay結(jié)構(gòu)的街道中軸線提取及網(wǎng)絡(luò)模型建立[J]. 測(cè)繪學(xué)報(bào), 2000, 29(4): 348-354. AI Tinghua, GUO Renzhong. Extracting Center-lines and Building Street Network Based on Constrained Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2000, 29(4): 348-354.

[23] 艾廷華, 劉耀林. 保持空間分布特征的群點(diǎn)化簡(jiǎn)方法[J]. 測(cè)繪學(xué)報(bào), 2002, 31(2): 175-181. AI Tinghua, LIU Yaolin. A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 175-181.

[24] ZHENG Yu, LI Quannan, CHEN Yukun, et al. Understanding Mobility based on GPS Data[C]∥Proceedings of the 10th International Conference on Ubiquitous Computing. New York: ACM, 2008: 312-321.

[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.

(責(zé)任編輯：宋啟凡)

The Extraction of Road Boundary from Crowdsourcing Trajectory Using Constrained Delaunay Triangulation

YANG Wei,AI Tinghua

School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079,China

Extraction of road boundary accurately from crowdsourcing trajectory lines is still a hard work.Therefore,this study presented a new approach to use vehicle trajectory lines to extract road boundary.Firstly, constructing constrained Delaunay triangulation within interpolated track lines to calculate road boundary descriptors using triangle edge length and Voronoi cell.Road boundary recognition model was established by integrating the two boundary descriptors.Then,based on seed polygons,a regional growing method was proposed to extract road boundary. Finally, taxi GPS traces in Beijing were used to verify the validity of the novel method, and the results also showed that our method was suitable for GPS traces with disparity density,complex road structure and different time interval.

crowdsourcing trajectory; road updating;Delaunay triangulation; spatial clustering

The National Natural Science Foundation of China (No.41531180); The National High Technology Research and Development Program of China(863 Program) (No.2015AA1239012)

YANG Wei(1987—)，male，PhD candidate，majors in spatial-temporal trajectory data modeling and mining.

AI Tinghua

楊偉，艾廷華.運(yùn)用約束Delaunay三角網(wǎng)從眾源軌跡線提取道路邊界[J].測(cè)繪學(xué)報(bào)，2017,46(2)：237-245.

10.11947/j.AGCS.2017.20160233. YANG Wei,AI Tinghua.The Extraction of Road Boundary from Crowdsourcing Trajectory Using Constrained Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica,2017,46(2):237-245. DOI:10.11947/j.AGCS.2017.20160233.

P208

A

1001-1595(2017)02-0237-09

國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(41531180);國(guó)家863計(jì)劃(2015AA1239012)

2016-05-11

楊偉(1987—)，男，博士生，研究方向?yàn)闀r(shí)空軌跡數(shù)據(jù)建模與挖掘。

E-mail： ywgismap@whu.edu.cn

艾廷華

E-mail： tinghua_ai@tom.com

修回日期： 2016-12-22