時空過程拓撲關系表達

張雪伍

摘要：利用前后兩個空間拓撲關系的組合來表達原子空間拓撲關系變化過程，從而將空過程之間復雜的空拓撲關系變化過程，分解成30種基元空間拓撲關系變化過程。利用4交模型將時態(tài)拓撲關系與空間拓撲關系過程基元進行笛卡兒積耦合，形成240種原子時空過程拓撲關系，并對其幾何表達和語義進行詳細的說明。最后，論文給出了利用原子時空過程拓撲關系進行時空過程拓撲關系表達方法進行說明，并給出了時間區(qū)間重合的多態(tài)時空過程拓撲關系表達鑒別策略。

關鍵詞： 時空數(shù)據(jù)挖掘；時空過程；時空過程拓撲；時空耦合

中圖分類號：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

時空過程是地理實體在指定時間區(qū)間內的發(fā)展演化過程，是時間與空間的有機統(tǒng)一整體，其間的拓撲關系是時間拓撲關系與空間拓撲序列的有機偶合體?？臻g拓撲和時態(tài)拓撲分別從空間和時間的角度獨立地表達拓撲關系，機械地離散了具有密切聯(lián)系的時空對象時間與空間的聯(lián)系，不能表達時空過程之間的動態(tài)拓撲關系。因此，很多學者開始嘗試將時間和空間納入一個統(tǒng)一的框架內，探索時空拓撲關系的表達。Christophe等基于時間與空間的等同性歸納出了56種時空關系，但其沒有區(qū)分時態(tài)方向與時態(tài)拓撲關系，也沒有進一步探討時空拓撲操作的實現(xiàn)[1-2]。徐志紅等基于地籍實體空間靜態(tài)空間關系，采用地籍實體變更事件驅動地籍實體及其拓撲關系的變更[3]。高勇等基于時間片時空數(shù)據(jù)模型和9交模型的建模思想針對二維歐式空間內的平面移動對象，構建了移動對象的時空拓撲關系定性表達模型[4]。還有部分學者利用空間拓撲與時態(tài)拓撲關系的笛卡爾積來表達時空拓撲關系，并利用耦合矩陣對時空拓撲進行描述[5-6]。曾聯(lián)斌等在時段時空數(shù)據(jù)模型的基礎上，利用9交模型定義了基于時段的時空對象時空拓撲關系模型[7]。以上研究，將空間拓撲和時態(tài)拓撲進行耦合來表達時空拓撲，是時空過程拓撲的一種特例，并沒有體現(xiàn)空間拓撲關系在時間區(qū)間的變化過程。

鑒于此，本文旨在統(tǒng)一的時空框架下，將基于時空過程原子實體來探討時空過程之間的拓撲關系，為進一步的時空過程推理、分析和時空數(shù)據(jù)挖掘提供理論基礎。因此，將時間與空間進行正交組合構建統(tǒng)一的時空框架體系，在時態(tài)拓撲和空間拓撲分析的基礎上構建原子時空過程拓撲關系，并對其幾何表達、語義描述和聯(lián)合矩陣表達進行討論，最后利用原子時空過程拓撲關系實現(xiàn)時空過程拓撲關系的統(tǒng)一存儲與計算表達。

1 時態(tài)與空間拓撲關系描述

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

Allen基于時間區(qū)間邏輯模型，給出了13種互不相交且聯(lián)合完備的時態(tài)拓撲關系，但是它混淆了時態(tài)方向關系和時態(tài)拓撲關系[8]。舒紅等將時態(tài)區(qū)間作為時態(tài)拓撲分析的基元，并用4-交模型和9-交模型來表達時態(tài)區(qū)間之間的拓撲關系，并證明二者在時態(tài)拓撲表達上具有等同性[9，10]。

8種時態(tài)拓撲關系分別為時間相離、時間相接、時間部分覆蓋、時間覆蓋、時間被覆蓋、時間重合、時間包含與時間被包含，記為：TDisjoint，TMeet，TOverlap，TCover，TCoveredBy，TEqual， TContain，TInside，其4交模型的矩陣表達，如圖1所示[10]。

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

