3DR39-3d方位關系模型與反方位關系

郝曉紅，張麗平，趙齡強，李 松

(哈爾濱理工大學計算機科學與技術學院，哈爾濱 150080)

1 概述

作為空間關系的3大關系之一，空間方向關系在空間數據庫、地理信息系統、空間數據挖掘、空間數據查詢、機器人智能等領域具有重要的作用[1]。

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

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

2 3DR39-3d方位關系模型

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

圖1 3DR39-3d方位關系模型平面投影

為了進一步提升計算機對復雜空間方位關系的表示和區分能力，本節給出3DR39-3d方位關系模型。

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

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

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

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

將3d距離關系結合進3DR39方向關系模型，則進一步可得出能更為精細表示定性距離和方向關系的3DR39-3d方位關系模型，如定義3所示。

定義3(3DR39-3d模型的方位關系)設距離關系元素集G={nd,md,fd},g∈G,H={u,d,m},h∈H,DR為3DR39方向關系模型的方向空間元素集。令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}，設2gDR表示gDR的冪集，則三維空間對象TO(目標對象)與NO(參照對象)的方位關系可表示為二元函數3DIR39-3d(NO,TO),3DIR39-3d(NO,TO)∈2gDR。圖1展示了3DR39-3d方位關系的平面投影。

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

基于定義3，可給出三維空間對象TO(目標對象)與NO(參照對象)的方位關系交集序列：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可進一步展開描述。由T1的定義可知，T1交集序列共含有115個交集項，其0,1串所能表達的3D空間中的方位關系將高達2115種，進一步增強了方位關系的表示精度。

3 3DR39-3d模型的動態方位關系

目標對象TO相對于參照對象NO的方位關系往往不是靜止不變的，TO和NO的運動均能導致方位關系發生變化。探討方位關系的動態變化規律具有重要意義。本節對基于對象運動的動態方位關系和基于盒空間擴張的動態方位關系進行了研究。

3.1 基于對象運動的動態方位關系

目標對象或參照對象的位置隨時間往往會發生動態的變化，例如，在圖1中，目標對象TO3由t1時刻到t2時刻運動到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時刻，目標對象所處的方位空間元素集FE2為{WNNu-fd,WNNm-fd,WNNd-fd,WNWu-fd,WNWm-fd,WNWd-fd}。t1時刻到t2時刻，TO3相對于NO的方位關系發生了較為顯著的變化，其經歷的中間方位關系則更為復雜、多樣。由于較為復雜的空間方位關系均可分解成目標對象相對于參照對象的各個方位空間元素的空間關系，方位關系的變化即是所處的相關方位空間元素的動態改變。方位空間元素的動態改變進一步可分解為一系列方位空間元素的動態鄰接關系的變化。

在本文中，某方位關系的下一鄰接方位關系定義為該空間方位關系由一個狀態不經過中間方位關系直接轉變為的空間方位關系。利用枚舉和逐一排除法，本節給出3DR39-3d模型的部分方位空間元素的動態鄰接關系，如表1所示。表1展示了3DR39-3d模型中的m層方位空間元素的動態鄰接關系。根據3DR39-3d模型的動態鄰接關系，進一步可對復雜對象的動態方位關系變化情況進行分析、預測、排錯和擇優。例如，沿圖1的曲線運動，若根據數據信息所得出TO3在t1時刻的下一緊鄰時刻t′1所處的動態鄰接方位空間元素集FE3為{Nu-fd,Nu-md,Nu-nd,Nm-fd,Nm-md,Nm-nd,Nd-fd,Nd-md,Nd-nd}。則由動態鄰接方位關系表(表1)對其進行檢測分析可知，TO3在t1時刻所處的方位空間元素集FE1在下一緊鄰時刻不能直接轉變為FE3，直接轉變成的方位空間元素集應為{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有誤，需重新收集方位信息進行分析。

表1 3DR39-3d模型的部分方位動態鄰接關系

3.2 基于盒空間擴張的動態方向關系

在實際應用中，nd,md和fd等 3個定性距離空間經常會進行定性調整，即盒空間大小會發生動態的變化(擴張或縮小)。盒空間的變化將會導致部分相關的方位空間元素集相應發生動態改變。從而，將會對目標對象TO相對于參照對象NO的空間方位關系產生動態的實質性影響。

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

表2 方位空間元素的變化和動態遷移

4 3DR39-3d模型的反方位關系

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

圖2 3DR39-3d反關系模型平面投影示例

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

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

5 模型比較與實驗分析

本節從關系模型及處理方法的表示能力、靜態和動態的針對性，反關系推導能力等方面和已有研究成果進行了對比。比較結果如表4所示。方法1～方法6分別表示文獻[5]～文獻[10]采用的方法。“√”表示相應方法適用；“×”表示不適用。本文基于3DR39方向關系和3d距離關系的結合所提出的3DR39-3d模型可表示和區分2115種復雜的方向關系，較已有的方法具有更強的表示能力。進一步的，和其他研究成果相比，本文方法更適合處理3D動態方向關系，且對3D方位關系的反關系推導具有較強的處理能力。

表4 典型方法比較

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

圖3 動態方位關系計算效率

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

圖4 方位空間關系的反關系計算效率

由圖4可知，在所轉變角色的空間對象個數較少時，2種方法計算反關系的效率差異較小；但當空間對象的個數較多時，利用基本方位空間元素的反關系的組合推理計算復雜的空間方位關系的反關系效率較高。

6 結束語

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

[1]李 松,張麗平.空間關系查詢與分析[M].哈爾濱:哈爾濱工業大學出版社,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對象動態方位鄰接關系及雙向關聯表示[J].計算機工程與應用,2009,45(29):68-71.

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

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

[12]張麗平,李 松,郝曉紅,等.Jrv粗糙Vague區域關系[J].浙江大學學報:工學版,2012,46(1):105-111.