Multi-scale Surface Entity Cascade Update Method based on Natural Grid Network Index

  • JIAO Yangyang , 1, 2, 3, * ,
  • LIU Pingzhi 2, 3 ,
  • XIONG Shun 2, 3 ,
  • XU Daozhu 2, 3
Expand
  • 1. Information Engineering University, Zhengzhou 450001, China
  • 2. State Key Laboratory of Geo-information Engineering, Xi'an 710054, China
  • 3. Xi'an Research institute of Surveying and Mapping, Xi'an 710054, China
* JIAO Yangyang, E-mail:

Received date: 2021-07-14

  Request revised date: 2021-09-04

  Online published: 2022-07-25

Supported by

National Natural Science Foundation of China(42071450)

National Natural Science Foundation of China(41801396)

Copyright

Copyright reserved © 2022.

Abstract

The incremental cascade updating of multi-scale geospatial data is one of the important means to enhance the real time of geospatial data. The incremental cascade updating includes multi-scale data matching, correlation relationship establishment, matching and change detection, incremental information generalization, and incremental cascade update. The adjacent scale data matching is the basic of multi-scale data correlation establishment and an important foundation for the implementation of incremental cascade update. Aiming at the low accuracy and efficiency of association matching between multi-scale entities with the same name in existing methods, an incremental cascade updating method of multi-scale surface entities based on natural grid index is proposed. By building the natural grid and coding, building the surface entity and assigning code, adjacent scale entity matching and associated relationship, the corresponding steps of the correlation relationship are established, and the natural grid index is introduced into the incremental cascade update. The specific steps include: firstly, incremental packets of the same source and same scale vector spatial data are detected; secondly, the grid location of the updating entity is determined by the natural grid index, and then deleted and updated automatically or manually; and finally, the cartographic generalization and edge joining are implemented. Taking the residential elements in Hushan villiage of Ganzhou City as an example, the experimental results show that: 1) when the matching threshold is set to 0.51, compared to the direct matching method, the time consumed by the natural grid index method proposed in this paper is reduced by 88.4%, and the recall and precision are increased by 5% and 4%, respectively, which demonstrates the effectiveness of the natural grid index method in matching geographical elements between adjacent scales; 2) compared with the traditional Hausdorff distance, Euclidean distance, and centroid methods, the method proposed in this paper performs best with low time cost (1.34s), and high recall (66.5%) and precision rates (94.1%), which demonstrates the effectiveness and efficiency of the cascade update method proposed in this paper; 3) the proposed method can avoid the influence of the difference of associated residential areas, thus greatly reducing the operation time of manual editing, and effectively improving the accuracy and efficiency of multi-scale incremental cascade updating of residential entities.

Cite this article

JIAO Yangyang , LIU Pingzhi , XIONG Shun , XU Daozhu . Multi-scale Surface Entity Cascade Update Method based on Natural Grid Network Index[J]. Journal of Geo-information Science, 2022 , 24(5) : 851 -863 . DOI: 10.12082/dqxxkx.2022.210350

1 引言

在自然界中,地理要素因受自然力量、人类活动等因素的影响而发生改变。为了保持地理空间数据的现势性,对现有的空间数据库进行更新是必要的。然而对地理空间数据库进行更新是一个繁杂且耗时的过程[1]。一方面是由于地理空间数据种类繁多,体积庞大;另一方面是因为在现阶段数据采集技术比较完善、基础空间数据库建库工作逐渐完成的情况下,现有的级联更新方法难以将局部空间变化在不同尺度空间数据之间准确传递,不同尺度的空间数据更新仍需要重复的数据采集工作,这一瓶颈导致大范围区域空间数据的生产和更新周期均滞后于城市发展速度[2,3]。因此,考虑到实际应用中对小比例尺空间数据库局部更新的广泛需求以及时间和人力成本问题,空间数据级联更新这一制约空间数据更新速度的关键技术成为现阶段研究的重心。
现阶段,学者们对地理空间数据更新进行了广泛的研究。例如,在空间数据库尺度方面,多比例尺空间数据库更新方案基于地理对象构建的关联关系实现多尺度空间数据的联动更新,有效地解决了多比例尺数据信息表达不一致的问题[4,5,6,7];在时空数据库组织形式方面,多级时空数据库联动增量更新模型更新了联动机制,实现了通过体系内任意节点增量变化来驱动不同数据库联动更新[8,9,10];在多尺度地图数据库工作模式方面,定期更新和动态更新相结合的工作模式可以整合多种数据资料,有效地提高了地图数据库的现势性和准确性[11,12]。总结现有的研究可以得出,多尺度空间数据联动更新方法因其保证空间数据在更新中的尺度一致性以及避免数据的重复采集与处理的特性备受学者关注。然而,就制图综合应用领域而言,由于作为关键地理要素的建筑物存在形式中的面实体中包含了复杂的空间拓扑关系[12],现阶段针对面实体空间数据级联更新关键技术的多尺度空间数据联动算法研究不够深入[13],依然制约了制约空间数据的更新速度。
现有的面实体的多尺度空间数据联动算法涉及临近尺度实体的匹配、变化检测、增量更新、更新信息级联传递等工作的研究[1,4,7]。即首先通过匹配算法[9,13-17]计算出在临近尺度级联更新中实体之间的对应关系,接下来基于变化检测算法[26]获取包含发生变化的空间实体信息的增量包,紧接着通过增量更新算法[4,8,18-20]获取对应的小比例空间实体,最后通过更新信息级联传递[3,5-6]工作完成小比例空间数据库的更新工作。经过多年的研究,现阶段制约空间数据级联更新的瓶颈仍然是通过匹配算法获取临近尺度实体间的对应关系。虽然有学者们依据松弛标记[21,22]、多阶段进行匹配[15]等算法来提高匹配精度,采用时态数据库[14]来确定空间数据的更新范围,基于树的形式组织管理待匹配空间实体[23],但临近比例空间实体之间的匹配问题仍没得到真正解决。现阶段匹配算法因缺乏对地理学第一定律的思考而忽略待匹配实体的搜索范围,并且缺乏对待匹配实体的高效组织与管理,这不仅会导致算力资源的浪费,其匹配精度结果也难以进一步提高,在一定程度上制约了级联更新算法的发展。
因此,亟需设计一种顾待匹配实体的搜索范围并且高效组织和管理空间数据的面实体级联更新方法。
综上,本文设计了一种多尺度自然格网索引结构用以描述多尺度地理实体间的关联关系,以消除关联实体个体差异和不同版本数据差异的影响,并基于此索引构建了一套完整的多尺度面实体增量级联更新方法。

