空间目标之间的方向关系模型

1、n空间目标之间的方向关系模型空间目标之间的方向关系模型 空间方向关系n空间方向关系是地理信息科学、计算机制图学、认知科学、人工智能、机器人等学科中共同关注的课题。在地理信息科学中，空间方向关系描述了两个目标间位置分布的基本空间约束在GIS空间查询、空间分析、空间推理、制图综合等过程中起着重要作用。在应用空间方向关系时, 一个最基本的问题是如何有效地建立描述空间方向关系的表达模型。 一些方向关系模型n锥形模型n基于投影的模型n基于 Voronoi 图模型 这些模型描述的并不是两个原始目标本身之间的空间方向关系, 而是对原空间目标进行形状简化后所得的替代空间目标间方向关系的描述。锥形模型n 锥形模

2、型由Haar等提出，其主要思想是将空间目标及其周围的区域分成带有方向性的几个区域,通过各目标本身及方向区域之间的交的结果来描述空间关系，具有代表性的是四方向、八方向锥形模型和三角化模型。n四方向锥形模型四方向锥形模型n 四方向锥形模型是以某一空间目标为参考目标，以东西南北方向线为轴将空间目标及周围的区域等分成四个方向区域来定义方向关系，如图1a所示。以参考点O为中心，将空间区域分为E、S 、W 、 N四个方向区域，用其他空间目标与这些方向区域间的位置关系来描述空间目标间的方向关系，如图1b。源目标B相对于参考目标A的方向关系为: dir(A,B) = E,即B在A的东边。锥形模型n 由于四方向

3、锥形模型将参考目标抽象为一个点,忽略了空间目标形状和大小对空间方向关系的影响,当空间目标之间的距离相对于自身大小比较近的时候,四方向锥形模型有时会出现对空间方向关系的错误描述,如图1c所示, A为参考目标, B为源目标,用该模型描述方向关系结果为B在A的北边,与实际我们的感知B在A的东边或东北边不一致。可见,四方向锥形模型适合于相对于空间目标形状和大小距离较远的空间目标间方向关系的判定。锥形模型n八方向锥形模型八方向锥形模型n 八方向锥形模型是以某一空间目标为参考目标,以东西南北方向线以及四方向锥形模型边界线为轴将空间目标及周围的区域分成八个方向区域定义方向关系,如图2a所示,以参考点O为中心

4、,将空间区域分为E、SE、S、SW、W、NW、N、NE八个方向区域,用其他空间目标与这些方向区域间的位置关系来描述空间目标间的方向关系。与四方向锥形模型相比,八方向锥形模型能更精确描述空间目标间的方向关系。图1c中空间目标间的方向关系用四方向锥形模型描述时出现错误,如果用八方向锥形模型描述即可得到正确的结果,如图2b所示,源目标B相对于参考目标A的方向关系为: dir(A,B) = NE,即B在A的东北边,这与我们的空间认知是一致的。锥形模型n 由于八方向锥形模型与四方向锥形模型对空间方向关系描述的基本思想是一样的,因此,当空间目标之间的距离相对于自身大小很近的时候,同样会出现错误描述的情况,

5、如图2c所示, A为参考目标, B为源目标,用该模型描述空间关系的结果为B在A的北边,与实际情况不符。可见,八方向锥形模型同样适合于描述相对于空间目标形状和大小距离较远的空间目标间方向关系,但对距离较近的情况比四方向锥形模型描述能力强.锥形模型n三角化模型三角化模型n 三角化模型是四方向锥形模型和八方向锥形模型的扩展。基本思想是从空间目标的某点出发,沿所需要的方向作两条射线形成一个三角形方向区域,从而描述与计算目标间的方向关系。如图3a所示,以参考目标A的质心为中心,以东方向线为轴,作两条相互垂直的射线,则源目标B相对于参考目标A的方向关系为: dir（A，B） = E,即B在A的东边。当空间

