地下停車場出入口眾包構建方法及應用探析

摘 ?要：停車場出入口是基礎地圖數據，采用傳統人工采集方式時效性差。根據車輛進出地下停車場時GPS信號狀態改變的特性，融合DR軌跡、車輛狀態、陀螺儀傾角等多傳感器數據，提出一種眾包地圖構建方法，使用DBSCAN聚類及多邊形生成算法，挖掘出地下停車場區域范圍、出入口及其通行方向。結果表明，該方法提取的出入口數據準確度高，應用于地圖數據生產中可實現數據動態更新。導航時將起終點綁定到出入口道路上，可提供最優路線，指引用戶進出停車場，改善用戶體驗。

關鍵詞：車輛軌跡;密度聚類;停車場出入口;多傳感器融合;末端導航

中圖分類號：U491.7+1;TP311.52 ? ? 文獻標識碼：A 文章編號：2096-4706（2020）04-0054-04

Abstract：The gateway to the underground parking lot is basic map data. Its difficult to guarantee data freshness under manual data collection conditions. According to the characteristics of GPS signal state change when vehicles enter and leave the underground parking lot，and the multi-sensor data such as DR track，vehicle state and gyroscope angle are integrated，a method of building crowdsourcing map is proposed. DBSCAN clustering and polygon generation algorithm are used to excavate the area range，entrance and exit of the underground parking lot and its traffic direction. The results show that the accuracy of gateway extracted by using this method is high. Application in map data production can implement dynamic data update. During navigation，the start and end points are bound to the access road，which can provide the best route，guide users to enter and exit the parking lot，and improve the user experience.

Keywords：vehicle trajectory;density clustering;gateway of parking lot;multi-sensor fusion;terminal navigation

0 ?引 ?言

有過開車經驗的人相信都遇到過找不到停車場入口的尷尬。地圖導航軟件如何解決末端導航中的用戶痛點是筆者工作中的研究課題。究其原因有二：一是導航算路時沒有將規劃路線的終點綁定到停車場入口道路;二是地圖數據中停車場出入口數據覆蓋率及鮮度都不足。以上海19Q1數據為例，現有圖商數據中，關聯了進出口道路的停車場只占總數的28%，且出入口的通行方向經常變化，導致數據準確性不高。傳統人工采集停車場出入口數據時效性差，無法反映出入口的后期變化[1]。近年來互聯網汽車的興起讓車輛位置可以發送到云端，通過車輛軌跡大數據挖掘的手段，獲取停車場對應的出入口，用全新的方式來補充現有停車場數據的不足。基于停車場出入口數據，改進導航軟件中的路徑規劃算法，實現用戶進出停車場時的精確引導。

在現有公開文獻中，未見有地下停車場出入口、通行方向及其區域范圍挖掘的詳細論述。本文融合GPS信號狀態、DR（慣性導航）軌跡、車輛狀態等多傳感器數據，通過DBSCAN聚類及多邊形生成算法，提取停車場出入口及區域，取得了良好效果，提供了一種數據更新的新思路。

1 ?數據采集及預處理

1.1 ?車輛數據上報到云端服務器

1.1.1 ?DR軌跡數據

慣性導航系統（INS）是依據牛頓慣性原理，利用陀螺儀、加速度計等慣性敏感元件及初始信息來計算載體的姿態、速度和位置[2，3]。組合導航綜合了INS的穩定性好及GPS的精度高等優點，可以提供高精度且穩定可靠的導航信息[4]，在地下停車場中GPS失效時，仍能提供準確的車輛位置。上報數據包含：車輛的DR軌跡、車速、行駛方向、GPS信號狀態、陀螺儀識別到的道路坡度變化值。

1.1.2 ?車輛開關機狀態

進出停車場時通常會有停車熄火、開車點火的動作。記錄車輛開關機狀態，可以區分出是由于進入地下車庫還是建筑物遮擋導致的GPS信號丟失。

1.1.3 ?行程信息

