基于網格分塊索引的車輛高頻活動區域算法

黎飛　程登　黃祖朋　張亮　張送　趙小羽　李淑英

摘 要：車輛的高頻活動區域對于車輛的服務應用有較大的參考意義，而汽車高頻活動區域的計算中會基于其采集模塊提供的經緯度數據進行運算，而該采集模塊的經緯度數據誤差通常為10米左右，較大誤差的引入會影響高頻區域計算的復雜度，準確性，及時性。若要降低該誤差通?？山柚岣卟杉K的采集精度，或第三方差分定位服務，但同時導致成本上升。本文將基于當前車輛采集模塊的經緯度數據精度，采用地圖網格化分塊索引的方式改進了車輛高頻活動區域的算法，提高了車輛高頻活動區域的計算的速度和準確性。

關鍵詞：網格 索引 高頻 區域算法

Algorithm of Vehicle High Frequency Activity Region Based on Grid Block Index

Li Fei Cheng Deng Huang Zupeng Zhang Liang Zhang Song Zhao Xiaoyu Li Shuying

Abstract：The high-frequency activity area of the vehicle has a great reference significance for the service application of the vehicle， and the calculation of the high-frequency activity area of the vehicle will be based on the longitude and latitude data provided by the collection module， and the longitude and latitude data error of the collection module is usually about 10 meters， and the introduction of large errors will affect the complexity， accuracy and timeliness of calculation in the high-frequency region. To reduce this error， it is usually possible to improve the acquisition accuracy of the acquisition module or a third-party differential positioning service， but at the same time it leads to an increase in cost. Based on the accuracy of the latitude and longitude data of the current vehicle acquisition module， this paper uses map gridding and block indexing to improve the algorithm of the vehicle high-frequency activity area， and improve the speed and accuracy of the calculation of the vehicle high-frequency activity area.

Key words：grid， index， high frequency， area algorithm

1 引言

隨著社會的發展和科技的進步，大數據，機器學習，人工智能等高新尖技術的飛速發展促使汽車向著智能化方向發展，基于車輛位置或活動區域的智能化服務作為其中重要的一環成為當下研究熱點。智能化服務的開展更多依賴車輛定位的精準度，運算速度，便于優化用戶畫像，給車輛的營銷，服務推薦等提供決策和改善方向。

當前大部分車輛位置所采集的經緯度誤差較大（通常為10～15米），要降低該誤差提高計算的準確度有兩種方案，一則提高采集設備的精度或引入第三方的差分定位服務，但此方案會導致車輛成本上升;二則通過引入其他特征數據，設計更復雜的運算模型，但此方案導致設計復雜性較高，運算實效和計算的硬件成本上升。綜上兩種方案均存在一些弊端。本文將介紹一種基于當前車輛經緯度誤差條件下，不增加硬件成本，降低運算的復雜性，提高運算時效性和定位精準度的優化算法方案。

2 算法思路

整體算法分為劃分區域網格，建立空間索引，處理車輛位置信息，車輛位置地圖映射，計算車輛所屬網格，確定高頻停車區域共6個步驟，如圖1。

2.1 劃分區域網格

將待分析區域的地圖按照經緯度坐標根據一定的間隔在縱橫方向上分成M 行和N列，即MxN個網格，如圖2。將網格上每個節點的經緯度作為該點的坐標Pi（xi，yi），其中x表示經度，y表示緯度，i表示網格節點編號索引，從0開始計。同時將每個網格建立編號索引。

2.2 建立空間索引

這是一種分割空間對象的索引方法。即為每個網格分配一個動態存儲區，并將該網格所框選的空間對象，如道路，建筑物等信息存入該網格對應的存儲空間中。

2.3 處理車輛位置數據

依據需求提取某個群體范圍里車輛經緯度數據并針對無效數據進行清洗，如空值，異常漂移值等。

2.4 車輛位置在地圖映射

將清洗好的車輛經緯度數據映射到地圖上，此時車輛每個位置將以點狀分布在地圖上，如圖3。

2.5 計算車輛位置所屬網格

假設每個網格的長度和寬度分別為dl，dw。dw為橫向兩相鄰節點橫坐標之差即經度之差，dl為縱向相鄰兩節點縱坐標之差即緯度之差（圖4）。

用車輛某個位置坐標xi和yi分別除以dw，dl，即可獲得改位置點所在的行和列編號，進而獲得網格編號。如公式1

行k=[yi/dl]+1

列j=[xi/dw]+1? ? ? ? ? ? ? ? 公式1

通過以上公式遍歷所有車輛位置數據，即可獲得每個位置點所屬的網格編號。

2.6 確定車輛高頻停車區域

計算各網格所包含的位置點的總數并按降序排列，選取數量最多的幾個（通常不超過3個）網格所在的區域即為該車輛的高頻活動區域。結合區域內存儲的空間對象，即可很好的判斷車輛的活動喜好。如圖5

3 算法總結

該算法的有兩個關鍵點。其一在于合理的定義網格的大小。網格劃分越小，確認的高頻活動區域越精準，但同時會增消耗較多計算資源和存儲資源，增加了計算時長。其二在于計算車輛位置所屬的網格編號。通常的算法會用車輛經緯度位置數據分別與每個網格的4個節點的經緯度數據進行比較運算來判斷所屬網格，但該算法需要遍歷每個網格的節點，運算效率不高，消耗的計算資源較多。本文算法采用車輛經緯度位置數據除以網格的長度和寬度的方法，僅計算一次變可以得到結果，效率較高。

4 結語

本文提出的算法無需引入高精采集設備或第三方差分定位服務或復雜計算模型，是一種低成本，高效率，高準確率的計算車輛高頻活動區域的算法，尤其面對在海量大數據及實時性要求較高的條件下，計算效能十分明顯。

基金項目：廣西創新驅動發展專項資金資助項目（桂科AA18242039）;柳州市科學研究與技術開發計劃資助項目（2019AG10202）

參考文獻：

[1]陶曉麗，張志華， 張麗等. 基于格網索引的點目標捕捉算法[J]. 測繪與空間地理信息，2015，38（10）：200.

[2]徐松杰，陳紫強.基于網格分塊的快速地圖匹配算法[J]. 桂林電子科技大學學報，2014，34（01）：33-36.

[3]張麗芬，王曉華，胡景松，宋維佳，龍斌. 基于網格劃分的幾種空間索引[J]. 北京理工大學學報，2004，24（02）：140-144.

[4]張順，尹洪權，吉敏. 基于網格索引的地圖匹配算法[J].齊魯工業大學學報[J]，2015，29（04）：77-80.