2 多尺度面实体自然格网索引结构 构建方法

多尺度面实体增量级联更新操作涉及多个比例尺数据的匹配和尺度变换操作,为了全方位服务于更新进程,要保证系列比例尺关联关系模型在进行相邻尺度之间更新传递时的兼容性和稳定性。更具体而言,首先要解决面实体综合中临近系列比例尺关联关系模型构建问题,其次提供多尺度关联关系模型的一致性约束条件,通过临近比例尺对象之间的关联来引导更新操作在不同比例尺数据之间传递。多尺度空间数据索引、多尺度空间数据显式存储、多尺度空间数据存储结构等是当前系列比例尺关联关系模型采用的主流构建技术[23]。然而现实中不同数据库的数据格式不尽相同,不便于修改和转换。因此,采用多尺度空间索引技术来是构建相邻尺度同名对象间的关联关系是一个行之有效的方法[24]
由于面实体在地图上往往成片出现,面实体所在的区域轮廓受到道路、水系等其他要素的约束,如若利用道路和水系将地图空间划分为一个个自然格网,那么自然格网为居民地匹配和尺度变换等操作提供很大的约束和支持。如果建立起基于自然格网的多尺度的索引结构,将有利于多尺度数据级联关系的建立与维护。本文所指的自然格网索引不但需要在单个比例尺建立索引,同时需要保证不同多尺度之间自然格网索引的对应性和兼容性,从而有效支撑多尺度数据的匹配、尺度变换与更新操作。
现阶段多尺度空间索引的构建需要建立相邻比例尺空间数据之间关联关系的匹配,即首先依次进行相邻比例尺空间数据之间的匹配建立多尺度空间数据关联关系,然后通过要素ID关联建立起不同比例尺要素之间的关联关系。基于相邻比例尺同名要素之间的数量对应关系,共存在1:1、1:0、 0:1、M:1、M:N 5种不同对应类别。因此如何建立相邻比例尺空间数据之间的关联关系并将数据有效组织起来,是多尺度空间索引的构建面临的基础问题。当前相邻比例尺空间面要素之间关联关系匹配面临2个方面的问题:① 传统面要素匹配通常采用面要素之间直接匹配的方法,匹配正确率与匹配效率都不是很高;②面要素之间匹配与级联关系的建立需要单独存储记录关联关系的文件或在要素属性中增加记录关联关系的字段,但由于缺乏唯一要素实体ID,造成级联关系维系困难。
空间面要素如居民地、湖泊要素在空间分布上具有独立或群组分布的特点,且常常受到道路、河流等线状要素所构成的自然格网约束,即相邻比例尺之间的不同层级的空间要素会受到相同自然格网的约束。基于这一特点,本文提出了多尺度面实体的自然格网索引结构,总体思路为:① 本文将面状要素实体化,赋予唯一的实体ID;② 引入全球经纬度格网剖分思想,将线状要素所构建的各层级自然格网分别赋予对应层级全球经纬度格网编码; ③ 利用面实体质心坐标计算其所在的自然格网的编码,在同一格网中进行面实体匹配并在实体数据中记录结果;④ 按照比例尺从小到大的顺序,依据匹配结果构建起树型系列比例尺自然格网索引结构。
基于以上分析,本文提出了面实体自然格网索引结构构建技术路线,以及其在级联更新中的作用,如图1所示。通过构建自然格网并编码,赋予自然格网内构建的面实体以相应编码,通过相邻比例尺自然格网内面实体匹配建立实体关联关系,构建完成面实体的自然格网索引。在级联更新第二步骤变化检测中,如果发生道路、河流等要素变化进而造成自然格网变化时,则需要进行自然格网索引的维护。
图1 面实体自然格网索引结构构建

Fig. 1 Construction of surface entity natural grid index structure

本文所提出的多尺度面实体的自然格网索引结构依据系列比例尺关联关系将空间要素织成为一个树状的结构,树状结构中的每一层对应系列比例尺数据中的一个尺度;在构造的相对固定深度(或层数)的树中,层与层之间的关系即为相邻比例尺同名要素之间的匹配关系,树状结构中每一个节点类别分为单一要素、M:1、M:N匹配关系同名要素组合。图2以面状建筑物实体为例描述了面状实体之间的级联关系,图2(a)指的是相邻地图比例尺下大比例地图与小比例地图中同名建筑物实体之间的级联关系,通过图中的自然格网的约束来确定相邻比例尺之间要素之间的匹配关系;图2(b)则是以图2(a)中相邻比例尺之间建筑物实体的级联关系为例,通过树状关联来展示一对多情况下,父节点与子节点之间的关联关系。
图2 相邻比例尺之间建筑物实体的级联关系

注:图2(a)是指将局部建筑物实体级联更新至临近的小比例尺的过程以及相关建筑物实体在不同尺度下的具体形态,箭头表示联级关系;图2(b)指的是不同层级的建筑物实体在四叉树索引中的位置。例如,建筑物实体8和9在图2(a)中与临近比例尺中的建筑物实体19相对应,它们在四叉树索引中的位置则如图2(b)所示。

Fig. 2 Cascade relationship of building entities between adjacent scales

