空間方向關系模型比較

1、空間方向關系模型分析 顏芬第一作者及通訊作者：顏芬，碩士生。Email:896211086* 李精忠1（1 武漢大學資源與環(huán)境科學學院，武漢市珞瑜路129號，430079）摘要：空間方向關系是空間關系的重要內容，是地理信息系統(tǒng)的基礎理論之一。在地圖制圖、計算機輔助設計、圖像和多媒體數據庫以及地理信息系統(tǒng)等領域中有著廣泛的應用。本文著重于詳細介紹目前主要的空間方向關系形式化描述模型的原理、優(yōu)缺點、適用性，分析目前存在的問題以及為未來空間方向關系模型的研究探討可行方向。關鍵詞：方向關系；空間關系；形式化描述模型；地理信息系統(tǒng)；空間分析1 介紹空間數據庫是一門前沿的交叉學科，也是近年來的熱點研究領域

2、1?？臻g數據庫中，空間數據的空間關系的表示和處理在地圖制圖、計算機輔助設計、圖像和多媒體數據庫以及地理信息系統(tǒng)等領域中有著廣泛的應用?？臻g方向關系作為地理信息系統(tǒng)中最為重要的空間關系之一2，在空間數據建模、空間查詢、空間分析、空間推理、制圖綜合和地圖解譯等研究工作中起著重要作用，空間方向關系模型是計算和表達目標間方向關系的重要工具，是空間方向關系理論研究的重點和難點3?？臻g方向關系模型考慮的基本問題是如何有效地建立描述空間方向關系的形式化模型4。描述空間方向關系的模型主要有錐形模型、基于投影的模型、基于Voronoi圖的模型，統(tǒng)計模型和基于點群分割的模型等。錐形模型主要包括四方向、八方向和三角

3、化等；基于投影的模型主要有MBR(Minimum Boundary Rectangle)模型和方向關系矩陣模型等；基于Voronoi圖的模型主要包括基于MBR Voronoi圖模型和方向Voronoi圖模型等。描述空間方向關系的方法可分為定性描述和定量描述。目前定性描述的空間方向關系模型主要有錐形模型、MBR模型和基于MBR Voronoi圖模型等；定量描述的空間方向關系模型主要有方向關系矩陣模型、方向Voronoi圖模型、統(tǒng)計模型和基于點群分割的模型等。用于定性計算的模型是基于對圖形的概括進行計算分析，因而存在一定的粗糙性，并且受目標之間距離、自身形狀以及人的主觀因素影響較大；用于定量計算的

4、模型比用于定性計算的模型對空間目標的空間方向關系描述得更加準確，且受目標之間距離和自身形狀等因素小，但往往計算要復雜得多。本文著重于詳細介紹目前主要的空間方向關系形式化描述模型的原理、優(yōu)點、缺點、適用性，了解空間方向關系模型研究的歷程，以及為今后空間方向關系模型的研究探討可行方向。2 空間方向關系模型2.1 錐形模型錐形模型由Haar5提出，其主要思想是將空間目標及其周圍的區(qū)域分成帶有方向性的幾個區(qū)域，通過各目標本身及方向區(qū)域之間的交的結果來描述空間方向關系，具有代表性的是四方向、八方向和三角化模型。錐形模型的優(yōu)點是原理簡單，易于編程實現(xiàn)。其缺點在于對空間目標間距離和自身形狀的特定組合會給出不

5、準確的描述6。2.1.1 四方向四方向錐形模型是以某一空間目標為參考目標，以東西南北方向線為軸將空間目標及周圍的區(qū)域等分成四個方向區(qū)域來定義方向關系，如圖1所示，以參考點O為中心，將空間區(qū)域分為E、S、W、N四個方向區(qū)域，用其他空間目標與這些方向區(qū)域間的位置關系來描述空間目標間的方向關系。如圖1所示，四方向錐形模型的局限性在于對于狹長的面狀物體A，以其質心為參考點O，源目標B相對于參考目標A的方向關系為：Dir(A，B)=N，而這與現(xiàn)實中人的認知是不相符的，人一般會認為B在A的東方。圖1 四方向錐形模型Fig. 1 Cone-based Model of four directions2.1.

