3DR39-3d方位關(guān)系模型與反方位關(guān)系

郝曉紅，張麗平，趙齡強(qiáng)，李 松

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

1 概述

作為空間關(guān)系的3大關(guān)系之一，空間方向關(guān)系在空間數(shù)據(jù)庫、地理信息系統(tǒng)、空間數(shù)據(jù)挖掘、空間數(shù)據(jù)查詢、機(jī)器人智能等領(lǐng)域具有重要的作用[1]。

目前，國內(nèi)外對空間方向關(guān)系的研究主要集中在2條主線上[1]：2D空間中的方向關(guān)系表示和推理技術(shù)與3D空間中的方向關(guān)系表示和推理技術(shù)。2D空間中方向關(guān)系的表示模型已經(jīng)較為豐富，研究成果主要有投影模型、錐形模型、四半?yún)^(qū)域模型、最小外接矩形模型、2D-String關(guān)系模型和2D不確定方向關(guān)系模型等。近年在基于MBR模型的2D主方向關(guān)系的表示和推理，以及路徑一致性檢驗(yàn)[2]和方向關(guān)系的組合表示與分析[3-4]等領(lǐng)域也取得了重要的成果。對于3D空間中的方向關(guān)系，由于3D空間對象的復(fù)雜性和多樣性使得3D空間中方向關(guān)系的表示和分析技術(shù)更有難度。3D方向關(guān)系的研究主要集中在3D方向關(guān)系模型的建立、3D方向關(guān)系推理和3D方向關(guān)系查詢等方面。文獻(xiàn)[5]將二維雙十字模型擴(kuò)展到3D空間，以描述3D空間點(diǎn)對象間的方向關(guān)系，但該方法將空間對象全部抽象為點(diǎn)，忽略了空間對象的形狀與大小，在實(shí)際應(yīng)用中具有很大的局限性。文獻(xiàn)[6]將2D主方向關(guān)系拓展到3D空間，建立了一種新的3D方向關(guān)系模型?；谒⒌哪Ｐ瓦M(jìn)一步研究了組合關(guān)系、反向關(guān)系和一致性檢驗(yàn)等重要內(nèi)容。文獻(xiàn)[7]擴(kuò)展了2D空間中開放區(qū)域模型的抽象基類，基于對象方位的2D方向關(guān)系描述模型提出了3D空間中的開放區(qū)域模型。文獻(xiàn)[8]基于對象相交立方體矩陣來描述3D空間中的主方向關(guān)系。文獻(xiàn)[9]基于3DR7模型、3DR27模型和3DR39模型給出3D空間體對象的單方向動態(tài)鄰接關(guān)系表，基于3DR27模型給出方向關(guān)系的雙向映射模型。文獻(xiàn)[10]對3D空間中的3DR44模型進(jìn)行了詳細(xì)研究。但上述模型僅對3D空間進(jìn)行方向劃分，只能對復(fù)雜的3D空間對象進(jìn)行方向關(guān)系的描述，無法對3D空間距離關(guān)系進(jìn)行表示。已有模型在表示和區(qū)分3D方向關(guān)系相同，但位置關(guān)系具有很大差別的空間方位關(guān)系方面具有較大的局限性。模型表示精度在實(shí)際應(yīng)用中有時不理想。

3DR39方向關(guān)系模型的空間劃分較為合理簡明且可擴(kuò)充性較高，該模型具有較大的應(yīng)用價值，但單純利用單一的3DR39方向關(guān)系模型具有較大的局限性。為了彌補(bǔ)已有方法和模型的不足，本文將3DR39方向關(guān)系和距離位置關(guān)系相結(jié)合，提出一種新的3D空間關(guān)系模型，即3DR39-3d方位關(guān)系模型，簡稱3DR39-3d模型。3DR39-3d模型將方向關(guān)系和距離位置關(guān)系進(jìn)行較好的融合，能定性反映3D空間中大量具有方向和位置雙重屬性的復(fù)雜的空間關(guān)系，即3D方位關(guān)系，可表示和區(qū)分2115種復(fù)雜的3D方位關(guān)系。

