夏永华，张新长，杜国明，郭泰圣

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

我国基础地理数据库建设取得了巨大成绩，为各类GIS 应用工程提供了多比例尺的地理空间数据[1]。然而，随着空间数据建设的逐步完成，人们逐渐意识到空间数据更新将代替空间数据获取成为地理信息系统建设的瓶颈[2]，当前地理信息系统研究的核心己从数据生产转移到数据的更新，数据更新关系着地理信息系统的可持续发展[3]。

空间数据库的更新模式一般包括增量式更新和版本式更新[4]。由于空间数据具有数据结构复杂，数据量大的特点。采用增量式更新，能够节省硬盘存储，提高更新效率，对历史数据进行有效的管理。增量式更新以其方式灵活而且能够更好的保证空间数据的现势性的优点，是未来空间数据库更新的主要趋势[5]。空间数据的变化捕捉过程是空间数据库进行增量式更新的首要环节[6-7]，也是近年来学术界研究的重点[8]，其精度和效率直接影响了数据库更新的精度和效率。

目前主要的变化捕捉方法有快照差分法、时间戳法、触发器法、日志法、API法等[9-11]。近年来，基于快照差分法的变化捕捉方法成为空间数据库领域更新的主流，涌现了一系列的研究成果。文献[12]对空间实体关系进行研究分析，根据Egenhofer九交模型，提出基于基于自定义空间关系的空间查询方法，进行要素变化检测。徐凯等[13]提出基于空间索引的搜索方法，利用基于规则网格的空间索引和基于对象的R树家族索引进行对象匹配，进行变化信息检测。而基于要素缓冲区叠加分析进行搜索匹配的方法则是目前领域应用中最为普遍的方法。然而这些变化检测方法一般采用要素遍历的方法，对于大范围、多地物的矢量数据用遍历法的运算量很大，搜索效率低下，不能满足实际的数据更新要求。本文在分析要素历遍缓冲区叠加分析方法的基础上，根据实际的工程化需求，提出基于四叉树的变化捕捉方法，提高空间数据更新的效率。

1 缓冲区叠加分析变化捕捉机制研究

空间数据具有空间特征和属性特征，通过要素历遍，比较新旧版本要素的空间特征和属性特征，采用几何匹配的方法来对比新旧版本要素的要素变化情况[14]。根据匹配要素的结果要素变化类型可分为：新增、删除、几何信息修改、属性信息修改、分解、合并、聚合[15]。具体关系如图1。

图1 要素匹配和变化类型之间的关系Fig.1 Relation between feature matching result and change type

缓冲区分析是地理信息系统重要和基本的空间操作功能之一。它是在给定空间对象或集合周围建立一定距离(缓冲半径)的多边形实体，以确定这些物体对周围环境的影响范围或服务范围[16]。对不同类型的目标实体，所产生的缓冲区也不同。叠加分析则是地理信息系统最常用的提取空间隐含信息的手段之一。空间叠加分析是指在统一的空间参照系统条件下，把分散在不同层上的空间信息按相同的空间位置叠加到一起，产生新的特征(新的空间图形或空间位置上的新属性)的分析方法[17]，其结果综合了原来两层或多层地图要素所具有的属性。

通过对旧图层要素进行遍历，建立旧要素缓冲区，并以此和新图层进行叠加分析，从而找到该旧要素的可能匹配的候选集，即利用旧要素的缓冲区，判断目标要素是否位于缓冲区内，如是，则将目标要素作为源要素的候选匹配要素，实现旧要素的粗匹配。并进一步进行要素精匹配，从而判断旧要素变化类型。具体算法思路如下：

1)历遍旧图层要素，建立原要素的缓冲区，并通过空间查询搜索与该要素缓冲区重叠的新要素。若搜索结果为空，则旧要素变化类型为1:0(删除)的情况。

2)若搜索结果存在要素集，则历遍要素集，建立的新要素的缓冲区，并搜索其区域重叠的旧要素图层，并比较匹配要素的属性信息，反复进行则可以判定旧要素变化类型为1∶1(几何修改、属性修改、未变化),1∶M(分解),N∶1(合并),N∶M(聚合)的情况。

3)历遍新图层要素，建立新要素的缓冲区(buffer)，并搜索出与原要素无任何区域重叠的新要素。则为0:1(新增)的情况。

该算法思路简单直观、易于理解，且精度较高，能够准确的搜索出新旧版本图层的变化信息，确定要素的变化类型，建立精度较高的增量要素集，为后续数据更新打下基础。然而该算法要求对新旧图层的所有要素进行多次要素历遍，运算量较大，使得更新效率较低，速度较慢，对硬件配置需求较高，并不能满足工程化数据更新对于更新效率的要求。

