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

關(guān)鍵詞：車輛軌跡;密度聚類;停車場出入口;多傳感器融合;末端導(dǎo)航

中圖分類號：U491.7+1;TP311.52 ? ? 文獻(xiàn)標(biāo)識碼：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 ?引 ?言

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

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

1 ?數(shù)據(jù)采集及預(yù)處理

1.1 ?車輛數(shù)據(jù)上報(bào)到云端服務(wù)器

1.1.1 ?DR軌跡數(shù)據(jù)

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

1.1.2 ?車輛開關(guān)機(jī)狀態(tài)

進(jìn)出停車場時通常會有停車熄火、開車點(diǎn)火的動作。記錄車輛開關(guān)機(jī)狀態(tài)，可以區(qū)分出是由于進(jìn)入地下車庫還是建筑物遮擋導(dǎo)致的GPS信號丟失。

1.1.3 ?行程信息

如用戶使用導(dǎo)航時行程中設(shè)置的起點(diǎn)和終點(diǎn)位置。停車場通常為用戶的出發(fā)地或目的地，更多維度的信息有助于提升數(shù)據(jù)挖掘的準(zhǔn)確度。

1.2 ?行程切分

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

1.3 ?出入口軌跡串提取

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

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

1.4 ?道路匹配

道路匹配是指將單個用戶行程中的連續(xù)軌跡點(diǎn)，根據(jù)行駛方向、經(jīng)緯度，與基礎(chǔ)路網(wǎng)中道路的方向和投影距離進(jìn)行相似度比較，取相似度最大的道路作為匹配結(jié)果，從而將軌跡集映射為道路集。文獻(xiàn)[5]通過路網(wǎng)拓?fù)潢P(guān)系來推測軌跡行進(jìn)路徑，以改善車輛軌跡數(shù)據(jù)在并行路段、立交橋等復(fù)雜道路場景中的地圖匹配效果。

將軌跡點(diǎn)匹配到道路后，就可以根據(jù)道路屬性、軌跡點(diǎn)與道路間的關(guān)系來過濾異常軌跡數(shù)據(jù)。

1.5 ?數(shù)據(jù)清洗

上述提到的每個行程的出入口軌跡子串，實(shí)際并不一定都是進(jìn)出停車場的場景。需要排除由于高架道路遮擋、進(jìn)出隧道等原因?qū)е碌腉PS信號丟失?；谲壽E點(diǎn)匹配道路、車速、車輛行駛方向等數(shù)據(jù)進(jìn)行篩選，以去除異常數(shù)據(jù)。

（1）因?yàn)樵诘貛熘熊囕v行駛速度受限，統(tǒng)計(jì)軌跡串中軌跡點(diǎn)速度大于30 km/h的個數(shù)，如果大于點(diǎn)總數(shù)的1/10，則認(rèn)為是非地庫場景。（2）軌跡串中是否存在類型為熄火或點(diǎn)火的信號，如果不存在，則認(rèn)為是非地庫場景;因?yàn)榈貛靾鼍爸写嬖诘湫吞卣魇牵很囕v會有停車熄火或開車點(diǎn)火的信號。（3）軌跡點(diǎn)匹配到的道路必須不是高速、高架類型，以排除高架道路遮擋的原因?qū)е碌腉PS信息丟失;同時也不會由高速高架路直接進(jìn)入地下停車場（需要經(jīng)由低等級道路進(jìn)入）。（4）軌跡點(diǎn)匹配到道路的總數(shù)過多，如果大于預(yù)定值（點(diǎn)總數(shù)的1/5），則認(rèn)為是非地庫場景;因?yàn)榈貛旆秶鷥?nèi)大概率存在地面建筑物，很少存在道路。（5）單個離散GPS信號丟失可能是由于周邊建筑物的遮擋引起，可通過連續(xù)多幀GPS信號丟失狀態(tài)來確認(rèn)進(jìn)入地庫的場景。

1.6 ?停車場入口點(diǎn)確定

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

1.7 ?停車場出口點(diǎn)確定

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

2 ?停車場出入口聚類

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

因?yàn)橥＼噲龀鋈肟趥€數(shù)不確定，且車輛軌跡存在一定程度的漂移，選用DBSCAN來實(shí)現(xiàn)停車場出入口個數(shù)自動發(fā)現(xiàn)，根據(jù)DR位置精度設(shè)置EPS參數(shù)，排除漂移的軌跡點(diǎn)。

