基于GPS数据和压缩栅格算法的城市路网电子地图快速构建方法

刘善武 忽晓阳 李进

摘  要： 路网电子地图对城市交通管理领域有重要的作用，但是地图服务机构提供的接口功能有限，商用地图一般价格高昂;而一些基于GPS数据的地图生成算法非常复杂、速度慢，在一些实际应用中受到限制，如区域地图即时更新、道路临时管制、应急路线规划等。为此提出一种直观、可扩展、操作灵活的城市道路地图构建方式。通过奥赛罗坐标化的方式，对单位栅格的表示方式进行重新设计，在改善栅格地图的拓扑表达能力、弥补栅格地图存储空间较大和处理时运算资源需求较多等弊端的同时，实现了地图的快速构建。文章以公共交通服务评估和路网韧性评价为例，展示了这一方法的应用潜力。

关键词： 数字栅格地图; 地图压缩; 地图拼接

中图分类号：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 引言

路網是整个交通系统的物质基础[1-3]。《哥尼斯堡的七座桥》[4]中的网络图表示法是城市路网的最早表现形式之一，其用节点集表示路口，用边集表示路段。在此基础上衍生出有向图[5]、对偶图[6]、对偶拓扑图[7]、邻近图[8]等方式对地图拓扑结构进行研究。信息化发展的新阶段，地理信息系统相关技术依据空间化建模和信息化分析的优势，在电子地图中发挥着重要的作用[9]。2015年，诺基亚HERE地图以25亿欧元的价格被宝马、奔驰和戴姆勒这三家汽车巨头联合收购，彰显着地图在商业领域越来越重要的地位。

然而，有限的地图接口与商用地图高精度下的高使用率与内存成本，让地图的开发条件与范围有所受限，对于非自动驾驶等低精度地图需求下的导航、路线规划、区域可视化、地理信息标准等应用场景，通过辅助数据自动生成地图，可以进一步提高应用开发使用的灵活性与扩展性，同时缩短了地图的更新周期。全球定位系统（Global Positioning System，GPS）的普及加速了电子地图的发展与应用[10]，已有学者通过一定的方法从GPS轨迹数据中生成道路的拓扑结构[11-13]。而大多数基于GPS生成电子地图的研究都是基于拓扑结构的地图（路网数据基图），对GPS精度要求高，算法复杂[14]。

栅格地图也称光栅图像，一般由图像数据绘制而成，若把栅格图像看作矩阵，矩阵中每一个点的值为图像中对应元素的灰度值，则完成了图像的离散化，在此基础上可以用数字矩阵的形式对地理信息进行抽象化表示。对于许多实际应用来说，栅格地图也能够很好的满足要求，如路线规划设计、设施选址、区域标注、路网管理、交通诱导与可视化分析等情形。

现有栅格地图的生成，主要借助遥感影像[15]、传感器[16]或GPS[14，17-18]这三种方式，前两者受困于技术、人力和经济成本等因素，其较长的更新周期极大限制了市县级以上区域型电子地图的衍生应用。而基于GPS轨迹的路网生成研究，其主要通过轨迹点聚类与分割、中心线拟合、虚拟中间点插值或类似卷积等方式对GPS数据进行处理，进而生成矢量化的路网。在这个过程中，路网在数据预处理后一次生成，即使只是个别数据的更新、也需要载入所有的数据;此外，当表述区域扩大时，其与传统拓扑地图一样，面临着数据量及其存储空间增大的问题。

在面對因事故、灾害等对局部或多个局部交通造成影响的情形时，不可能等待获取整体的GPS轨迹、生成路网后再去响应，也不会将多地分别生成路网去分别响应;对于跨区的资源调配，其对地图的精度需求可进一步降低，此时地理信息系统应更注重其鲁棒性和容错率，在不同的应用背景下可以灵活的应对不同硬件条件下的使用需求与范围。

为解决以上问题，本研究提出一种基于压缩栅格地图的地理信息快速构建方法，以适应于对精度要求不高的地图场景应用，其主要特点有：①通过坐标化路口方向与距离，用更少的数据和存储空间表述节点间的拓扑关系、“压缩”地图的大小、节约系统的运行内存需求;②采用多维坐标设计改进传统栅格表示方式，在解决区域更新需整体重新生成问题的同时、增加单位栅格的信息容量，只需在更新局部地图后，将其拼接并入主图即可完成整体的更新，避免输入全部数据给系统增加不必要的负担;③“压缩”与“还原”灵活可调，可依据场景对道路刻画精确程度做调整，具有良好的扩展性和适应性。本文最后以黑龙江省七台河市为例，检验了快速地图构建的效果。

1 模型原理与符号说明

栅格法原理简单、图形直观并且易于构造和维护，其精度与区域单元格划分大小有关。区域单元划分越小、建模过程中需要存储的数据量越多，处理的复杂度就越高。为解决这一问题，采用绝对坐标转相对坐标的方式，尽可能减少每个局部地图的尺寸，并保留偏移量，为后续局部地图的拼接以及全局地图的还原预留参数。这里对文中出现的定义作详细说明，如表1所示。

