面状实体增量信息提取过程中变化类型自动检测方法

张 旗 升，王 艳 慧

(首都师范大学资源环境与地理信息系统北京市重点实验室,北京 100048；首都师范大学三维信息获取与应用教育部重点实验室,北京 100048；首都师范大学城市环境过程与数字模拟国家重点实验室培育基地,北京 100048)

面状实体增量信息提取过程中变化类型自动检测方法

张 旗 升，王 艳 慧*

(首都师范大学资源环境与地理信息系统北京市重点实验室,北京 100048；首都师范大学三维信息获取与应用教育部重点实验室,北京 100048；首都师范大学城市环境过程与数字模拟国家重点实验室培育基地,北京 100048)

为解决空间数据库增量更新过程中空间实体变化类型识别困难、判别方法复杂度高、判别因子冗余度高以及识别过程自动化程度低等问题，提出一种基于实体特征匹配模型的面状实体变化类型检测方法。该方法在新旧版本面状空间数据库增量实体集合基础上，构建实体变化类型评判规则，设计并集成面状要素属性及几何特征算子，对单一面状实体9种变化类型进行检测和提取，最大限度地降低判别算法复杂度和判别因子冗余度，实现面状实体增量信息提取过程中变化类型的判别、提取、入库，以及判别过程与增量实体提取过程的紧密联系和有机耦合。

增量更新；变化类型检测；实体几何特征；增量信息提取

0 引言

增量更新是目前空间数据库更新的主要方法，实体变化信息检测和提取是空间数据库增量更新的基础。完整的变化信息不仅包含变化实体，还应记录引发实体物理变化的变化类型信息[1-4]。变化类型信息对于增量数据存储组织、增量信息采集、联动更新处理、更新质量控制和变化信息发布有着重要影响，用户可利用实体变化信息进行地物更新操作、生命周期跟踪、历史数据回溯、变化信息统计分析以及时空传播规律、地物变化趋势预测等应用[5-9]。

面状实体变化类型的分类方法较多，研究中常将变化类型分为消失、出现、重现、属性变化、扩张、收缩、平移、旋转、变形9种基本变化类型[10-12]。目前，对于增量信息变化类型的检测和提取，研究者主要从两种角度展开研究：地理实体变化事件驱动、实体特征变化信息驱动。大多数学者在基于事件驱动的增量更新过程中把空间实体变化类型信息更新到空间数据库中[6,8，13-15]，该方法一定程度上解决了增量信息提取过程中实体变化类型信息检测的难题，但需提前获知实体变化类型信息，并通过变化类型信息(地理变化事件)进行增量更新，这意味着需要在更新操作之前把变化类型信息存储在数据库中，其实质相当于人工添加变化类型信息，而多数情况下，对大量空间数据进行更新时，很难追溯这些实体所经历的变化过程并提前获知所有空间实体的变化类型信息。此外，实体间拓扑关系[16,17]以及实体目标维数、尺寸、形状和位置等属性信息也被用于变化类型信息判别[7,18]，还有学者采用快照差三元组描述模型[9]、四因子模型[19,20]等进行变化类型检测研究，这些方法与基于变化事件的判别方法相比，自动化程度有所提高，但或多或少存在判别方法复杂度高、判别因子冗余度高、变化类型信息推断不详细、不准确的问题。针对上述问题，本文提出一种面状实体增量信息提取过程中变化类型的自动检测方法，在实体匹配模型所提取的增量实体集合基础上，设计并定义变化类型自动检测规则，集成面状实体的属性信息和反映面状实体不同几何特征的子算子，对单一面状实体的9种变化类型进行检测和提取，在保证算法准确性的前提下，最大限度降低算法的复杂度和判别因子的冗余度，实现面状实体增量信息提取过程中变化类型的自动判别、提取、入库，以及判别过程与增量实体提取过程的有机耦合。

1 实体变化类型检测方法

面状实体变化类型检测方法主要用于完善空间数据增量更新中增量信息提取过程，将实体变化类型信息和变化实体一同组织在增量信息中。为顾及方法普适性，本文以集成属性和几何特征的空间实体匹配思想设计变化类型检测规则，对面状实体进行变化类型自动检测与提取。即在增量实体集合的基础上利用属性、几何位置、大小、形状、方向信息构建实体变化类型检测模型，以简洁的判别条件和判别算子保证变化类型信息检测的准确性，并最大限度降低算法的复杂度。同时，将其与增量实体提取过程紧密联系，实现增量信息提取过程中变化实体提取和变化类型信息推断的有机耦合。该方法在增量信息提取流程中的位置以及与增量实体提取的联系如图1所示。

