基于GPS數(shù)據(jù)和壓縮柵格算法的城市路網(wǎng)電子地圖快速構建方法

劉善武 忽曉陽 李進

摘? 要： 路網(wǎng)電子地圖對城市交通管理領域有重要的作用，但是地圖服務機構提供的接口功能有限，商用地圖一般價格高昂;而一些基于GPS數(shù)據(jù)的地圖生成算法非常復雜、速度慢，在一些實際應用中受到限制，如區(qū)域地圖即時更新、道路臨時管制、應急路線規(guī)劃等。為此提出一種直觀、可擴展、操作靈活的城市道路地圖構建方式。通過奧賽羅坐標化的方式，對單位柵格的表示方式進行重新設計，在改善柵格地圖的拓撲表達能力、彌補柵格地圖存儲空間較大和處理時運算資源需求較多等弊端的同時，實現(xiàn)了地圖的快速構建。文章以公共交通服務評估和路網(wǎng)韌性評價為例，展示了這一方法的應用潛力。

關鍵詞： 數(shù)字柵格地圖; 地圖壓縮; 地圖拼接

中圖分類號：TP301.6? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2021）12-64-05

Abstract： Electronic maps have an important role in the field of urban traffic management， but the interface functions the map servicer provided are limited， and commercial maps are generally expensive. In addition， some map generation algorithms based on GPS data are very complex and slow， which limits their application in some practical scenarios， such as real-time area map updates， temporary road control， emergency route planning and so on. In response to these problems， an intuitive， extensible， and flexible way of constructing urban road maps is proposed. Through Othello's coordinated way， the representation of unit grid is redesigned， while improving the topology expression ability of the raster map; making up for the disadvantages of the raster map in requiring large storage space， and large computing resource during processing， etc.， the rapid construction of the map is realized. Taking public transport service evaluation and road network toughness evaluation as examples， the application potential of this method is demonstrated.

Key words： digital raster map; map compression; map stitching

0 引言

路網(wǎng)是整個交通系統(tǒng)的物質基礎[1-3]。《哥尼斯堡的七座橋》[4]中的網(wǎng)絡圖表示法是城市路網(wǎng)的最早表現(xiàn)形式之一，其用節(jié)點集表示路口，用邊集表示路段。在此基礎上衍生出有向圖[5]、對偶圖[6]、對偶拓撲圖[7]、鄰近圖[8]等方式對地圖拓撲結構進行研究。信息化發(fā)展的新階段，地理信息系統(tǒng)相關技術依據(jù)空間化建模和信息化分析的優(yōu)勢，在電子地圖中發(fā)揮著重要的作用[9]。2015年，諾基亞HERE地圖以25億歐元的價格被寶馬、奔馳和戴姆勒這三家汽車巨頭聯(lián)合收購，彰顯著地圖在商業(yè)領域越來越重要的地位。

然而，有限的地圖接口與商用地圖高精度下的高使用率與內(nèi)存成本，讓地圖的開發(fā)條件與范圍有所受限，對于非自動駕駛等低精度地圖需求下的導航、路線規(guī)劃、區(qū)域可視化、地理信息標準等應用場景，通過輔助數(shù)據(jù)自動生成地圖，可以進一步提高應用開發(fā)使用的靈活性與擴展性，同時縮短了地圖的更新周期。全球定位系統(tǒng)（Global Positioning System，GPS）的普及加速了電子地圖的發(fā)展與應用[10]，已有學者通過一定的方法從GPS軌跡數(shù)據(jù)中生成道路的拓撲結構[11-13]。而大多數(shù)基于GPS生成電子地圖的研究都是基于拓撲結構的地圖（路網(wǎng)數(shù)據(jù)基圖），對GPS精度要求高，算法復雜[14]。

柵格地圖也稱光柵圖像，一般由圖像數(shù)據(jù)繪制而成，若把柵格圖像看作矩陣，矩陣中每一個點的值為圖像中對應元素的灰度值，則完成了圖像的離散化，在此基礎上可以用數(shù)字矩陣的形式對地理信息進行抽象化表示。對于許多實際應用來說，柵格地圖也能夠很好的滿足要求，如路線規(guī)劃設計、設施選址、區(qū)域標注、路網(wǎng)管理、交通誘導與可視化分析等情形。