2 3DR39-3d方位關(guān)系模型

由于3DR39方向關(guān)系模型[9]僅考慮了TO(目標(biāo)對象)與NO(參照對象)之間的定性方向關(guān)系，沒有涉及定性的距離關(guān)系，因此單純利用3DR39方向關(guān)系模型無法進(jìn)一步處理具有距離關(guān)系的復(fù)雜空間方位關(guān)系的表示和區(qū)分問題。例如，圖1中目標(biāo)對象TO1和TO2相對于參照對象NO的方向關(guān)系在3DR39模型中是一樣的，即3DR39模型無法對其進(jìn)一步區(qū)分，但TO1和TO2實(shí)際上相對于參照對象NO的空間關(guān)系具有較大的位置差異。

圖1 3DR39-3d方位關(guān)系模型平面投影

為了進(jìn)一步提升計(jì)算機(jī)對復(fù)雜空間方位關(guān)系的表示和區(qū)分能力，本節(jié)給出3DR39-3d方位關(guān)系模型。

定義1(盒空間)在三維立體空間中，參照對象NO的最小包圍盒(MBB)稱為NO的本體盒，將本體盒向各個方向進(jìn)行均勻擴(kuò)展而得出不同體積的擴(kuò)充盒，記為EB。擴(kuò)充盒的各個面將3D空間分割劃成距離NO遠(yuǎn)近不同的子空間，將這些的子空間統(tǒng)稱為盒空間。

擴(kuò)展盒的數(shù)量不同，劃分的子空間數(shù)相應(yīng)的也不同，本文著重研究基于2個擴(kuò)展盒劃分成的3個盒空間與3DR39方向關(guān)系模型的組合表示與動態(tài)分析問題。如圖1所示，NO的擴(kuò)展盒EB1和EB2將3D空間分成nd,md和fd共3個子空間，nd,md和fd分別定性表示距離NO的近距離空間，較近距離空間和較遠(yuǎn)距離空間。其中，nd和md是封閉的3D距離空間；fd是半封閉的三維距離空間。

定義2(3d距離關(guān)系)設(shè)G={nd,md,fd}表示包含3個盒空間的定性距離關(guān)系符號集，設(shè)2G表示集合G的冪集，則三維空間對象TO(目標(biāo)對象)與NO(參照對象)的距離關(guān)系可表示為二元函數(shù)3d(NO,TO),3d(NO,TO)∈2G。簡稱為3d距離關(guān)系。

由于nd,md和fd是定性劃分的距離空間，因此根據(jù)實(shí)際需要，nd,md和fd可動態(tài)地進(jìn)行調(diào)整(擴(kuò)展或縮小)。例如，EB2不變，EB1擴(kuò)展到圖1中的虛線所示時，則nd相應(yīng)的擴(kuò)大，md縮小，fd保持不變。TO相對于NO的定性的3d距離關(guān)系描述相應(yīng)會受到影響。

將3d距離關(guān)系結(jié)合進(jìn)3DR39方向關(guān)系模型，則進(jìn)一步可得出能更為精細(xì)表示定性距離和方向關(guān)系的3DR39-3d方位關(guān)系模型，如定義3所示。

定義3(3DR39-3d模型的方位關(guān)系)設(shè)距離關(guān)系元素集G={nd,md,fd},g∈G,H={u,d,m},h∈H,DR為3DR39方向關(guān)系模型的方向空間元素集。令gDR={Ed-g,ESEd-g,ESSd-g,Sd-g,WSd-g,WSWd-g,Wd-g,WNWd-g,WNNd-g,Nd-g,ENNd-g,ENEd-g,Em-g,ESEm-g,ESSm-g,Sm-g,WSSm-g,WSWm-g,Wm-g,WNWm-g,WNNm-g,Nm-g,ENNm-g,ENEm-g,Eu-g,ESEu-g,ESSu-g,Su-g,WSSu-g,WSWu-g,Wu-g,WNWu-g,WNNu-g,Nu-g,ENNu-g,ENEu-g,Cu-g,Cu-g,Cm-nd}，設(shè)2gDR表示gDR的冪集，則三維空間對象TO(目標(biāo)對象)與NO(參照對象)的方位關(guān)系可表示為二元函數(shù)3DIR39-3d(NO,TO),3DIR39-3d(NO,TO)∈2gDR。圖1展示了3DR39-3d方位關(guān)系的平面投影。

