一种自适应的矢量数据增量更新方法研究

张新长，郭泰圣，唐 铁

中山大学地理科学与规划学院，广东广州510275

一种自适应的矢量数据增量更新方法研究

张新长，郭泰圣，唐 铁

中山大学地理科学与规划学院，广东广州510275

针对GIS增量更新中存在的一致性维护与空间冲突问题，提出一种自适应的矢量数据增量更新方法。以同名对象匹配为切入点，探讨变化对象的检测与增量更新的方式。在综合考虑空间距离，语义相似度及拓扑一致性约束的基础上，提出接边匹配度的计算方法并设计自适应的对象接边算法。同时，介绍矢量数据增量更新中基于约束规则的空间冲突检测与处理方法。并以矢量地形图试验数据验证文中所提出的模型与算法。

自适应；增量更新；数据一致性；空间冲突

1 引 言

矢量空间数据更新是维护空间数据库现势性的主要手段［1］，已成为GIS的前沿研究课题。其研究重点主要为变化信息检测，更新事件建模和空间冲突检测。在变化信息检测方面，国内外学者从空间叠加［2］、拓扑关联等角度［3－4］，结合更新事件特征［5］提出检测方法。文献［3—4］以拓扑联动的方式进行实体变化类型的推断，为增量更新中拓扑一致性的维护提供了新思路。然而，拓扑判断的准确性容易受到数据不确定性的影响，且联动规则与专题信息联系密切，通用性有待进一步提高。在更新事件时空建模方面，研究内容已从基于版本管理的更新模式［6－7］发展到顾及更新传播与一致性维护的空间数据模型［8］及基于拓扑一致性维护的时空过程建模［9－10］。文献［8］在概念层面为GIS更新模型设计提出了解决思路，其具体的表达形式及实际的应用仍需要更深入的研究。文献［10］所提出的数据模型兼顾了拓扑关系维护与时空信息管理，有助于更新信息与历史数据的管理。但是，该模型对于拓扑关系的维护只局限于相邻对象，需要深化对复杂空间关系处理的研究。空间冲突检测与数据完整性维护是空间数据更新的另一个重要问题［11］。学者提出了空间实体完整性约束表达形式［12］及空间冲突的确认方法［13－14］。文献［12］所提出的约束模型有利于保证更新后数据的质量。然而，该模型缺少对属性及规则重要性的明确说明。在对象触犯多条约束规则时，处理的优先度需要更深入的考虑。

目前的研究侧重从变化检测及时空过程建模的角度，探讨更新方法、流程及变化信息的存储方式，对数据一致性维护及空间冲突处理的论述不够充分。因此，本文从增量更新与数据完整性维护的角度出发，提出一种自适应的矢量数据增量更新方法，实现矢量数据变化检测与增量更新、自适应的数据接边及空间冲突的检测与处理等功能，以保证更新后数据的完整性与一致性。

2 自适应的矢量数据增量更新方法

2.1 总体设计

本文所指的“更新数据”是地形图修补测量、竣工测量或市政测量产生的矢量空间数据，可作为增量信息进行更新。本文主要针对同级比例尺的更新研究，更新数据预处理操作是指在更新前依据入库标准，对更新数据进行坐标系、数据结构及拓扑关系的检查与修正处理，以产生标准数据。增量更新方法是利用对象的空间相似性、几何距离与拓扑特征进行变化目标检测［15－16］，然后进行添加、删除、几何或属性修改等更新处理。在更新过程中有可能产生同一地理实体的分割或空间错位。因此，需要进行对象的接边处理。更新数据采集或建模的差异有可能产生不合理的空间关系，有必要进行空间冲突的检测与处理。更新过程还包括历史数据的存储、管理与回溯功能。具体的实现步骤如图1所示。

2.2 空间对象变化检测与增量更新实现步骤

本文通过进行新旧数据间的实体匹配处理，检测空间对象的变化信息，再根据变化信息的分类采取不同的更新操作（见图2）。具体的步骤如下：

图1 矢量数据自适应增量更新方法Fig.1 An adaptive updating method of vector data

图2 矢量数据变化信息检测与增量更新方法Fig.2 Change detection and incremental updating operations of vector data

