空间关系描述与推理

*,单击此处编辑母版标题样式,单击此处编辑母版标题样式,*,空间关系描述及其推理,研究生课程,1,报告提纲,一、空间关系基本概念,二、拓扑关系描述,三、方向关系描述,四、邻近关系描述,五、距离关系描述,六、空间关系应用,七、总结,2,空间关系及其描述,空间关系指空间对象在几何上存在的一种相互依赖的概念，主要包括：,空间关系描述主要建立一种形式化的模型，通过该形式化的模型，能够把空间对象的几何结构描述为人们能够理解的符号或词语，这些符号或词语就是对空间关系的定性描述。,拓扑关系,方向关系,邻近关系,距离关系,3,拓扑,设,X,是一个非空集合。,X,的一个子集族,称为,X,的一个拓扑，如果它满足：,（,1,）,X,和空集,都属于,；,（,2,）,中任意多个成员的并集仍在,中；,（,3,）,中有限多个成员的交集仍在,中。,定义中的三个条件称为拓扑公理。条件（,3,）可以等价的换为,中两个成员的交集仍在,中。,称集合,X,连同它的拓扑,为一个,拓扑空间,，记作（,X,）。,称,中的成员为这个拓扑空间的开集。,4,拓扑,常用集合来代指一个拓扑空间，如拓扑空间,X,，拓扑空间,Y,等。,给出某集合的一个拓扑就是规定它的哪些子集是开集。,1.,欧几里德空间,在通常开集的意义下是拓扑空间，它的拓扑就是所有开集组成的集合。,2.,设,X,是一个非空集合。则集合,t,：,X,是,X,的一个拓扑。称,t,为,X,的平凡拓扑。显然（,X,t,）只有两个开集，,X,和,。,5,拓扑,3.,设,X,是一个非空集合。则,X,的幂集,T=2X,也是,X,的一个拓扑。称,T,为,X,的离散拓扑。显然,X,的任意子集都是,(X,T),的开集。,4.,一个具体的例子。设,X=1,2,。则,X,1,2,是,X,的一个拓扑，但,X,1,2,不是拓扑。（自己想想为什么）,6,拓扑学,拓扑学的英文名是,Topology,，直译是地志学，也就是和研究地形、地貌相类似的有关学科。我国早期曾经翻译成“形势几何学”、“连续几何学”、“一对一的连续变换群下的几何学”，但是，这几种译名都不大好理解，,1956,年统一的,数学名词,把它确定为拓扑学，这是按音译过来的。,7,拓扑学,拓扑学是几何学的一个分支，但是这种几何学又和通常的平面几何、立体几何不同。通常的平面几何或立体几何研究的对象是点、线、面之间的位置关系以及它们的度量性质。拓扑学对于研究对象的长短、大小、面积、体积等度量性质和数量关系都无关。,8,拓扑学,在通常的平面几何里，把平面上的一个图形搬到另一个图形上，如果完全重合，那么这两个图形叫做全等形。但是，在拓扑学里所研究的图形，在运动中无论它的大小或者形状都发生变化。在拓扑学里没有不能弯曲的元素，每一个图形的大小、形状都可以改变。例如，欧拉在解决哥尼斯堡七桥问题的时候，他画的图形就不考虑它的大小、形状，仅考虑点和线的个数。,9,拓扑性质 之拓扑等价,在拓扑学里不讨论两个图形全等的概念，但是讨论拓扑等价的概念。比如，尽管圆和方形、三角形的形状、大小不同，在拓扑变换下，它们都是等价图形。,10,拓扑等价,在一个球面上任选一些点用不相交的线把它们连接起来，这样球面就被这些线分成许多块。在拓扑变换下，点、线、块的数目仍和原来的数目一样，这就是拓扑等价。一般地说，对于任意形状的闭曲面，只要不把曲面撕裂或割破，他的变换就是拓扑变换，就存在拓扑等价。,11,环面不具有这个性质。把环面切开，它不至于分成许多块，只是变成一个弯曲的圆桶形，对于这种情况，我们就说球面不能拓扑的变成环面。所以球面和环面在拓扑学中是不同的曲面。,直线上的点和线的结合关系、顺序关系，在拓扑变换下不变，这是拓扑性质。在拓扑学中曲线和曲面的闭合性质也是拓扑性质。,12,通常讲的平面、曲面通常有两个面，就像一张纸有两个面一样。德国数学家,莫比乌斯,在,1858,年发现了莫比乌斯曲面。这种曲面就不能用不同的颜色来涂满两个侧面。,13,拓扑关系,topological relation,指满足拓扑几何学原理的各,空间数据,间的相互关系。即用结点、弧段和多边形所表示的实体之间的邻接、关联、包含和连通关系。如：点与点的邻接关系、点与面的包含关系、线与面的相离关系、面与面的重合关系等。,拓扑关系是指图形元素之间相互空间上的连接、邻接关系并不考虑具体位置,.,这种拓扑关系是由数字化的点、线、面数据形成的以用户的查询或应用分析要求进行图形选取、叠合、合并等操作,14,拓扑关系描述,基本概念,什么是拓扑关系？,拓扑关系指在拓扑变换下保持不变的性质，如旋转、平移和尺度变化,拓扑关系是一种定性关系，而不是定量的,什么是拓扑关系描述模型？,一种,形式化的模型，它能够用数学的手段区别不同的拓扑关系的，而不是仅仅从直观感觉上区分,描述模型所能区分的拓扑关系应该和人们直观感觉所区分的拓扑关系一致，这包括区分的关系种类数和含义的一致性,15,拓扑关系描述,九交模型,(,Egenhofer, 1991),16,拓扑关系描述,九交模型,(,Egenhofer,1991,),A,的内部和,B,的内部的交，记作,A,的内部和,B,的边界的交，记作,A,的内部和,B,的,外部,的交，记作,A,的边界和,B,的内部的交，记作,A,的边界和,B,的边界的交，记作,A,的边界和,B,的,外部,的交，记作,A,的外部和,B,的内部的交，记作,A,的外部和,B,的边界的交，记作,A,的外部和,B,的外部的交，记作,17,拓扑关系描述,面,/,面拓扑关系,(,Egenhofer,1991,),Disjoint,Meet,Overlap,Contain,Equal,CoveredBy,Inside,Cover,面与面间有效的拓扑关系共有,8,个,18,拓扑关系描述,线,/,面拓扑关系,(,Egenhofer,1991,),LR11,LR12,LR13,LR22,LR31,LR32,LR33,LR42,LR44,LR46,LR62,LR64,LR66,LR71,LR72,LR73,LR74,LR75,LR76,线与面间有效的拓扑关系共有,19,个,19,拓扑关系描述,线,/,线拓扑关系,(,Egenhofer,1991,),LL1,LL2,LL3,LL4,LL5,LL6,LL7,LL8,LL9,LL10,LL11,LL12,LL13,LL14,LL15,LL16,LL17,LL18,LL19,LL20,LL21,线与线间有效的拓扑关系共有,33,个，这里只给出了,21,个,20,拓扑关系描述,Voronoi,图模型,(,陈军等,2001),九交模型的缺点：,九交模型中的外部太大。对于一个面积有限的空间目标而言，它的外部是无限的。这导致任意两个目标的外部的交总是非空。,A,B,A,B,B,A,C,外部的无限性，导致目标的外部与边界和内部是线性相关的，使得外部在九交模型中的作用不是很明显。,只能描述简单目标（不带洞而单一的实体）间的拓扑关系，而不能描述复杂目标（带洞或由几个分离目标组成的目标）间的拓扑关系。,21,拓扑关系描述,Voronoi,图模型,(,陈军等,2001),Voronoi,图的定义,设有空间目标簇,P=P,1, P,2, P,3, , P,n, P,i,R,N, V(P,i,) = y | Dist(y, P,i,) Dist(y, P,j,),对所有,j,，式中,Dist(y, P,i,),点,y,到,P,i,的最小距离，,V(P,i,),被称为空间目标的,Voronoi,区域，,V(P)=V(P,1,),V(P,2,),V(P,n,),则被称为,Voronoi,图,Voronoi,能把对象间的邻接定义为对应,Voronoi,区域的邻接，采用等距离原则确定任一物体所处的,Voronoi,区域的边界线，从而将三种基本空间对象点、线和面纳入某种邻接物的集合,构成,V(P,i,),的点到,P,i,的距离比到,P,j,(i, j=1,n, ji),的距离要近，从而可以构造出点、线、面不同维空间对象的,Voronoi,区域。点和线、面，线和面之间的,Voronoi,区域边界线是曲线，而点与点之间，线和线之间的,Voronoi,区域边界线是直线。,22,拓扑关系描述,Voronoi,图模型,(,陈军等,2001),Voronoi,图的性质,势力范围特性。每个空间对象都有一个唯一的,Voronoi,区域与之对应。,局域动态特性。分析表明，,Voronoi,的平均边数不超过,6,。删除或增加一个生长目标，一般只影响周围,6,个左右的相邻空间生长目标，即只会影响局部范围内的目标。,侧向邻近特性。若两个空间对象之间没有其它对象，则它们的,Voronoi,区域必然有一个公共边。通过判断,Voronoi,区域是否有公共边，就可判断连个对象是否是侧向邻近。,与,Delaunay,三角形的对偶性。如果空间生长对象满足非共线特性，将其中具有公共,Voronoi,边的生长点对相连，就可得到,Delaunay,三角形。,23,拓扑关系描述,Voronoi,图模型,(,陈军等,1997),空间对象的,Voronoi,图,24,拓扑关系描述,Voronoi,图模型,(,陈军等,1997),两个重叠面对象的,Voronoi,图,25,拓扑关系描述,Voronoi,图模型,(,陈军等,1997),两个相交线对象的,Voronoi,图,26,拓扑关系描述,Voronoi,图模型,(,陈军等,1997),线和面相交的,Voronoi,图,27,拓扑关系描述,Voronoi,图模型,(,陈军等,2001),基于,Voronoi,图的九交模型,每一个空间对象的,Voronoi,图都可以被分成三部分，即,Voronoi,区域，空间对象的边界，空间对象的内部。,V9I,模型用对象的,Voronoi,区域代替九交模型中的外部，而对象的边界和内部与九交模型保持一致。,V9I,定义：,若两个空间对象相邻时， 非空；若被其它目标隔开，则 为空，因而空,V9I,模型用可以区分相邻和相离两种拓扑关系，而,9,交模型把二者均描述为相离。,28,拓扑关系描述,Voronoi,图模型,(,陈军等,1997),29,拓扑关系描述,Voronoi,图模型,(,陈军等,1997),30,基于维数扩展的九交模型能够很好地将两个空间目标的交集是空、点、线或面,4,种情况区分开,但同四元矩阵拓扑空间关系描述框架一样,不能描述邻接和相离等空间目标分离开的拓扑关系基于,voroni,图的九交模型在区分地理空间中邻近关系和相离关系时具有一定的优势,31,目前,空间拓扑关系形式化描述方法存在的主要问题体现在基于点集拓扑的空间关系描述框架无法描述相离的和没有公共元素的空间目标间的拓扑空间关系,即存在所谓的模型描述错误或者无法描述的情形,32,空间拓扑关系形式化描述模型的发展,结合人们空间认知的理论模型研究,形式化描述模型对空间目标间距离较近等复杂情况下空间方向关系的描述常会出现与人们认知不一致的情况。,融合不同的空间关系描述方法,进一步完善空间关系的理论模型,如方向关系的判定准则以及对度关系的形式化描述等,建立更符合人类认知模式的统一的空间关系描述体系,使得对地理空间目标间关系的刻画更准确、更全面,33,空间拓扑关系的推理,由空间对象已知的空间拓扑关系信息，推测和确定未知的其可能成立的空间拓扑关系。,例如，若已知空间对象,A,和,B,的拓扑关系为,R1,（,A,，,B,），,B,和,C,的拓扑关系为,R2,（,B,，,C,），通过已有的空间知识进行空间分析，从而可推导出,A,和,C,之间可能存在的空间拓扑关系,R3,（,A,，,C,）。,34,空间拓扑关系的推理分类,一种是在对动态空间目标建模时，空间目标之间的拓扑关系随着时间的变化而变化，在已知空间拓扑关系初始状态和空间目标的运动轨迹或其他相关度量指标时确定下一时刻未知的两空间目标之间的可能拓扑关系。,35,另一种：要求两空间目标之间的空间拓扑关系，但直接获取它们之间相关空间关系信息困难，而仅能获得它们与其他另一空间目标之间的关系，基于获得的空间拓扑信息，用空间推理的方法推出两空间对象间的空间拓扑关系。,36,第一种情形，可通过构建拓扑概念邻域图的方法进行定性推理；,第二种情形则可利用空间拓扑关系的组合运算的方法进行分析。,37,Cui,和,Cohn,等人给出了一套空间逻辑用来推理空间数据库中的空间对象间的拓扑关系。,Abdelmoty,等基于广义的交模型定义了线,/,面和面,/,面多种空间对象类型拓扑关系推理组合表。,Renz J,等研究了基于区域连接演算（,RCC,）进行空间拓扑关系推理的理论和方法。,38,基于,RCC-8,的空间区域关系的推理组合表,39,“*”表示全部关系。但,Renz J,的工作没有涉及点、线等空间对象的空间关系的推理，对空间区域的形状等具有很强的限制，不利于扩展。,Li S J,等研究了基于一致性组合表（,RCC8-CT,），对,RCC,模型进行了扩展分析，给出了,RCC8,组合表的扩展形式。,40,为了定性描述和推理形状、大小和位置等随时间发生变化的空间对象间的空间拓扑关系，,Egenhofer,等,9,基于九交模型给出了拓扑距离的定义，给出了相关的概念邻域图，基于概念领域图进一步分析了不同动态变化情形下的空间拓扑关系转变路径。,41,Egenhofer,的研究成果,针对空间面对象的空间关系推理，对点和线对象的空间关系推理无效。,郭庆胜等在线和面空间拓扑关系组合描述的基础上，对线与面的组合推理方法进行了研究，给出了线与面的拓扑关系组合推理表。,42,包含点和线的多维空间对象的空间关系表示和推理,王生生和刘大有将点和线对象视为特殊的区域，提出了能直接用,RCC,理论描述空间多维对象拓扑关系的,MRCC,理论，推导出,36,种基本,MRCC,关系，讨论了基于概念邻域图和复合表的,MRCC,推理。,43,44,拓扑关系描述,拓扑关系相似性,概念邻居图,45,自然语言空间关系,以线,/,面为例,那些关系与语言“道路进入公园”基本一致？,那些关系与语言“道路穿过公园”基本一致？,46,自然语言空间关系,道路进入公园,(Mark, et al., 1994),19,个线,/,面拓扑关系与自然语句“道路进入公园”的一致性程度,47,19,个线,/,面拓扑关系与自然语句“道路穿过公园”的一致性程度,自然语言空间关系,道路穿过公园,(Mark, et al., 1994),48,自然语言空间关系,道路穿过公园,(Mark, et al., 1994),穿过公园的道路必须属于这,5,个关系中的一个,穿过公园的道路不能完全在公园外部或位于其边界上,穿过公园的道路不能有端点在公园内,49,方向关系描述,基本概念,方向关系要素,一个参照对象、一个目标对象,主方向概念。人们认知的方向概念是离散的，能分辨的方向概念个数有限，并且以词语描述为主。如，东、南、西、北等,主,方向个数，即用多少个方向概念来描述空间对象间的方向关系,方向区域。为确定目标对象位于参照对象的那个方向，必须根据参照对象的空间形状和范围，按照主方向的个数，把参照对象所在空间划分成与主方向个数相等的空间区域,50,方向关系描述,评价描述方法的准则,能够统一描述不同维对象之间的方向关系,对参照对象和目标对象的空间形状、大小和岛屿是敏感的,A,B,B,A,B,A,B,A,51,方向关系描述,基本概念,能够与人们的认知概念一致,北,A,A,A,北,北,是可推理和比较的,52,方向关系描述,基本特征,方向关系描述的实质就是确定一个方向关系模型，难点在于采用何种方法对参照对象所在的空间范围进行划分，使得基于这种划分所得到的方向概念与人们的认知概念较为一致,根据需求确定方向关系中原子方向的个数,选择方向区域划分方法，确定每个方向的空间区域,把目标对象映射到根据参照对象确定的方向区域中去，计算目标对象与参照对象之间的方向关系,53,方向关系描述,锥形方法,(,Peuquet, 1987,),北,西,南,东,北,西北,东北,西南,东南,西,东,南,4,个主方向：东、南、西、北,8,个主方向：东、南、西、北、东北、西北、东南、东北,锥形方向区域、等角度划分,把参照对象和目标对象均当作点处理,锥形方法特点,54,方向关系描述,投影方法,(,Frank,1995,),西,东,北,南,东北,东南,西南,西北,西,东,北,南,北,西,南,东,东北,东南,西北,西南,方向区域为半平面或矩形区域,仍然把参照对象当作点处理,55,方向关系描述,MBR,模型,(,Papadias,1995,),A,B,利用参照对象和目标对象分别在,x,轴和,y,轴上投影间的关系来区分和描述方向关系,本质是对参照对象和目标对象均采用它们的外接矩形来近似,56,方向关系描述,MBR,模型,(,Papadias,1995,),Northwest,Restricted_north,Northeast,Restricted_west,Southwest,Restricted_south,Southeast,Restricted_east,north_west(p, q),X(p,c,)Y(q,c,),restricted_north(p,q),X(p,c,)=X(q,c,),Y(p,c,)Y(q,c,),north_east(p,q),X(p,c,)X(q,c,),Y(p,c,)Y(q,c,),restricted_west(p,q),X(p,c,)X(q,c,),Y(p,c,)=Y(q,c,),south_west(p,q),X(p,c,)X(q,c,),Y(p,c,)Y(q,c,),restricted_south(p,q),X(p,c,)=X(q,c,),Y(p,c,)X(q,c,),Y(p,c,)700 and areaval5) or (Tw.tpopulation10000 and NORTH(Su.Location, Tw.Location) and DISJOINT(Su.Location, Tw.Location),找出所有与高速公路距离不超过,5,公里或者在城镇的北部且在城镇外的所有超市,101,空间关系应用,基于图标的查询,(Morris,2004),SELECT * FROM road As Ru, country As Ct,WHERE ( Rd.type = “Motorway” and Ct.tpopulation50000 and CROSS(Ru.Location, Ct.Location),找出所有高速公路和城镇，城镇人口,50000,，且高速公路穿越城镇,102,空间关系应用,基于草图的空间查询,扩展,SQL,是基于文本的查询语言，空间关系的文本描述是模棱两可的，很容易造成误解释或误匹配，尤其是在多语言环境中，同一个词语可能有不同的含义,基于图标的查询语言使用了可视化的图标和界面来描述和组织查询语句，优点是把用户从记忆繁琐而复杂的语法规则中解放出来。但图标查询的语法和句法与结构化,SQL,是类似的，仅仅使用一些由系统预定义的标准图标很难真实而准确地描述对象间的空间关系，仍然会造成误匹配，并且由于不能从细节和数量上描述空间关系，导致匹配的结果集太大，其中一些可能不是用户所期望的结果。,在,基于草图的空间中，用户可以用鼠标、笔或手在触摸屏上画他要查询的空间对象结构，形成草图，包括对象间相对大小比例、空间关系的细节信息以及空间对象形状等。相对图标而言，草图包含了明确而详细的信息，可以做为查询条件提交给,GIS,，通过空间关系相似性匹配就可检索到用户所需的数据。,在,基于草图的空间中，草图的输入方式、管理、组织和描述非常重要。,103,空间关系应用,基于草图的空间查询,(Blaser,2000),104,空间关系应用,空间查询语言,实例介绍,4 ,基于草图的查询,105,空间关系应用,空间场景的相似性,106,空间关系推理,基本概念,GIS,中空间关系推理就是把人们这种推理能力通过某种定理或规律表达处理，以方便计算机实现。具体的讲，空间关系推理就是根据两个已知的空间关系，利用空间关系间蕴藏的规律和知识来推理未知的空间关系,这种推理不需要进行大量的几何计算，就可得到未知空间关系的可能形式，因而可以降