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

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

Figure 1.  Example of Road Network and Graph Representation

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

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

$R_w$反映了连接对路段形态的复杂程度。用化简前后连接对长度$l_{ab}$与$s_{ab}$的比值来表示，如图 2（a）所示。

图  2  连接对参量提取

Figure 2.  Link Pairs Parameters Extraction

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

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

$R_c$描述连接对角度偏转的程度，通过叠加节点路段在每个转折点处的偏转角度获得。构成格网的节点路段可能包含数个直角拐角，使用累计偏转角可以将路段内部角度变化的特征体现出来。设一条节点路段根据其n个折点可以划分为$a_{\mathrm{0}},a_{\mathrm{1}}\dots a_n$共$n+\mathrm{1}$条子路段，${\theta }_{a_{\mathrm{0}},a_{\mathrm{1}}}$表示子路段$a_{\mathrm{0}}$和$a_{\mathrm{1}}$间的偏转角，则该路段的累计偏转角就是所有${\theta }_{a_i,a_{i+\mathrm{1}}}$的和，如图 2（b）所示。由于每个连接对由两条路段组成，因此，将两条路段的累计偏转角相加作为整个连接对的累计偏转角。对于路段$a$和$b$组成的连接对，其累计偏转角计算公式为：

$R_a$是指连接对两条节点路段所构成的夹角，是格网识别的重要依据。格网模式中节点路段的连接角存在90°和180°两种情况。夹角为90°的连接对构成了格网的一个拐角，夹角为180°的连接对构成了格网的一条边。以路段交点为起点，到路段两端$p_{\mathrm{1}}$和$p_{\mathrm{2}}$的向量分别为a和b，则连接角的计算公式为：

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

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

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

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

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

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

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

本文图结构中，节点的度是指与该节点连接的边数。在利用连接对的特征去除图中的非格网边后，图中可能存在度为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所示。

利用计算得到的连接对的特征化简路段连接图，各参数阈值$[r_{\mathrm{1}},r_{\mathrm{4}}]$通过经验和数据确定。从数据中随机采集了部分构成格网的连接对，分析样本连接对的各个特征分布，并结合各连接对参数所反映的格网的特征，确定参数阈值。在试验中，设置形态复杂度、长度比和累计偏转角的阈值分别为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

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