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

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

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

2.哈爾濱工業大學計算機科學與技術學院，哈爾濱150001

1 引言

隨著信息技術的快速發展，空間數據對象信息的海量性、復雜性、不確定性和多態性對空間方向關系的表示和處理技術提出了越來越高的要求。

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

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

為了對復雜的3D方向關系進行更為精細化的表示和推理，本文提出了一種新的3D空間方向關系模型，即3DR46方向關系模型，3DR46方向關系模型可表示和區分246種3D方向關系；基于3DR46方向關系模型進一步對動態3D方向關系和模型的雙向映射關系進行了系統研究。

2 3DR46方向關系模型

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

3DR46方向關系模型共包含46個方向空間元素，其中8個方向空間元素是封閉空間，該8個方向空間元素可組成一個大的封閉空間，參照對象即處于該封閉空間中；其他38個方向元素是開放空間。3D目標對象可處于任何一個或幾個方向空間元素中。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中方向空間元素具有嚴格的先后順序。

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

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

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

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

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

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

3 3DR46模型的動態方向關系

3D方向關系的動態變化性主要分為兩類：目標對象的動態性所導致的方向關系的動態變化；參照對象的動態性所引起的方向關系的動態變化。

3.1 目標對象運動的動態方向關系

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

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

基于3DR46方向關系模型，定義3給出了動態鄰接方向塊和動態鄰接關系的概念。

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

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

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

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

定義5（鄰位方向塊）在3DR46方向關系模型中，設參照對象為QO，目標對象為MO，MO的主位方向塊集為CM。和CM中的主位方向塊分別具有動態鄰接關系的非主位方向塊稱為基于MO的鄰位方向塊。由MO的所有鄰位方向塊構成的集合稱為MO的鄰位方向塊集，記作PM。

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

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

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

基于以上討論，進一步給出動態方向關系連續性判定的檢驗算法如算法1所示。

算法1DC_DIRECTION(L)

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

3.2 參照對象運動的動態方向關系

現實中，3D參照對象QO往往也會發生動態運動，從而目標對象MO相對于動態參照QO的3D方向關系也會相應發生動態變化。參照對象QO的位置變化使得MO相對QO已有的方向關系信息變得無效，大量方向關系信息需要修正和重新確定。

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

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

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

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

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

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

Fig.3 Dynamic continuous adjacency relations of typical principal direction motion圖3 典型主方向運動動態連續鄰接關系

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

4 3DR46方向關系模型雙向映射關系

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

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

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

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

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

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

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

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

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

5 實驗比較與實例分析

5.1 實驗分析

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

為了分析本文所提出的動態方向關系連續性檢驗方法的效率，在Pentium4，3.2 GHz CPU，16 GB內存，Windows XP環境下進行了實驗分析。根據3DR46方向關系模型的特征和實例模型，所開發的方向關系實驗模擬器（DR_MOD3.0）生成的大量交集序列數據為本實驗提供了有效的實驗數據信息。圖4給出了實驗結果。

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

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

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

5.2 實例分析

Fig.5 Dynamic direction relation graphics in 3DR46 relational model圖5 3DR46關系模型下的動態方向關系圖示

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

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

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

Fig.6 Intersection sequences of dynamic direction relations圖6 動態方向關系的交集序列

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

6 結束語

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