6、1 八方向八方向錐形模型是以某一空間目標為參考目標，以東西南北方向線以及四方向錐形模型邊界線為軸將空間目標及周圍的區(qū)域分成八個方向區(qū)域定義方向關系。以參考點O為中心，將空間區(qū)域分為E、SE、S、SW、W、NW、N、NE八個方向區(qū)域，用其他空間目標與這些方向區(qū)域間的位置關系來描述空間目標間的方向關系。與四方向錐形模型相比，八方向錐形模型能更精確描述空間目標間的方向關系。但八方向錐形模型有與四方向錐形模型相同的局限性，對于狹長的面狀物體A，以其質心為參考點O，源目標B相對于參考目標A的方向關系為：Dir(A，B)=NE，而這與現(xiàn)實中人的認知是不相符的，人一般會認為B在A的東方7。圖2 八方向錐形模

7、型Fig. 2 Cone-based Model of eight directions2.1.3 三角化三角化模型是四方向錐形模型和八方向錐形模型的擴展。基本思想是從空間目標的某點出發(fā)，沿所需要的方向作兩條射線形成一個三角形方向區(qū)域，從而描述與計算目標間的方向關系。三角化錐形模型一定程度上顧及了空間目標的形狀和大小對空間方向關系的影響，克服了四方向錐形模型和八方向錐形模型的不足，提高了空間目標距離較近的情況下對空間方向關系的區(qū)分能力。但對于某些特定形狀的面狀物體A，如圖3所示，根據人的認知原理，源目標B處于參考目標A的東北方，這是三角化模型不能識別出來的。圖3 三角化錐形模型Fig. 3 T

8、riangulated cone-based Model2.2 基于投影的模型基于投影的模型與錐形模型最大的不同之處在于對區(qū)域的劃分，錐形模型選擇參考點來劃分區(qū)域，而基于投影的模型是指將空間目標投影到特定的坐標軸上，通過各目標投影間的關系去描述與定義方向關系，通過空間目標在水平軸和垂直軸上的投影，可以將空間分為E、S、W、N、O、NE、SE、SW、NW 9個方向區(qū)域?，F(xiàn)在運用范圍比較廣且具有代表性的是MBR模型和方向關系矩陣模型?；谕队暗哪Ｐ洼^好地顧及了參考目標的形狀和大小對方向關系的影響，在一定程度上克服了錐形模型存在的缺陷，但對空間目標的空間方向關系的推斷仍然受目標間距離的影響。2.2.

9、1 MBR模型MBR模型由D.Papadias等提出8，主要思想是通過空間目標最小外接矩形之間的方向關系來判定空間目標間的方向關系。該模型在水平方向和垂直方向上各能表達13種空間方向關系，因此能夠區(qū)分169種空間方向關系。該模型常用來作為空間目標拓撲關系判定的過濾器。當用于方向關系描述的時候，通常用來表達9個主要方向：E、S、W、N、O、NE、SE、SW、NW。MBR模型在一定程度上減小了空間目標的形狀和大小對判斷方向關系的影響，但當空間目標的最小外接矩形有重疊部分時，MBR模型不再適用。如圖4所示，參考目標A和源目標B的最小外接矩形部分重疊，難以判斷A和B的方向關系。圖4 MBR模型Fig.

10、 4 MBR Model2.2.2 方向關系矩陣模型方向關系矩陣模型可以判斷具有重疊最小外接矩形區(qū)域的目標之間的空間方向關系。該模型由Goyal等提出9，主要思想是以空間目標最小外接矩形為參考方向，將空間劃分為9個方向區(qū)域，以源目標與各方向區(qū)域的交疊情況為元素構成一個方向關系矩陣來描述與定義空間目標間的方向關系。在方向關系矩陣模型中，只建立參考目標的最小外接矩形，而源目標還是它的實際形狀。方向關系矩陣可以分為兩種，一種是粗略的方向關系矩陣，僅僅記錄源目標與參考目標的各方向區(qū)域是否相交，如圖5所示，源目標B相對于參考目標A的方向關系為：Dir(A，B)=N，NE，E，另一種是詳細的方向關系矩陣，

