论文推荐|刘闯：利用城市骨架线网的道路和居民地联动匹配方法

《测绘学报》

构建与学术的桥梁        拉近与权威的距离

阅读以下链接
赢中图集团旅游精品！

利用城市骨架线网的道路和居民地联动匹配方法

刘闯, 钱海忠, 王骁, 何海威, 谢丽敏, 王成舜     

信息工程大学地理空间信息学院, 河南 郑州 450052

收稿日期：2016-05-09； 修回日期：2016-09-10

基金项目：国家自然科学基金（41171305；41571442）

第一作者简介： 刘闯(1992-),男,硕士生,研究方向为空间数据匹配与更新、自动制图综合。

E-mail:

通信作者： 钱海忠

E-mail:

摘要：同名道路或者居民地数据间由于数据一致性程度不高，往往存在较大的几何位置偏差，当对道路或者居民地单独进行匹配时，不利于提高匹配正确率和效率。针对这一问题，本文提出了一种利用城市骨架线网的道路和居民地联动匹配方法。联动匹配即模仿人在读图时通过特征地物和空间关联寻找目标地物的思维过程，将匹配看作是一种特征目标寻找、信息关联传递的推理过程。首先，利用约束Delaunay三角网对地图构建城市骨架线网。然后，通过道路、骨架线、骨架线网眼和居民地之间的拓扑关系建立道路和居民地之间的匹配传递模型。最后，根据该传递模型实现通过道路匹配带动居民地匹配或者通过居民地匹配带动道路匹配的联动匹配。该方法优势在于只要有一种要素的数据一致性比较好，就能带动另一种要素取得很好的匹配效果，同时符合人类进行匹配时的认知过程。

关键词： 城市骨架线网     道路匹配     居民地匹配     联动匹配     拓扑关系    

A Linkage Matching Method for Road and Habitation by Using Urban Skeleton Line Network

LIU Chuang, QIAN Haizhong, WANG Xiao, HE Haiwei, XIE Limin, WANG Chengshun     

Abstract: Obvious data consistency degree is not high in roads or habitation data, often in the presence of large geometric position deviation, which is not conducive to improve the accuracy and efficiency of road or habitation matching. A linkage matching method for road and habitation by using urban skeleton line network is proposed to solve this problem. The linkage matching imitates the human thinking process of searching for target objects by the signal features and spatial correlation when reading maps, regarding matching as a reasoning process of goal feature searching and information association transmitting. Firstly, urban skeleton line network is constructed by constraint Delaunay triangulation network; then, the topological relationship among road, skeleton line, skeleton line mesh, habitation is constructed; last, matching transmission model is established by the topological relationship. According to this matching transmission model, linkage matching is fulfilled, which contains road matching drives habitation matching or habitation matching drives road matching. The advantage of this method is that as long as there is an element of data consistency is good, can drive another element to obtain a very good matching effect, at the same time conform to the human cognitive process.

Key words: urban skeleton line network     road matching     habitation matching     linkage matching     topology relationship    

随着我国城市化进程的加快，城市地理要素发生了翻天覆地的变化，如各种道路的改造和新建、大片居民地小区的建设、老城区拆迁与改造等，涉及各种繁杂的地理实体变化，这为地理空间数据的更新带来了巨大的挑战。与此同时，空间数据应用的多样性和复杂性决定了单一来源的空间数据往往很难满足实际应用的需要，如何将这些数据进行有效集成或合并，以达到数据共享、优势互补的目的，成为当前GIS面临的又一突出问题^[-]。无论是空间数据更新还是空间数据集成与融合，都要用到一项关键技术——同名实体匹配，其基本原理是通过一系列相似度指标或评价策略，识别出不同来源地图数据库中表达现实世界同一地物的地图要素的过程^[]。同名实体匹配是后续数据集成、融合以及更新的基础，具有重要应用意义。道路和居民地数据在城市化进程中变化尤其明显，对此展开研究更为迫切。据此，国内外学者围绕道路数据和居民地数据匹配进行了大量研究。

