沈敬伟,温永宁,闾国年,吴明光,张红平

(南京师范大学虚拟地理环境教育部重点实验室,江苏南京 210046）

时空拓扑关系描述及其推理研究

沈敬伟,温永宁,闾国年,吴明光,张红平

(南京师范大学虚拟地理环境教育部重点实验室,江苏南京 210046）

空间目标处于一定的时间与空间中,时态拓扑关系和空间拓扑关系经常交织在一起,形成时空拓扑关系,因此有必要在统一框架下研究时空拓扑关系。基于A llen对时态拓扑关系和 Egenhofer对空间拓扑关系的研究,对时态拓扑关系和空间拓扑关系分别采用3×3的矩阵进行描述,将时空拓扑关系表示为3×6的矩阵,并描述了简单面/面之间的104种时空拓扑关系。在研究时态拓扑关系推理和空间拓扑关系推理的基础上,提出了一种时空拓扑关系推理方法。该文提出的时空拓扑关系描述和推理方法对于拓展时空拓扑关系的研究具有重要意义。

时空拓扑关系;时态拓扑关系;空间拓扑关系;描述;推理

0 引言

地理空间中的目标之间存在着各种与空间相关的关系,如前后、左右、东西南北、包含、相邻、相距等,也存在同时发生、在不同的时刻结束等时态拓扑关系。空间目标是时间与空间的统一体,其时态、空间以及时空拓扑关系描述及其推理是国内外研究的热点问题。

在时态拓扑关系研究方面:A llen对时态拓扑关系描述和推理进行了研究,归纳出13种时态关系,并用组合表的形式描述了13种时态拓扑关系的推理结果[1];舒红等提出并证明了完备、唯一的描述时态拓扑关系的4交集模型(4IM）框架[2];Bassiri等基于粗集理论,研究了时段之间的时态拓扑关系,定义了68种时态拓扑关系[3]。在空间拓扑关系研究方面:点集拓扑法、区域连接演算法、符号投影法(2D String）、外接矩形法和广义交模型描述法等用于拓扑关系描述[4-7];基于谓词逻辑的推理、组合表推理、基于产生式的推理、基于代数的推理、基于语意网络的推理和分层逼近法等用于拓扑关系推理[8-10];Egenhofer基于点集拓扑理论,研究了基于面与面之间的8种基本拓扑关系在概念层次上的推理,使用组合表给出了64种可能的推理结果[11]。在时空拓扑关系研究方面:Claramunt等对统一框架体系下的时空拓扑关系进行了描述和分析[12,13];Hallot等提出了退化拓扑关系的概念,并对点对象之间的时空拓扑关系进行研究[14];高勇等针对二维欧氏空间内的平面移动对象,建立基于时间片的时空数据模型,并在9 IM的基础上,定义移动对象时空拓扑关系的定性模型[15];薛存金等提出基于笛卡尔运算的时空框架集成体系,归纳出64种联合完备且互不相交的时空拓扑关系[16],并引入 Rough集理论的上、下近似集概念对不确定性对象进行表达,研究了不确定性对象的时空拓扑关系[17];曾联斌等针对时空对象,建立了基于时段时空数据模型,根据9IM以及基于时段的时间表示方法,定义了时空对象时空拓扑关系模型[18]。

值得指出的是,虽然时态、拓扑及时空拓扑关系的研究取得了很大进展,但时空拓扑关系推理方面的研究比较滞后。时空拓扑关系描述是时空拓扑推理的基础,故对时空拓扑关系描述和推理进行研究。

1 时空拓扑关系描述

1.1 时态拓扑关系描述

牛顿时空观认为:绝对、真实的数学时间,就其自身及其本质而言,是永远均匀地流动的,不依赖于任何外界事物。时间是连续的,可用一个向过去和未来无限扩展的一维坐标轴表示。为了描述时态拓扑关系,本文给出了时间轴上几个概念的基本定义。

定义1 时刻:时间轴上的每个点表示一个时刻,它没有长短,只有先后,是一个序数,用 ti(i=1, 2,3,…,n）表示。

定义2 时间段:时间轴上的一段时间表示一个时间段,时间段可以表示为 T=[ts,te],ts和te分别表示时间段的开始时刻和结束时刻,且 ts＜te。

定义3 时间段前部、后部、内部:时间轴上的时间段 T=[ts,te]是一个闭区间,T-=(-,ts]表示时间段 T的前部,T+=[te,+）表示时间段 T的后部, To=(ts,te）表示时间段 T的内部。

时态拓扑关系可用3×3的矩阵表达,即通过比较两个时间段的前部、内部和后部的相交关系,对时态拓扑关系进行形式化表达。设有两个时间段 TX[Xs,Xe]和 TY[Ys,Ye],X-、Xo、X+、Y-、Yo和 Y+分别表示 TX和 TY的时间段前部、内部和后部。公式(1）给出时间段 TX和 TY之间的时态拓扑关系的矩阵表达形式,该式也可用长度为9的字符串表示,字符串的顺序按照矩阵中行优先的顺序排列,表达式为(X-∩Y-,X-∩Yo,X-∩Y+,Xo∩Y-,Xo∩Yo,Xo∩Y+,X+∩Y-,X+∩Yo,X+∩Y+）,TR中元素的取值可以为{0,1},分别表示{空集,非空集}。

A llen基于时间段逻辑模型,区分了13种互不相交且联合完备(Jointly Exhaustive and Pairw ise Disjoint,JEPD）的时态拓扑关系,分别是{equal,before,meets,overlaps,during,starts,finishes,after, met,overlapped,contain,started,finished}。表1给出了A llen描述的13种拓扑关系的3×3矩阵的字符串表现形式。

1.2 空间拓扑关系描述

拓扑关系描述的主要目的是建立空间目标与所对应的拓扑关系之间的映射。不同的拓扑关系可以采用不同的方法,但映射的结果必须与认知的概念相一致,还需要考虑拓扑关系的推理等特性。Randell等通过区域连接演算(RCC）理论描述空间目标之间的拓扑关系[5];Egenhofer等基于点集拓扑理论[4],先后提出4IM、9 IM模型描述简单空间目标拓扑关系,其中9IM通过描述空间目标的内部、边界和外部表达空间目标之间的拓扑关系。无论是RCC理论,还是交集模型,都区分8种符合人类认知的简单面/面之间的拓扑关系。为了将空间拓扑关系描述与时态拓扑描述统一到一个框架下,采用9IM描述简单面/面之间的拓扑关系。

如果空间目标A和B的内部、边界和外部分别用Ao、∂A、A-和Bo、∂B、B-表示,则9IM的表现形式如公式(2）所示,其中元素的取值可以为{0,1},分别表示{空集,非空集}。简单面/面之间存在8种有意义的拓扑关系:{Disjoint,M eet,Overlaps,Covers, Contains,Equal,CoveredBy,Inside}。图 1描述了简单面/面之间的8种拓扑关系,并给出了相应的9IM矩阵。

1.3 时空拓扑关系描述

时态拓扑关系是建立在时间维上,从空间目标生存时间的角度考察拓扑关系,并未考虑空间目标在空间位置上的关系;而空间拓扑关系则在空间维上定义,是从空间目标的空间位置出发,并未考虑空间目标在生存时间上的拓扑关系。空间目标存在于一定时间与空间中,研究空间目标之间的时空拓扑关系要综合考虑时间和空间两个因素。任意两个空间目标之间的时空拓扑关系是由时间维上的时态拓扑和空间维上的空间拓扑联合组成,即不但要考虑时态拓扑关系,还要考虑其与空间拓扑关系相互作用的因素,因此,需要将时态拓扑和空间拓扑联合考虑。通过对时态和空间拓扑关系的研究,进一步提出时空拓扑关系的集成表达方法。

由于时态拓扑关系和空间拓扑关系分别采用3 ×3的矩阵描述,空间目标之间时空拓扑关系的联合矩阵表达框架可表示为:

在公式(3）中,元素的取值可以为{0,1},分别表示{空集,非空集};左半部分3×3的矩阵表示时态拓扑关系,右半部分3×3的矩阵表示空间拓扑关系。时态和空间拓扑关系均采用3×3的矩阵表达,理论上分别能够区分29=512种时态和空间拓扑关系。因为存在13种有实际意义的时态拓扑关系和8种简单面/面之间的空间拓扑关系,共能表达13×8 =104种简单面/面之间的时空拓扑关系(表2）。

表2中灰色表示空间目标A,白色表示空间目标B;每一项的横向表示面/面之间时态拓扑关系的描述,纵向表示空间拓扑关系的描述。表2描述了在不同的时态拓扑关系和空间拓扑关系情况下所有的104种时空拓扑关系。为了便于在时空拓扑关系推理中表达时空拓扑关系,对表2中的时空拓扑关系进行编号,并按照行优先的顺序编号,表中各项的时空拓扑关系的编号为:1,2,3,…,103,104。

2 时空拓扑关系推理

2.1 时态拓扑关系推理

人类对各种事物进行分析、综合并最后决策的过程中,通常从掌握的已知事实出发,运用事物之间的相互关系(如因果关系等）,找出其中蕴含的更多的事实,这个过程通常被称为推理[7]。对于给定前提的时间段 X TRY和YTRZ时态拓扑关系,希望得到 X TRZ的时态拓扑关系。拓扑关系推理通常用组合表来表示,组合表是采用二维表格存储所有可能的推理结果的一种规则表示形式,它实质上是一种基于框架的知识表示,用二维表的数据结构实现。时间段之间有13种拓扑关系,它的推理组合表是一张13×13的表,表中的每一项分别表示不同组合所能推理到的可能的时态拓扑关系。A llen给出了时态拓扑关系组合推理表[1](表3）。

对于已知的时间段 X TRY和 YTRZ时态拓扑关系,通过表3可以得到 X TRZ的时态拓扑关系推理结果。若时间段 X和Y间的时态拓扑关系为before,而Y和Z间的时态拓扑关系为meets,则A和C间时态拓扑关系为befo re。通过时态拓扑关系推理表,能够推理出可能的时态拓扑关系。

表3 时态拓扑关系推理Table 3 Reasoning of temporal topological relationships

2.2 空间拓扑关系推理

空间拓扑关系推理是利用已知的空间目标之间拓扑关系,推理得到未知的拓扑关系或排除不可能的拓扑关系,从而获取空间目标之间的拓扑关系。即根据空间目标A和B及B和C间已知的拓扑关系,推理空间目标A和C间的拓扑关系。简单面/面之间有8种基本拓扑关系,它的推理组合表是一张8×8的表,表中的每一项分别表示不同组合所能推理到的可能的拓扑关系。基于集合包含关系的传递性,Egenhofer给出简单面/面之间推理组合表[11](表4）。

表4 简单面/面之间空间拓扑关系推理Table 4 Reasoning of spatial topological relationships between regions

2.3 时空拓扑关系推理

时空拓扑关系推理是指对占据空间并随时间变化的空间目标之间的拓扑关系进行的推理,它从时态拓扑关系推理和空间拓扑关系推理发展而来[19]。本文提出了一种结合时态拓扑关系推理和空间拓扑关系推理,研究时空拓扑关系推理的方法,即判断时态拓扑关系推理产生的结果 TO和空间拓扑关系推理产生的结果SO,从而得到时空拓扑关系推理的结果 TSO:

二维简单面/面之间存在104种时空拓扑关系,如果用拓扑推理表表达,则它的推理组合表是一张104×104的表,表中的每一项分别表示不同组合所能推理到的时空拓扑关系。限于篇幅,本文针对给定的时空情况,根据表3和表4推理出时空拓扑关系。

如果存在3个时空对象 TSA、TSB和 TSC:如果 TSA和 TSB时态拓扑关系为 meets,TSB和TSC时态拓扑关系为finished,则根据表 3可知, TSA和 TSC的时态拓扑关系为{during,starts,overlaps};如果 TSA和 TSB空间拓扑关系为Contains,TSB和 TSC空间拓扑关系为Overlap s,则根据表4可知,TSA和 TSC的空间拓扑关系为{Contains,Covers,Overlaps};由时态拓扑关系推理和空间拓扑关系推理可以得到时空拓扑关系:{(during-Contains）,(during-Covers）,(during-Overlaps）,(starts-Contains）,(starts-Covers）,(starts-Overlap s）,(overlaps-Contains）,(overlaps-Covers）,(overlaps-O-verlap s）},对应的时态拓扑关系编号分别是{22,23, 24,70,71,72,38,39,40}。以上通过推理得出的时态拓扑关系能够用公式(3）所表示的统一框架表达。

3 结语

时空拓扑关系描述和推理是地理信息系统、人工智能以及时空数据库等相关领域的研究热点。本文在对时态拓扑关系和空间拓扑关系统一采用9IM表达的基础上,提出一种新的时空拓扑关系描述框架,能够有效地描述时空拓扑关系;并结合时态拓扑关系推理和空间拓扑关系推理,进行时空拓扑关系推理,提出了一种时空拓扑关系推理的解决思路。本文提出的时空拓扑关系描述和推理方法,不仅适用于面/面时空拓扑关系,也能够用于线/线、线/面和体/体等时空拓扑关系描述和推理,具有普适性。

[1] ALLEN J.Maintaining know ledge about temporal intervals[J]. Communications of the ACM,1983,26(11）:832-843.

[2] 舒红,陈军,杜道生,等.时空拓扑关系定义及时态拓扑关系描述[J].测绘学报,1997,26(4）:299-306.

[3] BASSIRIA,MALEKM,ALESHEIKH A,et al.Temporal relationships between rough time intervals[A].Computational Science and Its Applications,ICCSA 2009[C].2009.543-552.

[4] EGENHOFER M,FRANZOSA R D.Point-set topological spatial relations[J].Geographical Information Systems,1991,5 (2）:161-174.

[5] RANDELL D,CU I Z,COHN A.A spatial logic based on regions and connectio[A].Proceedings of the 3rd International Conferenceon Principlesof Know ledge Rep resentation and Reasoning[C].San Francisco,1992.165-176.

[6] CHANG S,SHIQ,YAN C.Iconic indexing by 2-D strings[J]. IEEE Trans.Pattern Anal.Mach.Intellig lig.,1987,9(3）:413 -428.

[7] 刘瑜,龚咏喜,张晶,等.地理空间中的空间关系表达和推理[J].地理与地理信息科学,2007,23(5）:1-7.

[8] 郭庆胜,杜晓初,闫卫阳.地理空间推理[J].北京:科学出版社, 2006.69-86.

[9] 刘新.三维空间关系的描述及其定性推理[J].青岛:山东科技大学,2007.14-27.

[10] COHN A,RENZJ.Qualitative spatial reasoning[A].Handbook of Know ledge Rep resentation[C].Elsevier,2007.5-43.

[11] EGENHOFER M J.Deriving the composition of binary topological relations[J].Visual Languages and Computing,1994,5 (2）:133-149.

[12] CLARAMUN T C,JIANGB.A rep resentation of relationships in tempo ral spaces[J].GIS and Geocomputation,2000(41）:1 -13.

[13] CLARAMUN T C,JIANG B.An integrated rep resentation of spatial and temporal relationships between evolving regions [J].Geographical System s,2001,3(4）:411-428.

[14] HALLOT P,BILLEN R.Spatio-temporal configurationsof dynamics points in a 1D space[A].Behaviour Monitoring and Interp retation BM I[C].2007.77-90.

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

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

[17] 薛存金,苏奋振.不确定性对象表达及其时空拓扑研究[J].地球信息科学学报,2009,11(4）:475-481.

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

[19] 刘大有,胡鹤,王生生,等.时空推理研究进展[J].软件学报, 2004,15(8）:1141-1149.

Representation and Reason ing about Spatial-Temporal Topological Relationships

SHEN Jing-wei,WEN Yong-ning,LV Guo-nian,WU Ming-guang,ZHANG Hong-ping
(Key Laboratory of Virtual Geographic Environment(M inistry of Education）,Nanjing Normal University,Nanjing 210046,China）

Spatial object is the unit of space and time.Spatial-temporal topological relationship is composed of tempo ral topological relationship in time dimension and spatial topological relationship in spatial dimension.It is essential to study on spatial-temporal topological relationships in a unified framework.On the analysisof A llen′s13 temporal topological relationships and Egenhofer′s 8 spatial relationshipson regions,the integration framework fo r spatial-tempo ral topological relationships is p roposed.In this paper,temporal topological relationshipsand spatial topological relationshipsare rep resented by 3×3 matrix respectively,so the authors p roposed to use 3×6 matrix to depict spatial-temporal topological relationships.Asmany as 13×8=104 kinds of spatial-tempo ral topological relationships are illustrated.On the analysisof temporal topological relationshipsand spatial topological relationships reasoning,a spatial-temporal topological relationships reasoning method is p roposed.Spatial-tempo ral topological relationships rep resentation and reasoning method can be contributed to the research of spatial-temporal topological relationships.

spatial-temporal topological relationships;temporal topological relationships;spatial topological relationships;rep resentation;reasoning

P208

A

1672-0504(2010）06-0001-05

2010-09-08;

2010-10-25

国家自然科学基金“基于庞加莱对偶的三维自由拓扑模型”(40901186）;国家自然科学基金“面向地理问题求解的分布式地理建模环境研究”(40730527）

沈敬伟(1984-）,男,博士研究生,主要研究方向为虚拟地理环境、3D GIS。E-mail:jingweigis@163.com