（1）同名实体的匹配。点状实体的匹配通过比较两者的欧氏距离进行判断。线状实体的匹配可通过计算Hausdorff距离［17］，Fréchet距离或折线－点距离［18］实现。面状实体的匹配可以通过位置邻接度或重叠相似度确定。

（2）更新信息的检测。如果没有原对象与目标对象匹配，则认为目标对象是新增对象。没有目标对象与原对象匹配，认为原对象是消失对象。对于1∶1的对象匹配需要进一步比较几何形状与属性信息，判断是否发生变化。原对象与目标对象1∶n的匹配表明原对象的分解，m∶1的匹配则表示原对象的合并。m∶n的对象匹配表示出现了对象的聚合。

（3）面向对象的增量更新方法。对象的更新操作可分为创建、删除、几何修改与属性修改。对于新增或消失的对象可直接使用创建或删除操作；对于发生几何形状或属性变化的对象，则进行几何修改或属性修改。处理对象合并、分解及聚合的情况，均可采用删除原对象，创建与之匹配的目标对象进行处理。

2.3 接边匹配度计算与自适应的接边算法

2.3.1 接边匹配度计算

异构数据的增量更新可能会引入时空的不确定性，造成同一地理目标实体的分割及空间错位。因此，需要进行接边操作。接边对象的确定与空间距离，语义相似度及空间关系等因素有关。本文提出的接边匹配度计算模型如式（1）所示。

式中，M（A，B）表示对象A、B之间的接边匹配度；d（A，B）是对象A、B的距离衡量指标；s（A，B）为语义相似度衡量指标；r（A，B）表示对象A、B的空间关系，通过实体的缓冲区重叠面积计算进行衡量。ω1、ω2、ω3为权重值，其取值在［0，1］之间，且

距离邻接度的指标d（A，B）的值越大，说明对象A、B的距离越近，接边可能性越大。设对象点集分别为Apts｛a1，…，ap｝、Bpts｛b1，…，bq｝，式（2）

式中，｜Apts－Bpts｜是点集Apts和点集Bpts的欧氏距离。min（）函数是点集中最近两点的距离。dtolerance为距离阈值，若最近距离大于阈值，说明对象A、B之间的距离太远，超出了接边的考虑范围。

s（A，B）为对象的语义相似度。语义相似越高，说明两对象越有可能是同一地理实体的分割，接边的必要性更大。根据Cobb提出的对象属性匹配算法［19］，语义相似度评价模型如公式（3）所示

式中，N为属性数目；simAk是第k项属性值的相似程度；ESWAK为第k项属性的权重。属性类型不同，计算语义相似度的方法也有所差异。

对于数值型的属性，语义相似度可按式（4）计算

式中，x、y分别为接边对象的数值型；sim（x，y）值反映了数值型属性的语义相似度。

对于字符型属性的语义相似性的计算可分为两种情况。定类或定序属性按照语义排成偏序关系，通过计算次序的差别计算语义相似度。对于语义关联性属性不强的属性，则通过计算字符串之间的编辑距离（由字符串A编辑为字符串B所需要进行的最小编辑操作次数）判断两者的语义相似性，具体如式（5）所示

式中，order（x）、order（y）表示x、y在属性中的次序编号；N为属性值个数，对应于分类数或属性值的最大编号。

r（A，B）反映了A、B的空间关系，通过对象的缓冲区重叠面积计算进行衡量，计算方法如式（6）所示

式中，buffer（A）、buffer（B）表示对象A、B的缓冲区面积；intersect（）函数计算重叠的面积，max（）函数用于选择较大的缓冲区面积。

2.3.2 自适应接边的算法

目前的接边方法通过搜索邻近要素及比较属性来确定接边对象［20－21］，容错能力不强，难以处理属性不完整的数据。而且判断的因素单一，容易造成匹配错误。传统的接边处理直接采用union方法进行对象合并［21］，对数据特征的考虑不充分，缺乏灵活性。

自适应处理是根据数据特征自动调整处理方法、参数或约束条件，以取得最优效果的方法。在全球地形可视化［22］、全球离散格网建模［23］、制图表达等GIS领域得到了广泛应用。本文的接边方法综合多项评价指标，能更客观地反映对象特征，有助于提高准确度与容错能力。该方法的自适应性体现在：系统根据数据的精度特征，自动调整对象位移；选择合适的接边方法，使其与高精度的数据相适应。具体实现步骤如下：

