面向更新的空间目标快照差分类与形式化描述

陈 军，林 艳，2，刘万增，周晓光

1.国家基础地理信息中心，北京100830；2.北京师范大学资源学院，北京100875；3.中南大学测绘与国土信息工程系，湖南长沙410083

面向更新的空间目标快照差分类与形式化描述

陈 军1，林 艳1，2，刘万增1，周晓光3

1.国家基础地理信息中心，北京100830；2.北京师范大学资源学院，北京100875；3.中南大学测绘与国土信息工程系，湖南长沙410083

时空变化分类是地理信息建模与更新的一个核心问题，直接影响着数据存储组织、增量信息采集、联动更新处理和变化信息发布的效率与水平。以往主要研究目标整体的变化分类，对目标差异部分的变化分类研究甚少。分析时空目标公共部分在差异类型区分中的作用，认为应兼顾异同部分，提出一种基于目标差、被差和交的目标快照差三元组，为时空目标差异部分的分类描述提供形式化方法。继而对面、线的快照差进行形式化分类描述，给出有实际意义的变化类型。然后根据线目标快照差类型构建对应的增量更新操作；按照面目标快照差类型进行时空目标的变化提取及分类试验等。

时空变化；目标快照差；分类；增量；更新

1 引 言

目前地理信息更新主要是用空间快照模型去记录和表达时空变化，即将t1到t2时间段发生变化和未变化的地理空间目标全部用t2进行时间标识，形成t2时刻的整体快照［1－2］。其主要缺点是难以从中直接获知有哪些目标发生了变化，同时存在着大量的数据冗余，不利于变化信息传输和时空变化分析。英国测绘部门在其Master－Map产品中对每一个空间目标赋予唯一标识码，将其中几何或属性发生变化的目标用变化采集时间加以标识，所形成的更新数据集由目标快照组成［3］，由于只给出发生变化的目标，可减少更新信息的传输量，但并未给出这些目标发生了什么变化，因而目标快照并不是真正的变化信息。

就本质而言，地理空间目标从t1到t2时间段的变化由空间图形及属性差异表征，可看做是目标i在t1时刻快照Oi（t1）与t2时刻快照Oi（t2）之差，简称为目标快照差（object increments）。这种目标快照差直接能反映有哪些目标发生了什么变化，是真正的变化信息。地理信息更新的基本任务就是采集这种地理空间目标的快照差，并进行相应的更新处理、变化表达与传播［4－6］。因此，目标快照差的分类描述与表达是GIS时空数据建模的一个基本问题，直接影响着地理信息增量采集、联动更新处理、变化信息传播、变化分析等［5－7］。迄今为止，国内外同行对时空变化分类作过一些研究，但主要停留在目标整体变化的分类描述［8－13］，对目标快照差的分类研究很少。例如，文献［8］根据t1到t2时间段目标的存在状态、变换及运动，将目标整体变化分为出现、消失、扩张、移位等8类；文献［9］根据空间拓扑关系将居民地变化分为5种类型；文献［10—11］结合时间和拓扑关系，分析归纳出空间目标变化前后的多种时态拓扑关系；文献［12］通过跟踪空间数据库中代表目标存在与否的目标标识码，将地理实体在时间域的波动归纳为存在、不存在等9种变化类型；文献［13］提出以时空对象演变过程建立时空数据更新模型，来反映地籍对象的演变过程。就目标快照差的分类研究来说，笔者的研究小组曾通过目标变化前后的标识码、维数和图形求差，将目标图形及属性差分为14种基本类型［14－15］。其不足之处是通过枚举的方式进行三级细分，没有建立统一的快照差形式化区分方法，同时标识码和维数变化在本质上属于图形变化，即分类判断的3个依据存在相关性，导致分类结果在变化语义上存在着重叠。

本文针对这一问题，将空间目标的集合交加入到图形差的判断，以综合地考虑目标变化前后的异同部分，构建一个由目标差、被差、交组成的形式化分类描述模型；并对集合操作进行正则化处理，以保证快照差具有实际的时空变化语义；继而对面、线的快照差进行了形式化分类描述，给出了完备性分析，并探讨了快照差分类在增量信息采编与表达中的应用。

2 快照差分类描述的三元组

2.1 顾及异同部分的空间交、差判断

