時空拓撲關系描述及其推理研究

沈敬偉,溫永寧,閭國年,吳明光,張紅平

(南京師范大學虛擬地理環(huán)境教育部重點實驗室,江蘇南京 210046）

時空拓撲關系描述及其推理研究

沈敬偉,溫永寧,閭國年,吳明光,張紅平

(南京師范大學虛擬地理環(huán)境教育部重點實驗室,江蘇南京 210046）

空間目標處于一定的時間與空間中,時態(tài)拓撲關系和空間拓撲關系經(jīng)常交織在一起,形成時空拓撲關系,因此有必要在統(tǒng)一框架下研究時空拓撲關系?；贏 llen對時態(tài)拓撲關系和 Egenhofer對空間拓撲關系的研究,對時態(tài)拓撲關系和空間拓撲關系分別采用3×3的矩陣進行描述,將時空拓撲關系表示為3×6的矩陣,并描述了簡單面/面之間的104種時空拓撲關系。在研究時態(tài)拓撲關系推理和空間拓撲關系推理的基礎上,提出了一種時空拓撲關系推理方法。該文提出的時空拓撲關系描述和推理方法對于拓展時空拓撲關系的研究具有重要意義。

時空拓撲關系;時態(tài)拓撲關系;空間拓撲關系;描述;推理

0 引言

地理空間中的目標之間存在著各種與空間相關的關系,如前后、左右、東西南北、包含、相鄰、相距等,也存在同時發(fā)生、在不同的時刻結束等時態(tài)拓撲關系。空間目標是時間與空間的統(tǒng)一體,其時態(tài)、空間以及時空拓撲關系描述及其推理是國內(nèi)外研究的熱點問題。

在時態(tài)拓撲關系研究方面:A llen對時態(tài)拓撲關系描述和推理進行了研究,歸納出13種時態(tài)關系,并用組合表的形式描述了13種時態(tài)拓撲關系的推理結果[1];舒紅等提出并證明了完備、唯一的描述時態(tài)拓撲關系的4交集模型(4IM）框架[2];Bassiri等基于粗集理論,研究了時段之間的時態(tài)拓撲關系,定義了68種時態(tài)拓撲關系[3]。在空間拓撲關系研究方面:點集拓撲法、區(qū)域連接演算法、符號投影法(2D String）、外接矩形法和廣義交模型描述法等用于拓撲關系描述[4-7];基于謂詞邏輯的推理、組合表推理、基于產(chǎn)生式的推理、基于代數(shù)的推理、基于語意網(wǎng)絡的推理和分層逼近法等用于拓撲關系推理[8-10];Egenhofer基于點集拓撲理論,研究了基于面與面之間的8種基本拓撲關系在概念層次上的推理,使用組合表給出了64種可能的推理結果[11]。在時空拓撲關系研究方面:Claramunt等對統(tǒng)一框架體系下的時空拓撲關系進行了描述和分析[12,13];Hallot等提出了退化拓撲關系的概念,并對點對象之間的時空拓撲關系進行研究[14];高勇等針對二維歐氏空間內(nèi)的平面移動對象,建立基于時間片的時空數(shù)據(jù)模型,并在9 IM的基礎上,定義移動對象時空拓撲關系的定性模型[15];薛存金等提出基于笛卡爾運算的時空框架集成體系,歸納出64種聯(lián)合完備且互不相交的時空拓撲關系[16],并引入 Rough集理論的上、下近似集概念對不確定性對象進行表達,研究了不確定性對象的時空拓撲關系[17];曾聯(lián)斌等針對時空對象,建立了基于時段時空數(shù)據(jù)模型,根據(jù)9IM以及基于時段的時間表示方法,定義了時空對象時空拓撲關系模型[18]。

值得指出的是,雖然時態(tài)、拓撲及時空拓撲關系的研究取得了很大進展,但時空拓撲關系推理方面的研究比較滯后。時空拓撲關系描述是時空拓撲推理的基礎,故對時空拓撲關系描述和推理進行研究。

1 時空拓撲關系描述

1.1 時態(tài)拓撲關系描述

牛頓時空觀認為:絕對、真實的數(shù)學時間,就其自身及其本質(zhì)而言,是永遠均勻地流動的,不依賴于任何外界事物。時間是連續(xù)的,可用一個向過去和未來無限擴展的一維坐標軸表示。為了描述時態(tài)拓撲關系,本文給出了時間軸上幾個概念的基本定義。

定義1 時刻:時間軸上的每個點表示一個時刻,它沒有長短,只有先后,是一個序數(shù),用 ti(i=1, 2,3,…,n）表示。

定義2 時間段:時間軸上的一段時間表示一個時間段,時間段可以表示為 T=[ts,te],ts和te分別表示時間段的開始時刻和結束時刻,且 ts＜te。

定義3 時間段前部、后部、內(nèi)部:時間軸上的時間段 T=[ts,te]是一個閉區(qū)間,T-=(-,ts]表示時間段 T的前部,T+=[te,+）表示時間段 T的后部, To=(ts,te）表示時間段 T的內(nèi)部。

時態(tài)拓撲關系可用3×3的矩陣表達,即通過比較兩個時間段的前部、內(nèi)部和后部的相交關系,對時態(tài)拓撲關系進行形式化表達。設有兩個時間段 TX[Xs,Xe]和 TY[Ys,Ye],X-、Xo、X+、Y-、Yo和 Y+分別表示 TX和 TY的時間段前部、內(nèi)部和后部。公式(1）給出時間段 TX和 TY之間的時態(tài)拓撲關系的矩陣表達形式,該式也可用長度為9的字符串表示,字符串的順序按照矩陣中行優(yōu)先的順序排列,表達式為(X-∩Y-,X-∩Yo,X-∩Y+,Xo∩Y-,Xo∩Yo,Xo∩Y+,X+∩Y-,X+∩Yo,X+∩Y+）,TR中元素的取值可以為{0,1},分別表示{空集,非空集}。

A llen基于時間段邏輯模型,區(qū)分了13種互不相交且聯(lián)合完備(Jointly Exhaustive and Pairw ise Disjoint,JEPD）的時態(tài)拓撲關系,分別是{equal,before,meets,overlaps,during,starts,finishes,after, met,overlapped,contain,started,finished}。表1給出了A llen描述的13種拓撲關系的3×3矩陣的字符串表現(xiàn)形式。

1.2 空間拓撲關系描述

拓撲關系描述的主要目的是建立空間目標與所對應的拓撲關系之間的映射。不同的拓撲關系可以采用不同的方法,但映射的結果必須與認知的概念相一致,還需要考慮拓撲關系的推理等特性。Randell等通過區(qū)域連接演算(RCC）理論描述空間目標之間的拓撲關系[5];Egenhofer等基于點集拓撲理論[4],先后提出4IM、9 IM模型描述簡單空間目標拓撲關系,其中9IM通過描述空間目標的內(nèi)部、邊界和外部表達空間目標之間的拓撲關系。無論是RCC理論,還是交集模型,都區(qū)分8種符合人類認知的簡單面/面之間的拓撲關系。為了將空間拓撲關系描述與時態(tài)拓撲描述統(tǒng)一到一個框架下,采用9IM描述簡單面/面之間的拓撲關系。

如果空間目標A和B的內(nèi)部、邊界和外部分別用Ao、?A、A-和Bo、?B、B-表示,則9IM的表現(xiàn)形式如公式(2）所示,其中元素的取值可以為{0,1},分別表示{空集,非空集}。簡單面/面之間存在8種有意義的拓撲關系:{Disjoint,M eet,Overlaps,Covers, Contains,Equal,CoveredBy,Inside}。圖 1描述了簡單面/面之間的8種拓撲關系,并給出了相應的9IM矩陣。

1.3 時空拓撲關系描述

時態(tài)拓撲關系是建立在時間維上,從空間目標生存時間的角度考察拓撲關系,并未考慮空間目標在空間位置上的關系;而空間拓撲關系則在空間維上定義,是從空間目標的空間位置出發(fā),并未考慮空間目標在生存時間上的拓撲關系?？臻g目標存在于一定時間與空間中,研究空間目標之間的時空拓撲關系要綜合考慮時間和空間兩個因素。任意兩個空間目標之間的時空拓撲關系是由時間維上的時態(tài)拓撲和空間維上的空間拓撲聯(lián)合組成,即不但要考慮時態(tài)拓撲關系,還要考慮其與空間拓撲關系相互作用的因素,因此,需要將時態(tài)拓撲和空間拓撲聯(lián)合考慮。通過對時態(tài)和空間拓撲關系的研究,進一步提出時空拓撲關系的集成表達方法。

由于時態(tài)拓撲關系和空間拓撲關系分別采用3 ×3的矩陣描述,空間目標之間時空拓撲關系的聯(lián)合矩陣表達框架可表示為:

在公式(3）中,元素的取值可以為{0,1},分別表示{空集,非空集};左半部分3×3的矩陣表示時態(tài)拓撲關系,右半部分3×3的矩陣表示空間拓撲關系。時態(tài)和空間拓撲關系均采用3×3的矩陣表達,理論上分別能夠區(qū)分29=512種時態(tài)和空間拓撲關系。因為存在13種有實際意義的時態(tài)拓撲關系和8種簡單面/面之間的空間拓撲關系,共能表達13×8 =104種簡單面/面之間的時空拓撲關系(表2）。

表2中灰色表示空間目標A,白色表示空間目標B;每一項的橫向表示面/面之間時態(tài)拓撲關系的描述,縱向表示空間拓撲關系的描述。表2描述了在不同的時態(tài)拓撲關系和空間拓撲關系情況下所有的104種時空拓撲關系。為了便于在時空拓撲關系推理中表達時空拓撲關系,對表2中的時空拓撲關系進行編號,并按照行優(yōu)先的順序編號,表中各項的時空拓撲關系的編號為:1,2,3,…,103,104。

2 時空拓撲關系推理

2.1 時態(tài)拓撲關系推理

人類對各種事物進行分析、綜合并最后決策的過程中,通常從掌握的已知事實出發(fā),運用事物之間的相互關系(如因果關系等）,找出其中蘊含的更多的事實,這個過程通常被稱為推理[7]。對于給定前提的時間段 X TRY和YTRZ時態(tài)拓撲關系,希望得到 X TRZ的時態(tài)拓撲關系。拓撲關系推理通常用組合表來表示,組合表是采用二維表格存儲所有可能的推理結果的一種規(guī)則表示形式,它實質(zhì)上是一種基于框架的知識表示,用二維表的數(shù)據(jù)結構實現(xiàn)。時間段之間有13種拓撲關系,它的推理組合表是一張13×13的表,表中的每一項分別表示不同組合所能推理到的可能的時態(tài)拓撲關系。A llen給出了時態(tài)拓撲關系組合推理表[1](表3）。

對于已知的時間段 X TRY和 YTRZ時態(tài)拓撲關系,通過表3可以得到 X TRZ的時態(tài)拓撲關系推理結果。若時間段 X和Y間的時態(tài)拓撲關系為before,而Y和Z間的時態(tài)拓撲關系為meets,則A和C間時態(tài)拓撲關系為befo re。通過時態(tài)拓撲關系推理表,能夠推理出可能的時態(tài)拓撲關系。

表3 時態(tài)拓撲關系推理Table 3 Reasoning of temporal topological relationships

2.2 空間拓撲關系推理

空間拓撲關系推理是利用已知的空間目標之間拓撲關系,推理得到未知的拓撲關系或排除不可能的拓撲關系,從而獲取空間目標之間的拓撲關系。即根據(jù)空間目標A和B及B和C間已知的拓撲關系,推理空間目標A和C間的拓撲關系。簡單面/面之間有8種基本拓撲關系,它的推理組合表是一張8×8的表,表中的每一項分別表示不同組合所能推理到的可能的拓撲關系?；诩习P系的傳遞性,Egenhofer給出簡單面/面之間推理組合表[11](表4）。

表4 簡單面/面之間空間拓撲關系推理Table 4 Reasoning of spatial topological relationships between regions

2.3 時空拓撲關系推理

時空拓撲關系推理是指對占據(jù)空間并隨時間變化的空間目標之間的拓撲關系進行的推理,它從時態(tài)拓撲關系推理和空間拓撲關系推理發(fā)展而來[19]。本文提出了一種結合時態(tài)拓撲關系推理和空間拓撲關系推理,研究時空拓撲關系推理的方法,即判斷時態(tài)拓撲關系推理產(chǎn)生的結果 TO和空間拓撲關系推理產(chǎn)生的結果SO,從而得到時空拓撲關系推理的結果 TSO:

二維簡單面/面之間存在104種時空拓撲關系,如果用拓撲推理表表達,則它的推理組合表是一張104×104的表,表中的每一項分別表示不同組合所能推理到的時空拓撲關系。限于篇幅,本文針對給定的時空情況,根據(jù)表3和表4推理出時空拓撲關系。

如果存在3個時空對象 TSA、TSB和 TSC:如果 TSA和 TSB時態(tài)拓撲關系為 meets,TSB和TSC時態(tài)拓撲關系為finished,則根據(jù)表 3可知, TSA和 TSC的時態(tài)拓撲關系為{during,starts,overlaps};如果 TSA和 TSB空間拓撲關系為Contains,TSB和 TSC空間拓撲關系為Overlap s,則根據(jù)表4可知,TSA和 TSC的空間拓撲關系為{Contains,Covers,Overlaps};由時態(tài)拓撲關系推理和空間拓撲關系推理可以得到時空拓撲關系:{(during-Contains）,(during-Covers）,(during-Overlaps）,(starts-Contains）,(starts-Covers）,(starts-Overlap s）,(overlaps-Contains）,(overlaps-Covers）,(overlaps-O-verlap s）},對應的時態(tài)拓撲關系編號分別是{22,23, 24,70,71,72,38,39,40}。以上通過推理得出的時態(tài)拓撲關系能夠用公式(3）所表示的統(tǒng)一框架表達。

3 結語

時空拓撲關系描述和推理是地理信息系統(tǒng)、人工智能以及時空數(shù)據(jù)庫等相關領域的研究熱點。本文在對時態(tài)拓撲關系和空間拓撲關系統(tǒng)一采用9IM表達的基礎上,提出一種新的時空拓撲關系描述框架,能夠有效地描述時空拓撲關系;并結合時態(tài)拓撲關系推理和空間拓撲關系推理,進行時空拓撲關系推理,提出了一種時空拓撲關系推理的解決思路。本文提出的時空拓撲關系描述和推理方法,不僅適用于面/面時空拓撲關系,也能夠用于線/線、線/面和體/體等時空拓撲關系描述和推理,具有普適性。

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

[2] 舒紅,陳軍,杜道生,等.時空拓撲關系定義及時態(tài)拓撲關系描述[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] 郭慶勝,杜曉初,閆衛(wèi)陽.地理空間推理[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] 曾聯(lián)斌,宋迎春.地理信息系統(tǒng)中時空拓撲關系計算表達[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）;國家自然科學基金“面向地理問題求解的分布式地理建模環(huán)境研究”(40730527）

沈敬偉(1984-）,男,博士研究生,主要研究方向為虛擬地理環(huán)境、3D GIS。E-mail:jingweigis@163.com