2 基于四叉树的变化捕捉方法研究

增量式更新侧重获取数据变化的增量信息，对图层区域中不变区域进行历遍要素搜索匹配降低了增量信息提取的效率。在进行历遍要素搜索匹配之前，过滤掉不变区域会极大的提高变化捕捉的效率。本文结合实际，提出一种基于四叉树的变化捕捉方法，根据四叉树原理，对图层进行四叉树剖分，计算区域内的“节点-弧段”特征[18]，并进行层次检索，以快速定位到变化区域，再对该区域内的要素进行历遍要素搜索匹配，确定其变化类型。从而大大减小历遍要素次数，缩减计算量，提高变化捕捉的效率。

基于四叉树的变化捕捉算法思路：

1)把更新数据中的所有对象集合的最小外接矩形区域作为四叉树的根节点。

2)计算区域内的空间要素的变化情况，要素的节点数与弧段数可以快速获取，并对区域变化特征具有标识作用。因此，本文结合要素的节点与弧段树，提出区域要素变化特征评估模型：

F(Pf,Nf) =J(Pv,Nv)α1+H(Pe,Ne)α2

(1)

(2)

(3)

式(1)中，Pf，Nf分别为该区域范围内原数据和更新数据的集合，F(Pf,Nf)可反映要素的整体变化情况。Nv，Pv是新旧要素的结点集合。Ne，Pe为相应的新旧弧段集合，也可表示为面图层的边界弧段集合。J(Pv,Nv)和H(Pe,Ne)分别用于表示区域内新旧数据集的节点数与弧段长度的变化情况。α1,α2表示结点变化指标与弧段变化指标所占的权重，取值在0-1之间且α1+α2=1。对于点图层，由于无法计算弧段特征，故α2设为0。式(2)中，节点集的总数量通过函数Jcnt()来计算，式(3)中弧段集的总长度通过Hlen()计算。

3)判断区域内数据是否发生变化。若F(Pf,Nf)的计算结果大于0说明该区域存在明显的变化信息，需要进行分割。分割的方法为：分别提取区域内新旧要素重心的X，Y坐标，并计算其均值PXa，PYa，NXa，NYa。以点((PXa+PYa)/2，(NXa+NYa)/2)为中心沿X轴，Y轴方向把原区域分划为4个子区域。

4)重复执行步骤2)、3)，直到划分区域内的要素数目少于阈值为止。结束剖分后，记录区域范围及所包含的对象，以备进行下一步对象的匹配。如图2

图2 四叉树变化捕捉原理Fig.2 The principle of change detection on quad-tree

5)根据检索出的变化区域，采用缓冲区叠加分析的方法进行搜索匹配，进行变化捕捉，确定要素变化类型。具体流程如图3。

图3 基于四叉树的变化捕捉算法流程图Fig.3 The flowchart of change detection based on quad-tree

该算法结合对象节点数和弧段长度作为指标快速检测变化区域，利用四叉树索引原理，对更新数据进行分割，有助于数据的分步式并行处理，可以迅速定位变化区域。在数据量较大的矢量数据更新中，减少运算量和内存占用量，提高变化捕捉效率，以满足工程化数据更新对于硬件配置和更新效率的需求。

3 实验结果及分析

为验证算法实现效率，本文在Window系统下，利用Visual Studio 2008开发平台，集成ArcEngine9.3进行二次开发。系统分别实现要素历遍和四叉树变化捕捉两种算法，以增城市1∶2 000矢量地形图为示例数据，对比两种算法的更新效率。如图4。

实验选取点、线、面三种不同的几何类型的地形图数据进行实验，分别进行要素历遍缓冲区叠加分析变化检索和四叉树变化捕捉实验，对比其消耗时间。实验结果如表1所示。

图4 基于四叉树的变化捕捉实验Fig.4 An experiment of change detection based on quad-tree

方法几何类型更新要素个数平均计算时间/s历遍要素检索点56089四叉树变化捕捉点56013历遍要素检索线1176327四叉树变化捕捉线1176629历遍要素检索面98327654四叉树变化捕捉面9835763

实验结果表明，四叉树变化捕捉方法可以大幅度提高变化信息的检测效率。矢量数据的属性信息是存储在二维表中，相对空间信息来说，较为容易检索获取，在对区域的“点-弧段”变化特征进行计算时速度较快，能迅速定位至变化区域。在接下来的缓冲区叠加分析搜索匹配中，由于只对变化区域进行要素搜索匹配，从而使得整个变化捕捉过程效率得到大幅提高。对于点要素，由于只需要计算节点的数目变化情况，无需衡量弧段的长度变化情况。因此，计算效率提高得最明显。对于线要素和面要素由于减少了对不变数据的搜索匹配与指标计算，运算效率也有大幅度的提高。特别是对于变化率较小的区域，算法的效率提高更明显。在更新精度上，由于四叉树变化捕捉在计算“点-弧段”变化特征时仅从几何信息上进行比较，忽略了几何信息不变而属性信息变化的情况，同时也忽略部分因矢量要素位移或旋转等变化类型而使“点-弧段”不变的情况，使更新精度略低。