2.1 ?出入口位置聚類

基于軌跡點(diǎn)經(jīng)緯度可計(jì)算出任意兩點(diǎn)間的球面距離，使用該距離調(diào)整鄰域距離閾值，對停車場出入口分別使用DBSCAN算法，參數(shù)設(shè)置如下：

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

MinPts——鄰近區(qū)域內(nèi)至少包含點(diǎn)的個數(shù);該參數(shù)依賴于參與聚類的軌跡串個數(shù)而定;根據(jù)經(jīng)驗(yàn)采用數(shù)據(jù)集內(nèi)樣本數(shù)量的1/25[8]，設(shè)置個數(shù)為20。

2.2 ?出入口通行方向聚類

基于上述出入口位置聚類的結(jié)果，需要進(jìn)一步識別出軌跡的行駛方向，從而標(biāo)志為出口或入口。類似地，根據(jù)行駛方向?qū)ξ恢镁垲惤Y(jié)果進(jìn)行二次聚類即可。

2.3 ?停車場出入口聚合

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

3 ?停車場區(qū)域面聚合

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

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

4 ?停車場出入口在導(dǎo)航中的應(yīng)用

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

如圖1所示，車輛以XXX地下停車場為起點(diǎn)，規(guī)劃導(dǎo)航路線，現(xiàn)有導(dǎo)航軟件規(guī)劃的路線以距離車輛最近的B路優(yōu)先匹配，作為起始道路;而本文通過停車場區(qū)域與當(dāng)前位置點(diǎn)的包含關(guān)系，能夠準(zhǔn)確獲取到所在停車場及其出口，規(guī)劃路線起始道路為A路，即停車場出口道路，計(jì)算出最佳導(dǎo)航路線。

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

5 ?停車場出入口挖掘?qū)嵗治?/p>

5.1 ?實(shí)驗(yàn)數(shù)據(jù)

以上海為例，基于2019年10月份的軌跡數(shù)據(jù)，共挖掘出793個停車場，包含1 048個入口和1 049個出口。本公司設(shè)計(jì)的某停車場軟件如圖3所示，其中多邊形區(qū)域?yàn)樯傻哪惩＼噲鰠^(qū)域，兩個小圓點(diǎn)分別為進(jìn)出口位置。經(jīng)驗(yàn)證，多邊形區(qū)域范圍和出入口位置均與實(shí)際停車場數(shù)據(jù)相吻合。

5.2 ?實(shí)驗(yàn)結(jié)果評測

5.2.1 ?評測流程

考慮到人工驗(yàn)證的方式無法大量地評測挖掘結(jié)果，本文通過與圖商采集到的停車場數(shù)據(jù)進(jìn)行對比，實(shí)現(xiàn)大規(guī)模自動化評測，評測流程如圖4所示。

5.2.2 ?評測標(biāo)準(zhǔn)

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

5.2.3 ?評測結(jié)果

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

6 ?結(jié) ?論

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

參考文獻(xiàn)：

[1] 傅夢穎，王培曉，張恒才，等.一種室內(nèi)導(dǎo)航網(wǎng)絡(luò)眾包構(gòu)建方法 [J].測繪科學(xué)技術(shù)學(xué)報(bào)，2019，36（1）：100-104.

[2] 秦永元.慣性導(dǎo)航：第2版 [M].北京：科學(xué)出版社，2014.

[3] 孫澤鵬.淺談慣導(dǎo)發(fā)展及其分類 [J].山東工業(yè)技術(shù)，2017（17）：277.

[4] 楊新狀，許承東，李懷建，等.SINS/GPS組合導(dǎo)航計(jì)算機(jī)系統(tǒng)設(shè)計(jì)與開發(fā) [J].彈箭與制導(dǎo)學(xué)報(bào)，2004（1）：34-36.

[5] 張?；?，孫凱，職保平，等.針對復(fù)雜道路網(wǎng)絡(luò)的車輛軌跡地圖匹配算法 [J].測繪科學(xué)，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].測繪通報(bào)，1999（5）：3-5+11.

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

作者簡介：蔣民鋒（1978-），男，漢族，江西新余人，畢業(yè)于南京大學(xué)地圖學(xué)與地理信息系統(tǒng)專業(yè)，碩士，LBS部門經(jīng)理，研究方向：LBS數(shù)據(jù)挖掘及地圖引擎研發(fā)。