陳 杰,沈文怡,吳問宇,毛嘉莉

（華東師范大學(xué) 數(shù)據(jù)科學(xué)與工程學(xué)院,上海 200062）

0 引 言

隨著非機(jī)動車保有量的大規(guī)模增加,互聯(lián)網(wǎng)相關(guān)的非機(jī)動車行業(yè)蓬勃發(fā)展且已進(jìn)入快速成長期.為方便快捷地到達(dá)目的地,人們常以非機(jī)動車作為交通工具.由于缺少專業(yè)精準(zhǔn)的非機(jī)動車騎行導(dǎo)航地圖,非機(jī)動車常常進(jìn)入非機(jī)動車限行區(qū)域,導(dǎo)致在行程中花費(fèi)較多的時(shí)間并存在安全風(fēng)險(xiǎn).此外,騎行時(shí)若依賴更新不及時(shí)的兩輪車導(dǎo)航軟件所提供的線路前往目的地,則容易發(fā)生誤入深山、林區(qū)等事件.構(gòu)建并及時(shí)更新非機(jī)動車騎行地圖能保證高效騎行線路規(guī)劃,提升非機(jī)動車騎行體驗(yàn)感.隨著非機(jī)動車相關(guān)服務(wù)的迅猛增長,出現(xiàn)了海量的非機(jī)動車軌跡數(shù)據(jù),這些軌跡數(shù)據(jù)與所對應(yīng)產(chǎn)生的行程、車輛、基準(zhǔn)路網(wǎng)等數(shù)據(jù),為騎行地圖的推斷提供了數(shù)據(jù)基礎(chǔ).由于受定位設(shè)備誤差、非機(jī)動車騎行習(xí)慣等因素的影響,騎行軌跡數(shù)據(jù)集中存在大量異常數(shù)據(jù)以及定位信息缺失的情況,使非機(jī)動車騎行地圖的推斷面臨嚴(yán)峻的挑戰(zhàn),因此急需設(shè)計(jì)一種軌跡數(shù)據(jù)質(zhì)量提升方法,用來提升面向騎行地圖推斷的數(shù)據(jù)質(zhì)量.

通過對真實(shí)非機(jī)動車騎行軌跡數(shù)據(jù)的分析與調(diào)研,非機(jī)動車騎行軌跡中除了軌跡數(shù)據(jù)普遍存在的帶有方向、速度噪聲的異常軌跡點(diǎn)以外,還存在熱門騎行區(qū)域的徘徊軌跡段、帶有違規(guī)轉(zhuǎn)向與逆向騎行的違章軌跡段、信號漂移軌跡段以及信號缺失軌跡段等數(shù)據(jù)異常.徘徊軌跡段常見于非道路區(qū)域,伴有方向多變與低速行駛的現(xiàn)象.違章軌跡段則以非轉(zhuǎn)向區(qū)域的轉(zhuǎn)向以及逆行事件呈現(xiàn),它們?yōu)榈缆吠負(fù)涞木珳?zhǔn)提取帶來一定程度的干擾,需要及時(shí)發(fā)現(xiàn)并消除.信號漂移軌跡段和信號缺失軌跡段常發(fā)生在信號薄弱區(qū)域,需要利用歷史軌跡數(shù)據(jù)對漂移行為進(jìn)行有效識別以及基于稀疏數(shù)據(jù)對缺失軌跡進(jìn)行恢復(fù).非機(jī)動車騎行軌跡數(shù)據(jù)存在的質(zhì)量問題具體如下.

(1)異常軌跡點(diǎn): 騎行軌跡存在偏離其近鄰的異常軌跡點(diǎn),表現(xiàn)為與近鄰點(diǎn)在時(shí)間、距離、方向上具有明顯差異,如圖1(a)所示.

(2)徘徊軌跡段: 考慮用戶到達(dá)騎行終點(diǎn)附近需尋找停車位置,用戶的軌跡方向無規(guī)律地跳變,其騎行速度較慢,騎行終點(diǎn)附近區(qū)域存在大量到達(dá)狀態(tài)的軌跡點(diǎn)等,如圖1(b)所示的商務(wù)區(qū)CBD(central business district)地下停車場(以紅色圓圈標(biāo)注).該部分軌跡段不屬于在道路上的騎行狀態(tài),對于地圖推斷無意義.

(3)違章行駛軌跡段: 非機(jī)動車在行駛過程出現(xiàn)違規(guī)騎行行為,如逆向行駛、在非機(jī)動車限行道路上行駛、禁止轉(zhuǎn)向區(qū)域的轉(zhuǎn)向等,如圖1(c)所示(以紫色線段標(biāo)注).

(4)軌跡段缺失: 定位設(shè)備信號弱導(dǎo)致軌跡段缺失,如圖1(d)所示,在信號較弱區(qū)域,被采樣的軌跡出現(xiàn)大量軌跡點(diǎn)采樣缺失的情況,導(dǎo)致相鄰軌跡點(diǎn)的距離較遠(yuǎn),即連續(xù)軌跡點(diǎn)間連接產(chǎn)生的軌跡段較長,使用這些長距離的軌跡段定位信號薄弱區(qū)域.

(5)軌跡段漂移: 當(dāng)經(jīng)過高架、隧道等區(qū)域時(shí),GPS(global positioning system)信號無法準(zhǔn)確定位,移動設(shè)備自帶的慣導(dǎo)系統(tǒng)根據(jù)連續(xù)測得的運(yùn)動方向和加速度推算車輛后續(xù)位置,即相對位置.當(dāng)后續(xù)坐標(biāo)系轉(zhuǎn)換不恰當(dāng)時(shí),會出現(xiàn)整段漂移的情況,如圖1(e)所示.

針對上述問題,本文提出了一個(gè)面向騎行地圖推斷的軌跡數(shù)據(jù)質(zhì)量提升框架,具體如下.

