留言板

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

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

利用路段连接图识别道路网中的格网模式

李豪 郭黎 王云阁 姜晶莉

李豪, 郭黎, 王云阁, 姜晶莉. 利用路段连接图识别道路网中的格网模式[J]. 武汉大学学报 ( 信息科学版), 2022, 47(1): 126-132. doi: 10.13203/j.whugis20190300
引用本文: 李豪, 郭黎, 王云阁, 姜晶莉. 利用路段连接图识别道路网中的格网模式[J]. 武汉大学学报 ( 信息科学版), 2022, 47(1): 126-132. doi: 10.13203/j.whugis20190300
LI Hao, GUO Li, WANG Yunge, JIANG Jingli. Grid Pattern Recognition in Road Networks Using Link Graph[J]. Geomatics and Information Science of Wuhan University, 2022, 47(1): 126-132. doi: 10.13203/j.whugis20190300
Citation: LI Hao, GUO Li, WANG Yunge, JIANG Jingli. Grid Pattern Recognition in Road Networks Using Link Graph[J]. Geomatics and Information Science of Wuhan University, 2022, 47(1): 126-132. doi: 10.13203/j.whugis20190300

利用路段连接图识别道路网中的格网模式

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

国家自然科学基金 41471314

详细信息
    作者简介:

    李豪,硕士,主要从事路网模式识别与道路匹配研究。1017920864@qq.com

    通讯作者: 郭黎,博士,副教授。gl_750312@163.com
  • 中图分类号: P208

Grid Pattern Recognition in Road Networks Using Link Graph

Funds: 

The National Natural Science Foundation of China 41471314