現(xiàn)有柵格地圖的生成，主要借助遙感影像[15]、傳感器[16]或GPS[14，17-18]這三種方式，前兩者受困于技術、人力和經(jīng)濟成本等因素，其較長的更新周期極大限制了市縣級以上區(qū)域型電子地圖的衍生應用。而基于GPS軌跡的路網(wǎng)生成研究，其主要通過軌跡點聚類與分割、中心線擬合、虛擬中間點插值或類似卷積等方式對GPS數(shù)據(jù)進行處理，進而生成矢量化的路網(wǎng)。在這個過程中，路網(wǎng)在數(shù)據(jù)預處理后一次生成，即使只是個別數(shù)據(jù)的更新、也需要載入所有的數(shù)據(jù);此外，當表述區(qū)域擴大時，其與傳統(tǒng)拓撲地圖一樣，面臨著數(shù)據(jù)量及其存儲空間增大的問題。

在面對因事故、災害等對局部或多個局部交通造成影響的情形時，不可能等待獲取整體的GPS軌跡、生成路網(wǎng)后再去響應，也不會將多地分別生成路網(wǎng)去分別響應;對于跨區(qū)的資源調(diào)配，其對地圖的精度需求可進一步降低，此時地理信息系統(tǒng)應更注重其魯棒性和容錯率，在不同的應用背景下可以靈活的應對不同硬件條件下的使用需求與范圍。

為解決以上問題，本研究提出一種基于壓縮柵格地圖的地理信息快速構建方法，以適應于對精度要求不高的地圖場景應用，其主要特點有：①通過坐標化路口方向與距離，用更少的數(shù)據(jù)和存儲空間表述節(jié)點間的拓撲關系、“壓縮”地圖的大小、節(jié)約系統(tǒng)的運行內(nèi)存需求;②采用多維坐標設計改進傳統(tǒng)柵格表示方式，在解決區(qū)域更新需整體重新生成問題的同時、增加單位柵格的信息容量，只需在更新局部地圖后，將其拼接并入主圖即可完成整體的更新，避免輸入全部數(shù)據(jù)給系統(tǒng)增加不必要的負擔;③“壓縮”與“還原”靈活可調(diào)，可依據(jù)場景對道路刻畫精確程度做調(diào)整，具有良好的擴展性和適應性。本文最后以黑龍江省七臺河市為例，檢驗了快速地圖構建的效果。

1 模型原理與符號說明

柵格法原理簡單、圖形直觀并且易于構造和維護，其精度與區(qū)域單元格劃分大小有關。區(qū)域單元劃分越小、建模過程中需要存儲的數(shù)據(jù)量越多，處理的復雜度就越高。為解決這一問題，采用絕對坐標轉相對坐標的方式，盡可能減少每個局部地圖的尺寸，并保留偏移量，為后續(xù)局部地圖的拼接以及全局地圖的還原預留參數(shù)。這里對文中出現(xiàn)的定義作詳細說明，如表1所示。

2 路網(wǎng)柵格地圖的生成

2.1 地圖平面化

本文選擇墨卡托（G. Mercator）投影法，對經(jīng)緯度坐標進行平面化處理，即將經(jīng)緯度坐標映射在笛卡爾直角坐標系上，以便后續(xù)處理與管理工作的進行。對于所采集的公交車運營GPS數(shù)據(jù)來說，其可能因地磁干擾、高大建筑物遮蔽、傳輸丟包等情況造成各種定位誤差，以經(jīng)緯度距離計算算法為核心將與標準坐標在閾值范圍內(nèi)的、最近的點作為異常GPS數(shù)據(jù)的校正參考點，其偽代碼如下。

算法1 經(jīng)緯度距離計算算法

Input： longitude1， latitude1， longitude2， latitude2

Output： Distance between two points

Begin

1 Cov_radian = map （radians， input_point）

2 Square = sin（dis_lat/2）^2 + cos（lat1） * cos（lat2）

* sin（dis_lon/2）^2

3 Distance = 2*sqrt（Square） *R_Earth*1000

4 Result = round（Distance， x）

5 return Result

End

2.2 奧賽羅坐標化設計

傳統(tǒng)的柵格地圖每個格子用0或1代表“可達”或“障礙”，為壓縮柵格地圖的規(guī)模、提升地圖的擴展性和應用場景，本章節(jié)設計奧賽羅坐標化方法，對節(jié)點所在格子重新賦值。如圖1所示，在原節(jié)點N1周圍虛擬添加新行新列、以在周圍產(chǎn)生九個流點（實際上N1與N5等節(jié)點仍相鄰）。

