復(fù)雜3D空間中的3DR46模型的表示與推理*

郝曉紅，李 松，郝忠孝,2

1.哈爾濱理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院，哈爾濱150080

2.哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，哈爾濱150001

1 引言

隨著信息技術(shù)的快速發(fā)展，空間數(shù)據(jù)對象信息的海量性、復(fù)雜性、不確定性和多態(tài)性對空間方向關(guān)系的表示和處理技術(shù)提出了越來越高的要求。

近些年，2D空間中的方向關(guān)系的研究工作已經(jīng)較為深入，研究成果主要有錐形模型、投影模型、最小外接矩形模型、四半?yún)^(qū)域模型和2D字符串關(guān)系模型、2D不確定方向關(guān)系模型等。在基于MBR（minimum bounding rectangle）模型的2D主方向關(guān)系的表示和推理及路徑一致性檢驗[1]、不確定方向關(guān)系[2-3]、凹邊形地標(biāo)參照的主方向關(guān)系推理[4]、群組目標(biāo)空間方向關(guān)系[5]和復(fù)雜定性方向關(guān)系表示和推理[6-7]等領(lǐng)域也取得了一些重要的研究成果。

目前，對3D空間方向關(guān)系的研究尚處于起步階段，在一些關(guān)鍵問題方面留有許多空白。文獻[8]將二維雙十字模型擴展到3D空間以描述3D空間點對象間的方向關(guān)系，但該方法忽略了空間對象的形狀與大小，與現(xiàn)實中的空間對象具有很大差別，在實際應(yīng)用中具有局限性。文獻[9]將2D主方向關(guān)系拓展到3D空間，建立了一種新的3D方向關(guān)系模型?；谒⒌哪Ｐ瓦M一步研究了組合關(guān)系、反向關(guān)系和一致性檢驗等重要內(nèi)容。文獻[10]研究了基本主方向關(guān)系的反關(guān)系。文獻[11]擴展了2D空間中開放區(qū)域模型的抽象基類，基于對象方位的27個方向關(guān)系描述模型提出了3D空間中的開放區(qū)域模型。文獻[12]基于對象相交立方體矩陣來描述3D空間中的主方向關(guān)系。為了表示三維空間中的方位關(guān)系，文獻[13]基于點集拓?fù)鋵W(xué)對三維方向關(guān)系進行了定義，并研究了在3D空間語言中的應(yīng)用。文獻[14]考慮相對方向和粒度，提出了新的三維空間中的方位關(guān)系模型。文獻[15]對3D空間的主方向關(guān)系及推理技術(shù)進行了研究。文獻[16]提出了一種新的用于三維空間中具有塊間主方向關(guān)系的定性空間推理的方法。但文獻[8-16]所建立的方向關(guān)系模型不能有效表示與區(qū)分大量復(fù)雜的3D方向關(guān)系，沒有給出動態(tài)方向關(guān)系的表示與處理方法，無法對3D空間中的反向方向關(guān)系進行有效分析和處理。文獻[17]將定性距離關(guān)系和3DR39方向關(guān)系模型相結(jié)合，提出了一種新的能處理和分析方向和位置的關(guān)系模型。但該模型對三維空間中一些精細(xì)方向關(guān)系的表示和推理方面的能力顯不足，無法處理一些較為復(fù)雜的三維方向關(guān)系的表示和推理問題。

為了對復(fù)雜的3D方向關(guān)系進行更為精細(xì)化的表示和推理，本文提出了一種新的3D空間方向關(guān)系模型，即3DR46方向關(guān)系模型，3DR46方向關(guān)系模型可表示和區(qū)分246種3D方向關(guān)系；基于3DR46方向關(guān)系模型進一步對動態(tài)3D方向關(guān)系和模型的雙向映射關(guān)系進行了系統(tǒng)研究。

2 3DR46方向關(guān)系模型

由于3D空間對象的復(fù)雜性，3D空間對象的方向關(guān)系變得更為復(fù)雜多樣，方位空間劃分和空間對象的不同均能導(dǎo)致大量方向關(guān)系在表示和推理方面具有較大的誤差，已有的3D方向關(guān)系模型僅能表示一部分方向關(guān)系，對一些非常重要的方向關(guān)系卻無法表示和分析。例如，3DR44模型可區(qū)分圖1中的MO5和MO4相對于QO的方向關(guān)系，卻無法區(qū)分MO6和MO7相對于參照對象QO的方向關(guān)系。因此，本章提出3DR46方向關(guān)系模型。