More Information
    Author Bio:

    LI Hao, master, specializes in the road networks pattern recognition and road matching. E-mail: 1017920864@qq.com

    Corresponding author: GUO Li, PhD, associate professor. E-mail: gl_750312@163.com
  • 摘要: 提出一种基于路段连接图的格网模式识别方法。该方法以路段连接对作为研究的基本单元,以节点路段为点,路段的连接为边用路段连接图表达道路网。将在道路网中识别格网转化为在路段连接图中搜索格网回路。提出了描述路段连接对几何与连接关系的5个参量,用于筛选图中符合格网特点的节点和边。设计了图搜索的约束条件,使用广度优先遍历搜索连接关系图中的回路,完成了格网模式的提取。试验结果表明,该方法能够有效地识别格网模式。
  • 图  1  道路网及图结构描述示例

    Figure  1.  Example of Road Network and Graph Representation

    图  2  连接对参量提取

    Figure  2.  Link Pairs Parameters Extraction

    图  3  化简后的图结构和道路网

    Figure  3.  Simplified Graph and Road Network

    图  4  道路网及部分路段连接图

    Figure  4.  Road Network and Part of Link Graphs

    图  5  化简后的路段连接图

    Figure  5.  Simplified Link Graph

    图  6  格网模式识别结果

    Figure  6.  Grid Pattern Recognition Results

    图  7  文献[12]提出的算法的识别结果

    Figure  7.  Recognition Results of Experiments Using Yang's Algorithm

    图  8  识别复杂道路网中的格网

    Figure  8.  Recognize Grid in Complex Road Network

    表  1  部分路段连接对特征

    Table  1.   Indexes Values of Partial Link Pairs

    连接对 Rω Rl Rc Ra p
    17-28 1.001 0.217 86.723 83.294 14
    550-549 1.000 0.644 0.138 90.335 356
    1 535-1 570 1.000 0.488 94.73 82.094 945
    2 539-2 880 1.012 0.927 50.574 178.500 1 560
    2 432-2 462 1.004 0.326 3.641 85.469 1 491
    3 659-4 112 1.000 0.516 0.067 82.983 2 234
    5 052-5 468 1.006 0.538 28.872 90.551 3 036
    6 694-6 695 1.107 0.357 75.627 88.568 4 065
    9 660-9 659 1.097 0.376 44.485 81.466 7 812
    下载: 导出CSV
  • [1] Heinzle F, Anders K H, Sester M. Automatic Detection of Patterns in Road Networks-Methods and Evaluation[C]//Joint Workshop Visualization and Exploration of Geospatial Data, Stuttgart, Germany, 2007
    [2] Heinzle F, Anders K H, Sester M. Pattern Recognition in Road Networks on the Example of Circular Road Detection[M]//Raubal M, Miller H, Frank A. Geographic Information Science, Berlin, Germany: Springer-Verlag, 2006
    [3] Wang X S, You S K, Wang L. Classifying Road Network Patterns Using Multinomial Logit Model[J]. Journal of Transport Geography, 2017, 58: 104‍‐112 doi:  10.1016/j.jtrangeo.2016.11.013
    [4] Yang B S, Luan X C, Li Q Q. Generating Hierarchical Strokes from Urban Street Networks Based on Spatial Pattern Recognition[J]. International Journal of Geographical Information Science, 2011, 25(12): 2025-2050 doi:  10.1080/13658816.2011.570270
    [5] Zhang Q. Modeling Structure and Patterns in Road Network Generalization[C]//Workshop on Generalisation and Multiple Representation, Leicester, UK, 2004
    [6] 田晶, 宋子寒, 艾廷华. 运用图论进行道路网网格模式提取[J]. 武汉大学学报·信息科学版, 2012, 37(6): 724-727 http://ch.whu.edu.cn/article/id/234

    Tian Jing, Song Zihan, Ai Tinghua. Grid Pattern Extraction in Road Networks with Graph[J]. Geomatics and Information Science of Wuhan University, 2012, 37(6): 724-727 http://ch.whu.edu.cn/article/id/234
    [7] 何亚坤, 艾廷华, 杜欣, 等. 网络空间向量剖分法识别城市路网网格模式[J]. 武汉大学学报·信息科学版, 2018, 43(1): 138-144 doi:  10.13203/j.whugis20150757

    He Yakun, Ai Tinghua, Du Xin, et al. Grid Pattern Recognition in Street Network Space by Vector Tessellation Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(1): 138-144 doi:  10.13203/j.whugis20150757
    [8] Louf R, Barthelemy M. A Typology of Street Patterns[J]. Journal of the Royal Society Interface, 2014, 11(101): 924-933
    [9] 巩现勇, 武芳, 焦洋洋, 等. 基于关联规则分类的道路网网格模式识别[J]. 测绘科学技术学报, 2013, 30(6): 633-637 doi:  10.3969/j.issn.1673-6338.2013.06.020

    Gong Xianyong, Wu Fang, Jiao Yangyang, et al. The Association Rule Based Classification Approach to Grid Pattern Recognition in Road Networks[J]. Journal of Geomatics Science and Technology, 2013, 30(6): 633-637 doi:  10.3969/j.issn.1673-6338.2013.06.020
    [10] 杨必胜, 张云菲, 栾学晨. 保持几何模式的城市道路格网简化方法[J]. 中国图象图形学报, 2012, 17(1): 150-156 https://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB201201022.htm

    Yang Bisheng, Zhang Yunfei, Luan Xuechen. Pattern Preserving Method for Grid Simplification in Road Networks[J]. Journal of Image and Graphics, 2012, 17(1): 150-156 https://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB201201022.htm
    [11] Heinzle F, Anders K H, Sester M. Graph Based Approaches for Recognition of Patterns and Implicit Information in Road Networks[C]// The 22nd International Cartographic Conference, A Coruna, Spain, 2005
    [12] Yang B S, Luan X C, Li Q Q. An Adaptive Method for Identifying the Spatial Patterns in Road Networks[J]. Computers, Environment and Urban Systems, 2010, 34(1): 40-48 doi:  10.1016/j.compenvurbsys.2009.10.002
    [13] 田晶, 艾廷华, 丁绍军. 基于C4.5算法的道路网网格模式识别[J]. 测绘学报, 2012, 41(1): 121-126 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201201024.htm

    Tian Jing, Ai Tinghua, Ding Shaojun. Grid Pattern Recognition in Road Networks Based on C4.5 Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1): 121-126 https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201201024.htm
    [14] 田晶, 何遒, 周梦杰. 运用主成分分析识别道路网中的网格模式[J]. 武汉大学学报·信息科学版, 2013, 38(5): 604-607 http://ch.whu.edu.cn/article/id/2638

    Tian Jing, He Qiu, Zhou Mengjie. Gird Pattern Recognition in Road Network Using Principal Component Analysis[J]. Geomatics and Information Science of Wuhan University, 2013, 38(5): 604-607 http://ch.whu.edu.cn/article/id/2638
    [15] 田晶, 张泊宇, 杨雯雨. 对自组织映射聚类实现道路网网格模式识别[J]. 武汉大学学报·信息科学版, 2013, 38(11): 1330-1334 http://ch.whu.edu.cn/article/id/2804

    Tian Jing, Zhang Boyu, Yang Wenyu. Gird Pattern Recognition Based on Clustering of Self-Organizing Maps[J]. Geomatics and Information Science of Wuhan University, 2013, 38(11): 1330-1334 http://ch.whu.edu.cn/article/id/2804
    [16] 田晶, 艾廷华, 雷华清. 运用自组织映射识别街道网中的网格模式[J]. 武汉大学学报·信息科学版, 2012, 37(3): 362-365 http://ch.whu.edu.cn/article/id/158

    Tian Jing, Ai Tinghua, Lei Huaqing. Recognition of Grid Pattern in Street Network Using Self-Organizing Maps[J]. Geomatics and Information Science of Wuhan University, 2012, 37(3): 362-365 http://ch.whu.edu.cn/article/id/158
    [17] Jiang B, Liu C. Street-Based Topological Representations and Analyses for Predicting Traffic Flow in GIS[J]. International Journal of Geographical Information Science, 2009, 23(9): 1119-1137 doi:  10.1080/13658810701690448
    [18] Porta S, Crucitti P, Latora V. The Network Analysis of Urban Streets: A Dual Approach[J]. Physica A: Statistical Mechanics and Its Applications, 2006, 369(2): 853-866 doi:  10.1016/j.physa.2005.12.063
    [19] 沈敬伟, 刘德儿, 周廷刚, 等. 基于对偶图的道路网络空间邻近关系分析初探[J]. 地理与地理信息科学, 2017, 33(3): 1-4 doi:  10.3969/j.issn.1672-0504.2017.03.001

    Shen Jingwei, Liu De'er, Zhou Tinggang, et al. A Preliminary Study on Spatial Neighbor Relation Analysis Based on Dual Graph for Road Network[J]. Geography and Geo-Information Science, 2017, 33(3): 1-4 doi:  10.3969/j.issn.1672-0504.2017.03.001
    [20] Jiang B, Claramunt C. A Structural Approach to the Model Generalization of an Urban Street Network[J]. GeoInformatica, 2004, 8(2): 157-171 doi:  10.1023/B:GEIN.0000017746.44824.70
    [21] 翟仁健, 武芳, 黄博华, 等. 城市道路网面域层次结构特征的识别与表达[J]. 测绘科学技术学报, 2014, 31(4): 413-418 doi:  10.3969/j.issn.1673-6338.2014.04.018

    Zhai Renjian, Wu Fang, Huang Bohua, et al. A Method for Recognition and Representation of Areal Hierarchy of Urban Road Networks[J]. Journal of Geomatics Science and Technology, 2014, 31(4): 413-418 doi:  10.3969/j.issn.1673-6338.2014.04.018
  • [1] 赵庆志, 姚宜斌, 辛林洋.  融合ECMWF格网数据的水汽层析精化方法 . 武汉大学学报 ( 信息科学版), 2021, 46(8): 1131-1138. doi: 10.13203/j.whugis20190323
    [2] 李涌涛, 李建文, 魏绒绒, 师一帅, 张硕, 车通宇.  全球电离层TEC格网时空变化特性分析 . 武汉大学学报 ( 信息科学版), 2020, 45(5): 776-783. doi: 10.13203/j.whugis20180431
    [3] 林恒, 龚威, 史硕.  利用等边长正交格网进行层次聚合聚类 . 武汉大学学报 ( 信息科学版), 2018, 43(5): 786-791. doi: 10.13203/j.whugis20150668
    [4] 赵龙飞, 赵学胜, 朱思坤, 付瑞全.  一种球面退化四叉树格网的多层次邻近搜索算法 . 武汉大学学报 ( 信息科学版), 2018, 43(4): 529-535. doi: 10.13203/j.whugis20150611
    [5] 王磊, 赵学胜, 官亚勤, 赵龙飞.  QTM格网空间中的球面Voronoi图并行生成算法 . 武汉大学学报 ( 信息科学版), 2017, 42(5): 691-696. doi: 10.13203/j.whugis20140910
    [6] 佘冰, 朱欣焰, 刘汝倩, 呙维.  利用方向玫瑰图分析社会经济重心轨迹移动模式 . 武汉大学学报 ( 信息科学版), 2016, 41(8): 1055-1059. doi: 10.13203/j.whugis20140417
    [7] 雷海军, 谢莲花, 何业军, 朱国云.  AVS菱形搜索运动估计算法优化 . 武汉大学学报 ( 信息科学版), 2012, 37(3): 374-377.
    [8] 钟何平, 唐劲松, 张森, 陈鸣.  利用量化质量图和优先队列的快速相位解缠算法 . 武汉大学学报 ( 信息科学版), 2011, 36(3): 342-345.
    [9] 吴小平, 陈苏红, 赵文光, 王定涛.  市政排水管网节点汇水面积自动化计算的方法和应用 . 武汉大学学报 ( 信息科学版), 2011, 36(3): 355-357.
    [10] 文银平, 胡志祥, 赵文光, 朱宏平.  利用网格搜索进行地球椭球面闪电定位 . 武汉大学学报 ( 信息科学版), 2010, 35(9): 1057-1060.
    [11] 王春, 刘学军, 汤国安, 陶旸.  格网DEM地形模拟的形态保真度研究 . 武汉大学学报 ( 信息科学版), 2009, 34(2): 146-149.
    [12] 赵学胜, 崔马军, 李昂, 张美娟.  球面退化四叉树格网单元的邻近搜索算法 . 武汉大学学报 ( 信息科学版), 2009, 34(4): 479-482.
    [13] 卢秀山, 黄磊.  基于激光扫描数据的建筑物信息格网化提取方法 . 武汉大学学报 ( 信息科学版), 2007, 32(10): 852-855.
    [14] 王建, 杜道生.  规则格网DEM自动综合方法的评价 . 武汉大学学报 ( 信息科学版), 2007, 32(12): 1111-1114.
    [15] 孙文彬, 赵学胜.  基于Quaternary编码的球面三角格网邻近搜索算法 . 武汉大学学报 ( 信息科学版), 2007, 32(4): 350-352.
    [16] 童晓冲, 贲进, 张永生.  基于二十面体剖分格网的球面实体表达与Voronoi图生成 . 武汉大学学报 ( 信息科学版), 2006, 31(11): 966-970.
    [17] 白建军, 赵学胜, 陈军.  基于线性四叉树的全球离散格网索引 . 武汉大学学报 ( 信息科学版), 2005, 30(9): 805-808.
    [18] 李德仁, 邵振峰, 朱欣焰.  论空间信息多级格网及其典型应用 . 武汉大学学报 ( 信息科学版), 2004, 29(11): 945-950.
    [19] 梅雪良, 张祖勋, 张剑清.  最大集团图搜索法用于关系结构约束的全局等高线断线连接 . 武汉大学学报 ( 信息科学版), 1995, 20(2): 101-105.
    [20] 郑肇葆.  影象遮蔽区的自动搜索方法 . 武汉大学学报 ( 信息科学版), 1988, 13(4): 71-75.
  • 加载中
