空间目标匹配就是找出两个数据集中在地理空间位置上具有同等分布格局的实体。我国系列基本比例尺地理空间数据库逐步建成，而城市化发展带来道路网数据变化更新周期缩短，对这些不同尺度、不同精度的道路网数据进行高效管理已成为空间数据库技术的研究热点。有效解决这个问题的关键之一是对不同版本空间数据中的同名要素进行自动识别，并建立它们之间的匹配关系。因此，不同比例尺下同名实体间匹配关系的准确、快速识别与建立是后续道路数据更新、集成与融合的基础，具有重要意义^[1]。

国内外学者对道路网匹配算法已有比较深入研究，匹配算法主要分为：基于拓扑结构的匹配^[2-8]、基于几何相似度的匹配^[9-18]和基于数学模型的匹配^[19-22]。基于拓扑结构的匹配算法中，文献[7]的算法首先进行节点、弧段的粗匹配，然后利用节点和弧段拓扑关系的相似性和离散Fréchet距离进行精确匹配。基于几何相似度的匹配算法中，文献[15]提出了基于格网索引的“折线—节点”距离匹配算法，将复杂的折线与折线之间的几何相似度计算转换为求节点到折线距离的匹配方法，降低了计算复杂度，并通过建立格网索引来提高计算效率。文献[16]提出了一种基于概率理论的匹配模型，该模型在线目标匹配中融合多种匹配指标计算实体匹配概率大小来确定匹配实体。基于数学模型的算法中，文献[20]提出了一种基于概率松弛方法的道路网匹配算法。文献[22]通过多个几何指标衡量匹配对之间的几何特征差异，构建道路网回归匹配模型，并利用此模型对待匹配目标对进行匹配。

然而，由于制图综合的原因，再加上道路数据采集过程中，不同制图员会对空间抽象有着各自的理解，在制作不同比例尺的地图时，拓扑变化的规律具有不定性，不同比例尺道路网的匹配会出现一些特殊情况：

(1) 当比例尺变小时，道路网中的环会变成点、正方形或三角形道路；立交桥附属结构可能消失等情况。

(2) 当数据存在更新变化时，某一条道路在小比例尺地图上为连贯的空间目标，但在大比例尺图上可能因为道路的整改、变迁，该道路可能已经分裂成两条道路，或在道路形态结构上发生了很大的改变。

(3) 当道路网稠密时，小比例尺某条道路很可能会在大比例尺匹配数据集中找到多条长度、方向、形状等多个指标都基本一致的候选匹配对象，这就需要改进空间场景结构的评价方法。

(4) 在不同尺度下还会存在单行线变双行线、两车道变4车道等情况。

综上所述，单一匹配技术难以在不同比例尺道路网的匹配中得到较好的匹配效果。因此，本文试图融合stroke技术、多因子几何相似度计算、空间索引技术、正反双向匹配、改进的空间场景结构相似性评价方法以及stroke整体匹配与部分匹配相结合等多种技术进行不同比例尺道路网匹配。

1 不同比例尺道路网匹配的思路

不同比例尺的道路网匹配的数据处理流程如图 1所示，主要分为数据预处理、stroke整体匹配和stroke部分匹配3个部分。数据预处理部分主要完成不同比例尺道路内部节点加密、stroke连接以及空间格网索引的建立。在stroke整体匹配过程中，主要完成不同比例尺道路在几何形态和拓扑结构都相似的道路匹配。对于未匹配成功的道路，可利用stroke部分匹配，最大限度地搜查同名目标的匹配关系。

为了提高目标匹配的计算效率，算法中对多种基础几何算法进行了改进，包括近似的缓冲区代替精密缓冲区。对于克服单一几何相似度衡量指标的局限性，本文利用多个几何相似度衡量指标计算空间目标的几何相似度S(s₁, s₂)，计算见式 (1)

式中，ω₁、ω₂和ω₃均为经验权值 (ω₁、ω₂和ω₃均为正数，ω₁+ω₂+ω₃=1)；s₁和s₂表示两条stroke；H(·) 为文献[23]的所提出的Hausdorff距离修正计算方法；HT为Hausdorff距离阈值；LR (·) 为两个stroke长度之比计算函数，长度比越接近1，表明相似度越高；A(·) 是两个stroke之间的夹角 (范围在0~π之间) 计算函数，在计算过程中，两个stroke之间的夹角被抽象成由stroke首末节点所连成的线段之间的夹角；AT为夹角阈值。

根据Hausdorff距离的公式定义，若两空间目标在几何形态结构上差异较大，则两空间目标靠得再近，相互之间的Hausdorff距离也会较大。因此Hausdorff距离除了可以衡量目标之间的空间距离，还可以一定程度上衡量相互之间的几何形态结构相似度。此外，算法还融合了空间索引技术以及文献[24]的正反双向匹配。