图形差（ 和被差（／）是研究和判断目标变化的一种方法。设G1、G2分别为目标Oi在t1和t2时刻的空间图形；G1＼G2为那些属于G1但在G2不再存在的空间图形，即消失的那部分图形，称为负差，可用｛e｜e∈G1且┐（e∈G2）｝表示；G1／G2则代表增加的图形部分，即正差，用｛e｜e∈G2且┐（e∈G1）｝表示。

设有目标O1～O5，其在t1和t2时刻的空间分布如图1（a）、（b）所示。对变化前后的目标进行空间求差和被差，得出t1－t2时间段的目标快照差，如图1（c）所示。从中不难看出，目标O1在原地往某些方向上扩张，在另外方向上收缩，几何变化表现为负差D1及正差D2；目标O2整体移位，表现为负差D3和正差D4；O3在原地向外扩张，对应的变化为正差D5；线状目标O4局部发生摆动，变化部分呈负差D6和正差D7；O5为新增目标，D8为其正差。

图1 时空目标的变化Fig.1 Change of objects

式（1）给出了上述基于图形差和被差的目标快照差分类描述方法

式中，R2（G1，G2）是一个二元组。对图1而言，O1和O2属于两种不同的变化类型，O1既有增加部分和消失部分，还有部分图形保持不变，即变化前后目标有公共部分；而O2是目标整体发生偏离，变化前后的目标无重叠。若用式（1）进行图形差和被差计算，却会得到相同的二元组，无法将这两种不同的差异类型区分开来。同理，O3和O5也属于两种不同的差异类型，前者是在原图形基础上向四周扩张，前后目标有公共部分；后者是新增目标，不存在公共部分，但两者具有相同的差和被差。这说明仅用差和被差难以有效地区分空间目标的快照差类型，而“交”代表的时空目标公共部分有着特殊的作用，应该将其用于目标快照差类型的区分或判断。

若将目标Oi在t1和t2时刻的图形G1、G2投影到同一空间上去（图2），G1与G2之间存在着差、被差、交（∩）3种关系。为便于讨论，记G1＼G2为α，G1／G2为γ，G1与G2的公共部分即不变部分｛e｜e∈G1且e∈G2｝用G1∩G2表示，记为β。

图2 时空目标的快照差Fig.2 Object increments

将交加入到式（1），形成了基于“＼”、“／”、“∩”的目标快照差三元组描述模型

式（2）兼顾了时空目标的异、同两部分，能更好地区分目标快照差的类型。

2.2 基于几何完整性的图形正则化处理

图1（c）中部分目标的快照差（如D1、D2、D5）是不封闭的，究其原因，是由于空间目标的集合运算会产生缺边、悬边、缺点、悬点等低于当前目标维数的图形。对于面目标来说，是由封闭的边界来表达现实世界中的实体，而这些不封闭的图元虽在数学上有意义，却不能表达完整的空间实体，在数据库中是不可能存在的。

计算机图形学专家曾采用正则集合运算，解决了集合运算造成三维形体产生悬边、悬面等问题，生成完整的正则形体（regularized－set），其具体步骤是先求集合的内部，再求闭包［16－17］。参照这一做法，对前述二维图形的一般集合操作进行正则化处理，使之成为正则集合运算，正则集合运算去除了悬边、悬点，并补全缺边、缺点等，生成满足几何完整性约束要求的正则图形（regularized－graph）。

设“＼＊”、“∩＊”、“／＊”分别表示正则差、正则交和正则被差。线要素经过正则集合运算的结果不再是维数降低的点，仍然是线；面状要素经过正则集合运算的结果仍然是完整的封闭多边形。表1给出了图1中目标O1的运算示例，O1经一般集合运算形成的多边形轮廓是不封闭的，而经过正则集合运算后生成完整目标。

表1 正则集合运算示例Tab.1 Examples of regularized set operations

正则集合运算保证了计算得到的目标快照差的几何有效性，计算结果若非空，则必定是正则图形。将正则运算算子代入式（2），则得到目标快照差的三元组描述模型

3 面和线目标快照差的形式化分类

3.1 面目标快照差

采用式（3）目标快照差三元组描述模型，首先对面目标的快照差进行正则集合运算和判断，分别判断三元组的取值为空或非空，剔除实际不存在的情况，并排除几何图形保持不变的情况，得出6种具有实际意义的面目标快照差类型，如表2前6项所示。

表2 面目标的快照差类型Tab.2 Incremental difference of area objects

续表2