(1)本文研究了非機(jī)動車騎行軌跡中存在的影響后續(xù)地圖推斷的數(shù)據(jù)質(zhì)量問題,包括需要進(jìn)行軌跡去噪的軌跡噪聲中的異常軌跡點(diǎn)(方向噪聲、速度噪聲)和異常軌跡段(徘徊軌跡段、違章軌跡段)以及需要進(jìn)行軌跡恢復(fù)的軌跡段缺失和軌跡段漂移.

(2)為了解決非機(jī)動車騎行軌跡存在的異常軌跡和數(shù)據(jù)缺失等低質(zhì)量問題,本文針對異常軌跡點(diǎn)、異常軌跡段、軌跡段缺失及軌跡段漂移等制定了基于異常特征的檢測方法,并進(jìn)行了數(shù)據(jù)質(zhì)量提升.

(3)本文使用真實(shí)軌跡數(shù)據(jù),以非機(jī)動車軌跡的后續(xù)地圖推斷為標(biāo)準(zhǔn),通過與現(xiàn)有軌跡數(shù)據(jù)質(zhì)量提升方法進(jìn)行對比實(shí)驗(yàn),驗(yàn)證了本文所提出的方法能有效改進(jìn)非機(jī)動車軌跡數(shù)據(jù)的質(zhì)量,并且較大提升了后續(xù)的地圖構(gòu)建效果.

1 相關(guān)工作

1.1 軌跡去噪

目前實(shí)現(xiàn)軌跡去噪的方法主要可以分為以下兩類: 第一類是基于近鄰軌跡的離群去噪法,該方法以噪聲軌跡的時(shí)空相鄰軌跡為基準(zhǔn),比較噪聲軌跡與這些基準(zhǔn)軌跡在速度、方向和距離等特征上的差異以實(shí)現(xiàn)噪聲軌跡的檢測與去噪.文獻(xiàn)[1-3]先對軌跡進(jìn)行地圖匹配獲得未匹配軌跡,再使用kNN(knearest neighbor)算法獲得密度離群軌跡點(diǎn)并舍棄.文獻(xiàn)[4-5]首先基于采樣間隔對軌跡進(jìn)行分段、再刪除距離較短或軌跡點(diǎn)較少的分段并對軌跡進(jìn)行簡化.該方法對于采樣質(zhì)量較高且不存在違規(guī)軌跡段的軌跡數(shù)據(jù)的去噪效果較好,但對于在非機(jī)動車騎行軌跡中存在的大量違章軌跡段和非道路區(qū)域的徘徊軌跡段不能很好檢測與消除,這容易導(dǎo)致地圖構(gòu)建時(shí)出現(xiàn)大量錯(cuò)誤.第二類是保留關(guān)鍵信息的軌跡簡化法,通過保留最可信的部分軌跡并去除其余軌跡的方式以實(shí)現(xiàn)軌跡去噪[6-9].文獻(xiàn)[7]保留與前一個(gè)點(diǎn)大于等于10 m 的點(diǎn)進(jìn)行去噪,文獻(xiàn)[8-9]隨機(jī)選取軌跡點(diǎn),并將其附近小距離閾值內(nèi)的點(diǎn)的信息聚集到該點(diǎn),每次操作完將該范圍內(nèi)的所有其他點(diǎn)進(jìn)行刪除,直到所有的軌跡點(diǎn)都處理完畢,該方法對于密集軌跡的去噪效果較好.非機(jī)動車騎行軌跡較為稀疏,使用該方法進(jìn)行軌跡去噪則會遺漏大量軌跡數(shù)據(jù)使得數(shù)據(jù)更加稀疏,不利于騎行地圖的推斷.

1.2 軌跡恢復(fù)

目前對于缺失軌跡數(shù)據(jù)的處理方式主要可以分為以下3 類: 第一類是線性插值法,該方法在起始點(diǎn)和結(jié)束點(diǎn)之間進(jìn)行線性插補(bǔ).文獻(xiàn)[10]通過假設(shè)軌跡是沿直線且均勻移動,以此來恢復(fù)缺失位置.當(dāng)移動對象沿直線移動時(shí),該方法填補(bǔ)效果良好,實(shí)際上移動對象可能存在沿曲線行駛或進(jìn)行轉(zhuǎn)向的行為,導(dǎo)致線性插補(bǔ)效果較差.第二類是基于歷史軌跡數(shù)據(jù)的路徑推理填補(bǔ)法,該方法首先需要基于歷史軌跡數(shù)據(jù)生成可路由圖,然后考慮圖中點(diǎn)之間的轉(zhuǎn)移概率進(jìn)行路徑推理.文獻(xiàn)[11]提出了一種最大概率乘積算法,基于熱門度指標(biāo),以廣度優(yōu)先的方式從構(gòu)建的傳輸網(wǎng)絡(luò)中發(fā)現(xiàn)最熱門的路徑.文獻(xiàn)[12]將地理空間網(wǎng)格化,首先使用具有不確定性的歷史軌跡數(shù)據(jù)構(gòu)建可路由圖,然后根據(jù)路由算法在圖中搜索兩點(diǎn)之間的Top-k路徑(一系列點(diǎn)的位置).文獻(xiàn)[13]提出了一種基于錨點(diǎn)的校準(zhǔn)系統(tǒng),將軌跡與一組固定的錨點(diǎn)對齊以完成軌跡恢復(fù).當(dāng)待處理的軌跡段位于信號薄弱區(qū)域時(shí),該區(qū)域內(nèi)歷史軌跡數(shù)據(jù)非常稀疏,無法支持可路由圖的生成和轉(zhuǎn)移概率的計(jì)算.第三類是基于歷史軌跡數(shù)據(jù)的位置預(yù)測填補(bǔ)法,該方法采用循環(huán)神經(jīng)網(wǎng)絡(luò)等深度學(xué)習(xí)模型對軌跡進(jìn)行建模并使用歷史軌跡數(shù)據(jù)進(jìn)行訓(xùn)練,從而預(yù)測缺失的軌跡點(diǎn)位置.文獻(xiàn)[14]設(shè)計(jì)了一種帶有卡爾曼濾波器校準(zhǔn)組件的子序列到序列模型,從不規(guī)則的低采樣模型中恢復(fù)高采樣率軌跡.該方法可以捕捉到軌跡序列中的時(shí)空依賴關(guān)系,但當(dāng)訓(xùn)練的歷史軌跡數(shù)據(jù)中存在大量缺失時(shí)預(yù)測效果存在波動.