道路匹配方法大致可以分为以下3类：①利用“缓冲区增长”确定待匹配线串的候选匹配集进行匹配^[-]，此类方法简单易行，是道路匹配的常用方法；②利用曲线节点、形状、距离等几何特征进行匹配^[-]，该类方法主要是通过道路弧段的距离测度直接对道路弧段匹配，或者根据道路节点之间距离远近、拓扑结构相似性等对道路节点匹配实现道路匹配;③综合运用多个评价指标，从整体到局部进行匹配^[-]，该类方法主要运用道路网自身的空间结构特征进行匹配。

居民地匹配方法大致可以分为以下3类：①利用面积重叠率或面要素缓冲区面积重叠率进行匹配^[-]，显然重叠度越高，则匹配的可能性越大;②利用面要素轮廓形状相似性进行匹配^[-]，该类方法主要依据形状描述函数计算面要素轮廓形状相似性，通过比较相似性数值进行匹配;③综合运用多个指标进行加权综合或借鉴已经成熟的技术进行面要素匹配^[-]。这类方法通常借鉴已经成熟的技术方法如降维技术、骨架线技术等进行面要素匹配。

上述研究方法极大地推动了道路与居民地匹配技术的发展。但是进一步研究发现，当前对道路和居民地要素的匹配大多数是采取单独匹配的策略，当遇到较复杂的情况时，如道路数据一致性程度不高，存在较大的几何位置偏差或者居民地数据形状同质化较高，这时只考虑单一要素的匹配方法，往往不能取得较好的匹配效果。究其原因是没有从制图员的角度综合考量该要素所处的环境，对道路和居民地联动匹配方面的研究还相对较少。

1 联动匹配实现的关键技术

联动匹配的概念是：通过一个要素的匹配带动另一个要素的匹配，即当一个要素匹配结束后，和该要素关联的另外一个要素也随即完成匹配，而不需进行单独的匹配。联动匹配的实现能够简化匹配过程，提高匹配效率。

在实际矢量地图中，道路要素和居民地要素是处于分离状态、没有任何联系的，这不利于实现道路与居民地的联动匹配，本文引入城市骨架线网技术^[]建立道路与居民地的关联关系。

1.1 城市骨架线网概述

城市骨架线网，是指将二维的城市面状空间用一维的线状要素来进行概括。城市骨架线网在简化城市空间的同时，能够较好地保持城市空间的形态特征和分布情况。如所示，城市骨架线网由道路和空白区域骨架线两部分线要素构成。具体来说，地图中存在道路的地方，直接将道路视为城市骨架线；地图中道路和居民地以外的空白区域，则对其提取骨架线。分别将城市骨架线网中这两种来源的骨架线称为道路骨架线和空白区域骨架线。

图 1 城市骨架线网构成要素Fig. 1 Structure of urban skeleton line network

城市空白区域，指的是地图幅面中除了道路和居民地以外的所有区域的总和()。空白区域按照要素类型划分为面状要素，但是空白区域是较为特殊的面状要素，与普通的居民地、植被、水系等面状要素相比有具有明显的区别，具有范围大、内部孔洞多的特点，并且与道路、居民地一起构成了地图的全部幅面范围，是道路和居民地的补集。

图 2 地图幅面组成示意图Fig. 2 Diagram of map composition

1.2 城市骨架线网构建

1.2.1 空白区域骨架线提取

城市骨架线网由道路和空白区域骨架线两部分组成，本文采用约束Delaunay三角网方法提取空白区域骨架线。首先基于相似三角形原则对道路、居民地数据进行节点加密处理^[]。然后以加密处理后的道路和居民地外围轮廓为约束边，对整个居民地和道路数据构建约束Delaunay三角网，如所示。

图 3 构建约束Delaunay三角网Fig. 3 Constructing constraint Delaunay triangulation network

构建约束Delaunay三角网后即可依据三角网形成的三角形的类型()提取空白区域骨架线，三角形分类依据是其3个顶点在道路和居民地上的数量和位置，具体原则如下：①ⅰ类三角形：3个顶点均在居民地轮廓上；②ⅱ类三角形：1个顶点在道路上，另两个顶点在不同的居民地轮廓上；③ⅲ类三角形：1个顶点在道路上，另两个顶点在相同的居民地轮廓上；④ⅳ类三角形：两个顶点在道路上，另一个顶点在居民地轮廓上；⑤ⅴ类三角形：3个顶点均在道路上。