11、記錄源目標落在每個方向區(qū)域的面積比率，如圖所示，源目標B相對于參考目標A的方向關系為：B的25%在A的北方（N），50%在A的東北方（NE），25%在A的東方（N）。方向關系矩陣的局限性在于描述空間目標的空間方向關系的模糊性過大，且計算較復雜。圖5 方向關系矩陣模型Fig. 5 Direction relation matrix model2.3 基于Voronoi圖的模型基于Voronoi圖的模型的基本思想通過空間目標的Voronoi圖與空間目標的關系來描述和定義空間目標間的方向關系。與錐形模型、基于投影的模型和MBR模型相比，基于Voronoi圖的模型在方向關系描述準確性方面占有優(yōu)勢，適合

12、于對各種情況下空間目標間方向關系的精確描述。但基于Voronoi圖的模型受可視域限制, 對遮擋部分的圖形變化不敏感，角度不能隨著可視域外部分的圖形變化而發(fā)生變化，且基于Voronoi圖的模型的計算相對比較復雜。 2.3.1 基于MBR Voronoi圖模型李成名等10在空間目標MBR的基礎上建立Voronoi區(qū)域，通過空間目標MBR與Voronoi區(qū)域邊界線之間的關系來描述空間目標之間的方向關系。如圖6所示，一個空間實體A的最小矩形有4條邊分別表示為de= eastedge(A)、dw=westedge(A)、dn=northedge(A)和ds = southedge(A)。若將4條邊看作4

13、個線(Line)生成元，生成的4個Voronoi區(qū)分別為voronoi(de)、voronoi(dw)、voronoi(dn)和voronoi(ds)。NE、NW、SW和SE分別為邊de、dn、dw和ds的Voronoi多邊形的邊界，空間實體A的東部E(A)定義為de、SE和NE圍成的區(qū)域，空間實體A西部W(A)定義為dw、SW、NW圍成的區(qū)域，空間實體A的北部N(A)定義為dn、NE、NW圍成的區(qū)域，空間實體A的南部S(A)定義為ds、SE、SW圍成的區(qū)域。圖5 方向關系矩陣模型Fig. 5 Direction relation matrix model空間實體A和B之間的方向關系可以利用空

14、間實體的最小矩形邊和Voronoi多邊形的邊界線構成的5×5矩陣形式化描述表達，矩形的形式如式(1)，在式(1)中，NEA表示空間實體A的北-東線，NEB表示空間實體B的北-東線，BA表示空間實體A的最小矩形的邊，其余類似。基于此，基于MBR Voronoi圖模型可以表達目標間的八種主要方向：E、S、W、N、NE、SE、SW、NW。 （1）該模型對目標間的方向關系的描述較為精確，局限性在于不能處理兩目標纏繞交疊等復雜情況。2.3.2 方向Voronoi圖模型方向Voronoi圖模型通過計算用于表示目標間指向線法線的Voronoi圖得到目標間精確的方向關系11。該模型考慮了兩目標之間方

15、向關系的各個側面，用多個方向的集合（即多條指向線）來描述目標間的方向關系。該模型的構建包括以下四個步驟：1）目標圖形的綜合；2）可視區(qū)域的確定；3）空間方向的定量計算；4）定性描述結論的確定。如圖6a所示，粗實線L1L2是參考目標A與源目標B之間的方向Voronoi圖，它所描述的空間方向關系是：B的78%位于A的北面，22%位于A的東北面，或者描述為B位于A的北面。與其他模型相比，該模型最大的優(yōu)勢在于受兩目標的大小和距離等的影響很小，在絕大多數情況下總能得到精確的計算結果。該模型的局限性在于當不可視部分變化時，難以準確描述空間方向關系的變化12。如圖6a和圖6b所示，源目標B對參考目標A的不可

16、視部分發(fā)生變化，但根據該模型， B相對于A的方向關系不變。圖6 方向Voronoi圖Fig. 6 Direction Voronoi model2.4 統(tǒng)計模型鄧敏等13學者提出一種基于分解與組合的思想來分析空間目標間的方向關系。首先，將空間目標分解成更細小的基本單元。如果忽略這些細小單元的大小，那么在計算方向時可視為點來處理。然后，計算這些細小單元之間的方向，得到兩個目標的所有基本單元間的方向，即一組方向，或者視為一個分布。最后，對這組方向進行統(tǒng)計描述。具體實現(xiàn)是根據一定的內插方法對源目標進行內插，產生多個內插點，連接參考點和內插點，形成多條方向線，再選擇中值方向作為方向關系的分布中心趨勢。