2 概念定義及整體框架

2.1 概念定義

定義 2給定軌跡點(diǎn)pi與預(yù)設(shè)的距離閾值Ndis,以及軌跡點(diǎn)集合P,pi和pj之間的距離由Gdis(pi,pj)(實(shí)際地面距離)表示,pi的近鄰點(diǎn)定義為

定義 3給定軌跡T{p1,p2,···,pn},長采樣間隔軌跡段Li{pi,pi+1}滿足以下兩個(gè)條件:

(1)Gdis(pi,pi+1)＞(1+α2)×adis,其中adis表示連續(xù)軌跡點(diǎn)間的平均采樣距離間隔,α2為距離約束的調(diào)節(jié)參數(shù),據(jù)實(shí)際數(shù)據(jù)分析設(shè)為0.5;

如圖2 所示,橙色軌跡段是軌跡點(diǎn)對(ps,pe)的一條相似子軌跡.

2.2 整體框架

本文框架包括6 個(gè)部分: GeoHash 網(wǎng)格索引構(gòu)建、異常軌跡點(diǎn)的消除、徘徊軌跡段的消除、違章軌跡段的消除、漂移軌跡段的校準(zhǔn)和缺失軌跡段的恢復(fù),如圖3 所示.

圖3 整體框架圖Fig.3 Global architecture

針對上述提到的非機(jī)動車騎行軌跡存在的數(shù)據(jù)異常與缺失問題,本文使用如圖3 所示的策略.

第一,使用基于GeoHash 的單元?jiǎng)澐址椒▽⒌唾|(zhì)量區(qū)域分割成固定大小的網(wǎng)格,并對軌跡點(diǎn)建立GeoHash 網(wǎng)格索引以加速后續(xù)基于近鄰范圍的異常檢測與數(shù)據(jù)恢復(fù);第二,采用基于近鄰軌跡點(diǎn)的主方向與速度的軌跡噪聲檢測方法,識別轉(zhuǎn)向異常點(diǎn)和速度異常點(diǎn)并予以消除;第三,根據(jù)方向多變和低速特征,基于網(wǎng)格采用廣度優(yōu)先搜索(breadth first search,BFS)方法識別與較大范圍時(shí)空近鄰不同的徘徊軌跡段并消除;第四,使用核密度估計(jì)和基于網(wǎng)格的近鄰軌跡分析,檢測違章行駛軌跡段并消除;第五,利用漂移軌跡段的采樣間隔與歷史軌跡平均采樣間隔的差異,以及漂移軌跡段與空間近鄰軌跡移動行為的不一致性檢測漂移軌跡段,利用LCSS 和Fréchet 距離計(jì)算提取最相似近鄰軌跡段以替換漂移軌跡段實(shí)現(xiàn)校準(zhǔn);第六,根據(jù)近鄰軌跡點(diǎn)間的平均采樣間隔提取具有較長時(shí)間(或距離)間隔的軌跡線段,使用增量聚類方法對其進(jìn)行聚類以識別缺失軌跡所在區(qū)域,基于該區(qū)域的歷史軌跡數(shù)據(jù)獲取相似子軌跡,再采用最小距離和的擬合方法實(shí)現(xiàn)對缺失軌跡的恢復(fù).

3 面向騎行地圖推斷的軌跡數(shù)據(jù)質(zhì)量提升方法

3.1 GeoHash 網(wǎng)格索引構(gòu)建

面向地圖推斷應(yīng)用中所存在的異常軌跡大多數(shù)與其周圍近鄰軌跡數(shù)據(jù)存在差異,在進(jìn)行異常檢測時(shí),需要提取其周圍軌跡數(shù)據(jù)信息,以得到正常軌跡的相關(guān)特征并進(jìn)行異常判定,由于軌跡數(shù)據(jù)的海量性,如果直接對全量軌跡數(shù)據(jù)進(jìn)行搜索就會耗費(fèi)大量時(shí)間.為了解決該問題,本文使用GeoHash 網(wǎng)格索引,以網(wǎng)格的方法對軌跡數(shù)據(jù)信息進(jìn)行索引,用于提升后續(xù)異常數(shù)據(jù)檢測的近鄰軌跡搜索效率.

首先使用基于GeoHash 的網(wǎng)格單元?jiǎng)澐址椒▽?shù)據(jù)異常區(qū)域分割成固定大小的網(wǎng)格.然后對騎行軌跡數(shù)據(jù)中軌跡點(diǎn)的方向、相鄰軌跡點(diǎn)間的方向變化與速度變化、相鄰軌跡點(diǎn)之間采樣時(shí)間差進(jìn)行計(jì)算.最后在此基礎(chǔ)上結(jié)合軌跡點(diǎn)所處的行程狀態(tài)(如“騎行中”“到達(dá)騎行終點(diǎn)附近”)信息形成軌跡點(diǎn)的衍生屬性,對軌跡數(shù)據(jù)建立GeoHash 網(wǎng)格索引.

GeoHash 是一種地理編碼算法,可以在時(shí)間復(fù)雜度O(1)(O為時(shí)間復(fù)雜度符號)下將GPS 坐標(biāo)按照不同的編碼長度定位到不同大小的地理網(wǎng)格單元中,同時(shí),對于不同GPS 坐標(biāo)所對應(yīng)的編碼公共前綴長度越長,其所在位置則越近.考慮到國家標(biāo)準(zhǔn)的車道寬度為3.50 m 至3.75 m,設(shè)置對應(yīng)GeoHash編碼長度為9(即對應(yīng)網(wǎng)格單元的長、寬均為4.80 m).

3.2 異常軌跡點(diǎn)消除