（1）进行更新对象周边区域的缓冲区搜索，确定候选接边对象。线对象在首尾节点处创建缓冲区，进行候选对象的搜索。面对象则按一定距离创建缓冲区并搜索相交对象，作为候选接边对象。

（2）进行候选对象的接边匹配度计算，选取匹配度最高的对象进行接边操作。

（3）接边操作需根据对象的几何类型进行相应处理。线对象的优先接边策略是通过比较更新数据与原数据的精度，接边到精度较高的数据。如果数据间的精度相差不大，则可选用平均接边法（见图3）。

图3 线对象优先接边策略Fig.3 Edge matching preferential method of line features

面对象接边策略首先根据数据的精度选择平移的方式，精度低的数据平移至精度高的数据，精度接近的数据则让新旧对象分别平移坐标偏移量的一半。以房屋面对象接边为例进行说明：假设房屋面是具有4个节点的规则矩形，更新后房屋被分为两个独立对象。比较邻近的节点P1、P3或P2、P4的坐标，计算出坐标偏移量。由于对象精度相近，因此把节点分别平移坐标偏移量的一半。最后利用P′1、P′2、P′3、P′44个节点来重画一个多边形（见图4）。

图4 面对象优先接边策略Fig.4 Edge matching preferential method of polygon features

（4）属性融合。接边后对象的属性融合有3种方式，一是以原始数据的属性作为接边后对象的属性；二是以更新对象的属性作为接边后对象的属性；三是通过数值计算的方法获取接边后对象的属性，如数值平均，求和等。

2.4 基于约束规则的空间冲突检测与处理

数据更新可能会带来不符合完整性约束的空间关系，不能正确表达现实地理实体的结构特征［24］。因此，更新后需要进行空间冲突的检测与处理［25］。空间冲突的检测可以通过定义约束规则来实现。本文以Hakima Kadri－Dahmani提出的空间实体完整性约束表达式［12］为基础，修改了约束对象类的表达方法，并添加了属性约束规则与重要性指标。以六元组的方式表达约束规则

式中，ID是空间冲突约束的编号；C1、C2为受约束的空间对象类；TR表示指拓扑约束规则；AR表示属性约束规则；Bd表示规则的执行的范围；I是指该规则的重要性，取值在0～1之间。

空间冲突的检测方法是按照空间冲突约束规则，使用顾及语义的拓扑检验方法构建约束条件进行目标搜索。空间冲突的处理则利用空间编辑功能对冲突对象进行处理。反复检验直至消除所有冲突后，才进行历史库备份与现状库更新处理，完成更新的全过程。

3 试验分析

为验证本文所提出的更新模型与方法，本文在Windows环境下，以Visual Studio 2008为开发工具，集成ArcEngine开发包研制了更新原型系统。实现了增量更新，自适应接边及空间冲突检测等功能，以1∶1000矢量地形图数据进行试验（见图5）。

图5 自适应的矢量数据增量更新试验Fig.5 An experiment of the adaptive incremental updating method

式（1）中接边匹配度的计算与对象之间的空间距离、语义相似度及空间关系等因素密切相关。其中，语义相似度的计算取决于对象属性值的整体匹配程度。作为关键字的编码在语义相似度的计算中应占较大的比重（见图6），以保证接边对象的属性一致性。

图6 接边匹配中的语义相似程度评价Fig.6 The evaluation of semantic similarity in edge matching

接边匹配度参数的设置是通过分析更新对象与原数据，找出必须要进行接边的样例对象m对｛｛A1，B1｝，｛A2，B2｝，…，｛Am，Bm｝｝，把它们的接边匹配度M（Ai，Bi）设置为1，找出明显不需要接边的样例对象n对｛｛A1，B1｝，｛A2，B2｝，…，｛An，Bn｝｝，把它们的接边匹配度设置为0。分别计算对象Ai，Bi的距离邻近度d（Ai，Bi），语义相似度s（Ai，Bi）与空间关系衡量指标r（Ai，Bi）。然后，计算各分指标与接边匹配度的相关系数ri，并对相关系数进行归一化处理，作为接边匹配度的权重参数。