6、目标间距离较近时,如图3b所示,作参考目标A的最小外接矩形(Minimum Boundary Rectangle, MBR),通过矩形两端点作两条相互垂直的射线,则源目标B相对于参考目标A的方向关系为: dir（A，B） = E,即B在A的东边。而在图1c中空间目标间的方向关系用四方向锥形模型描述时则出现错误。如果考虑八方向的话,则每两个相邻方向区域之间会产生50%的重叠带。带。锥形模型n如图3c所示,源目标B位于参考目标A的东和东北方向重叠带,即B在A的东边或东北边,这与我们的空间认知是一致的。可见,三角化模型一定程度上顾及了空间目标形状和大小对空间关系的影响,克服了四方向和八方向锥形模型对

7、空间方向关系描述的不足,对空间目标的距离相对于其形状和大小较近时的方向关系,也有较好的区分能力。基于投影的模型n 基于投影模型是指将空间目标投影到特定的坐标轴上,通过各目标投影间的关系去描述与定义方向关系,如图4所示,通过空间目标在水平轴和垂直轴上的投影,可以将空间分为E、S、W、N、O、NE、SE、SW、NW9个方向区域。具有代表性的有二维字符串模型、MBR模型和方向关系矩阵模型。基于投影的模型n二维字符串模型二维字符串模型n 二维字符串模型由Chang S K等提出,基本思想是采用符号投影的方法,将不同二维空间目标的边界沿水平轴和垂直轴作正射投影,分别生成有顺序关系的字符串,以表达和判断目

8、标间的空间关系。如图5a所示,对空间目标A、B、C、D、E在水平轴和垂直轴上的投影可以描述为二维字符串(a= d :ea=bc, a=ab=cd: e)。其中“a,b,c,d,e”为空间目标对应的字符,如图5b所示；“=”表示在一维投影轴上相等;“”表示在一维投影轴上小于,水平轴上为西,垂直轴上为南; “:”表示在二维空间相等,即两空间目标处于同一方向区域。该模型并没有显式地表达两空间目标间的方向关系,而是要从二维字符串中解析出方向关系,如从二维字符串(a=d:ea=bc, a=ab=cd: e)中知道,水平分量上ac,即C在A的东边,垂直分量上ac,即C在A的北边,所以dir(A,C) =

9、NE,即C在A的东北方向。基于投影的模型n 不难发现,二维字符串模型存在着受空间目标形状和大小以及网格划分大小影响等缺陷。为此, Jungert与Chang等提出Generalized 2-D String模型, Lee等提出2-D C-String模型,一定程度上提高了对空间目标间方向关系的描述能力。由于二维字符串模型中参考目标不固定,比较适合于描述整个空间场景的方向关系,常用于影像检索等领域。基于投影的模型n MBR模型由D.Papadias等提出,主要思想是通过空间目标最小外接矩形之间的方向关系来判定空间目标间的方向关系。该模型在水平方向和垂直方向上各能表达13种空间关系,因此能够区分1

10、69种空间关系。该模型常用来作为空间目标拓扑关系判定的过滤器。当用于方向关系描述的时候,通常用来表达9个主要方向,俗称”井”字模型,如图6a所示,源目标B相对与参考目标A的方向关系为: Dir(A,B) = NE,即B在A的东北方向。该模型在一定程度上顾及了空间目标形状和大小对方向关系的影响。但是,当两个空间目标的MBR相交的时候,就可能导致空间方向关系描述困难,如图6b所示。基于投影的模型n方向关系矩阵模型方向关系矩阵模型 方向关系矩阵模型由Goyal等提出,主要思想是以空间目标最小外接矩形为参考方向,将空间划分为9个方向区域,以源目标与各方向区域的交叠情况为元素构成一个方向关系矩阵来描述与

11、定义空间目标间的方向关系。方向关系矩阵可以分为两种,一种是粗略的方向关系矩阵,元素值是0或1,仅仅记录源目标与参考目标的各方向区域是否相交;另一种是精确的方向关系矩阵,元素值是源目标与各方向区域的交叠面积百分比。如图7所示,若用粗略的方向关系矩阵模型,则只能得到B在A的北、东和东北方向。若用精确的方向关系矩阵模型,则能得到诸如B的40%位于A的东北方向, 30%位于A的北边,30%位于A的东边的结论。上面的两种方向关系矩阵模型,前者比较直观,符合人们的思维习惯,缺陷是在复杂情况下难以给出合适的描述;后者比较详细,对于任何情况下的两个空间目标总可以给出有效的描述,缺陷是计算比较复杂。基于投影的模

