基于浮動車數據的路口探測方法

譚 祥 爽，王 靜 ，宋 現 鋒,*，許 長 輝，汪 超 亮

(1.中國科學院大學，北京 100049；2.中國科學院光電研究院，北京 100094；3.中國測繪科學研究院，北京 100073)

?

基于浮動車數據的路口探測方法

譚 祥 爽1，王 靜1，宋 現 鋒1,2*，許 長 輝3，汪 超 亮2

(1.中國科學院大學，北京 100049；2.中國科學院光電研究院，北京 100094；3.中國測繪科學研究院，北京 100073)

路口及其通行規則探測是當前路網自動化提取工作中的難點問題，該文提出了一種簡單高效的從浮動車數據中探測路口與轉向規則的方法。假設車輛航跡線轉彎密集區為路口，首先通過對轉彎曲線空間聚類分析獲得路口中心，再利用同心圓面積遞增法估算出路口覆蓋范圍，最后根據路口范圍內航跡線行駛方向分布模式，識別出通行規則。該方法的特點是將路口視為具有中心和半徑的區域,而不是簡單的點。將該方法應用于淮北市城區出租車采集的浮動車數據，同人工解譯結果相比，探測路口的正確識別率約為91.6%，路口位置與解譯結果平均距離為3.57 m，表明方法具有較高的實用價值。

浮動車數據;路口識別;轉向規則;空間聚類;MeanShift算法

0 引言

電子地圖在交通管理、車輛導航、城市規劃等方面發揮著至關重要的作用[1]。但是，當前電子地圖的生產仍然是一個比較耗時費力的工作，尤其是含交通規則的可支持車輛導航和路徑規劃的路網，需要配備GNSS差分站等專門設備進行外業測量和室內手工編輯方能成圖[2]。當前出租車等公共車輛均配備了車載GNSS，在車輛安全監測的同時記錄了大量的行車航跡數據。這類低定位精度的海量浮動車數據能夠及時捕捉道路及其特征變化[3]，被認為是一種低成本、高效率的道路制圖新數據源，受到了國內外學者的關注。

交通路網是電子地圖的主體，是由路口和道路構成的具有拓撲關系的網絡結構。其中，路口是連接道路的交通樞紐，覆蓋一個局部空間區域，包含各種通行規則，控制著車輛在不同道路之間的有序通行。高質量導航交通地圖的構建，對路口的覆蓋范圍定位與通行規則的判斷必不可少。

鑒于路口的復雜結構，目前大部分學者通過提取道路，將路段交點視為路口，由此得到的路口是一個簡單的點，并非空間區域。例如：Lima和Ferreira 先柵格化航跡點覆蓋區域，再細化柵格區域方法構建道路網，同時將路段交叉點當作路口[4]。Cao和Krumm建立了一種新型的力學模型，將位置和方向相似的點聚類形成具有車道信息的路網，提出利用模式識別的方法判斷路口[5]。Bruntrup等先初始化道路網絡為空集，然后采用人工智能算法判斷航跡點與已有道路的空間關系，將GPS航跡逐條加入路網，也是將交叉點當作路口[6]。隨著研究深入，部分學者提出了可以獲取路口空間范圍的方法，但仍然缺少通行規則的判斷，使得路網的導航性受到限制。Fathi等首先選擇代表性路口區的航跡數據作為訓練樣本，然后通過待判定位置的GPS航跡線空間分布模式和訓練樣本的相似性來判斷其是否為路口[7]。Schroedl等通過分段、聚類等方法推斷出車道中心線的位置，再借助商業地圖和車道中心線判斷路口區域位置[8]。

因此，在目前提取路網和路口工作中，尚無法自動提取路口結構和通行規則等信息，構建出與實際路網相符的拓撲關系，實地測量和人工干預編輯仍然是當前交通路網制圖的主要方式。為了彌補以上方法的不足，本文充分利用浮動車數據的特點，不僅探測路口位置和路口分布范圍，而且提取路口的通行規則，探索路口提取的自動化方法，為支持構建高質量的車輛導航地圖奠定基礎。

1 路口探測原理