3DR46方向關(guān)系模型共包含46個方向空間元素，其中8個方向空間元素是封閉空間，該8個方向空間元素可組成一個大的封閉空間，參照對象即處于該封閉空間中；其他38個方向元素是開放空間。3D目標(biāo)對象可處于任何一個或幾個方向空間元素中。3DR46模型中的方向空間元素符號集合為{CNLm,CNRm,CEDm,CEUm,CSRm,CSLm,CWDm,CWUm,Wu,Wd,WNWd,WNNd,WSWd,Nd,Ed,WSSd,ENNd,ESEd,ENEd,ESSd,Cd,Sd,Wm,WNNm,WSWm,WNWm,WSSm,Em,Nm,ENNm,ESEm,ENEm,Sm,WNNu,ESSm,WSWu,WNWu,Nu,Eu,ENNu,WSSu,ESEu,Cu,ENEu,Su,ESSu}。該集合在本文中表示為DR，DR中方向空間元素具有嚴(yán)格的先后順序。

Fig.1 3DR46 relational model and plane projection graphics of some 3D objects圖1 3DR46關(guān)系模型及部分3D對象平面投影圖

定義1（3DR46模型的方向關(guān)系）設(shè)2DR表示集合DR的冪集，則3D空間對象MO（目標(biāo)對象）與QO（參照對象）的方向關(guān)系可表示為二元函數(shù)3DR46(QO,MO)，3DR46(QO,MO)∈2DR。

本文將每個方向空間元素簡稱為方向塊，每個方向塊簡記為DRi，1 ≤i≤46。若目標(biāo)對象MO處于DRi中，則簡記為MO□DRi。3DR46方向關(guān)系模型及部分空間對象的平面投影如圖1所示。

定義2（3DR46模型的方向關(guān)系交集序列）基于定義1，3D空間對象MO（目標(biāo)對象）與QO（參照對象）的方向關(guān)系交集序列集合為：

L-QOMO＝{MO∩DRi|DRi∈DR},1 ≤i≤46

交集序列L-QOMO中，若目標(biāo)對象MO的全部或一部分處于某個方向塊中，則MO和該方向塊的交集為1，否則為0。利用3DR46方向關(guān)系模型和交集序列即可表示和區(qū)分已有方向關(guān)系模型無法區(qū)分的方向關(guān)系。

3 3DR46模型的動態(tài)方向關(guān)系

3D方向關(guān)系的動態(tài)變化性主要分為兩類：目標(biāo)對象的動態(tài)性所導(dǎo)致的方向關(guān)系的動態(tài)變化；參照對象的動態(tài)性所引起的方向關(guān)系的動態(tài)變化。

3.1 目標(biāo)對象運動的動態(tài)方向關(guān)系

通常，3D目標(biāo)對象針對參照對象的空間方向關(guān)系隨時間經(jīng)常會發(fā)生動態(tài)改變，例如，飛行物和地面指揮塔間的方向關(guān)系，營救人員和遇險者間的方向關(guān)系等。利用本文提出的3DR46方向關(guān)系模型對各時刻的方向關(guān)系可表示和描述，計算機依據(jù)獲得的各交集序列即可動態(tài)處理3D方向關(guān)系。

