时空过程拓扑关系表达

张雪伍

摘要：利用前后两个空间拓扑关系的组合来表达原子空间拓扑关系变化过程，从而将空过程之间复杂的空拓扑关系变化过程，分解成30种基元空间拓扑关系变化过程。利用4交模型将时态拓扑关系与空间拓扑关系过程基元进行笛卡儿积耦合，形成240种原子时空过程拓扑关系，并对其几何表达和语义进行详细的说明。最后，论文给出了利用原子时空过程拓扑关系进行时空过程拓扑关系表达方法进行说明，并给出了时间区间重合的多态时空过程拓扑关系表达鉴别策略。

关键词： 时空数据挖掘；时空过程；时空过程拓扑；时空耦合

中图分类号：P208 文献标识码：A 文章编号：1009-3044（2015）21-0202-04

Spatiotemporal Process Topological Relation

ZHANG Xue-wu

（College of Computer Science and Engineering， Changshu Institute of Technology， Changshu 215500， China）

Abstract： The combination of two adjacent spatial topological relations can describe the atom spatial topology variation process. So， the complex variation process of spatial topological relation can be decomposed into the 30 atom spatial topology relation variation processes. The 240 atom spatiotemporal process topological relations are generated through coupling the temporal topological relations with the 30 kinds of atom spatial topological relations based on the Cartesian product. Finally， the author gives the method of describing the simple spatiotemporal process topological relationship based on the atom spatiotemporal process topology， and the strategies are used to identify the spatiotemporal process topology relationship with the coincidence time interval.

Key words：spatiotemporal data mining； spatiotemporal process； spatiotemporal topology； spatiotemporal coupling

时空过程是地理实体在指定时间区间内的发展演化过程，是时间与空间的有机统一整体，其间的拓扑关系是时间拓扑关系与空间拓扑序列的有机偶合体。空间拓扑和时态拓扑分别从空间和时间的角度独立地表达拓扑关系，机械地离散了具有密切联系的时空对象时间与空间的联系，不能表达时空过程之间的动态拓扑关系。因此，很多学者开始尝试将时间和空间纳入一个统一的框架内，探索时空拓扑关系的表达。Christophe等基于时间与空间的等同性归纳出了56种时空关系，但其没有区分时态方向与时态拓扑关系，也没有进一步探讨时空拓扑操作的实现[1-2]。徐志红等基于地籍实体空间静态空间关系，采用地籍实体变更事件驱动地籍实体及其拓扑关系的变更[3]。高勇等基于时间片时空数据模型和9交模型的建模思想针对二维欧式空间内的平面移动对象，构建了移动对象的时空拓扑关系定性表达模型[4]。还有部分学者利用空间拓扑与时态拓扑关系的笛卡尔积来表达时空拓扑关系，并利用耦合矩阵对时空拓扑进行描述[5-6]。曾联斌等在时段时空数据模型的基础上，利用9交模型定义了基于时段的时空对象时空拓扑关系模型[7]。以上研究，将空间拓扑和时态拓扑进行耦合来表达时空拓扑，是时空过程拓扑的一种特例，并没有体现空间拓扑关系在时间区间的变化过程。

鉴于此，本文旨在统一的时空框架下，将基于时空过程原子实体来探讨时空过程之间的拓扑关系，为进一步的时空过程推理、分析和时空数据挖掘提供理论基础。因此，将时间与空间进行正交组合构建统一的时空框架体系，在时态拓扑和空间拓扑分析的基础上构建原子时空过程拓扑关系，并对其几何表达、语义描述和联合矩阵表达进行讨论，最后利用原子时空过程拓扑关系实现时空过程拓扑关系的统一存储与计算表达。

1 时态与空间拓扑关系描述

1.1 时态拓扑关系描述

Allen基于时间区间逻辑模型，给出了13种互不相交且联合完备的时态拓扑关系，但是它混淆了时态方向关系和时态拓扑关系[8]。舒红等将时态区间作为时态拓扑分析的基元，并用4-交模型和9-交模型来表达时态区间之间的拓扑关系，并证明二者在时态拓扑表达上具有等同性[9，10]。

8种时态拓扑关系分别为时间相离、时间相接、时间部分覆盖、时间覆盖、时间被覆盖、时间重合、时间包含与时间被包含，记为：TDisjoint，TMeet，TOverlap，TCover，TCoveredBy，TEqual， TContain，TInside，其4交模型的矩阵表达，如图1所示[10]。

1.2 时态拓扑关系描述