2 空间场景结构的相似性评价

全局一致性评价是指将待匹配空间场景与候选匹配空间场景进行整体相似性评价，既评价个体相似性，同时也评价空间场景结构特征的相似性^[25]。个体相似性的衡量可利用相似度计算公式 (1) 完成，而空间场景结构的相似性则需要对stroke所处的空间分布格局进行评价。一条stroke的空间场景结构由与其首、末节点相连的stroke所构成，当需要比较两条stroke之间的空间场景结构相似度时，利用两个空间场景中相互匹配成功的stroke匹配对来计算^[25]。但是，不同比例尺道路网的抽象程度会有所不同，例如在表示同一地区的两幅不同比例尺地图上的道路数量可能存在差别，同名stroke的空间场景结构就有可能不同，导致在空间场景结构评价中出现误判断的情况。

在制图综合中，连通度、长度等被作为衡量一条道路重要性的常用指标，如果某条道路长度较长，则通常是一条具有“主干”“动脉”特点的道路，在制图综合中不易被剔除，也不容易因为时间的变化而出现消失、缩短等情况。基于这样地图制图规则，本文改进的空间场景结构评价方法如下：

(1) 对于两条可能存在匹配关系的stroke道路s(小比例尺) 和m(大比例尺)，设s的首、末节点分别为ss和se；m的首、末节点分别为ms和me。为了能保证stroke道路整体匹配中首、末节点相对应，需要先确定s与m的首、末节点对应关系。因为不同比例尺下两个同名空间目标的首末端点可能会有不同的对应关系 (若两道路的空间数据采集方向相同，则s与m的首、末节点相互对应；否则，可能是s的首节点与m的末节点相对应)。本文直接采用s与m的首、末节点相互之间的最小欧氏距离来确定节点的对应关系。若两道路首末节点走向一致，则得到两个节点对P₁(ss与ms) 和P₂(se与me)，否则，两个节点对为P₁(ss与me) 和P₂(se与ms)。

(2) 这里，设两个节点对为P₁(ss与ms) 和P₂(se与me)。对于节点对P₁，设与ss相连的stroke集合为A，与ms相连的stroke集合为B。若集合A不为空，则选出A中最长的stroke道路，记为A_i，同理在B中选出最长的B_j，转步骤 (3)(对于另外一种节点对情况可以进行类似处理)。

(3) 设A_i和B_j之间计算的几何相似度为S_s。若A和B都为空集，则S_s=1；若A、B中只有一个空集，则S_s=0；否则，利用式 (1) 进行计算S_s=S(A_i, B_j)。

(4) 得到S_s后，利用相同原理转步骤 (2)，对P₂中的节点对计算S_e。

(5) 最终的空间结构场景相似度为S_s与S_e的平均值S_{s, e}，若S_{s, e}大于给定的阈值，则认为匹配成功；否则匹配失败。

3 stroke部分匹配 3.1 算法提出的背景

当道路空间数据出现变化时，若只利用式 (1) 进行匹配，将会得到非常低的相似度。如图 2(a)所示，在小比例尺图上有s_Str₁(由弧段s₂和s₃组成) 和s_Str₂(由弧段s₁组成) 两条stroke。在数据出现更新变化的大比例尺图上则有m_Str₁(由弧段m₃组成) 和m_Str₂(由弧段m₁和m₂组成)，如图 2(b)所示。此时，小比例尺图上弧段s₁与s₂并没有连接成一条stroke，因而无法与大比例尺图上的m_Str₂相匹配。从图 2(c)可以看出，不同比例尺的道路之间存在匹配情况，但是若只是判断stroke是否整体匹配，则无法识别弧段s₃与m₃的匹配以及弧段s₂与m₂的匹配。很明显，s_Str₁与m_Str₁以及s_Str₁与m_Str₂之间只存在部分匹配的情况。

3.2 算法描述

在经过stroke整体匹配后，设未能匹配上的小比例尺的stroke集合为S(共有n条)，大比例尺的stroke集为L。本文提出的stroke部分匹配的算法如下：

(1) 若集合S和L不同时为空，则遍历集合S，对集合S中每条stroke道路S_i(其中S_i∈S; i=0, 1, …, n)，利用格网空间索引和近似缓冲区在集合L中搜索出候选匹配集为M；否则结束。若集合M为空，则将S_i从集合S中剔除，继续遍历S中的stroke；否则，设M共有m条stroke，对M的每一条stroke道路M_j(其中M_j∈M; j=0, 1, …, m) 进行遍历处理。

