（计算机应用技术专业论文）基于区域拓展的空间关系表示与获取的研究.pdf

江苏大学硕士学位论文 摘要 定性空间推理( q u a l i t a t i v es p a t i a lr e a s o n i n g ) 研究的是人类对空间对象 及其关系定性认知常识的表示与处理。近几年来，定性空间推理已被广泛应用于 空间数据查询、定性导航、地理信息系统等相关领域。研究、分析和探讨定性空 间关系的表示和获取，对定性空问推理的研究和应用有着重要的意义。 本文主要工作如下： ( 1 ) 在对区域连接演算r c c ( r e g i o nc o n n e c t i o nc a l c u l u s ) 理论研究的基础 上，结合数学形态学引入了定性空间推理的演算算子一区域拓展，提出了基于区 域拓展的空间关系形式化表示方法，此方法能以灵活多样的粒度描述区域间的距 离关系、方向关系等多种空间关系。 ( 2 ) 基于区域拓展的空间关系形式化表示方法，给出了一种利用栅格法自 动获取区域问拓扑关系、方向关系和距离关系的方法，开发了一个定性空间关系 获取系统。 ( 3 ) 在组合表和约束处理规则的基础上对定性空间关系的组合表推理技术 进行了研究，并利用逻辑程序语言实现了拓扑关系、方向关系、距离关系和方向 关系的组合推理。 ( 4 ) 在上述研究工作的基础上，对家庭会客厅环境进行了仿真实验，自动 获取家庭会客厅环境中物体间的空间关系，利用获取的空间关系进行定性空间推 理，从而验证了基于区域拓展的空间形式化表示方法的有效性以及基于栅格法获 取空间关系的合理性和实用性。 关键词：定性空间表示，定性空间推理，度量，栅格法，组合表推理，约束处理 规则 江苏大学硕士学位论文 a bs t r a c t t h er e p r e s e n t a t i o na n dd i s p o s a lr e f e r r e dt oq u a l i t a t i v ec o g n i t i v ec o m m o ns e n s e k n o w l e d g ea n dt h er e l a t i o n sb e t w e e nt h e ma r er e s e a r c h e di nq u a l i t a t i v es p a t i a l r e a s o n i n g q u a l i t a t i v es p a t i a lr e a s o n i n gi s a n i m p o r t a n tb r a n c hi na r t i f i c i a l i n t e l l i g e n c e ，a n d i th a sb e e nw i d e l ya p p l i e di ns p a t i a ld a t aq u e r y , q u a l i t a t i v e n a v i g a t i o na n dg i se t ci nr e c e n ty e a r s t h er e s e a r c h ，a n a l y s i sa n dd i s c u s so ft h e r e p r e s e n t a t i o na n do b t a i n m e n to ft h eq u a l i t a t i v es p e c i a lr e l a t i o n sh a v ei m p o r t a n t m e a n i n g sf o r t h er e s e a r c ha n da p p l i c a t i o no fq u a l i t a t i v es p a t i a lr e a s o n i n g t h ec o n t e n t si n c l u d e di nt h i sp a p e ra r el i s t e da sf o l l o w s ： ( 1 ) b a s e do nt h et h e o r yo fr c ca n db yc o m b i n i n gm a t h e m a t i c sm o r p h o l o g ，t h e r e g i o ne x t e n s i o ni si n t r o d u c e di na sq u a l i t a t i v es p a t i a lc a l c u l u so p e r a t o r s ，t h e nt h e f o r m a l i s mm e t r i z a t i o nm e t h o d so fs p a t i a lr e l a t i o n sa r ep r o v i d e da n dt h er e p r e s e n t a t i o n m o d e lb a s e do nr e g i o ne x t e n s i o na r ee x t e n d e d ，a n dd e s c r i b e sm u l t i p l e s p a t i a l r e l a t i o n si n c l u d i n gd i s t a n c e s ，d i r e c t i o n se t ci na tf l e x i b l ea n dv a r i o u sg r a n u l a r i t i e s ( 2 ) b a s e do nt h ef o r m a l i s mr e p r e s e n t a t i o nm e t h o d so fr e g i o n e x t e n d e ds p a t i a l r e l a t i o n s ，am e t h o du s i n gg r i dm e t h o dt oa u t o m a t i c a l l yo b t a i nt h et o p o l o g i c a l ， d i r e c t i o na n dd i s t a n tr e l a t i o n sa m o n gt h ea r e a sa r eg i v e n a no b t a i n i n g s y s t e mf o r q u a l i t a t i v er e l a t i o n si sd e v e l o p e d ( 3 ) o nt h ef o u n d a t i o no ft h ec o m p o s i t i o nt a b l ea n dc o n s t r a i n th a n d l er u l e s ，t h e c o m b i n a t o r i a lr e a s o n i n gf o rt o p o l o g i c a lr e l a t i o n ，d i r e c t i o nr e l a t i o n ，d i s t a n tr e l a t i o n a n dd i r e c t i o nr e l a t i o na r er e s e a r c h e da n dr e a l i z e db y u s i n gl o g i cp r o g r a m m i n g l a n g u a g e ( 4 ) b a s e do nt h ea b o v ew o r k s ，t h r o u g ht h es i m u l a t i o ne x p e r i m e n ti nf a m i l y l i v i n gr o o me n v i r o n m e n ，t h es p a t i a lr e l a t i o n sa m o n go b j e c t sc a nb ea u t o m a t i c a l l y o b t m n e d t h e nt h eo b t a i n e ds p a t i a lr e l a t i o n sa r eu s e dt os t a r tt h eq u a l i t a t i v es p a t i a l r e a s o n i n g t h ee f f e c t i v e n e s so fs p a t i a lf o r m a l i z e dg r i dm e t h o db a s e do nr e g i o n e x t e n s i o ni sp r o v e d t h eo b t a i n m e n to fq u a l i t a t i v es p a t i a lr e l a t i o n sb a s e do ng r i d m e t h o di sp r o v e dt ob er e a s o n a b l ea n da p p l i c a b l e k e yw o r d s ：q u a l i t a t i v e s p a t i a lr e p r e s e n t a t i o n ，q u a l i t a t i v es p a t i a lr e a s o n i n g ， m e t r i z a t i o n ，鲥dm e t h o d ，c o m p o s i t i o nt a b l er e a s o n i n g ，c o n s t r a i n th a n d l er u l e s i i 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容以外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：力写- ) - j 日期：矽口7 年 月 陟 e l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密囱。 学位论文作者签名：力孚t 手j 导师签名： 签字目期：加孵f 月f 午日签字日期： 白举 o 田年sr | 皇日 江苏大学硕士学位论文 1 1 引言 第一章绪论 空间推理( s p a t i a lr e a s o n i n g ) 的研究起源于2 0 世纪7 0 年代初，是指利用空间 理论和人工智能a i ( a r t i f i c i a li n t e l l i g e n c e ) 技术对空间对象进行建模、描述和表示， 并据此对空间对象间的空间关系进行定性或定量分析和处理的过程l l 】。当前国内 外关于空间推理的研究内容主要包括：空间对象的建模、空间知识的表示、对象 间空间关系的表示和推理、空间数据库、推理的可视化、空间和时态推理的结合 以及空间推理的应用等。目前，空间推理被广泛应用于地理信息系统、机器人导 航、高级视觉、自然语言理解、工程设计和物理位置的常识推理等方面，并且正 在不断向其它领域渗透，其内涵非常广泛。空问推理的研究在人工智能的研究中 占有很重要的地位，是人工智能领域的一个研究热点【2 】。 目前，人们对空间关系的研究主要集中在拓扑关系、度量关系和顺序关系等 方面。拓扑关系是指拓扑变换( 如平移、旋转、缩放) 下的拓扑不变量，如空间 对象的相邻和连通关系。度量关系是用某种度量空间中的度量指标来描述对象间 的关系，如对象间的距离、大小等；顺序关系是用来描述对象在空间中的某种顺 序关系，如前后、上下、左右关系等；顺序关系中研究最多的关系是方位和方向 关系。方位关系是指相对于地理空间的方位概念如东、西、南、北等；而方向关 系是指人类认知中的方向概念如前后、左右等。 定性空问推理( q s r ，q u a l i t a t i v es p a t i a lr e a s o n i n g ) 是对定性空间关系的表示、 分析与处理，它研究的是人类对几何空间中空间对象及其定性关系认知常识的表 示与处理过程。所涉及的定性空间关系主要包括拓扑、方向、距离等空间特征关 系。拓扑关系是空问关系中最重要的基本关系，其模型可分为区域拓扑【3 4 ，5 1 和点 集拓扑两大类，它们都有比较完整的理论体系。方向关系描述了对象之间的空间 顺序关系，其主要描述方法有基于锥形、基于投影等。距离关系是空间对象问的 度量关系，c l e m e n t i n i 等人【6 j 将距离划分为不同层次( 如近、中、远等) ，给出了 划分的原则，并且结合“基于圆锥”的方向模型与距离关系，提出了位置演算方 法。 江苏大学硕士学位论文 对空问拓扑关系、距离关系和方向关系的集成表示研究、分析，以及对空间 关系表示的获取技术和空间推理技术的探讨，在现实和学术中具有极其重要的意 义。 1 2 定性空间表示 1 2 1 拓扑关系 拓扑关系是空间关系中最重要的基本关系，是指在拓扑变换下( 如平移、旋 转、缩放) 的拓扑不变量。空问拓扑模型分为两大类：点集拓扑和区域拓丰i t 4 , 5 , 8 】， 它们都有比较完整的理论体系。 区域连接演算r c c ( r e g i o nc o n n e c t i o nc a l c u l u s ) 理论基于空间区域连接关系 c ( x ，y ) ，c ( x ，y ) 表示“区域x 和y 至少共享一个点”，c l a r k e 把c ( x ，y ) 作为原语概 念，提出了个体演算描述空间拓扑关系。1 9 9 2 年，r a n d e l l 等1 7 ，8 1 在此基础上将原 语c ( x ，y ) 解释为两个区域的拓扑闭包有一个公共点，得到了许多c l a r k e 不能得 到的定理，成为区域拓扑中最重要的理论。 由c ( x ，y ) 可以推导出r c c 5 ，r c c 8 ，r c c 1 5 等多种拓扑关系模型分别对 应着不考虑边界、考虑边界以及考虑时态的各种不同的情况。这些r c c 模型中 最重要的是r c c 一5 模型和r c c 一8 模型。r c c 5 模型区分了5 种j e p d ( 互不相 交且联合完备) 的r c c 关系 分离d r ，相交p o ，相等e q ，真部分p p ，反真部 分p p i ，。而r c c 8 模型区分了8 种j e p d ( 互不相交且联合完备) 的r c c 关系： 相离d c ，相邻e c ，交叠p o ，相等e q ，被覆盖t p p ，被包含n t p p ，覆盖t p p i 和包含n t p p i 。r c c 5 关系是最小的拓扑基本关系集合之一，r c c 理论定义的 其他关系大多数可看作是对r c c 5 关系的细化。 b e n n e t t l 9 , 1 0 】先后使用经典命题逻辑和模态逻辑对r c c 理论重新进行了表示， 使用的这两个逻辑都是可判定的。使用经典命题逻辑和模态逻辑主要是为了分析 空间关系集合的计算复杂性。 1 9 9 1 年e g e n h o f e r 等人【1 1 1 2 】采用点集拓扑方法对简单区域( 在二维空间中， 与闭合圆盘同构的有边界闭合点集，即内部是连通的、没有空洞) 间拓扑关系进 行了定义，提出了点集拓扑的n 一交集模型。4 交模型( 4 i m ) 对二维空间的面类 型对象的拓扑关系进行了划分。在这个模型中，拓扑关系的划分是基于两个对象 2 江苏大学硕士学位论文 和五的边界和内部的交。每个交可以是空或非空，所以有2 x 4 = 1 6 种可能的情 况。后来考虑每个区域由三个点集组成：内部、边界和外部。两个区域之间的拓 扑关系由三个点集的交的空或非空决定，对应一个3 3 的矩阵，即9 交模型 ( 9 i m ) 。通过考虑实际的物理空间，矩阵所取的可能的值最终可归纳为与r c c 8 理论相同的8 个关系。9 一交集模型比4 一交集模型的描述能力要强的多。n 一交模型 因其理论是建立在点集拓扑的理论基础之上，所以具有统一、简洁的形式，因此 n 交集成了表示拓扑关系的一种普遍采用的方法。 为了进一步研究空间拓扑关系，1 9 9 3 年c l e m e n t i n i 等人在e g e n h o l f e r 定义 的n 交集的基础上，引入维扩展法( 即用两个空间区域边界和内部之间交集的维 数) 对点集空间拓扑关系进行了扩展。 1 2 2 方向关系 方向关系是空间关系的重要组成部分，是一类重要的二元空间关系，它和拓 扑关系、距离关系一起构成了基本的空间关系。例如：东、南、西、北是一组方 向关系，利用它可以表示空间对象间的方向关系。方向关系依赖于主对象、参考 对象和参考框架。r e t z s e h m i d t 1 3 】将参考框架分为三个不同的参考框架：内部参 考框架、直接参考框架和外部参考框架三类。这三类参考框架是使用最广泛的空 间方向关系参考框架。空间方向关系在空间目标智能查询、模式识别、地理信息 可视化等领域有着广泛的应用。 空间方向关系相关的研究成果如下： ( 1 ) 锥形模型 1 9 7 6 年h a a r 提出了空间方位表示的锥形模型( c o n em o d e l ) 。该模型以参考 对象的质心作为原点，用通过原点的两条相互垂直的直线将空间区域划分成四个 无限的锥形区域，每个锥形区域对应着一个主方向( 如，东、南、西、北) ，目 标对象所落在区域的主方向即是目标对象相对于参考对象的方向。 1 9 8 7 年，在基本的锥形模型基础上，d p e u q u e t 1 5 】等以空间对象的最小边界 矩形m b r ( m i n i m u mb o u n d a r yr e c t a n g l e ) 来近似表示空间对象，并用m b r 间的 方向关系来代替对象间的方向关系对锥形模型进行了改进，m b r 模型能够判断 一些较复杂对象间的关系。 锥形模型的灵活性在于可以根据需要，通过参考对象的质心作多条直线，由 3 江苏大学硕士学位论文 此能够方便地调整主方向的数目，来适应实际情况的需要。 ( 2 ) 2 d 字符模型 2 d 字符模型( 2 d s t r i n gm o d e l ) 胖- 由s k c h a n 9 1 1 6 j 等提出，它是用字符串序 列来表示方向关系。在目标对象中用固定大小的网格将整个区域覆盖，并记录每 个网格中的目标标识符，然后将网格中的目标标识符按顺序排成两个序列( 如， x 方向序列和y 方向序列) 。通过对序列的分析可以获得对象问的方向关系。 ( 3 ) 投影模型 投影模型是将对象投影到坐标轴上并比较投影坐标值的大小来确定对象间 的方位关系。基于投影的方向模型使用通过参考物体的垂直线和水平线来划分空 间。选择不同的投影坐标轴将得到不同的投影模型。一条水平线把空间划分为北 与南两部分，称为水平投影模型；而一条垂直线把空间划分为东与西两部分，称 为垂直投影模型；同时使用水平线与垂直线将空问划分为东北、东南、西南、西 北四个部分，称为垂直一水平投影模型。 投影模型能够较好地表示空间点对象间的方位关系。例如，任意两个点对象 a 、b ，它们在水平投影下x 坐标分别记为凡、吸，那么有： d i r a b = e 当4 最 d 当及= 最 ( 4 ) 井字空间模型 以参考对象的最小边界矩阵m b r 来近似表示它，并做垂直一水平投影，得 到井字参考模型。井字参考模型将空间划分成9 个区域。这9 个区域记为9 个方 位关系d 9 = r e ，r s ，r w , r n , n w , n e ，s e ，s w , o ) ，各个对象本身通过与9 个区域之 间交的结果来描述它们与参照对象之间的方向关系。 ( 5 ) 双十模型 1 9 9 2 年f r e k s a 1 7 1 在基于投影方法的基础上，提出了“双十字 方向模型。 该模型基于人类感知空间的方式，将空间关系分为“前”、“后 、“左、“右”等。 和以前的模型相比主要的区别之一是对象( 点) 的位置不是相对于另一个位置来 说，而是相对于一个描述对象在两个位置间移动的向量。这样，可以将空间区分 为1 5 个关系。 ( 6 ) 其它方法 4 江苏大学硕士学位论文 除前述5 种方向关系表示模型以外还有其它的表示模型。如，d r m 模型、 四半无限区域( f s i a ，f o u rs e m i i n f i n i t e a r e a ) 模型，方向v o r o n o i 图模型等。 1 2 3 距离关系 距离关系是空间对象之间最基本的空间属性之一，它是空间对象问的某种度 量关系。距离不同于拓扑与方位的方面在于它是标量。距离的表示分为绝对距离 和相对距离，绝对距离关系直接表示两个空间对象之问的距离，相对距离关系通 过与第三个对象做比较得到的距离关系。 绝对距离关系可以定性表示，也可以定量的表示。而相对距离关系一般是定 性的表示。绝对距离关系的定性表示依赖于使用的空问的规模。大多数处理定性 距离的方法使用点作为基本的空间实体。绝对距离关系可以选择不同的粒度层次 划分距离关系，第一个粒度级上有两个定性距离关系：c l ( 近) 和f ( 远) ，这两个距 离关系将参考对象周围的空间划分为两个区域，外部区域趋向于无穷远。还可以 引入更多的粒度级。例如：划分为三种定性距离关系的粒度级【1 2 】：c 1 ( 近) ，r o d ( 中 等) 和f ( 远) ；划分为四种定性距离关系的粒度级：v c l ( 很近) ，c l ( 近) ，坟远) ，v f ( 很 远) 。五种距离划分的粒度级：v c l ( 很近) ，c l ( 近) ，m d ( 中等) ，坟远) ，v f i 很远) 。等 等( 见图1 1 ) 。显然，如果有必要还可以引入超过5 种定性距离关系划分的粒度 级。 n w 1 3 定性空间推理方法 w 图1 1 显巨离关系的划分 空间推理是从几何、使用和功能三个方面研究空间知识的表示和处理。最初 是以量空间为研究对象的。最近几年，由于认识到空间知识的本质是定性的，定 性空问推理研究成为空间推理研究的主流。定性空间推理的基础是定性空间知识 5 江苏大学硕士学位论文 库，采用组合表【1 8 , 1 9 , 2 0 , 2 1 , 2 2 】二公理化、代数方法【2 3 , 2 4 , 2 5 1 、几何约束满足【2 6 ，2 7 1 等推 理方法可以完成推理任务。 ( 1 ) 在空间知识表示中采用较多的是组合表，组合表结构简单。 组合表推理是空间关系事实的一种演绎推理，它从两个已知关系事实r ( a ，b ) 和r ( b ，c ) 推理得出仅含a , c 的新的关系事实r ( a ，c ) 。它的可行性在于无论是拓扑 关系还是方位关系，其关系全集均是有限集合。它的合法性在于多数情况下推理 不依赖于己知的事实，而依赖于关系的逻辑属性。这一方法的可行性和合法性使 得它成为空间关系推理的有效工具。 ( 2 ) 公理化方法以逻辑学或部分学( m e r e l o g y ) 为基础，选择一组基本的关系和 谓词建立一类空问概念和关系的公理和推理规则，以此表示并处理空间知识。这 类方法的代表性工作是r c c 理论2 8 , 2 9 】，r c c 理论利用部分学和拓扑学的概念建 立了一个关于定性空间推理的具有完整语义描述的完备公理系统。 r a n d e l l ，c u i 和c o h n 通过空问谓词c ( x ，y ) 定义空间逻辑系统，将空间对象间 的拓扑关系用谓词公式进行表示，利用一阶谓词逻辑建立了一阶逻辑范畴下空间 拓扑关系推理技术。b e i l n e t t 【3 0 l 对空间拓扑模型r c c 8 与命题逻辑的关系进行了 研究，对空问实体间的拓扑关系以命题逻辑的形式进行编码。1 9 9 6 年b e n n e t t 3 1 j 将模态逻辑引入到空间拓扑关系的描述和推理中，并给出了r c c 8 的模态逻辑 表示。 ( 3 ) 代数方法【3 2 , 3 3 , 3 4 1 把空间关系作为项来处理，在构造出基本空间关系的原子 复合表后，可以利用约束满足算法对关系集实现复合运算完成推理，也可以建立 全部关系集复合运算的完全复合表，通过查表实现推理。该方法使推理变得简单， 但代数系统的表示能力常常受到限制。 代数方法是a l l e n 3 5 , 3 6 , 3 7 1 在基于区间的时态逻辑理论中提出来的，后来在定 性空间推理领域得到应用，且在空间关系集代数运算等方面取得了进一步的发 展。 ( 4 ) 几何约束满足方法充分表示并利用几何领域的约束通过约束满足方法实 现空问知识的表示和推理。 1 9 9 3 年d u v e r d i e r 在利用几何约束满足方法研究空间规划问题时，提出了空 间位置关系和方位关系的序结构；1 9 9 4 年h e m a n d e z 在利用几何约束满足方法研 究位置关系时，在位置关系的概念邻域结构的基础上提出了抽象图表示方法。这 6 江苏大学硕士学位论文 些工作发展了几何约束满足方法。 以上方法都是空间推理的基本方法。随着人们对常识知识表示和推理的深入 研究，人们又提出了不同的空问推理方法。空间推理方法的不断研究促进了空间 推理的发展。定性空间推理作为人工智能学科处理常识性空间知识的一种方法， 其研究还有很多不足和缺陷，需要人们继续努力研究解决这些问题。 1 4 本文的主要研究工作 近年来，空间推理的理沦发展非常迅速，随着空间推理研究的深入，定性空 间推理的研究成为空间推理研究的主流。本文首先对定性空间表示和推理进行了 研究，研究了基于区域拓展的定性空间表示模型和基于栅格法的定性空问关系获 取模型，最后将获取的空间关系应用到定性空问推理中。本文的主要贡献如下： ( 1 ) 在对r c c 理论研究的基础上，结合数学形态学提出了定性空间推理的 演算算子一区域拓展，提出了以区域为度量单位的空间关系形式化的表示方法， 基于区域拓展扩展了空间关系表示的模型。 ( 2 ) 在对栅格法研究的基础上，基于区域拓展设计和实现了区域问拓扑关 系、方向关系和距离关系的自动获取，开发了一个定性空间关系获取系统。 ( 3 ) 在组合表和约束处理规贝j j ( c h r s ) 基础上，利用逻辑程序语言p r o l o g 实 现了拓扑关系、方向关系、距离关系和方向关系的组合推理。 ( 4 ) 对家庭会客厅环境进行了仿真实验，自动获取家庭会客厅环境中物体 间的空间关系，利用获取的空间关系进行定性空间推理，验证了基于区域拓展的 空问形式化表示方法的有效性以及基于栅格法获取空间关系的合理性和实用性。 1 5 本文的组织安排 全文共分七章，涉及定性空间拓扑关系、方向关系以及距离关系的表示，基 于区域拓展的空间关系表示、基于栅格法的空间关系的获取和基于组合表的定性 空间推理模型，最后给出了一个自动获取空间关系的应用实例以及对实例获取的 空问关系进行定性空间推理验证，并对结果进行了分析。 第一章绪论，介绍了定性空间表示和推理的基本概念与研究内容，以及国 内外研究现状，并分析了现有研究中的一些不足，确定了本文的研究内容。 7 江苏大学硕士学位论文 第二章关于r c c 模型推理的研究，为研究基于区域拓展的空间关系表示模 型奠定了逻辑基础。 第三章在r c c 模型基础上，以及对数学形态学的研究引入区域拓展这个演 算算子扩展了基于空问关系的表示模型。将r c c 5 拓扑关系扩展为t r c c 一5 拓 扑关系，定义了区域间的距离关系( 包括绝对距离和相对距离) 和方向关系。由 于引入区域拓展，给出了空问关系定性表示与度量相结合的一科，途径，增强了 r c c 的空间关系表达能力，扩展了r c c 理论的应用范围。 第四章根据第三章提出的空间关系表示模型，利用栅格法给出了空间关系 的自动获取算法，实现了空间关系的获取，且开发了定性空间关系获取系统。 第五章采用代数和组合表相结合的方法给出了拓扑关系组合表、方向关系 组合表以及距离关系推理模型，并且给出了空问关系推理的组合推理程序。 第六章在第三章和第四章研究的基础上，对家庭会客厅环境进行了仿真实 验，验证了基于区域拓展的空间形式化表示方法的有效性以及基于栅格法获取空 问关系的合理性和实用性。 第七章总结全文所做的工作和创新之处，同时提出了一些需要进一步深入 研究的内容。 8 江苏大学硕士学位论文 第二章基于逻辑的r c c 推理 定性空间推理的基础是定性空间关系的表示。空间关系主要研究的方向、距 离、拓扑关系等。在研究拓扑关系表示和推理模型中，影响最大的就是区域连接 演算( r c c ) 模型，本章节将对r c c 模型进行详细介绍。 区域连接演算( r c c ) 是由r a n d e n 等人为实现定性空间表示与推理而提出的 一阶理论。该理论是在c l a r k e 的个体连接演算的基础上提出来的，它修正了在 c l a r k e 3 8 , 3 9 1 系统中存在的几个问题，形成了一套正式的空间的表示与推理的形式 化系统。这就促成了区域连接演算理论的产生与发展。 2 1r c c 模型理论基础 区域连接演算r c c ( r e g i o nc o n n e c t i o nc a l c u l u s ) 模型，最早是由r a n d e l lc u i 和c o h n 提出的表示具有相同拓扑维数的空间对象( 如线与线，区域与区域) 之 间拓扑关系的模型。r c c 理论的基础是称为连接的函数c ( x ，坳，解释是两个区 域x 和y 至少共享一点，然而在r c c 理论中新的解释是两个区域拓扑的封闭区 域共享一点。 定义2 1 ：设x 、】，是区域，函数 c c 础，= 器篆慧：藿簇鬣呐 从c 的定义可以得到如下两个性质，也称为c 的公理： 自反性：诋【c ( x ) 】 。 对称性：v x v y c ( x , y ) jc ( y 歹) 】 在没有明确指出的情况下，函数和谓词的所有参数都是定义的区域类，下面 给出用c 定义的一些关系，如表2 1 所示。其中的关系p ，p p ，t p p 和n t p p 是 非对称的同时支持逆关系。对于这些关系的逆关系分别用p i ，p p i ，t p p i 和n t p p i 来表示。在r c c 理论的基础上，许多学者进行了进一步的研究。当不考虑区域 边界时，可以得到r c c 5 ，r c c 5 集合 分离d r ，相交p o ，相等e q ，真部分 p p ，反真部分p p i 是互不相交且是联合完备( j e p d ) 的。当考虑区域边界时，可 以得到r c c 8 ，r c c 一8 集合 相离d c ，相邻e c ，交叠p o ，相等e q ，被覆盖 江苏大学硕士学位论文 t p p ，被包含n t p p ，覆盖t p p i 和包含n t p p i 也是互不相交且是联合完备( j e p d ) 的。考虑非凸区域，通过研究区域闭包构造了r c c 一1 5 和r c c 2 3 。利用部分论 ( m e r e o l o g y ) ，b b e n n e t t 等研究了基于区域的定性几何学。j g s t e l l 等研究了区域 集合的代数结构和基于区域连接演算( r c c ) 的布尔连接代数。目前，基于r c c 理论的研究工作还在继续开展。 表2 1 根据c 定义的一些关系 关系解释关系的定义 d c ( x ，y )x 与y 不连接_ 1 c ( x ，y ) p ( x ，y )x 是y 的一部分v z c ( z ，x ) 专c ( z ，y ) 】 p p ( x ，y )x 是y 的真部分e ( x ，j ，) a 尸( y ，x ) e q ( x ，y )x 与y 相等 p ( x ，j ，) a p ( y ，x ) 0 ( x ，y )x 与y 重叠3 z p ( z ，x ) ap ( z ，y ) 】 d r ( x ，y )x 与y 相离- 1 d ( x ，j ，) p o ( x ，y )x 与y 部分重叠o ( x ，y ) a - , p ( x ，y ) a p ( y ，x ) e c ( x ，y )x 与y 外部相连c ( x ，j ，) a _ 1 d ( x ，少) x 是y 的真部分 t p p ( x ，y )胛( x ，y ) a3 z e c ( z ，力ae c ( z ，y ) 】 且与y 相切 x 是y 的真部分 n t p p ( x ，y ) p p ( x ，j ，) a - - , 3 z e c ( z ，x ) ae c ( z ，少) 】 且不与y 相切 2 2r c c 关系的连续变化 目前为止，对于空间区域结构的描述，考虑的只是其静态属性的一面而没有 考虑空间区域的结构随时间是怎么变化的。在很多领域中，区域结构的动态推理 的研究具有重要意义。在很多领域中，都做出这样的一个假设：变化是连续的。 在定性空问推理中，连续性假设就是假定形状的改变和移动都具有连续性。图 2 1 给出了r c c 5 中在考虑连续性时可能的状态转变。 例如，在一个从关系d r 向p p 的连续变化中，一定也包含p o ，这可以用概 念邻域图来表示。 l o 江苏大学硕士学位论文 o o d r p o 图2 1r c c 5 中拓扑关系的连续变化 2 3r c c 5 的命题逻辑表示 e q b e n n e t t 用i o 表示古典逻辑演算3 0 1 ，古典逻辑演算和集合论有着密切的联系， 它的朴素的语义是：把命题看作真值的表示，并且将联结词作为相对应的真值函 数。把命题逻辑的命题看做全集u 的任意一个子集，并且联结词“，、 、v ” 分别表示集合操作的“补、交、并”，则命题逻辑就是u 的子集的命题形式表示， 其中u 为全集。那么命题逻辑在全集u 中总为真。其语义可以形式化的表示为： 逻辑i o 的模型的结构式 ，其中u 是个非空的集合，p 是一个有限的命 题常量的集合，d 是一个映射函数，这个函数p 的常量是u 的子集的一个映射。 d 的定义域通过规定d ( 一p ) = d ( p ) ，d ( e q ) = d ( p ) nd ( q ) ， d ( p vq ) = d ( p ) u d ( q ) 扩展到所有i o 的命题常量的逻辑形式。 下面给出r c c 关系的重要子集r c c 5 的命题逻辑表示。首先给出下面的集 合表达式：a 是b 的一部分，当a 是b 的一部分并且a 和b 不相等的时候表达 式p p ( a ，b ) 成立，这样可以得出一个集合等式么ub = 2 ，和一个集合不等式 ( 彳u b ) n ( a u b ) u 。在以上的表示中，没有排除a 和b 为空集的情况，因此 在此规定a u ，b g ，那么得到的等式编码为模型约束，不等式编码为限制 约束。因此关系p p ( a ，b ) 的逻辑表示是一对( 么专b ) ， 彳b ，卅，1 b ) ) 。 ( 1 ) 模型约束 对于模型约束，假设有这样一个情形：在区域空间中存在两个区域分别是区 域a 和区域b ，区域a 和区域b 的集合关系是：区域a 和区域b 相离。那么可 以得到这样的关系：b 和a 的交集的补集是全体区域空间u ，可以用等式 够 江苏大学硕士学位论文 a n b = u 来表示，由于它与命题逻辑是一致的，也可以这样用_ 1 ( 彳a b ) 表示， 这个公式叫做与该情形有关的模型约束。因此必有下面的结论：当且仅当a 是b 的一部分的时候，任何模型a - 9 , b 都表示全域，永远为真。利用以上这些公式， 可以定义四种拓扑关系，如表2 2 。 表2 2 四种拓扑关系的描述、集合等式与模型约束 拓扑关系描述集合等式模型约束 d r ( x ，y )x 和y 相离x n y = “_ 1 ( x a y ) e ( x ，y )x 是y 的部分 x u y = 甜 x 专y p “( x ，y )y 是x 的部分 x u y = u yjx e q ( x ，y )x 和y 相等 ( x u y ) n ( x u 】，) = u xby 当每个命题符号都表示非空区域的时候，这个关系定义和r c c 关系高度一 致。当然这个规则也存在着例外，那就是当x 是y 的一部分，且x 和y 相离， 只有在x 为空时才成立的。 ( 2 ) 限制约束。 对于上述的模型约束表示具有一定的局限性，很多由集合等式定义的简单空 间关系都不能单独由模型约束来表示。例如，有如下的关系p p 。1 ( x ，y ) ，对于 p p 。1 ( x ，y ) 其意义是y 刚好是x 的一部分，此集合关系就不能用模型约束来表示， 但是这个关系可以用p 1 ( x ，y ) 来定义是为真的，但是却不能用e q ( x ，y ) 来定义。 如果能找到一种方式来定义缺少的p 。( x ，y ) ，那么这个问题就可以解决了。 根据以上对命题逻辑的讨论可以定义r c c 5 中拓扑关系见表2 3 。 表2 3r c c 一5 拓扑关系的模型约束与限制约束 关系模型约束限制约束 d r ( x ，y ) ( x a y ) - 1 x - 1 】厂 p o ( x ，y )叫v - 1 】，彳专】，】，一x ，o ，_ 1 】， p p ( x ，y ) xj y yjx ，o ，- 、y p p 。1 ( x ，y ) yjx xjy ，- 、y e q ( x ，y ) x 锖y 、y ， 】， 与关系相一致的模型约束在所有的这些关系模型中都是成立的公式。限制约 束排除了一些关系( 这些关系是和模型约束不相容的) ，因此限制约束和其他关 1 2 江苏大学硕士学位论文 系的模型约束是相容的。关系p o 在模型约束中是不能定义的，但是可以通过排 除其他的关系来定义它。 2 4 拓扑关系的一致性检验 可以使用g 理论作为有效的自动进行空间推理系统的基础。b e n e e t 简要的 总结了这个g 算法的一致性检验，而且还给出了一个情形描述，这个情形描述 是有r ( a ，) 的关系集合组成的。在g 中，r 是一个关系特征，两个参数口和 表示区域，下面的算法简单的描述了一个可能的情形。 ( 1 ) 对于情形描述中的每一个关系置( ，屈) 可以找到相对应的命题逻辑表示 ( m ，q ) 。 ( 2 ) 构造g 的命题表示：( m ，u q ) 。 ( 3 ) 对于每一个公式f v ，应用古典命题逻辑系统去证明以确定是否这个 u m 卢c of 成立。 ( 4 ) 如果有f 使得模型约束成立，同时f 也成立的话，则这种情形就是不可 能的。 2 5 对r c c 理论的进一步研究 r c c 理论的研究是建立在逻辑演算基础上的。r c c 理论在很多领域中具有 重要的应用价值。例如在地理信息系统中、自治机器人导航、时空数据库、计算 机视觉有着广泛的应用。 定性空间推理处理的是空间实体间不同的属性和特征，不同空间属性采用不 同的推理方法。目前的空间关系的形式化描述不能对拓扑、方向和距离等进行整 体的考虑。r c c 理论难以描述除拓扑关系之外的其它空间关系，这样就限制了 r c c 理论在其他应用领域中的发展和应用。为此，在数学形态学研究的基础上， 定义自己的运算一拓展。将拓展运算引入到定性空间推理中，对r c c 理论进行 了扩充，增强r c c 表达能力。同时还可以定义空间区域问的方向关系和距离关 系。 1 3 江苏大学硕士学位论文 2 6 本章小结 本章主要介绍了r c c 理论，探讨了r c c 理论的理论基础和r c c 关系的连 续变化，以及对r c c 5 的命题逻辑的表示进行了研究；并介绍了对r c c 理论进 行扩展的方法。 1 4 江苏大学硕士学位论文 第三章基于区域拓展的空间关系表示 在空间推理的研究领域中，空间关系的表示和推理是空间推理的两个主要研 究内容，空间关系的表示又是空问推理中知识表示的核心问题。在现有的空间推 理研究中，描述空间关系的定量方法不适合空间认知和推理，而定性方法通常忽 略了对度量特性的研究。这使得对空间关系的描述存在着一定的局限性，不能准 确的描述空问关系，从而不能满足实际的应用。同时现有的空间关系的表示方法 主要是适用于表示一种空间关系，比如单纯的表示空间拓扑和方向关系，而在实 际的应用中通常是需用集合几类空间关系的。就此问题已有很多学者尝试采用拓 扑、方向、距离等空间关系的相互限制性进行空间的集成表示和推理，但是由于 所集成的表示模型往往缺乏统一的理论基础、计算复杂、容易产生冲突等问题。 鉴于以上问题，在r c c 理论的基础上，和对数学形态学研究的基础上，提 出了区域拓展演算。基于区域拓展，不仅扩展r c c 一5 拓扑关系，而且能够形式 化描述区域i 、h j 的距离关系、方向关系等。引入了一种以区域为基元的度量方法， 在实际应用中能够以灵活多样的粒度更准确地描述多种空间关系。 3 1 数学形态学的基本理论 数学形态学f 4 0 ，4 1 ，4 2 】是- r 建立在严格的数学理论一集合论之上的学科。它体 现了逻辑推理与数学演绎的严谨性，又要求具备与实践密切相关的实验技术与计 算技术。它涉及微分几何、积分几何、测度论、泛函分析和随机过程等许多数学 理论，其中积分几何和集论是其赖以生存的基石。在1 9 6 5 年，j s e r r a 和g m a t e r h o i t l 奠定了这门学科的基础。在许多图像分析应用中