17、如圖7所示，將源面狀目標B進行柵格化，柵格中心作為內插點，連接參考目標A的質心與多個內插點形成多條方向線，最終選擇中值方向度量B相對于A的空間方向，如圖7中帶箭頭實線所示。圖7 統(tǒng)計模型Fig. 7 Statistical model與錐形模型相比，統(tǒng)計模型的優(yōu)點是采用了中值方向作為空間方向，中值方向能夠較好地從整體上度量空間目標方向關系分布的中心趨勢，并且與人的認知是相一致的；與基于投影的模型相比，統(tǒng)計模型是基于空間目標本身建立的，而不是空間目標的 MBR，減少了因對空間目標近似處理引起的不精確性；與基于Voronoi圖的模型相比，統(tǒng)計模型對整個源目標進行內插，源目標發(fā)生變化，其內插點和中值

18、方向也會發(fā)生變化，故統(tǒng)計模型能解決基于Voronoi圖的模型具有的源目標不可視部分變化而方向不變的問題。該模型的局限性在于1）難以保證內插的精度。將面狀目標柵格化時，不同的柵格大小產生不一樣的結果，柵格越小，精度越高；2）計算過于復雜。插值計算的基本復雜度T(n)=O(n2)，當目標圖形較復雜時，插值的計算量太大。2.5 基于點群分割的模型文學等學者14提出一種基于點群分割的空間方向計算模型。該模型的基本原理是把空間目標看做由點組成的點群，在目標之間建立方向關系參考線，并使參考線左右兩側的點數相等，然后利用參考線計算空間目標間的方向角度。具體實現(xiàn)如圖8所示，圖8a為點與線方向角度計算，參考目標

19、為點A，源目標為線B，把線目標B離散成點群，方向參考線 L與源目標點群交于Bmid，把B分為兩個子點群，兩個子點群中的點數應當相等。參考線 L 的方向角度即為B相對于A的方向。圖8b為線與線方向角度計算，參考目標為線A，源目標為線B，首先將A和B離散成點群，計算 A和B對應全部離散點的重心 M，從通過M的直線中尋找能夠平分A與B 對應全部離散點的直線作為備選參考線，如果備選直線多于一條，則從中選擇將A對應離散點分割最為平均的一條作為最終參考線。當參考目標或者源目標為面時，可以把它的邊界看做封閉的線進行點群離散，后續(xù)的計算方法則與線計算方法相同。圖8 基于點群分割的模型Fig. 8 Direct

20、ion relation model based on point group dividing基于點群分割的模型與統(tǒng)計模型有著相似的思想，都是將目標分解，形成離散的小目標?；邳c群分割的模型的優(yōu)點與統(tǒng)計模型的優(yōu)點相似，受目標之間的距離及自身形狀影響?。磺耶斢嬎隳繕嗽诳梢曈蛲獠糠职l(fā)生改變時，模型能夠對此改變做出反應，輸出更加合理的角度結果，表現(xiàn)出良好的適應性。且相比于統(tǒng)計模型，基于點群分割的模型對面狀目標的離散化更為合理，計算更簡單。基于點群分割的模型的局限性與統(tǒng)計模型相似，要將目標離散成點群時難以保證精度。一個目標的點群中的點之間的間隔越小，點群中的點的數目越多，其計算結果越精確，但這也意味

21、著計算量越大。為了在結果精確度和計算量之間找到權衡之處，這不得不對目標的離散化處理給予更多的考慮。2.6 模型適用性分析基于以上對各個空間方向關系模型的形式化描述、優(yōu)點和缺點的詳細介紹，本文總結了各個空間方向關系模型受空間目標之間的距離及自身形狀的影響度、對目標間空間方向關系描述的準確性和模型的計算復雜性，并對各個模型的適用性進行分析，見表1?？臻g方向關系形式化描述模型中，錐形模型比較簡單適合于表達空間點對象間的方向關系，在表達二維空間對象間的方向關系時，受空間目標形狀和大小的影響，有時會出現(xiàn)錯誤或難以描述，故適合于空間目標形狀和大小距離較遠的空間目標間方向關系的判定。其中，三角化模型引入了空