車輛轉彎起始(調頭)到轉彎(調頭)結束的航跡線段稱為轉彎曲線。車載GNSS航跡線的轉彎曲線和路口位置存在著很強的關聯性。從統計角度看，車載GNSS轉彎曲線發生在路口處的概率遠高于發生在直行道路的概率。

圖1a中灰色線段是從大量車載GNSS航跡線上提取的轉彎線段，圖1b從三維角度展現了路口區與非路口區曲線密度的差異。結果表明轉彎曲線空間分布密度在路口區和非路口區具有顯著差異：路口區異常密集、道路區分散稀疏。

圖1 車載GNSS轉彎曲線分布

Fig.1 Vehicle GNSS turning curves

基于路口與轉彎曲線的分布關系，本文提出假設：轉彎曲線分布密集的地區為路口。在此基礎上構建一種基于車載GNSS航跡線的路口自動提取方法。路口的探測分為3步：位置的探測、路口范圍探測和內部通行規則探測。通行規則是指路口允許的通行方式。例如，路口的某一方向駛入車輛只允許直行，不允許左轉。技術路線如下：首先提取航跡線的轉彎曲線并生成密度格網，統計各單元格中轉彎曲線分布密度；然后基于密度聚類方法[9-12]將轉彎曲線密度高的區域識別為路口區并計算出路口的中心位置；在路口位置的基礎上利用同心圓遞增法計算出路口覆蓋半徑；最后對覆蓋半徑內的行車軌跡的轉向進行聚類分類，分析出路口內的通車規則。

2 路口識別方法

2.1 轉彎曲線的空間密度估算

通常車輛在一條航跡線中，位于轉彎和掉頭處航跡點的平均曲率較大，而平直道路上航跡點的平均曲率較小甚至為0。根據曲率的變化可提取出位于車輛航跡線的轉彎線段部分。

采用網格將城區覆蓋范圍格網化，統計位于每個單元格內的彎曲航跡曲線的數目，計算網格密度值作為網格的屬性值。篩選線密度值大于0的單元用于路口探測，簡稱路口柵格點。

本文路口探測方法屬于點密度聚類分析類型，通過搜索密度峰值區域發現路口。路口區域內單元格值越高，路口越易被探測到。實際上，單元格過小，柵格數據量會急劇增加；過大則探測的路口位置準確性會大幅下降。通過設計一組網格劃分與密度計算實驗，比較了3個樣本路口在不同單元格大小下的最高密度值分布，本文確定了適合該組數據集的網格經驗值為5 m。

通常情況下，道路區內柵格點的屬性值非常低，而路口區相對較高，尤其是位于路口中心位置的密度值常為局部區域的高值點。統計整個地區柵格點的密度值分布，其近似符合泊松分布，考慮置信度為0.95的置信區間，假設小于置信區間下限的柵格點屬于路口的可能性很小(道路區非法掉頭、隨機轉彎等情況)，選擇大于置信區間下限的柵格，從而將路口區域的高密度值網格點提取出來用于路口探測分析。

2.2 基于密度聚類方法的路口探測

對篩選出的柵格點進行空間聚類，可有效探測出各路口及其中心位置。MeanShift算法[9]通過概率密度梯度函數估計離散點在各空間維的偏移均值來更新位置，通過不斷迭代使得離散點移動到局部高密度值區。MeanShift定義了一組核函數，確保離散點與當前聚類中心點的距離不同，其對新聚類中心偏移向量的貢獻亦不同。此外，筆者以柵格點的密度值作為權重系數，從而使得不同柵格點在決定路口中心位置時的重要性不同，其公式如下所示，本文中采用高斯核函數。

高斯核函數：

K(xi-x)=e-c||xi-x||2

(1)

路口中心位置：

(2)

式中:x為路口中心的初始位置，m(x)為x的新位置，N(x)為點x的鄰居集合，xi為路口區的第i個柵格點的位置，w(xi)為第i個柵格點的密度值(權重值)。

路口探測過程中需要給出聚類搜索半徑。若聚類半徑過大，則會將距離較近路口合并；若聚類半徑太小，則又可能將較大路口探測為多個路口。因此，本文采用雷普利函數分析聚合效果，給出了一個經驗值分布范圍，搜索半徑15～30m。其中，最優搜索半徑25m的聚合效果最好。