4 结论与展望

本文在分析要素历遍变化捕捉方法的基础上，从实际的空间数据更新需求出发，提出了基于四叉树的变化捕捉方法。该方法通过“点-弧段”变化特征计算，进行四叉树分割快速定位到变化区域，使变化检测更具有针对性，从而提高变化捕捉效率，满足工程化数据更新的要求，为GIS的数据动态更新提供有效的解决思路。最后通过开发系统对该理论方法进行实现，结合实际更新数据进行试验。试验结果也证明了该方法相比较于传统的更新方式能大幅度够提高变化捕捉的效率。

存在问题及下一步展望：四叉树变化捕捉方法在计算变化特征时会忽略部分几何信息不变而属性信息变化的要素，造成精度略低，其次，部分要素由于发生位移或旋转变化而导致区域的“点-弧段”特征没有发生改变，从而忽略这种变化类型。另外，在要素搜索匹配中N:M的类型中，空间分割容易造成新旧要素处于不同的空间区域，影响更新结果。因此，下一步的研究工作包括： ① 添加对属性信息变化的检测，考虑部分几何信息不变而属性信息变化的要素，提高变化捕捉的精度。② 更为严密的考虑要素的变化类型。研究对于要素位移或旋转等变化类型的有效检测方法，从而提高变化捕捉的准确度。③ 改进变化区域的分割方法，把具有集聚特征的新旧要素更有效地划分在同一区域，减少区域边界对变化捕捉的影响。

参考文献：

[1] 陈军. 论数字化地理空间基础框架的建设与应用[J]. 测绘工程, 2002, (03): 1-6.

[2] UITERMARK H T，VAN OOSTEROM P J M，MARS N J I．Propagating updates: Finding corresponding objects in a multi-source environment[C]// Proceedings of the 8th International Symposium on Spatial Data Handling, Vancouver, Canada, 1998：580-591.

[3] FRITSCH D. GIS data revision-visions and reality[C]//Note speech in joint ISPRS commission workshop on dynamic and multi-dimensional GIS. Beijing:NGCC,1999.

[4] 熊湘琛, 张新长, 曹凯滨. 城市基础地形数据增量更新研究[J]. 测绘通报, 2009, (03): 24-26.

[5] 孙英杰. 基于变化信息文件的增量更新方法研究 [D]. 长沙: 中南大学, 2008.

[6] 李德仁. 利用遥感影像进行变化检测[J]. 武汉大学学报:信息科学版, 2003, (S1): 7-12.

[7] 张剑清, 朱丽娜, 潘励. 基于遥感影像和矢量数据的水系变化检测[J]. 武汉大学学报:信息科学版, 2007, (8): 663-666.

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

[9] 钟巧华. 数据仓库的数据抽取技术研究[J]. 计算机工程, 2004, (S1): 62-63.

[10] 章水鑫, 徐宏炳, 于立. 增量式ETL工具的研究与实现[J]. 现代计算机:专业版, 2005, (03): 6-10.

[11] 刘伟, 佟俐鹃. 异构数据库集成中的变化捕获方案设计[J]. 计算机应用研究, 2005, (07): 213-215.

[12] 吴建华, 傅仲良. 数据更新中要素变化检测与匹配方法[J]. 计算机应用, 2008, (06): 1612-1615.

[13] 徐凯. 基于网格索引的几何匹配算法研究[D]. 长沙: 中南大学, 2009.

[14] 万远, 李霖, 应申. 地理信息数据变化检测系统的研究与实现[J]. 计算机工程, 2010, (09): 4-6+13.

[15] 王育红, 陈军. GIS客户数据库更新的基本问题[J]. 地理信息世界, 2008, (01): 5-12.

[16] 汤国安, 杨昕. ArcGIS地理信息系统空间分析实验教程[M].2版.北京:科学出版社, 2012, 153.

[17] 黄杏元, 马劲松, 汤勤. 地理信息系统概论[M].修订版. 北京: 高等教育出版社, 2001.

[18] CHENG C, LU F, CAI J A. Quantitative scale-setting approach for building multi-scale spatial databases[J]. Computers and Geosciences, 2009, 35(11): 2204-2209.