留言板

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

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

网络空间向量剖分法识别城市路网网格模式

何亚坤 艾廷华 杜欣 禹文豪

何亚坤, 艾廷华, 杜欣, 禹文豪. 网络空间向量剖分法识别城市路网网格模式[J]. 武汉大学学报 ● 信息科学版, 2018, 43(1): 138-139. doi: 10.13203/j.whugis20150757
引用本文: 何亚坤, 艾廷华, 杜欣, 禹文豪. 网络空间向量剖分法识别城市路网网格模式[J]. 武汉大学学报 ● 信息科学版, 2018, 43(1): 138-139. doi: 10.13203/j.whugis20150757
HE Yakun, AI Tinghua, DU Xin, YU Wenhao. Grid Pattern Recognition in Street Network Space by Vector Tessellation Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(1): 138-139. doi: 10.13203/j.whugis20150757
Citation: HE Yakun, AI Tinghua, DU Xin, YU Wenhao. Grid Pattern Recognition in Street Network Space by Vector Tessellation Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(1): 138-139. doi: 10.13203/j.whugis20150757

网络空间向量剖分法识别城市路网网格模式

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

国家自然科学基金重点项目 41531180

国家高技术研究发展计划(863计划) 2015AA1239012

武汉大学研究生自主科研项目 2015205020202

详细信息
    作者简介:

    何亚坤, 博士生, 主要从事时空分析与空间数据挖掘研究。hyk1990@whu.edu.cn

    通讯作者: 艾廷华, 博士, 教授。tinghua_ai@163.net
  • 中图分类号: P283

Grid Pattern Recognition in Street Network Space by Vector Tessellation Method

Funds: 

The National Natural Science Foundation of China 41531180

the National High Technology Research and Development Program (863) of China 2015AA1239012

the Fundamental Research Funds for the Central Universities 2015205020202

More Information
    Author Bio:

    HE Yakun, PhD candidate, specializes in spatial-temporal analysis and data mining. E-mail: hyk1990@whu.edu.cn

    Corresponding author: AI Tinghua, PhD, professor. E-mail: tinghua_ai@163.net
图(8) / 表(2)
计量
  • 文章访问数:  1313
  • HTML全文浏览量:  94
  • PDF下载量:  352
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-06-27
  • 刊出日期:  2018-01-05

网络空间向量剖分法识别城市路网网格模式

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

    国家自然科学基金重点项目 41531180

    国家高技术研究发展计划(863计划) 2015AA1239012

    武汉大学研究生自主科研项目 2015205020202

    作者简介:

    何亚坤, 博士生, 主要从事时空分析与空间数据挖掘研究。hyk1990@whu.edu.cn

    通讯作者: 艾廷华, 博士, 教授。tinghua_ai@163.net
  • 中图分类号: P283

摘要: 将道路网络空间视为嵌在2D空间中的独立子空间,利用形态单一的线性单元剖分图结构的边,实现网络空间的栅格化;提取网格模式的典型特征,包括几何和拓扑特征,以栅格单元邻域为目标计算特征值,构建特征向量描述栅格单元,实现对象空间到特征空间的映射,构建空间向量场;基于支持向量机(support vector machine,SVM)实现网格模式分类;结合格式塔原则完善实验结果。将此方法应用于深圳市路网数据,实验结果表明能有效地识别网格模式。

English Abstract