22、間目標的MBR，一定程度上顧及了空間目標的形狀和大小對空間方向關系的影響，提高了空間目標距離較近的情況下對空間方向關系的區(qū)分能力?；谕队暗哪Ｐ褪且阅繕说腗BR代替目標進行空間方向關系的判斷。當源目標和參考目標的MBR有重疊區(qū)域時，MBR模型不能對空間方向關系作出準確判斷，所以只能適用于MBR不相交情況下對空間方向關系進行定性描述。而方向關系矩陣模型是判斷參考目標的MBR和源目標的空間方向關系，大大減少了重疊MBR對目標之間的空間方向關系的判斷的影響，故適用于一般情況下對空間目標的空間方向關系的精確描述?；贛BR Voronoi圖的模型與MBR模型有著相似的局限性，難以對于兩目標纏繞交疊等復

23、雜情況，故適用于于MBR不相交情況下對空間方向關系進行定性描述，但與MBR模型相比，受空間目標之間的距離及自身形狀的影響更小，對空間方向關系的描述會更合理。方向Voronoi圖模型對目標進行了綜合處理，只考慮可視部分的空間方向關系，忽略不可視部分，未考慮空間目標的整體形狀和大小，故描述空間目標的方向關系時受目標自身形狀影響，總的來說方向Voronoi圖模型適用于一般情況下對空間目標的空間方向關系的精確描述。統(tǒng)計模型和基于點群分割的模型都是基于分解目標的思想，用內插或者離散化的方法將大目標分解為小目標，把線、面目標分解為點目標。統(tǒng)計模型和基于點群分割的模型對空間方向關系的描述幾乎不受空間目標之間

24、的距離、自身的形狀和大小的影響，且描述的準確性非常高，故適合各種情況下對空間目標的空間方向關系的精確描述。這兩種模型的局限性在于計算較復雜，可能會限制模型的推廣和應用。表1 主要空間方向關系模型的適用性 表現(xiàn)模型受影響程度描述準確性計算復雜性適用性（空間目標間的方向關系）錐形模型四方向大差簡單距離遠、點對象間八方向較大較差簡單距離遠、點對象間三角化小較好較簡單適用于一般情況下的定性描述基于投影的模型MBR模型較大較好較簡單MBR不相交情況下的定性描述方向關系矩陣模型小好較復雜適用于一般情況下的精確描述基于Voronoi圖的模型基于MBR Voronoi圖模型 較小較好較簡單MBR不相交情況下的

25、定性描述方向Voronoi圖模型較小好較復雜適用于一般情況下的精確描述統(tǒng)計模型統(tǒng)計模型很小很好較復雜適用于各種情況下的精確描述基于點群分割的模型基于點群分割的模型很小很好較復雜適用于各種情況下的精確描述3 總結目前描述空間方向關系的模型主要有錐形模型、基于投影的模型、基于Voronoi圖的模型，統(tǒng)計模型和基于點群分割的模型等。錐形模型比較簡單，但對方向關系區(qū)分較弱；基于投影的模型和基于Voronoi圖的模型對錐形模型有較大的改進，但仍存在對復雜圖形之間的空間方向關系描述不準確等問題；統(tǒng)計模型和基于點群分割的模型對空間方向關系的描述幾乎不受空間目標之間的距離、自身的形狀和大小的影響，且描述的準確