在3DR46方向關(guān)系模型下分析基于目標(biāo)對象運動的動態(tài)方向關(guān)系時，最重要的一個問題是在兩個時刻獲得動態(tài)目標(biāo)對象相對參照對象的兩個不同的方向關(guān)系，判定這兩個方向關(guān)系是否具有連續(xù)性。即后一時刻的方向關(guān)系是否能由前一時刻的方向關(guān)系連續(xù)轉(zhuǎn)變得到而不需要經(jīng)歷其他方向關(guān)系。該問題還可擴展到多個時刻的多個方向關(guān)系的連續(xù)判定問題。例如，圖1中，MO5由CWUm方向塊移動到CWDm方向塊，其相對QO的方向關(guān)系即是連續(xù)的；若MO5由CWUm方向塊移動到CNRm方向塊，則其相對QO的方向關(guān)系變化不具有連續(xù)性，必須經(jīng)過中間方向塊。若因為部分原始數(shù)據(jù)信息的缺失或計算誤差，計算機對目標(biāo)對象下一時刻的方位關(guān)系的判斷將會發(fā)生錯誤，即遺漏了關(guān)鍵的中間方位關(guān)系，將會導(dǎo)致錯誤決策。對方向關(guān)系的連續(xù)性進行有效校驗可較好提高判定預(yù)測的準(zhǔn)確性。此類問題廣泛存在于現(xiàn)實應(yīng)用中，例如，在某時刻已獲得戰(zhàn)機相對于目標(biāo)基地的方位信息，根據(jù)戰(zhàn)機的動態(tài)信息尚需要計算機系統(tǒng)智能預(yù)測下一時刻戰(zhàn)機最有可能出現(xiàn)的方位信息，同時還需要對兩個時刻的方位信息進行有效校驗，判斷是否出現(xiàn)紕漏。若因為部分原始數(shù)據(jù)信息的缺失或計算誤差，計算機對戰(zhàn)機下一時刻的方位關(guān)系的判斷發(fā)生錯誤，即遺漏了關(guān)鍵的中間方位關(guān)系，將會誤導(dǎo)決策。對方向關(guān)系的連續(xù)性進行有效校驗可較好提高判定預(yù)測的準(zhǔn)確性。

基于3DR46方向關(guān)系模型，定義3給出了動態(tài)鄰接方向塊和動態(tài)鄰接關(guān)系的概念。

定義3（動態(tài)鄰接方向塊和動態(tài)鄰接關(guān)系）在3DR46方向關(guān)系模型中，設(shè)有目標(biāo)對象MO，兩個不同的方向塊DRj、DRi，1 ≤i≤46，1 ≤j≤46，i≠j，MO□DRi。若MO可沿某條路徑由DRi運動到DRj而不經(jīng)過DRk，i≠j≠k，即MO∩DRk=?，則稱DRj為DRi的動態(tài)鄰接方向塊，DRj和DRi具有動態(tài)鄰接關(guān)系。一個方向塊DRj的所有動態(tài)鄰接方向塊的集合稱為DRj的動態(tài)鄰接方向塊集，本文表示為DAJ(DRj)。

針對3DR46方向關(guān)系模型，首先可根據(jù)定義3確定每個方向塊的動態(tài)鄰接方向塊，再依據(jù)動態(tài)鄰接方向塊，針對獲得的大量交集序列進行連續(xù)性的判定。利用這些動態(tài)鄰接方向塊，大量復(fù)雜的3D動態(tài)方向關(guān)系即可進行較好的表示、預(yù)測與分析。本節(jié)進一步給出了方向塊Cu、CNLm、CNRm、CEDm、CEUm、CSRm、CSLm、CWDm、CWUm、Em、Wm、Nm、Sm的動態(tài)鄰接方向塊集，其他方向塊的動態(tài)鄰接方向塊集可類似給出。

對于位置頻繁發(fā)生變化的3D目標(biāo)對象MO，針對特定的3D參照對象QO，表示和確定MO與各個方向塊的位置關(guān)系是進行連續(xù)性校驗的一個關(guān)鍵點。MO在某個時間段（即一些連續(xù)的時刻）內(nèi)的運動可能完全處于一個方向塊，也可能跨越不同方向塊移動。方向關(guān)系的變化情況將是復(fù)雜的。

定義4（主位方向塊）在3DR46方向關(guān)系模型中，設(shè)參照對象為QO，目標(biāo)對象為MO，方向塊為DRi，1 ≤i≤46。若MO∩DRi≠?，則稱DRi為MO相對于QO的主位方向塊。由MO的所有主位方向塊構(gòu)成的集合稱為MO的主位方向塊集，記作CM。

定義5（鄰位方向塊）在3DR46方向關(guān)系模型中，設(shè)參照對象為QO，目標(biāo)對象為MO，MO的主位方向塊集為CM。和CM中的主位方向塊分別具有動態(tài)鄰接關(guān)系的非主位方向塊稱為基于MO的鄰位方向塊。由MO的所有鄰位方向塊構(gòu)成的集合稱為MO的鄰位方向塊集，記作PM。

