面向騎行地圖推斷的軌跡數據質量提升方法

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

（華東師范大學 數據科學與工程學院,上海 200062）

0 引 言

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

通過對真實非機動車騎行軌跡數據的分析與調研,非機動車騎行軌跡中除了軌跡數據普遍存在的帶有方向、速度噪聲的異常軌跡點以外,還存在熱門騎行區域的徘徊軌跡段、帶有違規轉向與逆向騎行的違章軌跡段、信號漂移軌跡段以及信號缺失軌跡段等數據異常.徘徊軌跡段常見于非道路區域,伴有方向多變與低速行駛的現象.違章軌跡段則以非轉向區域的轉向以及逆行事件呈現,它們為道路拓撲的精準提取帶來一定程度的干擾,需要及時發現并消除.信號漂移軌跡段和信號缺失軌跡段常發生在信號薄弱區域,需要利用歷史軌跡數據對漂移行為進行有效識別以及基于稀疏數據對缺失軌跡進行恢復.非機動車騎行軌跡數據存在的質量問題具體如下.

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

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

(3)違章行駛軌跡段: 非機動車在行駛過程出現違規騎行行為,如逆向行駛、在非機動車限行道路上行駛、禁止轉向區域的轉向等,如圖1(c)所示(以紫色線段標注).

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

(5)軌跡段漂移: 當經過高架、隧道等區域時,GPS(global positioning system)信號無法準確定位,移動設備自帶的慣導系統根據連續測得的運動方向和加速度推算車輛后續位置,即相對位置.當后續坐標系轉換不恰當時,會出現整段漂移的情況,如圖1(e)所示.

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

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

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

(3)本文使用真實軌跡數據,以非機動車軌跡的后續地圖推斷為標準,通過與現有軌跡數據質量提升方法進行對比實驗,驗證了本文所提出的方法能有效改進非機動車軌跡數據的質量,并且較大提升了后續的地圖構建效果.

1 相關工作

1.1 軌跡去噪

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

1.2 軌跡恢復

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

2 概念定義及整體框架

2.1 概念定義

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

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

(1)Gdis(pi,pi+1)＞(1+α2)×adis,其中adis表示連續軌跡點間的平均采樣距離間隔,α2為距離約束的調節參數,據實際數據分析設為0.5;

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

2.2 整體框架

本文框架包括6 個部分: GeoHash 網格索引構建、異常軌跡點的消除、徘徊軌跡段的消除、違章軌跡段的消除、漂移軌跡段的校準和缺失軌跡段的恢復,如圖3 所示.

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

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

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

3 面向騎行地圖推斷的軌跡數據質量提升方法

3.1 GeoHash 網格索引構建

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

首先使用基于GeoHash 的網格單元劃分方法將數據異常區域分割成固定大小的網格.然后對騎行軌跡數據中軌跡點的方向、相鄰軌跡點間的方向變化與速度變化、相鄰軌跡點之間采樣時間差進行計算.最后在此基礎上結合軌跡點所處的行程狀態(如“騎行中”“到達騎行終點附近”)信息形成軌跡點的衍生屬性,對軌跡數據建立GeoHash 網格索引.

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

3.2 異常軌跡點消除

由于受采樣設備和信號的影響,原始軌跡中存在偏離其周圍軌跡的異常軌跡點,表現為與周圍近鄰軌跡點在方向和速度上存在較大差異.前者稱為轉向異常點,后者稱為速度異常點.異常軌跡點使軌跡產生較大波動,甚至產生錯誤的道路拓撲信息,不利于騎行地圖的準確推斷,應將其視為噪聲并消除.

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

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

3.3 徘徊軌跡段消除

由于非機動車騎行場景的特殊性,騎行者常常進入一些非道路區域,例如居民區、商圈等.在這些區域中,騎行者往往不能直接快速到達目的地,而是在小區域范圍內花費大量時間騎行.同時由于軌跡采樣本身存在的隨機誤差,所采樣的軌跡會在其真實軌跡附近產生隨機分布,軌跡會呈現出隨機徘徊的狀態,這樣的軌跡段不僅無法呈現出道路的拓撲結構,其存在更會影響附近區域路口和道路的識別,并影響騎行地圖的最終構建,需要對徘徊軌跡段識別并消除.

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

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

3.4 違章軌跡段消除

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

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

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

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

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

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

第一,考慮到逆行和違規轉向軌跡段與其大多數近鄰軌跡點在方向以及方向變化上均存在較大差異,故先通過范圍提取待檢測軌跡點的近鄰點,并將近鄰點根據方向與方向變化劃分到8 個方向類中.第二,當近鄰點的方向大致相同時(以大多數近鄰點的方向為主方向,設置不屬于主方向的方向占比閾值tprop0.1),判定該軌跡點所處道路為單向道.第三,若當前軌跡點方向與主方向相反(即與主方向相差180°),判定該軌跡點存在逆行行為.若連續軌跡點序列中不存在逆行行為的軌跡點占比低于設定的閾值(tprop0.1),則判定該軌跡點序列為逆行軌跡段應予以消除,如圖5(b)所示.第四,當軌跡點方向不屬于近鄰點主方向,且其方向變化不同于其近鄰軌跡點的方向變化時(取不屬于主方向變化的占比閾值tprop0.1),判定該點有違規轉向行為.第五,當連續軌跡點序列的方向屬于主方向的占比低于閾值(tprop0.1)且存在違規轉向行為的軌跡點,判定該軌跡點序列存在違規轉向行為應予以消除.

