留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

运用Delaunay三角网提取OpenStreetMap主干道多边形

杨伟 艾廷华

杨伟, 艾廷华. 运用Delaunay三角网提取OpenStreetMap主干道多边形[J]. 武汉大学学报 ● 信息科学版, 2018, 43(11): 1725-1731. doi: 10.13203/j.whugis20160294
引用本文: 杨伟, 艾廷华. 运用Delaunay三角网提取OpenStreetMap主干道多边形[J]. 武汉大学学报 ● 信息科学版, 2018, 43(11): 1725-1731. doi: 10.13203/j.whugis20160294
YANG Wei, AI Tinghua. Extracting Arterial Road Polygon from OpenStreetMap Data Based on Delaunay Triangulation[J]. Geomatics and Information Science of Wuhan University, 2018, 43(11): 1725-1731. doi: 10.13203/j.whugis20160294
Citation: YANG Wei, AI Tinghua. Extracting Arterial Road Polygon from OpenStreetMap Data Based on Delaunay Triangulation[J]. Geomatics and Information Science of Wuhan University, 2018, 43(11): 1725-1731. doi: 10.13203/j.whugis20160294

运用Delaunay三角网提取OpenStreetMap主干道多边形

doi: 10.13203/j.whugis20160294
基金项目: 

国家自然科学基金 41531180

详细信息
    作者简介:

    杨伟, 博士生, 主要从事时空大数据挖掘与可视化研究。ywgismap@whu.edu.cn

    通讯作者: 艾廷华, 博士, 教授。tinghua_ai@tom.com
  • 中图分类号: P208

Extracting Arterial Road Polygon from OpenStreetMap Data Based on Delaunay Triangulation

Funds: 

The National Natural Science Foundation of China 41531180

More Information
    Author Bio:

    YANG Wei, PhD candidate, specializes in spatial-temporal data mining and visualization.E-mail:ywgismap@whu.edu.cn

    Corresponding author: AI Tinghua, PhD, professor.E-mail:tinghua_ai@tom.com
图(6)
计量
  • 文章访问数:  1302
  • HTML全文浏览量:  115
  • PDF下载量:  296
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-07-17
  • 刊出日期:  2018-11-05

运用Delaunay三角网提取OpenStreetMap主干道多边形

doi: 10.13203/j.whugis20160294
    基金项目:

    国家自然科学基金 41531180

    作者简介:

    杨伟, 博士生, 主要从事时空大数据挖掘与可视化研究。ywgismap@whu.edu.cn

    通讯作者: 艾廷华, 博士, 教授。tinghua_ai@tom.com
  • 中图分类号: P208

摘要: 众源开放街道地图(OpenStreetMap,OSM)作为志愿者地理信息的典型代表,其数据质量制约了城市主干道提取。为此,引入约束Delaunay三角网,运用类似Voronoi图的空间等剖分几何构造表达道路线密度,通过线密度变化与三角形边长表征主干道形态特征,并集成两个指标构建主干道识别模型;类比林火蔓延扩展过程,提出了基于Delaunay三角网的OSM主干道多边形提取方法。运用5个城市的OSM数据进行实验,结果表明,该方法能有效提取主干道多边形,并且与OSM路网中的道路等级属性趋于一致。

English Abstract

