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

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

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

0 引 言

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

通過對(duì)真實(shí)非機(jī)動(dòng)車騎行軌跡數(shù)據(jù)的分析與調(diào)研,非機(jī)動(dòng)車騎行軌跡中除了軌跡數(shù)據(jù)普遍存在的帶有方向、速度噪聲的異常軌跡點(diǎn)以外,還存在熱門騎行區(qū)域的徘徊軌跡段、帶有違規(guī)轉(zhuǎn)向與逆向騎行的違章軌跡段、信號(hào)漂移軌跡段以及信號(hào)缺失軌跡段等數(shù)據(jù)異常.徘徊軌跡段常見于非道路區(qū)域,伴有方向多變與低速行駛的現(xiàn)象.違章軌跡段則以非轉(zhuǎn)向區(qū)域的轉(zhuǎn)向以及逆行事件呈現(xiàn),它們?yōu)榈缆吠負(fù)涞木珳?zhǔn)提取帶來一定程度的干擾,需要及時(shí)發(fā)現(xiàn)并消除.信號(hào)漂移軌跡段和信號(hào)缺失軌跡段常發(fā)生在信號(hào)薄弱區(qū)域,需要利用歷史軌跡數(shù)據(jù)對(duì)漂移行為進(jìn)行有效識(shí)別以及基于稀疏數(shù)據(jù)對(duì)缺失軌跡進(jìn)行恢復(fù).非機(jī)動(dòng)車騎行軌跡數(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)地下停車場(chǎng)(以紅色圓圈標(biāo)注).該部分軌跡段不屬于在道路上的騎行狀態(tài),對(duì)于地圖推斷無意義.

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 軌跡去噪

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

1.2 軌跡恢復(fù)

目前對(duì)于缺失軌跡數(shù)據(jù)的處理方式主要可以分為以下3 類: 第一類是線性插值法,該方法在起始點(diǎn)和結(jié)束點(diǎn)之間進(jìn)行線性插補(bǔ).文獻(xiàn)[10]通過假設(shè)軌跡是沿直線且均勻移動(dòng),以此來恢復(fù)缺失位置.當(dāng)移動(dòng)對(duì)象沿直線移動(dòng)時(shí),該方法填補(bǔ)效果良好,實(shí)際上移動(dòng)對(duì)象可能存在沿曲線行駛或進(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)對(duì)齊以完成軌跡恢復(fù).當(dāng)待處理的軌跡段位于信號(hào)薄弱區(qū)域時(shí),該區(qū)域內(nèi)歷史軌跡數(shù)據(jù)非常稀疏,無法支持可路由圖的生成和轉(zhuǎn)移概率的計(jì)算.第三類是基于歷史軌跡數(shù)據(jù)的位置預(yù)測(cè)填補(bǔ)法,該方法采用循環(huán)神經(jīng)網(wǎng)絡(luò)等深度學(xué)習(xí)模型對(duì)軌跡進(jìn)行建模并使用歷史軌跡數(shù)據(jù)進(jìn)行訓(xùn)練,從而預(yù)測(cè)缺失的軌跡點(diǎn)位置.文獻(xiàn)[14]設(shè)計(jì)了一種帶有卡爾曼濾波器校準(zhǔn)組件的子序列到序列模型,從不規(guī)則的低采樣模型中恢復(fù)高采樣率軌跡.該方法可以捕捉到軌跡序列中的時(shí)空依賴關(guān)系,但當(dāng)訓(xùn)練的歷史軌跡數(shù)據(jù)中存在大量缺失時(shí)預(yù)測(cè)效果存在波動(dòng).

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},長(zhǎng)采樣間隔軌跡段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)對(duì)(ps,pe)的一條相似子軌跡.

2.2 整體框架

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 徘徊軌跡段消除

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

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

