[發(fā)明專利]一種大規(guī)模移動(dòng)對(duì)象的軌跡快速預(yù)測(cè)方法、介質(zhì)和設(shè)備

有效

• 申請(qǐng)?zhí)枺?/td>: 202010160198.5
• 申請(qǐng)日: 2020-03-10
• 公開（公告）號(hào): CN111291280B
• 公開（公告）日: 2023-04-11
• 發(fā)明（設(shè)計(jì)）人: 錢塘文;徐勇軍;王飛;陳菲婭
• 申請(qǐng)（專利權(quán)）人: 中國科學(xué)院計(jì)算技術(shù)研究所
• 主分類號(hào): G06F16/9537
• 分類號(hào): G06F16/9537;G06F16/29
• 代理公司: 北京泛華偉業(yè)知識(shí)產(chǎn)權(quán)代理有限公司 11280
• 代理人: 王勇

本發(fā)明實(shí)施例提供了一種大規(guī)模移動(dòng)對(duì)象的軌跡快速預(yù)測(cè)方法、介質(zhì)和設(shè)備，本發(fā)明通過軌跡壓縮來減緩數(shù)據(jù)量大的壓力，采用柔和的獎(jiǎng)懲措施，即匹配成功后將對(duì)應(yīng)的兩個(gè)相鄰歷史規(guī)律點(diǎn)的高斯概率的均值作為相似度獎(jiǎng)勵(lì)來避免獎(jiǎng)懲措施過于尖銳，從而提高軌跡預(yù)測(cè)準(zhǔn)確性，并且本發(fā)明在獲取到與壓縮后的當(dāng)前軌跡相似度最高的壓縮后的歷史規(guī)律軌跡后，還通過插值補(bǔ)全法來實(shí)現(xiàn)在不降低軌跡預(yù)測(cè)準(zhǔn)確性的情況下提高實(shí)時(shí)性。

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

本發(fā)明涉及信息技術(shù)領(lǐng)域，具體來說軌跡預(yù)測(cè)技術(shù)，更具體地說，涉及一種大規(guī)模移動(dòng)對(duì)象的軌跡快速預(yù)測(cè)方法、介質(zhì)和設(shè)備。

背景技術(shù)

實(shí)時(shí)軌跡預(yù)測(cè)是預(yù)測(cè)目標(biāo)在未來一段時(shí)間內(nèi)的移動(dòng)路徑。對(duì)于個(gè)體而言，如果能有效預(yù)測(cè)出其未來一段時(shí)間內(nèi)的移動(dòng)路徑，可對(duì)其進(jìn)行個(gè)性化的服務(wù)推送，例如，推送提醒服務(wù)、廣告等。對(duì)于群體而言，準(zhǔn)確預(yù)測(cè)出每個(gè)目標(biāo)的未來移動(dòng)路徑，可以為智能交通管理提供便利，例如，提供基于軌跡預(yù)測(cè)的智能化交通服務(wù)。

軌跡預(yù)測(cè)通常的實(shí)現(xiàn)流程是計(jì)算出目標(biāo)的當(dāng)前軌跡與該目標(biāo)的所有歷史規(guī)律軌跡的相似性，繼而根據(jù)匹配到的歷史規(guī)律軌跡進(jìn)行未來時(shí)刻的軌跡預(yù)測(cè)。隨著智慧城市概念的提出，軌跡預(yù)測(cè)成為重要的研究主題，許多工作都致力于提升軌跡預(yù)測(cè)的實(shí)時(shí)性和準(zhǔn)確性。

軌跡相似性度量是實(shí)現(xiàn)軌跡預(yù)測(cè)的一個(gè)關(guān)鍵部分，用于計(jì)算當(dāng)前軌跡與歷史規(guī)律的相似度，當(dāng)前常用的相似度計(jì)算算法有：

動(dòng)態(tài)時(shí)間扭曲法(DTW)，其通過對(duì)當(dāng)前軌跡點(diǎn)的復(fù)制實(shí)現(xiàn)對(duì)軌跡進(jìn)行局部的拉伸或者縮放，從而可以對(duì)不同采樣率和不同長度的軌跡進(jìn)行比較；在變換域方面不設(shè)置閾值，直接計(jì)算其歐式距離；在有離群點(diǎn)出現(xiàn)時(shí)受到很強(qiáng)的影響；在處理不匹配點(diǎn)的方式上，重復(fù)使用某些點(diǎn)。