以居民地要素为例,在单一比例尺上构建自然格网索引时,从城市整体结构、主要道路完整性、道路网眼密度均衡和格网内建筑物的自适应聚类4个层次[25]着眼。宏观上考虑城市(综合区域)整体结构、自然水系、铁路以及高等级道路的分布构建索引的主要架构,完成图幅内主干格网划分。中观层次保证主要道路的连通性,采用Stroke技术[26],按照属性一致性、方向一致性、趋势一致性的优先级提取完整道路,形成中层格网。微观层次采用道路网眼技术处理中间格网道路水系的开放边缘形成密度均衡、符合区域特征的基本格网。对于大比例尺数据,在最小格网内还有大量的居民地要素,根据形状、方向、大小和邻近性等指标对居民地对象进行自适应聚类,提取居民地群。最终实现单一尺度自然格网索引的构建。如图3所示。该结构可以提高单一比例尺空间数据检索速度以及多比例尺空间数据级联更新效率,保障多级空间数据的逻辑一致性。
图3 基于自然格网的居民地索引结构

Fig. 3 Residential index structure based on natural grid

自然格网索引在应对不同空间尺度时,不同比例尺数据建立的自然格网索引是不同的。居民地实体对象的聚类群及其组成的基本格网,仅适用于较大比例尺数据,在实际应用过程中,随着比例尺的缩小和要素的合并,大量的聚类群和基本格网消失,索引的级数也会逐渐减少。对于多尺度面实体增量级联更新而言,纵向同名面实体关联关系空间一致性的保持要靠横向综合索引的辅助和约束,所以就要求不同比例尺的横向索引也具有一致性。为了实现自然格网对居民地实体尺度的约束作用,在小比例尺地图上构成基本格网的弧段如果在大比例尺数据中没有对应存在,就不能构建出相邻比例尺数据的对应基本格网,也就无法实现不同比例尺索引的横向对应,因此必须保证从小比例尺到大比例尺基本格网的层层包含关系,即大比例尺数据的基本格网是相邻小比例尺基本格网的子集,如 图4所示,图4(a)表示大比例尺地图索引结构,图4(b)表示小比例尺地图索引结构。L、M、S表示不同级别索引,其中M1、M2应由相同实体构成。
图4 不同层级比例尺居民地实体索引结构示例

Fig. 4 Example of residential entity index structure at different scale levels

3 基于自然格网索引的居民地增量级联更新方法

本文设计的基于自然格网索引的面实体级联更新的整体框架如图5所示。首先对大比例历史数据和现势数据进行变化检测,提取大比例的增量更新实体。然后将发生变化的实体数据缩编成小比例尺数据,并根据自然格网索引对相邻的小比例尺空间数据进行更新。最后,当格网内变化实体数量少且变化程度低时,则按照索引结构对各级比例尺的变化实体单独进行手动更新。本文以居民地要素为例论述基于自然格网索引的增量级联更新方法。
图5 级联更新框架

Fig. 5 Cascading update frameworks

3.1 基于自然格网构建多尺度居民地实体索引

通过空间索引可以排除掉一些明显不符合条件的图元,得到侯选集合,然后对侯选图元集合进行精确几何运算,得到最终结果。空间索引可以减少不必要的运算,显著提升算法效率和精度。因此,构建自然格网编码索引结构是必要的。解决多尺度居民地实体的增量级联更新,需要构建多尺度的居民地实体,并利用自然格网索引将居民地实体组织起来。
(1)自然格网构建并编码
依据本文第2节中所述多尺度自然格网索引构建思路,构建每个比例尺的4层自然格网,包括:水系和不同层级道路的拓扑关系,对应比例尺的基本格网,多尺度自然格网的索引结构和聚类群。
计算每层级自然格网能够被完全包含的全球规则格网层级,并将每一个自然格网所在的对应层级的全球规则格网编码赋予该自然格网。自然格网编码格式为GXXXXX…X,其中"X"为阿拉伯数字,位数根据对应层级全球规则格网编码决定。
(2)居民地实体构建并编码
计算各比例尺居民地实体质心在本比例尺基本格网,并将该基本格网编码赋予该居民实体,编码格式为GXXXXX…X-YYYYYY-ZZZZ,其中GXXXXX…X为所在基本格网编码,YYYYYY为居民地实体的6位地理信息要素分类编码,用于表示居民地实体对象所属的地理信息要素类型,ZZZZ为实体随机码。
(3)相邻比例尺居民地实体关联索引建立
以自然格网中基本格网为依据,建立系列比例尺间基本格网的树状关联关系;在关联自然格网内,利用多尺度居民地匹配方法[27]对的居民地实体进行匹配,构建起相邻比例尺居民地实体关联索引。
(4)自然格网索引的维护
当居民地的变化范围较大,同比例尺数据中道路等自然格网的构成要素也发展了变化时,该比例尺构成原有自然格网的基本格网发生改变,与相邻比例尺数据自然格网的对应关系也被破坏。此时,最初建立的自然网格索引将不再适用,需要重新构建该比例尺的自然格网,并建立与相邻比例尺自然格网的树状关联关系,实现自然格网索引的重构与维护。

3.2 基于居民地实体的级联更新