空间拓扑模型主要有两种表达模型RCC-n模型和n交模型。RCC-n模型是基于哲学逻辑的公理化拓扑，它的研究主要集中于空间推理领域[11]。n交模型是基于点集拓扑理论的数学形式拓扑，主要用于GIS领域的空间拓扑分析[12]。所以下面主要分析基于n交模型空间拓扑关系的表达。

现实世界中的空间对象A是由内部、边界和外部三个部分组成，用符号分别表示为，[A?]、[?A]和[A-]。n交模型的基本思想是利用两个对象的边界、内部、外部之间的交集矩阵来表达空间拓扑关系，矩阵元素取值为[θ]或[θ]。根据是否考虑对象的外部，又可以分成4交模型和9交模型，二者在空间拓扑关系表达上具有等同性。

8种面/面拓扑关系的4交模型的矩阵表达，如图2所示。

2 时空过程拓扑关系表达

2.1空间拓扑关系变化顺序

地理空间在时空过程中的变化体现在两个方面：①地理实体的变化，包括空间位置、形状、大小、属性变化等；②空间关系的变化，主要包括空间距离、方向和拓扑关系的变化。空间拓扑关系的变化主要是由地理实体自身的形状变化和地理实体位移所引起的。

时空过程中，地理实体会发生不同程度的变化，从而可能引起空间拓扑关系的变化，这种变化是按照一定的顺序进行的。图3 描述了由地理实体的位移和形变所引起的空间拓扑关系变化的顺序关系。

图3中，A和B是两个面状地理实体。双向箭头两侧的拓扑关系是相邻的，即箭头一侧拓扑关系发生变化可能会产生箭头另一侧的拓扑关系，但不可能出现跨越相邻拓扑关系直接形成另一种拓扑关系的变化过程，如相离拓扑关系变化不能直接产生部分覆盖拓扑关系，其必须经过相邻拓扑关系才能变成部分覆盖拓扑关系。图中黑色双向箭头两侧的拓扑关系皆可通过地理实体形变或地理实体位移完成相互转化；红色双向箭头两侧的拓扑关系只能通过地理实体的形变完成相互转化。

2.2原子时空过程拓扑关系

时空过程是地理实体在时空多维空间中，沿着时间维向前不断移动、变化的过程，其变化形成的轨迹是一个以时间为纵轴的时空立方体。图4展示了地理实体A和B沿着时间轴t演化，形成的时空立方体。

图4 时空多维空间中地理对象演化过程

在时间区间[Tstart，Tend]内，A和B都在向前演化，其中A从t1时刻开始向周围匀速扩散，B在整个时间区间内没有发生任何变化。A与B的拓扑关系在时间区间内发生了变化，由相离变化成相邻。时空过程中，地理实体的演化是一个持续变化的过程，但与其他地理实体之间空间拓扑关系的变化是离散的、突变的。

随着时间区间长度的增加，拓扑关系的变化过程变得更加复杂。以简单、明确为目的，这里仅探讨基本拓扑关系过程的表达。

定义 基元空间拓扑关系过程：在指定的时间区间内，地理实体间的空间拓扑关系仅在相邻拓扑关系之间变化或不发生变化，形式化表达为：[Tpprocess=Tp1→Tp2]，其中Tp1和Tp2分别为变化前后的拓扑关系，当Tp1=Tp2，被认为是一种特殊的基元空间拓扑关系过程。

基于4交模型，用拓扑关系组合结构来表达基元空间拓扑关系过程，如式1所示。

[Tpprocess=Tp1→Tp2=（A??B?）1：（A??B?）2（A???B）1：（A???B）2（?A?B?）1：（?A?B?）2（?A??B）1：（?A??B）2] （1）

为了表达的统一性，将在时间区间保持不变的空间拓扑关系也表达为前后相同的基元空间拓扑关系过程。根据拓扑关系变化的顺序，可以将相邻拓扑关系过程分解成30种基元空间拓扑关系过程，其几何表达，如图5所示。

图5 30种基元空间拓扑关系过程的几何表达

图5中黄绿色和灰色图形分别表达两个面状地理实体在时间区间[tstart，tend]演化过程所形成的时空立方体。此处空间拓扑关系的变化只涉及相同的时间区间的面状实体，并未考虑时间区间之间的时态拓扑关系。

2.3原子时空过程拓扑关系表达

在时空过程中，时间和空间是相互联系、相互影响的：时间是通过空间对象或相互关系的变化来体现，空间是通过地理实体在时间方向存在的延续性而得到证明；同时，二者又是相互独立的，它们可以单独地在各自领域中进行推理和计算。因此，通过时间与空间状态序列的耦合可以对时空过程进行表达。从认知学的角度出发，需要把时空过程作为一个时空整体进行理解与描述，但由于持续变化过程表达的复杂性和计算机只能进行二进制数存储，目前大都采用有序的空间状态序列来对时空过程进行表达。

