基于網(wǎng)格分塊索引的車輛高頻活動區(qū)域算法

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

摘 要：車輛的高頻活動區(qū)域?qū)τ谲囕v的服務(wù)應(yīng)用有較大的參考意義，而汽車高頻活動區(qū)域的計(jì)算中會基于其采集模塊提供的經(jīng)緯度數(shù)據(jù)進(jìn)行運(yùn)算，而該采集模塊的經(jīng)緯度數(shù)據(jù)誤差通常為10米左右，較大誤差的引入會影響高頻區(qū)域計(jì)算的復(fù)雜度，準(zhǔn)確性，及時性。若要降低該誤差通常可借助提高采集模塊的采集精度，或第三方差分定位服務(wù)，但同時導(dǎo)致成本上升。本文將基于當(dāng)前車輛采集模塊的經(jīng)緯度數(shù)據(jù)精度，采用地圖網(wǎng)格化分塊索引的方式改進(jìn)了車輛高頻活動區(qū)域的算法，提高了車輛高頻活動區(qū)域的計(jì)算的速度和準(zhǔn)確性。

關(guān)鍵詞：網(wǎng)格 索引 高頻 區(qū)域算法

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 引言

隨著社會的發(fā)展和科技的進(jìn)步，大數(shù)據(jù)，機(jī)器學(xué)習(xí)，人工智能等高新尖技術(shù)的飛速發(fā)展促使汽車向著智能化方向發(fā)展，基于車輛位置或活動區(qū)域的智能化服務(wù)作為其中重要的一環(huán)成為當(dāng)下研究熱點(diǎn)。智能化服務(wù)的開展更多依賴車輛定位的精準(zhǔn)度，運(yùn)算速度，便于優(yōu)化用戶畫像，給車輛的營銷，服務(wù)推薦等提供決策和改善方向。

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

2 算法思路

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

2.1 劃分區(qū)域網(wǎng)格

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

2.2 建立空間索引

這是一種分割空間對象的索引方法。即為每個網(wǎng)格分配一個動態(tài)存儲區(qū)，并將該網(wǎng)格所框選的空間對象，如道路，建筑物等信息存入該網(wǎng)格對應(yīng)的存儲空間中。

2.3 處理車輛位置數(shù)據(jù)

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

2.4 車輛位置在地圖映射

將清洗好的車輛經(jīng)緯度數(shù)據(jù)映射到地圖上，此時車輛每個位置將以點(diǎn)狀分布在地圖上，如圖3。

2.5 計(jì)算車輛位置所屬網(wǎng)格

假設(shè)每個網(wǎng)格的長度和寬度分別為dl，dw。dw為橫向兩相鄰節(jié)點(diǎn)橫坐標(biāo)之差即經(jīng)度之差，dl為縱向相鄰兩節(jié)點(diǎn)縱坐標(biāo)之差即緯度之差（圖4）。

用車輛某個位置坐標(biāo)xi和yi分別除以dw，dl，即可獲得改位置點(diǎn)所在的行和列編號，進(jìn)而獲得網(wǎng)格編號。如公式1

行k=[yi/dl]+1

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

通過以上公式遍歷所有車輛位置數(shù)據(jù)，即可獲得每個位置點(diǎn)所屬的網(wǎng)格編號。

2.6 確定車輛高頻停車區(qū)域

計(jì)算各網(wǎng)格所包含的位置點(diǎn)的總數(shù)并按降序排列，選取數(shù)量最多的幾個（通常不超過3個）網(wǎng)格所在的區(qū)域即為該車輛的高頻活動區(qū)域。結(jié)合區(qū)域內(nèi)存儲的空間對象，即可很好的判斷車輛的活動喜好。如圖5

3 算法總結(jié)

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

4 結(jié)語

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

基金項(xiàng)目：廣西創(chuàng)新驅(qū)動發(fā)展專項(xiàng)資金資助項(xiàng)目（桂科AA18242039）;柳州市科學(xué)研究與技術(shù)開發(fā)計(jì)劃資助項(xiàng)目（2019AG10202）

參考文獻(xiàn)：

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

[2]徐松杰，陳紫強(qiáng).基于網(wǎng)格分塊的快速地圖匹配算法[J]. 桂林電子科技大學(xué)學(xué)報(bào)，2014，34（01）：33-36.

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

[4]張順，尹洪權(quán)，吉敏. 基于網(wǎng)格索引的地圖匹配算法[J].齊魯工業(yè)大學(xué)學(xué)報(bào)[J]，2015，29（04）：77-80.