定義6（隔位方向塊）在3DR46方向關(guān)系模型中，設(shè)參照對象為QO，目標(biāo)對象為MO，MO的鄰位方向塊集為PM。和鄰位方向塊具有動態(tài)鄰接關(guān)系的非主位方向塊稱為1級隔位方向塊，由MO的所有1級隔位方向塊構(gòu)成的集合稱為MO的1級隔位方向塊集，記作SM1。和1級隔位方向塊鄰接的非鄰位和非主位方向塊稱為2級隔位方向塊，由MO的所有2級隔位方向塊構(gòu)成的集合稱為MO的2級隔位方向塊集，記作SM2。同理，可定義3級、4級、5級和6級隔位方向塊及隔位方向塊集。

分析3DR46方向關(guān)系模型可知，MO的隔位方向塊至多分為6級。目標(biāo)對象所處的方向塊不同，其隔位方向塊所劃分的級數(shù)將有所不同。

基于以上分析，對于方向關(guān)系連續(xù)性的檢驗思路為：分別確定目標(biāo)對象MO在時刻t和下一時刻t′的主位方向塊集、鄰位方向塊集和各級別的隔位方向塊集；檢驗時刻t的主位方向塊集和時刻t′的鄰位方向塊集的交集情況；檢驗時刻t′的主位方向塊集和時刻t的隔位方向塊集的交集情況。若兩次檢驗的交集均為?，則t到t′的方向關(guān)系的變化具有連續(xù)性；若不同時為?，則t到t′的方向關(guān)系的變化不具有連續(xù)性，即還存在未發(fā)現(xiàn)的中間方向關(guān)系。

基于以上討論，進一步給出動態(tài)方向關(guān)系連續(xù)性判定的檢驗算法如算法1所示。

算法1DC_DIRECTION(L)

算法DC_DIRECTION()對n個方向關(guān)系序列進行連續(xù)性判定，若找到不符合連續(xù)性的方向關(guān)系序列則將其返回，更新后繼續(xù)進行檢驗，直到檢驗完最后一個方向關(guān)系序列。由定義6可知，隔位方向塊最多為6級，故算法中for循環(huán)語句的變量j最大值為6。該算法的效率和方向關(guān)系交集序列數(shù)、各類方向塊的計算量、交集判定復(fù)雜度及交集序列更新的代價有密切關(guān)系。

3.2 參照對象運動的動態(tài)方向關(guān)系

現(xiàn)實中，3D參照對象QO往往也會發(fā)生動態(tài)運動，從而目標(biāo)對象MO相對于動態(tài)參照QO的3D方向關(guān)系也會相應(yīng)發(fā)生動態(tài)變化。參照對象QO的位置變化使得MO相對QO已有的方向關(guān)系信息變得無效，大量方向關(guān)系信息需要修正和重新確定。

Fig.2 Example of planar projection of dynamic direction relation of 3D reference object motion圖2 3D參照對象運動的動態(tài)方向關(guān)系平面投影示例

如圖2所示，在3DR46方向關(guān)系模型下，參照對象QO由初始位置沿著曲線l1進行運動（由ts時刻實線所示的QO運動變化到te時刻虛線所示的QO′），目標(biāo)對象MO1和MO2相對于QO的方向關(guān)系隨著QO的位置變化相應(yīng)也在變化。MO1和MO2在ts時刻和te時刻的方向關(guān)系交集序列為：

由以上交集序列可知，參照對象發(fā)生動態(tài)變化，將會極大影響計算機對方向關(guān)系的表示和分析結(jié)果。為了在3DR46方向關(guān)系模型下處理此類重要的動態(tài)方向關(guān)系表示與預(yù)測問題，首先給出動態(tài)連續(xù)鄰接關(guān)系的定義如定義7所示。

定義7（動態(tài)連續(xù)鄰接關(guān)系）在3DR46方向關(guān)系模型中，基于定義1，設(shè)參照對象為QO，目標(biāo)對象為MO，MO相對于QO的方向關(guān)系在t1,t2,…,tn時刻分別表示為3DR46(QO,MO)t1,3DR46(QO,MO)t2,…,3DR46(QO,MO)tn。若3DR46(QO,MO)ti＋1包含的方向塊可由3DR46(QO,MO)ti所包含的方向塊直接轉(zhuǎn)化而得（其中，1 ≤i＜n），則稱3DR46(QO,MO)t1,3DR46(QO,MO)t2,…,3DR46(QO,MO)tn為一組動態(tài)連續(xù)鄰接關(guān)系。