在定義3中，gDR中的各項(xiàng)表示基于3d距離關(guān)系結(jié)合進(jìn)3DR39方向關(guān)系模型劃分的更細(xì)方位空間元素。每個方位空間元素由距離關(guān)系集{nd,md,fd}和層標(biāo)識集{u,d,m}聯(lián)合表示。例如，在圖1中，Nh-md即表示Nd-md,Nu-md,Nm-md這3個方位空間元素的平面投影。3D439-3d方位關(guān)系模型將3D空間劃分為3層，本文用u,d,m表示，每層包含大量的方位空間元素，每個空間元素的距離信息由nd,md,fd來表示。例如，WSWu-md，即表示第u層，定性距離為md的3D空間方位元素WSW。

基于定義3，可給出三維空間對象TO(目標(biāo)對象)與NO(參照對象)的方位關(guān)系交集序列：T1={Ed-g∩NO,ESEd-g∩NO,ESSd-g∩NO,Sd-g∩NO,WSd-g∩NO,WSWd-g∩NO,Wd-g∩NO,WNWd-g∩NO,WNNd-g∩NO,Nd-g∩NO,ENNd-g∩NO,ENEd-g∩NO,Em-g∩NO,ESEm-g∩NO,ESSm-g∩NO,Sm-g∩NO,WSSm-g∩NO,WSWm-g∩NO,Wm-g∩NO,WNWm-g∩NO,WNNm-g∩NO,Nm-g∩NO,ENNm-g∩NO,ENEm-g∩NO,Eu-g∩NO,ESEu-g∩NO,ESSu-g∩NO,Su-g∩NO∩NO,WSSu-g∩NO,WSWu-g∩NO,Wu-g∩NO,WNWu-g∩NO,WNNu-g∩NO,Nu-g∩NO,ENNu-g∩NO,ENEu-g∩NO,Cu-g∩NO,Cu-g∩NO,Cm-nd∩NO}。

由G={nd,md,fd},g∈G可知，將g由nd,md和fd代換，T1可進(jìn)一步展開描述。由T1的定義可知，T1交集序列共含有115個交集項(xiàng)，其0,1串所能表達(dá)的3D空間中的方位關(guān)系將高達(dá)2115種，進(jìn)一步增強(qiáng)了方位關(guān)系的表示精度。

3 3DR39-3d模型的動態(tài)方位關(guān)系

目標(biāo)對象TO相對于參照對象NO的方位關(guān)系往往不是靜止不變的，TO和NO的運(yùn)動均能導(dǎo)致方位關(guān)系發(fā)生變化。探討方位關(guān)系的動態(tài)變化規(guī)律具有重要意義。本節(jié)對基于對象運(yùn)動的動態(tài)方位關(guān)系和基于盒空間擴(kuò)張的動態(tài)方位關(guān)系進(jìn)行了研究。

3.1 基于對象運(yùn)動的動態(tài)方位關(guān)系

目標(biāo)對象或參照對象的位置隨時間往往會發(fā)生動態(tài)的變化，例如，在圖1中，目標(biāo)對象TO3由t1時刻到t2時刻運(yùn)動到TO′3，在t1時刻，TO3所處的方位空間元素集FE1為{ENNu-fd,ENNu-md,ENNu-nd,ENNm-fd,ENNm-md,ENNm-nd,ENNd-fd,ENNd-md,ENNd-nd,Nu-fd,Nm-md,Nd-nd}；在t2時刻，目標(biāo)對象所處的方位空間元素集FE2為{WNNu-fd,WNNm-fd,WNNd-fd,WNWu-fd,WNWm-fd,WNWd-fd}。t1時刻到t2時刻，TO3相對于NO的方位關(guān)系發(fā)生了較為顯著的變化，其經(jīng)歷的中間方位關(guān)系則更為復(fù)雜、多樣。由于較為復(fù)雜的空間方位關(guān)系均可分解成目標(biāo)對象相對于參照對象的各個方位空間元素的空間關(guān)系，方位關(guān)系的變化即是所處的相關(guān)方位空間元素的動態(tài)改變。方位空間元素的動態(tài)改變進(jìn)一步可分解為一系列方位空間元素的動態(tài)鄰接關(guān)系的變化。

