朱鴻博，王山東，李 賀，方 琪，征 程

(河海大學(xué) 地球科學(xué)與工程學(xué)院，江蘇 南京 210000)

0 引 言

隨著國(guó)家經(jīng)濟(jì)迅速發(fā)展，城市汽車總量持續(xù)增長(zhǎng)，道路交通擁擠成為制約城市發(fā)展的一個(gè)瓶頸。如何快速高效實(shí)時(shí)反映路況成為新的研究課題，而對(duì)于路網(wǎng)提取與更新是實(shí)現(xiàn)實(shí)時(shí)反映路況的前提條件。如果導(dǎo)航地圖無(wú)法做到及時(shí)快速更新，其現(xiàn)勢(shì)性將不能滿足應(yīng)用需求。浮動(dòng)車軌跡數(shù)據(jù)憑借其成本低、實(shí)時(shí)性強(qiáng)、信息量大等優(yōu)點(diǎn)，逐漸地得到重視，對(duì)有效地提取路網(wǎng)提供了強(qiáng)有力的保證。

基于GPS軌跡數(shù)據(jù)提取路網(wǎng)已經(jīng)涌現(xiàn)出三類方法[1]：

1）利用各種聚類算法對(duì)柵格或是矢量數(shù)據(jù)聚類；

2）核密度估計(jì)算法;

3）軌跡合成算法。

本文主要針對(duì)第一種方法研究了國(guó)內(nèi)外的現(xiàn)狀。Edelkamp等人[2]最先提出了基于K-Means算法的路網(wǎng)提取方法，并引入了擬合方法來(lái)表示道路中心線，進(jìn)一步提高了路網(wǎng)的精度。Worrall等人[3]在K-Means算法基礎(chǔ)上，提出用簡(jiǎn)潔的線段與弧模型來(lái)表示生成的路網(wǎng)。Schroedl等[4-5]提出一種類似K-means 算法的路網(wǎng)提取方法，并引用最小二乘法擬合道路中心線，但是K-means算法不能滿足自動(dòng)確定類簇?cái)?shù)目的要求，且迭代的過(guò)程具有很高的時(shí)間復(fù)雜度；朱云龍等人[6]將基于網(wǎng)格相對(duì)密度的多密度聚類算法用于道路提取，雖然該法能夠有效地確定交叉口的位置及數(shù)量，能夠?qū)崿F(xiàn)路網(wǎng)結(jié)構(gòu)的快速構(gòu)造，但是沒(méi)有考慮不同鄰接網(wǎng)格對(duì)當(dāng)前網(wǎng)格影響的不同?；贒BSCAN算法的聚類方法不能很好地確定合適的密度閾值，可能會(huì)將相鄰的道路特征點(diǎn)合并或者同一個(gè)道路特征點(diǎn)拆分。

本文在研究了國(guó)內(nèi)外現(xiàn)狀的基礎(chǔ)上，提出將基于網(wǎng)格密度因子的多密度聚類算法引入路網(wǎng)提取，該聚類算法通過(guò)密度可達(dá)性來(lái)確定聚類類簇，有效地解決了K-Means算法需要事先設(shè)置類簇個(gè)數(shù)的缺點(diǎn)。且該算法考慮了相鄰網(wǎng)格之間的聯(lián)系，解決了大部分網(wǎng)格聚類算法只考慮網(wǎng)格內(nèi)包含的浮動(dòng)車數(shù)據(jù)，而忽視相鄰網(wǎng)格之間數(shù)據(jù)的相關(guān)性的問(wèn)題。解決了這些問(wèn)題之后得到的聚類點(diǎn)精度和準(zhǔn)確性都有了一定的提高。

1 理論與方法

1.1 疑似特征點(diǎn)提取

浮動(dòng)車軌跡中道路特征點(diǎn)可以看做是道路發(fā)生明顯變化的點(diǎn)，即行駛過(guò)程中航向角變化較大的點(diǎn)，這些點(diǎn)大都集中在道路交叉口附近。區(qū)別于路口轉(zhuǎn)彎點(diǎn)，利用道路特征點(diǎn)來(lái)生成路網(wǎng)擁有更好的擬合性，同時(shí)也能通過(guò)交叉判別，提取出路口轉(zhuǎn)彎點(diǎn)，建立完整的路網(wǎng)。

根據(jù)浮動(dòng)車軌跡中相隔一個(gè)頻率的前后相鄰的兩個(gè)軌跡點(diǎn)的方向角變化值進(jìn)行判別，如果變化角度超過(guò)一定的閾值，那么就懷疑這兩個(gè)點(diǎn)在真實(shí)轉(zhuǎn)彎點(diǎn)附近，為道路特征點(diǎn)。如圖1所示。