由于受采樣設(shè)備和信號的影響,原始軌跡中存在偏離其周圍軌跡的異常軌跡點(diǎn),表現(xiàn)為與周圍近鄰軌跡點(diǎn)在方向和速度上存在較大差異.前者稱為轉(zhuǎn)向異常點(diǎn),后者稱為速度異常點(diǎn).異常軌跡點(diǎn)使軌跡產(chǎn)生較大波動,甚至產(chǎn)生錯(cuò)誤的道路拓?fù)湫畔?不利于騎行地圖的準(zhǔn)確推斷,應(yīng)將其視為噪聲并消除.

考慮異常軌跡點(diǎn)與其周圍軌跡在方向和速度上的差異,采用基于近鄰軌跡點(diǎn)的主方向與速度的軌跡噪聲檢測方法,識別轉(zhuǎn)向異常點(diǎn)和速度異常點(diǎn)并予以消除,方法具體如下.

第一,統(tǒng)計(jì)相鄰軌跡點(diǎn)間的采樣時(shí)間間隔,以平均采樣時(shí)間間隔αtime作為軌跡段劃分的閾值對軌跡分段以得到時(shí)間采樣間隔正常的軌跡;第二,按照國家標(biāo)準(zhǔn)非機(jī)動車的上限速度tspeed為25 km·h–1,以上限速度為閾值檢測速度異常點(diǎn)并對其進(jìn)行刪除的軌跡點(diǎn)以消除速度異常點(diǎn);第三,基于少數(shù)轉(zhuǎn)向異常點(diǎn)與其大多數(shù)近鄰軌跡點(diǎn)的方向差異特性,先用GeoHash 網(wǎng)格查找待檢測軌跡點(diǎn)的近鄰;第四,對近鄰點(diǎn)按照方向?qū)⑵鋭澐譃? 個(gè)不同方向(與正北相差角度為(i0,1,2,···,7)的8 個(gè)方向)類;第五,考慮道路有單向/雙向道,如待測軌跡點(diǎn)方向不屬于軌跡點(diǎn)數(shù)量最多的兩個(gè)方向,則將其視為轉(zhuǎn)向異常點(diǎn)予以刪除.近鄰點(diǎn)的方向代表了待檢測軌跡點(diǎn)周圍大多數(shù)軌跡點(diǎn)的正常方向,如果待測軌跡點(diǎn)方向與之相差較大,則認(rèn)為其方向存在異常,考慮到國家標(biāo)準(zhǔn)的車道寬度為3.50 m 至3.75 m,設(shè)置比車道略寬的距離閾值,可取tdis4.00 m .

3.3 徘徊軌跡段消除

由于非機(jī)動車騎行場景的特殊性,騎行者常常進(jìn)入一些非道路區(qū)域,例如居民區(qū)、商圈等.在這些區(qū)域中,騎行者往往不能直接快速到達(dá)目的地,而是在小區(qū)域范圍內(nèi)花費(fèi)大量時(shí)間騎行.同時(shí)由于軌跡采樣本身存在的隨機(jī)誤差,所采樣的軌跡會在其真實(shí)軌跡附近產(chǎn)生隨機(jī)分布,軌跡會呈現(xiàn)出隨機(jī)徘徊的狀態(tài),這樣的軌跡段不僅無法呈現(xiàn)出道路的拓?fù)浣Y(jié)構(gòu),其存在更會影響附近區(qū)域路口和道路的識別,并影響騎行地圖的最終構(gòu)建,需要對徘徊軌跡段識別并消除.

如圖1(b)所示,非機(jī)動車騎行軌跡的徘徊軌跡段位于騎行行程所涉及的非道路區(qū)域,該類區(qū)域是大量狀態(tài)為“到達(dá)騎行終點(diǎn)附近”的軌跡點(diǎn)所在區(qū)域,同時(shí),徘徊軌跡段常伴有方向多變且速度相對于正常騎行軌跡速度較小等行為.

第一,根據(jù)這些特性,基于廣度優(yōu)先搜索(BFS),搜索待檢測軌跡點(diǎn)的近鄰點(diǎn),考慮到非道路區(qū)域相較于道路區(qū)域的軌跡稀疏特性,這里設(shè)置近鄰點(diǎn)距離閾值Ndis=8 m 以提取更多的近鄰軌跡點(diǎn);第二,基于得到的近鄰點(diǎn),統(tǒng)計(jì)其中狀態(tài)為“到達(dá)騎行終點(diǎn)附近”的軌跡點(diǎn)的數(shù)量在近鄰軌跡點(diǎn)中的占比,當(dāng)占比超過狀態(tài)為“騎行中”軌跡點(diǎn)數(shù)量的在近鄰軌跡點(diǎn)鐘的占比時(shí),將該區(qū)域視為與非機(jī)動車騎行相關(guān)的熱門非道路區(qū)域,如果一段軌跡連續(xù)多個(gè)軌跡點(diǎn)位于熱門非道路區(qū)域,將其視為候選徘徊軌跡段;第三,統(tǒng)計(jì)候選徘徊軌跡段內(nèi)軌跡點(diǎn)的方向并將其劃分到8 個(gè)方向類;第四,考慮到道路騎行軌跡可能偶發(fā)轉(zhuǎn)向行為以及轉(zhuǎn)向前后騎行方向不變的特性,如果候選徘徊軌跡段內(nèi)軌跡點(diǎn)的方向類超過兩個(gè),且軌跡段內(nèi)部由點(diǎn)連接成的線段存在空間交叉的情況,同時(shí)該候選徘徊軌跡段內(nèi)軌跡點(diǎn)的平均速度小于在道路騎行時(shí)的平均速度(這里設(shè)置平均速度αspeed4.0 m·s-1),就判斷該候選徘徊軌跡段為徘徊軌跡段予以刪除.

3.4 違章軌跡段消除

