留言板

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

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

图卷积网络模型识别道路正交网格模式

王米琪 艾廷华 晏雄锋 肖屹

王米琪, 艾廷华, 晏雄锋, 肖屹. 图卷积网络模型识别道路正交网格模式[J]. 武汉大学学报 ● 信息科学版, 2020, 45(12): 1960-1969. doi: 10.13203/j.whugis20200022
引用本文: 王米琪, 艾廷华, 晏雄锋, 肖屹. 图卷积网络模型识别道路正交网格模式[J]. 武汉大学学报 ● 信息科学版, 2020, 45(12): 1960-1969. doi: 10.13203/j.whugis20200022
WANG Miqi, AI Tinghua, YAN Xiongfeng, XIAO Yi. Grid Pattern Recognition in Road Networks Based on Graph Convolution Network Model[J]. Geomatics and Information Science of Wuhan University, 2020, 45(12): 1960-1969. doi: 10.13203/j.whugis20200022
Citation: WANG Miqi, AI Tinghua, YAN Xiongfeng, XIAO Yi. Grid Pattern Recognition in Road Networks Based on Graph Convolution Network Model[J]. Geomatics and Information Science of Wuhan University, 2020, 45(12): 1960-1969. doi: 10.13203/j.whugis20200022

图卷积网络模型识别道路正交网格模式

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

国家自然科学基金 41531180

详细信息

Grid Pattern Recognition in Road Networks Based on Graph Convolution Network Model

Funds: 

The National Natural Science Foundation of China 41531180