12、型基于 Voronoi 图模型n基于 Voronoi 图的模型的基本思想通过空间目标的 Voronoi 图与空间目标的关系来描述和定义空间目标间的方向关系。李成名等在空间目标MBR的基础上建立 Voronoi 区域,通过空间目标MBR与 Voronoi 区域边界线之间的关系来描述空间目标之间的方向关系。基于 Voronoi 图模型n 如图8所示,空间目标A的MBR有4条边分别表示为de = eastedge (A)、dw = westedge (A)、dn = northedge (A)和ds =southedge (A)。将4条边看作4个线(Line)生成元,生成的4个Voronoi区域分别

13、为voronoi(de)、voronoi (dw)、voronoi (dn)和voronoi (ds)。NE、NW、SW和SE分别为边de、dn、dw和ds的Voronoi多边形的边界,空间实体A的东部east(A)定义为de、SE和NE围成的区域,西部、北部和南部可以类推。空间实体A和B之间的方向关系可以利用空间实体的最小矩形边和Voronoi多边形的边界线构成的5*5矩阵形式化描述表达。基于 Voronoi 图模型基于 Voronoi 图模型n 闫浩文等通过建立与空间目标间指向线的法线比较近似的方向Voronoi图来描述空间目标间的方向关系,如图9所示。然后,计算方向Voronoi图每条边

14、的方位,得到空间目标之间方向关系的精确描述,如:源目标B的50%位于参考目标A的北边, 23%位于A的东北方向,27%位于A的东边。还可以连接两目标可视区域内方向Voronoi图的首尾端点,计算方向Voronoi图整体走向的方位角,转换为两空间目标的方向关系的概略表达: B位于A的东北方向。基于 Voronoi 图模型基于 Voronoi 图模型n 以上是两种代表性的基于Voronoi图的模型,前者适合于对空间方向关系的定性描述,后者进一步克服了空间目标的形状和大小对空间方向关系的影响,对空间目标间的方向关系描述更加准确,对空间方向关系的精确描述更具优势。各模型比较分析n 空间方向关系形式化描

15、述模型中,锥形模型比较简单,适合于表达空间点对象间的方向关系,在表达二维空间对象间的方向关系时,受空间目标形状和大小的影响,有时会出现错误或难以描述。因此,在表达二维空间对象间的方向关系时,适合于相对于空间目标形状和大小距离较远的空间目标间方向关系的判定。其中,三角化模型在空间目标距离较近的情况下,引入了空间目标的MBR,一定程度上顾及了空间目标的形状和大小对空间方向关系的影响,克服了四方向锥形模型和八方向锥形模型的不足,提高了空间目标距离较近的情况下对空间方向关系的区分能力。各模型比较分析 基于投影的模型与锥形模型相比有许多优点，基于Voronoi图的模型也在模型的适用性等很多方面表现出优越

16、性,表1给出了各种空间方向关系形式化描述模型的优缺点和适用性。n 从表1可以看出,与锥形模型相比,基于投影的模型和基于Voronoi图的模型在方向关系描述准确性方面占有优势,但计算相对比较复杂适合于对各种情况下空间目标间方向关系的精确描述。各模型比较分析各模型比较分析n目前大多数空间方向关系形式化描述模型,如三角化模型、二维字符串模型、MBR模型和基于空间目标MBR的Voronoi模型等,都借助了空间目标的MBR来描述空间方向关系,要么是通过空间目标的MBR之间的方向关系来代替空间目标间的方向关系,要么是通过参考目标的MBR来划分方向区域。虽然简化了空间方向关系的计算,在一定程度上克服空间目标形状和大小对空间方向关系的影响,却同时导致空间方向关系描述欠准确。方向关系矩阵模型通过源目标在参考目标各个方向的面积比,提高了