如用戶使用導航時行程中設置的起點和終點位置。停車場通常為用戶的出發地或目的地，更多維度的信息有助于提升數據挖掘的準確度。

1.2 ?行程切分

上傳到云端的軌跡數據是所有車輛數據的集合，需要根據每條軌跡記錄中的車輛通用唯一識別碼（UUID），提取出一輛車從進入到退出停車場的完整行駛路徑;每輛車對應一個行程，每個行程可以表示一個用戶的一次出行旅程。

1.3 ?出入口軌跡串提取

車輛在進入地下停車場時，GPS信號丟失，記錄為無信號狀態;相反，車輛在離開地下停車場時，GPS信號接收成功，變更為有信號狀態。

根據這一特征可大致定位到出入口位置的軌跡點。同時考慮到GPS信號的不穩定性及存在GPS漂移問題，在GPS信號狀態變更前后的連續若干個軌跡點都可能是實際出入口位置，這些包含有出入口位置的連續軌跡點本文稱之為出入口軌跡串，可形式化描述為軌跡點的時間序列T=P1，P2，…，PN。由于用戶一天的行程可能出入于多個不同的地庫，因此同一行程又可以進一步切分為進出各個地庫場景的軌跡子串。

1.4 ?道路匹配

道路匹配是指將單個用戶行程中的連續軌跡點，根據行駛方向、經緯度，與基礎路網中道路的方向和投影距離進行相似度比較，取相似度最大的道路作為匹配結果，從而將軌跡集映射為道路集。文獻[5]通過路網拓撲關系來推測軌跡行進路徑，以改善車輛軌跡數據在并行路段、立交橋等復雜道路場景中的地圖匹配效果。

將軌跡點匹配到道路后，就可以根據道路屬性、軌跡點與道路間的關系來過濾異常軌跡數據。

1.5 ?數據清洗

上述提到的每個行程的出入口軌跡子串，實際并不一定都是進出停車場的場景。需要排除由于高架道路遮擋、進出隧道等原因導致的GPS信號丟失。基于軌跡點匹配道路、車速、車輛行駛方向等數據進行篩選，以去除異常數據。

（1）因為在地庫中車輛行駛速度受限，統計軌跡串中軌跡點速度大于30 km/h的個數，如果大于點總數的1/10，則認為是非地庫場景。（2）軌跡串中是否存在類型為熄火或點火的信號，如果不存在，則認為是非地庫場景;因為地庫場景中存在典型特征是：車輛會有停車熄火或開車點火的信號。（3）軌跡點匹配到的道路必須不是高速、高架類型，以排除高架道路遮擋的原因導致的GPS信息丟失;同時也不會由高速高架路直接進入地下停車場（需要經由低等級道路進入）。（4）軌跡點匹配到道路的總數過多，如果大于預定值（點總數的1/5），則認為是非地庫場景;因為地庫范圍內大概率存在地面建筑物，很少存在道路。（5）單個離散GPS信號丟失可能是由于周邊建筑物的遮擋引起，可通過連續多幀GPS信號丟失狀態來確認進入地庫的場景。

1.6 ?停車場入口點確定

在每個行程終點附近，針對過濾異常數據后的出入口子串，可通過以下條件分析得到地下停車場入口的具體位置：（1）GSP信號狀態由有信號變更為信號丟失狀態。（2）存在連續多幀GPS信號丟失，且后續狀態一直持續。（3）車庫中車輛行駛速度受限，行駛速度<30 km/h（預定值）。（4）進入地庫時車輛通常會有較大的轉向角度。（5）陀螺儀識別到進入地下車庫時的坡度變化（下坡）。

1.7 ?停車場出口點確定

針對每個行程起點附近，連續多幀數據成功接收GPS信號時，將首個成功接收GPS信號的位置點確定為出口點。由此可以分析得到地下停車場出口的具體位置，確定出口點的條件為：（1）此前車輛位于地下停車場區域。（2）出車庫時，連續多幀數據成功接收GPS信號。（3）陀螺儀識別到退出地下車庫時的坡度變化（上坡）。