图 4 三角形分类^[]Fig. 4 Classification of triangle

三角形分类后，对上述5类三角形按照所示的方法提取骨架线^[25]。对ⅰ类三角形，首先判断其三边是否为约束边，然后将非约束边的中点与三角形中心相连(、、)；对ⅱ类三角形，直接将在道路上的唯一顶点与其对边中点相连()。对ⅲ、ⅳ、ⅴ类三角形不进行任何连接。对三角网形成的所有三角形按照该方法连接后即可得到空白区域骨架线，如所示。将空白区域骨架线和道路网结合起来即可得到城市骨架线网，如所示。

图 5 空白区域骨架线提取方法Fig. 5 Extraction of skeleton line in blank area

图 6 空白区域骨架线提取结果Fig. 6 Skeleton lines of blank area

图 7 城市骨架线网Fig. 7 Urban skeleton line network

1.2.2 城市骨架线网化简

城市骨架线网化简主要是对空白区域骨架线的化简，按照约束Delaunay三角网法提取出的空白区域骨架线存在如所示的复杂弯曲、孤立链、悬挂链这3种不理想的情况。这3种情况不利于后续的联动匹配，会干扰匹配结果。

图 8 空白区域骨架线问题Fig. 8 Problems of skeleton line in blank area

复杂弯曲是存在最多的一种情况。由于空白区域骨架线是通过连接三角形中心和相应边中点提取的，并且三角形分布密集，故极易出现类似“锯齿状”的复杂弯曲。这种弯曲显然是多余的，并不是骨架线自身的形态特征，会增加后续匹配的复杂度，故需对其进行化简。本文采用简单的“拉直”处理这些复杂弯曲，拉直处理后需要满足两个条件：一是骨架线不能与居民地相交；二是骨架线需保持必要的形态特征。

悬挂链和孤立链的出现是由居民地凹部造成的。由于约束Delaunay三角网法是一种较为敏感的骨架线提取方法，所以当居民地轮廓形态中出现凹陷时，通过骨架线能够反映出来。显然这两种情况也是多余的，需要进行处理，直接删除即可。通过化简可得满足后续匹配要求的最终城市骨架线网，如所示。

图 9 化简后城市骨架线网Fig. 9 Urban skeleton line network after simplification

1.3 城市骨架线网眼

在城市骨架线网中，将纵横交错的城市骨架线所围成的最小闭合区域称为“骨架线网眼”^[]，中黑色渐变填充区域即为骨架线网眼。骨架线网眼并不是真实存在的地理对象，而是为了更好地认识骨架线网的结构特征而抽象出来的面要素对象。骨架线网眼有如下特点：骨架线网眼由骨架线组成外围轮廓、每个骨架线网眼中只包含一个居民地要素、骨架线网眼之间是无缝连接的。

图 10 城市骨架线网眼Fig. 10 Urban skeleton line network mesh

根据骨架线网眼的上述特点，可以看出骨架线网眼是连接道路和居民地的“纽带”。通过骨架线网眼，能够把空间上分离的道路要素和居民地要素联系起来，从而为实现道路和居民地要素的联动匹配奠定基础。

1.4 城市骨架线分类

明确骨架线来源主要是为后续的由道路匹配联动居民地匹配奠定基础。本文借鉴道路网中的拓扑分类方法^[]，将城市骨架线网分为5种类型，分类依据如下：记StartN(L_i)为与骨架线L_i首节点相连接的其他骨架线数量；EndN(L_i)为与骨架线L_i末节点相连接的其他骨架线数量；A(L_i)为骨架线L_i参与构成的骨架线网眼数量，则按照如下标准可将骨架线网分为如所示的Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ，共5种类型：①Ⅰ类骨架线，StartN(L_i)>1且EndN(L_i)=0，或者StartN(L_i)=0且EndN(L_i)>1；②Ⅱ类骨架线，StartN(L_i)>1且EndN(L_i)>1且A(L_i)=0；③Ⅲ类骨架线，StartN(L_i)>1且EndN(L_i)>1且A(L_i)=1；④Ⅳ类骨架线，StartN(L_i)>1且EndN(L_i)>1且A(L_i)=2；⑤Ⅴ类骨架线，StartN(L_i)=0且EndN(L_i)=0。