3.5 漂移軌跡段校準

圖6 軌跡校準與恢復Fig.6 Calibration and recovery for trajectory

3.6 缺失軌跡段恢復

由于部分區域定位信號弱,存在連續軌跡點間的時間遠長于平均采樣時間間隔和距離遠大于平均采樣距離間隔的情況,稱為較長采樣間隔線段.因此,首先檢測發現較長采樣間隔線段,然后對其進行增量聚類以定位信號弱的區域.

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

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

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

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

4 實驗結果與分析

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

4.1 實驗數據集

騎行軌跡數據: 本文使用2020 年06 月到2021 年06 月的上海真實非機動車騎行軌跡,包含約80 萬個GPS 坐標點,1.6 萬條軌跡.

車行軌跡數據: 本文使用2020 年06 月01 日的上海真實車行軌跡數據,包含約360 萬個GPS 坐標點,1 萬條軌跡.

路網數據: 本文使用上海市2020 年的OSM(openstreetmap)騎行路網數據.

4.2 實驗環境

實驗時使用的Python 版本為 3.7.3,服務器操作系統為 CentOS Linux release 7.2.1511,硬件環境為 48 核Intel(R)Xeon(R)CPU E5-2670 v3 @ 2.30 GHz,內存125 GB.

4.3 評價標準

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

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

(2)道路生成: 將生成的道路與真實的OSM 路網進行地圖匹配,使用精度指標準確的數量AN,準確的長度AL以及正確匹配百分比CMP來評估實驗效果.Cwnu表示正確匹配的道路數量,Gwnu表示生成的道路數,Cwle表示正確匹配的道路長度,Gwle表示生成的道路長度,Cpnu表示正確匹配的樣本點數,Gpnu表示需要匹配的樣本點數,其中

4.4 對比算法

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

(1)CITT[4](a three-phase calibration framework for road intersection topology usingtrajectories):由軌跡數據質量提升、核心區檢測和影響區內拓撲結構校準構成的路口校準框架.

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

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

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

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

4.5 實驗效果

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

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

為了證明本文方法對騎行地圖推斷相關應用的提升,本文基于公開的騎行路網和現有地圖推斷應用的預處理方法進行路口發現和路網生成的評估實驗.選取的路口發現方法包括CITT 和Huang19,而選取的路網生成方法包括SLC 和Cao09.對于路口發現,所選取的進行量化評價的指標包括精確率、召回率和F1.對于路網生成,選取的進行量化評價的指標包括CMP、AL和AN,同時對實驗結果進行了可視化.

4.5.1 基于路口發現的數據質量提升評估

表1 為基于所選定的路口發現方法,并且分別在原始預處理和本文數據質量提升基礎上進行路口發現實驗的數據結果,其中CITT 和Huang19 對應基于原始預處理方法的結果,CITT+proposed和Huang19+proposed 對應基于本文數據質量提升方法的結果.

表1 路口發現的數據質量提升對比實驗結果Tab.1 Quantitative evaluation metrics for intersection finding

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

圖8 路口發現提升對比Fig.8 Example of road generation improving

徘徊軌跡段使得非道路區域內存在著大量不屬于道路范圍的軌跡,并且在密度、方向等因素上對真實路口的檢測特征存在較大影響,使CITT 方法檢測到更多的不在道路上的小路口同時對真實路口的檢測準確性下降,數據質量提升前后使用Huang 方法進行路口發現的可視化效果相差較大,其原因為Huang19 方法利用道路上的轉向點進行聚類,由于徘徊軌跡段的存在,會存在大量的非道路區域轉向點,影響路口的識別.

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

表2 路口發現的數據質量提升消融實驗結果Tab.2 Ablation experiment for intersection finding

4.5.2 基于路網生成的數據質量提升評估

表3 為基于選定的道路生成方法,并且分別在原始預處理和本文數據質量提升基礎上進行道路生成實驗的數據結果,其中SLC 和Cao09 對應基于原始預處理方法的道路生成結果,SLC+proposed和Cao09+proposed 對應基于本文數據質量提升方法的道路生成結果.

表3 道路生成的數據質量提升對比實驗結果Tab.3 Quantitative evaluation results of road generation

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

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

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

表4 為道路生成的數據質量提升消融實驗結果,其中Step1 為異常軌跡點的消除,Step2 為徘徊軌跡段的消除,Step3 為違章軌跡段的消除,Step4 為漂移軌跡段的校準,Step5 為缺失軌跡段的恢復,表4 展示了數據質量提升方法的不同步驟在道路生成的3 個評價指標中都得到了提升.其中徘徊軌跡段的消除和違章軌跡段消除對道路生成的影響最大,徘徊軌跡段的消除可以減少非道路區域中的大量徘徊軌跡,違章軌跡段的消除則可以減少道路區域的逆行軌跡和大量非騎行區域的軌跡,這些軌跡質量提升步驟最終減少了錯誤道路的生成.異常軌跡點的消除可以減少道路上的轉向異常點和距離異常點.漂移軌跡段校準步驟可以使得軌跡校準到其正確道路上,缺失軌跡恢復步驟可以恢復信號薄弱區的軌跡,能有效提升道路生成應用的效果.

表4 道路生成的數據質量提升消融實驗結果Tab.4 Ablation experiment for road generation

5 結 論

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