3.2.1 变化检测
变化检测是级联更新的前提,本文采用矢量空间数据变化检测方法[28],对同源同尺度矢量空间数据进行自动检测。首先,对2个时相的数据进行同一性叠置分析,再进行面状要素几何约束将变化类型分类为新生、删除和伸缩3类,最后通过缓冲分析和空间关系分析进行伪变化信息的剔除,从而得到最终的增量更新包。其中,新生是指新图中存在,与旧图叠置分析后没有发现包含或相交的对象;删除与新生相反,旧图中存在,而新图中没有发现相交或包含的对象;伸缩变化指面实体形状的改变。伪变化信息指面实体少量或单一节点,发生小于容差值的位置变化引起的系统对变化类型的误判。
几何约束由判断变化类型的规则构成。比较面要素的地理国情分类代码可以判断面要素地类是否发生变化,如未利用地转变为城镇住宅用地等。判断所有变化类型都需要依靠历史数据的国情分类代码 CC和现势数据的国情分类代码 CC '。新生变化主要依靠叠置分析处理后的面实体面积值 pIArea . Area和现势数据的实体面积值 Shape _ Area与容差值 ARC约束,计算方法如式(1)所示。删除变化主要依靠反向叠置分析处理后的实体面积值 pIArea . Area '和历史数据的实体面积值 Shape _ Ar _ 1与容差值 ARC约束,计算方法如式(2)所示。伸缩变化约束条件与新生变化和删除变化约束条件相反,计算方法如式(3)、式(4)所示。容差值可以根据现行规范或标准设定。
CC < > CC ' pIArea . Area _ > ARC Math . Abs pIArea . Area - Shape _ Area < ARC
CC < > CC ' pIArea . Area ' > ARC Math . Abs ( pIArea . Area - Shape _ Ar _ 1 ) < ARC
CC < > CC ' pIArea . Area > ARC Math . Abs pIArea . Area - Shape _ Area > ARC
CC = CC ' pIArea . Area > ARC Math . Abs Shape _ Area - Shape _ Ar _ 1 > ARC
式中: CC为历史数据的国情分类代码; CC '现势数据的国情分类代码; pIArea . Area为叠置分析处理后的面实体面积值; Shape _ Area为现势数据的实体面积值; ARC为容差值; pIArea . Area '为反向叠置分析处理后的实体面积值; Shape _ Ar _ 1为历史数据的实体面积值。
剔除伪变化信息,只需对历史数据和现势数据的面实体以容差值为参数生成缓冲区,进而对缓冲区和两者进行空间分析,若缓冲区包含两者则判定为伪变化。
3.2.2 制图综合及接边
缩编是解决多尺度数据获取的有效方式,本文采用Delaunay三角网分类过滤法[19]对大比例尺地图上检测到的变化信息进行多尺度的制图综合,得到不同比例尺的增量更新包。该方法对大比例尺面实体进行加密构建C-Delaunay三角网,即要求指定的边必须作为三角行边存在。依据位置特征、属性特征(顶点邻接三角形个数)、关联特征(邻接三角形个数)、高度特征、角度特征及边长特征6个度量参数对三角形进行过滤,保留位于面实体外侧,连接多个距离较近的面实体或关联多个三角形的锐角三角形。循环判断保留三角行是否有邻接三角形,将有邻接三角形的标记为桥联三角形;根据桥接三角形的属性特征得到其非公共边,从非公共边的顶点向公共边做垂足,进行直角化;融合公共边的桥联三角形得到制图综合后的面实体。
增量信息的传递在中间格网可能会产生同一地理实体被分割等拓扑问题。为保护空间数据逻辑一致性,需要对更新范围边界的实体进行自适应接边处理[20]。自适应接边方法,首先使用缓冲分析确定候选接边对象,按式(5)依次计算候选对象接边匹配度。选取匹配度最高对象按照低精度数据向高精度数据修改的原则接边,最后进行属性融合。
M ( A , B ) = d ( A , B ) ω 1 + s ( A , B ) ω 2 + r ( A , B ) ω 3
式中: M为对象接边匹配度; d代表距离匹配度; s代表语义(属性)匹配度; r代表空间关系匹配度; ω表示权重。
d A , B = 1 - min ( | Apts - Bpts | ) d tolerance ,
式中: A , B表示不同的面实体; Apts Bpts表示构成2个面实体的节点集; min ( | Apts - Bpts | )表示节点集中最近两点的欧式距离; d tolerance表示距离阈值。
$s(A, B)=\frac{\sum_{K=1}^{N}\left[\operatorname{Sim} A K(A, B) E S W_{A K}\right]}{N}$
式中: Sim表示属性相似度; ESW表示权重,即为属性相似度的加权平均值。
r A , B = interset ( buffer ( A ) , buffer ( B ) ) max ( buffer ( A ) , buffer ( B ) )
式中: r空间关系匹配度指实体 A B缓冲区交集 interset ( buffer ( A ) , buffer ( B ) ) A B缓冲区最大值 max ( buffer ( A ) , buffer ( B ) )的比值。
3.2.3 多尺度面实体级联更新
多尺度面实体级联更新是指将将大比例尺空间中发生变化的实体数据要素及要素集传递到小比例地图。现有的级联更新方式主要是依据匹配结果进行相邻比例尺之间的更新,主要分为2种:① 以单个元素作为载体,通过遍历未匹配的大尺度要素集中的所有要素,依次找出每一个要素对应的小比例尺空间要素。然后,将这些大比例尺要素传递给对应的小比例尺要素; ② 首先将更新的大比例尺要素对象与其对应的待更新的小比例尺要素对象进行组合,然后构造约束的Delaunay三角网模型,将更新信息问题转换成了对三角形的选取、丢弃问题。前者会有大量不必要运算,计算效率低;后者计算效率显著提升,但算法复杂,参数设定是一个问题。本文则是通过构建的自然格网索引直接获取发生变化的实体数据要素及要素集在大比例地图和小比例地图中的索引,实现进行多尺度面实体级联更新。本文所采用的级联更新方法避免了计算量巨大的遍历匹配和一系列复杂的参数设定,在性能和精度上均能得到保障。

4 实验与分析

4.1 基于自然格网索引的居民地实体级联更新

4.1.1 居民地实体级联更新数据
实验区选取赣州市虎山乡部分区域级联更新实验模拟用旧版本1:10 000和1:50 000矢量数据和新版本1:10 000矢量数据中的居民地要素(图6), 1:10 000居民地要素数据为图中深灰色街区和黑色房屋数据,共5719条数据,1:50 000居民地要素数据为图中浅灰色街区数据,共507条数据。
图6 旧版本1:10 000和1:50 000矢量居民地数据

Fig. 6 Old version 1:10 000 and 1:50 000 vector residential data