2 ?停車場出入口聚類

針對所有車輛、所有行程中的入口點和出口點，分別進行聚類分析，得到地下停車場的出口和入口。DBSCAN算法由Martin Ester、Hans-PeterKriegel等人[6]在1996年提出。它有以下優點：（1）聚類速度快且能夠有效處理噪聲點和發現任意形狀的空間聚類。（2）與K-Means比較起來，不需要輸入要劃分的聚類個數。

因為停車場出入口個數不確定，且車輛軌跡存在一定程度的漂移，選用DBSCAN來實現停車場出入口個數自動發現，根據DR位置精度設置EPS參數，排除漂移的軌跡點。

2.1 ?出入口位置聚類

基于軌跡點經緯度可計算出任意兩點間的球面距離，使用該距離調整鄰域距離閾值，對停車場出入口分別使用DBSCAN算法，參數設置如下：

EPS——在一個點周圍鄰近區域的半徑;待聚類的數據集中，任意兩個點之間的距離，反映了點之間的密度，說明了點與點是否能夠聚到同一類中;文獻[7]指出，民用GPS的定位誤差為±10 m，設置距離閾值為10 m。

MinPts——鄰近區域內至少包含點的個數;該參數依賴于參與聚類的軌跡串個數而定;根據經驗采用數據集內樣本數量的1/25[8]，設置個數為20。

2.2 ?出入口通行方向聚類

基于上述出入口位置聚類的結果，需要進一步識別出軌跡的行駛方向，從而標志為出口或入口。類似地，根據行駛方向對位置聚類結果進行二次聚類即可。

2.3 ?停車場出入口聚合

一個停車場會有多個出入口，而通過一次進出地庫的行程只能提取出一對出入口;如何將不同行程的出入口關聯到同一停車場？本文基于聚類簇和出入口成對關系進行停車場聚合，可挖掘出停車場對應的所有出入口：（1）從某一個聚類簇開始，簇內所有的出入口標記為同一停車場。（2）根據出入口成對關系找到另一個簇，而此簇內所有的出入口同樣標記為此停車場。（3）以此類推，遞歸找到該停車場所有出入口。

3 ?停車場區域面聚合

將上述出口點和入口點之間的軌跡確定為地下停車場內部軌跡，基于所有行程的地下停車場內部軌跡，通過外接多邊形生成算法，確定地下停車場區域。

（1）按天過濾聚類簇內沒有成對的出入口軌跡（過濾入口或出口信息丟失的軌跡串，只保留同時有出入口的軌跡串）。（2）按天取完整出入口軌跡計算外接多邊形凸包。（3）合并多天的凸包，得到停車場區域面。（4）建立停車場出入口與區域范圍的關聯。

4 ?停車場出入口在導航中的應用

基于上述停車場及其出入口數據，可以改善末端導航中缺乏引導信息或引導信息錯誤的問題。在以停車場為導航目的地時，現有主流導航軟件都無法精確地引導用戶到達停車場入口位置。在以地下停車場為出發地時，規劃路線的開始道路往往不是停車場的出口道路，而是離車輛位置直線距離最近的道路（該道路不可直達）。這會導致當用戶駛離停車場時，看不到規劃路線，直到GPS信號良好時（通常需要較長的時間），才會提示用戶重新計算路線。在新路線完成之前，用戶實際無路線可引導，經常走錯路口。

如圖1所示，車輛以XXX地下停車場為起點，規劃導航路線，現有導航軟件規劃的路線以距離車輛最近的B路優先匹配，作為起始道路;而本文通過停車場區域與當前位置點的包含關系，能夠準確獲取到所在停車場及其出口，規劃路線起始道路為A路，即停車場出口道路，計算出最佳導航路線。

在停車場導航中，圖2展示了基于出入口的路徑規劃策略;從停車場出入口道路精準地計算路線并引導，可解決用戶進出停車場時無路線引導或引導路線錯誤的問題。

5 ?停車場出入口挖掘實例分析