空間拓撲模型主要有兩種表達模型RCC-n模型和n交模型。RCC-n模型是基于哲學邏輯的公理化拓撲，它的研究主要集中于空間推理領域[11]。n交模型是基于點集拓撲理論的數(shù)學形式拓撲，主要用于GIS領域的空間拓撲分析[12]。所以下面主要分析基于n交模型空間拓撲關系的表達。

現(xiàn)實世界中的空間對象A是由內部、邊界和外部三個部分組成，用符號分別表示為，[A?]、[?A]和[A-]。n交模型的基本思想是利用兩個對象的邊界、內部、外部之間的交集矩陣來表達空間拓撲關系，矩陣元素取值為[θ]或[θ]。根據(jù)是否考慮對象的外部，又可以分成4交模型和9交模型，二者在空間拓撲關系表達上具有等同性。

8種面/面拓撲關系的4交模型的矩陣表達，如圖2所示。

2 時空過程拓撲關系表達

2.1空間拓撲關系變化順序

地理空間在時空過程中的變化體現(xiàn)在兩個方面：①地理實體的變化，包括空間位置、形狀、大小、屬性變化等；②空間關系的變化，主要包括空間距離、方向和拓撲關系的變化?？臻g拓撲關系的變化主要是由地理實體自身的形狀變化和地理實體位移所引起的。

時空過程中，地理實體會發(fā)生不同程度的變化，從而可能引起空間拓撲關系的變化，這種變化是按照一定的順序進行的。圖3 描述了由地理實體的位移和形變所引起的空間拓撲關系變化的順序關系。

圖3中，A和B是兩個面狀地理實體。雙向箭頭兩側的拓撲關系是相鄰的，即箭頭一側拓撲關系發(fā)生變化可能會產(chǎn)生箭頭另一側的拓撲關系，但不可能出現(xiàn)跨越相鄰拓撲關系直接形成另一種拓撲關系的變化過程，如相離拓撲關系變化不能直接產(chǎn)生部分覆蓋拓撲關系，其必須經(jīng)過相鄰拓撲關系才能變成部分覆蓋拓撲關系。圖中黑色雙向箭頭兩側的拓撲關系皆可通過地理實體形變或地理實體位移完成相互轉化；紅色雙向箭頭兩側的拓撲關系只能通過地理實體的形變完成相互轉化。

2.2原子時空過程拓撲關系

時空過程是地理實體在時空多維空間中，沿著時間維向前不斷移動、變化的過程，其變化形成的軌跡是一個以時間為縱軸的時空立方體。圖4展示了地理實體A和B沿著時間軸t演化，形成的時空立方體。

圖4 時空多維空間中地理對象演化過程

在時間區(qū)間[Tstart，Tend]內，A和B都在向前演化，其中A從t1時刻開始向周圍勻速擴散，B在整個時間區(qū)間內沒有發(fā)生任何變化。A與B的拓撲關系在時間區(qū)間內發(fā)生了變化，由相離變化成相鄰。時空過程中，地理實體的演化是一個持續(xù)變化的過程，但與其他地理實體之間空間拓撲關系的變化是離散的、突變的。

隨著時間區(qū)間長度的增加，拓撲關系的變化過程變得更加復雜。以簡單、明確為目的，這里僅探討基本拓撲關系過程的表達。