4.1.2 居民地实体动态级联更新
居民地级联更新过程涉及很多环节,本节将依次展开介绍。首先,依据本文3.1中提出的自然格网构建方法,利用道路和水系数据构建实验区域的自然格网,1:10 000部分区域矢量数据的自然格网如图7(a)所示。图7(a)中将部分断头路与最近的主要公路进行连接,组成基本格网。其次,依据全球规则格网计算基本格网的层级,经分析将1:10 000基本格网定义在15级,1:50 000基本格网定义在14级,赋予基本格网编码。同时,采用本文实体编码规则,对居民地实体进行编码。1:10 000部分区域居民地实体编码如图7(b)所示。图7(b)中橙色区域内的10个居民地实体编码如表1所示。以实体1为例,G001132013000232为实体所在基本格网编码,130204为实体要素分类编码,1550为实体随机码,依据该编码规则可以清晰表明所在基本格网和要素类型,唯一实体随机码可以实现单个实体的唯一编码。接下来,需要对两个临近比例关联格网中的居民地实体进行匹配(图7(c)),图7(c)中居民地实体编码为G00113201300023-130204-215,G00113201 300023为实体所在基本格网编码,130204为实体要素分类编码,215为实体随机码。紧接着需要实施新旧版本数据间的变化检测操作,局部细节如如图7(d)和图7(e)所示,伸缩标记为红色,删除标记为橙色,新增标记为绿色。最后,利用发现的变化信息,更新旧版本1:10 000版本的居民地实体数据后,获得了1:10000实体变化增量包,并通过本文提出的级联更新方法关联至相关1:50 000居民地实体,在进行增量包制图综合后,获得了新版1:50 000居民地实体数据(图8),实现了从1:10 000至1:50 000的级联更新。
图7 居民地实体动态级联更新过程示例

Fig. 7 Example of dynamic cascade updating process of residential entity

表1 1:10 000居民地实体编码

Tab. 1 Code of 1:10 000 vector residential entity

序号 实体编码
1 G001132013000232-130204-1550
2 G001132013000232-130102-1551
3 G001132013000232-130206-1572
4 G001132013000232-130102-1598
5 G001132013000232-130204-1652
6 G001132013000232-130204-1653
7 G001132013000232-130102-1704
8 G001132013000232-130102-1705
9 G001132013000232-130102-1707
10 G001132013000232-130204-1874
图8 1:50 000居民地实体数据更新结果

Fig. 8 1:50 000 residential entity data update result

4.2 方法有效性分析与讨论

本文所提出方法的关键在于利用自然格网索引构建相邻比例间实体数据之间的关联关系,其中相邻比例居民地实体数据之间的相似度计算采用了文献[25]中的算法。为了验证本文方法的有效性,下面从匹配阈值的选择、自然格网索引的作用、与传统匹配方法的对比分析3个方面进行分析和讨论。
4.2.1 匹配阈值的选择
在本文方法中,居民地实体之间建立匹配关系的核心环节在于相似性的度量,即当匹配算法中综合相似性大于一定的阈值时建立相邻比例实体之间的关联关系。因此,阈值的选择直接关系到匹配结果的质量,可通过匹配查全率和查准率方面来评估匹配质量。本文所提出方法中匹配计算结果为相似性归一化值,取值范围为[0,1],值越大代表其相似性越高,匹配的概率也越大。图9为不同阈值对于匹配结果(查全率和查准率)的影响。
图9 不同阈值对匹配结果的影响

Fig. 9 Influence of different thresholds on matching results

分析图9可知,对于本文方法和本次实验数据而言,阈值对于匹配结果的影响如下:
(1)阈值过小(0.3~0.5),本不存在匹配关系的实体之间被认定为匹配,即存在误匹配情况。此时查全率在高位(66%)缓慢下降,查准率以较高的增长率从低位(85%)逐渐上升。
(2)随着阈值的增加(0.3~0.5),错误匹配逐渐减少,查准率不断上升(85% 94%),查全率有所下降(67% 66%),并在阈值为0.5附近内达到一种相对的平衡,当匹配阈值在该区间取值时,错误匹配和漏匹配均较少,匹配正确率(94%)较高。
(3)随着阈值的进一步增加(0.5~0.8),过于严苛的阈值不仅排除了错误匹配,还将具备匹配关系的实体判断为不匹配,漏匹配的数量急剧增加,造成查全率快速下降(66% 54%),而此时查准率(94%)的增加并不明显。
通过进一步细化分析(0.45,0.53)区间内的结果,当阈值为0.51时,查准率(94.1%)已经达到较高水平,查全率(66.5%)还未急剧下降,此时匹配效果最佳。
4.2.2 自然格网索引的作用
为了验证本文基于自然格网索引方法的有效性,选取在不使用自然格网情况下直接进行居民地匹配[25]构建相邻比例实体数据之间的关联关系,具体方法为利用该方法对旧版本1:10 000和1:50 000居民地实体数据进行匹配,进而获得关联实体之间的相似性值,与本文方法进行比较。
因本章节只分析自然格网的作用,不涉及具体匹配相似性度量方法的比较,匹配的阈值统一采用0.51,表2为本文方法与对比方法中相邻比例居民地数据匹配实验中用时和精度对比。其中,查全率为匹配的数量占全部数量的比例,查准率为正确匹配的数量占该方法匹配总数的比例。
表2 是否采用自然格网索引的匹配结果比较

Tab. 2 Comparison of matching results whether to use natural grid index