图1 增量信息提取流程Fig.1 The process of incremental information extraction

1.1 基于实体匹配特征的变化类型判别思想

实体特征匹配内容包括几何特征匹配和属性(语义)特征匹配，两者同时达到匹配标准时，可将实体视为匹配对象。如果用M表示匹配模型，用Attribute表示其属性值，用Features表示其几何特征，则空间实体匹配模型：M=(Attribute,Features)。而面状实体几何特征又包括位置、大小、形状、方向[21]，用Position、Size、Shape、Direction分别表示面状实体的位置、大小、形状、方向4个几何特征，则Features=(Position,Size,Shape,Direction)，再根据空间实体匹配模型得到细化的面状实体匹配模型M=(Attribute,Position,Size,Shape,Direction)。

不同实体变化类型对应不同的属性信息及几何特征变化组合。结合上述模型进行分析，可知面状实体可通过Attribute、Position、Size、Shape、Direction5个匹配指标进行变化类型判别，模型中5个指标不同值的组合代表不同的变化类型信息；当匹配数据中不含属性数据时，可用除去Attribute之外的其他4个判别条件进行几何匹配和变化类型判别[22]。假设5个指标中任何一个达到该条件所设置的阈值标准，则将该条件判断值记为T，反之记为F，那么当M=(T，T，T，T，T)时表示实体匹配成功。

运用该匹配模型中5个指标值的组合进行实体变化类型推理的思路见图2，在增量实体集合的基础上，根据模型M中各判别条件的值可对除消失、出现、重现之外的6种变化类型进行区分。在变化实体集合基础上进行变化类型推断，不仅可以更加准确地对各种变化类型进行判别，还可大大减少判别流程计算量，提高算法效率。此外，对于消失、出现两种变化类型，只需要比较两个版本中任一地理实体在同一地理范围内是否有交集，如果新版本数据库中存在实体A，而待匹配的数据库中该范围内和实体A无交集，则可将此种变化类型归为出现类型，反之，为消失;重现则需要对3个时期的数据库进行判别，其变化过程可视为消失和出现过程的叠加。

图2 实体变化类型判别思想Fig.2 The thought of entity change type discrimination

1.2 实体变化类型判别算子选取

由上文可知，用属性信息和实体几何特征进行面状变化类型判别前，需选取相应的判别算子来度量其属性及几何匹配特征。对变化实体属性数据进行匹配判别时，只需对两个面状实体的属性字段进行语义匹配。而选取几何判别算子时，首先需要保证其整体性，即兼顾形状、大小、位置、方向四方面的判别指标，以保证判别的准确度；其次，应考虑算法的复杂度，以保证算法的简洁性；最后，所选取的算子组合判别模型应不受数据种类、尺度影响。综上所述，本文选取质心判别算子度量面状实体的位置特征,面积判别算子度量其大小特征,而转向角累积函数匹配算子度量其形状和方向特征。具体包括:

(1)质心判别算子：用于反映实体间的距离(位置)指标，质心距离越小代表两个面实体的位置相似度越高。这里，用E1、E2代表两个待匹配面实体，D(E1,E2)表示两个面实体之间的质心距离，r1、r2分别表示面实体E1和E2最小外接矩形对角线长的一半。此处引入r1、r2可使距离评分免受实体尺寸大小的影响。则质心判别算子度量式如下：

(1)

(2)面积判别算子：假设S(E1)、S(E2)分别表示两个面实体E1和E2的面积,则用面积差判别面状实体大小相似性的公式如下：

(2)