由定義7可知，每組動態(tài)連續(xù)鄰接關(guān)系均包含不同時刻目標(biāo)對象MO相對參照對象QO不同的方向關(guān)系，方向關(guān)系具有嚴(yán)格的順序性，相鄰方向關(guān)系之間可動態(tài)轉(zhuǎn)換。3D參照對象位置發(fā)生動態(tài)改變，依據(jù)動態(tài)連續(xù)鄰接關(guān)系的內(nèi)在聯(lián)系和規(guī)律即可進一步確定MO相對QO的方向關(guān)系的連續(xù)變化情況。由定義1和方向關(guān)系的交集序列可知，每個復(fù)雜的方向關(guān)系均可分解成MO和具體方向塊的關(guān)系。雖然參照對象的運動方向和運動軌跡是任意的，但其運動方向最后均可分解成{Cu,Nm,Em,Sm,Wm,Cd}的子集，又因為Em和Wm,Sm和Nm,Cu和Cd具有高度的對稱性，故重點研究參照對象朝Nm、Cd和Wm方向運動的46個方向塊的動態(tài)連續(xù)鄰接關(guān)系特性。其他運動情況可類似得出。

基于3DR46方向關(guān)系模型，圖3（a）～（c）分別給出了參照對象運動方向為Nm、Wm和Cd時的詳細(xì)動態(tài)連續(xù)鄰接關(guān)系。

Fig.3 Dynamic continuous adjacency relations of typical principal direction motion圖3 典型主方向運動動態(tài)連續(xù)鄰接關(guān)系

圖3中，“：”表示項和其動態(tài)轉(zhuǎn)變關(guān)系的對應(yīng)關(guān)系?！?”表示參照對象朝某主方向運動期間，其標(biāo)注的方向關(guān)系不變。例如，圖3（a）中的*WSSm即表示參照對象朝Nm方向運動時，目標(biāo)對象起始時刻若處于WSSm方向塊中，在之后的運動時間內(nèi)，其相對于參照對象的方向關(guān)系將保持WSSm不變，除非運動方向發(fā)生改變?！啊北硎具\動過程中方向關(guān)系的動態(tài)連續(xù)轉(zhuǎn)變，例如，圖3（c）中WNWm→14W，即隨著參照對象進行Wm方向的運動，目標(biāo)對象相對參照對象的方向關(guān)系若發(fā)生動態(tài)連續(xù)變化，則可由WNWm直接轉(zhuǎn)變到14W項所對應(yīng)的項，14W項所表示的動態(tài)連續(xù)鄰接關(guān)系為WNNm→13W，兩項合并即可得到WNWm→WNNm→13W，13W項所表示的動態(tài)連續(xù)鄰接關(guān)系為Nm→4W,… 。最后，由圖3（c）可得出WNWm→WNNm→ENNm→*ENEm。圖中“，”表示“或”的意思。根據(jù)方向塊的動態(tài)連續(xù)鄰接關(guān)系即可依據(jù)參照對象的運動情況對相關(guān)復(fù)雜的方向關(guān)系進行組合分析與智能預(yù)測。

4 3DR46方向關(guān)系模型雙向映射關(guān)系

對于連續(xù)的無分離部分的單純3D目標(biāo)對象，利用3DR46方向關(guān)系模型表示和區(qū)分一些重要方向關(guān)系時，交集序列中的一些交集信息的計算經(jīng)常是不必要的，往往具有很大的冗余性。尤其是3D目標(biāo)對象變異為2D面對象、線對象或點對象時，冗余計算量將更大。針對一些連續(xù)的無分離部分的形狀規(guī)則的3D目標(biāo)對象，可對3DR46方向關(guān)系模型進行“降維”處理。主要思路和步驟如下：

（1）確定3D參照對象QO的3DR46方向關(guān)系模型下的46個方向空間塊；

（2）確定目標(biāo)對象MO在3D空間中的位置；

（3）將QO和其3DR46方向關(guān)系模型下的方向塊分別向垂直相交的兩個2D平面進行投影映射，將3DR46方向關(guān)系模型分解為兩個2D空間中的方向關(guān)系模型；

（4）將目標(biāo)對象MO向第（3）步中的兩個2D平面進行投影映射，3D空間中的目標(biāo)對象MO轉(zhuǎn)化為兩個2D平面中的目標(biāo)對象；

（5）在兩個2D空間中進行方向關(guān)系的表示與判斷，得出相應(yīng)的交集序列，再利用交集序列的聯(lián)合來表示和分析目標(biāo)對象MO和參照對象QO的方向關(guān)系。

