李朋朋，劉紀平，羅 安，張玉婷

(1. 蘭州交通大學測繪與地理信息學院，甘肅 蘭州 730070； 2. 甘肅省地理國情監(jiān)測工程實驗室，甘肅 蘭州 730070； 3. 中國測繪科學研究院，北京100830)

隨著移動通信技術及定位技術的迅速發(fā)展，移動目標數(shù)據(jù)庫(moving object database,MOD)已經(jīng)成為數(shù)據(jù)庫領域近幾年來研究的熱點問題[1]。MOD作為表示移動目標及其位置信息的數(shù)據(jù)庫在民航管制、交通管理、軍事指揮、基于位置的信息服務等眾多領域有著廣泛的應用，但同時如何對移動目標存儲、檢索和位置管理等技術成為建設數(shù)據(jù)庫所面臨的新挑戰(zhàn)[2]。MOD的存儲和管理空間數(shù)據(jù)必然離不開空間關系分析，而空間拓撲關系作為空間關系的一個重要內(nèi)容，它的研究將直接影響MOD的建設。

在空間拓撲關系描述模型研究中，比較常用的是文獻[3]提出的基于拓撲關系點集理論描述框架的4元組模型(4-intersection model,4IM)和9交模型(9-intersection model,9IM)。同時，國內(nèi)外學者針對4IM和9IM描述空間拓撲關系的不足也作了很多研究，如文獻[4]提出維數(shù)的概念，定義了不同相交情況對應不同維數(shù)，得到維數(shù)擴展模型DE-4IM和DE-9IM；文獻[5]在9IM的基礎上，通過嵌套矩陣的模式區(qū)分各種空間對象之間的拓撲關系；文獻[6]利用空間對象之間、對象內(nèi)部之間和對象邊界之間的相互運算，提出新的4元組模型(4IDM)；文獻[7]利用空間對象Voronoi區(qū)域來替換它在9IM中的外部，提出了基于Voronoi圖的9交模型。同時還有學者提出不同的模型，如文獻[8]提出了空間代數(shù)模型來描述空間拓撲關系。

雖然以上模型對空間關系描述作了很多詳細的研究，但是基本上都是對空間拓撲關系的形式化描述，忽略了空間目標的度量特性。從而沒有足夠的細節(jié)對空間關系進行重要區(qū)分，得到的空間關系為粗略的空間關系分類，使其拓撲關系容易受誤差和不確定性的影響，并很難滿足動態(tài)信息分析和提取的需要[9]。為此一些學者也進行了空間拓撲關系度量化描述[10-11]及動態(tài)目標拓撲關系描述[12-14]的研究，盡管取得一些成果，但都是對靜態(tài)特定空間目標間的拓撲度量化描述和對動態(tài)目標間的拓撲形式化描述，并沒有將二者結合在一起，導致動態(tài)目標缺少細節(jié)上度量描述。

因此，本文基于格網(wǎng)化的思想[15]，通過引入內(nèi)部分量、邊界分量、外部分量等3種度量參數(shù)對移動目標空間拓撲關系進行度量描述。

1 9交模型

9交模型是Egenhofer(1990)[3]以點集拓撲學為理論基礎,在4交模型區(qū)分線與線、線與面兩類空間對象不足的情況下，提出的一種拓撲關系描述框架[16]。它將任何一個空間對象(A)劃分成邊界(?A)、內(nèi)部(A0)和外部(A-) 3個部分，并通過這3部分點集的交進行拓撲關系區(qū)分。這樣對于任意的兩個空間對象間的拓撲關系描述可表示成9種情況，每種情況的取值分為空(Φ)或非空(Φ)兩種值，如下所示

(1)

9交模型是對空間目標拓撲關系的形式化描述，因此它的分類為粗略的分類，它所描述的拓撲關系只是拓撲關系的類別。

2 目標格網(wǎng)化及確定拓撲關系