圖1 路口軌跡點(diǎn)Fig.1 Track point in intersection

以道路交叉口為例，圖1中點(diǎn)2和點(diǎn)3應(yīng)為道路特征點(diǎn)，但是其聚集性不好，并沒(méi)有聚集到交叉口中心位置，這是由于GPS點(diǎn)的粗粒度特性[7]。根據(jù)這樣的道路特征點(diǎn)提取路口點(diǎn)不夠精確，所以，本文引入聚集性更強(qiáng)的疑似道路特征點(diǎn)。

道路交叉口存在于道路轉(zhuǎn)彎點(diǎn)的行駛方向，因此，我們將轉(zhuǎn)彎點(diǎn)前后兩點(diǎn)的行駛方向的交會(huì)點(diǎn)作為真實(shí)道路的轉(zhuǎn)彎點(diǎn)，并使得行駛方向上當(dāng)前點(diǎn)與前一點(diǎn)連線的方向角之差小于轉(zhuǎn)向閾值，如圖2中，點(diǎn)5為更具集聚性的交叉路口點(diǎn)，即疑似道路特征點(diǎn)。

圖2 疑似道路特征點(diǎn)Fig.2 Suspected road feature points

疑似道路特征點(diǎn)提取流程圖如圖3所示。

圖3 提取流程圖Fig.3 Extract flow chart

1.2 基于網(wǎng)格密度影響因子的多密度聚類算法

定義如下：

定義1，數(shù)據(jù)集X。X={xi,i=1,2,…,n},X是一個(gè)二維空間的點(diǎn)集，xi=(xi1, xi2)，代表第i個(gè)數(shù)據(jù)對(duì)象，xi1和xi2這里用來(lái)描述浮動(dòng)車軌跡的經(jīng)緯度坐標(biāo)。

定義2，網(wǎng)格單元。在研究區(qū)域內(nèi)，設(shè)置取值范圍，并對(duì)該范圍進(jìn)行劃分，得到m×n個(gè)矩形單元集合U，U={u1,u2,…,um×n}，其中ui為網(wǎng)格單元。

定義3，網(wǎng)格密度。網(wǎng)格單元ui中，數(shù)據(jù)對(duì)象的數(shù)目之和稱為網(wǎng)格密度，記做den(ui)。當(dāng)den(ui)=0時(shí)，稱ui為空單元；當(dāng)den(ui)＞0時(shí)，稱ui為非空單元。

定義4，鄰接網(wǎng)格。當(dāng)且僅當(dāng)網(wǎng)格單元ui和uj有公共邊或公共點(diǎn)時(shí)，稱ui和uj是鄰接網(wǎng)格。ui所有的非空鄰接網(wǎng)格的集合記為Ngs(ui)。

二維空間中的鄰接網(wǎng)格只有兩種情況：第一種是有且只有一個(gè)公共點(diǎn)，這類我們稱為第一類鄰接網(wǎng)格；第二類是具有一個(gè)公共邊，這類我們稱為第二類鄰接網(wǎng)格。

對(duì)于網(wǎng)格ui的非空鄰接單元Ngs(ui)，若uj屬于上面所說(shuō)的第α類(α=1，2)，則uj對(duì)ui的影響權(quán)重ωij為：

式中，n為空間的維數(shù)，mα為Ngs(ui)中屬于第α類的非空鄰接單元的總個(gè)數(shù)，

定義5，網(wǎng)格的密度影響因子(impact factor of grid density ,IFGD)。網(wǎng)格ui的IFGD是指ui的網(wǎng)格密度與其非空鄰接網(wǎng)格Ngs(ui)中所有網(wǎng)格的密度值與權(quán)重值乘積的總和的比值[8]。

當(dāng)IFGD(ui)＜1時(shí)，說(shuō)明網(wǎng)格ui的密度值小于鄰接網(wǎng)格的平均密度；當(dāng)IFGD(ui)=1時(shí),說(shuō)明網(wǎng)格ui的密度值和鄰接網(wǎng)格的平均密度相近；當(dāng)IFGD(ui)＞1時(shí)，說(shuō)明網(wǎng)格ui的密度值大于鄰接網(wǎng)格的平均密度。IFGD(ui)的值越大，表明ui處于類簇的中心位置的概率越大，反之，則偏離類簇中心位置的概率越大。

定義6，核心網(wǎng)格。當(dāng)IFGD(ui)≥1時(shí)，說(shuō)明網(wǎng)格ui更靠近某個(gè)類簇的中心，則認(rèn)為是核心網(wǎng)格。

