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

劉善武 忽曉陽 李進(jìn)

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

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

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

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

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

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

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

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

1 模型原理與符號(hào)說明

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

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

2.1 地圖平面化

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

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

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 奧賽羅坐標(biāo)化設(shè)計(jì)

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

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

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

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

這里用假定的數(shù)值來對(duì)坐標(biāo)各參數(shù)進(jìn)行解釋：

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

2.3 地圖的壓縮與還原

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

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

算法2 地圖壓縮與奧賽羅坐標(biāo)化

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é)點(diǎn)坐標(biāo)中的行號(hào)、列號(hào)及其偏移量等信息，以指定規(guī)格構(gòu)建柵格矩陣、用流點(diǎn)填充節(jié)點(diǎn)間柵格的方式生成全局地圖。

2.4 地圖的拼接與更新

奧賽羅坐標(biāo)中的行、列偏移量為多地圖間的拼接和更新提供了標(biāo)準(zhǔn)，當(dāng)某一區(qū)域的道路狀況發(fā)生變化時(shí)，可依據(jù)該區(qū)域變化后的坐標(biāo)重新生成局部地圖，并對(duì)坐標(biāo)各值進(jìn)行更新，以規(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 實(shí)例研究

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

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

圖3和圖4展示了實(shí)際路網(wǎng)和轉(zhuǎn)換得到的柵格路網(wǎng)，可以看到轉(zhuǎn)換之后的地圖保留了真實(shí)路網(wǎng)的拓?fù)浣Y(jié)構(gòu)，而同時(shí)大大減少了存儲(chǔ)所占用的空間。

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

4 結(jié)束語

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

參考文獻(xiàn)（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] 王雪.基于復(fù)雜網(wǎng)絡(luò)理論的城市路網(wǎng)特性研究[D].長(zhǎng)安大學(xué)，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] 黃騫，上官甦，史洪芳等.空間信息技術(shù)在韌性交通中的應(yīng)用思考[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].計(jì)算機(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)地圖自動(dòng)生成方法[J].中國科學(xué)技術(shù)大學(xué)學(xué)報(bào)， 2012.42（8）：623-627，647

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

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

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

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