定義 基元空間拓撲關系過程：在指定的時間區(qū)間內，地理實體間的空間拓撲關系僅在相鄰拓撲關系之間變化或不發(fā)生變化，形式化表達為：[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）

為了表達的統(tǒng)一性，將在時間區(qū)間保持不變的空間拓撲關系也表達為前后相同的基元空間拓撲關系過程。根據(jù)拓撲關系變化的順序，可以將相鄰拓撲關系過程分解成30種基元空間拓撲關系過程，其幾何表達，如圖5所示。

圖5 30種基元空間拓撲關系過程的幾何表達

圖5中黃綠色和灰色圖形分別表達兩個面狀地理實體在時間區(qū)間[tstart，tend]演化過程所形成的時空立方體。此處空間拓撲關系的變化只涉及相同的時間區(qū)間的面狀實體，并未考慮時間區(qū)間之間的時態(tài)拓撲關系。

2.3原子時空過程拓撲關系表達

在時空過程中，時間和空間是相互聯(lián)系、相互影響的：時間是通過空間對象或相互關系的變化來體現(xiàn)，空間是通過地理實體在時間方向存在的延續(xù)性而得到證明；同時，二者又是相互獨立的，它們可以單獨地在各自領域中進行推理和計算。因此，通過時間與空間狀態(tài)序列的耦合可以對時空過程進行表達。從認知學的角度出發(fā)，需要把時空過程作為一個時空整體進行理解與描述，但由于持續(xù)變化過程表達的復雜性和計算機只能進行二進制數(shù)存儲，目前大都采用有序的空間狀態(tài)序列來對時空過程進行表達。

時間與空間的相互獨立性，為通過基元空間拓撲變化過程與時態(tài)拓撲關系耦合表達時空過程拓撲提供了可能。因此，本文采用基元空間拓撲關系過程與過程所占時間區(qū)間之間的時態(tài)拓撲關系進行笛卡爾積耦合，來表達原子時空過程拓撲關系。4交模型基元空間拓撲關系過程與4交模型時態(tài)拓撲關系笛卡爾積矩陣的原子時空過程拓撲關系表達，如式2所示。

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

以4交模型的基元空間拓撲關系過程與4交模型的時態(tài)拓撲關系笛卡爾積耦合，TPProcess×TEqual、TPprocess×TDisjoin、TPprocess×TMeet、TPprocess×TOverlay、TPprocess×TCover、TPprocess×TCoveredby、TPprocess×TContain、TPprocess×TInside，形成240種原子時空過程拓撲關系。由于篇幅所限，在此僅給出TPprocess×TDisjoin的30種原子時空過程拓撲關系的幾何表達和耦合矩陣，如圖6所示，其的基本語義描述如表1所示。其他的耦合矩陣的時空過程拓撲語義及其耦合矩陣，可以根據(jù)相同的方法得到。

圖6 TPprocess×TInside原子時空過程拓撲關系的幾何表達與耦合矩陣

表1 TPprocess×TInside原子時空過程拓撲關系的語義描述

[原子時空過程拓撲關系＼&語義描述＼&TRDisjoint→Disjoint：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系一直保持相離＼&TRDisjoint→Meet：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由相離變化到相接＼&TRMeet→Disjoint：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由相接變化到相離＼&TRMeet→Meet：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系一直保持相鄰＼&TRMeet→Overlay：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由相接變化到部分覆蓋＼&TROverlay→Meet：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由部分覆蓋變化到相接＼&TROverlay→Overlay：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系一直保持部分覆蓋＼&TROverlay→Cover：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由部分覆蓋變化到覆蓋＼&TRCover→Overlay：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由覆蓋變化到部分覆蓋＼&TRCover→Cover：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系一直保持覆蓋＼&TRCover→Contain：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由覆蓋變化到包含＼&TRContain→Cover：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由包含變化到覆蓋＼&TRContain→Contain：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系一直保持包含＼&TROverlay→Equal：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由包含變化到重合＼&TREqual→Overlay：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由重合變化到包含＼&TREqual→Equal：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系一直保持重合＼&TROverlay→Coveredby：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由部分覆蓋變化到被覆蓋＼&TRCoveredby→Overlay：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由被覆蓋變化到部分覆蓋＼&TRCoveredby→Coveredby：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系一直保持被覆蓋＼&TRCoveredby→Inside：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由被覆蓋變化到被包含＼&TRInside→Coveredby：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由被包含變化到被覆蓋＼&TRInside→Inside：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系一直保持被包含＼&TRCover→Equal：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由覆蓋變化到重合＼&TREqual→Cover：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由重合變化到覆蓋＼&TRContain→Equal：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由包含變化到重合＼&TREqual→Contain：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由重合變化到包含＼&TRCoveredby→Equal：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由被覆蓋變化到重合＼&TREqual→Coveredby：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由重合變化到被覆蓋＼&TRInside→Equal：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由被包含變化到重合＼&TREqual→Inside：：TInside＼&時空過程對應時間區(qū)間為被包含關系，空間拓撲關系由重合變化到被包含＼&]

2.4 時空過程拓撲關系表達

隨著時空過程所占時間區(qū)間長度的增大，地理實體之間的空間拓撲關系變化也變得更加頻繁和復雜。通過相鄰空間拓撲變化狀態(tài)的有序集合和與其對應時間區(qū)間的時態(tài)拓撲關系進行笛卡爾積耦合來表達復雜時空過程之間拓撲關系策略在理論上是可行的，但實際操作起來就會因為拓撲關系狀態(tài)過多、變化過程復雜和數(shù)目龐大的拓撲關系變化過程分類，而致使其實用性大大降低。

對于長時間區(qū)間時空過程拓撲關系，可以采用化繁為簡的策略，將其離散成多個原子時空過程拓撲關系，當需要表達整個時空過程拓撲關系時，可以通過時間區(qū)間聯(lián)接操作來實現(xiàn)。圖8展示了長時間區(qū)間時空過程拓撲關系的變化過程。

圖7 復雜時空過程拓撲關系

地理實體A在整個過程中沒有發(fā)生變化，而實體B卻不斷地發(fā)生變化：首先變大、再變小、最后又變大。在整個時間區(qū)間[t1，t4]內，二者之間的空間拓撲關系發(fā)生了三次變化：相離到鄰接、相鄰到相離和相離到部分覆蓋，變化發(fā)生的時間區(qū)間分別為，[t1，t2]，[t2，t3]和[t3，t4]。為了符合原子時空過程拓撲關系時間聯(lián)接表達時空過程拓撲關系的要求，將包含跨越相鄰空間拓撲關系的時間區(qū)間[t3，t4]拆分成[t3，t3_m]和[t3_m，t4]，分別對應相離到部分覆蓋拓撲關系變化的子過程，相離到相鄰和相鄰到部分覆蓋。圖8中時空過程拓撲關系離散成原子時空過程拓撲關系序列的操作過程，如圖8所示。

圖8 時空過程的原子時空過程拓撲關系拆分

顯然，時間區(qū)間的前后順序是很容易獲得的，因此在進行原子時空過程拓撲關系聯(lián)合后，就可以清晰地表達在指定時間區(qū)間內空間拓撲關系的變化過程。如圖9所示，前一原子時空過程拓撲表達矩陣中的后拓撲關系與后一原子時空過程拓撲表達矩陣中的前拓撲關系是相同的，稱此關系為連接拓撲關系。通過相同的連接拓撲關系，可以對有序的原子時空過程拓撲關系序列進行合并，來表達長時間區(qū)間時空過程之間的拓撲關系。例中時空過程拓撲關系變化過程為：相離→相鄰→相離→相鄰→部分覆蓋。當然，還可以對這個變化過程進行抽象以獲得更高層次上拓撲關系變化的趨勢。

3 結束語

時空過程之間的拓撲關系是時態(tài)拓撲關系與空間拓撲關系變化過程的有機耦合，是進行時空推理、時空數(shù)據(jù)挖掘和時空分析的重要基礎。論文主要完成以下幾個方面的工作：1）對時空過程間空間拓撲關系的變化過程進行分析，確定了30基本空間拓撲關系變化過程，并給出相應的幾何描述和組合矩陣表達；2）將30種基本空間拓撲過程與時態(tài)拓撲關系進行笛卡爾積耦合，構建了240種原子時空過程拓撲關系，并說明了相應的幾何語義和矩陣表達模型；3）基于原子時空過程拓撲關系，給出了時空過程拓撲關系分解與表達的方法?；谠訒r空過程拓撲的時空過程拓撲關系的表達，使得復雜的時空過程拓撲關系表達變得簡單、直觀和易操作，語義描述也更加符合人的認知習慣，能更好地解釋時空過程，并且存儲表達具有完備的數(shù)理基礎，為時空過程知識挖掘和時空過程推理奠定了基礎。

時空過程拓撲關系異常復雜，論文的討論是假定原子時空過程拓撲關系的時間區(qū)間內沒有出現(xiàn)地理實體本身消亡和新生，因此在建模中如何兼顧新生與消亡實體還有待于進一步的研究。

參考文獻：

[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] 曾聯(lián)斌， 宋迎春. 地理信息系統(tǒng)中時空拓撲關系計算表達[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] 舒紅， 陳軍， 杜道生，等. 時空拓撲關系定義及時態(tài)拓撲關系描述[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.