5.1 ?實驗數據

以上海為例，基于2019年10月份的軌跡數據，共挖掘出793個停車場，包含1 048個入口和1 049個出口。本公司設計的某停車場軟件如圖3所示，其中多邊形區域為生成的某停車場區域，兩個小圓點分別為進出口位置。經驗證，多邊形區域范圍和出入口位置均與實際停車場數據相吻合。

5.2 ?實驗結果評測

5.2.1 ?評測流程

考慮到人工驗證的方式無法大量地評測挖掘結果，本文通過與圖商采集到的停車場數據進行對比，實現大規模自動化評測，評測流程如圖4所示。

5.2.2 ?評測標準

（1）圖商停車場周邊30 m范圍內找到同類型的挖掘出入口，視為匹配成功;當距離超過30 m但匹配道路一致時，也視為匹配成功。（2）如果圖商停車場在30 m范圍內沒有道路，說明該點誤差太大，再擴大一倍搜索范圍。（3）挖掘的停車場面只包括1個圖商停車場，如果挖掘的出入口個數都匹配到圖商出入口，只是圖商個數多于挖掘的個數，仍視為成功。（4）挖掘的停車場面包括多個圖商停車場，如果圖商的出入口都能匹配到挖掘的出入口，忽略停車場名稱誤差，視為成功。

5.2.3 ?評測結果

（1）共有418個停車場關聯到圖商出入口，涉及挖掘的出口579個，挖掘的入口585個。（2）其中90.4%的停車場與圖商數據匹配成功。（3）其中90.2%的停車場出入口與圖商數據匹配成功。（4）在車輛接近停車場出入口時，DR軌跡會有一定程度的漂移，在GPS信號很差的情況下，聚類后的出入口點會與實際位置有所偏差。后續的改進方向，一是提升DR位置精度，二是收集更多的行程軌跡數據，以清洗掉漂移過大的軌跡點。

6 ?結 ?論

本文針對車輛進出地下停車場的場景，融合多傳感器數據，如DR位置、GPS信號狀態、車輛熄火點火狀態、陀螺儀傾角，通過大數據挖掘的方式，成功提取出停車場區域及其出入口，經與圖商采集到的停車場數據比較，有90.0%以上的匹配度，效果令人滿意;這一思路可直接應用于實際數據生產中，以提高生產效率、提升數據鮮度。在導航算路時，將起終點位置綁定到停車場出入口道路上，可規劃出最優路徑，以解決用戶末端導航時的引導焦慮問題，改善用戶體驗，具有很大的實用價值和應用前景。

參考文獻：

[1] 傅夢穎，王培曉，張恒才，等.一種室內導航網絡眾包構建方法 [J].測繪科學技術學報，2019，36（1）：100-104.

[2] 秦永元.慣性導航：第2版 [M].北京：科學出版社，2014.

[3] 孫澤鵬.淺談慣導發展及其分類 [J].山東工業技術，2017（17）：277.

[4] 楊新狀，許承東，李懷建，等.SINS/GPS組合導航計算機系統設計與開發 [J].彈箭與制導學報，2004（1）：34-36.

[5] 張校慧，孫凱，職保平，等.針對復雜道路網絡的車輛軌跡地圖匹配算法 [J].測繪科學，2018，43（8）：110-115.

[6] ESTER M，KRIEGEL H P，J?RG S，et al. A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise [C]// AAAI Press.KDD96.Proceedings of the Second International Conference on Knowledge Discovery and Data Mining，1996（8）：226–231.

[7] 韓明鋒，丁萬慶，謝世杰.GPS誤差概論 [J].測繪通報，1999（5）：3-5+11.

[8] 侯雄文.淺析DBSCAN算法中參數設置問題的研究 [J].科教導刊-電子版（下旬），2017（10）：266+277.

作者簡介：蔣民鋒（1978-），男，漢族，江西新余人，畢業于南京大學地圖學與地理信息系統專業，碩士，LBS部門經理，研究方向：LBS數據挖掘及地圖引擎研發。