空間目標之間的方向關(guān)系模型

1、n空間目標之間的方向關(guān)系模型空間目標之間的方向關(guān)系模型 空間方向關(guān)系n空間方向關(guān)系是地理信息科學(xué)、計算機制圖學(xué)、認知科學(xué)、人工智能、機器人等學(xué)科中共同關(guān)注的課題。在地理信息科學(xué)中，空間方向關(guān)系描述了兩個目標間位置分布的基本空間約束在GIS空間查詢、空間分析、空間推理、制圖綜合等過程中起著重要作用。在應(yīng)用空間方向關(guān)系時, 一個最基本的問題是如何有效地建立描述空間方向關(guān)系的表達模型。 一些方向關(guān)系模型n錐形模型n基于投影的模型n基于 Voronoi 圖模型 這些模型描述的并不是兩個原始目標本身之間的空間方向關(guān)系, 而是對原空間目標進行形狀簡化后所得的替代空間目標間方向關(guān)系的描述。錐形模型n 錐形模

2、型由Haar等提出，其主要思想是將空間目標及其周圍的區(qū)域分成帶有方向性的幾個區(qū)域,通過各目標本身及方向區(qū)域之間的交的結(jié)果來描述空間關(guān)系，具有代表性的是四方向、八方向錐形模型和三角化模型。n四方向錐形模型四方向錐形模型n 四方向錐形模型是以某一空間目標為參考目標，以東西南北方向線為軸將空間目標及周圍的區(qū)域等分成四個方向區(qū)域來定義方向關(guān)系，如圖1a所示。以參考點O為中心，將空間區(qū)域分為E、S 、W 、 N四個方向區(qū)域，用其他空間目標與這些方向區(qū)域間的位置關(guān)系來描述空間目標間的方向關(guān)系，如圖1b。源目標B相對于參考目標A的方向關(guān)系為: dir(A,B) = E,即B在A的東邊。錐形模型n 由于四方向

3、錐形模型將參考目標抽象為一個點,忽略了空間目標形狀和大小對空間方向關(guān)系的影響,當空間目標之間的距離相對于自身大小比較近的時候,四方向錐形模型有時會出現(xiàn)對空間方向關(guān)系的錯誤描述,如圖1c所示, A為參考目標, B為源目標,用該模型描述方向關(guān)系結(jié)果為B在A的北邊,與實際我們的感知B在A的東邊或東北邊不一致?？梢?四方向錐形模型適合于相對于空間目標形狀和大小距離較遠的空間目標間方向關(guān)系的判定。錐形模型n八方向錐形模型八方向錐形模型n 八方向錐形模型是以某一空間目標為參考目標,以東西南北方向線以及四方向錐形模型邊界線為軸將空間目標及周圍的區(qū)域分成八個方向區(qū)域定義方向關(guān)系,如圖2a所示,以參考點O為中心

4、,將空間區(qū)域分為E、SE、S、SW、W、NW、N、NE八個方向區(qū)域,用其他空間目標與這些方向區(qū)域間的位置關(guān)系來描述空間目標間的方向關(guān)系。與四方向錐形模型相比,八方向錐形模型能更精確描述空間目標間的方向關(guān)系。圖1c中空間目標間的方向關(guān)系用四方向錐形模型描述時出現(xiàn)錯誤,如果用八方向錐形模型描述即可得到正確的結(jié)果,如圖2b所示,源目標B相對于參考目標A的方向關(guān)系為: dir(A,B) = NE,即B在A的東北邊,這與我們的空間認知是一致的。錐形模型n 由于八方向錐形模型與四方向錐形模型對空間方向關(guān)系描述的基本思想是一樣的,因此,當空間目標之間的距離相對于自身大小很近的時候,同樣會出現(xiàn)錯誤描述的情況,

5、如圖2c所示, A為參考目標, B為源目標,用該模型描述空間關(guān)系的結(jié)果為B在A的北邊,與實際情況不符?？梢?八方向錐形模型同樣適合于描述相對于空間目標形狀和大小距離較遠的空間目標間方向關(guān)系,但對距離較近的情況比四方向錐形模型描述能力強.錐形模型n三角化模型三角化模型n 三角化模型是四方向錐形模型和八方向錐形模型的擴展。基本思想是從空間目標的某點出發(fā),沿所需要的方向作兩條射線形成一個三角形方向區(qū)域,從而描述與計算目標間的方向關(guān)系。如圖3a所示,以參考目標A的質(zhì)心為中心,以東方向線為軸,作兩條相互垂直的射線,則源目標B相對于參考目標A的方向關(guān)系為: dir（A，B） = E,即B在A的東邊。當空間