时间与空间的相互独立性，为通过基元空间拓扑变化过程与时态拓扑关系耦合表达时空过程拓扑提供了可能。因此，本文采用基元空间拓扑关系过程与过程所占时间区间之间的时态拓扑关系进行笛卡尔积耦合，来表达原子时空过程拓扑关系。4交模型基元空间拓扑关系过程与4交模型时态拓扑关系笛卡尔积矩阵的原子时空过程拓扑关系表达，如式2所示。

[Tpprocess：：T=Z??12Z??12Z??12Z??12：：T1??T2?T1???T2?T1?T2??T1??T2] （2）

以4交模型的基元空间拓扑关系过程与4交模型的时态拓扑关系笛卡尔积耦合，TPProcess×TEqual、TPprocess×TDisjoin、TPprocess×TMeet、TPprocess×TOverlay、TPprocess×TCover、TPprocess×TCoveredby、TPprocess×TContain、TPprocess×TInside，形成240种原子时空过程拓扑关系。由于篇幅所限，在此仅给出TPprocess×TDisjoin的30种原子时空过程拓扑关系的几何表达和耦合矩阵，如图6所示，其的基本语义描述如表1所示。其他的耦合矩阵的时空过程拓扑语义及其耦合矩阵，可以根据相同的方法得到。

图6 TPprocess×TInside原子时空过程拓扑关系的几何表达与耦合矩阵

表1 TPprocess×TInside原子时空过程拓扑关系的语义描述

[原子时空过程拓扑关系＼&语义描述＼&TRDisjoint→Disjoint：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系一直保持相离＼&TRDisjoint→Meet：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由相离变化到相接＼&TRMeet→Disjoint：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由相接变化到相离＼&TRMeet→Meet：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系一直保持相邻＼&TRMeet→Overlay：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由相接变化到部分覆盖＼&TROverlay→Meet：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由部分覆盖变化到相接＼&TROverlay→Overlay：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系一直保持部分覆盖＼&TROverlay→Cover：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由部分覆盖变化到覆盖＼&TRCover→Overlay：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由覆盖变化到部分覆盖＼&TRCover→Cover：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系一直保持覆盖＼&TRCover→Contain：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由覆盖变化到包含＼&TRContain→Cover：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由包含变化到覆盖＼&TRContain→Contain：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系一直保持包含＼&TROverlay→Equal：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由包含变化到重合＼&TREqual→Overlay：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由重合变化到包含＼&TREqual→Equal：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系一直保持重合＼&TROverlay→Coveredby：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由部分覆盖变化到被覆盖＼&TRCoveredby→Overlay：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由被覆盖变化到部分覆盖＼&TRCoveredby→Coveredby：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系一直保持被覆盖＼&TRCoveredby→Inside：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由被覆盖变化到被包含＼&TRInside→Coveredby：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由被包含变化到被覆盖＼&TRInside→Inside：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系一直保持被包含＼&TRCover→Equal：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由覆盖变化到重合＼&TREqual→Cover：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由重合变化到覆盖＼&TRContain→Equal：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由包含变化到重合＼&TREqual→Contain：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由重合变化到包含＼&TRCoveredby→Equal：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由被覆盖变化到重合＼&TREqual→Coveredby：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由重合变化到被覆盖＼&TRInside→Equal：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由被包含变化到重合＼&TREqual→Inside：：TInside＼&时空过程对应时间区间为被包含关系，空间拓扑关系由重合变化到被包含＼&]

2.4 时空过程拓扑关系表达

随着时空过程所占时间区间长度的增大，地理实体之间的空间拓扑关系变化也变得更加频繁和复杂。通过相邻空间拓扑变化状态的有序集合和与其对应时间区间的时态拓扑关系进行笛卡尔积耦合来表达复杂时空过程之间拓扑关系策略在理论上是可行的，但实际操作起来就会因为拓扑关系状态过多、变化过程复杂和数目庞大的拓扑关系变化过程分类，而致使其实用性大大降低。

对于长时间区间时空过程拓扑关系，可以采用化繁为简的策略，将其离散成多个原子时空过程拓扑关系，当需要表达整个时空过程拓扑关系时，可以通过时间区间联接操作来实现。图8展示了长时间区间时空过程拓扑关系的变化过程。

图7 复杂时空过程拓扑关系