由于引入了“交”，表2能将图1中混淆的快照差类型有效地区分出来。例如，目标O1对应着表2的第6种情况，即部分图形扩张和收缩，并保持一部分公共图形不变，其三元组取值为（┐∅┐∅ ┐∅）。O2对应着表2第3种情况，即图形发生了偏离，但不存在着公共部分，其三元组取值为（┐∅ ∅ ┐∅）；目标O3和O5分别对应第4和第1种类型，属于图形扩张正差、目标正差。

面目标快照差的类型反映了时空目标几何形态的变化，可用于时空变化的几何特征、分布规律的统计分析及表达。

3.2 线目标的快照差分类

同理，对线目标按式（3）进行分类判断，得到表3所示的线目标快照差分类描述结果，其中前6种具有实际意义。图1中线目标O4对应着表3的第6种情况，三元组取值为（┐∅ ┐∅┐∅），语义上属于延长缩短差。

表3 线目标的快照差类型Tab.3 Incremental difference of linear objects

上述时空目标快照差分类的完备性可以从以下3方面加以分析：一是参与计算的集合算子G1＼＊G2、G1∩＊G2、G1／＊G23部分互不包含，彼此独立，且共同构成了时空目标的全集G1∪G2，是对时空目标的完全剖分；二是从集合运算的结果来看，正则集合运算是同维数的图形计算，只需判断计算结果为空或非空即可，而无需从理论上分析集合运算可能产生低维数的图形；三是参与集合运算的对象来说，分别对线、面进行目标快照差的分类，满足了GIS数据库中不同地物要素类型的变化分类需求。

4 在增量更新中的应用试验

4.1 增量采集

增量采集的是线目标自身的变化部分或面目标轮廓线的变化部分，因此线目标快照差的类型决定了增量采集过程中采用何种更新操作。

按照有实际意义的6种线目标快照差类型，分析建立了与其相对应的更新操作：① 目标正差操作，创建线目标并赋予属性；② 目标负差操作，删除线目标及其属性记录；③ 偏离正负差操作，重新采集新目标的轮廓线或执行移动等操作；④延长正差操作，以原目标待延长的一端为起点，采集延长部分的线，并将其合并；⑤ 缩短负差操作，将线打断，并将缩短的一段删除；⑥ 延长与缩短差操作，采集延长部分的线，并求出该线与原目标的交点，将原目标在两交点之间的部分删除。

以一幅2004年1∶5万线状、面状（轮廓线）水系数据作为待更新数据，部分截图如3（a），与最新遥感影像对比，分别采集目标快照差、目标快照，如图3（c）、（d）所示，更新后数据如图3（b），其中黑色线为变化部分。以图3（c）虚线框中的快照差4为例说明采集方法，该湖泊轮廓向北方向改道，快照差为延长正差＋ΔP和缩短负差－ΔP，对其采集的放大图如3（e）所示，先求出＋ΔP与原目标的两个交点Pt1和Pt2，然后将原目标中以Pt1、Pt2为端点的线段－ΔP删除，最后将＋ΔP与原目标合并、重建拓扑，构成完整的新目标。面状河流2的采集方法与目标4相同。线状河流1和5均延长了＋ΔP，捕捉其延长端点，采集延长部分，重建拓扑，构成完整目标。3为新增水系，直接采集线目标的空间坐标及属性信息。

经统计，这幅图中发生变化的目标有57个，其中，若采集变化的目标快照，需采集4861个节点；若采集快照差只需采集529个节点，工作量减少了89%。可见，对于水系这样采样点较多的数据，当目标发生了局部变化，采集快照差相对于采集目标整体能显著提高工作效率。

图3 目标增量采集Fig.3 Incremental information collection

4.2 变化信息提取及分类

目标快照差的提取和分类是增量表达、统计、发布的前提，实现方法：首先根据名称、位置等信息对更新前后同一地理目标进行匹配，若某一目标不存在，将其图形定义为∅；然后对变化前后对应的目标分别进行求差、求交、求被差3种集合运算，并对集合运算结果进行正则化处理，使之表示完整的几何目标；最后，判断三元组的计算结果为空或非空，根据表2、表3的目标快照差分类规则，自动判断变化类型。

采用同一幅两个时期的1∶5万面状居民地数据进行上述试验，更新前后的数据分别包含1253个、1421个居民地目标，数据量分别为394K、406K，局部居民地分布情况如图4（a）、4（b）。在Window操作系统中，ArcMap的VBA环境下执行，消耗的时间为56s。图4（c）给出了目标快照差的分类计算结果。对分类结果进行人工判读，验证该分类方法的正确性。