何亚坤, 艾廷华, 杜欣, 禹文豪. 网络空间向量剖分法识别城市路网网格模式[J]. 武汉大学学报 ● 信息科学版, 2018, 43(1): 138-139. doi: 10.13203/j.whugis20150757
引用本文: 何亚坤, 艾廷华, 杜欣, 禹文豪. 网络空间向量剖分法识别城市路网网格模式[J]. 武汉大学学报 ● 信息科学版, 2018, 43(1): 138-139. doi: 10.13203/j.whugis20150757
HE Yakun, AI Tinghua, DU Xin, YU Wenhao. Grid Pattern Recognition in Street Network Space by Vector Tessellation Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(1): 138-139. doi: 10.13203/j.whugis20150757
Citation: HE Yakun, AI Tinghua, DU Xin, YU Wenhao. Grid Pattern Recognition in Street Network Space by Vector Tessellation Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(1): 138-139. doi: 10.13203/j.whugis20150757
  • 纵观城市形成的历史进程,道路网作为一种公共框架约束着城市形态和人类行为。作为城市系统的子系统,道路网被认为是城市的“指纹”[1],路网模式反映了城市道路的分布特点,影响着城市的结构和组织,蕴含着大量城市形成和演变的内在机制。由于城市系统本身的复杂性,路网模式在不同的领域都有不同的分类体系[2]。从研究载体上来看,路网模式识别方法可以分为基于面(网眼)的和基于线的识别方法。

    Heinzle等[3-4]基于图论对路网模式进行了系列研究,通过网眼中心的排列来识别网格模式;利用统计指标(Tukey深度值)和形态指标(仿射不变量)识别环状模式。田晶等[5-6]结合机器学习算法识别网格模式。Yang等[7]结合形态学指标和多指标评价提出了一种探测和量化网格模式的方法。Louf等[1]通过计算所有网眼的几何和拓扑信息得到城市的类型分布图来区分不同的城市。基于网眼的识别方法,以一种全局的观点将网眼作为抽象采样点对其进行统计描述,而忽略网眼内部的道路弧段的几何和拓扑特征。在构建网眼时也会丢失部分弧段的链接信息。

    Heinzle等[3]通过霍夫变换识别直线,相交识别网格模式。Heinzle等[8]通过Dijkstra算法探测延伸道路识别放射模式。Porta等[9]将空间句法理论及中心度量度结合分析城市路网拓扑模式,并得出网格模式在城市中是普遍存在的结论。Xie等[10]对路网构图,借助信息熵的概念来区别不同结构的道路网络。Jiang等[11-13]利用空间句法和复杂网络等理论研究和定义了城市的拓扑结构。基于线的识别方法,直接以道路弧段作为基本单元,着眼于线性扩展和局部的图形结构分析,而缺少全局的上下文环境分析,例如相邻区域内的弧段拓扑结构、节点分布统计特征和相邻区域边的排列组织等。

    根据格式塔认知原则,首先将目标作为一个整体获得完整的模式,继而对组成目标的细节进行分析[14]。基于面的方法用一种全局观念,以统计分析的方法进行模式识别;而基于线的方法以一种局部的图形结构分析实现模式探测。本文尝试将这两种方法中的有益思想综合,先给出一种图结构上的场模型,在线性结构上实施统计分析,然后以局部结构的特征分析实现网格模式识别。

    • 使用形态单一的线性栅格单元剖分网络空间已成为基于网络环境的空间分析的重要方法[15-18]。本文将此思想引入到路网模式识别中。定义道路交叉点和不同等级道路的分界点等特征点为网络节点,利用节点分割道路生成道路弧段,将道路网的每一条弧段都用相同的栅格单元进行剖分,构造节点-弧段、栅格单元-栅格单元和节点-栅格单元拓扑关系,建立网络剖分数据结构。

      剖分粒度的细化对应着算法时间复杂度的增长[19],适当的剖分粒度取决于应用环境及路网弧段的长度。Ai等[15]提出剖分粒度可以参考网络边的平均长度设定,网络边的平均长度越大,剖分粒度越大;She等[16]使用平均长度对道路网络进行剖分并证明其合理性,并指出由于实际路网中可能存在小于设定的剖分粒度的边,最终得到的剖分结构并不是严格相等的。本文将参考此方案进行网络空间栅格化剖分粒度的确定。

      本文将道路网视为嵌在2D空间中的独立空间,如图 1所示,在对象空间将道路网络空间剖分成连续分布的线性栅格单元组成的场模型。对原始数据的矢量运算转换成叠置、扩展及关系探测等地图代数运算。将模式定义为相邻栅格单元或相邻区域特征值上相互关系的表征。通过计算栅格单元邻域的拓扑和几何特征,得到栅格单元的特征向量。空间内的每一个位置都对应由一组特征值组成的特征向量,由此构建模式识别空间向量场[20-21]。本文使用监督分类的二值分类器支持向量机(support vector machine, SVM),提取网格模式的栅格单元。并利用邻近性、相似性和闭合性格式塔原则对实验结果进行完善。

      图  1  向量剖分法示意图

      Figure 1.  Vector Tessellation Method

    • 在剖分粒度确定的情况下,特征提取时选取的邻域大小将直接和尺度相关。O'Sullivan等[22]认为应邻域大小应根据研究对象的特性决定。Porta等[9]和She等[16]建议根据街道尺度来确定邻域大小。本文将邻域大小作为一个可控参数,参考了图像处理中对窗口大小选择的建议,首先对数据中的目标网格的尺寸进行预判,从而设定一个邻域大小的选择范围。

      网格模式是由一系列满足一定统计特征(包括几何和拓扑等)的相邻栅格单元组成的区域结构,各栅格单元在两个近似正交的方向上满足特定的排列方式。向量剖分法将其特征量化为五个指标,即方向分布指数、正交指数、隶属度、延展指数、结构指数。

      (1) 方向分布指数

      剖分后的栅格单元具有特定的方向,以正东作为初始方向,逆时针旋转的角度来表示栅格单元的方向。为了方便计算,将角度取值范围[0°, 180º]对18个区间, 以[1, 18]对18个区间编号,栅格单元的角度值将以其所在区间的序号代替。统计目标栅格单元邻域内所有栅格单元的角度值,得到方向分布统计图(图 2(c))。理想网格路网的方向统计图应表现为在两个区间上有聚集性(图 2(d))。本文定义方向分布指数,衡量栅格单元邻域内方向分布的双向聚集性,设置距离权重为将实际的方向分布空间映射到理想网格空间的距离的倒数。假设两个聚集方向区间序号记为ab,区间j的权重为ωj,角度值落在区间j内的概率为pj

      $$ {\omega _j} = \max \left( {\frac{1}{{\left| {j -a} \right|}}, \frac{1}{{\left| {j -b} \right|}}} \right), {\omega _j} \in \left( {0, 1} \right] $$ (1)

      图  2  方向分布指数

      Figure 2.  Direction Distribution Index

      式中,当j = ab时,ωj=1。栅格单元i的方向分布指数Di为:

      $$ {D_i} = \sum\nolimits_{j = 1}^{18} {{\omega _j}} \cdot {p_j},{D_i} \in {\rm{ }}\left( 0 \right.\left. {,1} \right] $$ (2)

      Di越大,目标栅格单元邻域的双向聚集性越强,被分类为网格模式的可能性越大。从表 1中看出,DADB,栅格单元A所处的环境中干扰单元即偏离两峰值方向的单元所占的比例比栅格单元B大(图 2(a), 2(b))。

      表 1  栅格单元A、B指标统计

      Table 1.  Indexes Values of Element A and Element B

      D V M G T
      A 0.907 69 1 0.2 0.842 7 0.62
      B 0.960 97 1 1.0 0.663 4 0.89

      (2) 正交指数

      为了判断栅格单元的邻域内两个聚集方向是否近似正交,定义正交指数Vi为:

      $$ {V_i} = \sin \left( {\left| {b - a} \right| \cdot \frac{{\rm{ \mathsf{ π} }}}{{18}}} \right), {V_i} \in \left[{0, 1} \right] $$ (3)

      Vi越大,目标栅格单元的邻域呈现出正交分布的可能性越大,在其他条件相同的情况下,也更容易被分类为网格模式。表 1中,栅格单元AB的正交指数均为1,从图 2中来看,栅格单元AB所处的邻域环境多为水平与竖直方向分布的栅格单元。

      (3) 隶属度

      当栅格单元所处的环境满足网格模式的方向分布时,仍需判断栅格单元自身是否偏离聚集方向而属于噪声单元。定义隶属度指标Mi为:

      $$ {M_i} = \max \left( {\frac{1}{{\left| {j -a} \right|}}, \frac{1}{{\left| {j -b} \right|}}} \right), {M_i} \in \left( {0, 1} \right] $$ (4)

      式中,当j=ab时,Mi=1。在图 2(a)2(b)中,栅格单元A的方向处于偏离正交方向的区间,其隶属度只有0.2(表 1)。栅格单元B则正好处于聚集区间,隶属度为1。

      (4) 延展指数

      网格模式下栅格单元呈现线性延展的特性,如图 3(a)中所示的蜿蜒排列和直线排列的对比。虽然网络扩展距离相同,但由于欧氏距离的差别,两条路径展现出截然不同的延展程度。定义延展指数Gi为:

      $$ {G_i} = \frac{{\sum\nolimits_{j = 0}^{m - 1} {{E_{di{s_{ij}}}}} }}{{\sum\nolimits_{j = 0}^{m - 1} {{N_{di{s_{ij}}}}} }}, {G_i} \in \left[{0, 1} \right] $$ (5)

      图  3  延展指数

      Figure 3.  Extension Index

      Edisij为目标单元i中点到延展终点单元中点ij的欧式距离,$ {E_{di{s_{ij}}}} = \sqrt {{{\left( {{x_i} - {x_{ij}}} \right)}^2} + {{\left( {{y_i} - {y_{ij}}} \right)}^2}} $。Ndisij为相应的网络距离,Ndisij=Nij×lgapdisNij为目标单元i到延展终点单元中点ij之间的单元个数,lgapdis为剖分粒度。且目标单元i共有m个延展终点。

      Gi值越大,邻域环境越松弛,延展性越好;相反,邻域环境越紧凑。参考表 1GAGB,相对于栅格单元B,栅格单元A所处的邻域环境较松散,且延展性较好。

      (5) 结构指数

      将构成网格的特征单元集合成两类,第一类栅格单元为骨架单元,一阶邻接度大于2,构成网格的骨架特征;第二类为连接单元,一阶邻接度小于等于2,连接骨架单元。

      设共有m个扩展终点,统计每个扩展方向上的骨架栅格个数,记作CjS,每个方向上的栅格个数Cj,定义结构指数Ti为:

      $$ {T_i} = \frac{{\sum\nolimits_{j = 1}^m {\frac{{C_j^S}}{{{C_j}}}} }}{m}, {T_i} \in \left[{0, 1} \right] $$ (6)

      结构指数Ti的意义为平均每一个方向上扩展Ti步可以遇到一个骨架栅格。该指标决定了网格的尺寸和链接方式,同时也可以排除道路中的大枝杈(图 4(a))。Ti越大,则该栅格单元邻域内包含的网格骨架结构越多,可能包含的网格密度越大。参考表 1,栅格单元B的邻域环境所包含的骨架结构要多于栅格单元A,栅格单元B邻域的网格密度更高。

      图  4  结构指数

      Figure 4.  Structure Index

    • 由于路网数据量较大且复杂程度较高,在分类时,变量之间可能具有相关性和冲突性,难以对各指标设置单一阈值。本文采用SVM根据路网数据特征自动综合各个指标实现分类。SVM分类由软件包libsvm完成[23]。分类步骤如下。

      (1) 将§2.1中提出的五个特征值的取值范围控制在[0, 1]之间,防止取值范围大的指标削弱取值范围较小的指标的作用。

      (2) 选用径向基核函数(radial basis function, RBF),RBF常用于非线性分类,相较多项式核函数所设参数较少(惩罚因子C和核参数γ),可以有效降低模型复杂度。

      (3) 为防止过拟合,对训练样本进行十折交叉验证,确定模型最佳参数。

      (4) 采用步骤(3)确定的最佳参数所构建的分类模型对测试样本进行模式分类。

    • 由于研究对象(栅格单元)与研究目标(网格)的不同和分类器精度的影响,难以保证分类结果的完善性。为了提高正确率,本文根据格式塔原则中的邻近性、相似性和闭合性对SVM分类结果进行优化。首先将与网格模式相邻的符合要求的背景单元合并到网格模式中,使边界向外部扩张;然后消除悬挂的边界单元,使边界向内部收缩。设定规则为:假设被识别为隶属网格模式的栅格单元记为Egrid,其他单元记为Enon_grid

      (1) 建立一个队列,将已经识别出来的栅格单元Egrid入队,取出队首单元,如果其邻接单元为Enon_grid,计算夹角AEgrid_iEnon_grid,并将夹角值记录给Enon_grid,设定阈值为10°。

      $$ {A_{{{\rm{E}}_{{\rm{grid\_i}}}}{{\rm{E}}_{{\rm{non\_grid}}}}}} = \left| {{\theta _{{E_{{\rm{grid}}\_i}}}} - {\theta _{{E_{{\rm{non\_grid}}}}}}} \right| + {\theta _{{\rm{accum}}\_i}} $$ (7)

      式中,θaccum_i为由SVM识别出的原始网格扩展到栅格单元i的累积夹角值。当AEgrid_iEnon_grid小于阈值时,将其类别改为Egrid,并将其入队。重复以上过程,直至队列为空。

      (2) 遍历所有栅格单元,将Egrid存入链表。遍历链表的每一个元素,当其连接的Egrid个数小于2或者只在一侧有邻接单元,则将其类别改为Enon_grid;重复以上过程,直到链表元素的类别不再变化。

      由于优化过程需要两次遍历所有的栅格单元,假设共有n个栅格单元,则图形补全和枝杈修剪的时间复杂度是O(2n)。

    • 本文使用Python实现路网网格模式识别的实验系统,在i5-2640 m/2.8 GHZ/4 G/Wind-ows7的环境下,选用中国深圳市1: 10 000比例尺的道路网数据作为实验数据。对数据进行必要的预处理,删除立交桥,对道路进行拓扑检查,删除伪节点,并在交叉点处打断。预处理后深圳市道路网弧段平均长度为308 m,采用300 m的栅格单元剖分道路网。预判出网格尺寸的端点值为4步和12步,参考此范围,本文采用10步邻域。

      图 5中,训练样本区域(图 7中蓝色矩形框内)内道路细节较为丰富,包含不同分布范围和不同排列方式的网格模式,同时具有大枝杈和大弯曲类型的道路。通过交叉验证达到的最大模型训练正确率为85%。将训练得到的模型用于测试样本,截取深圳市福田区的一块区域观察识别结果的细节变化,SVM分类结果不能保证网格模式边缘的完整性(图 6(a)),经过图形补全即膨胀操作后(图 6(b)),网格模式的边界向外扩张,最后通过枝杈修剪减掉毛糙的枝杈(图 6(c))。将测试样本的最终识别结果与目视判别选取的网格模式相比,以正确分类的网格栅格单元个数与目视判别网格栅格单元个数的比值计算正确率,以正确分类的网格栅格单元个数与向量剖分法识别出的网格栅格单元个数的比值计算召回率。向量剖分法识别网格模式的正确率达到91.30%,召回率达到82.91%。

      图  5  训练区域

      Figure 5.  Training Area

      图  7  网格识别结果

      Figure 7.  Recognition Result

      图  6  网格识别细节图

      Figure 6.  Details of Grid Recognition

      为了对比向量剖分法与传统方法的识别效率,本研究将Yang等[7]和Heinzle等[8]提出的两种经典算法作为参考,识别结果如图 8所示。据表 2可以发现,向量剖分法在召回率相差较小的情况下,取得了更高的正确率。召回率相对较低,这和样本选择相关,由于城市路网本身的复杂性,样本选择会丢失一定的信息。从识别结果细节特征来看,如图 7图 8中方框I中所示,对于阶梯状模式,向量剖分法能够很好的排除,而两组对比实验由于不考虑上下文,使得误将其分为网格模式。而对于方框II中显示的复杂节点连接组成的网格模式,Heinzle等[8]的方法不能有效识别。

      图  8  对比实验结果

      Figure 8.  Results of Contrast Experiments

      表 2  网格模式识别结果

      Table 2.  Statistics of Grid Pattern Recognition Results

      算法 正确率/% 召回率/%
      向量剖分法 91.30 82.91
      Yang等[7]提出的算法 78.81 89.63
      Heinzle等[8]提出的算法 86.63 84.26
    • 本文提出向量剖分法识别网格模式,该方法以路网栅格化处理后的栅格单元为基本单元,以邻域特征描述栅格单元,结合SVM和格式塔原则实现分类。向量剖分法从整体上把握道路网模式具有空间认知的一览性,识别方法上建立一种新的空间认知归纳思维,将统计分析与局部图形的结构分析统一应用于空间剖分后的栅格单元,所得到的分类结果在更细节的层面上取得了更高的正确率。此外,本方法需要设定的参数意义明确,可以通过对参数的设置自适应地满足实验区域和数据尺度的需求。

      进一步的研究工作将从理论体系上利用向量剖分法构建识别其他路网模式(放射模式和环模式)的模型;从方法应用上尝试将本文提出的方法应用于道路网选取和更新,以及城市功能区的辅助识别。

参考文献 (23)

目录

    /

    返回文章
    返回