在本文中，某方位關(guān)系的下一鄰接方位關(guān)系定義為該空間方位關(guān)系由一個狀態(tài)不經(jīng)過中間方位關(guān)系直接轉(zhuǎn)變?yōu)榈目臻g方位關(guān)系。利用枚舉和逐一排除法，本節(jié)給出3DR39-3d模型的部分方位空間元素的動態(tài)鄰接關(guān)系，如表1所示。表1展示了3DR39-3d模型中的m層方位空間元素的動態(tài)鄰接關(guān)系。根據(jù)3DR39-3d模型的動態(tài)鄰接關(guān)系，進(jìn)一步可對復(fù)雜對象的動態(tài)方位關(guān)系變化情況進(jìn)行分析、預(yù)測、排錯和擇優(yōu)。例如，沿圖1的曲線運(yùn)動，若根據(jù)數(shù)據(jù)信息所得出TO3在t1時刻的下一緊鄰時刻t′1所處的動態(tài)鄰接方位空間元素集FE3為{Nu-fd,Nu-md,Nu-nd,Nm-fd,Nm-md,Nm-nd,Nd-fd,Nd-md,Nd-nd}。則由動態(tài)鄰接方位關(guān)系表(表1)對其進(jìn)行檢測分析可知，TO3在t1時刻所處的方位空間元素集FE1在下一緊鄰時刻不能直接轉(zhuǎn)變?yōu)镕E3，直接轉(zhuǎn)變成的方位空間元素集應(yīng)為{ENNu-fd,ENNu-md,ENNu-nd,ENNm-fd,ENNm-md,ENNm-nd,ENNd-fd,ENNd-md,ENNd-nd,Nu-nd,Nm-nd,Nd-nd,Nu-md,Nm-md,Nd-md}。從而說明FE3有誤，需重新收集方位信息進(jìn)行分析。

表1 3DR39-3d模型的部分方位動態(tài)鄰接關(guān)系

3.2 基于盒空間擴(kuò)張的動態(tài)方向關(guān)系

在實(shí)際應(yīng)用中，nd,md和fd等 3個定性距離空間經(jīng)常會進(jìn)行定性調(diào)整，即盒空間大小會發(fā)生動態(tài)的變化(擴(kuò)張或縮小)。盒空間的變化將會導(dǎo)致部分相關(guān)的方位空間元素集相應(yīng)發(fā)生動態(tài)改變。從而，將會對目標(biāo)對象TO相對于參照對象NO的空間方位關(guān)系產(chǎn)生動態(tài)的實(shí)質(zhì)性影響。

在3DR39-3d模型中，nd,md和fd的變化是由擴(kuò)展盒EB1和EB2的變化決定的。EB1和EB2變化分為(EB1擴(kuò)張，EB2擴(kuò)張)，(EB1擴(kuò)張，EB2縮小)，(EB1擴(kuò)張，EB2恒定)，(EB1縮小，EB2擴(kuò)張)，(EB1縮小，EB2縮小)，(EB1縮小，EB2恒定)共6種情況。每種情況都會引起部分方位空間元素發(fā)生相應(yīng)的變化?；?DR39-3d模型方位空間的劃分和分布，表2給出了(EB1擴(kuò)張，EB2不變)所引起的方位空間元素變化和動態(tài)遷移規(guī)律。其他情況的方位空間元素的動態(tài)變化規(guī)律可類似得出。表2中的“↓”表示相應(yīng)的方位空間元素變小，“↑”表示相應(yīng)的方位空間元素變大；“→”表示方位空間動態(tài)遷移。

表2 方位空間元素的變化和動態(tài)遷移