對于傳統(tǒng)空間目標的拓撲關系判定都是利用矢量數(shù)據(jù)，通過求解矢量點、線、面交的方式，其計算量大。因此本文通過格網(wǎng)化的思想進行求解，首先將對象劃分為固定大小的格網(wǎng)陣列，然后利用9交模型判定各個格網(wǎng)相交情況對空間拓撲關系進行形式化描述。

2.1 目標對象的格網(wǎng)化

為了更好地表達和計算空間關系，本文定義點目標為一個格網(wǎng)，線目標為一系列連續(xù)點目標構成的格網(wǎng)鏈，面目標為一條首尾相接的線目標構成的封閉區(qū)間格網(wǎng)面，如圖1所示。每個格網(wǎng)都由量化的橫縱坐標表示其位置，并通過動態(tài)調(diào)整格網(wǎng)大小，保證目標邊界格網(wǎng)唯一性，使邊界對應的格網(wǎng)只能表示一個目標對象的邊界。

圖1 空間目標的格網(wǎng)化

目標內(nèi)部、邊界、外部對應格網(wǎng)位置的存儲采用單向鏈表的方式進行存儲，定義鏈表Boundary_List存儲邊界格網(wǎng)；鏈表Interior_List存儲內(nèi)部格網(wǎng)；鏈表Exterior_List存儲外部格網(wǎng)。其中，點狀目標的邊界格網(wǎng)鏈表和內(nèi)部格網(wǎng)鏈表相同，線狀目標的邊界格網(wǎng)鏈表為線目標兩端點格網(wǎng)位置，以方便后面計算。

2.2 確定拓撲關系

通過上面的格網(wǎng)化，點、線、面等空間對象均被描述為一個或多個格網(wǎng)陣列，然后借助9交模型的定性描述，判斷邊界格網(wǎng)鏈表、內(nèi)部格網(wǎng)鏈表和外部格網(wǎng)鏈表等鏈表是否含有相同數(shù)據(jù)元素值來確定拓撲關系，即判斷空間目標邊界、內(nèi)部、外部是否有交集。本文將拓撲關系形式化描述主要分為：相等關系(equal)、相離關系(disjoint)、相接關系(touch)、相交關系(overlap)和包含關系(contain)等5種關系。

3 目標空間拓撲關系度量描述

9交模型中空間對象之間的拓撲關系通過內(nèi)部、邊界和外部的相互作用來描述。因此，對于內(nèi)部、邊界和外部交的度量是拓撲關系的度量描述的關鍵。本文引入內(nèi)部分量、邊界分量、外部分量對空間對象內(nèi)部、邊界和外部進行細化的度量描述。

3.1 內(nèi)部分量

空間對象內(nèi)部有相交情況一般為拓撲包含、拓撲相交和拓撲相接等關系，而在連續(xù)變化的空間目標為拓撲相交時，9交模型就難以有效的形式化描述空間關系，如圖2所示，在t1、t2、t3、t4時刻，拓撲形式化描述都為相交關系，但是在空間對象A的內(nèi)部相交面積在不斷地發(fā)生變化。

圖2 連續(xù)變化的空間目標拓撲關系

因此，本文引入內(nèi)部分量二元組(OA，OB)對空間目標內(nèi)部情況進行度量描述，通過計算參考目標內(nèi)部格網(wǎng)相交點數(shù)占參考目標內(nèi)部所有格網(wǎng)數(shù)的比重和占對象目標所有格網(wǎng)的比重得到。OA和OB計算公式為

(2)