杨伟, 艾廷华. 运用Delaunay三角网提取OpenStreetMap主干道多边形[J]. 武汉大学学报 ● 信息科学版, 2018, 43(11): 1725-1731. doi: 10.13203/j.whugis20160294
引用本文: 杨伟, 艾廷华. 运用Delaunay三角网提取OpenStreetMap主干道多边形[J]. 武汉大学学报 ● 信息科学版, 2018, 43(11): 1725-1731. doi: 10.13203/j.whugis20160294
YANG Wei, AI Tinghua. Extracting Arterial Road Polygon from OpenStreetMap Data Based on Delaunay Triangulation[J]. Geomatics and Information Science of Wuhan University, 2018, 43(11): 1725-1731. doi: 10.13203/j.whugis20160294
Citation: YANG Wei, AI Tinghua. Extracting Arterial Road Polygon from OpenStreetMap Data Based on Delaunay Triangulation[J]. Geomatics and Information Science of Wuhan University, 2018, 43(11): 1725-1731. doi: 10.13203/j.whugis20160294
  • 城市路网主干道作为地理空间数据的组成元素, 体现了路网的骨架结构, 是空间数据库多尺度建模的重要内容。主干道的提取对于路网多尺度表达[1]、地图综合[2]、智能交通服务[3]等具有重要作用。众源开放街道地图(OpenStreetMap, OSM)作为志愿者地理信息[4]的典型代表, 志愿者能够随时编辑提交地理数据到数据库中并快速更新地图。利用OSM数据及其众包制图思想, 从OSM道路数据中提取主干道, 成为地理信息领域感兴趣的问题。

    在高精度城市路网数据中, 高等级主干道将两条或多条车道线独立存储, 表现为多条平行道路的组合[5]。在小比例尺地图中, 这些主干道中的平行车道线需要被合并成单线表示, 该过程的实质是识别平行道路结构模式并提取主干道多边形。主干道结构模式的识别与提取方法可分为两类:①利用道路属性信息提取主干道。文献[6]利用OSITN(OS integrated transport network)数据的弧段和结点要素属性信息准确识别平行道路, 但该方法只适于OSITN数据, 不具有一般性。②根据道路的几何特征计算道路重要性, 划分道路等级以提取主干道。文献[7]通过分析道路街区的延展度、紧凑度和凸度来识别平行道路模式, 但没有给出具体的技术流程; 文献[8]基于缓冲区搜索备选平行路段, 计算平行度来识别平行道路; 文献[9]运用缓冲区增长标识出所有可能的平行道路, 使用启发式跟踪算法提取主干道。以上方法对道路数据的质量要求较高、算法复杂。目前, 已有研究聚焦于OSM数据质量[10], 但从OSM中提取主干道的研究相对较少。文献[5, 11]认为主干道由平行细长的多边形组成, 根据几何形态特征分类多边形, 利用区域扩展算法提取主干道多边形; 但该方法重点关注主干道几何特征, 较少考虑道路线空间分布模式。在道路自动综合、地图多尺度表达领域, 对道路结构模式的研究较多, 如文献[12-13]从道路几何特征、空间分布模式等方面对道路数据进行综合选取、多尺度表达, 但这些方法多关注道路的整体结构模式, 对于平行道路这种微观尺度的局部结构模式研究较少。为此, 本文利用约束Delaunay三角网, 通过骨架线剖分构建道路弧段的Voronoi图来计算道路线密度, 表征道路线密度分布差异, 将道路线密度空间分布模式与道路几何特征结合, 识别平行道路结构模式并提取主干道多边形。

    • 主干道多边形提取的核心是从道路线集中识别平行道路结构模式, 并确定主干道多边形边界, 其本质是空间邻近分析问题。约束Delaunay三角网是空间邻近分析的有力工具, 广泛用于路网模式识别[14]、地图综合[15]、空间邻近探测[16]等。故本文运用约束Delaunay三角网从OSM数据中提取主干道多边形。该方法的过程主要包括:①运用Delaunay三角网及道路弧段Voronoi图计算主干道识别指标并构建识别模型; ②根据识别模型分类三角形, 类比林火蔓延扩展过程, 利用约束Delaunay三角网提取OSM主干道多边形。

    • 1) 线密度变化率。OSM路网中的主干道以多条道路线独立存储, 道路线间相互平行且聚集分布[5]。主干道内部平行线之间距离近, 线密度高; 主干道外部道路线之间距离远, 线密度低。主干道边界作为主干道面域内外的分界线, 其两边的局部线密度差异显著, 线密度变化率成为主干道边界识别的重要指标。道路线密度计算方法包括格网方法、核密度方法、网眼方法、骨架剖分Voronoi图方法[14-15]。骨架剖分Voronoi图方法相比其他方法能更好地表达道路线的局部密度, 并定量描述局部区域的密度差异[14-15], 适用于主干道多边形边界线密度变化率的计算。文献[15]将每条道路弧段以相同速率向外扩张获取生成空间, 直到彼此相遇时终止, 最后每条道路弧段被一个多边形区域包围, 称该多边形区域为道路弧段Voronoi图(图 1(a))。道路弧段的密度即是该弧段长度与弧段Voronoi图单元面积之比。每条道路弧段将Voronoi图区域分割为左右两部分(图 1(b)V1V2), Voronoi图左右单元面积的大小表达了该道路弧段与左右区域中线目标的邻近关系和密度差异。在由道路弧段构建的约束Delaunay三角网中, 位于道路弧段上的三角形边将道路弧段Voronoi图单元分为左右两部分, 该边(Ei)的Voronoi图左右单元面积之比即是该边的线密度变化率(line density change rate, LDCR), 用DEi表示为:

      $$ {D_{{E_i}}} = \frac{{{A_{{\rm{left}}}}}}{{{A_{{\rm{right}}}}}} $$ (1)

      图  1  线密度变化率计算方法

      Figure 1.  The Method for Calculating LDCR

      式中, Aleft、Aright分别表示道路弧段Voronoi图左右单元的面积。本文约定以面积小值比面积大值, 则DEi的值域为(0, 1]。三角形边的DEi值越小, 线密度差异越大, 是主干道多边形边界的可能性就越高。如图 1(b)中道路弧段L2L3DEi值远小于L1, 则L2L3即是主干道边界。利用自然间断点分级法确定LDCR的阈值, 用α表示。若三角形边的DEiα, 则称该边为主干道道路边界, 简称突变边, 用De表示; 反之称为普通边, 用Pe表示。

      2) 边长距离。在道路线构建的约束Delaunay三角网中, 对主干道形态特征单元的识别则转换为对Delaunay三角形的几何特征分析。如图 1(a)所示, 主干道与非主干道区域的三角形边长差异大。故可根据三角网边长差异识别主干道多边形, 计算公式为[17]:

      $$ \beta = {M_{DT}} + \lambda \times {V_{DT}} $$ (2)

      式中, β为边长阈值; MDT为三角网的平均边长; VDT为三角网的边长变异; λ为调节系数, 默认为1, λ值越大, 整体约束越宽松, 反之越严格。如果三角形边长Lβ, 则为非主干道区域的三角形边, 称为长边, 用Le表示; 反之, 则为主干道区域内部的三角形边, 称为短边, 用Se表示。

      3) 主干道多边形识别模型构建。上述两个识别指标在主干道识别过程中具有不同的控制领域和适用条件。OSM道路细节层次丰富(包括车行道、人行道等, 见图 2(a)), 使得由突变边(De)确定的主干道边界具有不连续性、拓扑断开(如图 2(b)AB处)。LDCR阈值作为线密度相对变化的度量指标, 会随着道路线间的空间距离不断变化, 导致非主干道被识别为突变边。LDCR指标适于长弯型、长直型[11]等细长主干道的多边形识别; 对于颗粒型多边形、短小道路线的交叉口等区域则出现道路边界识别错误。边长指标适合于颗粒型、细粒度道路数据的主干道多边形识别。在道路线交叉口处, 三角形边长较小, 边长指标会错误地将这些区域识别为主干道多边形区域(如图 2(b)CD处)。主干道内车道线间的距离不同, 使得全局边长阈值难以顾及这种距离差异, 故本文集成两个识别指标构建主干道多边形识别模型。识别模型如图 2(c)所示, 对于每一条三角形边, 如果是长边(Le)或者突变边(De), 则该边为主干道边界, 称为障碍边。在主干道多边形提取过程中, 还需要根据上下文关系、领域知识等来综合确定障碍边。

      图  2  识别指标集成与识别模型构建

      Figure 2.  Recognition Indexes Integrating and Recognition Model Constructing

    • 对OSM道路线加密[15]后构建约束Delaunay三角网, 根据三角形中障碍边的数目, 将三角形分为4类:只有1条障碍边的为Ⅰ类三角形; 有2条障碍边的为Ⅱ类三角形; 有3条障碍边的为Ⅲ类三角形; 没有障碍边的为Ⅳ类三角形, 如图 3(a)所示。

      图  3  三角形分类及主干道多边形提取算法

      Figure 3.  Classification of Triangles and Extraction of Road Polygons

      根据三角形类型及邻接关系, 本文提出了类比林火蔓延扩展过程的主干道多边形提取算法。算法思想为:类比林火蔓延扩展过程, 将任意Ⅳ类三角形作为林火“火源”, 以“火源”为“种子点”向森林四周不断燃烧, 扩展搜索主干道多边形范围(见图 3(b)); 在保持拓扑连通性的前提下, 从与种子点相连的任意三角形出发, 向三方向扩展; 对于一个三角形来说, 搜索路径为一边进入、两边输出, 因此采用二叉树广度优先遍历三角网, 一旦输出边为障碍边, 则停止该边方向上的搜索。Ⅱ类三角形可看作叶子节点, 只有一边进入, 没有输出; Ⅰ类三角形是拥有一个孩子节点的非叶子节点; Ⅳ类三角形是拥有两个孩子节点的非叶子节点; Ⅲ类三角形为障碍区, 不进行搜索。在算法设计上, 利用栈数据结构递归调用实现算法搜索。

      根据三角形边邻接关系持续扩展直到扩展边均为障碍边, 且所有Ⅳ类三角形都被“燃烧”, 则所有燃烧区域构成的封闭多边形即为提取结果(见图 3(c))。在提取过程中还需要根据上下文关系、三角形类型来综合确定多边形边界, 包括以下几种情形:

      1) 障碍边仍继续扩展。OSM数据的高细节层次特性导致在算法扩展中出现零散分布的孤立障碍边(图 4(a)A)、障碍三角形(图 4(a)B), 这些障碍边及障碍三角形的邻接区域都是已扩展搜索过的区域, 处于活跃状态。针对该情形, 把这些障碍边当做非障碍边继续扩展。在不同等级的主干道连接处, 出现由孤立障碍边和障碍三角形造成的扩展“瓶颈”(见图 4(b)图 4(c))。如果障碍边左右邻接的三角形都处于扩展活跃状态, 则需跨越该障碍边继续扩展(见图 4(b)); 如果障碍三角形的3个邻接三角形中至少有两个处于扩展活跃状态(见图 4(c)), 则将与扩展活跃状态三角形邻接的边作为非障碍边继续扩展。

      图  4  不同特殊情形下的主干道多边形提取

      Figure 4.  Arterial Road Polygon Extraction in Different Special Cases

      2) 非障碍边停止扩展。道路交叉口处有较多横穿主干道的人行道路, 使得平行车道线破碎、短小, 导致LDCR指标难以发挥作用。在扩展搜索过程中, 则以边长指标作为控制条件, 使得搜索的多边形范围超出主干道多边形区域, 出现“扩展泄露”, 如图 4(d)AB处; 对于图 4(d)C处, 由于道路线完整, LDCR指标发挥作用, 则不会出现“泄露”问题。针对该问题, 在扩展搜索过程中需判断停止扩展的三角形边是否为道路线。如果终止搜索的三角形边不是道路线, 则需要从边界处根据三角形邻接关系不断回溯查找, 直到多边形边界的三角形边为道路线为止, 如图 4(d)AB处将非障碍边作为障碍边终止扩展。

      3) 道路交叉口处理。在非平行道路的交叉口处, 边长较小的三角形往往被错误地识别为主干道(见图 4(e))。这些多边形一般位于单线道路交叉口处且面积较小, 通过计算多边形面积与平行度[11]进行剔除。在主干道道路交叉口处, 容易出现多边形孤岛(如图 4(f)中的红色圈出部分), 需将这些多边形孤岛与主干道多边形合并, 以保证提取结果的完整与拓扑联通。

    • 选取北京、成都、武汉、柏林、慕尼黑5个城市中心城区的OSM道路数据进行实验。本实验在不使用道路属性信息的前提下, 从道路线密度空间分布模式和几何形态特征入手, 运用约束Delaunay三角网构建道路弧段的Voronoi图, 计算LDCR和边长指标并构建道路多边形识别模型; 基于林火蔓延扩展思想, 运用Delaunay三角网邻近特性提取主干道多边形。主干道提取结果如图 5所示, 其中浅灰色部分为原始OSM道路网数据, 黑色为利用面积与平行度剔除小面积多边形后最终提取的主干道多边形。将本文方法提取出的主干道与依据目视判别人工选取的平行车道进行比较, 得出本文方法提取主干道的正确率分别是北京92.54%、成都93.21%、武汉93.01%、柏林88.57%、慕尼黑90.41%, 表明本文方法对于方格型、放射型、自由型等不同结构模式的路网提取结果均较好, 并适用于不同丰富程度的OSM数据。图 5中, 北京、慕尼黑的OSM道路与成都、武汉的OSM数据相比, 数据量大, 数据完整度和细节层次更高。

      图  5  主干道多边形提取结果

      Figure 5.  Arterial Road Polygon Extraction Results

      为对比分析实验结果, 将本文提取的主干道数据与官方发布的道路数据的等级属性进行比较, 结果如图 6(a)所示。从图 6(a)可以看出, 本文提取的主干道多边形主要是城市一级道路, 较好地反映了路网中的主干道信息; 但也包含了部分二三级道路, 原因是这些道路在OSM数据中同样以平行车道的形式数字化存储, 这也体现了路网几何结构与属性信息的不一致性。将提取的主干道与OSM数据自身的等级属性信息进行比较分析, 如图 6(b)为北京市主干道与OSM道路等级的比较结果。从图 6(b)可以看出, 提取的主干道主要为一级道路, 反映了平行道路结构模式与主干道形态特征的一致性; 同时也包括了自行车道、步行小路等类型, 主要是由于这些道路线作为一、二级道路的附属设施伴随存在, 如高速路上的紧急通道、上下高速路的转盘等。城市街道低等级道路也会被当做平行道路提取, 主要有两方面原因:一是在公园、广场等处的道路线多以双线、多线的数字化形式存储, 本文算法则会将这种平行结构作为主干道提取; 二是OSM数据的众源和自发性导致出现道路线重复数字化与数据冗余等质量问题。如图 5(b)中的红色处, 重复数字化导致错误地将单线道路识别为主干道多边形。

      图  6  实验结果对比分析

      Figure 6.  Comparative Analysis of the Results

    • 本文针对OSM路网主干道多边形提取问题, 引入Delaunay三角网计算道路弧段的LDCR和边长距离来构建主干道多边形识别模型, 根据三角形类型及邻接关系提取主干道。选取5个城市的OSM道路数据进行实验, 结果表明, 该方法能有效地识别和提取主干道多边形, 且与道路等级属性趋于一致。由于数据的复杂性, 一些不属于主干道的多边形可能被错误地提取, 且提取结果中包含了不同等级的道路。如何利用语义信息对错误的识别结果进行有效区分需要深入研究。另外, 随着众源轨迹数据的泛在获取, 如何将轨迹数据中所蕴含的道路信息与路网主干道数据进行整合分析将是下一步的研究重点。

参考文献 (17)

目录

    /

    返回文章
    返回