4 3DR39-3d模型的反方位關(guān)系

現(xiàn)實(shí)中，由于應(yīng)用的需求，空間參照對象NO和空間目標(biāo)對象TO的角色往往會經(jīng)常變換。即確定TO相對于NO的空間方位關(guān)系的問題和確定NO相對于TO的空間方位關(guān)系的問題均有可能出現(xiàn)。如圖2所示，NO2,NO3,NO4相對與NO1具有各自的空間方位關(guān)系，相反，NO1相對于NO2,NO3,NO4也具有不同的空間方位關(guān)系。

圖2 3DR39-3d反關(guān)系模型平面投影示例

基于定義3，在3DR39-3d方位關(guān)系模型中，將方位關(guān)系3DR39-3d(TO,NO)稱為3DR39-3d(NO,TO)的反方位關(guān)系，簡稱反關(guān)系。若基于每個空間對象均建立3DR39-3d模型，進(jìn)而對其進(jìn)行方位關(guān)系的表示和確定，則在空間對象數(shù)量較少時效率較高，在需要確定大量的空間對象間的方位關(guān)系及其反關(guān)系時，計(jì)算量將顯著增大。由于復(fù)雜的空間方位關(guān)系的反關(guān)系可分解為基本方位空間元素的反關(guān)系，因此表3進(jìn)一步給出了3DR39-3d模型的基本方位空間元素的反關(guān)系。利用基本方位空間元素的反關(guān)系的組合即可在不需要對每個空間對象都建立3DR39-3d模型的情況下推理得出復(fù)雜的空間方位關(guān)系的反關(guān)系。

表3 部分3DR39-3d模型基本方位空間元素的反關(guān)系

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

本節(jié)從關(guān)系模型及處理方法的表示能力、靜態(tài)和動態(tài)的針對性，反關(guān)系推導(dǎo)能力等方面和已有研究成果進(jìn)行了對比。比較結(jié)果如表4所示。方法1～方法6分別表示文獻(xiàn)[5]～文獻(xiàn)[10]采用的方法?！啊獭北硎鞠鄳?yīng)方法適用；“×”表示不適用。本文基于3DR39方向關(guān)系和3d距離關(guān)系的結(jié)合所提出的3DR39-3d模型可表示和區(qū)分2115種復(fù)雜的方向關(guān)系，較已有的方法具有更強(qiáng)的表示能力。進(jìn)一步的，和其他研究成果相比，本文方法更適合處理3D動態(tài)方向關(guān)系，且對3D方位關(guān)系的反關(guān)系推導(dǎo)具有較強(qiáng)的處理能力。

表4 典型方法比較

為了分析本文所研究方法的效率，在Pentium 4,3.2 GB CPU，4 GB內(nèi)存，Windows XP環(huán)境下，利用C++builder 6.0進(jìn)行了實(shí)驗(yàn)比較分析。圖3給出了利用動態(tài)方位鄰接關(guān)系進(jìn)行方位關(guān)系判斷排錯的實(shí)驗(yàn)結(jié)果。其中，橫坐標(biāo)表示動態(tài)方位空間元素集的個數(shù)，縱坐標(biāo)表示利用本文所研究的動態(tài)方位鄰接關(guān)系進(jìn)行計(jì)算推導(dǎo)的效率和對每個動態(tài)方位空間元素集中的每個空間方位元素進(jìn)行逐一計(jì)算的效率之比。由圖3可知，當(dāng)動態(tài)方位空間元素集的數(shù)目較少時，2種方法的效率差別不大，但當(dāng)元素集數(shù)目逐漸增多時，利用動態(tài)方位鄰接關(guān)系進(jìn)行方位關(guān)系的判斷排錯具有更為顯著的計(jì)算優(yōu)勢。

圖3 動態(tài)方位關(guān)系計(jì)算效率

圖4給出了方位關(guān)系的反關(guān)系計(jì)算效率比較結(jié)果。其中，橫坐標(biāo)表示由目標(biāo)對象變換為參照對象的空間對象個數(shù)，縱坐標(biāo)表示利用本文所提出的基本方位空間元素的反關(guān)系進(jìn)行計(jì)算推導(dǎo)的效率和對每個空間對象都建立3DR39-3d模型進(jìn)行計(jì)算的效率之比。