(3)转向角累积函数判别算子：用来度量面状实体形状相似性，同时还可以在一定程度上度量其方向相似度。原理如下：选取两个实体顶点中的某个方向的形状特征点为参考点，该参考点和实体质心连线与坐标系横轴所成的夹角的正弦值最大，同时参考点的X轴的坐标大于该实体质心的X坐标，这种参考点选取方法的好处是：可以将面状实体的方向信息考虑到算法中。记录特征点逆时针弧段方向与X轴的夹角，并沿逆时针记录每个弧段的归一化长度(弧段长度与周长比值)，以归一化长度作为X轴，各点沿周边转向角累加值作为Y轴。假设E1(x)、E2(x)为面实体E1和E2的转向角累积函数，则度量实体形状和方向信息的转向角累积函数判别算子公式如下:

(3)

转向角累积函数判别算子可同时度量面状实体的形状和方向信息，但匹配实体的形状差异性和方向差异性都可能造成该判别算子不达标的情况，用以上3个算子的组合并不能判别实体的旋转变化类型，因此，当且仅当质心判别算子和面积差判别算子达标，而转向角累积函数判别算子不达标时，引入辅助判别算子进行旋转变化类型的判别，若该辅助算子计算结果大于所设置的阈值则代表两个实体形状相同而方向不同，此时，可将变化类型判定为旋转，否则将变化类型归类为变形。该判别算子采用形状参数(Form Factor)[21]度量其形状差异性，假设S(E1)、S(E2)，L(E1)、L(E2)分别表示两个面实体E1和E2的面积和周长，则辅助判别算子公式如下：

AssistResult=

(4)

1.3 实体变化类型判别规则

下文中IsAttributeMatch代表两个面状实体属性匹配与否，若匹配则记为True,反之，记为False;将1.2节中4个子算子的结果分别用PositionResult、AreaResult、ShapeDirectionResult、AssistResult表示，其相似性阈值分别设定为φ1、φ2、φ3、φ4,符号and为逻辑与运算符,ChangeType代表变化类型结果；对于旧版空间数据库除GeoDatabase(O)中的任意面状实体A和新版空间数据库中GeoDatabase(N)中的任意面状实体B,同时存在一个早于GeoDatabase(O)的地理空间数据库 GeoDatabase(E)。

对于任意的面状实体A和B,根据匹配模型可得其匹配规则，描述如下：

MatchingRule:if((IsAttributeMatch=True)and(PositionResult>=φ1)and(AreaResult>=φ2)and(ShapeDirectionResult>=φ3))thenMatching(A,B)

即：如果面状实体E1和E2被认定为属性信息和几何特征信息均匹配，则E1和E2被视为匹配对象。

在此基础上，假设各版空间数据库中除去匹配实体之外的对应实体集合分别为ChangeCollection(O)、ChangeCollection(N)、ChangeCollection(E)，其对应面状实体分别为E1、E2、E0。对任意的E1、E2、E0，根据上文描述的变化类型判别思想，结合所选取的几何特征判别算子，单一面状实体的9种基本变化类型推断规则可描述为：

Rule1:∀E2∈ChangeCollection(N),∃E1∈ChangeCollection(O),if(E1∩E2=Ø)thenChangeType(E1)←Vanish

如果面状实体E1与任意实体E2在同一空间范围内无交集，则将实体E1的变化类型归为消失。

Rule2:∀E1∈ChangeCollection(O),∃E2∈ChangeCollection(N),if(E2∩E1=Ø)thenChangeType(E2)←Appearance

如果面状实体E2与任意实体E1在同一空间范围内无交集，则将实体E2的变化类型归为出现。

Rule3:if((Matching(E0,E2)=Ture)and(ChangeType(E0)=Vanish)and(ChangeType(E2)=Appearance))thenChangeType(E2)←Reappearance

如果面状实体E0和E2匹配且其变化类型分别为消失和出现，则将E2的变化类型归为重现。

Rule4:if((IsAttributeMatch=False)and(PositionResult>=φ1)and(AreaResult>=φ2)and(ShapeDirectionResult>=φ3))thenChangeType(E1→E2)←AttributeChange

如果面状实体E1和E2中几何特征未改变，而属性信息改变，则将实体变化类型归为属性变化。

