（计算机应用技术专业论文）基于图的主方向关系一致性检验.pdf

摘要 摘要 一致性检验问题是一个基础理论问题，是空间方向关系推理研究领域 的重要分支，越来越引起研究者的注意。就一般情况而言，一致性检验是 n p 完全的，由此，国内外学者主要都是针对特定子类凸关系网络展开 研究，虽采用的合成运算方法不同，但最终的判定原理大都是基于业内现 有的“路径一致性理论”，传统的纯数学方法没有新的突破。 本文分别对区域物体和点物体，给出了新的解决方案，一种基于有向 图的可视检验，为一致性检验提供了新的思路。首先论文给出了区域物体 方向关系的图模型的一系列相关定义，通过划分，把每一组方向关系转化 为有向图，即节点代表对象，有向边表示它们之间的方向关系。然后依据 一定规则对整个约束关系集的划分图进行合并、精炼，得到最终的 s g v ( s p a t i a lg r a p hi nv e r t i c a l ) 。通过检验s g v 中是否存在环来检验其一致 性，若有环存在则说明给定的方向关系集是不一致的，同时给出了理论证 明。最后运用实例证明了该方法的正确性。 随后本文义讨论了点物体的主方向关系一致性检验，基本思路是通过 引入欧几里德空间坐标图的概念，即全局坐标系统与地理的外部参考框架 一致，然后根据主物体和参考物体的方向关系，分别对主物体和参考物体 在x 一轴和y - 轴进行投影的方式构建坐标图，从而使得一致性检验问题转化 为检查图中是否存在环的问题。最后论文给出了实施伪码算法，时间复杂 度是d ( n + p ) ，优于a l l e n 的0 ( n 2 ) 。 关键词定性空间推理；主方向关系；一致性检验；划分；合并；垂直空间 图；坐标图 燕山大学工学硕士学位论文 a b s t r a c t c o n s i s t e n c yc h e c k i n gp r o b l e m i saf u n d a m e n t a lt h e o r yc a s e ，a n db e c o m e sa m o s tb r a n c ho f r e a s o n i n g0 1 1s p a t i a ld i r e c t i o nr e l a t i o n s m o r ea n dm o r er e s e a r c h - e r sb e g i nt of o c u so nt h ef i e l d i ng e n e r a l ，c o n s i s t e n c yc h e c k i n gi sn p c o m l e t e ， m o s to fr e s e a r c h e r sh o m ea n da b r o a dc o n c e n t r a t eo nt h es u b c l a s so fc o n v e x r e l a t i o n s a l t h o u g ht h e yu s ek i n d so fc o m p o s i n gm e t h o d s ，m o s to ft h e i rf i n a l r e s u l t sa l eb u i l to nt h e t h e o r yo f “p a t hc o n s i s t e n c y ”t r a d i t o n a r yp u r e m a t h e m a t i c sm e t h o dh a sf e wb r e a k t h r o u t h t h i sp a p e rp r e s e n t san e ws o l u t i o nf o rr e g i o no b j e c t sa n dp o i n to b j e c t s ，a v i s u a lc h e c k i n gb a s e do i ld i r e c t e dg r a p h , w h i c hp r o v i d e san e ww a y f i r s t l y ，a s e r i e so fd e f i n i t i o n so fg r a p hm o d e la b o u tr e g i o no b j e c t sa r ei l l u s t r a t e d ，e v e r y s e to fd i r e c t i o n a lr e l a t i o ni st r a n s l a t e di n t od i r e c t e dg r a p hb yp a r t , i o n ，n a m e l y , n o d e sr e p r e s e n to b j e c t sa n de d g e sd e n o t er e l a t i o n sb e t w e e np r i m a r yo b j e c ta n d r e f e r r e n c eo b j e c t t h e na c c o r d i n gt og i v e nr u l e s ，t h eg r a p ho fw h o l er e l a t i o n s p e c i f i c a t i o n sw a sm e r g e da n dr e f i n e d ，as p a t i a lg r a p hi nv e r t i c a l ( s g vf o rs h o r t ) i sg e n e r a t e d i fa c y c l ei sd e t e c t e di ns g v , t h e nt h eg i v e ns p e c i f i c a t i o n sa l ei n - c o n s i s t e n t l a s t l yt h i sp a p e rp r o v e st h ec o r r e c t n e s so ft h i sm e t h o di nt h e o r ya n d b ye x a m p l e i m m e d i a t e l y , t h ep a p e rd i s c u s s e sp o i n to b j e c t s ，t h eb a s i ci d e ai st oi n t r o d u c e t h en o t i o no fc o o r d i n a t e sg r a p h ，t h a ti sg l o b a lc o o r d i n a t e ss y s t e mc o r r e s p o n d i n g t og e o g r a p h i cr e f e r r e n c ef r a m e ，b yp r o j e c t i n gd i r e c t i o nc o n s t r a i n t so nb o t hx a n dya x i st of o r mc o o r d i n a t e sg r a p h ，c o n s i s t e n c yc h e c k i n gi st h e nt r a n s f o r m e d t oag r a p hc y c l ed e t e c t i o np r o b l e m a tl a s tt h ep a p e rg i v ei t s p s e u d o c o d e a l g o r i t h mw h i c hc a nb ea c h i e v e dw i t h0 ( h + 力t i m e ，e x c e e d i n ga l l e n so ( n 2 ) k e y w o r d sq u a l i t a t i v es p a t i a lr e a s o n i n g ；c a r d i n a ld i r e c t i o nr e l a t i o n ；c o n s i s t e n c y c h e c k i n g ；p a r t i t i o n ；m e r g e ；s p a t i a lg r a p hi nv e r t i c a l ；c o o r d i n a t e s g r a p h i i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于图的主方向关系一 致性检验，是本人在导师指导下，在燕山大学攻读硕士学位期问独立进行 研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人 已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集 体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字 勿k 林 1 日期珈严聊日 燕山大学硕士学位论文使用授权书 基于图的主方向关系一致性检验系本人在燕山大学攻读硕士学位 期问在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所 有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全 了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山 大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全 部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于， 不保密d ( 请在以上相应方框内打“”) 作者签名= 列易孙 导师签名：毋1 嘉甜1 日期：词年p 月叼日 日期一一7 年2 月彭日 第1 章绪论 1 1引言 第1 章绪论 空间推理是指利用空间理论和人工智能a i ( a r t i f i c i a li n t e l l i g e n c e ) 技术 对空间对象进行建模、描述和表示，并据此对空间对象间的空间关系进行 定性或定量分析和处理的过程i l 】。目前，空间推理被广泛应用于地理信息系 统、机器人导航、高级视觉、自然语言理艇、工程设计和物理位置的常识 推理等方面，并且正在不断向其他领域渗透，其内涌非常广泛。空间推理 的研究在人工智能中占有很重要的地位，是人工智能领域的一个研究热点。 地理信息系统g 1 s ( g e o g r a p h i ei n f o r m a t i o ns y s t e m ) 是空间推理应用得最为广 泛的领域之一，也是空间推理的研究热点之一。 当描述一个空间配置或对这样的配置进行推理的时候，要获得精确、 定量的数据通常是不可能的或是不必要的。在这种情况下，可能要用到关 于空间配置的定性推理1 2 ，”。定性空间表示包括许多不同的方面，我们不仅 要判定什么样的空间实体是我们可以接受的，同时还要考虑描述这些空间 实体之间关系的不同方法。例如，我们可以考虑它们的拓扑结构、大小、 形状，或它们之间的距离。当然，这些概念之间并不是完全独立的【4 】。由于 空间知识本质上是定性的，所以研究空间推理的重点就是研究定性空间推 理。 空间推理的研究起源于2 0 世纪7 0 年代初，最初是以量空间( 例如，仅 包括 _ ，0 ，4 - 1 的量空间，它代表实数线的两个半开区间及它们的分界点) 为研 究对象的，多维的并且不能通过单一的纯量充分表示的空间，只是近年来 才成为人工智能，更确切的说，成为知识表示中的一个重要研究领域l ，j 。由 于空间推理的研究对象的转变，极大地扩展了空间推理的应用领域，使空 间推理的理论和应用研究近年来有了长足的发展。 定性空间推理是空间推理的一个分支领域，是空间推理的重要组成部 燕山大学t 学硕士学位论文 分。定性空间推理主要是对几何形状或者运动性质进行定性推理睁9 1 ，是针 对空间关系的推理。空问关系( 包括拓扑关系、方向关系、度量关系1 是空间 查询与分析的基础。作为空间关系的重要组成部分，空间方向关系的表示 和分析不仅能够弥补现有地理信息系统数据库的空间特征存储、提取、查 询、更新等操作的不足，而且有利于加强现有地理信息系统对空间分析及 辅助决策的能力。因此，空间方向关系的描述与识别非常重要。目前，将 a l l e n 的时态逻辑与r a n d a l l 的空间逻辑结合起来，形成空间、时间、连续 运动的表达逻辑i l0 1 ，另外，从定性空间推理派生出来的空间规划理论，可 用于为一组几何对象寻找满足一组约束的分布设计，有关方法主要用于设 计自动化、定性建模等领域。在这一领域已取得了一些较实际的成果，如 约束满足问题c s p ( c o n s t r a i n ts a t i s f a c t i o np r o b l e m s ) 求解理论，而实际上很多 定性空间规划都是一个几何约束满足问题。定性空间推理从几何、使用和 功能三个方面研究空间知识的表示和处理，主要研究内容包括：视觉对象的 识别、认知图和路径规划、人类比喻的模拟和定性物理的可视化。近几年， 由于认识到空间知识本质上是定性的，定性空间推理研究已成为空间推理 研究的主流，发展出公理化、代数、几何约束满足、基于模型的推理及组 合表等方法。 c s p 是人工智能的一个研究领域，人工智能以及计算机科学中的许多 问题都看作是c s p 的特例【1 1 1 。c s p 可表示为三元组( v ，d ，r ) ：其中v 是问题 变量的集合，d 是v 中变量的域的集合，r 足v 中变量问的约束关系的集 合。求解约束满足问题是对v 中的每个变量赋予其对应域中的值，使得r 得以满足。诸如机器视觉( m a c h i n ev i s i o n ) t 1 2 l ，规划( s c h e d u l i n g ) 0 3 1 ，时态推 理( t e m p o r a lr e a s o n i n g ) o “j ，图论问题( g r a p hp r o b l e m ) ”】，平面设计( f l o o r p l a nd e s i g n ) 【1 6 】，电路设计( c i r c u i td e s i g n ) 1 ”1 等都可用c s p 加以解决。 一致性检验问题的形式框架就属于c s p 。在空间数据库中经常要识别 数据间隐含的矛盾信息，例如：假设a 、b 、c 是三个空间物体，若b 位于 a 的西方，c 位于b 的西方，但数据库显示c 在a 的东方，那么显然该信 息是不一致的。本文将这一定性空间推理问题用约束满足问题的方法表达， 试图用约束满足问题的求解方法来解决空间方向关系的推理，以寻求定性 2 第1 章绪论 空间推理的有效解决方法。空问方向关系推理是空间思维的高级阶段，是 g i s 的重要理论问题。空间方向关系推理是方向关系理论研究的重要组成部 分，它主要分为空间方向关系合成，空间方向关系一致性检验等方面。在 众多空间关系约束类别中都涉及到致性检验问题，例如，拓扑关系约束， 基于点和基于矩形的方向关系约束等，在很大程度上都需要实施一致性检 验。除了空间关系方面外，一致性检验还被应用到其他定性关系方面，例 如，维护空间数据库的完整性，优化空间查询请求等。n e b e l 和b u r c k e r t 在分析a l l e n 的1 3 种间隔关系与v a nb e e k 的点代数关系时就考虑了一致性 检验问题。 1 2 研究目的与意义 通过对空间推理研究工作进行总结和比较可以发现，空间推理是人工 智能以及地理信息系统、时空数据库等相关领域的热点研究方向。在基础 理论方面，对时间、空间信息表示和推理的理论研究工作比较充分，对方 向关系研究刚刚起步，在应用研究方面，空间推理中很多理论研究成果， 如一致性检验理论，已应用于g i s 、知识发现和机器人等领域。通过总结近 年来对空间推理中方向关系一致性问题的研究，我们认为其主要目的和意 义如下： ( 1 ) 空间方向关系理论完整性的需要空间方向关系推理是空间关系方 向理论不可或缺的重要组成部分。缺少了方向关系推理的空间关系理论， 就不能或不能很好的对空间信息进行分析、加工和优化。在g i s 的实际应 用中，人们不能满足只对空间信息进行存储和简单的位置描述，需要对已 有的地理信息进行分析和处理，空间方向推理研究可以很好的支持对未知 空间信息的推导和对已有信息正确性的检验，方便空间查询和剪枝。 ( 2 ) 空间查询的需要空间查询是g i s 中应用最多的功能之一。现在流 行的a r c i n f o 等g i s 软件，其查询功能基本是基于空问距离和拓扑关系， 基于空间方向关系的查询很少涉及。空问方向推理理论的研究正好填补了 这一空白，空间方向关系具有自反性和传递性，其具备空间推理的条件。 燕山大学工学硕上学位论文 空间方向推理理论的研究正好填补了这一空白，实现高效的空间推理算法 可以为预处理空间查询以及对需要搜索空问的提前剪枝提供了快捷可行的 方法。 ( 3 ) 时空结合的知识表示和推理时间和空间相结合的研究工作还存在 很多问题。为了构造适应性更强的时空结合理论，很可能需要摒弃原来针 对单纯时问和空间的建模方法，从根本上提出一套面向时空统一的新理论 现在的时空结合工作多数限于拓扑关系和时间区间关系的结合还需要进一 步深入研究多种空间和时间关系的结合，最终建立包括所有空间和时间关 系的统一模型。 ( 4 ) 时空本体的研究本体技术不仅有助于解决不同时空表示系统之间 的交互、集成、共享、重用等方面的问题，而且还是常识知识表示等研究的 重要工具。由于时空本体在生物信息化、g i s 、常识库建造以及语义w e b 等方面都有重要的应用，其研究已经引起了各个领域学者的广泛关注。未 来有关时空本体的研究将作为时空推理领域中的重要分支，成为研究的热 点。 ( 5 ) 时空推理研究与应用结合时空推理的应用领域已经由地理信息领 域向军事、交通、医疗、生物信息等领域扩展。近几年来，随着移动对象 数据库等一批已经( 或接近) 商业化的时空信息处理系统的出现，时空推理的 应用前景越来越明朗。将现有理论成果向应用领域推广以及基于时空推理 理论研究应用问题将是今后时空推理研究的重点之一。 ( 6 ) 新一代g i s 研制的需要新一代g i s 的一个显著特征是语音功能的 增加，即g i s 和用户可以进行语言的直接交流，这种语言交流的语法规则 就要依据空间概念的形式化描述【l 虮。而空问推理则是这种空间概念描述的 具体执行者，系统通过空间推理算法才可以得到人们所预期的正确结果。 一致性问题对人们日常生活来说是至关重要的。例如：人们布置家具， 规划建筑等，所以信息系统提供处理复杂的空间推理功能是非常必要的。 方向作为一个重要的空间关系，已经用在了很多领域，例如：空间数据库、 人工智能、人工推理等。于是关于方向关系的推理研究是十分重要的，对 其进行深入、系统地研究是具有深远意义的。 4 第1 章绪论 1 3 本课题在国内外的研究现状 空间推理是人工智能领域针对空间问题的研究方向，它研究空间信息 的表示和推理，广泛应用于地理信息系统、机器人导航等领域。空间推理 一般采用代数或逻辑方法描述拓扑、距离、方向等空间关系以及形状、尺 寸等空间特征，并研究复合推理、约束满足问题、一致性检验问题。空间 知识多数是粗粒度、主观的、不确定的，对空间问题进行定性分析往往比 定量度量更有效。 目前，对于空间方向关系许多世界著名大学教育机构都在进行空间推 理的研究，但关于空间方向关系的一些基本问题目前还没有一个为大家共 同接受的标准，致使其基本上还处于尝试和探索阶段。在国外，近年来成 立了许多专门从事空间推理方面研究的协会和联盟，如n c g i a ( n a t i o n a l c e n t e rf o rg e o g r a p h i ca n da n a l y s i s ) ，u s g s ( u s g e o l o g i c a ls u r v e y ) ，欧洲定 性空间推理网s p a c e n e t 以及匹兹堡大学的空间信息研究组和慕尼黑大学 空间推理研究组等等。国际知名期刊a r t i f i c i a li n t e l l i g e n c e 近年来发表了许 多篇空间推理方面的文章，而且呈逐年成长的趋势，这可以从近年来这本 期刊的总目录上看出来。在一些大学里，不仅有了越来越多的研究人员从 事与空间推理方面的研究工作，而且还在大学生和研究生中开设了空间推 理方面的课程。近年来空间推理方面的会议也是越来越多。以上种种迹象 表明，空间推理已经成为人工智能的一个走向成熟的领域。目前空间推理 被广泛应用于地理信息系统、机器人导航、高级视觉、自然语言理解、工 程设计和物理位置的常识性推理，并且正在向其他领域渗透。正是由于空 间推理有着广泛的应用前景，才激励着空间推理研究者不断的研究和探索。 在国内，则仅有少数专家对其进行理论研究，研究成果甚微。 方向关系的研究是空间推理研究的重要课题。近几年来人们主要从以 下几个方面来对方向关系进行研究：基于方向关系的查询、基于方向关系 的推理、方向关系模型。 针对方向关系模型的研究，人们先后提出各种模型包括方向角模型、 锥形方向模型，三角方向模型、二维区间方向模型、方向字符数组模型、 燕山大学t 学硕士学位论文 极小边界矩形模型m b r ( m i n i m u mb o u d i n gr e c t a n g l e ) 以及井字空间等。 n e o d o r i d s 利用m b r 建立了基于m b r 的主方向关系模型，给出了 一系列主方向关系的定义，并且利用r 树进行了m b r 的索引，加速了基 于m b r 主方向关系的查询速度。但该理论没有针对空间推理给出相应讨 论，致使其仍处于空间信息描述阶段。r k g o y a l l 2 0 1 提出的模型已证明是目 前较合理、较好的模型，本文就是把他的模型和极小边界矩形模型结合起 来进行研究的。 对于空间方向推理首先是a l l e n 提出了区间代数理论，给出了1 3 种区 间关系以及这1 3 种关系的基本运算法则，为时态关系推理提供了基础。 e g e n h o f e r t 2 l 】发展了a l l e n 理论，形成了矩形代数理论。利用矩形代数理论 可以将一维的时态时态关系推理算法扩展到为二维空间领域，但e g e n h o f e r 的矩形代数理论没有将方向关系推理整合到其理论中。l i g o z a t l 2 2 1 应用a l l e n 理论提出基于点物体的空间方向关系推理并给出了一致性检验算法，但他 在文献中讨论的物体类型仅限于点物体，在实际应用中很难满足复杂物体 的形状的要求。 目前关于方向关系合成的研究主要有最早由g o y a l 和e g e n h o f e r 所提出 合成理论，以及后来s p i r o s 和m a n o l i s 的理论【2 3 】。但是g o y a l 和e g e n h o f e r 的理论被s k i a d o p o u l o s 和k o u b a r a k i s 证明足不完善的1 2 “，而s k i a d o p o u l o s 和k o u b a r a k i s 的合成问题研究是基于方向关系谓词的不能直观的表示空间 区域之间的方向关系，所以需要使用一种新的方向关系模型既能用来表示 各个空间区域的方向关系又能使用该模型进行方向关系的各种推理的运 算。 对于空间拓扑关系推理中，当空间关系可以表达为一组j e p d 基本关系 时，可以应用约束满足技术加以解决，这一点与时态推理中的情况类似。 1 9 9 9 年，r e n z l 2 5 】证明了区域连接演算r c c 一8 ( r e g i o nc o n n e c t i o nc a l c u l u s ) 公式的可满足问题是n p 完全的。r e n z 采用与时态推理研究类似的方法对 r c c 8 的推理复杂性进行研究，得到了3 个最大易处理子集( h 8 ，c 8 ，q 8 ) 。 这一发现对解决处丁：“相变”区域的较难的r c c 8 空间拓扑约束问题有很 大帮助。但最近清华大学的李三江基于r c c 复合表的可扩展性1 2 6 j 理论，指 6 第1 章绪论 出r e n z 证明过程中使用的一个定理是错误的。因此，有关最大易处理子集 的结果需要重新证明| 2 7 3 3 。 与国外相比，国内对空间推理、空间关系的研究都要稍晚，还没有形 成整体力量。目前，国内许多科研单位和高等院校竞相开展空间推理、g i s 及空间数据挖掘的研究。其中，武汉大学李德仁院士在1 9 9 4 年就提出了从 g i s 数据库发现知识的建议。他们的研究集中在空间数据挖掘和知识发现的 理论、方法与应用，并得到了测绘遥感信息工程国家重点实验室基金项目( 项 目编号：w k l ( 9 7 ) 0 3 0 2 ) 和国家自然科学基金优秀国家重点实验室研究项目 ( 项目编号：4 0 0 2 3 0 0 4 ) 的资助，其研究水平居国内领先。廖士中等人提出了 定性空问推理的分层逼近方法，此外，中科院地理所资源与环境信息系统 国家重点实验室、中科院遥感所等单位的学者也开展了定性空间推理的研 究。但总的说来，定性空间推理、空间关系的研究还处于起步阶段。 1 4 本文的主要内容及组织结构 本文主要的研究内容是关于定性空间推理中的主方向关系网络的一致 性检验。简而言之，方向关系一致性就是给定一组方向关系约束集合，现 实地理环境中是否存在满足该约束集的场景。现有的检验方法大都基于 l i g o z a t 的路径一致性理论，本文创造性提出利用有向图的理论实施一致性 检验，简便实用。其基本思路是：把每一组方向关系转化为有向图，即节 点代表对象，有向边表示它们之间的方向关系。然后依据一定规则对整个 约束关系集的划分图进行合并、精炼，得到最终的空间图s g v 。通过检验 s g v 中足否存在环来检验其一致性，若有环存在则说明给定的方向关系集 足不一致的，最后给出了理论证明，同时运用实例证明了该方法的正确性。 本文的结构安排如下： 第l 章是绪论，介绍了本课题的研究背景及意义，讨论了什么是空间 方向关系以及什么是定性空间推理。重点介绍了空间中的方向关系的研究 与发展，最后给出了本文的研究内容及组织结构。 第2 章是定性空间推理与空间方向关系，介绍了定性空间推理的概念， 7 燕山大学t 学硕上学位论文 研究对象，说明了空间方向关系的分类原则，详细介绍了主流的方向关系 模型，最后给出了本文的关系模型。 第3 章是主方向关系网络一致性检验，本章深入研究了主方向关系以 及主方向关系网络的一致性，给出了关于一致性检验的几种数学实现方法。 第4 章是区域物体主方向关系的一致性检验，具体阐述了本文提出的 关于主方向关系一致性检验的新方法，即利用s g v 实施可视性检验，并给 出了实例用以说明该方法的实际运用。 第5 章是点物体主方向关系的一致性检验，讨论了二维欧几里德空间 点物体方向关系的一致性，通过分析x y 轴投影上的坐标图中是否存在环 的方式来检验方向关系约束集的一致性。该方法可在线性时间内完成，还 可扩展到区间，m b r 上。 第2 章定性空间推理与空间方向关系 第2 章定性空间推理与空间方向关系 定性空间推理q s r ( q u a l i t a t i v es p m i a lr e a s o n i n g ) 是空间推理和定性推 理的重要组成部分，当描述一个空问配置或对这样的配置进行推理的时候， 要获得精确、定量的数据通常是不可能的或不必要的。在这种情况下，可 能要用到关于空间配置的定性推理 3 4 】。定性空间推理主要是对几何形状或 者运动性质进行定性推理，是利用空间理论和人工智能技术对空间对象进 行建模、描述和表示，并据此对空间对象间的空间关系进行定性分析和处 理的过程。这使得它既与空间推理有联系，也与空间推理有区别；既有别 于空间推理，也有别于定性推理。 2 1 定性空间推理 首先简要介绍一下有关定性空间推理的概念，研究内容以及与定性推 理和空间推理的关系。 2 1 1 定性空间推理的概念 空间推理时，当描述一个空间配置或对这样的配置进行推理的时候， 要获得精确、定量的数据通常是不可能的或不必要的。在这种情况下，可 能要用到关于空间配景的定性推理1 3 5 】。 究竟什么是定性空间推理，学术界并没有一个严格完整的形式化的定 义，但根据现有资料及前人的总结可以理解为：定性空间推理主要是对几 何形状或者运动性质进行定性推理，是利用空间理论和人工智能技术对空 间对象进行建模、描述和表示，并据此对空间对象间的空间关系进行定性 分析和处理的过程。定性空间推理首先需要对空间几何体位置及运动方向 进行定性描述，进而对对几何形状及运动性质进行推理研究及预测分析， 并且做出逻辑解释。定性空间推理广泛存在于人们日常与物理世界的交互 9 燕山大学t 学硕士学位论文 中。大多数情况下人们对物理世界的判断多数基于抽象的定性描述，而不 是完整的定量描述。移动机器人定性导航中关于空间位置的表示和推理研 究属于这一研究领域，定性力学中对刚体的形状及其运动性质的研究也是 这方面的主要代表工作之一。 2 1 2 定性空间推理的研究内容 定性空间推理研究的关键问题有两个，一个是对空间实体及其相互位 置关系我们怎样去加以表示即定性空间表示；另一个是与第一个问题紧密 相关的，也就是在一定表示方法下的推理方法即定性空间推理【3 6 】。历史上 物理科学产生过很多空间表示方法，这些方法基本上都是建立在定量的基 础上，强调数值的精确性。这些方法并不适用丁二本文。除了定量的表示以 外，还可以从很多不同的方面去定性地表示一个空间，空间实体有很多不 同方面的特征这也造成空间表示的多样性。我们不仅要决定什么样的空间 实体是我们可以接受的，而且要决定用什么样的形式来表示空间实体间的 关系3 7 1 。 综合上面的分析，我们认为定性空间推理研究的足人类对几何空间中 空间对象及其定性关系认知常识的表示与处理过程。 2 1 3 空间推理中定性与定量的关系 定性表示是相对于定量表示而言的。一般地，定性表示仅表示独特的 和主要的特征，而定量表示以预定的单位表示所有的细节。人类对客观世 界的认识往往是从定性的认识上升到定量的认识。 空间知识的定性表示具有其特殊性和重要性。由于空间知识的信息量 大，给出仅是必需的表示是重要的。对空间系统中的某些环节，由于条件 的限制也只能得到它们的定性描述，在这种情形下通过定性推理也能得到 系统的某些性质和结论。这种定性方法不同于传统的定量方法，它们是两 种不同的方法体系，其主要区别为： ( 1 ) 物理量度量尺度不同这是两种方法体系的本质区别。在传统的定 量方法中，物理量的度量尺度是无限稠密和均匀的，物理量用精确的数值 0 第2 章定性空间推理与空间方向关系 表示。而在定性方法中，物理量的度量尺度是被界标点离散化的实空间， 不再具有无限稠密、均匀和精确的性质。 ( 2 ) 物理模型不同传统定量方法中使用的是定量物理模型，物理量之 间的关系用代数方程、微分方程等精确描述，系统的因果关系必须在模型 外由人来给出。而定性方法中使用的是定性物理模型，物理量之间的关系 用定性约束、定性进程等描述，系统的因果关系体现在模型之中。 ( 3 ) 仿真过程和仿真结果不同在传统的定量方法中，仿真的过程就是 求解代数方程或者微分方程的过程，仿真的结果是精确的物理量数值。而 在定性方法中，仿真是通过局部传播实现的，仿真的结果是系统的行为描 述，能完成系统的行为预测与行为解释。 ( 4 ) 推理能力不同在传统的定量方法中，物理量及物理量之间的关系 都是精确描述的，模型本身不具备推理能力，物理量之间的因果关系淹没 在精确的数值之中，系统的行为分析和因果解释必须由人来完成。而在定 性方法中，物理量之间的因果关系直接反映在系统的结构描述中，通过局 部传播就能实现系统的行为预测和行为解释。 2 1 4 定性空间推理与空间推理、定性推理之间的区别与联系 定性空间推理是对空间对象问的空间关系进行定性分析和处理的过 程，这使得它既与空间推理有联系，也与定性推理有联系；既有别于空间 推理，也有别于定性推理。 空间推理与定性空间推理的联系是：随着人们对空间信息认识的深入， 认识到空间对象本质上是定性的1 3 引，从而使定性空间推理逐步成为空间推 理的主流。空间推理与定性空间推理的区别是：定性空间推理不仅研究空 间对象问关系的定性分析和处理，还研究空间对象及空间关系的定性表示， 所涉及的空间关系包括空间拓扑关系、方位方向关系、距离关系以及空间 对象形状等。在空间对象认知上，定性空间推理不局限于空间推理的本体 论。既有从本体论角度研究的，如r c c 理论【3 9 4 2 1 ，也有从点集拓扑学角度 进行研究的，如n 一交集模型1 4 5 1 。 定性推理q r ( q u a l i t a t i v er e a s o n i n g ) 源于对物理现象的研究，早期的工 燕山大学t 学硕上学位论文 作针对特定的问题，比如针对动力学问题、流体力学问题和热流问题等。 定性推理是对物理系统行为、特征的描述、预测、诊断和解释，它涉及具 体系统的领域知识。由此，定性空间推理与定性推理的区别在于 4 6 l ：定性 空间推理是关于人类对空间认知常识的表示与处理过程，它与论域空间有 关而与具体的领域( 实际物理系统) 无关，它针对的是常识知识而非专家知 识，定性空间推理系统不是专家系统。定性空间推理与定性推理的联系是： 定性空间推理也需要将论域中的连续对象进行定性的量化，定性推理中将 论域量化为离散符号集合的方法在定性空间推理中具有指导意义。 2 2 空间方向关系 方向关系描述了空间对象在空间中的某种排序，如前后、东西等等， 是空间关系的重要组成部分，是一类重要的二元空间关系，它和拓扑关系、 几何关系一起构成了基本的空间关系，在空间目标智能查询、模式识别、 地理信息可视化等领域有着广泛的应用。 2 2 1 空间方向关系的表示 过去，人们习惯于用定量的方法来研究方向关系的定性表示与推理。 传统的g i s 使用完全定量的方法表示和推导空间信息，定量表示为科学计 算提供了依据，然而定量方法需要空间对象几何信息的完全描述，不能处 理不完全、不精确的定性空间信息【4 ”。不精确的几何信息、有限的计算精 度以及误差的积累都会给定量方法带来严重影响。对于方向关系来说，人 们有关方向的概念不仅依赖于空间对象的绝对位置，而且依赖于空间对象 的相对大小和形状，以及其它对象的位置、参照系等，即方向的概念是与 环境有关的。如果使用定量方法，势必要将所有的方向信息简化到一个绝 对度量尺度来避开环境的影响。由于空间问题固有的复杂性和不确定性， 并且在大比例尺地理空间，人们经常遇到不完全、不精确的空间信息，因 而普遍使用定性描述理解、分析和对空间对象环境下结论。例如在报刊文 章的旅程路线描述、突发事件报道中经常使用地理空间的定性描述等等， 1 2 第2 章定性空间推理与空间方向关系 都不需要给出对象的精确坐标位置。当所得的信息为定性信息，缺少更为 精确的地理信息的情况下，定性推理成为推导隐含信息和未知信息的唯一 可行方法。定性推理可以处理非精确数据，虽然可能只提供近似的、粗略 的解，丢失了一些精度，但简化了推理过程，足以解决特定的地理问题。 目前，g i s 中空间关系的表示大多是定性的，而且自然语言描述中往往采用 定性的方法。因此，本文讨论的，都足方向关系的定性表示。 2 2 2 空间方向参考框架 方向是人们日常生活中常用的定性词汇。试看下面的例子： 例一：辽宁、吉林、黑龙江在中国的东北，海南岛在中国南方。 例二：黄河以北，长江以南。 例三：在我左前方，一层楼的房子就是计算机学院。 这些都是定性方向描述的例子，从这几个例子中我t f j 戋n 道： ( 1 ) 方向是相对的要描述一个方向需要两个对象，一个足参考对象， 另一个是目标对象，方向是目标对象相对于参考对象的方向。 ( 2 ) 参考对象具有多样性参考对象可以是区域、线或点，前面的例一、 二、三中分别以区域、线、点作为参考对象。 ( 3 ) 参考对象与目标对象的关系存在多样性如在上面的例子中，例一 中目标对象包含在参考对象中( 拓扑关系为i n ) ，例二中目标对象与参考对象 相接触( 拓扑关系为t o u c t l ) ，例三中的目标对象与参考对象相分离( 拓扑关系 为d i s j o i n t ) 。 ( 4 ) 方向的划分不同例二中仅使用北与南两个方向，例一、三中则使 用两个以上的方向。 除上述四个方面的因素外，人类对同一方向的认知也存在差异。图2 - 1 描述的“北”( 肋的概念表明了这种差异。 图2 - 1 对“北”( v ) 的不同认知 f i g u r e2 - 1t h ed i f f e r e n tc o g n i t i o n sf o rn o r t h ( ) 1 3 燕山大学丁= 学硕士学位论文 从上述例子可知，确定方向和方向关系的基础足参考框架，空间方向 的参考框架是由于不同目的、用途和观点对空间进行的剖分，如果参考框 架改变了，空间方向一般也会改变。r e t z - s c h m i d t l 4 8 1 将参考框架( 也称为方 向参考系统) 分为3 类，如图2 - 2 所示。 ( 1 ) 内部参考框架( i n t r i n s i cr e f e r e n c ef r a m e ) 该框架是指一个对象在自 身内部建立的方向参照系，多用前、后、左、右等词语描述，如图2 2 ( a ) 所示。例如，一栋居民住宅，正门入口为前，阳台为后，卧室居左，其他 房间、物品的空间方向可以此确定。 ( 2 ) 直接参考框架( d e i c t i cr e f e r e n c ef r a m e ) 该框架基于观察者的观点 建立，一个观察者以自己的前、后、左、右等对空问进行划分，建立空间 方向的参照系，如图2 - 2 ( b ) 所示。 ( 3 ) 外部参考框架( e x t r i n s i cr e f e r e n c ef r a m e ) 地球表面上的外部参考 框架可通过选择不同的北方向( 磁北、直北、坐标北等) 来建立，如图2 - 2 ( c ) 所示。相应的外部参考框架也有所区别。 ( a ) 内部参考框架 ( a ) i n t r i n s i cr e f e r e n c e f r a m e 左，两 前- i t ,北 右东西 后，南 ( b ) 直接参考框架 d e i c t i cr e f e r e n c e f r a m e 图2 - 2 空间参考框架 东 南 ( c ) 外部参考框架 ( c ) e x t r i n s i cr e f e r e n c e f r a m e f i g u r e2 2t h es p a t i a lr e f e r e n c ef r a m e 内部参考框架用于小尺度( s m a l l s c a l e ) 的地理空间，直接参考框架用于 人们的日常方向判断描述。在g i s 中，地理空间目标的空间方向参考框架 足典型的外部参考框架，而且，g i s 中所指的地理空间是大尺度( l a r g e s c a l e ) 的，而不是小尺度的。本文研究的空间方向借助于平面上的大尺度地理空 间的外部参考框架。 1 4 第2 章定性空间推理与空间方向关系 2 3 方向关系模型 方向关系模型的表示能力在研究地理信息系统里面是至关重要的，在 将来，地理信息系统将会提供多种用户界面应用模型，提供语音查询等多 种功能。例如用户可以使用自然语言询问“查找中国长江以北的所有的河 流”，地理信息系统将会具有这个功能提供查询结果。这种空间推理任务对 人类的智能来说是非常容易的，但是为了通过计算机的帮助来完成这些任 务，则需要正式的方向关系模型。 2 3 1定量的方向模型 在地里应用中目标点的方向主要使用的是相对于一个参考点的方位角 来定义的。方位角是一个通过参考点的子午线以及通过参考点到目标点的 连线( 测量线) 之间的角度，见图2 3 ，子午线上所有的点相对于参考点来说 在正北方向，也就是角度为0 0 。 图2 - 3 方位角定义 f i g u r e2 - 3t h ed e f i n i t i o no f a z i m u t ha n g l e 对所有的其他的点方位角是由顺时针方向从子午线的北方滑到测量线 的角度，角度值为【0 ，3 6 0 ) ，可用公式( 2 1 ) 来计算。 ，、 口：t a n 4 立玉1 ( 2 - 1 ) l 一n 对于那些大于3 6 0 0 的角则循环映射到这个区间，例如3 6 0 0 映射为o o ， 4 5 0 0 映射为9 0 0 。 两个点之间的定量的方向关系使用方位角的角度来测量，它们的值可 燕山大学t 学硕士学位沦文 以近似的用在某些领域中。例如点b 相对于点a 的方位角可能为4 3 0 3 4 ， 可以应用在例如陆地测量或者足机器设计等领域。然而空问数据库中的查 询语言使用的是定性的方向而不是定量的方向，因此本文重点介绍的足定 性的方向关系。 2 3 2 定性的方向模型 定性的方向关系相对于定量的方向关系来说足对方向关系的一种更为 粗糙的近似，并且使用更少的符号集来记录方向关系的信息。例如区间 o o ，3 6 0 0 ) 会被划分为四个或者是八个方向区域，每一个区间表示一种方向关 系。四个区域的系统使用首要的方向东、南、西、北，八个区域的系统使 用首要的方向东北、北、西北、西、西南、南、东南、东。人们经常使用 的定性的空间推理而不是定量的空间推理主要是因为定性的方向关系足够 人们用来交流信息，而定量的信息例如t a n 。在人们的头脑里不能很快的得 到结果，且不容易理解。在人们使用g i s 的时候很少会使用象“查找与北 京方位角为4 3 0 3 4 的所有的湖泊”这样的查询，而是经常使用类似象“查 找所有位于北京西北方向的湖泊”这样的查询。 主方向关系的研究使用的是外部参考框架，下面就方向