图(8) / 表(1)
计量
  • 文章访问数:  505
  • HTML全文浏览量:  147
  • PDF下载量:  55
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-10-12
  • 刊出日期:  2022-01-05

利用路段连接图识别道路网中的格网模式

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

    国家自然科学基金 41471314

    作者简介:

    李豪,硕士,主要从事路网模式识别与道路匹配研究。1017920864@qq.com

    通讯作者: 郭黎,博士,副教授。gl_750312@163.com
  • 中图分类号: P208

摘要: 提出一种基于路段连接图的格网模式识别方法。该方法以路段连接对作为研究的基本单元,以节点路段为点,路段的连接为边用路段连接图表达道路网。将在道路网中识别格网转化为在路段连接图中搜索格网回路。提出了描述路段连接对几何与连接关系的5个参量,用于筛选图中符合格网特点的节点和边。设计了图搜索的约束条件,使用广度优先遍历搜索连接关系图中的回路,完成了格网模式的提取。试验结果表明,该方法能够有效地识别格网模式。

English Abstract

李豪, 郭黎, 王云阁, 姜晶莉. 利用路段连接图识别道路网中的格网模式[J]. 武汉大学学报 ( 信息科学版), 2022, 47(1): 126-132. doi: 10.13203/j.whugis20190300
引用本文: 李豪, 郭黎, 王云阁, 姜晶莉. 利用路段连接图识别道路网中的格网模式[J]. 武汉大学学报 ( 信息科学版), 2022, 47(1): 126-132. doi: 10.13203/j.whugis20190300
LI Hao, GUO Li, WANG Yunge, JIANG Jingli. Grid Pattern Recognition in Road Networks Using Link Graph[J]. Geomatics and Information Science of Wuhan University, 2022, 47(1): 126-132. doi: 10.13203/j.whugis20190300
Citation: LI Hao, GUO Li, WANG Yunge, JIANG Jingli. Grid Pattern Recognition in Road Networks Using Link Graph[J]. Geomatics and Information Science of Wuhan University, 2022, 47(1): 126-132. doi: 10.13203/j.whugis20190300
  • 道路网是城市的基础骨架,体现了城市的面貌和基本形态。道路模式是指空间分布可以明确命名且能够识别的道路形状和排列。道路模式反映了道路的分布特征,蕴含着城市变化的历史信息,影响着未来城市发展的走向。道路网中主要存在路链模式、格网模式、星状模式和环状模式[1]4种基本模式。识别道路网的空间模式有助于路网匹配、制图综合、地理可视化和城市空间结构分析等方面研究,有助于道路网的设计与交通运输效率的提高[2]

    格网模式是经典的道路模式,由两组平行的道路垂直相交构成[3]。当前识别格网模式的方法按照识别依据可以分为基于道路线要素特征和基于网眼多边形特征两类。基于道路线要素特征的识别方法是从道路选取的角度出发[4-5],根据道路线要素的几何特征,在道路网中识别出相互垂直且相邻的道路。田晶等[6]将道路的方位、连接关系等用图结构表达,运用交、联、提取连通分量和极大完全子图等图论算法完成格网提取。基于道路线要素特征的识别方法从全局出发,着眼于分析构成格网的道路的整体形态特征,容易忽视或错误识别局部格网[7]。由于人们观察道路网时,更加关注道路网眼的形状和分布[8],因此,当前识别格网模式的研究多是基于网眼多边形的。

    基于网眼多边形特征的格网模式识别本质是通过网眼的几何、排列等特征判断多边形是否属于网格[9-10]。Heinzle等[11]定位节点度为4的网眼,通过网眼中心的排列和面积识别格网结构。Yang等[12]综合利用网眼多边形的主方向、排列一致性、形状相似性和格网系数描述网眼特征识别格网结构。田晶等[13-16]将格网模式的识别看作是考虑上下文关系的分类问题,使用机器学习算法识别格网模式。基于网眼多边形特征的方法从局部考虑格网模式识别的问题,忽略了格网的整体特征,只考虑格网自身形态和最多一阶邻近的网眼。识别的准确度依赖于网眼构建的质量。何亚坤等[7]使用栅格单元剖分道路网,通过分析剖分后栅格单元的局部结构特征,使用支持向量机(support vector machine,SVM)识别并提取网格模式,但方法计算较为复杂。

    分析上述两类研究方法可以发现,研究对象的粒度影响格网识别的效果。道路的粒度较大,格网一般是由道路的部分路段组成,而这部分路段可能占整条道路的比例并不大,因此,整条道路线的特征无法精确地反映构成格网的部分路段的形态。网眼多边形的粒度较小,但这种方法仅考虑单个网眼多边形的特征,无法识别由多个不规则的网眼多边形拼接而成的格网矩形。

    节点路段是指道路网中相邻节点间的路段,是道路线和网眼多边形的组成部分。节点路段能够精准地描述格网中路段的几何特征,但难以量化路段间的连接关系特征,因此,本文以任意两条相连的节点路段为研究对象,将其命名为连接对,尝试用图结构表达节点路段的连接关系,利用连接对的几何与连接特征和图的回路搜索算法实现格网模式识别。

    • 道路网是指在一定区域内,由道路相互联通构成的道路系统。在实际研究中,道路并没有一个准确的定义,一条道路既可以指相邻交叉口之间的路段,也可以是指名字相同的路段。为了统一道路网的表达,本文以节点路段为点,路段之间的连接为边构造路段连接图,以图结构描述道路网[17-19]。在路段连接图中,每个节点表示道路网中的一条节点路段,如果两个节点之间的边存在,则说明这两个节点所对应的路段相互连接[20]图 1是道路网及其对应的路段连接图的示例。

      图  1  道路网及图结构描述示例

      Figure 1.  Example of Road Network and Graph Representation

      将道路网转化为路段连接图后,节点路段的连接特征被直观地表达出来。只需要对路段连接图中的边做筛选,即可以排除部分不能构成道路格网的连接对[21]

    • 本文研究对象为任意两条相连的节点路段,即连接对。识别格网结构需要考虑连接对的几何与连接关系特征。构成格网的节点路段一般较为顺直,部分会包含一到两个直角拐角,路段间多以平角或直角相连接。本文根据格网模式的特点,构造了如下5个连接对特征用于格网识别,即形态复杂度Rw、长度比Rl、累计偏转角Rc、连接角Ra和节点编号p

      Rw反映了连接对路段形态的复杂程度。用化简前后连接对长度labsab的比值来表示,如图 2(a)所示。

      图  2  连接对参量提取

      Figure 2.  Link Pairs Parameters Extraction

      考虑到格网模式中的连接对形态通常较为简单,将连接对的两条节点路段连接后看作一条路段,使用经典的Douglas-Peucker线化简算法化简连接对为最多5个节点,突出了连接对路段的整体形态。复杂度是一个大于等于1的值,复杂度越大,说明影响路段整体形态的节点越多,连接对路段越不可能构成格网。复杂度的计算公式为:

      Rw=labsab

      Rl用于描述连接对两条节点路段的相对大小,用路段直线长度的比值表示,取值范围为[0, 1]。组成格网的连接对,其两条节点路段长度差距不宜过大。使用这项指标可以排除不属于格网模式的细长矩形。长度比的计算公式为:

      Rl=dadb, dadb

      Rc描述连接对角度偏转的程度,通过叠加节点路段在每个转折点处的偏转角度获得。构成格网的节点路段可能包含数个直角拐角,使用累计偏转角可以将路段内部角度变化的特征体现出来。设一条节点路段根据其n个折点可以划分为a0, a1ann+1条子路段,θa0, a1表示子路段a0a1间的偏转角,则该路段的累计偏转角就是所有θai, ai+1的和,如图 2(b)所示。由于每个连接对由两条路段组成,因此,将两条路段的累计偏转角相加作为整个连接对的累计偏转角。对于路段ab组成的连接对,其累计偏转角计算公式为:

      Rc=i=1nθai-1, ai+i=1mθbi-1, bi

      Ra是指连接对两条节点路段所构成的夹角,是格网识别的重要依据。格网模式中节点路段的连接角存在90°和180°两种情况。夹角为90°的连接对构成了格网的一个拐角,夹角为180°的连接对构成了格网的一条边。以路段交点为起点,到路段两端p1p2的向量分别为ab,则连接角的计算公式为:

      Ra=arccosabab

      节点编号p是指连接对两条节点路段相连节点的编号。每一条节点路段都有两端,路段连接图用节点和边表示路段和连接关系,但是无法体现连接位置信息,即连接的是路段的哪一端,因此,使用连接点编号表示连接对的连接位置。

      将形态复杂度、长度比、累计偏转角、连接角和节点编号5个连接对特征作为边的属性加入路段连接图,用于后续格网的搜索。

    • 使用图结构表达道路网时,格网可以看作是符合某种约束的简单回路。通过搜索连接关系图中所有满足特定约束的回路可以提取出格网。广度优先搜索(breadth first search,BFS)是图搜索算法的一种,是指按照广度优先的遍历策略展开并检查图中所有节点。图搜索算法一般用于寻找某两个节点之间符合条件的路径,将广度优先搜索的目标节点设置为初始节点,即可将图搜索算法用于搜索回路。

      利用图结构识别格网模式有两个关键步骤,分别是图化简以及利用改进的图搜索算法搜索格网回路。在较大的图中搜索回路通常效率低下。为了提高搜索效率,利用连接对的特征对图结构进行化简,减少图的节点数和边数。为了保证搜索到的回路是道路格网,本文根据格网的特点,对搜索过程进行约束,从而改进了搜索算法,使其能够应用于格网识别。

    • 道路网的路段连接图中有着大量的节点和边,表示道路网中的路段和连接。直接在这样庞大复杂的图结构中搜索回路会十分低效。利用连接对特征对图结构进行化简能够有效减少图结构的节点数和边数,甚至可能将图结构拆分成多个子图。

      图化简的依据是上文得到的连接对的特征,可以构成格网的连接对应该符合一定的条件,这些条件可以看作是对连接对特征数值上的约束。需要注意的是,图化简的目的是减少搜索时的计算量,不能因为图的简化而影响回路搜索的结果,所以阈值的设置较为保守,倾向于尽可能保留连接对。

      形态复杂度描述连接对路段形态上的复杂程度,形态复杂度是一个大于1的数值,其值越接近于1,连接对的形态越简单,应排除形态复杂度大于阈值r1的连接对。长度比描述格网路段的相对大小,使用长度比的目的是排除细长矩形,应排除长度比小于阈值r2的连接对。累计偏转角和连接角是对连接对角度特征的描述,其中,累计偏转角计算了构成连接对的两条路段所包含拐角的和,而连接角是连接对两条节点路段的夹角。组成格网的连接对,其连接角应该接近90°或180°。包含拐角的路段,其累计偏转角应该接近90°的整倍数,且小于某一阈值r3,设置算法允许的角度误差为r4。因为当前并没有一个对格网模式严格的定义,所以本文主要采用经验与试验相结合的方式确定阈值r1r4

      本文图结构中,节点的度是指与该节点连接的边数。在利用连接对的特征去除图中的非格网边后,图中可能存在度为0或1的节点。这些节点在道路网中表现为孤立的或只有一条路段连接的路段,不可能构成格网,因此,将这些节点去除。经过化简后,图结构的节点数和边数都会大量减少。图 1中的道路网经过化简后的图结构及其对应的道路如图 3所示。

      图  3  化简后的图结构和道路网

      Figure 3.  Simplified Graph and Road Network

    • 经过图化简,路段连接图的节点数和边数大量减少,庞大的连接图也被分解为多个子图。但是,图化简不能排除所有与格网模式无关的连接对。因为格网是路段构成的回路,所以识别格网模式还需要在化简后的图结构中搜索回路。路段连接图中的回路可能有共点回路、格网回路和不规则回路3种情况。3种回路的定义如下:

      1)共点回路。在路段连接图中,除了首尾相连的路段构成的回路外,还存在共点回路。共点回路中,路段相交于同一道路节点,体现在道路网中一般是道路交叉口,如图 3中由路段38-39-40构成的三路交叉口。

      2)格网回路。是指在道路网中表现为道路格网的回路,如图 3中的回路38-39-22-33。道路格网的特点是有4个直角,并且组成单个格网矩形的节点路段数量较少。格网回路是本文要搜索的回路类型。

      3)不规则回路。除上述两种回路,其余的回路都属于不规则回路。不规则回路在道路网中表现为一组首尾闭合的路段,其构成的道路结构没有统一的形态。

      图搜索的目的是找到路段连接图中的格网回路,但是传统的搜索算法无法区分上述3种回路。为确保搜索到的回路为格网回路,本文根据道路格网角度和边的特征,设计了如下3个条件约束搜索过程:

      1)共点路径约束是指在遍历路段连接图时,一条搜索路径不能存在重复的道路节点。通过记录路径上连接对的节点编号p实现。使用共点路径约束可以保证搜索到的回路不是共点回路。

      2)路径长度约束是对搜索路径长度的限制,如果某条搜索路径达到了最大长度仍没有构成回路,则放弃该条路径,不再进一步搜索。构成单个格网的路段数量不会很多,使用路径长度约束可以控制图搜索规模,减少计算量。

      3)路径偏转角约束是对路径偏转角度总和的限制。回路搜索过程可以想象成在节点路段上的移动。格网回路中,路段角度偏转的总和不大,算法将路径中的每一个偏转角相加,如果偏转角度的和大于设定的最大值仍没有构成回路,则放弃该条路径。角度约束可以有效减少搜索到不规则回路的数量,缩小图搜索的规模。

      在算法实现上,首先,创建一个访问标记数组和先进先出的路径队列;然后,从图中某一未被访问过的节点开始遍历,将符合约束条件的路径入队。在后续的搜索过程中,取出队首路径,在已有路径的末尾节点处向其相邻节点继续延伸,并判断新的路径是否符合上述3个约束条件。如果新的路径满足约束条件,且其首尾节点相同(即构成了回路),则认为该路径为格网回路,将结果保存,同时,将该回路上的所有路段节点标记为已访问。如果路径满足约束条件,但首尾节点不相同,则将该路径加入到队列尾部。当路径队列为空时,在图中寻找一个未访问过的节点,重复上述过程,直到所有节点都被标记为访问过后,算法流程结束。将搜索到的格网回路以连接路段的形式表示,即可提取道路网中的所有格网。

    • 使用Web技术搭建试验平台,后端使用Python构建,实现连接对参量计算,图结构的生成与操作,并在前端可视化图结构和道路网。本文所用的试验数据为深圳市的导航道路数据,如图 4(a)所示。因为全部道路网节点路段的连接图较为复杂,所以只展示部分道路网的路段连接图,如图 4(b)所示。

      图  4  道路网及部分路段连接图

      Figure 4.  Road Network and Part of Link Graphs

      对道路网数据进行预处理,对道路进行拓扑检查,去除道路上的伪节点,并将道路在交叉点处打断。预处理后的道路网由12 697条节点路段组成。将道路网以路段连接图的形式重新组织,得到的连接图共有29 635条边。对连接对的各项参数进行量化,部分结果如表 1所示。

      表 1  部分路段连接对特征

      Table 1.  Indexes Values of Partial Link Pairs

      连接对 Rω Rl Rc Ra p
      17-28 1.001 0.217 86.723 83.294 14
      550-549 1.000 0.644 0.138 90.335 356
      1 535-1 570 1.000 0.488 94.73 82.094 945
      2 539-2 880 1.012 0.927 50.574 178.500 1 560
      2 432-2 462 1.004 0.326 3.641 85.469 1 491
      3 659-4 112 1.000 0.516 0.067 82.983 2 234
      5 052-5 468 1.006 0.538 28.872 90.551 3 036
      6 694-6 695 1.107 0.357 75.627 88.568 4 065
      9 660-9 659 1.097 0.376 44.485 81.466 7 812

      利用计算得到的连接对的特征化简路段连接图,各参数阈值[r1, r4]通过经验和数据确定。从数据中随机采集了部分构成格网的连接对,分析样本连接对的各个特征分布,并结合各连接对参数所反映的格网的特征,确定参数阈值。在试验中,设置形态复杂度、长度比和累计偏转角的阈值分别为1.08、0.1和360°。角度偏差允许在15°以内,即当角度值在[75°,105°]内,可近似为直角,当角度值在[165°,180°]内,可认为是平角,确定格网的累计偏转角的范围为[75°n,105°n],其中,n为自然数。格网连接角的取值范围为[75°,105°]或[165°,180°]。

      图 4(b)所对应的部分道路网的路段连接图按照上述阈值化简,结果如图 5所示。化简后,路段连接图的节点数从2 035减少到1 321,边数从4 874减少到2 434,有效简化了图结构。原本较为连续的连接图被分解为多个子图,这进一步提高了搜索格网回路的效率。

      图  5  化简后的路段连接图

      Figure 5.  Simplified Link Graph

      在化简后的路段连接图中搜索格网回路,为了兼顾搜索效率和识别结果,在人工判别过的样本数据上测试,发现当设置搜索深度为8和最大路径偏转角为540°时,可以得到最佳搜索结果。应用算法于道路数据,最终格网识别的结果如图 6所示。

      图  6  格网模式识别结果

      Figure 6.  Grid Pattern Recognition Results

      为了对比基于路段连接图和基于网眼多边形面状特征识别格网模式的效果,本文实现了Yang等[12]提出的算法,如图 7所示。对试验结果进行评估,使用本文算法识别的准确率为89.13%,召回率为82.49%。而文献[12]提出的算法的准确率为84.15%,召回率为85.82%。可见,基于路段连接图的算法取得了更高的识别准确率。进一步分析发现,本文算法的优点在于能够识别复杂道路网中的格网模式而不受其他路段的干扰。在复杂道路网中,格网网眼的多边形会被干扰道路切割成多个不规则的多边形,而基于路段连接图的算法则会无视干扰道路的影响。如图 8所示,图 8中两个格网的边角存在干扰路段,若构建网眼多边形,则会错误地将一个网眼分解为多个多边形,从而影响识别效果,而基于连接对的识别方法能够正常识别格网模式。其缺点在于,算法难以识别形态上存在连续小幅度变化的格网路段。

      图  7  文献[12]提出的算法的识别结果

      Figure 7.  Recognition Results of Experiments Using Yang's Algorithm

      图  8  识别复杂道路网中的格网

      Figure 8.  Recognize Grid in Complex Road Network

    • 本文提出了一种基于路段连接图和图搜索的格网模式提取方法。以路段连接对为研究的基本单元,提取了连接对的几何与连接关系特征。将道路连接关系表示为图结构,使用图化简和回路搜索识别复杂道路网中的格网模式。但是方法存在较为复杂且计算量大的问题。进一步的研究工作是如何提高算法效率以及拓宽算法适用范围。如使用计算量较小的特征描述连接对,以及使用启发式的图搜索算法提高运算效率。基于路段连接的模式识别方法有着独特的优势,将这种识别方法推广到识别其他路网模式也是下一步研究的方向。

参考文献 (21)

目录

    /

    返回文章
    返回