圖4 方位空間關(guān)系的反關(guān)系計(jì)算效率

由圖4可知，在所轉(zhuǎn)變角色的空間對象個數(shù)較少時，2種方法計(jì)算反關(guān)系的效率差異較?。坏?dāng)空間對象的個數(shù)較多時，利用基本方位空間元素的反關(guān)系的組合推理計(jì)算復(fù)雜的空間方位關(guān)系的反關(guān)系效率較高。

6 結(jié)束語

本文將3DR39方向關(guān)系模型和3d距離關(guān)系模型結(jié)合，提出了3DR39-3d方位關(guān)系模型，增強(qiáng)了三維方位關(guān)系的表示精度；詳細(xì)研究了3DR39-3d方位關(guān)系模型的動態(tài)方位關(guān)系的表示和分析方法；給出了3DR39-3d模型的基本方位空間元素的反關(guān)系。利用基本方位空間元素的反關(guān)系組合即可在不需要對每個空間對象都建立3DR39-3d模型的情況下推理得出復(fù)雜空間方位關(guān)系的反關(guān)系。本文的研究成果作為基礎(chǔ)理論框架模型的一部分，已應(yīng)用于所開發(fā)的空間關(guān)系模擬分析軟件SR-3中。下一步研究重點(diǎn)主要是將Vague區(qū)域關(guān)系[11-12]進(jìn)行擴(kuò)展，結(jié)合3DR39-3d方位關(guān)系模型以處理復(fù)雜的不確定3D空間方位關(guān)系問題。

[1]李 松,張麗平.空間關(guān)系查詢與分析[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2011.

[2]Cicerone S,Felice P D.Cardinal Directions Between Spatial Objects:The Pairwise Consistency Problem[J].Informatics and Sciences,2004,164(1/4):165-188.

[3]Skiadopoulos S,Koubarakis M.Composing Cardinal Direction Relations[J].Artificial Intelligence,2004,152(2):143-171.

[4]Schockaert S,de Cock M,Kerre E E.Modelling Nearness and Cardinal Directions Between Fuzzy Regions[C]//Proc.of IEEE World Congress on Computational Intelligence.[S.l.]:IEEE Press,2008:1548-1555.

[5]Pacheco J,Escrig M T,Toledo F.Integrating 3D Orientation Models[C]//Proc.of the5th Catalonian Conference on Artificial Intelligence.Castellon,Spain:[s.n.],2002:88-100.

[6]Chen Juan,Liu Dayou,Jia Haiyang,et al.Cardinal Direction Relations in 3D Space[C]//Proc.of the 2nd International Conference on Knowledge Science,Engineering and Management.Melbourne,Australia:[s.n.],2007:623-629.

[7]Liu Yongshan,Gao Shiwei,Wang Dechen,et al.Open Shape Model Based on Absolute Frame in Three-dimensional Space[J].Innovative Computing,Information and Control Express Letters,2009,3(3(B)):599-605.

[8]Chen Tao,Schneider M.Modeling Cardinal Directions in the 3D Space with the Objects Interaction Cube Matrix[C]//Proc.of ACM Symposium on Applied Computing.New York,USA:[s.n.],2010:906-910.

[9]張麗平,李 松.3D對象動態(tài)方位鄰接關(guān)系及雙向關(guān)聯(lián)表示[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(29):68-71.

[10]郝曉紅,張麗平,李 松.三維空間中3DRR44方向關(guān)系表示模型[J].計(jì)算機(jī)工程,2011,37(1):75-77.

[11]李 松,郝忠孝.基于Vague集的含洞不規(guī)則Vague區(qū)域關(guān)系[J].計(jì)算機(jī)研究與發(fā)展,2009,46(5):823-831.

[12]張麗平,李 松,郝曉紅,等.Jrv粗糙Vague區(qū)域關(guān)系[J].浙江大學(xué)學(xué)報(bào):工學(xué)版,2012,46(1):105-111.