移動目標空間拓撲關系的度量描述

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

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

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

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

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

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

1 9交模型

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

(1)

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

2 目標格網化及確定拓撲關系

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

2.1 目標對象的格網化

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

圖1 空間目標的格網化

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

2.2 確定拓撲關系

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

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

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

3.1 內部分量

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

圖2 連續變化的空間目標拓撲關系

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

(2)

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

3.2 邊界分量

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

(3)

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

3.3 外部分量

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

(4)

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

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

移動目標是空間與時間耦合框架下的統一體，其位置或形狀會隨時間的變化而變化[18]。因此，移動目標拓撲的度量需要一個靜止的目標對象作為參考目標；同時，在某一時間段內移動目標相對于參考目標的拓撲關系可以由時間段內連續時間點的拓撲關系組合描述。本文通過引入時間變量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內的拓撲關系；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的內部分量、邊界分量和外部分量。

4 試驗與分析

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

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

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

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

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

5 結 語

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