接边匹配度的阈值选择影响着接边的准确度与查全率，本文将接边匹配度设为不同数值进行试验。试验结果如图7所示。观测结果表明随着匹配阈值的提高，匹配要求越严格，查准率也相应提高，并在匹配阈值为0.96处达到高峰。然而，匹配要求的过分严格会造成查全率降低，查全率在匹配阈值为0.95处达到高峰后就逐渐下降。

图7 接边匹配度阈值对接边结果的影响Fig.7 The impact of threshold to the edge－matching results

根据上述参数确定的方法，对接边匹配度的计算参数设定如下：距离指标的权重设为0.6，语义相似度指标的权重设为0.2，空间关系指标的指标值设为0.2，匹配度的阈值设为0.95。将不同的更新样本导入程序进行计算，自适应接边运算的结果如表1所示。

表1 自适应接边方法的试验结果Tab.1 Experimental results of the adaptive edge matching method

试验表明，自适应接边匹配度与接边算法在运算过程中可以保持健壮性，运算速度保持稳定。综合考虑几何与语义条件的接边匹配算法准确程度与查全率高，能够实现自适应的接边操作。

在算法试验中，本文定义了空间冲突拓扑的样例规则，以地形图数据进行模拟运算，空间冲突的检测结果如表2所示。

表2 基于约束规则的空间冲突检查试验Tab.2 The experiment of rule－based spatial conflict detection

试验结果显示：在矢量数据增量更新中产生了空间冲突现象，导致数据的相互关系与地理现实不符，冲突的检查与处理具有必要性。基于约束规则的空间冲突检查方法能有效地检测出错误，结合人工的空间冲突确认与处理，有助于更新后数据库的拓扑一致性维护。

4 结 论

本文以一致性维护与空间冲突处理为切入点，提出了一种自适应的矢量数据增量更新方法。试验表明该方法可应用到基础地理数据库及规划管理数据库的更新与维护中。增城市规划管理数据库系统使用本文所提出的方法，在2008—2011年之间把增城市区域内742宗建设用地竣工测量数据作为增量信息进行入库更新，减少了大量人工操作。因此，可以得出以下结论：

（1）本文所提出的自适应的对象接边算法综合考虑了对象间的空间距离、语义相似度及拓扑一致性，对几何及语义联系最紧密的对象进行自适应的接边处理。可用于解决矢量数据更新中的数据完整性维护的问题。

（2）基于约束规则的空间冲突检测与处理方法，有助于修正与现实地理实体不符的空间关系，维护更新后空间数据库的拓扑一致性。该约束模型设计合理、计算效率高，有利于更新过程中数据质量的控制。

本文提出的增量更新方法是针对同级比例尺的数据进行处理。如果更新数据与基础地理数据的比例尺不同，需要依据相应的数据规范，对更新数据进行制图综合处理。此外，还需要结合多尺度对象匹配的技术进行变化检测，确定更新的对象与范围，以执行跨尺度的联动更新处理。这将是本文后续的研究重点。为更好地提高更新效率与自动化程度，自适应的矢量数据更新方法还应该朝着智能化与网络化的方向发展。因此，进一步的研究工作包括：① 以更新信息的跨尺度传递为切入点，结合制图综合模型与算法，探讨多尺度空间数据联动更新算法；② 应用人工智能与数据挖掘技术，确定接边匹配度模型中的权重参数，并实现空间冲突约束规则的自动提取，提高算法的智能化水平；③ 搭建空间数据动态更新的网络服务框架，实现自适应的矢量数据在线动态更新。

［1］ BRIAT M O，MONNOT J L，KRESSMANN T.Incremental Update of Cartographic Data in a Versioned Environment［C］∥Proceedings of 22nd ICA Conference.A Coruña：［s.n.］，2005：1－9.

［2］ CHEN Jun，LIN Yan，LIU Wanzeng et al.Formal Classification of Spatial Incremental Changes for Updating［J］.Acta Geodaetica et Cartographica Sinica，2012，41（1）：108－114.（陈军，林艳，刘万增，等.面向更新的空间目标快照差分类与形式化描述［J］.测绘学报，2012，41（1）：108－114.）