6、目標間距離較近時,如圖3b所示,作參考目標A的最小外接矩形(Minimum Boundary Rectangle, MBR),通過矩形兩端點作兩條相互垂直的射線,則源目標B相對于參考目標A的方向關(guān)系為: dir（A，B） = E,即B在A的東邊。而在圖1c中空間目標間的方向關(guān)系用四方向錐形模型描述時則出現(xiàn)錯誤。如果考慮八方向的話,則每兩個相鄰方向區(qū)域之間會產(chǎn)生50%的重疊帶。帶。錐形模型n如圖3c所示,源目標B位于參考目標A的東和東北方向重疊帶,即B在A的東邊或東北邊,這與我們的空間認知是一致的。可見,三角化模型一定程度上顧及了空間目標形狀和大小對空間關(guān)系的影響,克服了四方向和八方向錐形模型對

7、空間方向關(guān)系描述的不足,對空間目標的距離相對于其形狀和大小較近時的方向關(guān)系,也有較好的區(qū)分能力?；谕队暗哪Ｐ蚽 基于投影模型是指將空間目標投影到特定的坐標軸上,通過各目標投影間的關(guān)系去描述與定義方向關(guān)系,如圖4所示,通過空間目標在水平軸和垂直軸上的投影,可以將空間分為E、S、W、N、O、NE、SE、SW、NW9個方向區(qū)域。具有代表性的有二維字符串模型、MBR模型和方向關(guān)系矩陣模型?；谕队暗哪Ｐ蚽二維字符串模型二維字符串模型n 二維字符串模型由Chang S K等提出,基本思想是采用符號投影的方法,將不同二維空間目標的邊界沿水平軸和垂直軸作正射投影,分別生成有順序關(guān)系的字符串,以表達和判斷目

8、標間的空間關(guān)系。如圖5a所示,對空間目標A、B、C、D、E在水平軸和垂直軸上的投影可以描述為二維字符串(a= d :ea=bc, a=ab=cd: e)。其中“a,b,c,d,e”為空間目標對應(yīng)的字符,如圖5b所示；“=”表示在一維投影軸上相等;“”表示在一維投影軸上小于,水平軸上為西,垂直軸上為南; “:”表示在二維空間相等,即兩空間目標處于同一方向區(qū)域。該模型并沒有顯式地表達兩空間目標間的方向關(guān)系,而是要從二維字符串中解析出方向關(guān)系,如從二維字符串(a=d:ea=bc, a=ab=cd: e)中知道,水平分量上ac,即C在A的東邊,垂直分量上ac,即C在A的北邊,所以dir(A,C) =

9、NE,即C在A的東北方向?；谕队暗哪Ｐ蚽 不難發(fā)現(xiàn),二維字符串模型存在著受空間目標形狀和大小以及網(wǎng)格劃分大小影響等缺陷。為此, Jungert與Chang等提出Generalized 2-D String模型, Lee等提出2-D C-String模型,一定程度上提高了對空間目標間方向關(guān)系的描述能力。由于二維字符串模型中參考目標不固定,比較適合于描述整個空間場景的方向關(guān)系,常用于影像檢索等領(lǐng)域。基于投影的模型n MBR模型由D.Papadias等提出,主要思想是通過空間目標最小外接矩形之間的方向關(guān)系來判定空間目標間的方向關(guān)系。該模型在水平方向和垂直方向上各能表達13種空間關(guān)系,因此能夠區(qū)分1

10、69種空間關(guān)系。該模型常用來作為空間目標拓撲關(guān)系判定的過濾器。當用于方向關(guān)系描述的時候,通常用來表達9個主要方向,俗稱”井”字模型,如圖6a所示,源目標B相對與參考目標A的方向關(guān)系為: Dir(A,B) = NE,即B在A的東北方向。該模型在一定程度上顧及了空間目標形狀和大小對方向關(guān)系的影響。但是,當兩個空間目標的MBR相交的時候,就可能導(dǎo)致空間方向關(guān)系描述困難,如圖6b所示?；谕队暗哪Ｐ蚽方向關(guān)系矩陣模型方向關(guān)系矩陣模型 方向關(guān)系矩陣模型由Goyal等提出,主要思想是以空間目標最小外接矩形為參考方向,將空間劃分為9個方向區(qū)域,以源目標與各方向區(qū)域的交疊情況為元素構(gòu)成一個方向關(guān)系矩陣來描述與

11、定義空間目標間的方向關(guān)系。方向關(guān)系矩陣可以分為兩種,一種是粗略的方向關(guān)系矩陣,元素值是0或1,僅僅記錄源目標與參考目標的各方向區(qū)域是否相交;另一種是精確的方向關(guān)系矩陣,元素值是源目標與各方向區(qū)域的交疊面積百分比。如圖7所示,若用粗略的方向關(guān)系矩陣模型,則只能得到B在A的北、東和東北方向。若用精確的方向關(guān)系矩陣模型,則能得到諸如B的40%位于A的東北方向, 30%位于A的北邊,30%位于A的東邊的結(jié)論。上面的兩種方向關(guān)系矩陣模型,前者比較直觀,符合人們的思維習(xí)慣,缺陷是在復(fù)雜情況下難以給出合適的描述;后者比較詳細,對于任何情況下的兩個空間目標總可以給出有效的描述,缺陷是計算比較復(fù)雜。基于投影的模