图 11 5种类型骨架线Fig. 11 Five types of skeleton line

由于城市骨架线网是由道路和空白区域骨架线构成，所以通过骨架线的分类依据可以判断出其来源。如所示，Ⅰ、Ⅱ、Ⅲ、Ⅴ类骨架线均来源于道路，而Ⅳ类骨架线既来源于道路，又来源于空白区域骨架线。

表 1 骨架线类型来源Tab. 1 Source of skeleton line

骨架线类型	骨架线来源
Ⅰ类骨架线	道路骨架线
Ⅱ类骨架线	道路骨架线
Ⅲ类骨架线	道路骨架线
Ⅳ类骨架线	道路骨架线、空白区域骨架线
Ⅴ类骨架线	道路骨架线

2 道路和居民地联动匹配模型2.1 道路、骨架线、居民地、骨架线网眼之间拓扑关系

道路、骨架线、骨架线网眼以及居民地之间具有如下的拓扑关系()：道路与骨架线之间为相等关系，即道路一定等于骨架线，而骨架线其中一部分等于道路； 骨架线与骨架线网眼两者之间为关联关系，即一条骨架线关联了一至两个骨架线网眼，一个骨架线网眼关联了至少3条骨架线；骨架线网眼与居民地两者之间为一一对应关系。从这种拓扑关系结构图中可得，在地图上原本在空间上处于分离状态、没有任何联系的道路和居民地要素，通过骨架线网眼而联系起来，这就为道路和居民地的联动匹配奠定了基础。

图 12 道路、骨架线、骨架线网眼以及居民地之间拓扑关系Fig. 12 Topological relationship of road,skeleton line,skeleton line mesh and habitation

2.2 联动匹配

联动匹配实际上是一种通过拓扑关系来传递匹配结果的思想，符合人类进行匹配时的认知过程。居民地匹配结果能够根据包含关系传递给骨架线网眼，骨架线网眼根据关联关系，能够把匹配结果传递给骨架线，进而骨架线完成匹配，也即完成了道路的匹配，从而能够实现居民地匹配带动道路匹配的联动匹配效果。

反过来，道路匹配结果通过关联关系能够传递到骨架线网眼，而骨架线网眼匹配结果再根据包含关系能够传递到居民地，从而实现道路匹配带动居民地匹配的联动匹配效果。如所示，数据源1与数据源2的匹配结果可按照上述的匹配传递模型一步步进行传递，从而实现联动匹配。

图 13 匹配传递模型Fig. 13 Model of matching transfer

2.2.1 居民地匹配联动道路匹配

居民地匹配联动道路匹配的步骤如下：

步骤1：获取居民地、骨架线网眼、骨架线、道路之间的拓扑关系，将其存入对应类变量中。

步骤2：对数据双方中的居民地要素进行匹配，具体的匹配方法可以选择面积重叠率法、缓冲区匹配法等，得到居民地匹配结果。

步骤3：根据拓扑关系与匹配传递模型，将居民地匹配结果传递到其包含于的骨架线网眼中，获得骨架线网眼的匹配结果。

步骤4：根据拓扑关系，获得每个骨架线网眼包含的骨架线集合，设骨架线集合中道路骨架线数量为N_R，再进行下面3种判断：①若N_R=0，则该骨架线网眼的匹配结果无需传递给骨架线；②若N_R=1，则双方骨架线网眼中这唯一一条道路骨架线互相匹配，得到道路匹配结果；③若N_R≥2，则需对这些道路骨架线进行小范围的精确匹配，匹配结果即为最终的道路匹配结果。匹配流程如所示。

图 14 联动匹配流程图Fig. 14 Flow Chart of linking matching

需特别说明的是，通常一个骨架线网眼中一般最多只包含两条道路骨架线，故道路匹配关系的获得相对比较简单，只有在极少数情况下道路骨架线数量才大于2条，这是由骨架线网眼的构成方法决定的。所以可认为骨架线网眼的匹配结果可直接传递到道路，从而获得道路匹配结果。