式中，num(IGridAB)表示參考目標A內(nèi)部相交重疊的格網(wǎng)數(shù)，包括目標B邊界與目標A內(nèi)部相交的格網(wǎng)數(shù)和目標B內(nèi)部與目標A內(nèi)部相交的格網(wǎng)數(shù)；num(IGridA)和num(IGridB)分別表示目標A的內(nèi)部所有格網(wǎng)數(shù)和目標B的所有格網(wǎng)數(shù)(包括邊界格網(wǎng)數(shù)和內(nèi)部格網(wǎng)數(shù))。OA和OB的取值范圍[0,1]，當拓撲關系為相離時兩個值取值均為0；當拓撲關系為包含時OA的取值為(0,1)，OB的取值為1；當拓撲關系為相交時兩個值取值均為(0,1)；當拓撲關系為相接時兩個值取值均為[0,1)；當拓撲關系為相等時OA的取值為1，OB的取值為(0,1)。

3.2 邊界分量

對于拓撲相接和相交關系，邊界相交部分的大小及相交特征等的度量描述是區(qū)別于其他拓撲關系的一個重要因素。因此，本文引入邊界分量二元組(TA,TB)對空間目標邊界情況進行度量描述，通過計算參考目標邊界格網(wǎng)相交點數(shù)占參考目標邊界所有格網(wǎng)數(shù)的比重和占對象目標所有格網(wǎng)的比重得到。TA和TB計算公式為

(3)

式中，num(BGridAB)表示參考目標A邊界相交重疊的格網(wǎng)數(shù)，包括目標A和B邊界相交格網(wǎng)數(shù)和目標B內(nèi)部與目標A邊界相交格網(wǎng)數(shù)；num(BGridA)和num(BGridB)分別表示目標A的邊界所有格網(wǎng)數(shù)和目標B的所有格網(wǎng)數(shù)(包括邊界格網(wǎng)數(shù)和內(nèi)部格網(wǎng)數(shù))。TA和TB的取值范圍[0,1]，當拓撲關系為包含或相離時兩個值取值均為0；當拓撲關系為相等時TA的取值為1，TB的取值為(0,1)；當拓撲關系為相接時兩個值取值均為[0,1]；當拓撲關系為相交時取值為[0,1)。

3.3 外部分量

在9交模型中，空間對象的外部為除去空間對象自身以外的所有二維空間，其范圍太大，直接對外部度量描述比較困難。因此，本文引入外部分量Dmin通過計算兩目標邊界格網(wǎng)間最小距離的格網(wǎng)數(shù)進行度量描述。Dmin的計算公式

(4)

式中，n、m分別表示目標A、B邊界格網(wǎng)數(shù)；i、j分別表示目標A、B邊界中任意一個格網(wǎng)；disij表示目標A邊界上第i個格網(wǎng)與目標B邊界上第j個格網(wǎng)間的格網(wǎng)數(shù)。在計算含有線狀目標外部分量時，由于線目標的邊界為兩端點，不能完全表達外部的內(nèi)邊界，因此，在計算過程中線狀目標邊界格網(wǎng)由自身的內(nèi)部格網(wǎng)和邊界格網(wǎng)構成。

3.4 移動目標拓撲關系度量表達

移動目標是空間與時間耦合框架下的統(tǒng)一體，其位置或形狀會隨時間的變化而變化[18]。因此，移動目標拓撲的度量需要一個靜止的目標對象作為參考目標；同時，在某一時間段內(nèi)移動目標相對于參考目標的拓撲關系可以由時間段內(nèi)連續(xù)時間點的拓撲關系組合描述。本文通過引入時間變量T并利用有序三元組Top(A,B,T)的形式來度量描述移動目標的拓撲關系，即

Top(A,B,T)=(top(A,B)t=0,top(A,B)t=1,…,

top(A,B)t=i,…,top(A,B)t=n)

(5)

式中，A表示參考目標；B表示移動目標；Top(A,B,T)表示移動目標B相對于參考目標A在時間段T內(nèi)的拓撲關系；top(A,B)t=i表示在t=i時刻移動目標相對于參考目標的拓撲度量描述，計算公式為

top(A,B)t=i=〈tr9(A,B),(OA,OB),

(TA,TB),Dmin)〉

(6)