匹配方法 耗时/s 匹配数/个 正确数/个 查全率/% 查准率/%
直接匹配 11.55 346 312 61.5 90.1
基于自然格网索引匹配 1.34
(构建格网索引耗时0.53)
358 337 66.5 94.1
通过上述实验可以发现相较不使用自然格网而言,本文提出的自然格网索引具有两方面优势:
(1)虽然本文方法在匹配计算之前建立自然格网索引需要消耗少量时间(构建格网索引耗时0.53s),但是在匹配计算时仅需要对关联基本格网内的居民地实体进行综合相似性度量,匹配效率突出,比对比实验减少88.4%的时间消耗,最终的计算耗时与数据范围成线性正相关关系。如果不采用自然格网索引,匹配计算的遍历范围将急剧增加,匹配计算的耗时与数据范围将成指数正相关关系,因此可以预测在大区域、大数据量级联更新中自然格网索引的效率优势将更加明显。
(2)基于自然格网索引约束的居民地实体匹配方法顾及了与道路河流等要素的关系,在保持较高匹配精度(查全率达到66.5%)的同时也降低了错误匹配发生的概率(查准率达到94.1%)。相较于对比实验,自然格网索引的加入使得查全率和查准率分别提升了5%和4%。
此外,由于传统方法缺乏道路河流等要素对面实体约束信息的考虑,在对相邻比例数据之间空间实体进行匹配时会把空间位置相关度极低的空间实体匹配到一起(图10)。图中所示1:10 000误匹配居民地本应在道路南侧,由于数据位置有所差异,造成与道路北侧1:50 000居民地匹配,从建立了错误的关联关系。相反,由于自然格网索边界会对待匹配实体的范围进行约束,采用自然格网索引进行匹配时可以很好地避免这个问题的出现。
图10 不采用自然格网索引直接匹配的错误

Fig. 10 Error of direct matching method without natural grid network index

4.2.3 与传统匹配方法的对比分析
为了进一步验证本文方法在相邻比例尺居民地匹配中的有效性,本文选取3种传统匹配方法进行比较分析:Hausdorff距离、欧式距离和质心包含3种匹配方法。
基于距离的匹配方法在处理跨比例尺面实体匹配时,会出现阈值选择困难情况。如图11所示,1:50 000居民地实体202(蓝色数字指示)与1:10 000居民地实体354(红色数字指示)的欧式距离高达192.7299,而1:50 000居民地实体215(蓝色数字指示)与1:10 000居民地实体356(红色数字指示)的欧式距离为131.3286,显然202与354应建立匹配关系,215与356并不能匹配。
图11 欧氏距离直接匹配的错误

注:红色字体表示1:10 000居民地实体编码后四位;蓝色字体表示1:50 000居民地实体编码后四位。

Fig. 11 Error of Euclidean distance direct matching method

通过实验发现,Hausdorff距离匹配阈值设置为11.9时,欧式距离匹配阈值设置为128.3时,对应的匹配准确率最高。由于1:10 000和1:50 000居民地数据尺度差异较大,使用质心包含方法进行匹配时需要使用单向匹配方法,即当1:10 000居民地多边形质心被1:50 000居民地多边形包围时确定为匹配,此时质心包围方法的匹配正确率最高。在确定好最优参数情况下,上述3种传统匹配方法的匹配结果如表3所示。
表3 3种传统匹配方法结果对比

Tab. 3 Result statistics of three traditional matching methods

匹配方法 耗时/s 匹配数/个 正确数/个 查全率/% 查准率/%
Hausdorff距离 7.59 305 277 52.7 87.5
欧式距离 8.18 318 242 47.7 76.1
质心包含 4.12 325 293 57.8 90.2
实验表明,在保障匹配准确度(查准率)的前提下,Hausdoff距离和欧式距离匹配方法需通过较小的匹配阈值来避免出现大量的匹配错误,但此策略会牺牲匹配查全率。因此上述两种方法对于跨比例尺面状要素一对多匹配效果较差。单向的质心包含方法较为适用于一对多的匹配情况,但是缺乏多种指标的相似性度量也使得该方法相较于一对多方法的匹配成功率略低,加之没有自然格网索引的约束,与本文方法的差距更大。通过以上3个方面的对比分析,本文方法在居民地匹配环节具有较好的效果,其原因在于旧版本数据库中的1:10 000和1:50 000居民地的现势性存在很多不一致的情况,同一地块居民地形状、方向等方面存在差异,且未考虑道路、河流等自然格网的约束,造成传统匹配方法的失效。同时,由于Hausdoff距离和欧式距离匹配方法在匹配时仅需进行不同面状居民地之间的距离计算,质心包含方法仅需要进行单项的点面包含计算,即使在不使用自然格网索引的情况下依然具有较高的效率;但是根据对匹配结果特别是匹配错误案例的分析,3种传统方法均存在一定的固有缺陷,无法胜任相邻比例尺居民地实体匹配中非1:1的情况,在实际更新过程中难以作为匹配依据。而本文基于自然格网索引构建起的相邻比例尺关联关系,不受因现势性、生产方等因素造成的关联居民地形状等差异影响,具有更高的匹配准确度和算法适应性,从而大大减少了人工编辑作业时间,为后续级联更新提供了良好基础。

5 讨论

本文提出了一种基于自然格网索引的多尺度面实体增量级联更新方法,重点研究了自然格网索引约束对临近比例的面实体级联更新结果的影响。已有的级联更新算法可以在一定程度上保持较好的级联更新结果,但这些方法缺乏对级联更新匹配环节中待匹配的空间实体之间对应关系的考虑,生硬地采用通过提高匹配算法精度的思想提高级联更新结果,不仅有着相当的时间开销,并且已经达到了瓶颈,难以取得更好的成效。本文基于自然格网索引方法确定了待匹配实体之间的范围并且对其进行高效组织与管理,进而提高了匹配效率以及精度,所提出的级联更新方法有着更好的适用性。
顾及自然格网索引的级联更新的查全率和查准率分别可以达到66.5%和94.1%。在本实验中,无论是本文所提出的方法还是对比方法,查全率似乎并没有特别高(本文所提出方法查全率可达66.5%,对比方法的查全率最高为61.5%),这个现象是由于本文所采用的查全率的计算方式所导致。在本文中,查全率是指匹配的数量占全部数量的比例,查准率为正确匹配的数量占该方法匹配总数的比例。通过定义可以发现全部数量是由两个临近比例的全部实体组成,故而查全率数值偏低,后续研究可以针对这个问题优化查全率计算方案,使读者更容易理解。此外,本文的查准率虽然比较高(94.1%),但仍然有上升的空间。通过研究实验结果发现有以下两个原因制约了本方法查准率:① 虽然本方法引进自然格网索引优化待匹配实体之间的搜索范围,但在划分的自然格网内仍有空间关联性极高但不匹配的空间实体对,导致匹配错误发生;② 部分待匹配实体间虽然存在级联关系,但并非临近,本文所提提出方法把它们归为一类,这在一定程度上也降低了本文所提方法的查准率。针对以上问题,未来可以通过进一步优化空间索引结构来解决问题。