2.3 路口半徑確定

通常，路口形狀較為復雜，本文采用圓形近似代替，路口大小用覆蓋路口的圓形半徑表示。柵格點呈簇狀不均勻地分布在路口物理區域和功能區，柵格密度值呈現從路口中心向外圍逐漸遞減的趨勢。

本文提出了一種同心圓遞增法來探測路口的覆蓋半徑。該方法以聚類中心為圓心逐步增大探測半徑，以同心圓圓環內柵格密度平均值與同心圓內圓柵格密度平均值的比值z為指標(理論上z位于0～1之間)，判斷當前外圓半徑是否為最佳半徑。具體步驟如下：1)以探測出的路口位置為圓心，以初始半徑(如5m)確定圓，計算圓內柵格密度平均值；2)以一定增量增加圓半徑(如1m)，計算z值；3)循環步驟2直到圓半徑達到預定值或者z接近0時終止循環。

分析z值變化規律(圖2)，可將路口區域附近柵格點分為內核區、邊緣區和道路區。在路口內核區，z波動接近數值1，說明內核區內密度變化不大。路口邊緣區內z逐漸降低說明此區域逐步偏離路口。在靠近道路區，z在0值附近波動，表示已離開路口區。

圖2 基于同心圓遞增法的路口半徑探測

Fig.2Determiningtheradiusofanintersectionbytheconcentricareaincrementmethod

在路口內核區和邊緣區交界處，z值發生急劇下降，實驗中將該位置所對應的半徑數值定為路口覆蓋區的半徑(圖3)(見封3)。由于航跡線定位誤差原因，探測的半徑值較實際路口偏大，但是可以確保對轉彎航跡線的完整切割，用于路口通行規則分析。

2.4 路口通行規則的識別

在城市中，為了緩解交通壓力，路口會設置通行規則，禁止某些轉向，避免引起交通阻塞，提取路口通行規則對構建路網準確的拓撲關系至關重要。

基于探測的路口及其范圍，裁剪路口處的行車軌跡線，采用層次聚類對這些軌跡線的駛入和駛出方向進行聚類，將相同駛入和駛出路口方向的航跡線分為同一類。典型路口的轉彎分類結果如圖4所示(見封3)，路口行車軌跡被分成不同類別，計算每一類別所有軌跡駛入和駛出方向的平均值，以獲得通行規則，如(2°，87°)表示由南向北駛入路口，右轉彎駛向東方。這些通行規則是路網拓撲、路徑規劃和車輛導航的基礎信息。同時，利用這些規則及其類別數目還可進一步從探測的路口中甄別出道路急轉彎。

3 實驗結果與討論

3.1 研究區

實驗區位于安徽省淮北市城區，其中路口以平面交叉口為主，有丁字、十字、環島等類型。實驗數據來源于出租車車載GNSS記錄儀，數據采集頻率為1s，定位精度為5～15m。每條數據記錄了采集時間、經度、緯度、行駛速度和方向角等信息。本文數據集包含了從2011年6月到2013年1月的215萬條航跡點記錄，覆蓋了整個淮北市區的交通道路。

3.2 路口探測結果

本方法采用Python和SciPY軟件包，實現了路口自動探測程序。圖5將路口提取結果同遙感影像疊加，同人工解譯結果對比，路口結果較好。

圖5 淮北市區路口提取結果

Fig.5DetectedintersectionsbasedonfloatingcardatainHuaibeiCity

實驗數據覆蓋淮北市區交通路口462個。采用本方法探測到437個路口，其中非路口地區錯判成路口為14個，正確路口為423個，共遺漏39個路口，路口正確識別率約為91.6%，探測路口位置與解譯結果平均距離為3.57m。從實驗結果看，本文方法具有較高的實用價值。

錯判路口主要發生于城市的大型環島路口處，由于環形路口覆蓋范圍較大，并且路口中心區域沒有航跡覆蓋，在MeanShift聚類過程中無法找到環形路口中心，迭代最后終止在圓環與路段的連接處。結合探測的路口半徑和環島(或環形)路口的特點通過GIS空間疊置分析，將鄰近的錯判路口合并。未能探測出的路口主要發生在立交橋區和航跡線極其稀疏處(如：城市南部或小支路區)。立交橋覆蓋區域大、匝道轉彎平緩，局部范圍內所經過的航跡線曲率較小，導致立交橋部分路口不能被識別。