式中，tr9(A,B)表示目標A、B拓撲關系形式化描述，即基于9交模型的拓撲關系；(OA，OB)、(TA，TB)和Dmin分別表示目標A、B的內(nèi)部分量、邊界分量和外部分量。

4 試驗與分析

試驗分為兩組，分別是以線狀目標和面狀目標為參考目標，對點、線、面狀移動目標進行拓撲度量分析。如圖3所示，圖3(a)—(c)組參考目標為線狀目標，圖3(d)—(f)組為面狀目標；圖3中(a)和(d)、(b)和(e)、(c)和(f)組分別表示移動點目標、線目標、面目標的拓撲關系描述。圖中淺色表示目標邊界，深色表示相交格網(wǎng)。表1表示了圖3中每組移動目標在t1、t2、t3、t4、t5時刻拓撲度量描述；表2表示了圖3中每組移動目標在時間段T=[t1,t5]內(nèi)的拓撲度量描述。

圖3 移動目標拓撲關系度量描述

時間點t1、t2、t3、t4、t5通常選擇拓撲關系或度量參數(shù)發(fā)生變化的時刻。在表1中a(t1)、a(t4)、b(t1)、b(t5)、c(t1)、c(t5)、d(t1)、d(t4)、e(t1)、e(t5)、f(t1)、f(t5)為拓撲相離時，內(nèi)部分量和邊界分量的取值均為(0,0)，邊界分量取值為兩目標邊界間最小格網(wǎng)數(shù)，在其他拓撲關系中，邊界分量取值均為0；在表1中a(t3)、b(t2)、b(t4)、c(t2)、c(t4)、d(t2)、e(t2)、f(t2)為拓撲相接時，內(nèi)部分量OA和OB的取值范圍為[0,1)，邊界分量TA和TB的取值范圍為[0,1]；在表1中b(t3)、c(t3)、e(t1)、e(t4)、f(t3)為拓撲相交時，內(nèi)部分量OA和OB的取值范圍為(0,1)，邊界分量TA和TB的取值范圍為[0,1)；在表1中a(t2)、e(t3)、f(t4)為拓撲包含時，內(nèi)部分量OA的取值為(0,1)，OB的取值為1，邊界分量TA和TB的取值為0；這些取值范圍不考慮兩目標相互纏繞的情況。在表1組別b的t2、t4時刻，拓撲關系形式化描述都為相接關系，通過內(nèi)部變量和邊界變量的計算，可以看到t2時刻是線、線對象邊界相接，內(nèi)部沒有相交(OA,OB)=(0,0)，t4時刻是線、線對象內(nèi)部相接，邊界沒有相交(TA,TB)=(0,0)；t3、t4時刻，線拓撲關系形式化描述分別為相交關系和相接關系，由于參考目標內(nèi)部相交格網(wǎng)相同都為5，所有內(nèi)部分量和邊界分量相同。因此，利用拓撲形式化和度量化描述相結合的方法能夠更加有效、準確地描述空間目標間拓撲關系。表2中，將具有代表性時間點的拓撲度量描述有序的組合在一起描述移動目標相對于參考目標的拓撲變化，使得移動目標的拓撲關系描述更加直觀和詳細。

表1 各組移動目標特在定時刻的拓撲度量描述

表2 各組移動目標在時間段內(nèi)的拓撲度量描述

5 結 語

本文基于格網(wǎng)化的思想，首先將對象目標和參考目標格網(wǎng)化，然后利用9交模型對空間目標的拓撲關系進行形式化描述，最后引入內(nèi)部分量、邊界分量、外部分量對拓撲關系進行細化度量描述，使得拓撲關系描述更加詳細；在描述移動目標拓撲關系時通過引入時間變量，利用有序三元組Top(A,B,T)的形式來度量描述。通過試驗分析，該方法計算簡單、直觀，能更加有效、詳細地度量移動目標間的拓撲關系的。在接下來的工作中，將對復雜空間拓撲關系度量描述和不確定性空間對象拓撲度量描述進行研究。