6 结论

本文针对现有方法中多尺度同名实体间的关联关系匹配的精度和效率问题提出了基于自然格网索引的多尺度面实体增量级联更新方法。利用道路水系等线状要素构建自然格网,通过自然格网对面要素进行实体化处理和编码,建立相邻比例尺实体数据之间的关联关系,建立多尺度自然格网索引,进而实现基于自然格网索引的面实体级联更新。主要结论如下:① 相较于直接匹配的方法,采用本文提出的自然格网索引方法进行匹配在匹配阈值为0.51的情况下所消耗的时间减少了88.4%,查全率和查准率分别提升了5%和4%,这一结果表明了自然格网索引方法在匹配相邻尺度间地理要素时的必要性; ② 相较于传统的Hausdorff距离、欧式距离和质心包含3种匹配方法,本文所提出的方法在耗时(1.34s)、查全率(66.5%)和查准率(94.1%)方面处于领先地位,这充分表明了本文提出的级联更新方法的在对空间信息数据进行更新时的优越性;③ 本文提出的方法不受因现势性、生产方式等因素造成的关联居民地形状差异等影响,可大大减少人工编辑作业时间,相较于传统方法能够有效提高空间面要素的匹配效率和匹配精度,其索引结构也为级联更新打下了良好基础。
[1]
Mader G L. GPS antenna calibration at the national geodetic survey[J]. GPS Solutions, 1999, 3(1):50-58. DOI: 10.1007/PL00012780

DOI

[2]
陈军, 王东华, 商瑶玲, 等. 国家1:50 000数据库更新工程总体设计研究与技术创新[J]. 测绘学报, 2010, 39(1):7-10.