More Information
  • 摘要: 街道网作为城市的骨架,其模式识别对于城市景观分析、市政规划、交通流量分析等都具有重要作用,是综合了道路几何特征、语义特征及上下文关系的智能识别问题。道路网模式识别目前主要是基于边-节点的图结构和道路网眼的多边形群结构两种模型,运用相关几何度量和统计指标通过模式识别规则探测获得。由于道路模式表达受人的空间认知、视觉心理影响,具有一定的不确定性和复杂性,基于规则推理与统计分析的方法很难获得与人工判断相一致的结果。在人工智能技术的驱动下,引入一种图结构上的深度学习模型,即图卷积网络,用于识别道路网正交网格模式。先以道路交叉点作为节点、道路连接作为边构建图结构,并划分出网格和非网格两类,作为模型的标注和预测目标; 同时将道路网线性剖分以获取图节点特征,作为模型的输入信息; 然后提取两端点都被预测为网格点的路段,实现网格模式的识别。实验结果表明,该方法中,道路网节点分类的准确率达到89.2%,道路段分类的准确率达到86.1%,能有效用于网格模式识别。
  • 图  1  基于图卷积网络的道路网络网格模式识别整体框架

    Figure  1.  Framework of Grid Pattern Recognition in a Road Network Using Graph Convolution Network

    图  2  基于图结构的道路网络建模和标注

    Figure  2.  Modeling and Labeling of the Road Network Using a Graph Structure

    图  3  节点A的邻域

    Figure  3.  Connection Roads and Neighborhoods of Node A

    图  4  节点A邻域方向分布统计图

    Figure  4.  Direction Distribution of Neighborhoods of Node A

    图  5  直线性

    Figure  5.  Straightness

    图  6  图卷积网络的节点分类模型

    Figure  6.  Node Classification Model of Graph Convolution Network

    图  7  实验区域

    Figure  7.  Experimental Area

    图  8  训练集、验证集的准确度和损失值

    Figure  8.  Accuracies and Loss Changes of the Training Set and Validation Set

    图  9  GCN对道路网格网模式的识别结果

    Figure  9.  Recognition Results of Road Grid Pattern Using GCN

    图  10  模型深度和卷积核数量对准确度的影响

    Figure  10.  Effect of Model Depth and Number of Convolution Kernel on Accuracy

    图  11  项式阶数,邻域范围,线性单元对模型性能的影响

    Figure  11.  Effect of Difference Polynomial Orders, Neighborhoods, and Linear Unit on Accuracy

    图  12  实验区域

    Figure  12.  Experimental Area

    图  13  节点嵌入的演化过程

    Figure  13.  Evolution Process of Node Embedding

    表  1  图节点的特征参量定义

    Table  1.   Definition of Descriptive Variables for Graph Nodes

    分类 特征 计算方法 说明
    连接特征 节点度 Degree of node
    形状特征 直线性 $\begin{array}{l} S = \frac{{\sum \limits_{i = 1}^n {s_i}}}{n}\\ {s_i} = {l_1}/{l_2} \end{array}$ 节点连接路段的直线性的均值
    邻域特征 方向分布指数 $\begin{array}{l} D = \mathop \sum \limits_{i = 1}^{18} {w_i} \cdot {p_i}\\ \;\;\;\;\;\;{w_i} = \\ {\rm{max}}(\left| {{\rm{cos}}\left( {i - a} \right)} \right|, \\ \;\;\;\;\left| {{\rm{cos}}\left( {i - b} \right)} \right|) \end{array}$ 方向区间i包含的线性单元数量的频率为piwii与主方向的接近程度,i越接近主方向,wi越接近1,当i=ab时,wf=1,D越大,节点邻域的线性单元的聚集性越强
    正交指数 $V = {\rm{sin}}\left( {\left| {b - a} \right|} \right)$ V越大,节点邻域内剖分单元正交分布的可能性越大
    下载: 导出CSV

    表  2  道路格网模式识别的混淆矩阵

    Table  2.   Confusion Matrix of Road Grid Pattern Recognition

    GCN 实际网格 实际非网格
    预测网格 1 390 172
    预测非网格 123 1 037
    下载: 导出CSV

    表  3  特征对比混淆矩阵

    Table  3.   Confusion Matrix of Feature Contrast

    GCN 实际网格 实际非网格
    预测网格 1 255 235
    预测非网格 258 974
    下载: 导出CSV

    表  4  GCN与其他算法准确率和召回率对比/%

    Table  4.   Comparison of Accuracy and Recall Rate of the Proposed GCN Model and Other Algorithms/%

    指标 GCN MLP SVM LightGBM
    准确率 89.1 77.8 77.6 77.6
    召回率 91.6 90.4 88.2 88.0
    下载: 导出CSV
  • [1] Jang B. A Topological Pattern of Urban Street Networks: Universality and Peculiarity[J].Physica A: Statistical Mechanics and Its Applications, 2007, 384(2): 647-655 doi:  10.1016/j.physa.2007.05.064
    [2] Zhang Q. Modeling Structure and Patterns in Road Network Generalization[C]. Workshop on Generalisation and Multiple Representation, Leicester, UK, 2004
    [3] Porta S, Crucittip 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
    [4] Wang X, You S, Wang L. Classifying Road Network Patterns Using Multinomial Logit Model[J]. Journal of Transport Geography, 2017, 58(1): 104-112 http://www.sciencedirect.com/science/article/pii/S0966692316307001
    [5] Marshall S. Streets and Patterns[M]. London, the United Kingdom: Routledge, 2004
    [6] 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
    [7] He Y, Ai T, Yu W, et al. A Linear Tessellation Model to Identify Spatial Pattern in Urban Street Networks[J]. International Journal of Geographical Information Science, 2017, 31(8): 1 541-1 561 doi:  10.1080/13658816.2017.1298768
    [8] Ai T, Yu W, He Y. Generation of Constrained Network Voronoi Diagram Using Linear Tessellation and Expansion Method[J]. Computers, Environment and Urban Systems, 2015, 51(5): 83-96 http://smartsearch.nstl.gov.cn/paper_detail.html?id=0ad43d85746fa4786a4f18afddf739b2
    [9] Yang B, Luan X, Li 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
    [10] 杨必胜, 栾学晨.城市道路网几何结构模式的自动识别方法[J].中国图象图形学报, 2009, 14(7):1 251-1 255 http://www.cqvip.com/Main/Detail.aspx?id=30924607

    Yang Bisheng, Luan Xuechen. An Automated Method for Structural Pattern Recognition of Road Networks[J]. Journal of Image and Graphics, 2009, 14(7):1 251-1 255 http://www.cqvip.com/Main/Detail.aspx?id=30924607
    [11] 田晶, 艾廷华, 丁绍军.基于C4.5算法的道路网网格模式识别[J].测绘学报, 2012, 41(1):121-126 http://www.cqvip.com/QK/90069X/20121/40872188.html

    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 http://www.cqvip.com/QK/90069X/20121/40872188.html
    [12] 田晶, 何遒, 周梦杰.运用主成分分析识别道路网中的网格模式[J].武汉大学学报·信息科学版, 2013, 38(5):604-607 http://ch.whu.edu.cn/article/id/2638

    Tian Jing, He Qiu, Zhou Mengjie. Grid 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
    [13] Heinzle F, Anders K H, Sester M. Automatic Detection of Pattern in Road Networks―Methods and Evaluation[C]. Joint Workshop Visualization and Exploration of Geospatial Data, Stuttgart, 2007
    [14] Xie F, Levinson D. Measuring the Structure of Road Networks[J]. Geographical Analysis, 2007, 39(3): 336-356 doi:  10.1111/j.1538-4632.2007.00707.x
    [15] Zhang Y, Wang X, Zeng P, et al.Centrality Characteristics of Road Network Patterns of Traffic Analysis Zones[J]. Transportation Research Record, 2011, 2 256(1): 16-24 doi:  10.3141/2256-03
    [16] Jiang B, Claramunt C. Topological Analysis of Urban Street Networks[J]. Environment and Planning B: Planning and Design, 2004, 31(1): 151-162 doi:  10.1068/b306
    [17] Lecun Y, Bengio Y, Hinton G. Deep Learning[J]. Nature, 2015, 521(7 553): 436
    [18] Yan X, Ai T, Yang M, et al. A Graph Convolutional Neural Network for Classification of Building Patterns Using Spatial Vector Data[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2019, 150(4): 259-273 http://www.sciencedirect.com/science/article/pii/S0924271619300437
    [19] Tobler W R. A Computer Movie Simulating Urban Growth in the Detroit Region[J]. Economic Geography, 1970, 46(sup1): 234-240 doi:  10.2307/143141
    [20] Bruna J, Zaremba W, Szlam A, et al. Spectral Networks and Locally Connected Networks on Graphs[OL].https://arxiv.org/abs/1312.6203arXiv, 2013
    [21] Defferrard M, Bresson X, Vandergheynst P. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering[C].Advances in Neural Information Processing Systems, Barcelona, Spain, 2016
    [22] Hammond D K, Vandergheynst P, Gribonval R. Wavelets on Graphs via Spectral Graph Theory[J]. Applied and Computational Harmonic Analysis, 2011, 30(2): 129-150 doi:  10.1016/j.acha.2010.04.005
    [23] Kipf T N, Welling M. Semi-supervised Classification with Graph Convolutional Networks[OL]. https://arxiv.org/abs1609.02907, 2016
    [24] Glorot X, Bengio Y. Understanding the Difficulty of Training Deep Feed Forward Neural Networks[C]. The 13th International Conference on Artificial Intelligence and Statistics, Sardinia, Italy, 2010
  • [1] 卢剑, 张学东, 张健钦, 郭小刚, 张悦颖.  利用卷积神经网络识别交通指数时间序列模式 . 武汉大学学报 ● 信息科学版, 2020, 45(12): 1981-1988. doi: 10.13203/j.whugis20200035
    [2] 徐江河, 张飞舟, 张立福, 邓楚博, 孙雪剑.  一种综合利用图像和光谱信息的物体真假模式识别方法 . 武汉大学学报 ● 信息科学版, 2019, 44(8): 1174-1181. doi: 10.13203/j.whugis20190139
    [3] 何亚坤, 艾廷华, 杜欣, 禹文豪.  网络空间向量剖分法识别城市路网网格模式 . 武汉大学学报 ● 信息科学版, 2018, 43(1): 138-139. doi: 10.13203/j.whugis20150757
    [4] 范仲鸣, 李精忠, 张小波.  矢量多边形模式识别的小波方法 . 武汉大学学报 ● 信息科学版, 2017, 42(10): 1400-1405, 1416. doi: 10.13203/j.whugis20150688
    [5] 李飞, 栾学晨, 杨必胜, 李秋萍.  高等级道路网的拓扑自动保持方法 . 武汉大学学报 ● 信息科学版, 2014, 39(6): 729-733. doi: 10.13203/j.whugis20140115
    [6] 田晶, 何青松, 颜芬.  道路网stroke生成问题的形式化表达与新算法 . 武汉大学学报 ● 信息科学版, 2014, 39(5): 556-560. doi: 10.13203/j.whugis20120127
    [7] 巩现勇, 武芳, 钱海忠, 马克楠.  建筑群多连通直线模式的参数识别方法 . 武汉大学学报 ● 信息科学版, 2014, 39(3): 335-339. doi: 10.13203/j.whugis20120708
    [8] 田晶, 何遒, 周梦杰.  运用Q统计分析网络空间现象关联模式 . 武汉大学学报 ● 信息科学版, 2014, 39(4): 486-491. doi: 10.13203/j.whugis20120562
    [9] 郭黎, 李宏伟, 张泽建, 张斌.  道路网信息投影匹配方法研究 . 武汉大学学报 ● 信息科学版, 2013, 38(9): 1113-1117.
    [10] 田晶, 张泊宇, 吴荡.  一种矢量道路网辐射模式识别新方法 . 武汉大学学报 ● 信息科学版, 2013, 38(10): 1234-1238.
    [11] 田晶, 何遒, 周梦杰.  运用主成分分析识别道路网中的网格模式 . 武汉大学学报 ● 信息科学版, 2013, 38(5): 604-607.
    [12] 田晶, 张泊宇, 杨雯雨.  对自组织映射聚类实现道路网网格模式识别 . 武汉大学学报 ● 信息科学版, 2013, 38(11): 1330-1334.
    [13] 栾学晨, 杨必胜, 张云菲.  城市道路复杂网络结构化等级分析 . 武汉大学学报 ● 信息科学版, 2012, 37(6): 728-732.
    [14] 田晶, 艾廷华, 雷华清.  运用自组织映射识别街道网中的网格模式 . 武汉大学学报 ● 信息科学版, 2012, 37(3): 362-365.
    [15] 田晶, 宋子寒, 艾廷华.  运用图论进行道路网网格模式提取 . 武汉大学学报 ● 信息科学版, 2012, 37(6): 724-727.
    [16] 董卫华, 李志林, 郭庆胜.  基于动态分段的道路网示意性地图模型综合 . 武汉大学学报 ● 信息科学版, 2010, 35(8): 892-895.
    [17] 陈玉敏, 龚健雅.  基于模糊数学的多因素道路网权值确定算法 . 武汉大学学报 ● 信息科学版, 2007, 32(10): 928-931.
    [18] 王树根.  基于认知心理学的模式识别模型框架 . 武汉大学学报 ● 信息科学版, 2002, 27(5): 543-547.
    [19] 杨挺, 刘友光, 黄幼才.  模式识别在手腕骨自动识别中的应用研究 . 武汉大学学报 ● 信息科学版, 1998, 23(1): 43-46.
    [20] 刘少创, 林宗坚.  基于神经网络的地图数字注记识别 . 武汉大学学报 ● 信息科学版, 1994, 19(3): 194-198.
  • 加载中
图(13) / 表(4)
计量
  • 文章访问数:  854
  • HTML全文浏览量:  171
  • PDF下载量:  121
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-04-02
  • 刊出日期:  2020-12-05

图卷积网络模型识别道路正交网格模式

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

    国家自然科学基金 41531180

    作者简介:

    王米琪,硕士,主要从事地图自动综合研究。wangmiqi1996@whu.edu.cn

    通讯作者: 艾廷华,博士,教授。tinghuaai@whu.edu.cn
  • 中图分类号: P208

摘要: 街道网作为城市的骨架,其模式识别对于城市景观分析、市政规划、交通流量分析等都具有重要作用,是综合了道路几何特征、语义特征及上下文关系的智能识别问题。道路网模式识别目前主要是基于边-节点的图结构和道路网眼的多边形群结构两种模型,运用相关几何度量和统计指标通过模式识别规则探测获得。由于道路模式表达受人的空间认知、视觉心理影响,具有一定的不确定性和复杂性,基于规则推理与统计分析的方法很难获得与人工判断相一致的结果。在人工智能技术的驱动下,引入一种图结构上的深度学习模型,即图卷积网络,用于识别道路网正交网格模式。先以道路交叉点作为节点、道路连接作为边构建图结构,并划分出网格和非网格两类,作为模型的标注和预测目标; 同时将道路网线性剖分以获取图节点特征,作为模型的输入信息; 然后提取两端点都被预测为网格点的路段,实现网格模式的识别。实验结果表明,该方法中,道路网节点分类的准确率达到89.2%,道路段分类的准确率达到86.1%,能有效用于网格模式识别。

English Abstract

王米琪, 艾廷华, 晏雄锋, 肖屹. 图卷积网络模型识别道路正交网格模式[J]. 武汉大学学报 ● 信息科学版, 2020, 45(12): 1960-1969. doi: 10.13203/j.whugis20200022
引用本文: 王米琪, 艾廷华, 晏雄锋, 肖屹. 图卷积网络模型识别道路正交网格模式[J]. 武汉大学学报 ● 信息科学版, 2020, 45(12): 1960-1969. doi: 10.13203/j.whugis20200022
WANG Miqi, AI Tinghua, YAN Xiongfeng, XIAO Yi. Grid Pattern Recognition in Road Networks Based on Graph Convolution Network Model[J]. Geomatics and Information Science of Wuhan University, 2020, 45(12): 1960-1969. doi: 10.13203/j.whugis20200022
Citation: WANG Miqi, AI Tinghua, YAN Xiongfeng, XIAO Yi. Grid Pattern Recognition in Road Networks Based on Graph Convolution Network Model[J]. Geomatics and Information Science of Wuhan University, 2020, 45(12): 1960-1969. doi: 10.13203/j.whugis20200022
  • 道路网作为城市的骨架,体现了一个城市的主要结构和空间格局,反映出城市的交通模式、区域发展和规划情况。识别和提取道路网的空间结构特征(即空间模式),对于路径分析[1]、道路规划、自动驾驶和交通模式分析[2-3]具有重要意义。道路网模式由其整体形状和道路网元素(例如交叉点)相互配置而成[4]。相关研究从不同模型出发,将道路网分为不同模式,其中最常见的方式是按照道路网的形状特征将道路网分为辐射型、格网型、环型以及不规则型等[2-5]。辐射型道路网通常存在一个射线辐射中心,道路从辐射中心向周围伸展; 环型道路网则近似于一个圆,具有圆的特性; 正交网格型通常由两组平行的道路相互垂直正交形成,其网眼形状大多为矩形或者平行四边形; 不规则型则没有明显可辨别的规则形状和结构。道路网模式识别受主体的心理认知因素影响,需要高度的抽象概括,不是在相关指标控制下通过确定的规则推理就可实现的,这增加了该问题的难度。

    道路网模式识别的方法可以根据其识别单元,分为基于线(路段)和基于面(网眼)两种。基于线的方法通常表现为路段的图结构进行模式识别,如Heinzle等[6]利用霍夫变换识别网格的道路段,该方法只能识别出形状规则的方格网; He等[7]利用线性剖分来识别格网型道路段。基于面的方法从整体的角度,通过统计方法识别模式[8],如杨必胜等[9-10]从形状相似性、方向一致性以及格网的形状特征出发,对网眼数据进行识别,该方法克服了对形状不规则的格网的识别,但只能识别出最小单位的格网; 田晶等[11-12]将机器学习中的c4.5算法、主成分分析用于格网模式的网眼识别,但不能识别出形状不规则的格网。基于线的方法主要通过线性单元的网络分析提取其中的特定模式,而基于面的方法则是通过二维面目标的空间格局划分提取特定的空间分类。

    道路网的模式识别不仅要考虑其形状特征,还应考虑其拓扑特征,将道路网建模为图,可以很好地结合道路网的形状和拓扑特征。其中最直接的方法是将道路交叉口作为图的节点,将道路作为图的边,对道路网进行建模。Heinzle等[13]基于该方法通过计算道路节点的连通度实现了道路网典型模式的识别。Xie等[14]将道路网抽象为有向平面图,并基于图论的基本概念定量地分析道路网图的拓扑和几何特征。Zhang等[15]将道路网建模为图结构,通过网络分析计算道路图的中心度、接近中心度、中介中心度,对道路网进行度量研究。与上述方法相对的则是将边与节点的角色交换,构建一种新的图结构,Jiang等[16]利用图的对偶思想,将道路用图的节点表示,将道路交叉口表示为图的边,推导道路网络的拓扑结构。尽管基于图结构的道路网模式识别已经取得了较为丰硕的成果,但当前主要是从几何度量和统计指标考虑,缺少有效的决策和推理过程。由于道路模式表达的复杂性与不确定性,基于规则推理与统计分析的方法难以获得与人工判断相一致的结果。

    近年来,深度学习在模式识别[17-18]等方面取得了丰富的成果,卷积神经网络作为目前广泛应用的深度学习模型,具有学习局部平稳结构的能力,在图像、视频、声音领域发挥巨大的作用。卷积神经网络的基础在于学习对象数据的局部相关性与梯度效应,基于地理学第一定律[19],空间数据也具备典型的局部相关性,因此地理相关性问题的求解运用CNNs深度学习方法是有一定的理论基础的。但是CNNs在视觉信息、听觉信息的识别应用主要是基于规范的阵列结构(如图像)和线性结构(如声音讯号),而地理信息系统空间的地理实体难以构建成这两种规范的结构,更多的是一种图结构,在人工深度学习领域被称为非规则结构,因为节点间的连接在数量和形式上都不是固定的。道路表达的图结构属于非规范结构,节点关联的边的数目、节点间的邻接方式具有多样性特征。

    本文针对道路模式识别,引入一种基于图结构的深度学习模型——图卷积网络(graph convolution network,GCN),用于识别道路网格模式。本文将道路网建模为无向平面图,并使用道路线性剖分的方式获取道路的图节点特征,作为图卷积网络的输入值,将节点是否为构成网格的节点作为标签通过对GCN模型进行训练,通过提取节点都为正交网格类的路段提取道路网模式。

    • 本文针对道路网模式中的正交网格模式开展道路模式识别研究。正交网格是一种典型的道路网模式,它的基本特征是由一组近似平行道路与另一组近似平行的道路相互垂直正交形成,在城市道路网中普遍存在,可以反映出城市的发展情况,对城市规划、交通模式分析有重要意义。本文将节点是否为网格节点作为标签输入GCN模型进行训练,提取网格节点构成的路段完成路网模式识别。该过程整体框架如图 1所示,主要分为以下几个步骤:

      图  1  基于图卷积网络的道路网络网格模式识别整体框架

      Figure 1.  Framework of Grid Pattern Recognition in a Road Network Using Graph Convolution Network

      1)道路网图建模:以道路交叉口作为节点、道路作为边,将道路网构建为图结构; 同时将图节点划分并标注为网格和非网格两类。

      2)图节点特征提取:将道路网线性剖分,同时从图节点的连接特性、邻域的形状特征和统计指标来提取其描述特征。

      3)GCN学习:以图节点特征作为输入,通过图卷积运算提取其模式特征,并预测图节点的类别,即网格和非网格两类。

      4)道路网模式识别:将网格节点组成的道路提取出来,实现网格模式的识别。

    • 图可以被定义为G =(VEA),其中V={v0, v1, v2vn-1}是由n个节点构成的集合,E是连接节点的边的集合,A是一个n×n的邻接矩阵,表示每对节点间边的权重,每个节点可以包含一个或多个节点特征,代表图信号或函数。

      基于图结构的道路网络建模和标注如图 2所示,针对道路网,可以在道路交叉点将道路分割,以道路交叉口作为节点、道路作为边,构建无向平面图。为了实现以图为基础的道路网模式识别,还需要通过节点的特征来标注或训练学习,其中标注时,采用人工方式识别为网格模式,并将其关联道路的两个节点标注为网格点,其余节点为非网格点; 训练后,将网格点组成的道路提取出来,识别为正交网格模式。道路模式表达受人的空间认知、视觉心理影响,根据格式塔整体性原则,道路模式应该考虑其整体的分布,例如,在网格模式中,少量的非网格路段在人的视觉感知上不会影响网格模式的判断,这些少量的非网格路段也会被标注为网格模式。

      图  2  基于图结构的道路网络建模和标注

      Figure 2.  Modeling and Labeling of the Road Network Using a Graph Structure

    • 本文基于道路网图节点类型实现道路网的模式识别,为了获取有效的节点特征,利用网络空间线性剖分提取节点的特征。该方法可以有效结合统计分析和几何图形分析,提高识别的准确率。

      对于平面空间,栅格数据结构利用场模型思想,可将平面空间分割成离散而又相互联系的表达形式,以全局方式对均质空间进行建模。扩展到网络空间,可使用线性单元来剖分网络空间,将网络分解为一组连续的线段[7-8]。基于该思想,本文将道路网剖分成小的线性单元,建立道路网的网络剖分数据结构。

      本文采用等间隔方式剖分每一段道路。需要注意到,由于道路长度并非严格等倍于剖分间隔长度,因此可能会存在末端线性单元长度不及预设间隔的问题。对于每个节点,它的邻域由节点的线性缓冲区组成,包含着一组线性单元,如图 3所示。

      图  3  节点A的邻域

      Figure 3.  Connection Roads and Neighborhoods of Node A

      为分析线性单元在各方向的频率进而探测主流方向空间格局,将半平面(180°)划分18等分,计数统计每10°方向上的线性单元数目。例如,图 4图 3中节点A的300 m邻域的线性单元方向分布图,其中角度表示线性单元方向,半径表示该方向线性单元的个数,线性单元中出现频率最高的两个方向ab为节点邻域的两个主方向。可以明显看出,当线性单元展现显著的正交性时,主流方向将呈90°方向差异。

      图  4  节点A邻域方向分布统计图

      Figure 4.  Direction Distribution of Neighborhoods of Node A

    • 道路网模式主要来自于读者对地图的认知,根据格式塔认知原则,人们对物体进行观察时,首先会对一个物体进行全面的观察,然后才会注意其内部的细节。正交网格模式的识别不仅要考虑道路段的细节特征,还应该顾及上下文局部特征。本文从道路网的图连接特性、道路的形状特征以及道路节点邻域特征3个方面提取节点的特征。

      图连接特性通过节点的度反映,描述了道路交叉口相连接的道路的数量,当节点的度为3或者4时,该节点为网格类的可能性更大。

      道路网的形状特征通过直线反映,正交网格大多由正交的直线组成,所以直线性是判断格网的一个重要特征。路段的直线性通过路段的长度除以首尾点的距离获取(图 5),通过计算所有节点连接的路段直线性的均值作为节点的直线性。

      图  5  直线性

      Figure 5.  Straightness

      本文通过计算方向分布指数和正交指数来反映道路节点的邻域特征。方向分布指数和正交指数通过统计节点邻域内线性单元的方向分布频率得出,计算方式见表 1

      表 1  图节点的特征参量定义

      Table 1.  Definition of Descriptive Variables for Graph Nodes

      分类 特征 计算方法 说明
      连接特征 节点度 Degree of node
      形状特征 直线性 $\begin{array}{l} S = \frac{{\sum \limits_{i = 1}^n {s_i}}}{n}\\ {s_i} = {l_1}/{l_2} \end{array}$ 节点连接路段的直线性的均值
      邻域特征 方向分布指数 $\begin{array}{l} D = \mathop \sum \limits_{i = 1}^{18} {w_i} \cdot {p_i}\\ \;\;\;\;\;\;{w_i} = \\ {\rm{max}}(\left| {{\rm{cos}}\left( {i - a} \right)} \right|, \\ \;\;\;\;\left| {{\rm{cos}}\left( {i - b} \right)} \right|) \end{array}$ 方向区间i包含的线性单元数量的频率为piwii与主方向的接近程度,i越接近主方向,wi越接近1,当i=ab时,wf=1,D越大,节点邻域的线性单元的聚集性越强
      正交指数 $V = {\rm{sin}}\left( {\left| {b - a} \right|} \right)$ V越大,节点邻域内剖分单元正交分布的可能性越大

      图 3所示,正交网格节点的邻域内线性单元的角度值应聚集在2个正交的主方向上。本文使用方向分布指数来衡量方向的聚集性,邻域内单元的方向越聚集,方向分布指数越大,当邻域内线性单元完全聚集在两个方向上时,方向分布指数为1;通过计算正交指数来判断两个主方向是否近似正交,道路主方向越接近90°,正交指数越大。

      所有参量定义如表 1所示,其中线性单元中出现频率最高的两个方向ab为节点邻域的两个主方向。这些参量即构成道路网图节点的描述特征,并作为模型的输入。

    • 根据图傅里叶变换和卷积定理,图的卷积运算通过将图的节点序列构成的图信号在图的顶点域的卷积转化为傅里叶域中的点积实现。其中,傅里叶变换是信号在时域(或空间域)和频域之间的变换,可以看作是信号在拉普拉斯算子特征函数中的展开式。将图信号处理的概念与传统信号处理的概念联系起来,图的傅里叶变换也可以看作是图信号在拉普拉斯矩阵特征向量中的展开式。图的拉普拉斯矩阵L是一个实对称矩阵,它有一组正交的特征向量$\left\{ {\mathit{\boldsymbol{X}}_l^T} \right\}_{l = 0}^{N - 1}$,且特征值[λ0, λ1, λ2λn-1]均为实数,L=X∧XT, =diag(λ0, λ1, λ2λn-1)。对任意定义在图G顶点上的信号f(n),它的图傅里叶变换$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}} \over f} $可表示为$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}} \over f} \left( {{\mathit{\boldsymbol{\lambda}}_t}} \right) = {\mathit{\boldsymbol{X}}^T}f$,它的逆变换为$f\left( n \right) = \mathit{\boldsymbol{X}}\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}} \over f} $。

      根据卷积定理,两函数的卷积等于它们傅里叶变换后的乘积的逆变换。图上的卷积算子也一样,图上的函数fRn与滤波器gθ的卷积可表示为:

      $${g_\theta }{\rm{*}}f = \mathit{\boldsymbol{X}}{g_\theta }\left(\mathit{\boldsymbol{\Lambda}} \right){\mathit{\boldsymbol{X}}^{\rm{T}}}f$$ (1)

      式中,gθ()是一个关于L特征值的函数,可以把它看作是卷积运算中的滤波器,gθ()=diag(θ)=diag(θ0, θ1, θ2θn-1)。

      上文的卷积运算主要有两个弊端:特征向量的计算非常复杂,同时与特征向量X相乘的时间复杂度为On2),对于大规模的图,计算代价过高; 缺乏空间局部相关性,一个顶点的变量值会与它的全局顶点相关联[20-21]。为了解决这些问题,Hammond等[22]提出一种快速局部滤波器,用K阶切比雪夫多项式Tk(x)来近似表达gθ():

      $${g_{\theta '}}\left( \mathit{\boldsymbol{\Lambda}} \right) = \mathop \sum \limits_{k = 0}^{K - 1} \theta _k^{\rm{'}}{T_k}\left( {\tilde {\mathit{\boldsymbol{\Lambda}}}} \right)$$ (2)

      式中,$\tilde \Lambda = \frac{2}{{{\lambda _{{\rm{max}}}}}}\Lambda - {I_N}$,其中λmax是拉普拉斯矩阵L的最大特征值; θ'∈Rk是切比雪夫系数向量,切比雪夫多项式的公式为:${T_k}\left( X \right) = 2x{T_{k - 1}}\left( X \right) - {T_{k - 2}}\left( X \right)$,其中${T_0}\left( X \right) = 1, {T_1}\left( X \right) = X$,因为${(X\Lambda {X^{\rm{T}}})^k} = X{\Lambda ^k}{X^{\rm{T}}}$,所以f与滤波器gθ'卷积的公式为:

      $${g_{\theta '}}\left( \mathit{\boldsymbol{\Lambda}} \right){\rm{*}}f = \mathop \sum \limits_{k = 0}^{K - 1} \theta _k^{\rm{'}}{T_k}\left( {\tilde L} \right)f$$ (3)

      式中,$\tilde L = \frac{2}{{{\lambda _{{\rm{max}}}}}}L - {I_N}$,通过拉普拉斯矩阵的K阶切比雪夫多项式实现的K阶局部邻域的卷积运算,可以使一个顶点的变量值不是与全局顶点相关联而只和它的K阶邻域内的节点有关,对输入数据每进行一次卷积,类似于对每个顶点的K阶邻域内的节点进行加权求和。

    • 图卷积网络模型可以通过叠加多个卷积层形成,Kipf等[23]提出了一种用于图节点分类的图卷积网络模型,本文将其应用于道路网节点分类,其结构如图 6所示。

      图  6  图卷积网络的节点分类模型

      Figure 6.  Node Classification Model of Graph Convolution Network

      将道路网建模为图结构后,先按照§2.2的方式提取特征作为GCN的输入,然后通过多个隐藏层逐层传播,其中第l+1层隐藏层的第j个输出的计算方式如下:

      $$H_j^{\left[ {l + 1} \right]} = \sigma \left( {\mathop \sum \limits_{i = 1}^N \left( {\mathop \sum \limits_{k = 0}^K \theta _{i, jk}^{\rm{'}}{T_k}\left( {\tilde L} \right)H_i^{\left[ l \right]}} \right) + b_j^{\left[ l \right]}} \right)$$ (4)

      式中,σ(*)是非线性激活函数,例如${\rm{ReLU}}\left( \cdot \right) = {\rm{max}}\left( {0, \cdot } \right)$; Hi[l]是第l层的第i个输入,N为输入神经元数,H[0]=f; Hj[l+1]为第l+1层第j个输出; $\theta _{i, jk}^{\rm{'}} \in {R^{N \times D}}$和$b_j^{\left[ l \right]} \in {R^{1 \times D}}$是图卷积网络的K阶切比雪夫多项式系数和偏置,其中D为输出神经元,可通过梯度下降训练得到。

      在GCN的训练过程中,每个输入样本包含两组输出:预测值Z以及真实标签值y,计算预测值与标签值的交叉熵作为损失函数,整个网络通过最小化损失函数进行优化,并通过反向传播算法更新其参数[24]

      GCN使用半监督的方式进行训练,训练时可以利用无标签的数据提升学习性能。GCN将图的所有节点都作为输入值,包含有标签数据(训练集)和无标签数据(测试集),无标签数据使用0向量作为伪标签,同时在计算损失函数时,会跳过无标签数据的损失。

    • 本文采用Python和TensorFlow实现道路网网格模式识别方法,实验在i7-8750H/NVIDIAGeForceGTX1050Ti硬件平台下完成。

      本文选用深圳市1:10 000比例尺的道路网数据作为实验数据,该实验区域内共有13 267条道路,8 513个道路交叉口。将其构建成图结构,并人工标注出网格模式的路段,其中标注为网格模式的道路共6 317条,非网格6 950条,如图 7所示。进一步将网格道路两端的节点提取出来,标记为网格点,其余节点标记为非网格点,共4 336个格网点,4 177个非网格点。为了获取稳定的剖分效果,采用50 m的线性单元剖分道路网,根据道路网的网格尺寸,选择500 m的曼哈顿距离作为邻域范围计算道路图节点的特征。

      图  7  实验区域

      Figure 7.  Experimental Area

      为了更好地呈现最后结果的视觉效果,本文对网眼进行随机抽样并将这些网眼包含的节点作为测试集。实验区域共有4 755个网眼,随机选择595个网眼的节点,共计2 722个节点作为测试样本,训练集、测试集的比例大约为7:3,随机选择500个节点作为验证集进行超参数调试,剩余节点作为训练集进行训练。

      本文使用一个5层的GCN进行训练,它包含4个卷积层和1个输出层,其中每个卷积层包含128个卷积核,考虑到判断格网节点所需要的邻域范围,使用三阶的切比雪夫多项式作为卷积核。初始化卷积核的权重后[24],通过反向传播算法对权重进行更新,最大迭代次数为2 000,为了防止过拟合,如果验证集损失经过800次的迭代后的值大于这800次训练的平均值,则停止训练。

      GCN的输出值为二维的概率向量,分别表示节点为网格和非网格的概率,对于单类别分类问题,一般最大值为分类的结果,也可以根据需要设置接受阈值。本文将网格的接受阈值设置为0.5进行分类,经过2 035个训练周期后,训练集和测试集的准确率分别为97.7%和89.2%,损失分别为0.220和0.394,其混淆矩阵如表 2所示。

      表 2  道路格网模式识别的混淆矩阵

      Table 2.  Confusion Matrix of Road Grid Pattern Recognition

      GCN 实际网格 实际非网格
      预测网格 1 390 172
      预测非网格 123 1 037

      表 2中结果表明,该训练集训练的GCN具有较强的泛化能力,对数据集具有较好的适用性。图 8给出了训练集、验证集的精度和损失随迭代次数的变化。可以看出,随着训练次数的增加,精度逐渐提高,损失值逐渐减小,经过约1 500次的训练后,验证集收敛。

      图  8  训练集、验证集的准确度和损失值

      Figure 8.  Accuracies and Loss Changes of the Training Set and Validation Set

      GCN对道路节点分类后,还需要将网格节点构成的路段的道路提取出来作为正交网格模式道路。将测试集的GCN识别结果与人工选取的网格模式相比,以正确分类的道路段数与人工标注的道路段数的比值计算正确率,该模型的道路段分类的正确率达到了86.1%,以GCN模式识别结果的节点数与网格节点数计算召回率,该模型的召回率达到了91.6%。

      从实验结果(图 9)可以看出,使用GCN能够较好地识别出正交网格模式,因为GCN具有局部相关性,在分类过程中可以根据节点的连接关系顾及周围节点的特征,可以有效识别一些复杂节点组成的网格模式,对于一些形状不规则的网格也能进行有效的识别(见图 9(b)图 9(d)所示的放大图); 对于密集格网的识别效果很好(图 9(c)所示的放大图),对各种排列方式的网格都能有效识别。但因为城市路网本身比较复杂,且道路模式存在一定的主观性,对于一些网格与非网格混杂以及网格特征不明显的情况,与会存在一定的误判,例如格网密集区域的一些弯曲道路,也会被识别为网格模式(图 9(d)中圆圈所示)。

      图  9  GCN对道路网格网模式的识别结果

      Figure 9.  Recognition Results of Road Grid Pattern Using GCN

      同时,实验还研究了对该模型有影响的几个参数的敏感性,包括模型的深度(隐藏层的数量)、卷积核的数量、切比雪夫多项式阶数、邻域范围大小以及剖分单元的大小。图 10展示了模型的深度及卷积核数量对模型性能的影响。

      图  10  模型深度和卷积核数量对准确度的影响

      Figure 10.  Effect of Model Depth and Number of Convolution Kernel on Accuracy

      图 10可以看出,模型深度及卷积核数量的增加可以有效地提升模型的性能,但同时也需要更大的计算代价,并且由于模型使用反向传播算法,隐藏层数过多会导致梯度消失或者爆炸,从而影响模型的性能。

      为了分析多项式的阶数、邻域范围、线性单元大小对模型性能的影响,本文保持其他参数不变,分别改变多项式的阶数、邻域范围、线性单元大小,对模型进行训练,模型准确度见图 11。从图 11可以看出,随着多项式阶数的增加准确度逐渐增加,3阶之后趋于稳定; 邻域范围过小或过大都不利于节点特征的获取,实验数据中道路网眼的边长大多集中在100~500 m之间,邻域的范围在该区间内可以获得较好的性能; 相比之下,线性单元的大小并没有显著影响模型的分类性能。

      图  11  项式阶数,邻域范围,线性单元对模型性能的影响

      Figure 11.  Effect of Difference Polynomial Orders, Neighborhoods, and Linear Unit on Accuracy

      节点特征的选择是本文的关键,为了说明通过线性剖分提取的特征可以有效提高模型的准确性,本文使用节点度、直线性以及节点连接路段的夹角与直角差值的最小值作为输入值,对模型进行训练,实验其他参数不变,得到的混淆矩阵见表 3,节点分类的准确度为81.9%。实验结果说明,该方法能够有效提升节点的特征质量,提高模型分类的准确度。

      表 3  特征对比混淆矩阵

      Table 3.  Confusion Matrix of Feature Contrast

      GCN 实际网格 实际非网格
      预测网格 1 255 235
      预测非网格 258 974

      本文以图 12所示的道路网为例,展示节点嵌入在训练迭代过程中的演化,演化过程见图 13

      图  12  实验区域

      Figure 12.  Experimental Area

      图  13  节点嵌入的演化过程

      Figure 13.  Evolution Process of Node Embedding

      为了更好地展示效果,本文使用只有一个只包含两个卷积核的隐藏层的GCN模型为例(与输出层一样),分别将两个卷积核的输出值作为横坐标和纵坐标进行可视化。为了使坐标值范围为-1~1,隐藏层使用tanh(*)作为激活函数,输出层使用softmax(*)作为激活函数,迭代次数为800次,灰色线段表示节点间的连接关系。从图 13中可以看出,初始状态下,两类节点的嵌入是随机的,随着迭代次数的增加,两类节点逐渐分离开并最终趋于稳定,说明该模型成功地实现了基于图结构的不同类型样本的分离。因为图卷积网络的训练是一个提取节点特征的过程,随机初始化后的卷积核可以在反向传播的过程中不断更新权重,使不同节点特征差异增大,使这些特征可以更好地分离两类节点。

      为了对比图卷积网络与其他方法的效果,本文分别将多层感知机(multi layer perceptron,MLP)、支持向量机(support vector machine,SVM)、LightGBM作为参考,实验结果见表 4

      表 4  GCN与其他算法准确率和召回率对比/%

      Table 4.  Comparison of Accuracy and Recall Rate of the Proposed GCN Model and Other Algorithms/%

      指标 GCN MLP SVM LightGBM
      准确率 89.1 77.8 77.6 77.6
      召回率 91.6 90.4 88.2 88.0

      MLP、SVM以及LightGBM都是常用的机器学习算法,常用于各种分类任务,对于道路网节点的分类任务,这3种算法分类的准确性相差不大,GCN节点分类的准确率和召回率高于其他方法,具有很强的优越性。这是因为图节点分类不同于常规分类任务,需要考虑节点之间的连接关系,GCN模型可以在训练过程通过卷积使分类结果不仅与节点自身有关,还与它连接的节点有关。

    • 道路网作为城市的骨架,体现了一个城市的主要结构和空间格局,反映出城市的交通模式、区域发展和规划情况。识别和提取道路网的空间结构特征(即空间模式),对于路径分析、道路规划、自动驾驶和交通模式分析具有重要意义。本文提出一种基于GCN的网格模式识别方法。该方法以道路网中的节点为基本单元,将其分为网格点和非网格点,并通过将路网线性剖分来计算节点的特征,从连接特征、几何形状特征、节点邻域特征3个方面来描述节点特征,构成GCN的输入值。实验结果表明,该方法可以有效地对道路网节点进行分类,能够用于网格模式识别。进一步的研究工作将尝试利用GCN识别其他路网模式(放射模式和环模式),以及将GCN运用到建筑物、水系等要素的识别和提取上。

参考文献 (24)

目录

    /

    返回文章
    返回