定義7，直接密度可達(dá)。若uj∈Ngs(ui),且滿足：

即當(dāng)鄰接網(wǎng)格滿足式（3）時(shí)，我們可以稱uj直接密度可達(dá)ui，式（3）中pct是密度浮動(dòng)參數(shù)，易證直接密度可達(dá)是對(duì)稱的，即如果uj直接密度可達(dá)ui，則ui也直接密度可達(dá)uj。這樣就可以在聚類過(guò)程中來(lái)判別網(wǎng)格是否應(yīng)當(dāng)合并擴(kuò)展成類簇的主要輪廓。

定義8，密度可達(dá)。在網(wǎng)格序列u1,u2,…,un中，ui=p,un=q，滿足ui直接密度可達(dá)ui+1，1≤i＜n，則稱網(wǎng)格p密度可達(dá)網(wǎng)格q，同樣易證網(wǎng)格密度可達(dá)是對(duì)稱的。

定義9，基類。基類C即一個(gè)簇的骨架，是一個(gè)非空子集，滿足：至少存在一個(gè)核心網(wǎng)格u0∈C,且任意ui是從u0基于密度可達(dá)的，則ui∈C（極大性和連通性）。

基于以上定義，基于網(wǎng)格密度影響因子的多密度聚類算法步驟如下：

1）將數(shù)據(jù)集D所在的空間范圍劃分為 m×n個(gè)網(wǎng)格單元；

2）計(jì)算每個(gè)網(wǎng)格單元的密度值和網(wǎng)格密度影響因子；

3）根據(jù)定義6提取核心網(wǎng)格；

4）根據(jù)密度可達(dá)性進(jìn)行標(biāo)記、歸類，得到類簇。

1.3 基于加權(quán)質(zhì)心的特征點(diǎn)確定

確定了道路特征點(diǎn)的類簇之后，再提取出每個(gè)類簇的質(zhì)心，確定道路特征點(diǎn)的位置，就可以完成道路特征點(diǎn)的最終提取。針對(duì)本文這種具有明顯集聚性的數(shù)據(jù)，此處采用了加權(quán)求質(zhì)心的方法[9]。

我們假設(shè)一個(gè)聚類好的點(diǎn)集數(shù)據(jù)W={W1,W2,…,Wn}，n為類簇的個(gè)數(shù)，Wp={wp1,wp2,…,wpm}，為第p個(gè)類簇的點(diǎn)集，p=1,2,…,n，m為該類簇內(nèi)點(diǎn)的個(gè)數(shù)，wpq={xi,yi},為p類中的一個(gè)點(diǎn)，q=1,2,…,m，i=1,2,…,m。每個(gè)類簇的質(zhì)心都是未知的，其坐標(biāo)為(Xe,Ye)，則加權(quán)質(zhì)心計(jì)算公式如下：

式（4）和（5）中：ωi表示每個(gè)疑似道路特征點(diǎn)賦的權(quán)重值。這里，根據(jù)統(tǒng)計(jì)，我們將每個(gè)點(diǎn)在其位置出現(xiàn)的次數(shù)作為權(quán)重值，出現(xiàn)的次數(shù)越多，代表其越靠近真實(shí)位置，其影響也越大。

通過(guò)加權(quán)求質(zhì)心的方法，可以求得每個(gè)類簇質(zhì)心的坐標(biāo)值，即道路特征點(diǎn)的位置。

1.4 道路拓?fù)浣Y(jié)構(gòu)及路網(wǎng)構(gòu)建

基于道路網(wǎng)絡(luò)幾何模型可以得到道路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，將路網(wǎng)數(shù)據(jù)中的交叉口和路段以節(jié)點(diǎn)-弧段模型的方式記錄，即以圖的形式存儲(chǔ)起來(lái)[10]。

本文選取了鄰接表表示法，通過(guò)創(chuàng)建路段表來(lái)存儲(chǔ)相關(guān)數(shù)據(jù)和拓?fù)湫畔11]。表結(jié)構(gòu)見(jiàn)表1。

表1 路段存儲(chǔ)結(jié)構(gòu)表Tab.1 Section of the storage structure table

表1中路段ID是路段的唯一標(biāo)識(shí)號(hào)；道路特征點(diǎn)編號(hào)為路段從起始點(diǎn)編號(hào)依次記錄到路段終止點(diǎn)編號(hào)。