图4 增量发布中的变化表达Fig.4 Change representation in increments publishing

将提取的目标快照差作为增量发布，其优势体现在以下3个方面：

（1）从变化表达来看，以目标快照的方式发布变化信息，如图4（d），提供的是所有变化的居民地目标整体，没有描述各个目标究竟哪里发生了变化。而目标快照差，如图4（c）直观地表达了“差异”情况。

（2）从统计变化量得知，该幅数据中居民地的变化率为7.3%，目标快照差存储量占原数据量的4.9%，显然，相对于整幅地图，只发布目标快照差能大大提高数据传输的效率。

（3）就变化类型而言，目标快照只能将居民地几何变化描述为新建、消失、几何变化3类，而目标快照差将其细化为目标正差、目标负差、扩张正差、收缩负差、偏离正负差、扩张收缩差共6种类型。表4给出了对变化分类的统计，得知该地区居民地的变化类型以目标正差、扩张正差为主，即有36个新修的居民地斑块，增加面积达2.23km2，有23块居民地在原有基础上向外扩建了1.62km2；此外，还有16块居民地共0.92km2完全拆除；14块在原有基础上部分拆除，共计0.59km2；有2块居民地既有扩建又有拆除部分，面积分别为0.38km2、0.27km2；有1块居民地整体发生了偏移，偏移前后的面积分别为0.22km2、0.16km2。这些统计数据可用于研究地形数据的空间格局变化、时空传播规律等。

表4 地物目标变化类型Tab.4 Change type of object increments in updating

5 结 论

时空变化的分类描述是地理信息时空建模的核心问题之一，目前只对目标变化的差异做了初步分类描述，尚未建立形式化分类描述模型。本文通过实例分析，讨论了公共部分在区分时空目标差异类型中的重要作用，认为在判断时空目标差异时要兼顾异、同部分，并进行基于几何完整性的图形正则化处理，从而提出了一种基于目标差、被差和交的三元组描述方法，较好地解决了目标快照差的形式化分类与描述难题。按照这种形式化描述模型，分别将线、面目标快照差分为6种，在此基础上，根据线目标快照差类型，构建了对应的增量更新操作；按照面目标快照差类型进行了时空目标的增量提取与发布试验等。点目标变化较简单，按三元组描述方法，将点目标快照差分为目标正差、目标负差、偏离正负差三种。

研究表明，目标快照差分类为地理信息增量数据采集、提取、发布等提供了规范作业和定量分析的科学依据，可以为表达、处理地理目标的变化提供统一的分类和描述方法。

三元组模型可用于简单空间目标的快照差描述与分类，下一步将针对网络化标报、增量信息采编、变化信息服务等实际需要，对其进行必要的扩展或细化，进一步研究复杂时空目标的差异分类与形式化描述、顾及语义的基础地理信息要素差异分类和增量信息模型等，为应用系统开发和工程化应用提供技术支撑。

［1］ LANGRAN G.Time in Geographic Information Systems［M］.London：Taylor ＆Francis，1992.

［2］ CHEN Jun，WANG Donghua，SHANG Yaoling，et al.Master Design and Technical Development for National 1∶50 000Topographic Database Updating Engineering in China［J］.Acta Geodaetica et Cartographica Sinica，2010，39（1）：7－10.（陈军，王东华，商瑶玲，等.国家1∶50 000数据库更新工程总体设计研究与技术创新［J］.测绘学报，2010，39（1）：7－10.）

［3］ MURRAY K，SHIELL D.A Framework for Geographic Information in Great Britain［J］.Cartographic Journal，2004，41（2）：123－129.

［4］ CHEN Jun，ZHAO Renliang，WANG Donghua.Dynamic Updating System for National Fundamental GISs：Concepts and Research Agenda［J］.Geomatics World，2007，5（5）：4－9.（陈军，赵仁亮，王东华.基础地理信息动态更新技术体系初探［J］.地理信息世界，2007，5（5）：4－9.）

［5］ COOPER A，PELED A.The International Cartographic Association’s Working Group on Incremental Updating and Versioning［C］∥ICA／ISPRS Workshop on Incremental Updating and Spatial Databases.Amsterdam：［s.n.］，2000：1－9.