Rule5:if((IsAttributeMatch=True)and(PositionResult>=φ1)and(AreaResult<φ2)and(ShapeDirectionResult>=φ3)and(S(E2)

如果面状实体E1和E2中面积几何特征改变，E2的面积相对于E1减小，而其他判别指标达标，则将实体变化类型归为收缩。

Rule6:if((IsAttributeMatch=True)and(PositionResult>=φ1)and(AreaResult<φ2)and(ShapeDirectionResult>=φ3)and(S(E2)>S(E1)))thenChangeType(E1→E2)←Expansion

如果面状实体E1和E2中面积几何特征改变，且E2的面积相对于E1增大，而其他判别指标达标，则将实体变化类型归为扩张。

Rule7:if((IsAttributeMatch=True)and(PositionResult<φ1)and(AreaResult>=φ2)and(ShapeDirectionResult>=φ3))thenChangeType(E1→E2)←Translation

如果面状实体E1和E2中位置几何特征改变，而其他判别指标达标，则将实体变化类型归为平移。

Rule8:if((IsAttributeMatch=True)and(PositionResult>=φ1)and(AreaResult>=φ2)and(ShapeDirectionResult<φ3)and(AssistResult>=φ4))thenChangeType(E1→E2)←Rotation

如果面状实体E1和E2中方向几何特征改变，而其他判别指标达标，则将实体变化类型归为旋转。

Rule9:∀E1∈ChangeCollection(O),E2∈ChangeCollection(N),if((ChangeType∉(Rule1∪Rule2∪Rule3∪Rule4∪Rule5∪Rule6∪Rule7∪Rule8))thenChangeType(E1→E2)← Deformation

由于变形类型众多,如对所有情况进行判别，将增加算法复杂度，降低算法效率,故将变化实体集合中不符合Rule1-Rule8的变化类型归为变形。

1.4 变化类型检测流程

(1)匹配数据预处理：在进行变化类型检测前应对匹配数据进行预处理以确定其候选匹配数据集，得到的候选数据集在大致相同的空间范围内应具有相同的数据格式、坐标及投影系统，同时消除空间拓扑错误等，避免影响算法性能和匹配准确度。

(2)面状变化实体提取：对面状实体变化类型进行检测以避免对两个数据库中的全部空间数据进行检测，提高算法效率。可通过前述匹配规则或其他任意面状实体匹配方法得到匹配面实体，新、旧版本数据中的实体与匹配实体的差集Collection2、Collection1分别为新、旧版本数据中的变化实体集合。

(3)变化实体集合交集判断：对于Collection2和Collection1中没有交集的面状实体，则可直接用Rule1-Rule3进行判别，得到消失、出现、重现3种变化类型结果。

(4)计算各判别子算子的值，并判断实体间属性是否匹配：对Collection1和Collection2中的交集不等于空集的面状实体，分别计算其质心判别算子、面积差判别算子、转向角累积函数判别算子的值PositionResult、AreaResult、ShapeDirectionResult，并确定属性判别结果IsAttributeMatch,匹配为True,不匹配为False。

(5)设定判别子算子阈值：阈值为经验值，其设定与数据种类、尺度、用途、精度要求等均有关系，阈值设定的大小影响类型判别的准确度，算法中将3个算子的阈值分别设定为φ1、φ2、φ3。

(6)变化类型判别：将PositionResult、AreaResult、ShapeDirectionResult三者的值与阈值φ1、φ2、φ3进行比较，根据上文所叙述的9种判别规则判定变化类型。特别地，当且仅当两个面状实体符合条件((IsAttributeMatch=True)and(PositionResult>=φ1)and(AreaResult>=φ2)and(ShapeDirectionResult<φ3))时,计算其辅助判别算子的值AssistResult，并对其设置合适的阈值φ4，若AssistResult>φ4,则变化类型为Rotation，否则为Deformation。

(7)变化类型信息汇总，并将变化类型信息与变化实体关联：将步骤(3)、(6)中得到的变化类型结果进行汇总，并将变化类型结果赋到增量实体的属性当中，从而得到完整的面状空间数据库增量信息。

上述7个步骤即为增量信息提取过程中面状实体变化类型检测流程(图3)。

图3 变化类型检测方法流程Fig.3 The process of change type discrimination method

2 实验及结果分析

为验证本文面状实体增量信息提取过程中变化类型检测方法的可行性，采用c#编程语言结合ArcGIS Engine进行实验，选取北京市房山区不同时期的两幅相同范围的大比例尺电子地图中的部分房屋数据进行判别实验。由于实验数据为新旧两期建筑物数据，而实际数据集中少有旋转、平移两种变化类型，且重现变化类型是基于三期变化数据而言，因此，为完整证明本方法的可行性，实验中将模拟的具有平移、旋转变化类型的地物加入所提取的变化实体集合当中进行模拟实验。重现作为消失和出现变化类型的复合变化类型，可通过消失、出现、属性变化3种变化类型的实验结果来验证其判别的可行性。实验结果如图4所示，图中每一行前半部分代表的是旧版本和新版本数据对应的ID号，后半部分代表对应实体的变化类型。对所得结果进行统计，并将实验判别结果与实际变化类型进行对比，同时进行精度分析，结果如表1。

图4 变化类型实验判别结果Fig.4 Discriminant result of change type experiment

表1 变化类型实验判别结果精度分析Table 1 Accuracy analysis of change type discriminant experiment result

上述实验表明,该方法可以对除旋转和变形两种之外的变化类型进行精准判别；而旋转物变化类型的判别准确度为93%，完整度为89%，变形地物变化类型的判别准确度为90%，完整度为95%。从表1可知，旋转地物变化类型判别的漏判数为1，错判数为1，而变形的情况中判别冗余数为1，错判数也为1，旋转地物变化类型中漏配的地物为变形判别时冗余的地物，而错判地物的实际变化类型则为旋转，变形地物变化类型当中错判地物的实际变化类型则为旋转。通过分析可知，产生判别错误的原因一是转向角累积判别算子对于地物方向的描述不够精确，二是判别算子阈值设定不准确。对于整体(全部)变化类型而言，由于本文的判别方法是在增量变化实体集合的基础上，实验得到的变化类型实体判别个数和实验数据中的变化实体个数应相等，因此其判别准确度和完整度应保持一致，本实验中，整体变化类型的判别准确度和完整度均为97%。

同时，为了验证该方法的可靠性，另外选取其他不同比例尺的4个研究区域进行变化类型检测实验。实验结果中旋转和变形地物变化类型的判别准确度以及完整度均维持在90%～97%之间；而对于其余变化类型，其判别精度依然可以达到100%。因文章篇幅限制,本文仅给出几个研究区的整体变化类型判别结果(表2)，其精度均保持在95%以上。综上可知，本文所提出的面状实体增量信息提取过程中变化类型检测方法在实际应用中能够很好地对增量信息中的面状实体变化类型进行判别，具有良好的可行性和适用性。

表2 不同研究区域判别实验结果Table 2 Discriminant experiment result of different research areas

3 结论

本文对面状实体增量信息提取过程中变化类型检测问题进行了研究，基于目标匹配思想，并在新旧版本面状空间数据库增量实体集合的基础上，选取面状实体的属性信息和反映其不同几何特征的判别子算子对单一面状实体的9种变化类型进行检测和提取，详细描述了面状实体增量信息提取过程中实体变化类型检测流程，实现了实体变化类型判别方法与增量实体提取过程的紧密联系和有机耦合。实验结果表明，本方法在实际应用中能够很好地对增量信息中的面状实体进行变化类型判别，具有良好的可行性和适用性。但本文仅探讨了相同比例尺下的面状实体变化类型的判别，对于不同比例尺下的实体变化类型判别方法及算法实现过程中自适应阈值的设定还需进行更深层次的探讨和研究。

[1] BRIATM O,MONNOT J L,KRESSMANN T.Incremental Updata of Cartographic Data in a Versioned Environment[C].Proceedings of 22nd ICA Conference,2005.1-9.

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

[3] 姬存伟,武芳,巩现勇,等.居民地要素增量信息表达模型研究[J].武汉大学学报(信息科学版),2013,38(7):857-861.

[4] BADARD T,RICHARD D.Using XML for the exchange of updating information between geographical information systems[J].Computers Environment and Urban Systems,2001,25(1):17-31.

[5] GOMBOS I M,Z ALIK B,KRIVOGRAD S.Comparing two sets of polygons[J].International Journal of Geographical Information Science,2003,17(5):431-443.

[6] 周熠,孙群,刘海砚,等.用于变化发现的地理事件建模与表达[J].测绘科学技术学报，2013,30(1),87-90.

[7] 邢汉发,陈军,李长辉,等.参数化的空间实体变化分类方法[J].中南大学学报(自然科学版),2014,45(2):495-500.

[8] 罗国玮,张新长,齐立新.顾及地理要素变化过程的数据增量更新方法[J].中山大学学报(自然科学版),2014,53(4):131-141.

[9] 陈军,林艳,刘万增,等.面向更新的空间目标快照差分类与形式化描述[J].测绘学报,2012,41(1)：108-114.

[10] CLARAMUNT C,THEIAUL T M.Managing time in GIS:An event-oriented approach[A].CLIFFORD J,TUZHILIN A.Recent Advances on Temporal Databases[C].Zurich Switzerland:Springer-Verlag,1995.

[11] HORNSBY K,EGENOFER M.Identity-based change:A foundation for spatio-temporal knowledge representation[J].International Journal of Geographical Information Science,2000,14(3):207-224.

[12] 周晓光,陈军.基于变化映射的时空数据动态操作[J].遥感学报,2009,13(4)：653-658.

[13] 周晓光,陈军,朱建军,等.基于事件的时空数据库增量更新[J].中国图形图像学报,2006,11(10):1431-1438.

[14] KLIPPEL A,WORBOYS M,DUCKHAM M.Identifying factors of geographic event conceptualisation[J].International Journal of Geographical Information Science,2008(2):183-204.

[15] 姬存伟，武芳,巩现勇,等.居民地要素增量信息表达模型研究[J].武汉大学学报(信息科学版),2013,38(7):857-861.

[16] 陈军,周晓光.基于拓扑联动的增量更新方法研究——以地籍数据库为例[J].测绘学报,2008,37(3):322-327.

[17] 潘励,王华.利用拓扑关系模型自动检测居民地的变化类型[J].武汉大学学报(信息科学版),2009,34(3):301-304.

[18] 朱华吉,吴华瑞,马少娟.空间目标增量时空变化分类模型[J].武汉大学学报(信息科学版),2013,38(3):339-343.

[19] 马少娟,朱华吉.时空变化分类与表达研究[J].测绘科学,2007,32(4):88-90.

[20] 朱华吉,吴华瑞.基于4 因子模型的地形数据变化分类[J].长安大学学报(自然科学版),2007,27(1):59-62.

[21] 邵世维.基于几何特征的多尺度矢量面状实体匹配方法研究与应用[D].武汉：武汉大学，2011.

[22] ZHAO Z Q,STOUGH R R,SONG D J.Measuring congruence of spatial objects[J].International Journal of Geographical Information Science,2011,3(1):113-130.

Automatic Detection Method for Change Type in Incremental Information Extraction Process of the Area Entities

ZHANG Qi-sheng,WANG Yan-hui

(BeijingKeyLaboratoryofResourceEnvironmentandGeographicInformationSystem,CapitalNormalUniversity,Beijing100048;KeyLaboratoryof3-DimensionalInformationAcquisitionandApplication,MinistryofEducation,CapitalNormalUniversity,Beijing100048;StateKeyLaboratoryIncubationBaseofUrbanEnvironmentalProcessesandDigitalSimulation,CapitalNormalUniversity,Beijing100048，China)

In order to solve the problems such as the difficulties of identifying the spatial entities change types,high complexity of discrimination methods,redundancy of discrimination factors,low automation degree of the identification process,et al,in the process of incremental updating,an automatic detection method for entity change type on the foundation of entity features matching model has been presented.The method builds the discriminant rules for entity change type based on incremental entity sets of old and new versions′ area spatial databases,designs and integrates attribute and geometric feature operators of area entities to detect and extract nine change types of single area entity,minimizes complexity of the algorithm and redundancy of detection factors,achieves identification,extraction,storage of change types in the process of incremental information extraction,and achieves close connection,organic coupling with the process of discrimination and increment entities extraction.Experimental results show that the method has good feasibility and applicability,and the method could be well applied to change type discrimination of area entities.

incremental updating;change type detection;entity geometric feature;incremental information extraction

2015-10-12；

2015-12-17

国家自然科学基金项目(41371375)；北京市自然科学基金项目(8132018)

张旗升(1990-)，男，硕士研究生,主要研究方向为GIS方法与应用。*通讯作者E-mail：huiwangyan@sohu.com

10.3969/j.issn.1672-0504.2016.02.003

P208

A

1672-0504(2016)02-0011-06