[發(fā)明專利]一種基于軌跡相似度的轉(zhuǎn)向路徑提取及路網(wǎng)拓撲變化檢測框架方法

有效

• 申請?zhí)枺?/td>: 202010059781.7
• 申請日: 2020-01-19
• 公開（公告）號: CN111291790B
• 公開（公告）日: 2021-03-26
• 發(fā)明（設計）人: 毛嘉莉;趙俐晟;劉國平;錢衛(wèi)寧;周傲英
• 申請（專利權(quán)）人: 華東師范大學;北京嘀嘀無限科技發(fā)展有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 上海德禾翰通律師事務所 31319
• 代理人: 陳艷娟

本發(fā)明在第一階段設計了一種基于軌跡相似度的轉(zhuǎn)向路徑提取方法，首先根據(jù)軌跡間Fréchet(弗雷歇)距離、起點夾角、終點夾角計算軌跡之間的相似度；隨后使用DBSCAN聚類算法根據(jù)相似性度量結(jié)果對軌跡進行聚類代表不同方向的轉(zhuǎn)向簇；最后通過設計的中心線擬合方法(即引入force?attraction方法的Fréchet距離計算，同時采用B?spline方法平滑中心線)提取不同方向簇的轉(zhuǎn)向路徑。本發(fā)明第二階段使用基于HMM(隱馬爾科夫模型)的地圖匹配方法，由提取的轉(zhuǎn)向路徑對路口路網(wǎng)拓撲結(jié)構(gòu)的變化進行檢測，本發(fā)明可以有效地對現(xiàn)有路網(wǎng)進行增量更新。

技術(shù)領(lǐng)域

本發(fā)明屬于軌跡挖掘技術(shù)領(lǐng)域，具體涉及一種基于軌跡相似度的轉(zhuǎn)向路徑提取及路網(wǎng)拓撲變化檢測框架方法。

背景技術(shù)

使用車輛軌跡對道路交叉口內(nèi)的轉(zhuǎn)向路徑提取的應用場景有導航轉(zhuǎn)向播報、自動駕駛及路口路網(wǎng)更新等。車輛到達轉(zhuǎn)向點前，導航能夠根據(jù)提取的轉(zhuǎn)向路徑讓用戶提前知曉下一步的動向，如右轉(zhuǎn)，左轉(zhuǎn)，掉頭等。此外自動駕駛車輛能夠依賴轉(zhuǎn)向路徑在道路交叉口正確地行駛。同時該方法是對道路交叉口的進一步研究，能夠更加精確地完善地圖。

目前主要存在兩種提取方法，一種方法是基于軌跡線段，使用SVM或?qū)哟尉垲惖姆椒ㄌ崛〉缆方徊婵趦?nèi)的轉(zhuǎn)向路徑，這類方法需要預先給轉(zhuǎn)向路徑類別的特征和數(shù)量才能有效分類。另一種是根據(jù)各軌跡的起點和終點的位置，對軌跡進行聚類區(qū)分，該方法丟失了軌跡行駛路徑的特征，在復雜路口區(qū)分的效果仍舊不理想。

由于道路基礎(chǔ)設施的不斷更新及交通狀況的動態(tài)變化，原始路網(wǎng)會存在新路缺失，偏移等現(xiàn)象，容易給用戶的移動導航帶來嚴重影響，可以利用提取的轉(zhuǎn)向路徑對道路交叉口范圍內(nèi)，道路進行更新。目前主要有兩種方法，第一種為人工上報，通過導航用戶的主動上報或?qū)I(yè)制圖人員進行實地考察，該方法依賴人工，可能會存在誤差。第二種是根據(jù)軌跡熱力圖像更新的方式，該方法計算成本較高，仍然不能滿足數(shù)字地圖快速更新的需求。

以上分析可見，在實際情況中，各道路交叉口的路口形狀和轉(zhuǎn)向行為不同，不能夠用統(tǒng)一的先驗知識去描述它，SVM和層次聚類方法需要預先定義分類的個數(shù)，不能夠自動化實現(xiàn)對于路口拓撲的提取。只根據(jù)軌跡的起點和終點進行聚類區(qū)分的方法，丟失了軌跡行駛路徑的特征，結(jié)果中會存在較多誤差。現(xiàn)有的軌跡熱力圖像檢測路網(wǎng)的更新的方法在軌跡密集區(qū)的難以區(qū)分同一區(qū)域內(nèi)的不同道路，如平行道路中的交叉口，同時在稀疏軌跡區(qū)域，不能夠識別路段。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是針對上述現(xiàn)有技術(shù)的不足，本發(fā)明第一階段首先設計了一種基于軌跡相似度的轉(zhuǎn)向路徑提取方法，根據(jù)軌跡間Fréchet(弗雷歇)距離、起點夾角、終點夾角計算軌跡之間的相似度，然后使用DBSCAN由相似度進行聚類得到不同類別的轉(zhuǎn)向簇，最后通過中心線擬合得到轉(zhuǎn)向路徑，在本發(fā)明第二階段基于HMM的地圖匹配方法，由提取的轉(zhuǎn)向路徑對路口路網(wǎng)進行拓撲結(jié)構(gòu)變化檢測。

為實現(xiàn)上述技術(shù)目的，本發(fā)明采取的技術(shù)方案為：

一種基于軌跡相似度的轉(zhuǎn)向路徑提取及路網(wǎng)拓撲變化檢測框架，包含以下步驟：

S1:對全量的軌跡兩兩進行相似度度量，生成相似度矩陣；

S2:基于步驟S1得到的相似度矩陣，使用DBSCAN算法對各軌跡進行聚類生成轉(zhuǎn)向簇；

S3:基于步驟S2得到的轉(zhuǎn)向簇，提取各轉(zhuǎn)向簇的中心線，得到轉(zhuǎn)向路徑；

S4:基于步驟S3提取出的道路交叉口轉(zhuǎn)向路徑后，提取相關(guān)的路網(wǎng)凸包，使用HMM模型，與原始路網(wǎng)進行地圖匹配，檢測出發(fā)生拓撲變化的路網(wǎng)；[0019]為優(yōu)化上述技術(shù)方案，采取的具體措施還包括：

上述的步驟S1具體包括：