[發(fā)明專利]地圖匹配

有效

• 申請?zhí)枺?/td>: 201380072025.6
• 申請日: 2013-03-15
• 公開（公告）號: CN104969032A
• 公開（公告）日: 2015-10-07
• 發(fā)明（設計）人: 王音;魏紅;喬治·福曼
• 申請（專利權）人: 惠普發(fā)展公司;有限責任合伙企業(yè)
• 主分類號: G01C21/30
• 分類號: G01C21/30;G01C21/34
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 柴德海;康泉

1.一種處理器實現(xiàn)的地圖匹配方法，包括：

接收數(shù)據集中的多個全球定位系統(tǒng)(GPS)數(shù)據點；

接收與多條道路相關的道路地圖數(shù)據；

為GPS數(shù)據集確定具有最小弗雷歇距離的多條路徑；

通過應用權重函數(shù)來向具有最小弗雷歇距離的每條路徑分配權重；以及

輸出具有最小權重的路徑。

2.根據權利要求1所述的方法，其中每個GPS數(shù)據點包括時間戳、經緯度對、速度和方位的組合。

3.根據權利要求1所述的方法，進一步包括：針對每個GPS數(shù)據點從所述多條道路中，確定候選道路位置，所述候選道路位置是位于一半徑內的道路的投影。

4.根據權利要求1所述的方法，其中為GPS數(shù)據集確定最小弗雷歇距離進一步包括：計算所述多條道路的值并且應用二進制查找。

5.根據權利要求4所述的方法，進一步包括：當值的剩余范圍比預定閾值更短時，停止所述二進制查找。

6.根據權利要求1所述的方法，其中通過應用權重函數(shù)來向具有最小弗雷歇距離的每條路徑分配權重進一步包括：使用所述權重函數(shù)基于距離和最短路徑計算每條路徑的權重。

7.根據權利要求6所述的方法，其中通過應用權重函數(shù)來向具有最小弗雷歇距離的每條路徑分配權重進一步包括：將所述權重函數(shù)選擇為針對具有不同采樣率的GPS數(shù)據集是魯棒的。

8.根據權利要求7所述的方法，其中所述權重函數(shù)根據以下函數(shù)來選擇具有最小權重的路徑：

9.根據權利要求1所述的方法，其中通過應用權重函數(shù)來向具有最小弗雷歇距離的每條路徑分配權重進一步包括：使用動態(tài)編程來避免具有最小弗雷歇距離的每條路徑的顯式枚舉。

10.根據權利要求9所述的方法，其中所述動態(tài)編程包括維特比動態(tài)編程。

11.根據權利要求1所述的方法，其中輸出具有最佳權重的路徑進一步包括：比較具有最小弗雷歇距離的每條路徑的權重，并且識別具有所述最小權重的路徑。

12.一種地圖匹配系統(tǒng)，包括：

處理器；

存儲器，聯(lián)接至所述處理器；以及

地圖匹配模塊，在所述存儲器中存儲且在所述處理器上執(zhí)行以：

接收數(shù)據集中的多個全球定位系統(tǒng)(GPS)數(shù)據點；

為每個GPS數(shù)據點確定候選道路位置，每個候選道路位置是位于一半徑內的道路的投影；

計算從與第一GPS數(shù)據點關聯(lián)的每個候選道路位置至與第二GPS數(shù)據點關聯(lián)的候選道路位置的最短路徑，所述第一GPS數(shù)據點和所述第二GPS數(shù)據點是連續(xù)的；以及

根據權重函數(shù)來選擇具有最小權重的路徑，所述權重函數(shù)基于所計算的最短路徑。

13.根據權利要求12所述的系統(tǒng)，其中所述地圖匹配模塊進一步在所述處理器上執(zhí)行以：并行處理從與所述第一GPS數(shù)據點關聯(lián)的每條道路候選至所述第二GPS數(shù)據點的候選的所述最短路徑的每個計算。

14.根據權利要求12所述的系統(tǒng)，其中所述地圖匹配模塊進一步在所述處理器上執(zhí)行以：

為所述GPS數(shù)據集確定具有最小弗雷歇距離的多條路徑。

15.根據權利要求12所述的系統(tǒng)，其中所述地圖匹配模塊進一步在所述處理器上執(zhí)行以：

限定包含所述多個GPS數(shù)據點的包圍矩形；以及

不理會位于所限定的矩形以外的道路位置。

16.根據權利要求12所述的系統(tǒng)，其中所述地圖匹配模塊進一步在所述處理器上執(zhí)行以：

將從候選道路位置至GPS數(shù)據點的最短路徑的查找范圍限制成基于預定速度和所述多個GPS數(shù)據點的采樣間隔計算的閾值。

17.根據權利要求12所述的系統(tǒng)，其中所述地圖匹配模塊進一步在所述處理器上執(zhí)行以：

將所述候選道路位置的集合的查找半徑限制成預定閾值，以減少候選的規(guī)模。

18.根據權利要求12所述的系統(tǒng)，其中所述權重函數(shù)根據下面的公式來選擇最小權重路徑：