每一個節(jié)點與其他節(jié)點的關系，用虛擬的斜紋格子表示，每個節(jié)點在矩陣中的數(shù)值為0，因一個節(jié)點的虛擬斜紋外層有八個方向（雙向通行道僅占一個方向）可以與另一個節(jié)點相連，故對于絕大多數(shù)城市道路的通行方向都可以包含，若后續(xù)研究中遇到更復雜的路口相連情況（如高架橋），可以將其路網(wǎng)分層，引入三（多）維矩陣進行分析。

斜紋格子在整個柵格地圖中是不存在的，本文建立七維坐標用以刻畫局部柵格地圖在局部區(qū)域與整體區(qū)域間的復雜相互關系，其坐標表示為：

其中，[Dr]表示節(jié)點的方向連通屬性，從右往左每一位依次表示正東、東北、正北、西北、正西、西南、正南、東南等，0表示該方位可達;[Ds]表示兩個節(jié)點間的曼哈頓距離，每三位對應[Dr]中的一個方位，其進制為六十四位、單位為米;[Dm]表示此節(jié)點在局部地圖中的標號，[Dx]、[Dy]表示行標、列標，[Dpx]、[Dpy]表示行標、列標相對于絕對坐標的偏移量。

這里用假定的數(shù)值來對坐標各參數(shù)進行解釋：

柵格地圖每一格所對應的實際物理長度可依據(jù)需要重新定義，式⑵坐標各參數(shù)代表距離正東的節(jié)點2379米、距離正北的節(jié)點632米、距離正南的節(jié)點1365米;此節(jié)點在局部地圖中的標號為2，行標為100、偏移量為891，列標為37、偏移量為657。

2.3 地圖的壓縮與還原

如圖2所示，地圖壓縮的過程即去除全為流點的行或列，為奧賽羅坐標化的緊鄰工序。

而地圖的拼接則指在絕對坐標 下，柵格地圖兩兩重新增（減）行（列）后組合成新的柵格地圖的過程。地圖的壓縮與奧賽羅坐標化算法偽代碼如下。

算法2 地圖壓縮與奧賽羅坐標化

Input： longitude1， latitude1， longitude2， latitude2，…， longitude_n， latitude_n

Output： Raster map

Begin

1 Cov_coo = Algorithm 1（input_point）

2 for direction in one-around_point：

While not beyond borders：

if another point is available：

Distance = Euclidean distance

Direction = direction

3 Othello_coo = （Cov_coo ， Distance， Direction， …）

4 Result_map = zip（map_Othello（i，j））

5 return Result

End

地圖的還原過程為提取還原范圍內(nèi)的節(jié)點坐標中的行號、列號及其偏移量等信息，以指定規(guī)格構建柵格矩陣、用流點填充節(jié)點間柵格的方式生成全局地圖。

2.4 地圖的拼接與更新

奧賽羅坐標中的行、列偏移量為多地圖間的拼接和更新提供了標準，當某一區(qū)域的道路狀況發(fā)生變化時，可依據(jù)該區(qū)域變化后的坐標重新生成局部地圖，并對坐標各值進行更新，以規(guī)格最大的局部地圖作為基圖，之后以地圖為單位整體拼接。地圖更新算法的偽代碼如下所示。

算法3 地圖拼接與更新算法

Input： Raster_map1， Raster_map2，…， Raster_map_n

Output： Raster_map_new

Begin

1 for i in range（n）：

Raster_map_i_global = unzip（Raster_map_i）

for nodes in map_1 and map_i：

if the same coordinate points exist：

new_coo = XOR（two_points）

elif one of the horizontal and vertical

coordinates is the same：

Deposit row or column

new_coo = XOR（two_points_same_coordinate）

else：

new_coo = point_i

Deposit row and column

Temporary _map = zip（map_1*）

2 Result = combining（Temporary _map）

3 return Result

End

3 實例研究

本章節(jié)以黑龍江省七臺河市的交通網(wǎng)絡為例，展示算法的應用效果。所使用的數(shù)據(jù)選自七臺河市出租車2018年1月27日運營GPS數(shù)據(jù)，共計192，464組不重復的經(jīng)緯度坐標點。