為了便于投影計算，進行“降維”時，互相垂直的2D平面（投影面）的選擇需要遵循一個原則：兩個2D平面不能與參照對象和目標(biāo)對象相交。

在三維坐標(biāo)空間中，設(shè)O為坐標(biāo)原點，坐標(biāo)面xoz和xoy互相垂直，x,z,y是兩兩相互垂直的坐標(biāo)軸，坐標(biāo)面xoy和3D參照對象QO的最小包圍盒的上、下面平行；坐標(biāo)面xoz與前、后面相平行。將參照對象QO的3DR46方向元素空間分別向xoy面和xoz面進行映射投影。相應(yīng)的，將目標(biāo)對象MO也向坐標(biāo)面xoy和xoz投影，得到投影像Pxy和Pxz。用BM(DRj)表示一個方向塊DRj的投影像的集合。本章進一步給出了方向塊Cu、CNLm、CNRm、CEDm、CEUm、CSRm、CSLm、CWDm、CWUm的投影像，其他方向塊的投影像集可類似給出。

設(shè)參照對象QO的3DR46方向關(guān)系模型在xoz坐標(biāo)面的投影方向集Ψxoz為{WSxz,WNxz,ENxz,CLxz,ESxz,Sxz,Nxz,Exz,Wxz,CRxz}；在xoy坐標(biāo)面的投影方向集Ψxoy為{ENNxy,Sxy,Wxy,WNWxy,CWUxy,Exy,Nxy,CNLxy,WSWxy,ENExy,CWDxy,WSSxy,ESSxy,CSLxy,CEUxy,WNNxy,CEDxy,ESExy,CNRxy,CSRxy}。基于所得的雙向映射關(guān)系即可利用2D方向關(guān)系模型對一些重要的3D方向關(guān)系進行表示和處理。在描述形狀復(fù)雜的3D目標(biāo)對象和參照對象的方向關(guān)系時，由于經(jīng)過投影映射這一重要環(huán)節(jié)，對象的復(fù)雜性和細(xì)節(jié)特性在映射后往往被掩蓋了，有時會造成表示誤差。

5 實驗比較與實例分析

5.1 實驗分析

已有的研究成果從不同角度給出了3D方向關(guān)系表示與處理方法。雖然文獻[8-12,17]的方法都適合表示3D方向關(guān)系，但方向關(guān)系的表示和區(qū)分能力各有差別。本文所提出的3DR46模型可表示和區(qū)分246種復(fù)雜的方向關(guān)系，分別是文獻[12,17]所提模型的128倍，是文獻[8-11]所提方法的219倍。進一步，和其他研究成果相比，本文方法更適合處理3D動態(tài)方向關(guān)系，且對3D方向關(guān)系序列的連續(xù)性推導(dǎo)有較強的處理能力。文獻[8-12,17]的方法無法有效處理動態(tài)方向關(guān)系的連續(xù)性檢驗與分析問題。

為了分析本文所提出的動態(tài)方向關(guān)系連續(xù)性檢驗方法的效率，在Pentium4，3.2 GHz CPU，16 GB內(nèi)存，Windows XP環(huán)境下進行了實驗分析。根據(jù)3DR46方向關(guān)系模型的特征和實例模型，所開發(fā)的方向關(guān)系實驗?zāi)M器（DR_MOD3.0）生成的大量交集序列數(shù)據(jù)為本實驗提供了有效的實驗數(shù)據(jù)信息。圖4給出了實驗結(jié)果。

Fig.4 Efficiency analysis of sequence continuity testing algorithms圖4 序列連續(xù)性檢驗算法效率分析

圖4（a）展示了在待檢驗序列數(shù)目遞增，不連續(xù)序列數(shù)分別為1 300、4 100和7 500的情況下的實驗結(jié)果（如曲線l1、l2和l3所示）。橫坐標(biāo)表示待檢驗的序列數(shù)，縱坐標(biāo)表示檢驗和更新的時間耗費。由圖4（a）可知，在不連續(xù)序列數(shù)保持不變的情況下，隨著待檢驗序列數(shù)目的遞增，耗費的代價將逐漸增加；若待檢測的序列集數(shù)不變，序列集中的不連續(xù)序列數(shù)越大，耗費的代價將越大。