如圖4(a)所示,黃色軌跡是上海市延安高架路附近的非機(jī)動車騎行軌跡,紅色軌跡是一條在機(jī)動車區(qū)域內(nèi)行駛的騎行軌跡,此類軌跡將會對合規(guī)的騎行地圖構(gòu)建、路徑規(guī)劃等應(yīng)用造成精度損失.鑒于網(wǎng)格下軌跡點(diǎn)密度的稀疏性會影響機(jī)動車的車行區(qū)域的平滑性,利用核密度估計(jì)來計(jì)算各網(wǎng)格單元內(nèi)的騎行軌跡與(汽車)車行軌跡密度,根據(jù)車行區(qū)域內(nèi)軌跡密度應(yīng)顯著大于騎行軌跡密度的特性,判定其屬于非機(jī)動車限行區(qū)域的網(wǎng)格單元.

圖4 非機(jī)動車限行區(qū)域軌跡的消除Fig.4 Elimination of trajectories in non-motor vehicle restricted areas

基于上述步驟識別的限行區(qū)域網(wǎng)格單元,對騎行軌跡進(jìn)行遍歷,當(dāng)相鄰軌跡點(diǎn)連接形成線段覆蓋的限行區(qū)域網(wǎng)格單元的占比超過閾值tprop(設(shè)置tprop0.1 以保證限行區(qū)域內(nèi)騎行、車行軌跡的差異顯著性),判斷該線段為異常軌跡段;當(dāng)異常軌跡段存在連續(xù)軌跡點(diǎn)間長度超過距離閾值dlen(這里,以時(shí)間平均采樣間隔與騎行限速的乘積設(shè)置dlen84 m)時(shí),判定其為異常行駛軌跡段并消除,效果如圖4(b)—(c)所示.

用戶騎行非機(jī)動車時(shí)在前往目的地過程中由于抄近道等原因,存在著逆向行駛和違規(guī)轉(zhuǎn)向(如橫穿馬路)的行為,這些行為本身并不符合道路交通法則,對騎行地圖的構(gòu)建會產(chǎn)生較大誤差.

用戶騎行非機(jī)動車時(shí)由于抄近道具有逆向行駛和違規(guī)轉(zhuǎn)向(如橫穿馬路)行為.如圖5(a)所示,藍(lán)色軌跡與其所在道路(黑色箭頭標(biāo)注)方向相反,該軌跡為逆行軌跡,紫色軌跡區(qū)域存在違規(guī)轉(zhuǎn)向行為,表現(xiàn)為在馬路中間穿行,屬于違規(guī)轉(zhuǎn)向,具體違章軌跡段消除的方法如下.

圖5 違章行駛軌跡段示例Fig.5 Illustration of illegal driving

第一,考慮到逆行和違規(guī)轉(zhuǎn)向軌跡段與其大多數(shù)近鄰軌跡點(diǎn)在方向以及方向變化上均存在較大差異,故先通過范圍提取待檢測軌跡點(diǎn)的近鄰點(diǎn),并將近鄰點(diǎn)根據(jù)方向與方向變化劃分到8 個(gè)方向類中.第二,當(dāng)近鄰點(diǎn)的方向大致相同時(shí)(以大多數(shù)近鄰點(diǎn)的方向?yàn)橹鞣较?設(shè)置不屬于主方向的方向占比閾值tprop0.1),判定該軌跡點(diǎn)所處道路為單向道.第三,若當(dāng)前軌跡點(diǎn)方向與主方向相反(即與主方向相差180°),判定該軌跡點(diǎn)存在逆行行為.若連續(xù)軌跡點(diǎn)序列中不存在逆行行為的軌跡點(diǎn)占比低于設(shè)定的閾值(tprop0.1),則判定該軌跡點(diǎn)序列為逆行軌跡段應(yīng)予以消除,如圖5(b)所示.第四,當(dāng)軌跡點(diǎn)方向不屬于近鄰點(diǎn)主方向,且其方向變化不同于其近鄰軌跡點(diǎn)的方向變化時(shí)(取不屬于主方向變化的占比閾值tprop0.1),判定該點(diǎn)有違規(guī)轉(zhuǎn)向行為.第五,當(dāng)連續(xù)軌跡點(diǎn)序列的方向?qū)儆谥鞣较虻恼急鹊陀陂撝?tprop0.1)且存在違規(guī)轉(zhuǎn)向行為的軌跡點(diǎn),判定該軌跡點(diǎn)序列存在違規(guī)轉(zhuǎn)向行為應(yīng)予以消除.

3.5 漂移軌跡段校準(zhǔn)

圖6 軌跡校準(zhǔn)與恢復(fù)Fig.6 Calibration and recovery for trajectory

3.6 缺失軌跡段恢復(fù)

由于部分區(qū)域定位信號弱,存在連續(xù)軌跡點(diǎn)間的時(shí)間遠(yuǎn)長于平均采樣時(shí)間間隔和距離遠(yuǎn)大于平均采樣距離間隔的情況,稱為較長采樣間隔線段.因此,首先檢測發(fā)現(xiàn)較長采樣間隔線段,然后對其進(jìn)行增量聚類以定位信號弱的區(qū)域.

先維護(hù)一個(gè)較長采樣間隔線段簇的集合,當(dāng)檢測到一條較長采樣間隔線段Li時(shí),通過計(jì)算Li與現(xiàn)有較長采樣間隔線段簇的代表軌跡之間的距離,搜索距離Li最近的較長采樣間隔線段簇(滿足Li與其的距離小于指定閾值β),將Li插入該簇并重新計(jì)算所在簇的代表軌跡.如未找到,將Li單獨(dú)作為一個(gè)簇,β的值按照公式 m in{,β}計(jì)算得到,其中l(wèi)len表示較長采樣間隔線段的長度.較長采樣間隔線段簇Ck的代表軌跡的起點(diǎn)lcs和終點(diǎn)lce由以下公式計(jì)算得到,其中為Li的起點(diǎn)，為Li的終點(diǎn).

