移動(dòng)目標(biāo)空間拓?fù)潢P(guān)系的度量描述

李朋朋，劉紀(jì)平，羅 安，張玉婷

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

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

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

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

因此，本文基于格網(wǎng)化的思想[15]，通過引入內(nèi)部分量、邊界分量、外部分量等3種度量參數(shù)對(duì)移動(dòng)目標(biāo)空間拓?fù)潢P(guān)系進(jìn)行度量描述。

1 9交模型

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

(1)

9交模型是對(duì)空間目標(biāo)拓?fù)潢P(guān)系的形式化描述，因此它的分類為粗略的分類，它所描述的拓?fù)潢P(guān)系只是拓?fù)潢P(guān)系的類別。

2 目標(biāo)格網(wǎng)化及確定拓?fù)潢P(guān)系

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

2.1 目標(biāo)對(duì)象的格網(wǎng)化

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

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

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

2.2 確定拓?fù)潢P(guān)系

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

3 目標(biāo)空間拓?fù)潢P(guān)系度量描述

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

3.1 內(nèi)部分量

空間對(duì)象內(nèi)部有相交情況一般為拓?fù)浒?、拓?fù)湎嘟缓屯負(fù)湎嘟拥汝P(guān)系，而在連續(xù)變化的空間目標(biāo)為拓?fù)湎嘟粫r(shí)，9交模型就難以有效的形式化描述空間關(guān)系，如圖2所示，在t1、t2、t3、t4時(shí)刻，拓?fù)湫问交枋龆紴橄嘟魂P(guān)系，但是在空間對(duì)象A的內(nèi)部相交面積在不斷地發(fā)生變化。

圖2 連續(xù)變化的空間目標(biāo)拓?fù)潢P(guān)系

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

(2)

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

3.2 邊界分量

對(duì)于拓?fù)湎嘟雍拖嘟魂P(guān)系，邊界相交部分的大小及相交特征等的度量描述是區(qū)別于其他拓?fù)潢P(guān)系的一個(gè)重要因素。因此，本文引入邊界分量二元組(TA,TB)對(duì)空間目標(biāo)邊界情況進(jìn)行度量描述，通過計(jì)算參考目標(biāo)邊界格網(wǎng)相交點(diǎn)數(shù)占參考目標(biāo)邊界所有格網(wǎng)數(shù)的比重和占對(duì)象目標(biāo)所有格網(wǎng)的比重得到。TA和TB計(jì)算公式為

(3)

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

3.3 外部分量

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

(4)

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

3.4 移動(dòng)目標(biāo)拓?fù)潢P(guān)系度量表達(dá)

移動(dòng)目標(biāo)是空間與時(shí)間耦合框架下的統(tǒng)一體，其位置或形狀會(huì)隨時(shí)間的變化而變化[18]。因此，移動(dòng)目標(biāo)拓?fù)涞亩攘啃枰粋€(gè)靜止的目標(biāo)對(duì)象作為參考目標(biāo)；同時(shí)，在某一時(shí)間段內(nèi)移動(dòng)目標(biāo)相對(duì)于參考目標(biāo)的拓?fù)潢P(guān)系可以由時(shí)間段內(nèi)連續(xù)時(shí)間點(diǎn)的拓?fù)潢P(guān)系組合描述。本文通過引入時(shí)間變量T并利用有序三元組Top(A,B,T)的形式來度量描述移動(dòng)目標(biāo)的拓?fù)潢P(guān)系，即

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表示參考目標(biāo)；B表示移動(dòng)目標(biāo)；Top(A,B,T)表示移動(dòng)目標(biāo)B相對(duì)于參考目標(biāo)A在時(shí)間段T內(nèi)的拓?fù)潢P(guān)系；top(A,B)t=i表示在t=i時(shí)刻移動(dòng)目標(biāo)相對(duì)于參考目標(biāo)的拓?fù)涠攘棵枋?，?jì)算公式為

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

(TA,TB),Dmin)〉

(6)

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

4 試驗(yàn)與分析