［3］ FAN Y T，YANG J Y，ZHU D H.An Event－based Change Detection Method of Cadastral Database Incremental Updating［J］.Mathematical and Computer Modeling，2010，51（11－12）：1343－1350.

［4］ CHEN Jun，ZHOU Xiaoguang.Incremental Updating of Spatial Database Based on Topological Linkage，Taking Cadastral Database’s Updating as an Example［J］.Acta Geodaetica et Cartographica Sinica，2008，37（3）：322－337.（陈军，周晓光.基于拓扑联动的增量更新方法研究－以地籍数据库为例［J］.测绘学报，2008，37（3）：322－337.）

［5］ LIN Yan，LIU Wanzeng，WANG Yuhong.Spatial Changed Information Description Based on Updating Process［J］.Geography and Geo－information Science，2011，27（4）：24－27.（林艳，刘万增，王育红.一种基于更新过程的空间变化信息描述方法［J］.地理与地理信息科学，2011，24（4）：24－27.）

［6］ COOPER A K，PELED A.Incremental Updating and Versioning［C］∥Proceedings of 20th International Cartographic Conference.Beijing：Sinomap Press，2001：2806－2809.

［7］ HARDY P，WOODSFORD P.Incremental Updating Using the Gothic Versioned Object Database with the Hydrographic S57ENC and SOTF Spatial Object Transfer Formats［C］∥Proceedings of ICA／ISPRS Workshop on Incremental Updating and Versioning of Spatial Databases.Amsterdam：［s.n.］，2000：1－13.

［8］ HAKIMA K D.Updating Data in GIS：Towards a More Generic Approach［C］∥Proceedings of 20th International Cartographic Conference.Beijing：Sinomap Press，2001：1463－1471.

［9］ ZHANG Feng，LIU Nan，LIU Renyi，et al.Research of Cadastral Data Modeling and Database Updating Based on Spatio－temperal Process［J］.Acta Geodaetica et Cartographica Sinica，2010，39（3）：303－309.（张丰，刘男，刘仁义，等.面向对象的地籍时空过程表达与数据更新模型研究［J］.测绘学报，2010，39（3）：303－309.）

［10］ VAN OOSTEROM P.Maintaining Consistent Topology Including Historical Data in a Large Spatial Database［C］∥Proceedings of ACSM／ASPRS of Autocarto.Seattle：［s.n.］，1997：327－336.

［11］ ADBELMOTY A I，JOINES C B.Towards Maintaining Consistency of Spatial Databases［C］∥Proceedings of 6th International Conference on Information and Knowledge Management.Las Vegas：［s.n.］，1997：293－300.

［12］ HKIMA K D.Consistent Updating of Geographical Database as Emergent Property over Influence System［J］.International Journal of Modeling Identification and Control，2008，3（1）：58－68.

［13］ LIU Wanzeng，Chen Jun.A Method to Confirm the Spatial Conflict in GIS Database for Circular Economy［J］.Geoinformation Science，2007，9（1）：78－83.（刘万增，陈军.循环经济GIS数据库空间冲突的确认方法研究［J］.地球信息科学，2007，9（1）：78－83.）

［14］ CHEN J，LIU W，LI Z，et al.Detection of Spatial Conflict between Rivers and Contours in Digital Map Updating［J］.International Journal of Geographical Information Science，2007，21（10）：1093－1114.

［15］ AN Xiaoya，SUN Qun，XIAO Qiang，et al.A Shape Multilevel Description Method and Application in Measuring Geometry Similarity of Multi－scale Spatial Data［J］.Acta Geodaetica et Cartographica Sinica，2011，40（4）：495－508.（安晓亚，孙群，肖强，等.一种形状多级描述方法及在多尺度空间数据几何相似性度量中的应用［J］.测绘学报，2011，40（4）：495－508.）

［16］ MASUYAMA A.Methods for Detecting Apparent Differences between Spatial Tessellations at Different Time Points［J］.International Journal of Geographical Informa－tion Science，2006，20（6）：633－648.

［17］ DENG M，LI Z L，CHEN X Y.Extended Hausdorff Distance for Spatial Objects in GIS［J］.International Journal of Geographical Information Science，2007，21（4）：459－475.