地理实体A在整个过程中没有发生变化，而实体B却不断地发生变化：首先变大、再变小、最后又变大。在整个时间区间[t1，t4]内，二者之间的空间拓扑关系发生了三次变化：相离到邻接、相邻到相离和相离到部分覆盖，变化发生的时间区间分别为，[t1，t2]，[t2，t3]和[t3，t4]。为了符合原子时空过程拓扑关系时间联接表达时空过程拓扑关系的要求，将包含跨越相邻空间拓扑关系的时间区间[t3，t4]拆分成[t3，t3_m]和[t3_m，t4]，分别对应相离到部分覆盖拓扑关系变化的子过程，相离到相邻和相邻到部分覆盖。图8中时空过程拓扑关系离散成原子时空过程拓扑关系序列的操作过程，如图8所示。

图8 时空过程的原子时空过程拓扑关系拆分

显然，时间区间的前后顺序是很容易获得的，因此在进行原子时空过程拓扑关系联合后，就可以清晰地表达在指定时间区间内空间拓扑关系的变化过程。如图9所示，前一原子时空过程拓扑表达矩阵中的后拓扑关系与后一原子时空过程拓扑表达矩阵中的前拓扑关系是相同的，称此关系为连接拓扑关系。通过相同的连接拓扑关系，可以对有序的原子时空过程拓扑关系序列进行合并，来表达长时间区间时空过程之间的拓扑关系。例中时空过程拓扑关系变化过程为：相离→相邻→相离→相邻→部分覆盖。当然，还可以对这个变化过程进行抽象以获得更高层次上拓扑关系变化的趋势。

3 结束语

时空过程之间的拓扑关系是时态拓扑关系与空间拓扑关系变化过程的有机耦合，是进行时空推理、时空数据挖掘和时空分析的重要基础。论文主要完成以下几个方面的工作：1）对时空过程间空间拓扑关系的变化过程进行分析，确定了30基本空间拓扑关系变化过程，并给出相应的几何描述和组合矩阵表达；2）将30种基本空间拓扑过程与时态拓扑关系进行笛卡尔积耦合，构建了240种原子时空过程拓扑关系，并说明了相应的几何语义和矩阵表达模型；3）基于原子时空过程拓扑关系，给出了时空过程拓扑关系分解与表达的方法。基于原子时空过程拓扑的时空过程拓扑关系的表达，使得复杂的时空过程拓扑关系表达变得简单、直观和易操作，语义描述也更加符合人的认知习惯，能更好地解释时空过程，并且存储表达具有完备的数理基础，为时空过程知识挖掘和时空过程推理奠定了基础。

时空过程拓扑关系异常复杂，论文的讨论是假定原子时空过程拓扑关系的时间区间内没有出现地理实体本身消亡和新生，因此在建模中如何兼顾新生与消亡实体还有待于进一步的研究。

参考文献：

[1] Claramunt C， Jiang Bin. An integrated representation of spatial and temporal relationships between evolving regions. Journal of Geographical Systems， 2001：3411-429.

[2] Claramunt V， Jiang Bin. A representation of relationships in temporal spaces[M].Atkinson P， Martin .Innovations in GIS VII： Geocomputation. London： Taylor and Francis：41-45.

[3] 徐志红， 边馥苓. 地籍空间实体及其时空拓扑关系[J]. 武汉大学学报：信息科学版，2002，27（5）： 522-527

[4] 高勇， 张晶， 朱晓禧， 等. 移动对象时空拓扑关系模型[J].北京大学学报：自然科学版，2007，43（4） ： 468- 473.

[5] 薛存金， 苏奋振. 基于笛卡尔运算的时空拓扑关系研究[J].计算机工程与应用，2008，44（21）：20-24

[6] 沈敬伟， 温永宁， 闾国年，等. 时空拓扑关系描述及其推理研究[J].地理与地理信息科学， 2010，26（4）：1-5.

[7] 曾联斌， 宋迎春. 地理信息系统中时空拓扑关系计算表达[J].湖南大学学报：自然科学版，2010， 37（4）：85-89.

[8] Allen J F. Towards a general theory of action and time[J]. Artificial Intelligence， 1984， 23： 123-154.

[9] Egenhofer M J.A model for detailed binary topological relationships[J]. Geomatica， 1993， 47（3-4）： 261-273.

[10] 舒红， 陈军， 杜道生，等. 时空拓扑关系定义及时态拓扑关系描述[J]. 测绘学报，1997，26（4）：209-306

[11] Randell D A， Cui Z， Cohn A G. A spatial logic based on regions and connection[C]// Nebel B， Rich C， Swartout W R.Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning. San Francisco： Morgan Kaufmann Publishers， 1992：165-176.

[12] Grigni M， Papadias D， Papadimitriou C. Topological inference[C]//Mellish C S. Proceedings of the 14th International Joint Conference on Artificial Intelligence， Vol I. San Francisco： Morgan Kaufmann Publishers， 1995：901-906.