12、型基于 Voronoi 圖模型n基于 Voronoi 圖的模型的基本思想通過空間目標的 Voronoi 圖與空間目標的關(guān)系來描述和定義空間目標間的方向關(guān)系。李成名等在空間目標MBR的基礎(chǔ)上建立 Voronoi 區(qū)域,通過空間目標MBR與 Voronoi 區(qū)域邊界線之間的關(guān)系來描述空間目標之間的方向關(guān)系。基于 Voronoi 圖模型n 如圖8所示,空間目標A的MBR有4條邊分別表示為de = eastedge (A)、dw = westedge (A)、dn = northedge (A)和ds =southedge (A)。將4條邊看作4個線(Line)生成元,生成的4個Voronoi區(qū)域分別

13、為voronoi(de)、voronoi (dw)、voronoi (dn)和voronoi (ds)。NE、NW、SW和SE分別為邊de、dn、dw和ds的Voronoi多邊形的邊界,空間實體A的東部east(A)定義為de、SE和NE圍成的區(qū)域,西部、北部和南部可以類推?？臻g實體A和B之間的方向關(guān)系可以利用空間實體的最小矩形邊和Voronoi多邊形的邊界線構(gòu)成的5*5矩陣形式化描述表達?；?Voronoi 圖模型基于 Voronoi 圖模型n 閆浩文等通過建立與空間目標間指向線的法線比較近似的方向Voronoi圖來描述空間目標間的方向關(guān)系,如圖9所示。然后,計算方向Voronoi圖每條邊

14、的方位,得到空間目標之間方向關(guān)系的精確描述,如:源目標B的50%位于參考目標A的北邊, 23%位于A的東北方向,27%位于A的東邊。還可以連接兩目標可視區(qū)域內(nèi)方向Voronoi圖的首尾端點,計算方向Voronoi圖整體走向的方位角,轉(zhuǎn)換為兩空間目標的方向關(guān)系的概略表達: B位于A的東北方向?；?Voronoi 圖模型基于 Voronoi 圖模型n 以上是兩種代表性的基于Voronoi圖的模型,前者適合于對空間方向關(guān)系的定性描述,后者進一步克服了空間目標的形狀和大小對空間方向關(guān)系的影響,對空間目標間的方向關(guān)系描述更加準確,對空間方向關(guān)系的精確描述更具優(yōu)勢。各模型比較分析n 空間方向關(guān)系形式化描

15、述模型中,錐形模型比較簡單,適合于表達空間點對象間的方向關(guān)系,在表達二維空間對象間的方向關(guān)系時,受空間目標形狀和大小的影響,有時會出現(xiàn)錯誤或難以描述。因此,在表達二維空間對象間的方向關(guān)系時,適合于相對于空間目標形狀和大小距離較遠的空間目標間方向關(guān)系的判定。其中,三角化模型在空間目標距離較近的情況下,引入了空間目標的MBR,一定程度上顧及了空間目標的形狀和大小對空間方向關(guān)系的影響,克服了四方向錐形模型和八方向錐形模型的不足,提高了空間目標距離較近的情況下對空間方向關(guān)系的區(qū)分能力。各模型比較分析 基于投影的模型與錐形模型相比有許多優(yōu)點，基于Voronoi圖的模型也在模型的適用性等很多方面表現(xiàn)出優(yōu)越

16、性,表1給出了各種空間方向關(guān)系形式化描述模型的優(yōu)缺點和適用性。n 從表1可以看出,與錐形模型相比,基于投影的模型和基于Voronoi圖的模型在方向關(guān)系描述準確性方面占有優(yōu)勢,但計算相對比較復(fù)雜適合于對各種情況下空間目標間方向關(guān)系的精確描述。各模型比較分析各模型比較分析n目前大多數(shù)空間方向關(guān)系形式化描述模型,如三角化模型、二維字符串模型、MBR模型和基于空間目標MBR的Voronoi模型等,都借助了空間目標的MBR來描述空間方向關(guān)系,要么是通過空間目標的MBR之間的方向關(guān)系來代替空間目標間的方向關(guān)系,要么是通過參考目標的MBR來劃分方向區(qū)域。雖然簡化了空間方向關(guān)系的計算,在一定程度上克服空間目標形狀和大小對空間方向關(guān)系的影響,卻同時導(dǎo)致空間方向關(guān)系描述欠準確。方向關(guān)系矩陣模型通過源目標在參考目標各個方向的面積比,提高了