第一,根據(jù)這些特性,基于廣度優(yōu)先搜索(BFS),搜索待檢測(cè)軌跡點(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ī)動(dòng)車騎行相關(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ī)動(dòng)車騎行軌跡,紅色軌跡是一條在機(jī)動(dòng)車區(qū)域內(nèi)行駛的騎行軌跡,此類軌跡將會(huì)對(duì)合規(guī)的騎行地圖構(gòu)建、路徑規(guī)劃等應(yīng)用造成精度損失.鑒于網(wǎng)格下軌跡點(diǎn)密度的稀疏性會(huì)影響機(jī)動(dòng)車的車行區(qū)域的平滑性,利用核密度估計(jì)來計(jì)算各網(wǎng)格單元內(nèi)的騎行軌跡與(汽車)車行軌跡密度,根據(jù)車行區(qū)域內(nèi)軌跡密度應(yīng)顯著大于騎行軌跡密度的特性,判定其屬于非機(jī)動(dòng)車限行區(qū)域的網(wǎng)格單元.

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

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

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

用戶騎行非機(jī)動(dòng)車時(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)在方向以及方向變化上均存在較大差異,故先通過范圍提取待檢測(cè)軌跡點(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ū)域定位信號(hào)弱,存在連續(xù)軌跡點(diǎn)間的時(shí)間遠(yuǎn)長(zhǎng)于平均采樣時(shí)間間隔和距離遠(yuǎn)大于平均采樣距離間隔的情況,稱為較長(zhǎng)采樣間隔線段.因此,首先檢測(cè)發(fā)現(xiàn)較長(zhǎng)采樣間隔線段,然后對(duì)其進(jìn)行增量聚類以定位信號(hào)弱的區(qū)域.

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

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

考慮到基于距離計(jì)算得到的參考軌跡段具有不穩(wěn)定性,使用參考軌跡段附近的軌跡點(diǎn)對(duì)參考軌跡段進(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,以完成代表軌跡段地提取,并使用該代表軌跡段替換與之對(duì)應(yīng)的較長(zhǎng)采樣間隔線段,當(dāng)代表軌跡段替換完成后即完成缺失軌跡段的恢復(fù),如圖6(b)所示.

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

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

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

騎行軌跡數(shù)據(jù): 本文使用2020 年06 月到2021 年06 月的上海真實(shí)非機(jī)動(dòng)車騎行軌跡,包含約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 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

4.4 對(duì)比算法

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

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

(2)Huang19[17]: 通過將主路口與次路口分別檢測(cè)再合并的方式獲取路口信息,使用DBSCAN(density-based spatial clustering of applications with noise)方法對(duì)收斂點(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ì)量的評(píng)估,算法(3)、(4)用于道路生成質(zhì)量的評(píng)估.

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

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

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

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

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

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

表1 路口發(fā)現(xiàn)的數(shù)據(jù)質(zhì)量提升對(duì)比實(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)提升對(duì)比Fig.8 Example of road generation improving

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

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

表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ì)量提升評(píng)估

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

表3 道路生成的數(shù)據(jù)質(zhì)量提升對(duì)比實(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 道路生成提升對(duì)比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è)評(píng)價(jià)指標(biāo)中都得到了提升.其中徘徊軌跡段的消除和違章軌跡段消除對(duì)道路生成的影響最大,徘徊軌跡段的消除可以減少非道路區(qū)域中的大量徘徊軌跡,違章軌跡段的消除則可以減少道路區(qū)域的逆行軌跡和大量非騎行區(qū)域的軌跡,這些軌跡質(zhì)量提升步驟最終減少了錯(cuò)誤道路的生成.異常軌跡點(diǎn)的消除可以減少道路上的轉(zhuǎn)向異常點(diǎn)和距離異常點(diǎn).漂移軌跡段校準(zhǔn)步驟可以使得軌跡校準(zhǔn)到其正確道路上,缺失軌跡恢復(fù)步驟可以恢復(fù)信號(hào)薄弱區(qū)的軌跡,能有效提升道路生成應(yīng)用的效果.

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

5 結(jié) 論

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