使用傳統(tǒng)方法，將原始數(shù)據(jù)平面化處理后生成全局地圖，其大小為43784*24582的矩陣，其導出的csv格式文件大小為4，305，436，484 字節(jié);而使用本文方法生成的地圖為956*947的矩陣，導出的csv格式文件大小為3，690，426字節(jié)，僅占處理前文件大小的約0.086%，壓縮過程約用時55.2秒。

圖3和圖4展示了實際路網(wǎng)和轉換得到的柵格路網(wǎng)，可以看到轉換之后的地圖保留了真實路網(wǎng)的拓撲結構，而同時大大減少了存儲所占用的空間。

柵格化的地圖將道路特點直觀、可視化地呈現(xiàn)出來，即使是為減少存儲空間、壓縮后地柵格地圖也可以保留各節(jié)點地相對位置?？蛇_性評價結果可以為區(qū)域韌性交通發(fā)展規(guī)劃的進一步完善提供參考。

4 結束語

本文提出了一種基于GPS點數(shù)據(jù)和柵格地圖的城市路網(wǎng)數(shù)字化方法，結合奧賽羅坐標化，可靈活應用于城市路網(wǎng)的不同場景需求中。實例分析表明，該模型可以在保留相對位置的情況下對城市路網(wǎng)的全局地圖做不同程度的壓縮，以近萬分之九的大小保留源路網(wǎng)的奧賽羅坐標信息。此外，其良好的信息保留、拼接與更新性能，大大提升了其應用場景和范圍。

參考文獻（References）：

[1] Koks E E， Rozenberg J， Zorn C， et al. A global multi-hazard risk analysis of road and railway infrastructure assets[J]. Nature communications，2019.10（1）：1-11

[2] Mahriyar M Z， Rho J H. The compact city concept in creating resilient city and transportation system in Surabaya[J].Procedia-Social and Behavioral Sciences，2014.135：41-49

[3] Bloomberg M. A stronger， more resilient New York[J]. City of New York， PlaNYC Report，2013：69-86

[4] Euler L. Solutio problematis ad geometriam situs pertinentis[J]. Commentarii academiae scientiarum Petropolitanae，1741：128-140

[5] Aho A V， Garey M R， Ullman J D. The transitive reduction of a directed graph[J]. SIAM Journal on Computing，1972.1（2）：131-137

[6] Anez J， De La Barra T， Pérez B. Dual graph representation of transport networks[J].Transportation Research Part B： Methodological，1996.30（3）：209-216

[7] 王雪.基于復雜網(wǎng)絡理論的城市路網(wǎng)特性研究[D].長安大學，2014：20-32

[8] Watanabe D. A study on analyzing the grid road network patterns using relative neighborhood graph[C]. The Ninth International Symposium on Operations Research and Its Applications. Lecture Notes in Operations Research. Beijing， China： World Publishing Corporation，2010：112-119

[9] 黃騫，上官甦，史洪芳等.空間信息技術在韌性交通中的應用思考[J].公路，2018.5：222-227

[10] des Dorides C. GNSS market report[J]. European GNSS Agency， Report，2019.6：8-10

[11] 歐陽鴻，劉建勛，劉毅志等.基于步行GPS軌跡的路網(wǎng)提取方法[J].計算機與現(xiàn)代化，2014.2：124-128

[12] Xu X， Xu Z， Zhao X. Traffic flow visualization using taxi GPS data[C]. International Conference on Advanced Data Mining and Applications. Springer， Cham，2016：811-814

[13] Shi W， Shen S， Liu Y. Automatic generation of road network map from massive GPS， vehicle trajectories[C].2009 12th International IEEE Conference on Intelligent Transportation Systems.IEEE，2009：1-6

[14] 孔慶杰，史文歡，劉允才.基于GPS軌跡的矢量路網(wǎng)地圖自動生成方法[J].中國科學技術大學學報， 2012.42（8）：623-627，647

[15] 丁午，程琳.基于柵格GIS的公交站點覆蓋率算法研究[J].測繪科學，2011.36（4）：249-251

[16] 彭剛，沈宇.一種變柵格地圖的巡檢機器人路徑規(guī)劃方法研究[J].智能機器人， 2017.4：41-43，68

[17] 徐士昊.基于公交車GPS軌跡數(shù)據(jù)動態(tài)生成矢量路網(wǎng)算法的研究[D].山東財經(jīng)大學，2016：27-48

[18] 王少槐.基于GPS軌跡的路網(wǎng)生成與地圖匹配算法研究[D].華南理工大學，2019：27-98