(2) 设S_i的弧段数为NS_i，每条弧段表示为S_{i, q}(其中，q=0, 1, …, NS_i)；设T为Hausdorff距离阈值。利用文献[21]提出的SM_HD算法计算S_i中的每一条弧段S_{i, q}与M_j的Hausdorff距离H_q。若H_q＞T，则设S_{i, q}的属性值HB_{i, q}为false，否则HB_{i, q}为true。这样就可以得到S_i各个弧段相对于M_j的Hausdorff距离是否满足阈值的一个布尔型集合PS_i

同理，设M_j的弧段数为NM_j，反过来计算M_j中每一条弧段M_{j, p}(其中，p=0, 1, …, NM_j) 与S_i的Hausdorff距离H_p，同理可得到HB_{j, p}并形成布尔型集合PM_j

若PS_i或PM_j其中之一的元素全为false，则继续对集合M的下一个stroke元素M_j+1进行处理；否则，转到步骤 (3)。

(3) 对PS_i和PM_j的元素值分别进行对比分析，若元素值从左到右连续的都为true值，则组成一个匹配体。PS_i中第k个匹配体可以表示为P_kS_i=[S_{i, k′}, S_{i, k″}](其中k′、k″≤NS_i，且k′、k″之间连续)，这说明在S_i中，从S_{i, k′}到S_{i, k″}之间的所有弧段的HB属性值均为true，且所有弧段在S_i中连续 (依次相连)。

(4) 对PS_i和PM_j中的每个下标k一致的匹配体进行组合，形成一个“匹配对”，得到“匹配对”集合P。

(5) 遍历P，对每个“匹配对”中所包含的S_i中的弧段和M_j中的弧段分别重新连接成stroke。

(6) 对新生成的stroke进行长度比值和夹角计算。若长度比值和夹角都符合阈值条件，则认为部分匹配成功，将部分匹配成功的所有弧段标志为已匹配。若长度比值或夹角其中之一不符合阈值条件，则对较长的stroke按照顺序 (从首至末) 剔除一条弧段后，将所剩下的弧段生成新stroke，再与“匹配对”中较短的stroke进行长度比值和夹角的计算，直至符合阈值条件或弧段全部剔除完，继续遍历P，若P已遍历完毕，转至步骤 (7)，否则转至步骤 (5)。

(7) 检查M是否被遍历完毕。若遍历完毕，则对S_i的下一元素S_i+1进行处理，转至步骤 (1)；否则，对M_j的下一元素M_j+1进行处理，转至步骤 (2)。

4 试验与分析