線段間的距離采用豪斯多夫距離方法,該方法結(jié)合平行距離、垂直距離和角距離等對線段之間的距離進(jìn)行評測.當(dāng)長采樣間隔軌跡段簇的數(shù)量超過內(nèi)存所能保存的最大數(shù)量m時(shí),合并兩個(gè)距離最近的簇.當(dāng)軌跡簇Ck的線段數(shù)Nnum大于預(yù)設(shè)閾值tnum(tnum10)時(shí),將該簇所在區(qū)域視為弱信號區(qū)域.針對弱信號區(qū)域內(nèi)的缺失軌跡,以位于這些區(qū)域的長采樣間隔軌跡段的兩個(gè)端點(diǎn)(Sst,Eed)為查詢點(diǎn),從歷史軌跡中提取相似軌跡段集合.分別計(jì)算相似軌跡段集合中軌跡段之間的Fréchet 距離,找出與其相似軌跡段之間距離之和最小的軌跡段,將其作為參考軌跡段.

考慮到基于距離計(jì)算得到的參考軌跡段具有不穩(wěn)定性,使用參考軌跡段附近的軌跡點(diǎn)對參考軌跡段進(jìn)行校準(zhǔn),具體方法為: 首先將Sst視為代表軌跡點(diǎn)rps;再依次以參考軌跡段的軌跡點(diǎn)pi+k(0 ≤k≤m)為圓心,以道路寬度d為半徑,找出該區(qū)域內(nèi)的所有軌跡點(diǎn),并在這些軌跡點(diǎn)中篩選出與軌跡點(diǎn)pi+k的方向夾角小于閾值tangle的軌跡點(diǎn)集合Sp(tangle設(shè)置為10°),將Sp中軌跡點(diǎn)的平均位置點(diǎn)作為這些軌跡點(diǎn)的代表軌跡點(diǎn)pi+k.

為保證代表軌跡的平滑性,若連續(xù)兩個(gè)代表軌跡點(diǎn)間的距離小于平滑度閾值tsm(實(shí)驗(yàn)中設(shè)為30 m),跳過當(dāng)前代表軌跡點(diǎn)遍歷.直到Eed與當(dāng)前軌跡點(diǎn)之間的距離小于平滑度閾值tsm,將Eed作為最后一個(gè)代表軌跡點(diǎn)pe,以完成代表軌跡段地提取,并使用該代表軌跡段替換與之對應(yīng)的較長采樣間隔線段,當(dāng)代表軌跡段替換完成后即完成缺失軌跡段的恢復(fù),如圖6(b)所示.

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

為了驗(yàn)證框架的有效性,本文基于真實(shí)軌跡數(shù)據(jù)集進(jìn)行對比實(shí)驗(yàn)和消融實(shí)驗(yàn).通過與各種路口檢測和道路生成中的預(yù)處理方法進(jìn)行對比,并分析不同步驟帶來對應(yīng)路口檢測和道路生成效果的提升,觀察路口檢測和道路生成在本文方法基礎(chǔ)上路口檢測準(zhǔn)確性與道路生成質(zhì)量上的效果差異來驗(yàn)證本文框架的有效性.

4.1 實(shí)驗(yàn)數(shù)據(jù)集

騎行軌跡數(shù)據(jù): 本文使用2020 年06 月到2021 年06 月的上海真實(shí)非機(jī)動車騎行軌跡,包含約80 萬個(gè)GPS 坐標(biāo)點(diǎn),1.6 萬條軌跡.

車行軌跡數(shù)據(jù): 本文使用2020 年06 月01 日的上海真實(shí)車行軌跡數(shù)據(jù),包含約360 萬個(gè)GPS 坐標(biāo)點(diǎn),1 萬條軌跡.

路網(wǎng)數(shù)據(jù): 本文使用上海市2020 年的OSM(openstreetmap)騎行路網(wǎng)數(shù)據(jù).

4.2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)時(shí)使用的Python 版本為 3.7.3,服務(wù)器操作系統(tǒng)為 CentOS Linux release 7.2.1511,硬件環(huán)境為 48 核Intel(R)Xeon(R)CPU E5-2670 v3 @ 2.30 GHz,內(nèi)存125 GB.

4.3 評價(jià)標(biāo)準(zhǔn)

為定量評價(jià)本文框架對地圖推斷算法的有效性,將地圖推斷算法得到的結(jié)果與真實(shí)路網(wǎng)數(shù)據(jù)進(jìn)行比較.文獻(xiàn)[15]將地圖推斷算法分為道路提取[16]、交叉鏈接[6,17-18]和增量分支[7]3 類,在本實(shí)驗(yàn)中將基于這3 類方法進(jìn)行定量評估,根據(jù)不同的地圖推斷原理,實(shí)驗(yàn)主要涉及路口檢測和道路生成兩部分,其中交叉鏈接方法的路口檢測較為重要,而道路提取和增量分支工作更多體現(xiàn)在道路生成上,相關(guān)評價(jià)標(biāo)準(zhǔn)如下.

(1)路口檢測: 使用精確率nP、召回率nR、F1分?jǐn)?shù)作為評估標(biāo)準(zhǔn),其中真實(shí)位置從OSM 路網(wǎng)數(shù)據(jù)中獲得,Ltru表示真實(shí)路口數(shù)量,Ldet表示檢測到的路口數(shù)量,Lcor表示正確識別的路口數(shù)量.F1值越高表示性能越好,精確率nP、召回率nR、F1分?jǐn)?shù)分別定義為

(2)道路生成: 將生成的道路與真實(shí)的OSM 路網(wǎng)進(jìn)行地圖匹配,使用精度指標(biāo)準(zhǔn)確的數(shù)量AN,準(zhǔn)確的長度AL以及正確匹配百分比CMP來評估實(shí)驗(yàn)效果.Cwnu表示正確匹配的道路數(shù)量,Gwnu表示生成的道路數(shù),Cwle表示正確匹配的道路長度,Gwle表示生成的道路長度,Cpnu表示正確匹配的樣本點(diǎn)數(shù),Gpnu表示需要匹配的樣本點(diǎn)數(shù),其中

4.4 對比算法