26、性非常高，但計算的復雜度也很高。目前，空間方向關系形式化描述方法存在的主要問題是：1）存在模型描述錯誤或者無法描述的情形；2）存在計算復雜等應用困難的情形。故本文認為未來空間方向關系模型的研究主要集中在以下兩個方向：1）結合人類空間認知理論研究。傳統(tǒng)的形式化描述對復雜圖形之間的空間方向關系的描述與人類認知往往不一樣，這就要求用人類空間認知理論來解決這樣的問題，比如基于Voronoi圖的模型就是一個很好的嘗試。2）模型算法的優(yōu)化。對于計算復雜度較高的模型進行優(yōu)化處理，或者針對不同應用領域對空間方向關系描述的精確度要求不同，而對空間方向關系模型進行改進，使之能應用于特定的領域。參考文獻(Refer

27、ence)1.Xia yu, Zhu xinyan, Li deren, et al. Analysis of formal representations of spatial direction relation in GISJ. Science of Surveying and Mapping, 2007. 32(5): p. 94-97. (夏宇, 朱欣焰, 李德仁等. GIS空間方向關系形式化描述模型分析J. 測繪科學, 2007. 32(5): p. 94-97.)2.Zhang lifeng. Research on direction relationships of grou

28、ped point object based on convex hullJ. Journal of Gansu Lianhe University (Natural Sciences), 2009(05): p. 39-41.) (張立峰. 基于凸殼的點群目標空間方向關系研究J. 甘肅聯(lián)合大學學報(自然科學版), 2009(05): p. 39-41.)3.He yunbin, Bian jian. Researchs on direction relation models in spatial reasoningJ. Computer & Digital Engineering,

29、 2010(04): p. 62-65+120. (何云斌, 邊健. 空間推理中方向關系模型的研究J. 計算機與數字工程, 2010(04): p. 62-65+120.)4.De min, Huang xingyuan, Li junjie, et al. A model for computing spatial direction relations in vector GISA. Chinese Association for Geographic Information Society. The eighth annual meeting of Chinese Association

30、 for Geographic Information SocietyC. Chinese Association for Geographic Information Society,2004:9 (鄧敏, 黃杏元, 李俊杰等. 矢量GIS空間方向關系的計算模型A. 中國地理信息系統(tǒng)協(xié)會.中國地理信息系統(tǒng)協(xié)會第八屆年會論文集C.中國地理信息系統(tǒng)協(xié)會:,2004:9)5.Harr, R. Computational Model of Spatial RelationsR. TR-478, MSC-72-03610, Computer Science, University of Marylan

31、d, College Park,M D, 1976.6.Qi po. Key technology research of spatial direction relationsD. Harbin University of Science and Technology, 2014. (齊坡. 空間方向關系的關鍵技術研究D. 哈爾濱理工大學, 2014.)7.Wang zhonghui, Yang yanchun. Compound model for describing qualitative direction relationsJ. Journal of image and graph

32、ics, 2014(06): p. 979-984. (王中輝, 楊艷春, 描述定性方向關系的復合表達模型. 中國圖象圖形學報, 2014(06): p. 979-984.)8.Paradias D. Relation-based representation of spatial knowledgeD.Department of Electrical and Computer Engineering, National Technical University of Athens, 1994.9.Goyal R K. Similarity assement for cardinal dire

33、ction between extended spatial objectsD.Maine: The University od Maine, 2000.10.Li chengming, Zhu yinghao, Chenjun. Directional relationship description and determination based on Voronoi diagram in GISJ. Journal of the PLA Institute of Surveying and Mapping. 1998(02): p. 117-120. (李成名, 朱英浩,陳軍. 利用Vo

34、ronoi圖形式化描述和判斷GIS中的方向關J系. 解放軍測繪學院學報, 1998(02): p. 117-120.)11.Yan haowen, Guorenzhong. A formal description model of directional relationships based on Voronoi diagramJ. Geomatics and Information Science of Wuhan University, 2003(04): p. 468-471+479. (閆浩文, 郭仁忠. 基于Voronoi圖的空間方向關系形式化描述模型J. 武漢大學學報(信息科學

35、版), 2003(04): p. 468-471+479.)12.Wang zhonghui, Yan haowen. Computation of direction relations between object groups based on direction Voronoi diagram modelJ. Geomatics and Information Science of Wuhan University, 2013(05): p. 584-588. (王中輝, 閆浩文. 基于方向Voronoi圖模型的群組目標空間方向關系計算J. 武漢大學學報(信息科學版), 2013(05): p. 584-588.)13.De min, Zhang yan, Li jun jie. A statistical model for computing direction relations between spatial objects in GISJ. Geomatics W