［6］ CHEN Jun，LI Zhilin，JIANG Jie，et al.Key Issues of Continuous Updating of Geo－spatial Databases［J］.Geomatics World，2004，2（5）：1－5.（陈军，李志林，蒋捷，等.基础地理数据库的持续更新问题［J］.地理信息世界，2004，2（5）：1－5.）

［7］ 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.）

［8］ CLARAMUNT C，THÉRIAULT M.Managing Time in GIS：an Event－oriented Approach［C］∥Recent Advances on Temporal Databases.Zurich：Springer－Verlag，1995：23－42.

［9］ PAN Li，WANG Hua.Automatic Recognition of Change Types of Residential Area Using Topology Relations Model［J］.Geomatics and Information Scicence of Wuhan University，2009，34（3）：301－303.（潘励，王华.利用拓扑关系模型自动检测居民地的变化类型［J］.武汉大学学报：信息科学版，2009，34（3）：301－303.）

［10］ CHRISTOPHE C，BIN J.An Integrated Representation of Spatial and Temporal Relationships between Evolving Regions［J］.Journal of Geographical Systems，2001，3（4）：411－428.

［11］ SHU Hong，CHEN Jun，DU Daosheng，et al.Definition of Spatio－temporal Topological Relationships and Description of Temporal Topological Relationships［J］.Acta Geodaetica et Cartographica Sinica，1997，26（4）：299－306.（舒红，陈军，杜道生，等.时空拓扑关系定义及时态拓扑关系描述［J］.测绘学报，1997，26（4）：299－306.）

［12］ HORNSBY K，EGENHOFER M J.Identity－based Change：a Foundation for Spatio－temporal Knowledge Representation［J］.International Journal of Geographical Information Science，2000，14（3）：207－224.

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

［14］ ZHU Huaji，CHEN Jun，JIANG Jie.Research on Modeling and Classifying of Topographical Data Change for Incremental Information Distribution［C］∥Proceedings of MIPPR05：Geospatial Information，Data Mining，and Applications.Wuhan：［s.n.］，2005.

［15］ ZHU Huaji.Research on the Classification and Representation of Incremental Information of Topographic Data［D］.Beijing：Institute of Remote Sensing Application，Chinese Academy of Sciences，2005.（朱华吉.地形数据增量信息分类与表达研究［D］.北京：中国科学院遥感应用研究所，2005.）

［16］ SUN Jiaguang，HU Shimin.A Fundation Coursebook of Computer Graphics［M］.Beijing：Tsinghua University Press，2005.（孙家广，胡事民.计算机图形学基础教程［M］.北京：清华大学出版社，2005.）

［17］ REQUICHA A A G，VOELCKER H B.Constructive Solid Geometry［C］∥Technical Memorandum，Production Automation Project.Rochester：University of Rochester，1977.

Formal Classification of Spatial Incremental Changes for Updating

CHEN Jun1，LIN Yan2，1，LIU Wanzeng1，ZHOU Xiaoguang3
1.National Geomatics Center of China，Beijing100830，China；2.College of Resources Science and Technology，Beijing Normal University，Beijing100875，China；3.Department of Geomatics，Central South University，Changsha410083，China

The classification and description of spatial incremental changes is one of the fundamental problems in geo－spatial data modeling and updating.It plays a significant role in the spatio－temporal data organization，incremental change capture，event－based updating and propagation of changes.Existing studies in this field is focused mainly on the classification of the whole of objects and the incremental changes of spatial objects has not been well addressed.The study examined the role of the common parts of two spatio－temporal objects and proposed to consider both the common parts and differences in the distinguishing and formalizing the incremental changes of spatial objects.A formal description model is proposed based on three elements，i.e.，difference，difference by，and intersection，with the associated regularization operation.A formal classification of the incremental changes is derived for both area and linear objects.The results of this formal classification have been applied to develop the operations of incremental capture and to calculate and analyze the incremental changes.

sptaio－temporal；object increments；classification；incremental changes；updating

CHEN Jun（1956—），male，professor，PhD supervisor，majors in geo－spatial data modeling，updating and services.

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.）

P208

A

1001－1595（2012）01－0108－07

国家自然科学基金（40701141）；国家测绘地理信息局科技领军人才基金

雷秀丽）

2010－12－30

2011－06－20

陈军（1956—），男，教授，博士生导师，主要从事基础地理信息系统建模、更新与服务的研究与应用。

E－mail：jchen＠gps.ceic.gov.cn