为了校验本文所提出的算法对不同比例尺下的道路网匹配的有效性，选择了VS2010(C#) 进行了算法的设计与实现。

4.1 比例尺变化较小的试验

试验选取了南昌市某地区两幅比例尺分别为1:5000和1:2.5万的道路网数据。其中，大比例尺地图中弧段数、stroke数和总长度分别为739条、502条和1 027.4 km。而小比例尺地图中弧段数、stroke数和总长度分别为301条、176条和634.8 km。试验中，设插入点距离、Hausdorff距离阈值以及近似缓冲半径均为150 m。两种数据叠加后的情况如图 3所示。

在图 3中的A区域放大后如图 4(a)所示，大比例尺图上原为双行道 (M₁和M₂)，在道路某处拓宽为4车道 (增加a和b)，但在小比例尺图中抽象为一条道路S。图 3的B区域放大后为图 4(b)所示，大比例尺图上有纵横交叉的道路所构成的十字路口，在十字路口处还存在一些道路附属结构，使得道路交叉口处道路十分稠密，但在小比例尺地图上，抽象简化为纵横交叉的两条相交道路。

在匹配处理后，得到图 4(a)中S与M₁、M₂匹配，但并没有把a和b纳入为匹配对象。所以，本算法在处理多车道目标匹配问题时，只选择最佳匹配的对象，因为抽象而退化的附属结构目标不参与匹配。图 4(b)中也是如此, S与M₁、M₂匹配，十字交叉路口的附属结构道路没有被纳入匹配对象。

图 3上的C区域放大后如图 5所示，在大比例尺地图上弧段a、b、c和d组成一条stroke (m_stroke)，但在小比例尺地图上，由于道路结构发生了变化，在小比例尺上不再存在与弧段b、c相匹配的目标，即大比例地图上的m_stroke在小比例尺地图上缺少圆弧部分，分成s₁和s₂两条stroke。在进行stroke部分匹配过程中，计算得到s₁与a的几何相似度为0.990，s₂与d的几何相似度为0.905。此两个匹配对都符合匹配阈值要求。

4.2 比例尺变化较大的试验

试验数据为合肥市某地区的比例尺变化较大的两幅地图数据 (1:5000和1:10万)。小比例尺数据与大比例尺数据在道路形态和测量精度上都有较大的差异。其中，大比例尺地图中弧段数、stroke数和总长度分别为1945条、1294条和1 308.7 km。而小比例尺地图中弧段数、stroke数和总长度分别为359条、143条和629.5 km。试验中，设插入点距离为150 m，Hausdorff距离阈值为200 m，近似缓冲半径300 m。两种数据叠加后的情况如图 6所示。

图 6中的区域A放大后如图 7所示，大比例尺的环形道路结构变为小比例尺图上的十字路口。在进行stroke匹配时，小比例尺的弧段a′和c′会连接成s_stroke₁，弧段b′和d′会连接成s_stroke₂。而在大比例尺道路中，因为弧段a、b、c和d与环连接，所以它们各自成一条stroke。在匹配过程中，s_stroke₁与弧段a所在的stroke和弧段b所在的stroke的几何相似度分别是0.562和0.517，空间场景结构相似度均为0。所以，需要进行stroke部分匹配，s_stroke₁的a′弧段形成的stroke与弧段a形成的stroke的几何相似度为0.934，c′弧段所在的stroke与弧段c形成的stroke的几何相似度为0.942，说明这两个“匹配对”的匹配成功。

图 6中B区域放大后如图 8所示，在复杂的道路连接口处，在大比例尺图上为横向分布的两条道路连接纵向分布的双行道，并在连接口处出现分叉的连接结构。而在小比例尺图上，因为比例尺度跨度较大的原因，直接抽象成十字交叉路。经过stroke整体匹配和stroke部分匹配算法处理后，弧段a与弧段a′匹配，弧段b与弧段b′匹配。而双行道c在几何形态和空间场景结构都与c′相似度高，无需进行stroke部分匹配算法就可完成匹配过程。

4.3 城郊接合部与乡村道路的试验

以上两个试验主要针对城市道路网的匹配，为了验证本算法的高适应性，选取了城郊接合部 (武汉市某地区，试验3) 和乡村道路 (佛山市某地区，试验4) 作为试验数据，这两类数据的大小比例尺都分别为1:5000和1:2.5万。两次试验都设插入点距离、Hausdorff距离阈值以及近似缓冲半径均为150 m。其中，城郊接合部大比例尺地图中弧段数、stroke数和总长度分别为258条、211条和20.5 km。而小比例尺地图中弧段数、stroke数和总长度分别为144条、100条和15.9 km。城郊接合部的数据在比例尺变化不大时较少存在拓扑结构发生变化的匹配情况，利用stroke整体匹配即可取得较好的匹配效果。

乡村道路的试验数据中，大比例尺地图中弧段数、stroke数和总长度分别为133条、77条和14.3 km。而小比例尺地图中弧段数、stroke数和总长度分别为70条、26条和11.9 km。乡村道路的数据与城郊接合部数据特点相似，但乡村道路数据变化更新频繁，部分区域的匹配需要stroke部分匹配算法进行处理。

4.4 试验结果对比分析

为了对匹配效果进行评价, 采用人工方式对试验匹配结果进行了检查, 并利用文献[21]的评价公式对结果进行评估, 见式 (2)

式中, P为匹配准确率；R为匹配召回率；f(C) 为正确匹配数；f(W) 为错误匹配数；f(U) 为漏匹配数。前后4次试验结果的统计信息如表 1所示。表中除试验3外各个试验中f(C)+f(W)+f(U) 都大于相应试验数据中的小比例尺的stroke数目。其原因是在匹配过程中，一部分小比例尺的stroke会在部分匹配中由一条stroke分成了若干条stroke形成若干匹配对。

根据试验结果的统计信息，本算法有着较高的匹配准确率和召回率。按照“数据集总长度/耗时”计算匹配速度，得到试验1至试验4的匹配速度分别是641.8 km/s、791.1 km/s、1 213.3 km/s和524 km/s。在试验1中匹配速度之所以低于试验2，是因为试验2中比例尺变化较大，在大比例尺道路网中存在大量没有匹配对象的细小stroke，从而减轻了计算压力。而试验3和试验4因为数据复杂度较低、路网稀疏，匹配速度较高。

5 结语

本文通过分析不同比例尺下的道路网匹配所存在的问题和技术难点，提出了一种融合多种道路网匹配技术的策略。同时，对空间场景结构的评价方法进行了改进，针对整体stroke匹配不能适应存在数据变化的道路网匹配情况，提出了stroke部分匹配方法。试验表明，本文所提出的方法具有较高的匹配准确率、召回率和运行效率，且在处理不同比例尺道路网中的拓扑结构变化时也能有很好的适应性，可适用于不同比例尺的国家基本比例尺地理空间数据库的道路网匹配。但是，阈值和权重这些参数目前都是通过人为经验设定的。在今后的研究工作中，将研究如何根据具体的数据自动设定阈值和权重，以进一步确保匹配的效果和质量。