（计算机应用技术专业论文）方位关系层次表示与推理.pdf

中文摘要 摘要 r s 与g p s 为空间信息的采集提供了技术支持，g i s 从定量的角度建立了空 间信息处理与应用的理论和技术体系。但是，空间信息是复杂的，从量上来看是 海量级的；从种类上看不仅包含数值型、字符型，还包括图形、图象等多种类型； 并且空间信息间的相互联系是固有的。因此，对空间信息仅进行定量的研究是不 够的，还必须从定性方面进行研究。 结合定性推理、空间推理与人工智能产生的定性空间推理，已成为人工智能 的一个研究热点。不同于定性推理研究物理系统的结构、行为、功能及其相互联 系，定性空间推理分析和处理的是人们对几何空间常识知识的认知；不同于空间 推理研究空间对象的建模、描述、表示及其关系的分析和处理，定性空间推理面 对的是空间对象的定性特征和定性关系。 本文研究的空间对象是二维空间的点、线、面，研究内容是空间对象问的方 位关系的表示与推理，推理方法为层次推理。在对方位关系表示与推理进行深入 分析的基础上，本文进行了以下几方面的创新性研究： ( 1 ) 方位关系的表示 简要介绍了定性空间推理的相关理论和方位关系的相关概念，以及三种常用的 方位表示模型( 锥形模型，字符串模型，投影模型) 。其中着重对投影模型做了 详细的研究，针对d 1 4 的不足进行了扩展，提出了一种新的方位关系g d 8 。 ( 2 ) 层次空间推理 介绍了层次和层次空间推理的相关理论，深入研究了层次空间推理在识路中的 应用。文章对已有的基于层次的识路算法( h w a 算法) 做了深入研究，发现其不 足，并提出了改进算法h w a 算法。 ( 3 ) 方位关系的层次表示与推理 通过分析方位关系层次推理已有的研究成果，文章提出了基于区域覆盖的层次 结构，给出了区域间方位关系推理的算法。 方位关系具有形状相关性，用不同的形状来近似空间对象会影响推理结果。将 空间对象分别抽象为点，矩形，凸多边形和凹多边形，研究了空间对象间基于层 次的方位关系的表示与推理。文章给出了算法，并举例验证。 关键词：空间推理，方向关系，层次空间推理 英文摘要 a b s t r a c t r sa n dg p s p r o v i d et e c h n i c a ls u p p o r tf o rc o l l e c t i o no f s p a t i a li n f o r m a t i o n ，a n d g i sc r e a t e st h et h e o r e t i c a la n dt e c h n i c a la r c h i t e c t u r eo f s p a t i a li n f o r m a t i o np r o c e s s i n g a n d a p p l i c a t i o nf r o mt h ea s p e c to f q u a n t i t y h o w e v e r , s p a t i a li n f o r m a t i o ni sc o m p l e x c o n s i d e r i n gq u a n t i t y ，s p a t i a li n f o r m a t i o ni sm a s s t h ek i n d so f s p a t i a li n f o r m a t i o nn o t o n l yh a v en u m e r i c a lt y p e ，c h a r a c t e rt y p e ，b u ta l s oh a v ef i g u r et y p ea n di m a g et y p e t h e c o r r e l a t i o nb e t w e e ns p a t i a li n f o r m a t i o ni si n h e r e n t s o ，q u a n t i t a t i v er e s e a r c ho fs p a t i a l i n f o r m a t i o ni sn o te n o u g h , a n dq u a l i t a t i v er e s e a r c hi sn e c e s s a r y q u a l i t a t i v es p a t i a lr e a s o n i n gt h a ti sg e n e r a t e db yc o m b i n i n gq u a l i t a t i v e r e a s o n i n g ， s p a t i a lr e a s o n i n ga n da r t i f i c i a li n t e l l i g e n c e ( a i ) h a sb e e nah o t s p o ti nt h er e s e a r c ho f a i d i f f e r e n tf r o mt h er e s e a r c h e so fs t r u e t t t r e ，a c t i o n , f u n c t i o na n dt h e i ri n t e r c o n n e c t i o n so f p h y s i c a ls y s t e mi nq u a l i t a t i v ep h y s i c s ，q u a l i t a t i v es p a t i a lr e a s o n i n ga n a l y z e sa n d p r o c e s s e st h eh u m a nc o g n i t i o no fg e o m e t r i cs p a t i a lc o m n l o nk n o w l e d g e d i f f e r e n tf r o m t h er e s e a r c h e so fm o d e l i n g ，d e s c r i p t i o n s ，r e p r e s e n t a t i o n s ，r e l a t i o n s a n a l y s i sa n d p r o c e s s i n go fs p a t i a lo b j e c t si ns p a t i a lr e a s o n i n gr e s e a r c h i n g ，q u a l i t a t i v es p a t i a l r e a s o n i n gf a c e st ot h eq u a l i t a t i v ec h a r a c t e r sa n dq u a l i t a t i v er e l a t i o n so fs p a t i a lo b j e c t s s p a t i a lo b j e c t sr e s e a r c h e di nt h i sp a p e ra r ep o i n t s ，l i n e sa n da r e a si n2 - d i m e n s i o n a l s p a c e ，a n dc o n t e n t sa r ed i r e c t i o nr e l a t i o n sr e p r e s e n t a t i o na n dr e a s o n i n gb e t w e e ns p a t i a l o b j e c t s a n dt h er e a s o n i n gr e s e a r c h e sh i e r a r c h i c a ls t r u c t u r er e a s o n i n g b a s e do nt h e p r o f o u n da n a l y s i sf o rr e p r e s e n t a t i o na n dr e a s o n i n go fd i r e c t i o nr e l a t i o n s ，t h i sp a p e r p r o c e e d s 埘t l ls o m e 丽西n a l i t yi n n o v a t i o nr e s e a r c h e sa sf o l l o w s ： ( 1 ) r e p r e s e n t a t i o no fs p a t i a ld i r e c t i o nr e l a t i o n s t h et h e o r i e sa b o u tq u a l i t a t i v e s p a t i a lr e a s o n i n ga n dd i r e c t i o nr e l a t i o n s f i l e i n t r o d u c e d t h ep a p e rr e s e a r c h e st h eb a s i cr e p r e s e n t a t i o nm o d e l so fd i r e c t i o nr e l a t i o n s ( c o n em o d e l ，2 d s t r i n gm o d e l ，p r o j e c t i o n - b a s e dm o d e l ) b ya n a l y z i n gt h e p r o j e c t i o n - b a s e dm o d e ld 1 4 , an e wd i r e c t i o ni sp u tf o r w a r dn a m e dg d s d 1 4a n dg d 8 c a nb ec o n s i d e r e da st w ol e v e l so fd i r e c t i o nr e p r e s e n t a t i o n t h er e l a t i o ni nd 1 4i sm o r e p r e c i s et h a nt h a ti ng d s ，b u tg d s g a l lr e p r e s e n td i r e c t i o nr e l a t i o n sw h i c hd 1 4c o u l d n t ( 2 ) h i e r a r c h i c a ls p a t i a lr e a s o n i n g t h et h e o r i e sa b o u th i e r a r c h ya n dh i e r a r c h i c a ls p a t i a lr e a s o n i n ga r ei n t r o d u c e d t h e p a p e rr e s e a r c h e sw a y f m d i n gb a s e do nh i e r a r c h i c a ls p a t i a lr e a s o n i n gp a r t i c u l a r l y t h e a l g o r i t h mh w a h a ss o m ed i s a d v a n t a g e s t h ep a p e ri m p r o v e sh w aa n dp r o p o s e s i l l 重庆大学硕士学位论文 a l g o r i t h mh w a 3 ) h i e r a r c h i c a lr e a s o n i n ga b o u td i r e c t i o nr e l a t i o n s a1 l i e 黼l l i c a l r r u c r l r eb a s e do no v e r l a yo fa r e ai sp r o p o s e d a n dp r c ma n a l g o r i t h mf o ri n f e r e n c ed i r e c t i o nr e l a t i o n sb e t w e e nr e g i o n si nh i e r a r c h y d i r e c t i o nt e l a t i o ni ss h a p e - s e m i t i v e ，w h i c hm e a n sd i r e c t i o nr e l a t i o ni sr e l a t e dw i t h t h es h a p eo fs p a t i a lo b j e c t s w em a yo b t a i nd i f f e r e n td i r e c t i o nr e l a t i o ni fw ea b s t r a c t s p a t i a lo b j e c t sw i t hd i f f e r e n ts h a p e s w eu s ep o i n t , m i n i m u mb o u n d a r yr e c t a n g l e ， c o n v e xp o l y g o na n da r b i t r a r y - s h a p e dp o l y g o nf o ra p p r o x i m a t i o n t h ep a p e rp r o p o s e s a l g o r i t h m sf o rh i e r a r c l l i c a ld i r e c t i o nr e 髂o n i n g a c c o r d i n gw i t ht h ea l g o r i t h mw ec a n i n f e rt h er e l a t i o n sb e l 3 a r e e ns p a t i a lo b j e c t su s i n gt h er e l a t i o n so f t h e i ra n c e s t o rr e g i o n s k e y w o r d s ：s p a t i a lr e a s o n i n g ，d i r e c t i o nr e l a t i o n s , h i e r a r c h i c a ls p a t i a lr e a s o n i n g i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庞太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：谴熬签字日期：1 。o6 年2 月占日 学位论文版权使用授权书 本学位论文作者完全了解重压态堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重麽太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 、) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名： 熏燕、 签字日期： 五66 年i 胡6 日 导师签名：研f 签字日期：勿肋年f 月 1 绪论 l 绪论 1 1 课题来源及研究的目的和意义 进入2 1 世纪以来，地理信息系统g i s 已成为信息时代的重要组成部分之一， 并为其他信息技术提供空间信息处理和分析功能，深化信息技术的应用，同时， g i s 也成为数字城市的重要支撑技术。g i s 为人类由客观世界到信息世界的认识、 抽象过程以及由信息世界返回客观世界的利用改造过程的发展和转化，创造了空 前良好的条件和环境。 空间查询与分析是g i s 的核心，是g i s 最重要和最具有魅力的功能，也是 g i s 有别于其它信息系统的本质特征。但是，目前g i s 中空间分析功能的发展显 得比较落后，因此研究空间分析的理论成为研究的重点和热点。空间分析建立在 空间目标位置和属性表达以及目标间复杂空间关系表达的基础上，若要提高空间 分析能力，必须解决空间关系描述与表达。因此，研究空间关系成为促进g i s 更 大发展的迫切要求，对推动g i s 的发展有着重要的意义。 空间推理是利用空间理论和人工智能技术对空间对象进行建模、描述和表示， 并据此对空间对象间的空间关系( 方向关系、拓扑关系、度量关系) 进行定性或 定量分析和处理的过型”。近年来，空间推理的理论发展非常迅速，国内外的各种 研究团体、科研单位都对它引起了高度的重视。随着研究的深入，人们逐渐认识 到，空间推理本质上是定性的。 定性推理是通过对( 物理) 系统的结构、行为、功能以及它们之间的关系和 因果性进行研究，以探索人类常识( 定性) 推理机制为目的，从而有效地完成各 项求解任务的一种跨领域的推理方法体系。由于空间知识和空问推理本质上是定 性的，因而定性空间推理作为表示和处理空间知识的一种有效方法，它的研究不 仅具有重要的理论意义，同时也具有广泛的应用前景，近几年受到普遍的重视， 定性空间推理的研究逐渐成为空间推理研究的主流。同时，定性空间推理的研究 领域也从人工智能拓展到更宽广的领域，地理信息系统成为定性空间推理最成熟 也最广泛的应用领域，定性空间推理的发展也促进了g i s 的发展。定性空间推理 的研究方法主要应用在空间关系的描述和分析上，因此，研究、分析、探讨空间 关系和定性空间推理，以及它们的结合有着重要的学术和应用意义。 近几年来，人们又提出了基于层次的空间推理，而且目前已有了一些研究成果。 人类对客观世界的认知过程总是由粗到细、由简到繁、由表及里的，这一认知规 律的抽象化描述即是层次性。将知识表示分为不同的层次并在各层次上进行推理 是与人类认知相吻合的。层次性这一认知规律对于认识空间对象问的方位关系， 重庆大学硕士学位论文 我们认为也楚邋用髓。空间的层次表承有很强的心理学渤机 2 j ，并且在很多领域包 括数据结构【3 1 1 4 ) 和导航i s 等方面有许多计算上的优势。 本论文的瞬的就是通过研究分析g i s 中的部分核心问题一空间方位关系， 探讨空闻推理中秀饪关系的屡次表零与推理，这也是方像荚系表示与推理熬一个 重要方瑟。 1 2 国内外研究现状 空间推理的研究工作始予2 0 世鳃7 0 年代初。2 0 世纪8 0 年代，由予计算机图形 学、计算极褫觉、图像处瑾、税器入学、计算复杂毽、黛阂数蕹痒、蠡然谗言处 理耱专家系统簿鬏壤郝震要磺究空翅疑识瓣表示纛勉联，因孬形成了空闽攘瑗这 一新的专门的研究颁域嘲。 空间推理的研究最初是以瑟空阀为研究对象h j ，多维的并且不能通过单一的纯 量充分表示的掇阀，在近年成为了知识表示中的一个黧鼹研究领域 7 1 。随着研究的 深入，近几年人们逐渐认识到，空间推理本质上是定悛的嘲。由于空间推理的研究 对象懿转交，羧大趣扩震了室怒黎壤麓应蔫镶装，德象黧攘瑾豹理论纛瘦麓疆究 运年来畜了妖怒戆遴震。当嚣空闽攘理主要骞激下建令魄较热豹研究方彝： 空间推理岛地理信息系统 时空推理 定性交阉攘耀 近尼年，由予认谖到空闻翔识本质上是定性的1 9 i o l ，爱性空闼雄瑾研究成为空 阉摊毽磅究瓣藏流。有关定佳空弼猴理的研究工铮始予年筏末驻磷。1 9 7 7 年， d e k l e e r 在n e w r o n 系统中研究了滑率运动轨道的定性袭示和推理方法。问年， k m p c r s 在博士论文“大规模空间知识的表示”中提出了机器入导航的t 吼m 模溅，将 空间知识组织成感知运动、过程、拓扑和度量四十层次。1 9 7 8 年h a y e s 采用公理化 瓣方法表示雾嚣熬澎姨。1 9 8 0 9 ，f o r b u s 在f r o b 系绫审，挺壅了度蠢霆式( m e t r i c d i a g r a m ) 窃绣掰攘逑1 8 龆v o c a b l l l a r y ) 戆壤念。莠在汉嚣豹童痒孛鞠确摇塞m d p v 模型是空闯撩璞的慕本框架。1 9 8 3 零，a l i e n 给出了瑟予聪闯的时态逻辑及潦予约 束传播的推理算法。8 0 年代后期，f o r b u s ，f a h i n g 和n i e l s e n 开展了定性运动学和定 性空阉推理的研究正作，从此定性缀间推理作为一个独藏豹研究领域日益援到人 们的重视。1 9 9 2 零，f r e k s a 搓出了橇念帮域熬概念，捂滋了定性空闻攘理研究酶重 要往。1 9 9 4 年, h e m a n d e z , 鎏结了定毪黧翅攘毽豹孚麓童傣噬。逅莛年来，a a a i 、i j c a l 和c o s i t 等会议上，定性空间推理研究工作都受到了熬税，u c a i 9 3 、i j c a l 9 7 、 和u c a i 9 7 会议t 逐专门举办了有关定性空间推理的研讨班。2 0 0 0 年6 月在美国得 克萨斯州召开的a a a i - 2 0 0 0 ( 1 4 t he n r o p e a nc o n f e r e n c eo na r t i l f i c a li n t e l l i g e n c e ) 等人 2 1 绪论 工智能学术会议都是以空间推理为主题。许多大学和研究机构纷纷在互联网上建 立自己的空间推理网站，研究人员可以十分方便地查阅资料和进行交流。在国外， 近年来成立了许多专门从事空间推理方面研究的协会和联盟，如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 以及匹兹堡大学的空间信息课题组和慕尼黑大学空间推理课题 组等等。 现在，定性空间推理的研究涉及空问知识的拓扑、距离、朝向、形状、路径、 时间、运动、语言学、认知科学、空间描述的可视化等方面，对空间知识与时间、 因果性和动力学的集成也予以了足够的重视，探索出了公理化、代数、几何约束 满足、基于模型的推理等基本方法。并在导航、地理信息系统，工程设计、定性 物理、空间数据库和图形图象等领域进行了应用研究1 9 1 0 1 。目前定性空间推理研究 的方位关系主要包括方位关系，拓扑关系和度量关系。 定性方向指将空间方向定性量化后形成的若干主方向，空间方位关系指用主 方向来表示空间对象间的方位关系。例如，东、南、西、北是一组主方向，利用 它可以表示空间对象间的方位关系。方位关系是相对的，并且需要一定的参考系。 r e t z - s c h m i d t 1 1 1 给出的方向关系参考框架一直沿用至今。r e t z - s c h m i d t 将参考框架 分为内部参考框架、直接参考框架和外部参考框架3 类。对于方位关系表示与推理， 探索出了许多表示模型。锥形模型( c o n em o d e l ) 由h a a r ( 1 9 7 6 年) 提出，以参考 对象的质心为参考点，用两条相互垂直的直线将平面划分为4 个无界的锥形区域， 并为每一个区域指定一个主方向( 如，东、南、西、北) ，目标对象所落在区域 的主方向即是目标对象相对于参考对象的方位。2 d 字符模型( 2 d - s t r i n g m o d e l ) 最早由c h a n gs k 【1 2 1 等提出，它用固定大小的网格将整个区域覆盖，并记录每个网 格中的目标标识符，然后根据网格的相对位置将标识符排成两个序列( 如，x 方 向序列和y 方向序列) 。通过序列可以获得对象间的方位关系。基于最小边界矩 形的投影模型相关的研究成果有：p a p a d i a s 1 3 1 等提出的9 方位模型和1 6 9 方位模型 ( 即d 9 和d 1 6 9 ) 。d r m ( d i r e c t i o n r e l a t i o n m a t r i x ) 模型由o o y a l r k 【1 4 j 于2 0 0 0 年 提出，它以投影模型为基础，通过计算目标对象落入各个区域的面积与目标对象 的面积之比来判定目标对象与参考对象间的方位关系。曹菡等对d r m 模型进行了 扩展研究，提出了空间方位关系描述的分层多级处理方法，建立了以点、线、面 为参考对象的方位关系描述的3 层模式结构。除前述4 种方位关系表示方法以外， 还有一些其它的方法。如，四半无限区域( f s i a ，f o u rs e m i - i n f i n i t ea r e a ) 模型， 方位v o r o n o i 图模型等。 另一方面，也提出了一系列方位关系推理方法。例如组合表推理，逻辑演算， 分层逼近法和公理化等。虽然关于定性空间推理的研究已有十几年，获得了一些 重庆大学硕士学位论文 推理方法，但是基于组合表的推理仍是定性空间推理最常用的推理方法 1 5 , 1 6 , 1 7 , 1 8 , 1 9 , 2 0 , 2 1 盈】。通过逻辑演算来进行推理是定性空间推理的另一种方法。r a n d e l t c u ia n dc o h n l 2 a 通过空间谓词c ( x ，y ) 定义空间逻辑系统，将空间对象间的拓扑关系 表示为谓词公式，利用一阶谓词逻辑建立了一阶逻辑范畴下空间拓扑关系推理技 术。石纯一，廖士中阱】等将定性空间推理问题划分为易处理类与非易处理类，给 出了易处理类的分层逼近推理方法。1 9 9 0 年，e d a v i s 针对一个简单的例子，首 先确定了角度、坐标系、形状和拓扑基本元素，然后建立了有关的几何公理和物 体物理形态公理。公理和场景都以谓词逻辑的形式描述。1 9 9 5 年n a s h e r 和l v i e u l 2 5 】利用部分学和拓扑学的概念，建立了一个具有完整语义描述的空间推理公 理系统。 近年来，人们又提出了方位关系的层次推理，目前已有一些研究成果。 c l e m e n t i n ie 在研究空间方位关系层次表示时，给出了方位带模型1 2 6 1 。但是这样的 层次划分存在的问题是层次中的方位关系不互斥。d p a p a d i 罄1 2 7 】对方位关系的层次 推理也作了深入研究，他将空间对象抽象为点，研究了方位关系的层次推理。但 总的说来，目前关于方位关系层次表示与推理还不成熟，不完善，没有形成统一 的规则和方法。 本文针对方位关系的层次推理提出了另一类层次划分：基于区域覆盖的层次 结构，并将空间对象抽象为不同的几何形状。 1 3 研究内容 本文通过研究目前层次推理的不足，提出了基于区域覆盖的层次结构，并从 点对象，矩形对象，凸多边形和凹多边形四个方面出发，研究了空间对象方位关 系的层次表示和推理。研究的内容主要包括以下几部分： 方位关系表示的研究 层次空间推理的研究 方位关系层次推理的研究 其中，方位关系表示和层次空间推理的研究是文章的理论基础，方位关系层 次推理的研究是论文的重点。 基于研究的目的和内容，本论文结构如下： 第一章：绪论。介绍本论文的研究背景和意义，以及国内外研究现状，确定 论文的研究范围和内容。 第二章：空间推理和定性空间推理。首先简要介绍空间推理，定性推理和定 性空间推理相关理论，然后着重介绍方位关系。为了论文的研究需要，提出了新 的方位关系表示方法。 4 1 绪论 第三章：层次空间推理。简要介绍层次空间推理的相关理论以及层次空间推 理在识路中的应用。通过分析已有的基于层次的识路算法的不足，提出了改进算 法。 第四章：方位关系的层次表示与推理。这一章是文章的重点。文章提出了基 于区域覆盖的层次结构，把空间对象分别抽象为点，矩形，凸多边形和凹多边形。 这种抽象也形成了一种粒度层次。这种粒度相当于地图中的比例尺，在较小的比 例尺下，空间对象可以看作是“点”，而在较大的比例尺下，对象可以抽象为“面”。 本章的主要内容如下： 基于区域覆盖的层次结构 点对象间方位关系的层次表示与推理 矩形对象间方位关系的层次表示与推理 凸多边形对象间方位关系的层次表示与推理 凹多边形对象间方位关系的层次表示与推理 第五章：原型系统的设计。在理论研究的基础上，通过仿真实验，验证了本 文所提出的推理方法。 第六章：总结与展望。对本论文所做研究进行总结，确定下一步研究的方向和 工作。 2 空间推理与定性空间推理 2 空间推理与定性空间推理 空间推理的研究工作始于2 0 世纪7 0 年代初。2 0 世纪8 0 年代，由于计算机图 形学、计算机视觉、图像处理、机器人学、计算复杂性、空问数据库、自然语言 处理和专家系统等领域都需要研究空间知识的表示和处理，形成了定性空间推理 这一新的专门的研究领域”o l 。 2 1 空间推理 2 1 1 空间对象与空间关系 空间表示与推理总是针对特定几何空间中的空间对象与对象间关系进行的。 本节，给出空间对象以及空间关系的概念。 空间对象 空间对象是客观存在的地理实体在人类认识世界中的反映，它是人们对客观 世界的认识与抽象。基于不同的认识方法，可以得到空间对象的不同认识。当我 们以地理实体的类别来划分空间对象时，可以得到诸如道路、河流、山脉等空间 对象。如果我们以地理实体的形状来划分空间对象，可以得到点、线、区域、体 等类别的空间对象。 当我们将点作为最基本的空间元素时，点被作为一种空间对象，其它空间对 象则是通过点来描述的。这是点集拓扑学的观点。点被作为空间构成的基元，它 没有大小，仅代表空间位置或位于某一空问位置的地理要素( 实体) 。由此，可以得 到在r 2 空间中空间对象的认知： 定义2 1 ：点是没有空间尺度的表示空间位置或该位置地理要素的空间对象。规定 其拓扑维数为0 。基于点对象，可以定义其它空间对象。 定义2 2 ：连续映射f 【0 ，1 】一r 2 的象，若且满足：t j ，缸 0 ，1 1 ，当t 1 4 t 2 时，f ( t - ) f m ) ， 称为线或者简单曲线。特别，当f ( 0 ) = f ( 1 ) 时，称简单闭曲线。规定简单曲线和简单 闭曲线的拓扑维数为1 。 定义2 3 ：简单曲线l = f ( 【0 ，1 】) 的边界l = 坟o ) ，f ( 1 ) ，。简单闭曲线的边界为空集。地 理空间中的许多地理实体可以被抽象为线，如，河流、道路、通讯线路等。 定义2 4 ：简单区域指r 2 中规则的有界闭子集，且它的内部、外部均是连通的， 边界为简单闭曲线，规定它的维数为2 。简单区域在本文中简称区域。有许多的地 理实体可以被作为区域来考虑，如，湖泊、城市、种植同一种农作物的地块等。 本文采用g i s q 6 关于空间对象的概念，但并不关心与对象关联的地理实体。在 空问表示理论中如果将空间粒度( 空间比例尺) 作为研究的一个因素，区域与点、线 7 重庆大学硕士学位论文 间存在转换，即在小比例尺下的区域在大比例下可能转换为线甚至点，反过来也 是一样的。本文以点、线、区域作为空间基本对象，即：空间对象= f 点，线，区 域， 空间关系 空间关系是指空间对象间存在的与空间特性有关的关系。空问关系分为拓扑 关系、方位关系和度量关系【3 6 1 2 , 1 3 , 2 8 1 。拓扑关系指拓扑变换下保持不变的空间关系， 如，空间对象的分离、相连、连通等。方位关系指空间对象在空间的一种顺序， 如，前、后、左、右、上、下，东、南、西、北等。度量关系指用某种度量尺度 来描述的空间对象间的关系，如，距离等。 空间关系表示了空间对象之间的联系，通过这些联系，空间信息被有机地组 织在一起，成为空间信息查询与处理的重要组成部分。空间关系的描述与表达成 为g i s 与c a d 等计算机图形处理系统区别的标志。空间关系是空间对象间固有存 在的。在g i s 中，空间对象被放在一定的空间中进行研究，在这样的空间中，对 象的分离、连通、方位及距离是客观存在的，它们需要与空间对象一起被表示。 同时，空间关系又是复杂的。空间对象间不仅存在上述的拓扑、方位、度量关系， 还存在相似关系、相关关系等。要完整地描述空间对象间的关系是困难的，也是 不可能的。 空间关系表示方法分为3 类：定量表示、定性表示、定性与定量结合表示。定 量表示方法是目前g i s 系统中普遍采用的方法。定量表示的特点是用代数与数值 分析方法进行空间信息分析和处理的基础。然而，大量的空间信息和复杂的空间 关系仅用定量方式来描述是不够的。定性表示是使用非定量的方法和技术来对空 间对象及空间关系进行描述的方法。大量的空间对象及其关系要通过定量的方法 来表示它既不可能，也没有必要。另一方面，对空间对象( 如，山脉、海岸线) 的描 述总是在一定程度上的近似表示，而不可能获得准确值。近年来，定性表示越来 越受到研究者的重视，这与空间关系本质上是定性的【7 】认识相一致。定性表示是空 间对象及关系描述在更高层次上的抽象。它以空间对象的本质特征为主而忽略次 要特征，以空间关系的主要方面为主而抛弃一些枝节的、对解决问题不重要的关 系。定性表示获得的定性信息一方面可以满足一定的应用需求，另一方面它为进 一步更精细的定量表示和处理提供更可靠的候选集。将定性表示与定量表示结合 起来便成为定性与定量结合方法。 2 1 2 空间推理的定义 空间推理是指利用空间理论和人工智能a i ( a r t i f i c i a li n t e l l i g e n c e ) 技术对空间对 象进行建模、描述和表示，并据此对空间对象问的空间关系进行定性或定量分析 和处理的过程。目前，空间推理被广泛应用于地理信息系统、机器人导航、高级 2 空问推理与定性空间推理 视觉、自然语言理解、工程设计和物理位置的常识推理等方面，并且正在不断向 其他领域渗透，其内涵非常广泛。空间推理的研究在人工智能中占有很重要的地 位，是人工智能领域的一个研究热点。 空间推理具有以下1 1 项关键属性【3 2 1 ，其中，至少前7 项是基本空间推理所必 须具备的，其余的为可选项。 1 ) 空间推理是以空间和存在于空间中的空间对象为研究对象，不能脱离空问 和存在于空间中的空间对象来研究空间推理。 2 ) 在空间推理过程中运用了人工智能技术和方法。 3 ) 空间推理处理的是个或几个推理的问题。 4 ) 空间推理是基于空间和存在于空间中的空间对象已经被建模的前提下，不 能在没有模型的情况下讨论空间推理。 5 ) 空间推理必须能够给出关于空间和存在于空间中的空间对象的定性或定 量的推理结果。 6 、空间推理必须能够描述空间行为。 刀当空间推理模型把问题分解为几个组成部分时，必须能够描述这些组成部 分的相互作用。 8 1 在空间推理过程中，可能用到空间谓词，空间中确定的点使某些空间谓词 为真，而使另一些空间谓词为假。 9 1 空间推理应该能够处理带有模糊性和不确定性的空间信息。 1 0 1 空间推理中应该能够添加和处理时间因素，即成为时空推理。 1 1 1 空间推理应该具有空间自然语言理解能力。 本论文所研究的空间推理，也具有上述属性。 2 1 3 空间推理的研究内容 从研究内容上看，空间推理研究的对象是目标之间的空间关系，目的是通过 对空问关系的分析处理提取出可供决策支持的空间信息，是一种智能化的空间数 据处理技术。因此从广义上讲，空间推理可以理解为通过对空间数据的自动处理 以得到可支持空间决策的数据的智能化处理过程【3 2 1 。同时，空间推理的过程又是 一个从空间数据到空间数据的过程，前者为利用一定的数据格式保存下来的数据， 后者则为所发掘出来的数据，所发掘出来的空间数据又可以丰富原始空间数据， 因而，空间推理的过程又是一个循环反馈的过程。 以下介绍几个有代表性的空间推理研究机构、网站以及它们的研究工作，在后 面给出的空间推理的主要研究方向和研究热点是在对它们的研究工作进行分析和 总结之后得到的。这些有代表性的空间推理研究机构和网站有以下几个： 美国国家地理信息和分析中, t ：, n c g i a ( n a t i o n a lc e n t e rf o rg e o g r a p h i c 9 重庆大学硕士学位论文 i n f o r m a t i o na n da n a l y s i s ) 是一个独立的研究联盟，致力于包括g i s 在内的地理信息 秘学粒穗关按零豹基聪骚究，残立予1 9 8 8 年。这令联爨豹3 令转会是热利福慰驻大 学、布法罗大学和缅阙州大学，主要由国家自然科学基金会n s f ( n a t i o n a ls c i e n c e f o u n d - a f i o n ) 瓷秘，瑰嶷，这个联盟每笨摄到犬终5 0 0 7 5 美元懿爨劈。今天，n c g i a 已经成为一个国际的熬础研究焦点，它的3 个站点吸引了来自世界各地的短期和长 魏诱淘喾，它的教弯帮基也满足了不瓣层次戆学生戆爨要。n c g i a 静磷究课嚣主要 包括：空间数据的精度和不确定性、认知的模型和表示等。 欧溯定性窆闻接理网s p a c e n e t 是一个瞧多魇大学联合戆空阉攘理毂嬲终， 分布谯欧洲的有1 2 个s p a c e n e t 站点，是由欧盟资助的。由英国利泫大学计算机 研究学院主任a 赶壤o n yc o h n 教授领导，致力予空阕表示和窟动推理( 龙其是定性空 问推联) 以及掰扑和形式化的镦间模型。c o h n , r a n d e l l 和c u i 等人曾提出了著名的区 域连接演算( r c c ) 算法。 旺兹堡大学的空间信息研究组。是一个致力子空间信息的理解和应用的研究 机构。它们的研究主要涉及g i s 、超文本导航釉科学可视化的特征、空间推理的形 式方法和人们对空间认识经验的研究。 慕尼黑大学空间推理研究组，主要研究方向是定性空间推理。包括空间位置 知识酌表示、空闻信纛传播约束、定性空间推理和神经网络模型的综合。 - 瑞士洛蔡的a i 实验室e p f l ，主要研究方向包括自然语富的语义和逻辑分析、 时空推理、谱富和感知之间的关系。 通过对有代表性的空间推理研究机构和网站以及它们的研究工作的分析和总 结，农查阕许多空闯攘理方瑟的论文豹墓穑上，我髓可越妇缡舀空间接理酌童要 研究方向( 内容) 。由于空间推理涉及的内容和空间推理的成用领域都十分广泛， 不能搬空阋擦理的研究方向梦l j 举褥j 妻子详细。园缱，下面给激的主甏研究方向是 对空间推理的许多研究方向进行分类、归纳和整理之厝得到的。 1 ) 空闻数据库静精度 2 ) 空间关系语言 3 ) 空蠲臻淫与缝灌信惠系统 4 ) 空间决策支持系统 5 ) 空麓数据酶不淤定往憝瑾 6 ) 形式化的绘图知识 7 ) 薅空攘瑷 8 ) 定性空间推理 9 空蠢攘理兹焉声赛嚣 1 0 ) 基于实例( c a s e b a s e d ) 的空间推理 1 0 2 空间推理与定性空间推理 1 1 ) 空间推理的认知问题 1 2 ) 空间推理与机器人视觉 1 3 ) 常识推理 1 4 ) 区域连接演算r c c $ 其中的研究热点有时空推理s t s r ( s p a t i o - t e m p o r a ls p a t i a lr e a s o m n d ，定性空间 推理q s r ( q u a l i t a t i v es p a t i a lr e a s o i l i n g ) 和地理信息系统三个主要方向，下面分别介 绍。 时空推理 总的说来影响空间推理的结果包括时间因素和空间因素。所谓时空推理是指 空间推理过程中添加时间因素。地表、地下和大气等空间对象的状态不仅受空间 因素的影响，同时从一个较长的时间段来看是要受到时间因素的影响的。可以说， 时空推理是更一般的空间推理，而空间推理是时空推理的一个特例。 定性空间推理 当描述一个空间位置或对这样的某一位置进行定位的时候，要获得精确、定 量的描述往往是不可能的而且也是不必要的。在这种情况下要用到关于空间位置 的定性推理。定性空间包括许多不同的方面，我们不仅要判断什么样的空间实体 是我们可以接受的，同时还要考虑描述这些实体间关系的不同方法，例如：我们 可以仅考虑它们的拓扑结构、大小、形状、区域和它们之间的距离，当然这些因 素之间并不是绝然孤立的。 地理信息系统 地理信息系统是为了解决资源和环境等全球性问题而发展起来的技术与产 业。地理信息系统是一个能够收集、存储、处理、和显示地理空间信息( 包括位置 信息和非空间的文字信息) 和处理用户查询的计算机系统。现在，地理信息系统应 该根据现有的或者增加的空间结构信息对空间结构进行定量和定性的推理，而且 可以处理模糊性和不确定性的信息，其中用到空间推理的有关技术。 2 1 4 空间推理的方法学 空间推理从几何、使用和功能三个方面研究空间知识的表示和处理，主要研 究的内容包括：空间推理与机器人视觉、形式化的绘图知识、空间关系语言、定 性空间推理等等。近几年，由于认识到空间知识本质上是定性的，定性空间推理 ( q u a l i t a t i v es p a t i a lr e a s o i l i l l g ) 研究成为空间推理研究的主流，发展出公理化、代 数、几何约束满足和基于模型的推理等方法田j 。 公理化方法以逻辑学或部分学( m e r e o l o g y ) 为基础，选择一组基本的关系和谓 词，建立一类空间概念和关系的公理和推理规则，以此表示并处理空间知识。 代数方法把空间关系作为项来处理。在构造出基本空间关系的原子复合表 重庆大学硕士学位论文 后，既可以利用约束满足算法，通过实现关系集的复合运算完成推理，也可以建 立全部关系集复合运算的完全复合表，通过查表实现推理。 几何约束满足方法充分表示并利用几何领域的约束，通过约束满