2.2.2 道路匹配联动居民地匹配

道路匹配联动居民地匹配的过程与居民地联动道路匹配的过程有所不同，其采用拓扑关系不能一次性地将匹配结果进行传递，根据骨架线分类进行改进，采用如下的步骤进行：

步骤1：获取道路、骨架线、骨架线网眼、居民地之间的拓扑关系，将其存入对应类变量中。

步骤2：对数据双方中的道路要素进行匹配，具体的匹配方法可以选择缓冲区增长算法、Hausdorff距离判断法等，得到道路匹配结果；同时对空白区域骨架线进行匹配，得到其匹配结果。

步骤3：判断骨架线网中的骨架线类型，得到5类骨架线(1.4节所述)。

步骤4：将Ⅲ类骨架线的匹配结果传递到其关联的唯一骨架线网眼中，获取外围骨架线网眼的匹配结果，并将外围骨架线网眼匹配结果传递到其包含的居民地中，获取部分居民地匹配结果。

步骤5：设经过外围匹配后，未匹配的居民地数量为N_UH：①若N_UH≠0，则剔除Ⅰ、Ⅱ、Ⅲ、Ⅴ类骨架线，将剩余骨架线视为新的未判断类型的骨架线，跳回步骤3；②若N_UH=0，则结束匹配，此时所有居民地要素均以取得匹配关系。匹配流程图如所示。

根据上述步骤可以得出，通过道路要素匹配联动居民地要素匹配是一个迭代匹配的过程，骨架线(道路)匹配结果不能一次性通过拓扑关系传递给居民地，这是由于一条骨架线(Ⅳ类骨架线)可能关联两个骨架线网眼，这就使得匹配关系传递变得复杂；由于Ⅲ类骨架线只关联1个骨架线网眼，所以其匹配关系能够直接传递；通过迭代操作使得所有的道路结果均能直接传递给骨架线网眼，从而传递给居民地，实现联动匹配。

3 试验与分析3.1 数据来源与匹配方法

3.1.1 联动匹配数据来源

选取某城市同一区域、相同比例尺的4幅不同来源的数据作为试验数据，进行算法验证。两两数据源叠加显示效果如和所示。其中，中居民地数据一致性比较好，道路数据存在较大位置偏差。中道路数据一致性比较好，居民地数据存在较大位置偏差。

图 15 匹配数据叠加显示效果Fig. 15 Overlap of matching data

根据上文介绍，首先对两组匹配数据分别构建城市骨架线网并对其进行化简，得到和所示效果；然后分别获取两数据源中居民地、骨架线网眼、骨架线、道路之间的拓扑关系，最后进行道路和居民地联动匹配试验。

图 16 构建城市骨架线网Fig. 16 Constructing urban skeleton line

3.1.2 居民地匹配联动道路匹配试验

对中的道路偏差数据进行居民地匹配联动道路匹配试验，并用经典的缓冲区增长方法做对比试验。采用面积重叠率法对两数据中的居民地要素进行匹配，得到所示的居民地匹配结果，其中短线连接的是两个互相匹配的居民地。

图 17 居民地匹配结果Fig. 17 Matching results of habitation

根据居民地匹配结果，即可根据拓扑关系将匹配结果进行传递得到道路匹配结果，而不需要进行单独的道路匹配，从而简化了匹配过程。所示为居民地匹配结果所联动的道路匹配最终结果。

图 18 居民地匹配结果联动道路匹配结果Fig. 18 Matching results of road linked by habitation matching results

对中的数据用道路缓冲区增长方法经进行对比试验，经反复试验，发现当缓冲区半径为20时，道路匹配正确率相对高，试验结果如所示。

图 19 道路偏差数据缓冲区增长法匹配结果Fig. 19 The result of road deviation buffer growth matching

3.1.3 道路匹配联动居民地匹配试验

对中的居民地偏差数据进行道路匹配联动居民地匹配试验。采用缓冲区增长算法对两数据中的骨架线要素进行匹配，得到匹配结果，如所示。

图 20 骨架线匹配结果Fig. 20 Matching results of skeleton line

