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

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

時空拓?fù)潢P(guān)系描述及其推理研究

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

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

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

時空拓?fù)潢P(guān)系;時態(tài)拓?fù)潢P(guān)系;空間拓?fù)潢P(guān)系;描述;推理

0 引言

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

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

值得指出的是,雖然時態(tài)、拓?fù)浼皶r空拓?fù)潢P(guān)系的研究取得了很大進(jìn)展,但時空拓?fù)潢P(guān)系推理方面的研究比較滯后。時空拓?fù)潢P(guān)系描述是時空拓?fù)渫评淼幕A(chǔ),故對時空拓?fù)潢P(guān)系描述和推理進(jìn)行研究。

1 時空拓?fù)潢P(guān)系描述

1.1 時態(tài)拓?fù)潢P(guān)系描述

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

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

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

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

時態(tài)拓?fù)潢P(guān)系可用3×3的矩陣表達(dá),即通過比較兩個時間段的前部、內(nèi)部和后部的相交關(guān)系,對時態(tài)拓?fù)潢P(guān)系進(jìn)行形式化表達(dá)。設(shè)有兩個時間段 TX[Xs,Xe]和 TY[Ys,Ye],X-、Xo、X+、Y-、Yo和 Y+分別表示 TX和 TY的時間段前部、內(nèi)部和后部。公式(1）給出時間段 TX和 TY之間的時態(tài)拓?fù)潢P(guān)系的矩陣表達(dá)形式,該式也可用長度為9的字符串表示,字符串的順序按照矩陣中行優(yōu)先的順序排列,表達(dá)式為(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)拓?fù)潢P(guān)系,分別是{equal,before,meets,overlaps,during,starts,finishes,after, met,overlapped,contain,started,finished}。表1給出了A llen描述的13種拓?fù)潢P(guān)系的3×3矩陣的字符串表現(xiàn)形式。

1.2 空間拓?fù)潢P(guān)系描述

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

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

1.3 時空拓?fù)潢P(guān)系描述

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

由于時態(tài)拓?fù)潢P(guān)系和空間拓?fù)潢P(guān)系分別采用3 ×3的矩陣描述,空間目標(biāo)之間時空拓?fù)潢P(guān)系的聯(lián)合矩陣表達(dá)框架可表示為:

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

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

2 時空拓?fù)潢P(guān)系推理

2.1 時態(tài)拓?fù)潢P(guān)系推理

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

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

表3 時態(tài)拓?fù)潢P(guān)系推理Table 3 Reasoning of temporal topological relationships

2.2 空間拓?fù)潢P(guān)系推理

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

表4 簡單面/面之間空間拓?fù)潢P(guān)系推理Table 4 Reasoning of spatial topological relationships between regions

2.3 時空拓?fù)潢P(guān)系推理

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

二維簡單面/面之間存在104種時空拓?fù)潢P(guān)系,如果用拓?fù)渫评肀肀磉_(dá),則它的推理組合表是一張104×104的表,表中的每一項分別表示不同組合所能推理到的時空拓?fù)潢P(guān)系。限于篇幅,本文針對給定的時空情況,根據(jù)表3和表4推理出時空拓?fù)潢P(guān)系。

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

3 結(jié)語

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

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

[2] 舒紅,陳軍,杜道生,等.時空拓?fù)潢P(guān)系定義及時態(tài)拓?fù)潢P(guān)系描述[J].測繪學(xué)報,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] 劉瑜,龔詠喜,張晶,等.地理空間中的空間關(guān)系表達(dá)和推理[J].地理與地理信息科學(xué),2007,23(5）:1-7.

[8] 郭慶勝,杜曉初,閆衛(wèi)陽.地理空間推理[J].北京:科學(xué)出版社, 2006.69-86.

[9] 劉新.三維空間關(guān)系的描述及其定性推理[J].青島:山東科技大學(xué),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] 高勇,張晶,朱曉禧,等.移動對象時空拓?fù)潢P(guān)系模型[J].北京大學(xué)學(xué)報(自然科學(xué)版）,2007,43(4）:468-473

[16] 薛存金,蘇奮振.基于笛卡爾運算的時空拓?fù)潢P(guān)系研究[J].計算機(jī)工程與應(yīng)用,2008,44(21）:20-24.

[17] 薛存金,蘇奮振.不確定性對象表達(dá)及其時空拓?fù)溲芯縖J].地球信息科學(xué)學(xué)報,2009,11(4）:475-481.

[18] 曾聯(lián)斌,宋迎春.地理信息系統(tǒng)中時空拓?fù)潢P(guān)系計算表達(dá)[J].湖南大學(xué)學(xué)報(自然科學(xué)版）,2010,37(4）:85-89.

[19] 劉大有,胡鶴,王生生,等.時空推理研究進(jìn)展[J].軟件學(xué)報, 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

國家自然科學(xué)基金“基于龐加萊對偶的三維自由拓?fù)淠Ｐ汀?40901186）;國家自然科學(xué)基金“面向地理問題求解的分布式地理建模環(huán)境研究”(40730527）

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