3.3 通行規則結果分析

路口通行規則是基于對路口范圍內的航跡數據分類進行提取的。路口每一個允許的通行方式都存在著大量軌跡線，統計這些軌跡線不僅獲得了某通行規則允許駛入路口和駛出路口的方向，而且航跡線的數目以及時段分布還可以提示路口各方向之間交通壓力的相對大小。圖6(見封3)是淮北市的一個交叉口，該路口軌跡線分為8類，分別用不同顏色表示。根據規則可以看出，南北走向的路是單行車道，路口東側允許掉頭。表1是一個路口通行規則及其對應的航跡線統計數目結果。

表1 通行規則提取結果

Table1Trafficrules

類別軌跡數(個)轉向規則(°)駛入/駛出方向轉向說明1217(178，267)北向西右轉2345(177，178)北向南直行3263(178，92)北向東左轉4336(87，88)西向東直行5298(268，267)東向西直行685(88，175)西向南右轉7127(267，179)東向南左轉8134(265，89)東向調頭

3.4 聚類方法選擇

本文采用了聚類分析的路口探測方式，結合海量航跡數據特點，對聚類方法有以下要求：1)路口數目未知，即聚類方法要求輸入的參數中不應該包含聚類數目；2)柵格間的空間距離與柵格值(轉彎曲線密度值)對聚類結果影響都較大，在聚類過程中必須予以考慮。根據以上條件， MeanShift、DBSCAN兩種聚類方法都比較適用。

Meanshift 算法是一個迭代過程，直至找到概率密度函數局部最大值結束。DBSCAN算法是將具有足夠高密度的區域劃分為一類，要求類中的每個點在給定的半徑范圍內至少包含一定數目的點[13]。Meanshift聚類算法只需要指定一個搜索半徑作為參數，DBSCAN聚類算法需要搜索半徑和聚類最小規模閾值。DBSCAN對最小規模閾值比較敏感，閾值過小將會切割大路口，過大又會合并鄰近的路口，應用于本工作時結果波動大。Meanshift聚類則可以較好地解決這一問題，其迭代尋找局部密度的高值點，密度不同的地區相互間不受干擾。

表2是兩種聚類方法在結果和時間性能上的對比，從計算效率上看，DBSCAN聚類方法比Meanshif方法耗時長，但是仍然在可接受范圍內。從效果上分析，兩種算法探測出的路口數目都少于人工解譯的462個，但是MeanShift的正確識別率較高。

表2 聚類效果及效率對比

Table 2 Comparison of intersections detecting result and computational time of different cluster methods

聚類方法識別路口數(個)錯判路口數(個)遺漏路口數(個)聚類時間(s)MeanShift437143921．10DBSCAN428175132．84

圖7(見封3)顯示了兩個柵格相連的路口，柵格中存在兩個密度高值區，中間存在著密度較小的柵格點(噪音點)。MeanShift算法將每個柵格點都選作種子起點尋找路口中心，柵格點不斷從外圍向路口中心移動，各點逐漸匯攏，如圖7a中綠色線條所示的移動軌跡，最后分別匯集至兩個密度高值區，形成兩個路口中心。DBSCAN是尋找密度符合要求的點的最大集合，圖7b 是在聚類最小規模閾值偏小時得出的結果，每個點都符合要求，所有柵格點被歸為一類。由于數據中存在多處兩個相鄰路口被噪音柵格相連的情況，很難選擇一個統一的域值，最終導致DBSCAN得到的結果比MeanShift遺漏的路口多。

4 結論