2 路网栅格地图的生成

2.1 地图平面化

本文选择墨卡托（G. Mercator）投影法，对经纬度坐标进行平面化处理，即将经纬度坐标映射在笛卡尔直角坐标系上，以便后续处理与管理工作的进行。对于所采集的公交车运营GPS数据来说，其可能因地磁干扰、高大建筑物遮蔽、传输丢包等情况造成各种定位误差，以经纬度距离计算算法为核心将与标准坐标在阈值范围内的、最近的点作为异常GPS数据的校正参考点，其伪代码如下。

算法1 经纬度距离计算算法

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 奥赛罗坐标化设计

传统的栅格地图每个格子用0或1代表“可达”或“障碍”，为压缩栅格地图的规模、提升地图的扩展性和应用场景，本章节设计奥赛罗坐标化方法，对节点所在格子重新赋值。如图1所示，在原节点N1周围虚拟添加新行新列、以在周围产生九个流点（实际上N1与N5等节点仍相邻）。

每一个节点与其他节点的关系，用虚拟的斜纹格子表示，每个节点在矩阵中的数值为0，因一个节点的虚拟斜纹外层有八个方向（双向通行道仅占一个方向）可以与另一个节点相连，故对于绝大多数城市道路的通行方向都可以包含，若后续研究中遇到更复杂的路口相连情况（如高架桥），可以将其路网分层，引入三（多）维矩阵进行分析。

斜纹格子在整个栅格地图中是不存在的，本文建立七维坐标用以刻画局部栅格地图在局部区域与整体区域间的复杂相互关系，其坐标表示为：

其中，[Dr]表示节点的方向连通属性，从右往左每一位依次表示正东、东北、正北、西北、正西、西南、正南、东南等，0表示该方位可达;[Ds]表示两个节点间的曼哈顿距离，每三位对应[Dr]中的一个方位，其进制为六十四位、单位为米;[Dm]表示此节点在局部地图中的标号，[Dx]、[Dy]表示行标、列标，[Dpx]、[Dpy]表示行标、列标相对于绝对坐标的偏移量。

这里用假定的数值来对坐标各参数进行解释：

栅格地图每一格所对应的实际物理长度可依据需要重新定义，式⑵坐标各参数代表距离正东的节点2379米、距离正北的节点632米、距离正南的节点1365米;此节点在局部地图中的标号为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

地圖的还原过程为提取还原范围内的节点坐标中的行号、列号及其偏移量等信息，以指定规格构建栅格矩阵、用流点填充节点间栅格的方式生成全局地图。

2.4 地图的拼接与更新

奥赛罗坐标中的行、列偏移量为多地图间的拼接和更新提供了标准，当某一区域的道路状况发生变化时，可依据该区域变化后的坐标重新生成局部地图，并对坐标各值进行更新，以规格最大的局部地图作为基图，之后以地图为单位整体拼接。地图更新算法的伪代码如下所示。

算法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 实例研究

本章节以黑龙江省七台河市的交通网络为例，展示算法的应用效果。所使用的数据选自七台河市出租车2018年1月27日运营GPS数据，共计192，464组不重复的经纬度坐标点。

使用传统方法，将原始数据平面化处理后生成全局地图，其大小为43784*24582的矩阵，其导出的csv格式文件大小为4，305，436，484 字节;而使用本文方法生成的地图为956*947的矩阵，导出的csv格式文件大小为3，690，426字节，仅占处理前文件大小的约0.086%，压缩过程约用时55.2秒。

图3和图4展示了实际路网和转换得到的栅格路网，可以看到转换之后的地图保留了真实路网的拓扑结构，而同时大大减少了存储所占用的空间。

栅格化的地图将道路特点直观、可视化地呈现出来，即使是为减少存储空间、压缩后地栅格地图也可以保留各节点地相对位置。可达性评价结果可以为区域韧性交通发展规划的进一步完善提供参考。

4 结束语

本文提出了一种基于GPS点数据和栅格地图的城市路网数字化方法，结合奥赛罗坐标化，可灵活应用于城市路网的不同场景需求中。实例分析表明，该模型可以在保留相对位置的情况下对城市路网的全局地图做不同程度的压缩，以近万分之九的大小保留源路网的奥赛罗坐标信息。此外，其良好的信息保留、拼接与更新性能，大大提升了其应用场景和范围。

参考文献（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] 王雪.基于复杂网络理论的城市路网特性研究[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轨迹的路网提取方法[J].计算机与现代化，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轨迹的矢量路网地图自动生成方法[J].中国科学技术大学学报， 2012.42（8）：623-627，647

[15] 丁午，程琳.基于栅格GIS的公交站点覆盖率算法研究[J].测绘科学，2011.36（4）：249-251

[16] 彭刚，沈宇.一种变栅格地图的巡检机器人路径规划方法研究[J].智能机器人， 2017.4：41-43，68

[17] 徐士昊.基于公交车GPS轨迹数据动态生成矢量路网算法的研究[D].山东财经大学，2016：27-48

[18] 王少槐.基于GPS轨迹的路网生成与地图匹配算法研究[D].华南理工大学，2019：27-98