編輯距離方法(ERP)，其基于當(dāng)前軌跡點(diǎn)的相似性度量，是全局匹配度量，編輯距離又稱字符串的編輯距離，是指通過對(duì)字符串進(jìn)行增、刪、改等操作以使其中一個(gè)字符串與另一個(gè)字符串完全相同所需要的最小操作次數(shù)；該方法在變換域方面不設(shè)置閾值，直接計(jì)算其歐式距離；在有離群點(diǎn)出現(xiàn)時(shí)受到很強(qiáng)的影響；在處理不匹配點(diǎn)的方式上，不匹配的點(diǎn)會(huì)被用來和原點(diǎn)計(jì)算距離。

最長公共子序列(LCSS)主要考慮軌跡之間相似的部分作為軌跡相似性的度量；在變換域方面設(shè)置一個(gè)絕對(duì)閾值，滿足閾值變成0或者1；在有離群點(diǎn)出現(xiàn)時(shí)受到小幅度的影響；在處理不匹配點(diǎn)的方式上，不匹配的點(diǎn)會(huì)被忽略。

豪斯多夫距離法(Hausdorff)，其基于軌跡段的相似性度量，將軌跡進(jìn)行分段，段與段之間的距離用垂直距離、平行距離、角距離三個(gè)部分計(jì)算；在變換域方面根據(jù)兩條線段計(jì)算三種距離并加權(quán)取和；其不涉及對(duì)不匹配點(diǎn)的處理。

上述軌跡相似性度量算法存在著兩個(gè)問題：第一個(gè)問題是在計(jì)算相似度的獎(jiǎng)懲措施方面，要么直接用兩點(diǎn)間的絕對(duì)距離，要么直接加上0或1，這種獎(jiǎng)懲措施太過尖銳，拉大了相似與不相似的差距，降低了軌跡預(yù)測(cè)的準(zhǔn)確性；第二個(gè)問題是軌跡預(yù)測(cè)的實(shí)時(shí)性差，因?yàn)樵诰哂写笠?guī)模的移動(dòng)對(duì)象的情況下,要進(jìn)行軌跡預(yù)測(cè)的群體目標(biāo)數(shù)據(jù)量大，單體目標(biāo)的規(guī)律數(shù)目多，再加上相似性度量算法本身的時(shí)間復(fù)雜度均是O(n²)(其中，n表示當(dāng)前軌跡點(diǎn)的數(shù)量總數(shù)，O(n²)表示該算法若運(yùn)行完成所需花費(fèi)的時(shí)長是n²)，從而導(dǎo)致了大規(guī)模移動(dòng)對(duì)象的情形下，軌跡數(shù)據(jù)量(即n)大，而軌跡預(yù)測(cè)的步驟中必定有相似性度量，相似性度量算法的時(shí)間復(fù)雜度是O(n²)，導(dǎo)致軌跡預(yù)測(cè)的時(shí)長會(huì)變大，降低了軌跡預(yù)測(cè)的實(shí)時(shí)性。

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

因此，本發(fā)明的目的在于克服上述現(xiàn)有技術(shù)的缺陷，提供一種大規(guī)模移動(dòng)對(duì)象的軌跡快速預(yù)測(cè)方法、介質(zhì)和設(shè)備。

本發(fā)明的目的是通過以下技術(shù)方案實(shí)現(xiàn)的：

根據(jù)本發(fā)明的第一方面，提供一種大規(guī)模移動(dòng)對(duì)象的軌跡快速預(yù)測(cè)方法，包括如下步驟：

S1、獲取目標(biāo)的當(dāng)前軌跡和歷史規(guī)律軌跡，所述當(dāng)前軌跡包括多個(gè)當(dāng)前軌跡點(diǎn)，所述歷史規(guī)律軌跡包括多個(gè)歷史規(guī)律點(diǎn)；