本文提出了一種利用浮動車數據探測路口的方法。不同于以前的方法，本文獲取的路口是有中心和半徑大小并且含內部通行規則的區域?；谠摲椒ǚ治隽塑囕v航跡數線在路口處的曲率與航向變化特點，采用Meanshift聚類算法探測路口中心，同時用提出的同心圓遞增法確定了路口半徑，這一信息有助于路口等級劃分與規模比較。更為重要的是，路口區域內不同航向的航跡線代表了不同的通行規則，通過航跡線的轉向分類，提取出了路口通行規則。最后，利用在淮北市出租車采集的GNSS航跡線數據進行了實驗，結果表明本方法在探測平面路口方面取得了較好的效果，正確識別率約為91.6%。后續工作還需要對該算法進一步改進，對大型環形路口和立交橋區路口的探測進行深入探索。

[1] 謝振東.智能交通系統的發展與思考[J].廣州交通， 2001(2)：32-36.

[2] LI J,QIN Q M,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.

[3] EKPENYONG F,PALMER-BROWN D,BRIMICOMBE A.Extracting road information from recorded GPS data using snap-drift neural network[J].Neurocomputing,2009,73(1-3):24-36.

[4] LIMA F,FERREIRA M.Mining spatial data from GPS traces for automatic road network extraction[A].6th International Symposium on Mobile Mapping Technology[C].Presidente Prudente,S o Paulo,Brazil,2009.

[5] CAO L,KRUMM J.From GPS traces to a routable road map[A].17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPAITLA GIS 2009)[C].ACM:Seattle,WA USA.2009.3-12.

[6] BRUNTRUP R,EDELKAMP S,JABBAR S,et al.Incremental map generation with GPS traces[A].Proceedings of the 8th International IEEE Conference on Intelligent Transportation Systems[C].Vienna,Austria,2005.

[7] FATHI A,KRUMM J.Detecting road intersections from GPS traces[A].GIScience 2010,Sixth International Conference on Geographic Information Science[C].Zurich,2010.

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

[9] CHENG Y Z.Mean shift,mode seeking and clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence (IEEE),1995,17(8):790-799.

[10] ESTER M,KRIEGEL H P,SANDER J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[A].Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining[C].Portland,OR,AAAI Press,1996.226-231.

[11] COMANICIU D,MEER P.Mean shift:A robust approach toward feature space analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(5):603-619.

[12] ROSENBLATT M.Remarks on some nonparametric estimates of a density function[J].Annals of Mathematical Statistics,1956,27(3):832-837.

[13] 馮少榮，肖文俊.DBSCAN 聚類算法的研究與改進[J].中國礦業大學學報， 2008，37(1)：105-111.

Detection of Road Intersections Using Floating Car Data

TAN Xiang-shuang1，WANG Jing1，SONG Xian-feng1,2，XU Chang-hui3，WANG Chao-liang2

(1.UniversityofChineseAcademyofSciences，Beijing100049;2.AcademyofOpto-Electronics,ChineseAcademyofSciences，Beijing100094;3.ChineseAcademyofSurveyingandMapping，Beijing100073,China)

The detection of intersections is a hotspot and difficulty issue in the automated extraction of road network from floating car data (vehicle GNSS trajectories).This paper presents a simple but efficient approach for detecting intersections and associated turning rules.Assuming intersections are located in the areas where exists local maxima of dense turning curves of vehicles,the locations of intersection are first detected by the MeanShift algorithm,the sizes of intersections are then estimated by the proposed concentric area increment method,and the turning rules are finally determined by classifying the directions of both entrance and exit of those approaching trajectories.The advantage of this work is that an intersection is treated as a compact area in which traffic rules are used to schedule vehicles approaching,not a simplified point.This approach was tested using taxi trajectories collected in Huaibei City,China.In a comparison of visually interpreted results,more than 91.6% of intersection could be correctly recognized and the average distance between the result and the truth is 3.57 m.This shows a big potential advantage of applying the approach in generating routable maps.

floating car data;intersection recognition;turning rules;spatial clustering;MeanShift algorithm

2015-03-23；

2015-05-19

國家科技重大專項(2011ZX05039-004);中國科學院知識創新工程項目(KZCX2-EW-QN605);國家自然科學基金項目(40771167)。

譚祥爽(1987-)，男， 碩士，主要從事空間數據挖掘研究。*通訊作者E-mail：xfsong@ucas.ac.cn

10.3969/j.issn.1672-0504.2015.05.008

P283.7

A

1672-0504(2015)05-0034-05