［18］ CHEN Yumin，GONG Jianya，SHI Wenzhong.A Distance－based Matching Algorithm for Multi－scale Road Network［J］.Acta Geodaetica et Cartographic Sinica，2007，36（1）：84－90.（陈玉敏，龚健雅，史文中.多尺度道路网的距离匹配算法研究［J］.测绘学报，2007，36［1］：84－90.）

［19］ COBB M A，CHUNG M J.FOLEY III H，et al B.A Rule－based Approach for the Conflation of Attributed Vector Data［J］.GeoInformatica，1998，2（1）：7－35.

［20］ DAI Xiangxi，ZHOU Wei，GAO Lei.The Algorithm and Realization of DLG Edge Match of Arbitrary Scope［J］.Bulletin of Surveying and Mapping，2008，7：32－35.（戴相喜，周卫，高磊.DLG数据任意范围接边算法及实现［J］.测绘通报，2008，7：32－35.）

［21］ CAO Jian，LI Guozhong，XU Xiaobo，et al.Study on Edge Matching of Digital Topographic Maps on the Basis of ArcGIS Engine［J］.Geomatic ＆Spatial Information Technology，2010，33（2）：76－78.（曹键，李国忠，徐效波，等.基于ArcGIS Engine的多图幅数字地形图接边算法研究［J］.测绘与空间地理信息，2010，33（2）：76－78.）

［22］ ZHAO Xuesheng，Bai Jianjun，WANG Zhipeng.An Adaptive Visualized Model of the Global Terrain Based on QTM［J］.Acta Geodaetica et Cartographica Sinica，2007，36（3）：316－320.（赵学胜，白建军，王志鹏.基于QTM的全球地形自适应可视化模型［J］.测绘学报，2007，36（3）：316－320.）

［23］ ZHAO Xuesheng，WANG Lei，WANG Hongbin，et al.Modeling Methods and Basic Problems of Discrete Global Grids［J］.Geography and Geo－information Science，2012，28（1）：29－34.（赵学胜，王磊，王洪彬，等.全球离散格网的建模方法及基本问题［J］.地理与地理信息科学，2012，28（1）：29－34.）

［24］ SERVIGNE S，UBEDA T，PURICELLI A，et al.A Methodology for Spatial Consistency Improvement of Geographic Databases［J］.GeoInformatica，2000，4（1）：7－34.

［25］ VAN DER POORTEN P M，ZHOU S，JONES C B，et al.Topologically－consistent Map Generalization Procedures and Multi－scale Spatial Databases［C］∥Proceedings of the Second International Conference on Geographic Information Science.London：Springer－Verlag，2002：209－227.

An Adaptive Method for Incremental Updating of Vector Data

ZHANG Xinchang，GUO Taisheng TANG Tie
School of Geography and Planning，Sun Yat－Sen University，Guangzhou 510275，China

To maintain data consistency and eliminate the spatial conflicts brought by spatial database updating，an adaptive method for incremental vector data updating is proposed.Based on the matching of correspondent objects，a change－object detection and incremental updating method is discussed.Considering the constraint of spatial distance，semantic similarity and topology consistency，it is proposed a calculated method for edge matching evaluation.An adaptive edge matching strategy is also designed to maintain the consistency of spatial data.The rule－based detection and manipulation of spatial conflicts is also discussed.Topographical data are used to verify the practicality and efficiency of the method.

adaptive；incremental updating；data consistency；spatial conflict

ZHANG Xinchang（1957—），male，PhD，professor，PhD supervisor，majors in urban GIS.

ZHANG Xinchang，GUO Taisheng，TANG Tie.An Adaptive Method for Incremental Updating of Vector Data［J］.Acta Geodaetica et Cartographica Sinica，2012，41（4）：613－619.（张新长，郭泰圣，唐铁.一种自适应的矢量数据增量更新方法研究［J］.测绘学报，2012，41（4）：613－619.）

P208

A

1001－1595（2012）04－0613－07

国家自然科学基金（40971216；41071246）

丛树平）

2012－03－01

2012－05－17

张新长（1957—），男，博士，教授，博士生导师，研究方向为城市地理信息系统。

E－mail：eeszxc＠mail.sysu.edu