為了說明本文框架的有效性,將其搭建在現(xiàn)有的地圖推斷算法上進(jìn)行比較.

(1)CITT[4](a three-phase calibration framework for road intersection topology usingtrajectories):由軌跡數(shù)據(jù)質(zhì)量提升、核心區(qū)檢測和影響區(qū)內(nèi)拓?fù)浣Y(jié)構(gòu)校準(zhǔn)構(gòu)成的路口校準(zhǔn)框架.

(2)Huang19[17]: 通過將主路口與次路口分別檢測再合并的方式獲取路口信息,使用DBSCAN(density-based spatial clustering of applications with noise)方法對收斂點(diǎn)和約束收斂點(diǎn)聚類以提取路口位置.

(3)SLC[16](spatial-linear clustering): 結(jié)合路網(wǎng)線性特性,使用空間線性聚類算法生成空間線性簇,利用基于幾何的方法提法空間線性簇的代表軌跡.

(4)Cao09[7]: 引入吸引力模型調(diào)整軌跡點(diǎn)的位置,并根據(jù)軌跡點(diǎn)與圖節(jié)點(diǎn)的距離、方向差異依次將軌跡點(diǎn)合并或者插入已有圖中.

算法(1)、(2)用于路口推斷質(zhì)量的評估,算法(3)、(4)用于道路生成質(zhì)量的評估.

4.5 實(shí)驗(yàn)效果

本文基于上述真實(shí)非機(jī)動車騎行軌跡數(shù)據(jù)、實(shí)驗(yàn)環(huán)境和評價(jià)標(biāo)準(zhǔn)進(jìn)行數(shù)據(jù)質(zhì)量提升實(shí)驗(yàn),圖7(a)為沒有進(jìn)行數(shù)據(jù)質(zhì)量提升之前的非機(jī)動車騎行軌跡可視化效果圖,可以看出原始軌跡存在大量的軌跡漂移等低質(zhì)量現(xiàn)象.通過本文的非機(jī)動車騎行軌跡的數(shù)據(jù)質(zhì)量提升方法對其進(jìn)行數(shù)據(jù)質(zhì)量提升后得到的效果圖來看,軌跡質(zhì)量得到了顯著提升,如圖7(b)所示.

圖7 軌跡質(zhì)量提升例子Fig.7 Example of trajectory quality improving

為了證明本文方法對騎行地圖推斷相關(guān)應(yīng)用的提升,本文基于公開的騎行路網(wǎng)和現(xiàn)有地圖推斷應(yīng)用的預(yù)處理方法進(jìn)行路口發(fā)現(xiàn)和路網(wǎng)生成的評估實(shí)驗(yàn).選取的路口發(fā)現(xiàn)方法包括CITT 和Huang19,而選取的路網(wǎng)生成方法包括SLC 和Cao09.對于路口發(fā)現(xiàn),所選取的進(jìn)行量化評價(jià)的指標(biāo)包括精確率、召回率和F1.對于路網(wǎng)生成,選取的進(jìn)行量化評價(jià)的指標(biāo)包括CMP、AL和AN,同時(shí)對實(shí)驗(yàn)結(jié)果進(jìn)行了可視化.

4.5.1 基于路口發(fā)現(xiàn)的數(shù)據(jù)質(zhì)量提升評估

表1 為基于所選定的路口發(fā)現(xiàn)方法,并且分別在原始預(yù)處理和本文數(shù)據(jù)質(zhì)量提升基礎(chǔ)上進(jìn)行路口發(fā)現(xiàn)實(shí)驗(yàn)的數(shù)據(jù)結(jié)果,其中CITT 和Huang19 對應(yīng)基于原始預(yù)處理方法的結(jié)果,CITT+proposed和Huang19+proposed 對應(yīng)基于本文數(shù)據(jù)質(zhì)量提升方法的結(jié)果.

表1 路口發(fā)現(xiàn)的數(shù)據(jù)質(zhì)量提升對比實(shí)驗(yàn)結(jié)果Tab.1 Quantitative evaluation metrics for intersection finding

表1 所示的實(shí)驗(yàn)結(jié)果可以看出,采用本文數(shù)據(jù)質(zhì)量提升方法得到的軌跡數(shù)據(jù)進(jìn)行路口發(fā)現(xiàn)在精確率、召回率以及F1上相比原先的預(yù)處理方法有一定程度的提升.圖8(a)為原始CITT 預(yù)處理方法后的路口發(fā)現(xiàn)效果圖,圖8(b)為基于本文數(shù)據(jù)質(zhì)量提升方法后使用CITT 方法的路口發(fā)現(xiàn)效果圖,熱門區(qū)域內(nèi)的徘徊軌跡被明顯消除,圖8(c)為原始Huang19 預(yù)處理方法后的路口發(fā)現(xiàn)效果圖,圖8(d)為同一區(qū)域的本文數(shù)據(jù)質(zhì)量提升后使用Huang19 方法的路口發(fā)現(xiàn)效果圖,噪聲軌跡被大量消除.

圖8 路口發(fā)現(xiàn)提升對比Fig.8 Example of road generation improving

徘徊軌跡段使得非道路區(qū)域內(nèi)存在著大量不屬于道路范圍的軌跡,并且在密度、方向等因素上對真實(shí)路口的檢測特征存在較大影響,使CITT 方法檢測到更多的不在道路上的小路口同時(shí)對真實(shí)路口的檢測準(zhǔn)確性下降,數(shù)據(jù)質(zhì)量提升前后使用Huang 方法進(jìn)行路口發(fā)現(xiàn)的可視化效果相差較大,其原因?yàn)镠uang19 方法利用道路上的轉(zhuǎn)向點(diǎn)進(jìn)行聚類,由于徘徊軌跡段的存在,會存在大量的非道路區(qū)域轉(zhuǎn)向點(diǎn),影響路口的識別.