試驗(yàn)分為兩組，分別是以線狀目標(biāo)和面狀目標(biāo)為參考目標(biāo)，對(duì)點(diǎn)、線、面狀移動(dòng)目標(biāo)進(jìn)行拓?fù)涠攘糠治觥Ｈ鐖D3所示，圖3(a)—(c)組參考目標(biāo)為線狀目標(biāo)，圖3(d)—(f)組為面狀目標(biāo)；圖3中(a)和(d)、(b)和(e)、(c)和(f)組分別表示移動(dòng)點(diǎn)目標(biāo)、線目標(biāo)、面目標(biāo)的拓?fù)潢P(guān)系描述。圖中淺色表示目標(biāo)邊界，深色表示相交格網(wǎng)。表1表示了圖3中每組移動(dòng)目標(biāo)在t1、t2、t3、t4、t5時(shí)刻拓?fù)涠攘棵枋觯槐?表示了圖3中每組移動(dòng)目標(biāo)在時(shí)間段T=[t1,t5]內(nèi)的拓?fù)涠攘棵枋觥?/p>

圖3 移動(dòng)目標(biāo)拓?fù)潢P(guān)系度量描述

時(shí)間點(diǎn)t1、t2、t3、t4、t5通常選擇拓?fù)潢P(guān)系或度量參數(shù)發(fā)生變化的時(shí)刻。在表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)為拓?fù)湎嚯x時(shí)，內(nèi)部分量和邊界分量的取值均為(0,0)，邊界分量取值為兩目標(biāo)邊界間最小格網(wǎng)數(shù)，在其他拓?fù)潢P(guān)系中，邊界分量取值均為0；在表1中a(t3)、b(t2)、b(t4)、c(t2)、c(t4)、d(t2)、e(t2)、f(t2)為拓?fù)湎嘟訒r(shí)，內(nèi)部分量OA和OB的取值范圍為[0,1)，邊界分量TA和TB的取值范圍為[0,1]；在表1中b(t3)、c(t3)、e(t1)、e(t4)、f(t3)為拓?fù)湎嘟粫r(shí)，內(nèi)部分量OA和OB的取值范圍為(0,1)，邊界分量TA和TB的取值范圍為[0,1)；在表1中a(t2)、e(t3)、f(t4)為拓?fù)浒瑫r(shí)，內(nèi)部分量OA的取值為(0,1)，OB的取值為1，邊界分量TA和TB的取值為0；這些取值范圍不考慮兩目標(biāo)相互纏繞的情況。在表1組別b的t2、t4時(shí)刻，拓?fù)潢P(guān)系形式化描述都為相接關(guān)系，通過內(nèi)部變量和邊界變量的計(jì)算，可以看到t2時(shí)刻是線、線對(duì)象邊界相接，內(nèi)部沒有相交(OA,OB)=(0,0)，t4時(shí)刻是線、線對(duì)象內(nèi)部相接，邊界沒有相交(TA,TB)=(0,0)；t3、t4時(shí)刻，線拓?fù)潢P(guān)系形式化描述分別為相交關(guān)系和相接關(guān)系，由于參考目標(biāo)內(nèi)部相交格網(wǎng)相同都為5，所有內(nèi)部分量和邊界分量相同。因此，利用拓?fù)湫问交投攘炕枋鱿嘟Y(jié)合的方法能夠更加有效、準(zhǔn)確地描述空間目標(biāo)間拓?fù)潢P(guān)系。表2中，將具有代表性時(shí)間點(diǎn)的拓?fù)涠攘棵枋鲇行虻慕M合在一起描述移動(dòng)目標(biāo)相對(duì)于參考目標(biāo)的拓?fù)渥兓?，使得移?dòng)目標(biāo)的拓?fù)潢P(guān)系描述更加直觀和詳細(xì)。

表1 各組移動(dòng)目標(biāo)特在定時(shí)刻的拓?fù)涠攘棵枋?/p>

表2 各組移動(dòng)目標(biāo)在時(shí)間段內(nèi)的拓?fù)涠攘棵枋?/p>

5 結(jié) 語

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