有了道路特征點(diǎn)，通過(guò)軌跡段的獲取，就可以判斷相鄰道路特征點(diǎn)間是否存在道路段，完成路網(wǎng)的構(gòu)建。通過(guò)判斷兩個(gè)道路特征點(diǎn)之間是否存在一定數(shù)量的公共軌跡段，如果存在，則說(shuō)明這兩個(gè)點(diǎn)之間可能存在路段，反之，則不一定存在路段。

這里，我們將浮動(dòng)車的軌跡按照車牌號(hào)、采集時(shí)間的順序排列，當(dāng)滿足一定的時(shí)間連續(xù)性和方向角變化時(shí)，可按照同一輛車時(shí)間的先后順序?qū)⑵滢D(zhuǎn)化為車輛的軌跡段T，T={x1,x2,…,xn}，xi為浮動(dòng)車軌跡點(diǎn)。

對(duì)提取得到的道路特征點(diǎn)進(jìn)行緩沖區(qū)生成，將車輛軌跡段所經(jīng)過(guò)的道路特征點(diǎn)按照時(shí)間先后順序排成一個(gè)序列R={r1,r2,…,rn}, ri為道路特征點(diǎn)，i=1,2,…,n，則稱道路特征點(diǎn)ri和ri+1存在一條公共軌跡段。遍歷所有的軌跡段和道路特征點(diǎn)，得到所有道路特征點(diǎn)兩兩之間公共軌跡段的數(shù)量，當(dāng)數(shù)量達(dá)到一定的閾值時(shí)，則認(rèn)為這兩個(gè)道路特征點(diǎn)之間存在直接相連的道路。確定所有道路特征點(diǎn)的鄰接關(guān)系，將存在路段的道路特征點(diǎn)相連接得到道路段，就完成了路網(wǎng)的構(gòu)建工作。本文提取路網(wǎng)流程圖如圖4所示。

圖4 路網(wǎng)提取流程圖Fig.4 Flowchart of road network extraction

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

2.1 疑似特征點(diǎn)提取

1）實(shí)驗(yàn)數(shù)據(jù)

本文數(shù)據(jù)是2010年9月南京市區(qū)及周邊地區(qū)的1萬(wàn)多輛出租車1天的軌跡數(shù)據(jù)，采樣頻率在30～60 s之間。預(yù)處理后的部分軌跡點(diǎn)數(shù)據(jù)如圖5所示。

圖5 預(yù)處理后部分軌跡點(diǎn)Fig.5 Partial trajectory after pretreatment

2）疑似特征點(diǎn)提取

將完成數(shù)據(jù)預(yù)處理后的軌跡點(diǎn)按照車牌號(hào)和采集時(shí)間進(jìn)行排序，得到數(shù)據(jù)集X={x1,x2…,xn1}，n1為車輛的數(shù)量，xi為第i輛車按照采集時(shí)間排序的車輛軌跡，i=1,2,…,n1，xi={p1,p2,…,pn2}，n2為第i輛車軌跡點(diǎn)的數(shù)量，pj為第i輛車的軌跡點(diǎn)，j=1,2,…,n2，pj={xj,yj,tj,dirj,vj}，其中，xj為pj的經(jīng)度坐標(biāo)，yj為pj的緯度坐標(biāo)，tj為pj的采集時(shí)間，dirj為pj的方向角，vj為pj的瞬時(shí)速度。設(shè)定時(shí)間閾值為Δt閾，方向角閾值為Δdir閾，當(dāng)Δt=ti+1-ti＜Δt閾，且Δdir=diri+1-diri＞Δdir閾時(shí)，則認(rèn)為pi和pi+1為轉(zhuǎn)彎點(diǎn)，將pi和pi-1的連線作為當(dāng)前路段的行駛方向，將pi+1和pi+2的連線作為即將轉(zhuǎn)入的路段的行駛方向，那么可以認(rèn)為兩個(gè)行駛方向的交會(huì)點(diǎn)為疑似道路特征點(diǎn)。同時(shí)，通過(guò)方向角確定出當(dāng)前車輛的行駛方向。這里根據(jù)采樣間隔和經(jīng)驗(yàn)值，設(shè)置Δt閾=60 s，Δdir閾=30°，提取出來(lái)的疑似道路特征點(diǎn)如圖6所示。

圖6 疑似道路特征點(diǎn)Fig.6 Suspected road feature points

2.2 基于聚類方法及加權(quán)質(zhì)心提取特征點(diǎn)

1）將實(shí)驗(yàn)區(qū)域劃分成n×m個(gè)矩形網(wǎng)格，并統(tǒng)計(jì)每個(gè)網(wǎng)格內(nèi)疑似道路特征點(diǎn)的數(shù)目，利用基于網(wǎng)格密度影響因子的多密度聚類算法對(duì)疑似道路特征點(diǎn)進(jìn)行聚類。