表2 為數(shù)據(jù)質(zhì)量提升基于路口發(fā)現(xiàn)方法的消融實(shí)驗(yàn),從表2 可知數(shù)據(jù)質(zhì)量提升的每一步驟都提升了路口發(fā)現(xiàn)的效果,其中徘徊軌跡段的消除對路口發(fā)現(xiàn)的影響最大,非道路區(qū)域中存在的大量徘徊軌跡段,其方向和速度等特征會影響到路口的準(zhǔn)確發(fā)現(xiàn),使得路口位置偏移或得到錯(cuò)誤路口,異常軌跡點(diǎn)消除和違章軌跡段消除可以減少道路中間的異常點(diǎn)對路口發(fā)現(xiàn)準(zhǔn)確率的影響,減少將道路中間位置識別為路口的概率,漂移軌跡段校準(zhǔn)可以將軌跡校準(zhǔn)到其真實(shí)道路上以識別路口真實(shí)位置,缺失軌跡段恢復(fù)則可以提升軌跡稀疏區(qū)域的路口識別效果.

表2 路口發(fā)現(xiàn)的數(shù)據(jù)質(zhì)量提升消融實(shí)驗(yàn)結(jié)果Tab.2 Ablation experiment for intersection finding

4.5.2 基于路網(wǎng)生成的數(shù)據(jù)質(zhì)量提升評估

表3 為基于選定的道路生成方法,并且分別在原始預(yù)處理和本文數(shù)據(jù)質(zhì)量提升基礎(chǔ)上進(jìn)行道路生成實(shí)驗(yàn)的數(shù)據(jù)結(jié)果,其中SLC 和Cao09 對應(yīng)基于原始預(yù)處理方法的道路生成結(jié)果,SLC+proposed和Cao09+proposed 對應(yīng)基于本文數(shù)據(jù)質(zhì)量提升方法的道路生成結(jié)果.

表3 道路生成的數(shù)據(jù)質(zhì)量提升對比實(shí)驗(yàn)結(jié)果Tab.3 Quantitative evaluation results of road generation

從表3 所示的實(shí)驗(yàn)結(jié)果可以看出,采用本文數(shù)據(jù)質(zhì)量提升方法的數(shù)據(jù)進(jìn)行道路生成時(shí)在CMP、AL、AN等量化指標(biāo)上都有著較為顯著的提升.圖9(a)為原始的SLC 預(yù)處理后的道路生成效果圖,如圖9(b)所示為本文數(shù)據(jù)質(zhì)量提升后的使用SLC 方法進(jìn)行道路生成的效果圖,生成的路網(wǎng)缺失情況減少且熱門區(qū)域內(nèi)的徘徊軌跡段不影響路網(wǎng)生成,如圖9(c)所示為原始的Cao09 預(yù)處理后的道路生成效果圖,如圖9(d)所示為本文數(shù)據(jù)質(zhì)量提升后使用Cao09 方法進(jìn)行道路生成的效果,所生成的路網(wǎng)冗余情況明顯減少.

圖9 道路生成提升對比Fig.9 Comparison of road generation improving

異常軌跡段使得原始軌跡數(shù)據(jù)中存在大量不適合用于道路生成的軌跡,它們或者不在道路范圍內(nèi),或者產(chǎn)生了錯(cuò)誤的道路連接信息.漂移軌跡段和缺失軌跡段則使得道路缺失了連接信息,無法完成道路的生成,從而本文所提出的數(shù)據(jù)質(zhì)量提升方法可以有效提升道路生成的效果.

表4 為道路生成的數(shù)據(jù)質(zhì)量提升消融實(shí)驗(yàn)結(jié)果,其中Step1 為異常軌跡點(diǎn)的消除,Step2 為徘徊軌跡段的消除,Step3 為違章軌跡段的消除,Step4 為漂移軌跡段的校準(zhǔn),Step5 為缺失軌跡段的恢復(fù),表4 展示了數(shù)據(jù)質(zhì)量提升方法的不同步驟在道路生成的3 個(gè)評價(jià)指標(biāo)中都得到了提升.其中徘徊軌跡段的消除和違章軌跡段消除對道路生成的影響最大,徘徊軌跡段的消除可以減少非道路區(qū)域中的大量徘徊軌跡,違章軌跡段的消除則可以減少道路區(qū)域的逆行軌跡和大量非騎行區(qū)域的軌跡,這些軌跡質(zhì)量提升步驟最終減少了錯(cuò)誤道路的生成.異常軌跡點(diǎn)的消除可以減少道路上的轉(zhuǎn)向異常點(diǎn)和距離異常點(diǎn).漂移軌跡段校準(zhǔn)步驟可以使得軌跡校準(zhǔn)到其正確道路上,缺失軌跡恢復(fù)步驟可以恢復(fù)信號薄弱區(qū)的軌跡,能有效提升道路生成應(yīng)用的效果.

表4 道路生成的數(shù)據(jù)質(zhì)量提升消融實(shí)驗(yàn)結(jié)果Tab.4 Ablation experiment for road generation

5 結(jié) 論

針對在騎行地圖推斷的應(yīng)用中非機(jī)動車騎行軌跡數(shù)據(jù)存在的大量異常以及定位信息缺失的情況,本文提出了一種面向騎行地圖推斷的軌跡數(shù)據(jù)質(zhì)量提升方法,分別包括GeoHash 網(wǎng)格索引構(gòu)建、異常軌跡點(diǎn)的消除、徘徊軌跡段的消除、違章軌跡段的消除、漂移軌跡段的校準(zhǔn)以及缺失軌跡段的恢復(fù).基于真實(shí)的軌跡數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明,本文所提出的方法在基于非機(jī)動車騎行軌跡的路口發(fā)現(xiàn)和道路生成中對現(xiàn)有方法有著較大的提升效果.考慮到不同場景下的騎行地圖推斷所需騎行軌跡與其對應(yīng)的業(yè)務(wù)相關(guān)性較強(qiáng),在不同應(yīng)用上的數(shù)據(jù)要求存在差異,未來擬考慮增加相關(guān)信息,基于不同騎行地圖應(yīng)用制定針對性的數(shù)據(jù)質(zhì)量提升方法.