因为骨架线是匹配的，所以每条道路所参与构成的骨架线网眼也是匹配的，从而每个骨架线网眼中所包含的居民地也是匹配的，由此根据一条道路的匹配结果得到居民地的匹配结果，如所示。

图 21 道路匹配结果联动居民地匹配结果Fig. 21 Matching results of habitation linked by road matching results

对中的数据用缓冲区面积重叠率法进行对比试验，缓冲区半径为7.5，其试验结果如所示。

图 22 居民地偏差数据缓冲区面积重叠率法匹配结果Fig. 22 The result of habitation deviation buffer area overlap rate matching

3.2 试验分析

根据试验结果进行结果统计，从匹配率、匹配正确率两方面进行试验对比分析。其中匹配率是指匹配结果中实现匹配的要素个数与同名要素个数的比值；匹配正确率是指匹配结果中正确匹配的要素个数与匹配要素个数的比值。试验结果如、所示。

表 2 居民地匹配联动道路匹配结果质量评价Tab. 2 Quality of linkage matching results %

匹配方法	匹配率	匹配正确率
居民地匹配结果	95.5	92.3
居民地匹配结果联动道路匹配	93.3	89.3
偏差道路缓冲区增长法匹配	83.3	64

表 3 道路匹配联动居民地匹配结果质量评价Tab. 3 Quality of linkage matching results %

匹配方法	匹配率	匹配正确率
道路匹配结果	93.3	92.8
道路匹配结果联动居民地匹配	92.7	93.7
偏差居民地缓冲区法匹配	72.5	78

从和中可以得出，当道路和居民地数据一方存在位置偏差时，传统的缓冲区增长法和缓冲区面积重叠率法都是通过增大缓冲区半径来增加同名实体的重叠，但同时也会增加与周边要素的重叠，形成错误匹配。本文方法实现了居民地匹配联动道路匹配或者道路匹配联动居民地匹配，只要有一方要素数据一致性较好，就可以使数据一致性较差的要素很好地实现匹配。

值得注意的是，联动匹配的质量受到联动源要素匹配质量影响较大。例如，居民地匹配结果质量高，则其联动的道路匹配结果质量也相对较高；反之，居民地匹配结果质量较低，则其联动的道路匹配结果质量也相对较低。因为通过本文的传递模型不仅能够将正确的匹配结果传递给另一种要素，同时也将其错误进行了传递。道路匹配、居民地匹配的结果不可能达到100%的正确率，所以这些错误的匹配结果也会传递到相应的另一种要素的匹配，这是联动匹配难以避免的问题。

避免这种错误传递的方法是，在一种要素匹配结束后，对其匹配质量进行评价，设定适当的联动匹配传递阈值，若其匹配正确率大于阈值，则可将其结果传递给另一种要素的匹配；若匹配正确率小于阈值则不能将结果进行传递，需要通过检查对匹配结果进行修改达到传递阈值。通过这种方法能够有效避免错误的传递，从而提高联动匹配的正确率。

4 结论

本文提出了一种道路和居民地要素的联动匹配方法，通过构建城市骨架线网，将地图中在空间上分离的道路和居民地要素依托拓扑关系进行联系，根据匹配传递模型，实现道路匹配结果联动居民地匹配，以及居民地匹配结果联动道路匹配的联动匹配模式。该方法的优势在于，只要有一种要素的数据一致性较好，就能够带动另一种要素取得很好的匹配效果。联动匹配为空间数据匹配提供了新的方法和手段，同时也为后续的数据更新与融合等提供了新的技术支撑。如何在多尺度道路和居民地数据中实现联动匹配是进一步研究的内容。

【引文格式】刘闯，钱海忠，王骁，等。 利用城市骨架线网的道路和居民地联动匹配方法[J]. 测绘学报，2016，45(12)：1485-1494. DOI: 10.11947/j.AGCS.2016.20160221 

---

更多精彩内容：

权威 | 专业 | 学术 | 前沿

微信投稿邮箱 | [e-mail]

微信公众号中搜索「测绘学报」，关注我们，扫描上图二维码，关注学术前沿动态。

欢迎加入《测绘学报》作者QQ群： 297834524

进群请备注：姓名+单位+稿件编号