[ Chen J, Wang D H, Shang Y L, et al. Master design and technical development for national 1:50 000 topographic database updating engineering in China[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(1):7-10. ]

[3]
蒋捷, 陈军. 基础地理信息数据库更新的若干思考[J]. 测绘通报, 2000(5):1-3.

[ Jiang J, Chen J. Some consideration for update of fundamental geo-information database[J]. Bulletin of Surveying and Mapping, 2000(5):1-3. ] DOI: 10.3969/j.issn.0494-0911.2000.05.001

DOI

[4]
许俊奎. 多尺度居民地要素增量级联更新方法研究[D]. 郑州:信息工程大学, 2013.

[ Xu J K. Research on multi-scale settlement incremental propagating updating techniques[D]. Zhengzhou: Information Engineering University, 2013. ]

[5]
刘建军, 李雪梅, 张元杰, 等. 国家1:25万基础地理信息数据库联动更新技术设计与工程应用[J]. 测绘通报, 2016(4):1-4.

[ Liu J J, Li X M, Zhang Y J, et al. Technical innovation and application for linkage updating of national fundamental geographic information database at 1:250 000 scale[J]. Bulletin of Surveying and Mapping, 2016(4):1-4. ] DOI: 10.13474/j.cnki.11-2246.2016.0109

DOI

[6]
张鹏, 韦通, 李庆永, 等. 省市级基础地理信息框架数据联动更新探究[J]. 山东国土资源, 2016, 32(11):65-69.

[ Zhang P, Wei T, Li Q Y, et al. Research on the data linkage updating of provincial and municipal basic geographic information framework[J]. Shandong Land and Resources, 2016, 32(11):65-69. ] DOI: 10.3969/j.issn.1672-6979.2016.11.013

DOI

[7]
张新长, 张志强, 孙颖, 等. 模式识别的空间数据联动更新技术研究[J]. 测绘科学, 2019, 44(1):66-72.

[ Zhang X C, Zhang Z Q, Sun Y, et al. Research on multi-scale spatial data linkage updating technology based on pattern recognition[J]. Science of Surveying and Mapping, 2019, 44(1):66-72. ] DOI: 10.16251/j.cnki.1009-2307.2019.01.013

DOI

[8]
魏雪梅. 多级时空数据库联动增量更新方法[J]. 测绘通报, 2019(5):134-138.

[ Wei X M. Linkage incremental update method of multilevel spatiotemporal database[J]. Bulletin of Surveying and Mapping, 2019(5):134-138. ] DOI: 10.13474/j.cnki.11-2246.2019.0166

DOI

[9]
Zhang et al. Data matching of building polygons at multiple map scales improved by contextual information and relaxation[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 9(2):147-163. DOI: 10.1016/j.isprsjprs.2014.03.010

DOI

[10]
罗鹏, 张俊, 王明亮, 等. 基础地理信息联动更新技术研究与应用[J]. 测绘与空间地理信息, 2017, 40(6):83-85.

[ Luo P, Zhang J, Wang M L, et al. The research and application of basic geographic information linkage updating technology[J]. Geomatics & Spatial Information Technology, 2017, 40(6):83-85. ] DOI: 10.3969/j.issn.1672-5867.2017.06.027

DOI

[11]
付荣祥, 吴彬卓, 叶哲璐. 地理空间数据库联动更新技术[J]. 测绘通报, 2017(5):136-138.

[ Fu R X, Wu B Z, Ye Z L. Geospatial database linkage updating technique[J]. Bulletin of Surveying and Mapping, 2017(5):136-138. ] DOI: 10.13474/j.cnki.11-2246.2017.0173

DOI

[12]
方川, 白光平. 多尺度地图数据库更新机制研究及应用[J]. 测绘与空间地理信息, 2021, 44(2):86-89.

[ Fang C, Bai G P. Research and application of multi-scale map database update mechanism[J]. Geomatics & Spatial Information Technology, 2021, 44(2):86-89. ]

[13]
汪艳霞, 杜清运, 任福, 等. 目标相似性的矢量数据联动更新方法[J]. 测绘科学, 2015, 40(5):106-111.

[ Wang Y X, Du Q Y, Reng F, et al. Propagating update method of vector data based on objective similarity[J]. Science of Surveying and Mapping, 2015, 40(5):106-111. ] DOI: 10.16251/j.cnki.1009-2307.2015.05.023

DOI

[14]
王建丽. 面向电子地图服务的地理框架数据联动更新技术研究与实现[D]. 郑州:信息工程大学, 2015.

[ Wang J L. Research and implementation of geographic frame data linkage update technology for electronic map service[D]. Zhengzhou: Information Engineering University, 2015. ]

[15]
Hacar M, Gökgöz T. A new, score-based multi-stage matching approach for road network conflation in different road patterns[J]. ISPRS International Journal of Geo-Information, 2019, 8(2):81-81. DOI: 10.3390/ijgi8020081

DOI

[16]
赵慧慧, 赵凡, 陈仁海, 等. 基于地理空间大数据的高效索引与检索算法[J]. 计算机研究与发展, 2020, 57(2):333-345.

[ Zhao H H, Zhao F, Chen R H, et al. Efficient index and query algorithm based on geospatial big data[J]. Journal of Computer Research and Development, 2020, 57(2):333-345. ] DOI: 10.7544/issn1000-1239.2020.20190565

DOI

[17]
秦育罗, 郭冰, 孙小荣. 改进Hausdorff距离及其在多尺度道路网匹配中的应用[J]. 测绘科学技术学报, 2020, 37(3):313-318.

[ Qin Y L, Guo B, Sun X R. Improved Hausdorff distance and its application in multi-scale road network matching[J]. Journal of Geomatics Science and Technology, 2020, 37(3):313-318. ] DOI: 10.3969/j.issn.1673-6338.2020.03.016

DOI

[18]
王峰, 安晓亚, 朱璇. 地理空间数据增量更新版本化管理方法研究[J]. 地理空间信息, 2021, 19(2):26-29.

[ Wang F, An X Y, Zhu X. Research on versioning management method for geo-spatial data’s incremental updating[J]. Geospatial Information, 2021, 19(2):26-29. ] DOI: 10.3969/j.issn.1672-4623.2021.02.007

DOI

[19]
郭沛沛, 李成名, 殷勇. 建筑物合并的Delaunay三角网分类过滤法[J]. 测绘学报, 2016, 45(8):1001-1007.

[ Guo P P, Li C M, Yin Y. Classification and filtering of constrained delaunay triangulation for automated building aggregation[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(8):1001-1007. ] DOI: 10.11947/j.AGCS.2016.20150587

DOI

[20]
张新长, 郭泰圣, 唐铁. 一种自适应的矢量数据增量更新方法研究[J]. 测绘学报, 2012, 41(4):613-619.

[ Zhang X C, Guo T S, Tang Y. An adaptive method for incremental updating of vector data[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(4):613-619. ]

[21]
Zhang Y F, Huang J C, Deng M, et al. Automated matching of multi-scale building data based on relaxation labelling and pattern combinations[J]. ISPRS International Journal of Geo-Information, 2019, 8(1):38-38. DOI: 10.3390/ijgi8010038

DOI

[22]
Karsznia I, Przychodzeń M, Sielicka K. Methodology of the automatic generalization of buildings, road networks, forests and surface waters: a case study based on the topographic objects database in Poland[J]. Geocarto International, 2020, 35(7):735-758. DOI: 10.1080/10106049.2018.1533591

DOI

[23]
程昌秀. 矢量数据多尺度空间索引方法的研究[J]. 武汉大学学报信息科学版, 2009, 34(5):597-601.

[ Cheng C X. A multi-scale spatial index method[J]. Geomatics and Information Science of Wuhan University, 2009, 34(5):597-601. ]

[24]
许俊奎, 武芳, 钱海忠. 多比例尺地图中居民地要素之间的关联关系及其在空间数据更新中的应用[J]. 测绘学报, 2013, 42(6):898-905,912.

[ Xu J K, Wu F, Qian H Z. The establishment and usage of the neighborhood scale settlement features' links in spatial data updating process[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(6):898-905,912. ]

[25]
赵彬彬, 邓敏, 李光强, 等. 基于城市形态学原理的面状地物层次索引方法[J]. 测绘学报, 2010, 39(4):435-440.

[ Zhao B B, Deng M, Li G Q, et al. A new hierarchical spatial index for area entities based on urban morphology[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4):435-440. ]

[26]
杨敏, 艾廷华, 周启. 顾及道路目标stroke特征保持的路网自动综合方法[J]. 测绘学报, 2013, 42(4):581-587,594.

[ Yang M, Ai T H, Zhou Q. A method of road network generalization considering stroke properties of road object[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(4):581-587,594. ]

[27]
许俊奎, 武芳, 钱海忠, 等. 一种空间关系相似性约束的居民地匹配算法[J]. 武汉大学学报·信息科学版, 2013, 38(4):484-488.

[ Xu J K, Wu F, Qian H Z, et al. Settlement matching algorithm using spatial similarity relations as constraints[J]. Geomatics and Information Science of Wuhan University, 2013, 38(4):484-488. ]

[28]
石善球. 矢量空间数据变化检测及其应用研究[J]. 测绘与空间地理信息, 2020, 43(9):25-29.

[ Shi S Q. Research on change detection of vector spatial data and its applications[J]. Geomatics & Spatial Information Technology, 2020, 43(9):25-29. ]

Outlines

/