在一個規(guī)模較大的序列集中，非連續(xù)序列的分布情況是多樣的。非連續(xù)序列分布情況的不同，檢驗方法的代價將會有很大差別。圖4（b）展示了非連續(xù)序列不同分布情況下的比較情況，其中橫坐標(biāo)表示非連續(xù)序列在序列集中的占比，縱坐標(biāo)γ表示非連續(xù)序列隨機分布情況下的檢驗代價α和正態(tài)分布情況下的檢驗代價β的比值，即γ=α/β。由圖4（b）可知，對于規(guī)模較大的一個序列集，非連續(xù)序列在其中的比重較小時，隨機分布和正態(tài)分布兩種情況下的檢驗代價較為接近，在占比較大的情況下，隨機分布情況下的檢驗代價將遠(yuǎn)大于正態(tài)分布情況下的代價。

5.2 實例分析

Fig.5 Dynamic direction relation graphics in 3DR46 relational model圖5 3DR46關(guān)系模型下的動態(tài)方向關(guān)系圖示

基于理論研究成果，本節(jié)進一步給出模擬實例模型。如圖5所示，在3DR46關(guān)系模型下，3D目標(biāo)對象M1隨時間進行運動（位置變化），Q和M2是3D靜止對象。圖中表示起始時刻的目標(biāo)對象，等表示中間時刻的目標(biāo)對象，表示終止時刻的目標(biāo)對象。曲線l1和l2表示兩條運動路徑及運動方向。

M1若沿著l1由起始位置運動到終點位置，即由變?yōu)椋?DR46方向關(guān)系模型可知其相對于參照對象Q的3D方向關(guān)系共經(jīng)歷了18種不同的方向關(guān)系。以下給出M1在起始時刻t1到終止時刻t2共18個時刻所處的不同的方向塊信息。顯然，該18個時刻分別隸屬于18個連續(xù)時間段，在每個時間段，M1相對于Q的方向關(guān)系保持不變。

基于以上方向塊信息，進一步得出18個方向關(guān)系的交集序列如圖6所示。

Fig.6 Intersection sequences of dynamic direction relations圖6 動態(tài)方向關(guān)系的交集序列

根據(jù)3DR46模型的方向動態(tài)鄰接關(guān)系和算法1，可檢測所得出的交集序列的連續(xù)性。根據(jù)算法1，M1沿著l1運動時，在緊鄰的時刻t6和t7所得的Lt6和Lt7不具有連續(xù)性（Lt7在圖6中用灰色特別標(biāo)出）。具體分析Lt6和Lt7可知，在t6時刻，M1的一部分處于CSRm、CEDm、CEUm等方向塊中；在緊鄰的t7時刻，M1沒有任何部分處于CSRm和CEDm方向塊中，但M1的一部分尚處于CEUm方向塊中。由圖5可知，CSRm和CEUm由CEDm分割開；又由3DR46模型的動態(tài)鄰接關(guān)系可知，CSRm的5個鄰接方向塊為CEDm、CSLm、Sm、Cd和Cu。由此可知，M1沿著l1運動時，M1的一部分不可能由方向塊CSRm跳過CEDm而直接運動到CEUm，故Lt6和Lt7不具有連續(xù)性。

6 結(jié)束語

為了彌補已有方法的不足，本文提出了3DR46方向關(guān)系模型。在目標(biāo)對象的運動情況下詳細(xì)研究了該模型的動態(tài)方向關(guān)系，給出了判斷3D方向關(guān)系動態(tài)連續(xù)性的檢驗算法；進一步研究了參照對象的運動情況下方向關(guān)系的動態(tài)連續(xù)鄰接關(guān)系；在處理一些特殊的3D方向關(guān)系時，為了減少計算冗余和充分利用2D空間方向關(guān)系表示技術(shù)，給出了3DR46方向關(guān)系的雙向映射關(guān)系。理論分析和實驗表明，本文的工作增強了空間數(shù)據(jù)庫對空間方向關(guān)系的表示精度，提高了對靜態(tài)和動態(tài)的復(fù)雜的3D細(xì)節(jié)方向關(guān)系的處理能力。未來的研究重點主要是基于3DR46方向關(guān)系模型構(gòu)建3D方向關(guān)系的空間索引樹，設(shè)計高效的查詢算法以增強空間數(shù)據(jù)庫對復(fù)雜空間方向關(guān)系的查詢能力。