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

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

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

1 引言

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

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

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

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

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

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

3DR46方向關(guān)系模型共包含46個(gè)方向空間元素，其中8個(gè)方向空間元素是封閉空間，該8個(gè)方向空間元素可組成一個(gè)大的封閉空間，參照對(duì)象即處于該封閉空間中；其他38個(gè)方向元素是開(kāi)放空間。3D目標(biāo)對(duì)象可處于任何一個(gè)或幾個(gè)方向空間元素中。3DR46模型中的方向空間元素符號(hào)集合為{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對(duì)象平面投影圖

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

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

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

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

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

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

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

3.1 目標(biāo)對(duì)象運(yùn)動(dòng)的動(dòng)態(tài)方向關(guān)系

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

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

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

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

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

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

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

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

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

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

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

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

算法1DC_DIRECTION(L)

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

3.2 參照對(duì)象運(yùn)動(dòng)的動(dòng)態(tài)方向關(guān)系

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

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

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

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

定義7（動(dòng)態(tài)連續(xù)鄰接關(guān)系）在3DR46方向關(guān)系模型中，基于定義1，設(shè)參照對(duì)象為QO，目標(biāo)對(duì)象為MO，MO相對(duì)于QO的方向關(guān)系在t1,t2,…,tn時(shí)刻分別表示為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為一組動(dòng)態(tài)連續(xù)鄰接關(guān)系。

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

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

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

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

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

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

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

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

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

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

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

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

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

設(shè)參照對(duì)象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)系模型對(duì)一些重要的3D方向關(guān)系進(jìn)行表示和處理。在描述形狀復(fù)雜的3D目標(biāo)對(duì)象和參照對(duì)象的方向關(guān)系時(shí)，由于經(jīng)過(guò)投影映射這一重要環(huán)節(jié)，對(duì)象的復(fù)雜性和細(xì)節(jié)特性在映射后往往被掩蓋了，有時(shí)會(huì)造成表示誤差。

5 實(shí)驗(yàn)比較與實(shí)例分析

5.1 實(shí)驗(yàn)分析

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

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

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

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

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

5.2 實(shí)例分析

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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