網(wǎng)格大小的設(shè)定對(duì)于算法的效果有很大的影響，網(wǎng)格設(shè)置太小，會(huì)影響算法的效率，網(wǎng)格設(shè)置太大，則分類效果不好。這里考慮到正常的道路寬度，并結(jié)合經(jīng)驗(yàn)值和多次實(shí)驗(yàn)，將實(shí)驗(yàn)區(qū)域劃分成10 m×10 m的網(wǎng)格，第一類鄰接網(wǎng)格有4個(gè)，影響因子為1/12，第二類鄰接網(wǎng)格有4個(gè)，影響因子為1/6。將空網(wǎng)格剔除，設(shè)定pct=0.8，通過(guò)基于網(wǎng)格密度影像因子的方法進(jìn)行聚類，剔除噪聲點(diǎn)。

2）提取出每個(gè)類簇的質(zhì)心，即道路特征點(diǎn)，結(jié)果如圖7所示，共265個(gè)道路特征點(diǎn)，這些特征點(diǎn)中還包括了道路段上可以進(jìn)行轉(zhuǎn)向掉頭的岔口。將道路特征點(diǎn)和影像圖進(jìn)行比對(duì)，發(fā)現(xiàn)具有較高的吻合性。

圖7 道路特征點(diǎn)Fig.7 Road feature points

2.3 路網(wǎng)生成

將上述步驟生成的道路特征點(diǎn)加入到道路網(wǎng)絡(luò)模型中構(gòu)建道路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，以節(jié)點(diǎn)-弧段的方式存儲(chǔ)生成軌跡段，通過(guò)生成的軌跡段來(lái)確定道路特征點(diǎn)的鄰接關(guān)系，完成路網(wǎng)的提取。如果相鄰兩個(gè)特征點(diǎn)具有足量的共同軌跡，則認(rèn)為這兩個(gè)道路特征點(diǎn)之間存在路段，可以連接形成道路段。路網(wǎng)生成結(jié)果如圖8所示。

圖8 路網(wǎng)Fig.8 Road Network

部分道路拓?fù)潢P(guān)系表見(jiàn)表2。

表2 道路拓?fù)潢P(guān)系表Tab.2 Road topological relation table

2.4 結(jié)果分析

本文的數(shù)據(jù)是2010年的浮動(dòng)車軌跡數(shù)據(jù)，參考路網(wǎng)的矢量數(shù)據(jù)為2008年的數(shù)據(jù)，通過(guò)匹配判別，可以看出提取路網(wǎng)的準(zhǔn)確性。如圖9所示，通過(guò)比較，可以發(fā)現(xiàn)提取得到的道路交叉口和路網(wǎng)數(shù)據(jù)具有較好的一致性，有些沒(méi)有匹配成功的道路，一是存在一些變動(dòng)過(guò)的道路，如新增道路或者廢棄道路等，二是存在一些錯(cuò)誤相連的道路，三是存在數(shù)據(jù)覆蓋率不足的原因。其中，錯(cuò)誤相連的道路情況如圖10所示。

圖9 對(duì)比分析Fig.9 Comparative analysis

圖11 中轉(zhuǎn)向口B與交叉口A和C相鄰接，但是由于路段AB、BC都較短，因此，當(dāng)車輛從A快速行駛至C時(shí)，會(huì)忽略B的存在，認(rèn)為交叉口A和C是直接相連的，且存在路段，因此會(huì)生成錯(cuò)誤的不存在的路段[6]。

圖10 錯(cuò)誤關(guān)聯(lián)道路Fig.10 Wrong connected road

圖11 示意圖Fig.11 Illustration

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

隨著車載定位設(shè)備的普及應(yīng)用，車輛軌跡數(shù)據(jù)的來(lái)源越來(lái)越豐富。尤其是出租車的軌跡數(shù)據(jù)具有覆蓋面廣、信息更新速度快等特點(diǎn)。利用車輛軌跡構(gòu)建的道路網(wǎng)絡(luò)，可更新現(xiàn)有電 子地圖的道路信息。本文將基于網(wǎng)格密度影響因子的多密度聚類算法引入路網(wǎng)提取，在實(shí)驗(yàn)區(qū)范圍內(nèi)取得了不錯(cuò)的結(jié)果，但是由于實(shí)驗(yàn)數(shù)據(jù)較少，而且沒(méi)有考慮立交橋，高架等復(fù)雜道路情況。在以后的研究中，這些復(fù)雜路況也會(huì)成為我們研究的重點(diǎn)。