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

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

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

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

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

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

4）道路网模式识别：将网格节点组成的道路提取出来，实现网格模式的识别。

图可以被定义为G =（V，E，A），其中V={v₀, v₁, v₂…v_n-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邻域的线性单元方向分布图，其中角度表示线性单元方向，半径表示该方向线性单元的个数，线性单元中出现频率最高的两个方向a、b为节点邻域的两个主方向。可以明显看出，当线性单元展现显著的正交性时，主流方向将呈90°方向差异。

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

Figure 4.  Direction Distribution of Neighborhoods of Node A

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

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

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

图  5  直线性

Figure 5.  Straightness

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

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

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

根据图傅里叶变换和卷积定理，图的卷积运算通过将图的节点序列构成的图信号在图的顶点域的卷积转化为傅里叶域中的点积实现。其中，傅里叶变换是信号在时域（或空间域）和频域之间的变换，可以看作是信号在拉普拉斯算子特征函数中的展开式。将图信号处理的概念与传统信号处理的概念联系起来，图的傅里叶变换也可以看作是图信号在拉普拉斯矩阵特征向量中的展开式。图的拉普拉斯矩阵L是一个实对称矩阵，它有一组正交的特征向量$\left\{ {\mathit{\boldsymbol{X}}_l^T} \right\}_{l = 0}^{N - 1}$，且特征值[λ₀, λ₁, λ₂…λ_n-1]均为实数，L=X∧X^T, ∧=diag(λ₀, λ₁, λ₂…λ_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} $。

根据卷积定理，两函数的卷积等于它们傅里叶变换后的乘积的逆变换。图上的卷积算子也一样，图上的函数f∈Rⁿ与滤波器g_θ的卷积可表示为：

式中，g_θ(∧)是一个关于L特征值的函数，可以把它看作是卷积运算中的滤波器，g_θ(∧)=diag(θ)=diag(θ₀, θ₁, θ₂…θ_n-1)。

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

式中，$\tilde \Lambda = \frac{2}{{{\lambda _{{\rm{max}}}}}}\Lambda - {I_N}$，其中λ_max是拉普拉斯矩阵L的最大特征值; θ'∈R^k是切比雪夫系数向量，切比雪夫多项式的公式为：${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_θ'卷积的公式为：

式中，$\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个输出的计算方式如下：

式中，σ(*)是非线性激活函数，例如${\rm{ReLU}}\left( \cdot \right) = {\rm{max}}\left( {0, \cdot } \right)$; H_i^[l]是第l层的第i个输入，N为输入神经元数，H^[0]=f; H_j^[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中结果表明，该训练集训练的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%。实验结果说明，该方法能够有效提升节点的特征质量，提高模型分类的准确度。

本文以图 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。

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

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