（计算机应用技术专业论文）基于认知的空间拓扑关系表示与推理.pdf

中文摘要 摘要 地理信息系统( g i s ) 在资源调查、评价、管理和监测，在城市的管理、规划和市 政工程、行政管理与空间决策、灾害的评估与预测、地籍管理及土地利用，在交通、 农业、公安等诸多领域得到了广泛的应用。但是，g i s 中空间分析功能的发展显得比较 落后，而空间分析是建立在空间目标位置和属性表达以及目标间复杂空间关系表达的 基础上，要提高空间分析能力，必须解决空间关系描述与表达。因此，空间拓扑关系 的研究已成为g i s 研究的重点和热点。结合定性推理、空间推理与人工智能产生的定 性空间推理，已成为人工智能的一个研究热点，不同于定性推理研究物理系统的结构、 行为、功能及其相互联系，定性空间推理分析和处理的是人们对几何空间常识知识的 认知：不同于空间推理研究空间对象的建模、描述、表示及其关系的分析和处理，定 性空间推理面对的是空间对象的定性特征和定性关系。定性空间推理研究的是人类对 几何空间中空间对象及其关系定性认知常识的表示与处理。近年来，定性空间推理的 快速发展，也促进了g i s 的发展，地理信息系统成为定性空间推理最成熟也最广泛的 应用领域。因此，研究、分析、探讨定性空间拓扑关系和定性空间推理，对促进地理 信息系统的发展有重要的学术和实用意义。 本文通过研究g i s 中的核心问题拓扑空间关系，将定性空间推理的方法应用到 空间关系的分析中。在基于层次认知的拓扑关系组合推理的基础上，研究了空间拓扑关 系层次表示方法和推理方法，以及空间约束满足问题推理求解算法。 论文首先介绍了定性空间拓扑关系表示和定性空间推理的基本概念、研究背景、内 容和现状，确定了论文研究涉及的相关知识领域。 其次以点集拓扑学和本体论为基础，研究了空间拓扑关系表示方法。证明了r c c 、 n 交集与分类不变量模型具有相同的二维空间区域拓扑关系分类能力：证明了4 交集模 型对于分类二维空间区域间拓扑关系的充分必要性，从而将3 种不同的研究方法统一起 来。并从人类认知的角度提出了基于层次认知的拓扑关系分类方法h b m 。该方法的分 类能力等价于c b m 模型，不弱于r c c 模型、n 交集模型( 4 i m ，9 i m ，d e4 1 m ，d e _ 9 i m ) 和分类不变量模型中的任意一种。 再次，给出了空间拓扑关系层次组合表，给出了空间拓扑关系层次表示方法和推理 方法，给出了比路径约束满足算法更有效的空间约束满足问题推理求解算法。 最后，开发了拓扑推理的原型系统，从实践的角度验证这一推理模型的正确性。 关键词：定性空间表示，定性空间推理，h b m ，约束满足问题 英文摘要 a b s t r a c t g i s ( g e o g r a p h i c a li n f o r m a t i o ns y s t e m ) h a sb e e nw i d e l yu s e di nm a n yf i e l d s ，s u c ha s r e s o u r c er e s e a r c h ，e v a k m t i n n , m a n a g e m e n ta n di n s p e c t i o n ；c i t ym a n a g e m e n t ，c i t yl a y o u t , m u n i c i p a lw o r k s ，a d m i n i s t r a t i v em a n a g e m e n t ，s p a t i a ld e c i s i o n ，d i s a s t e re v a l u a t i o na n d f o r e c a s t ，l a n dm a n a g e m e n ta n du t i l i z a t i o n ，a n dt r a f f i c ，a g r i c u l t u r e ，p u b l i cs e c u r i t y , e t c ，b u tt h e d e v e l o p m e n to fs p a t i a la n a l y t i c a lf i m c t i o no fg i si ss l o w m e a n w h i l e , s p a t i a la n a l y s e sa r e b a s e do nt h es p a t i a lt a r g e tl o c a t i o n ，a t t r i b u t i o ne x p r e s s i o na n dc o m p l e xs p a t i a lr e l a t i o n e x p r e s s i o nb e t w e e nt a r g e t s i no r d e rt oi m p r o v et h ec a p a b i l i t yo fs p a t i a la n a l y s e s ，t h e d e s c r i p t i o na n de x p r e s s i o no fs p a t i a lr e l a t i o n sm u s tb es o l v e d t h e r e f o r e ，t h er e s e a r c ho f s p a t i a lt o p o l o g i c a lr e l a t i o n s h i ph a sb e c o m eah o tp o i n ti nt h er e s e a r c ho fg i s q u a l i t a t i v e s 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 er e a s o n i n g , s p a t i a lr e a s o n i n ga n d a 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 o fs t r u c t u r e ，a c t i o n , f u n c t i o ua n dt h e i ri n t e r c o n n e c t i o n so fp h y s i c a ls y s t e m si nq u a l i t a t i v e p 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 dp r o c e s s e st h eh u m a nc o g n i t i o no f g e o m e t r i cs p a t i a lc o m m o n s e n s ek n o w l e d g e d i f f e r e n tf r o mt h er e s e a r c ho 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 sa n a l y z i n ga n dp 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 l r 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 lr e a s o n i n gt r e a t st h eq u a l i t a t i v ec h a r a c t e r sa n d q 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 q u a l i t a t i v es p a t i a lr e a s o n i n gr e s e a r c h e sr e p r e s e n t a t i o n a n dp r o c e s s i n go fh u m a n sq u a l i t a t i v ec o g n i t i o nf o rs p a t i a lo b j e c t sa n dt h e i rr e l a t i o n si n g e o m e t r i cs p a c e i nr e c e n ty e a r s ，s p a t i a lr e a s o n i n gh a sg r e a td e v e l o p m e n t ，a tt h es a m et i m ei t p r o m o t e st h ed e v e l o p m e n to fg i st h a th a sb e c o m et h em o s tw i d e l ya n dm a t u r ea p p l i c a t i o n d o m a i no fs p a t i a lr e a s o n i n g h e n c e ，t h er e s e a r c ho ft h es p a t i a lt o p o l o g i c a lr e l a t i o n s h i pa n d q u a l i t a t i v er e a s o n i n gh a si m p o r t a n ta c a d e m i ca n dp r a c t i c a ls c e n ei na d v a n c i n gt h e d e v e l o p m e n to fg i s t h i sp a p e ra p p l i e ss p a t i a lr e a s o n i n gm e t h o dt os p a t i a lr e l a t i o n a la n a l y s i sb ys t u d y i n gt h e c e n t e rp r o b l e mo fg i s 一s p a t i a lt o p o l o g i c a lr e l a t i o n s h i p i nt h ef o u n d a t i o no fc o m b i n a t i v e r e a s o n i n go f t o p o l o g i c a lr e l a t i o n s h i pb a s e do nh i e r a r c h i c a lc o g n i t i o n ，h i e r a r c h yr e p r e s e n t a t i o n m e t h o d sa n dh i e r a r c h yr e a s o n i n gm e t h o d so fs p a t i a lt o p o l o g i c a lr e l a t i o n sa r er e s e a r c h e d ，a n d t h er e a s o n i n gr e s o l v i n ga l g o r i t h r af o rs p a t i a lc o n s t r a i n ts a t i s f a c t o r yp r o b l e mi sr e s e a r c h e dt o o f i r s t l y , t h eb a s i cc o n c e p t i o n , i n v e s t i g a t i o nb a c k g r o u n d , c o n t e n ta n da c t u a l i t yo f 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 no f t o p o l o g i c a lr e l a t i o n sa n dq u a l i t a t i v es 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 ， a n dt h er e l a t e ds t u d yf i e l d sa r cc o n f i r m e d s e c o n d l y , b a s e do nt h ep o i n t s e tt o p o l o g ya n do n t o l o g y , r e p r e s e n t a t i o nm e t h o d sf o rs p a t i a l i 重庆大学硕士学位论文 t o p o l o g i c a r e l a t i o n sa r er e s e a r c h e d i ti sp r o v e dt h a tr c cm o d e l ，n - i n t e r s e c t i o nm o d e la n d c l a s s i f i c a t i o ni n v a r i a n tm o d e lh a v et h es a m ec l a s s i f i c a t i o nc a p a b i l i t yf o rt o p o l o g i c a lr e l a t i o n s b e t w e e n2 - - d i m e n s i o n a ls p a t i a la r e a s ；t h a t4 i n t e r s e c t i o nm o d e li sn e c e s s a r ya n ds u f f i c i e n tf o r c l a s s i l y i n gt o p o l o g i c a lr e l a t i o n sb e t w e e n2 - d i m e n s i o n a ls p a t i a la r e a si sp r o v e d ，t h e nt h e s e3 d i f f e r e n tm e t h o d sa r eu n i f i e d ，f r o mt h ea s p e c to fh u m a nc o g n i t i o n 1 璐m ( h i e r a r c h y b a s e d m e t h o d ) ，an e wm e t h o df o rc l a s s i f y i n gt o p o l o g i c a lr e l a t i o n s ，i sp r e s e n tb a s e do nh i e r a r c h i c a l c o g n i t i o n t h ec l a s s i f i c a t i o nc a p a b i l i t yo fh b mi sa ss t r o n ga st h a to fc b m a n di sn o t w e a k e rt h a nt h a to fa n ym o d e li nr c cm o d e l ，n - i n t e r s e c t i o nm o d e l ( 4 i m ，9 i m ，d e _ 4 i m ， d e _ 9 i m ) a n dc l a s s i f i c a t i o ni n v a r i a n tm o d e l f u r t h e r , t h eh i e r a r c h yr e p r e s e n t a t i o nm e t h o da n dt h eh i e r a r c h yr e a s o n i n gm e t h o do f s p a t i a lt o p o l o g i c a lr e l a t i o n sa r ep r e s e n t ，a n dar e a s o n i n gr e s o l v i n ga l g o r i t h mf o rs p a t i a l c o n s t r a i n ts a t i s f a c t o r yp r o b l e mt h a ti sm o r ee f f i c i e n tt h a np a t h - c o n s i s t e n c ya l g o r i t h mi sg i v e n f i n a l l y , ap r o t o t y p es y s t e mf o rt o p o l o g i c a lr e a s o n i n gi sb u i l ta n dt h ec o i t e c t n e s so ft h e s y s t e mi sv a l i d a t e d k e y w o r d s ：q u a l i t a t i v es 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 ，i - i b m ，c o n s t r a i n t s a t i s f a c t o r yp r o b l e m i v 1 绪论 1 绪论 “数字地球”、“数字中国”的提出促进了空间信息采集、处理与应用的研究。 r s 与g p s 为空间信息的采集提供了技术支持，g i s 技术从定量的角度建立了空间 信息处理与应用的理论和技术体系。但是，空间信息是复杂的，从量上来看是海 量级的；从种类上看不仅包括数值型、字符型，还包括图形、图像等许多类型； 并且空间信息间的相互联系是固有的。因此，对空间信息仅进行定量的研究是不 够的，还需要从定性方面进行研究。本章对本文的研究对象、目的以及研究现状 进行了介绍，并介绍了本文的工作。 1 1 课题来源及研究的目的和意义 空间推理( s p a t i a lr e a s o n i n g ，s r ) 是指利用空间理论和人工智能( a n i f i c i a l i n t e l l i g e n c e ，a t ) 技术对空间对象进行建模、描述和表示，并据此对空间对象间的 空间关系进行定性或定量分析和处理的过程。目前，空间推理被广泛应用于地理 信息系统、机器人导航、高级视觉、自然语言理解、工程设计和物理位置的常识 推理等方面，并且正在不断向其他领域渗透，其内涵非常广泛。空间推理的研究 在人工智能中占有很重要的地位，是人工智自领域的一个研究热点t ”。 空间推理和地理信息系统是密不可分的。地理信息系统( g e o g r a p h i c i n f o r m a t i o ns y s t e m ，g i s ) ，一般来说，可定义为：“用于采集、存储、管理、处理、 检索、分析和表达地理空间数据的计算机系统，是分析和处理海量地理数据的通 用技术”。随着地理信息系统在资源调查、评价、管理和监测，在城市的管理、规 划和市政工程、行政管理与空间决策、灾害的评估与预测、地籍管理及土地利用， 在交通、农业、公安等诸多领域得到了广泛的应用，学术界与工程界都越来越关 注地理信息系统的发展；目前，g i s 是空间推理应用得最为广泛的领域，也是空间 推理的研究热点之一【6 】。 当描述一个空间对象或对这样的对象进行推理的时候，要获得精确、定量的 数据通常是不可能的或不必要的。在这种情况下，需要用到关于空间结构的定性 空间推理p j 。由于空间提供了非常丰富的结构，空间的许多不同方面，例如距离、 方向、形状和拓扑结构都具有定性特征f 4 ；另一方面，人们接触到的不确定定性空 间信息远远多于确定性空间信息1 5 】，因此定性空间推理是空间推理中必不可少的重 要组成部分。 定性空间推理所研究的是空间推理中关于定性的部分内容，它主要从空间对象 间关系的定性表示与推理的角度来研究空间推理问题。所涉及的空间关系包括：度 重庆大学硕士学位论文 量关系、方位关系和拓扑关系等i ”。度量空间关系是用某种度量空间中的度量指标 来描述的对象间的关系( k r e y s z i g1 9 8 7 ，r o b i n s o n e t a1 9 8 7 ) ，如对象间的距离等； 方位空间关系是用来描述对象在空间中的某种顺序的关系( k a i n z1 9 9 0 ，f r e e m a n 1 9 7 5 ，h e m a n d e z1 9 9 1 ) ，如前后、上下、左右、东西南北等；拓扑空间关系是指拓 扑交换下的拓扑不变量( e g e n h o f e r1 9 8 9 ，e g e n h o f e ra n dh e r r i n g1 9 9 0 ) ，如空间对象 的相邻和连通关系。 一般说来，对象间的空间关系与对象的维数、形态、大小及其所在空问的维 数有关，各类拓扑空间关系也存在着一定的联系，对象间空间关系的描述形式各 不相同，因此对象间的空间关系是极为复杂多样的。认识空间关系的本质与判定 机理，寻找空间关系形式化描述、表达和操作的方法与途径，便是空间关系理论 研究的目的所在。 拓扑空间关系表示是空间关系理论的重要组成部分，也是空间数据库设计的 重要基础，其研究将有助于设计有效的空间查询和数据处理方式。 由上可知，研究、分析、探讨空间拓扑关系表示和定性空间推理技术，对于 提高我国各行业、特别是城市规划、建设、管理与服务的数字化水平，促进地理 信息系统的发展，都有着极为重要的学术和实用意义。 此学位论文的研究工作是国家“十五”科技攻关项目：城市规划、建设、管理与 服务的数字化工程( 项目编号：2 0 0 2 b a l 0 7 b ) 的一部分。 从2 0 0 0 年开始，我们课题组就在郭平副教授的指导下，系统地开始了本课题 的研究，几年中己取得了初步的成果。以上这些研究背景为本论文研究工作的开 展打下了良好的基础。 1 2 国内外研究现状 1 2 1 定性空间表示的研究现状 我们知道，空间关系包括：度量关系、方位关系和拓扑关系等。但本论文的 研究只涉及拓扑关系的定性表示与推理，因此这里也只介绍空间拓扑关系的表示。 目前，空间对象拓扑关系的研究主要集中在两条主线上： 确定性区域间拓扑关系的研究，主要体现在g i s 和空间推理的相关研究 中； 不确定区域的表示及其分析方法的研究，主要体现在地理分析、图像理解 和计算机视觉的相关研究当中。 本文主要研究确定性区域间的拓扑关系。 对于确定性区域间拓扑关系模型，主要有基于逻辑的公理化拓扑理论和传统 的数学拓扑两大类方法，其中最有代表性的是r c c 形式化模型和n 一交集模型，另 1 绪论 外还有许多学者提出的改进方法。 ( 1 ) r c c 形式化模型 r a n d e l l 等人基于c l a r k e 的空间演算逻辑公理提出了以区域为本体基元的r c c 理论1 9 1 “。r c c 模型假设个原始的二元关系c ( x ，y ) 表示区域x 与y 连接。关系c 具有自反性和对称性，可以根据点出现在区域中来给出关系c 的拓扑解释。c ( x ，y ) 表示x 和y 的拓扑闭包共享至少一个点，使用关系c 可以定义8 个基本关系 分 离( d c ) ，外接( d e ) ，部分覆盖但o ) ，内切( t i p ) ，包含( n t t p ) ，被内切( t t p i ) ，被 包含q i t r p i ) ，相等( e q ) ，也称为r c c - 8 ，如果不考虑区域的边界，则得到r c c 5 。 此后c o h n 等人【1 l 】以区域的凸壳为基元，得到了2 3 个不相交且联合完备的关系，即 r c c - 2 3 ，如果不区分d c 和e c ，则缩减为r c c 1 5 。 ( 2 ) n 交集模型 以点集拓扑学为基础，o u t i n g “】在1 9 8 8 年首先定义了两个空间物体间的拓扑关 系集 = , # , i n s i d e ，o u t s i d e ，i n t e r s e c t s 。其后，通过考虑点集边界和内部的交集给出了 拓扑空间关系的描述，但是这些关系既不互斥也不完各。 p u l l a r 等口”将点集方法加以扩充，运用拓扑学理论中点集的边界( b o u n d a r y ) 和 内部( i n t e r r i e r ) 的概念，给出了覆盖( o v e r l a p ) 和相邻( n e i g h b o r ) 两个关系定义。 w a g n e r ( 1 9 8 8 ) 定义了相邻、相离、严格包含、相交四种拓扑空间关系。e g e n h o f e r ；和f r a n z o s a t 2 2 】提出了一个4 ，交集表达的拓扑空间关系描述框架。e g e n h o f e r l 3 8 】引进了 点集的外部，构造了一个由点集的边界、内部、余之间的交集组成的9 交集，以此 作为描述两个点集间拓扑空间关系的框架。c l e m e n t i n i 等人n 3 】在e g c n h o 向所定义的 4 一交集基础上，运用维数扩展法( d i m e n s i o ne x t e n d e dm e t h o d ，d e m ) ，即用两个空 间对象内部与对象之间交集的维数，作为描述两个对象间拓扑空间关系的框架。 进一步，他们给出了二维拓扑空间关系的最小集。这种方法形式化地描述了二维 空间目标之间的拓扑空间关系。 ( 3 ) c b m ( c a l c u l u s - b a s e dm e t h o d ) r c c 及n _ 交集模型研究的拓扑关系划分越来越精细，但作为人类的认知常识 是不能同时区分这么多种关系的。c l e m e n t i n i ，e ，d if e l i c e ，p a n do o s t e r o m ，p i j3 】以 人类认知为基础，给出了5 种基本拓扑关系，f m u c h , i n , c r o s s ，o v e r l a p ，d i s j o i n t ， 称为c b m ( c a l c u l u s b a s e dm e t h o d ) 。在此基础上，通过添加线对象与区域对象的 求边界函数，证明了c b m 与d e9 i m 具有相同的拓扑关系分类能力。由此，将空 间对象间拓扑关系的分类与人类认知习惯联系了起来。 ( 4 ) v o r o n o i 图模型 在研究空闻点的邻近区域或影响区域时，使用了v o r o n o i 图。李成民等 4 】基 于v o r o n o i 图，提出并研究了面条模型中动态空间关系推断的四邻近数序模型 重庆大学硕士学位论文 ( 4 砸i ) ，给出了唯一、完备性推断规则。陈军等1 1 5 1 基于v o r o n o i 图用交叉与交相 结合的方法对9 i m 进行改进，提出了基于v o r o n o i 图的9 交模型( v o r o n o i b a s e d 9 - i n t e r s e c t i o n ) 来描述空间拓扑关系。 ( 5 ) 拓扑不变量方法 拓扑关系是拓扑变换下的不变量，因此从拓扑不变量的角度研究空间对象间 的拓扑关系是一种自然的选择。1 6 在4 i m 的基础上研究了空间对象交的类型、维 数、序等不变量，给出了分类不变量的概念。利用不同的分类不变量可以刻划空 间拓扑关系更进一步的细节，给出拓扑关系更丰富的分类。1 7 对一般空间对象研 究了交容度不变量( c o n t e n ti n v a r i a n t s ) 、交维数不变量和交集数量不变量，对简单 线对象研究了交序列( i n t e r s e c t i o ns e q u e n c e ) 、交类型( h a l e r s e c l i o nt y p e ) 、共线性 ( c o l l i n e a r i t ys e n s e ) 、连接方向( l i n ko r i e n t a t i o n ) 等不变量，同时给出了分类线 对象间拓扑关系的分类不变量。 ( 6 ) 非经典逻辑方法 b e n n e 硭1 8 1 发展了空间逻辑的研究成果，给出了空间对象关系表示与推理的命 题逻辑方法，b e n n e t t 【“懈模态逻辑方法引入到空间对象关系表示与推理中。b e n n e t t 和c o h n l 2 0 1 研究了多维多模态逻辑在定性时空关系表示中的应用。 1 2 2 定性空间推理的研究现状 空间推理的研究源于7 0 年代，最初是以量空间为研究对象的。多维的并且不 能通过单一的纯量表示的量空间，只是在近年来才成为知识表示中的一个重要领 域。由于空间推理的研究对象的转变，极大的拓展了空间推理的研究领域，使空 间推理的理论和应用近年来有了长足的进步。定性空间推理也成为空间推理的重 要研究领域【”。 ( 1 ) 组合表推理 虽然关于定性空间推理的研究已有十几年，获得了一些推理方法，但是基于 组合表的推理仍是定性空间推理最常见的推理方法【2 1 1 。组合表推理的简单性与有 效性受到了许多研究者的关注，如 2 2 ，2 3 ，2 4 ，2 5 ，2 6 ，2 7 ，2 8 。 ( 2 ) 逻辑演算 通过逻辑演算来进行推理是定性空间推理的另一种方法。r a n d e l l ，c u ia n d c o h n t g l 通过空间谓词c ( x ，y ) 定义空间逻辑系统，将空间对象间的拓扑关系表示为谓 词公式，利用一阶谓词逻辑建立了一阶逻辑范畴下空间拓扑关系推理技术。 【1 8 】用命题逻辑来表示空间对象间的拓扑关系，由此推理成为命题演算。 【1 9 将模态逻辑引入空间拓扑关系的描述与推理中，进行了一些尝试性研究。 ( 3 ) 拓扑关系推理的分层逼近法 石纯一，廖士中等 2 9 1 将定性空间推理问题划分为易处理类与非易处理类，给 4 1 绪论 出了易处理类的分层逼近推理方法。所谓易处理类即是在多项式时间内能解决的 问题的集合。 【2 9 】建立了空间区域到单位闭球区域的联系，证明了在度量空间( r n ，6 ) 上引 入6 ( 时上的欧氏度量) 诱导的拓扑后，若t ( n ，n ) 是有效的( n ，n ) 完备集( n 维空间 区域对象间拓扑关系完备集) ，b 。是r n 中非空闭球区域问拓扑关系的有效完备集， 则有：t ( n ，n ) = b 。 由此，他们建立了空间区域对象间组合表的推导算法，利用b 。推导出了空间 区域之间的拓扑关系组合表。进一步的工作是利用r c c 8 的概念邻域，设计了空 间拓扑关系约束满足问题的分层逼近法，实现了不同拓扑关系层次问的推理。 ( 4 ) 其它方面 1 9 9 0 年，e d a v i s 针对一个简单的例子，首先确定了角度、坐标系、形状和拓 扑基本元素，然后建立了有关的几何公理和物体物理形态公理。公理和场景都以 谓词逻辑的形式描述。1 9 9 5 年，n a s h e r 和l e u l 3 0 1 利用部分学和拓扑学的概念， 建立了一个具有完整语义描述的空间推理公理系统。 综上所述，在定性空间推理中，更多的研究工作在定性关系表示方面，推理 研究相对较少。 1 3 研究内容 1 3 1 论文主要内容 本论文研究的内容主要包括以下几部分 基于分类不变量的拓扑空间表示研究 基于点集拓扑的空间表示研究 基于分类不变量的拓扑空间表示与基于点集拓扑的空间表示之间关系的 研究 基于层次的空间拓扑关系分类研究 基于人类认知模型的推理研究 原型系统开发与实现 1 3 2 论文结构 全文共分6 章，涉及定性空间拓扑关系表示、定性空间推理和原型系统的开 发与实现。 第1 章是绪论，介绍了定性空间表示和推理的基本概念与研究内容，以及国 内外研究现状，并分析了现有研究中的些不足，确定了研究内容。 第2 章是关于定性空间知识表示研究。通过几何空间的分析确定了本文中涉 及的空间对象类型与空间关系类型。以此为基础研究了空间拓扑关系的主要表示 1 绪论 出了易处理类的分层逼近推理方法。所谓易处理类即是在多项式时间内能解决的 问题的集合。 2 9 1 建立了空间区域到单位闭球区域的联系，证明了在度量空间( r n ，6 ) 上引 入6 ( r n 上的欧氏度量) 诱导的拓扑后，若t ( n n ) 是有效的( n ，n ) 完备集( n 维空间 区域对象间拓扑关系完备集) ，b 。是r n 中非空闭球区域问拓扑关系的有效完备集， 则有：t ( n ，n ) - b 。 由此，他们建立了守问区域对象问组合表的推导算法，利用b 。推导出了空间 区域之问的拓扑关系组合表。进一步的工作是利用r c c - 8 的概念邻域，设计了宅 间拓扑关系约柬满足问题的分层逼近法，实现了不同拓扑关系层次间的推理。 ( 4 ) 其它方面 1 9 9 0 年，e d a v i s 针对一个简单的例子，首先确定了角度、坐标系、形状和拓 扑基本元素，然后建立了有关的几何公理和物体物理形态公理。公理和场景都以 谓词逻辑的形式描述。1 9 9 5 年，n a s h e r 和lv i e u 【”1 利用部分学和拓扑学的概念， 建立了一个具有完整语义描述的空间推理公理系统。 综上所述，在定性空间推理中，更多的研究工作在定性关系表示方面，推理 研究相对较少。 1 3 研究内容 1 3 1 论文主要内容 本论文研究的内容主要包括以下几部分 基于分类不变量的拓扑空问表示研究 基于点集拓扑的空间表示研究 基于分类不变量的拓扑空间表示与基于点集拓扑的空间表示之间关系的 研究 基于层次的空间拓扑关系分类研究 基于人类认知模型的推理研究 原型系统开发与实现 1 3 2 论文结构 全文共分6 章，涉及定性空间拓扑美系表示、定性空间推理和原型系统的开 发与实现。 第1 章是绪论，介绍了定性空间表示和推理的基本概念与研究内容，咀及国 内外研究现状，并分析了现有研究中的一些不足，确定了研究内容。 第2 章是关于定性空间知识表示研究。通过几何空间的分析确定了本文中涉 及的空间对象类型与空间关系类型。以此为基础研究了空间拓扑关系的主要表示 及的空问对象类型与空间关系类型。以此为基础研究了空间拓扑关系的主要表示 重庆大学硕士学位论文 方法。提出并研究了拓扑关系表示法h b m 。 第3 章介绍了定性推理和空间推理理论，综述了定性空间推理的研究方法和 成果。 第4 章研究了以组合表为基础的定性空间推理技术和定性空间层次表示与推 理技术。研究了拓扑关系组合表推理方法，研究了h b m 的层次结构及其推理方法， 给出了空间约束满足问题的推理求解算法a 第5 章开发并实现了基于层次的空间对象约束满足问题求解的原型系统。 第6 章是论文所做工作的总结，同时提出了一些需要进一步研究的问题。 6 2 定性空问表示研究 2 定性空间表示研究 空间查询与分析是g i s 的核心，也是g i s 有别于其他信息系统的本质特征，空 间查询与分析的基础是空间关系。空间关系的描述与识别非常重要。方面它是 为g i s 数据库的有效建立、空间查询、空间分析、辅助决策等提供了最基础的关系， 另一方面是将空间关系理论应用于地理信息系统查询语言，形成一个标准的s q l 空间查询语言，从而通过应用程序进行空间特征的存储、提取、查询、更新等h 0 1 。 本章主要研究了几种主要的空间拓扑关系模型以及它们之间的关系，然后根 据人类认知给出了一种完备的定性空间关系表示模型_ h b m ，并证明了其完备 性以及表示能力。 2 1 空间对象和空间关系 空间表示与推理总是针对特定几何空间中的空间对象与对象间关系进行的。 本节给出空间对象以及空间关系的概念。 2 1 1 空间对象 空间对象是客观存在的地理实体在人类认识世界中的反映，它是人们对客观 世界的认知与抽象。基于不同的认识方法，可以得到空间对象的不同认识， 当我们以地理实体的类别来划分空间对象时，可以得到诸如道路、河流、山 脉等空间对象。如果我们以地理实体的形状来划分空间对象，可以得到点、线、 区域、体等类别的空间对象。 在g i s 应用中，地理对象通常表示为二维几何对象。因此，在本文中，我们主 要考虑二维空间对象的拓扑关系分类。 首先，我们基于点集拓扑来定义二维空间对象。点集的特征是集合，点是这 些集合的元素。基于此可将二维空间对象分为点、线、区域三类。下面给出三者 的具体定义： 定义2 1 ：点是没有空间尺度的表示空间位黄或该位置地理要素的空间对象。规定 其拓扑维数为0 。 基于点对象，可以定义其它空间对象： 定义2 2 ：线是连续映射f i 【o ，l 卜 豫2 的象，且满足：v t l ，t 2 e 0 ，1 】，当t l t 2 时，f ( t 1 ) f ( t 2 ) 。 线没有宽度，约定其拓扑维数为1 。特别，当坟0 声f ( 1 ) 时称为简单闭曲线。 定义2 3 ：简单区域指上品2 中规则的有界闭子集，且它的内部、外部均是连通的，边 界为简单闭曲线。规定它的拓扑维数为2 。简单区域在本文中简称区域。 有许多的地理实体可以被作为区域来考虑，如，湖泊、城市、种植同一种农作 重庆大学硕士学位论文 物的地块等。 本文以点、线、区域作为空间基本对象，即； 空间对象= 点，线，区域) 如果用p 、l 、a 分别表示点、线、区域，约定；点的边界a p 为空集，线l = f ( o ，1 】) 的边界为a l = f 【o ) ，f ( 1 ) ，区域的边界0 a 是闭曲线，维数为l 。 定义2 4 ：对象九的内部表示为九o ，定义为：九o = 九一孰 定义2 5 ：对象九的外部表示为圹，定义为：r = 埋l 一九 将空问对象与地理要素联系起来是g i s 与几何学的主要区别。本文采用g i s 中 关于空间对象的概念，但并不关心与对象关联的地理实体。 2 1 2 空间关系 空间关系是指地理实体间存在的一些具有空间特性的关系【3 “。空间关系形式 化模型的发展是空间推理、地理信息系统、计算机视觉等领域中的一个非常重要 的主题，越来越受到相关领域研究者的重视。空间关系对于在大型空间数据库中 进行空间检索以及在空间推理中推断新信息都是非常重要的【3 2 】。 在g i s 中，空间关系包括：度量关系、方位关系和拓扑关系等【7 】。度量空间关 系是用某种度量空间中的度量来描述的对象间的关系；方位空间关系是用来描述 对象在空间中的某种顺序的关系；拓扑空间关系是指拓扑变换下的拓扑不变量。 空间关系表示的基本任务是以数学或逻辑的方法区分不同的空间关系，给出形式 化的表示。其意义在于澄清不同用户关于空间关系的语义，为构造空间查询语言 和空间分祈提供形式化工具。 空间对象间的拓扑关系是空间中最基本的关系，构成了空间推理的基本方面， 一些研究者甚至指出，对象问的空间关系与对象本身同等重要，有关拓扑关系的 研究在空间推理中占有重要的地位。拓扑关系作为基本的空间关系，能够产生定 性差异，是定性空间推理研究的基本问题之一。 空闻关系表示方法分为3 类：定量表示、定性表示、定性与定量结合表示。定 量表示方法是目前g i s 系统中普遍采用的方法。g 1 s 中，通过空间坐标来定位空 间点对象，通过线段、多边形来表示线和区域。空间数据库通过点表、边表和多 边形表来表示点、线及区域间的关系。定量表示的特点是用代数与数值分析方法 进行空间信息分析和处理的基础。如，计算两个空间对象间的距离，计算空间对 象的面积或长度等。然而，大量的空间信息和复杂的空间关系仅用定量方式来描 述是不够的。 定性表示是使用非定量的方法和技术来对空间对象及空间关系进行描述的方 法。大量的空间对象及其关系要通过定量的方法来表示既不可能，也没有必要。 例如，要了解全国铁路分布时，用一张铁路示意图就可以了，而没有必要将每一 2 定性空间表示研究 条铁路的空间位置准确地给出；要确定两个行政区是否相邻时，没有必要将它们 的公共边界( 如果存在公共边界) 准确地给出。另一方面，对空间对象( 如，山脉、 海岸线1 的描述总是在一定程度上的近似表示，而不可能获得准确值。近年来，定 性表示越来越受到研究者的重视，这与空闽关系本质上是定性的陋j 认识枢一致。 定性表示是空间对象及关系描述在更高层次上的抽象。它以空间对象的本质特征 为主而忽略次要特征，以空间关系的主要方面为主而抛弃一些枝节的、对解决问 题不重要的关系。由于空间问题固有的复杂性和不确定性，空间关系的表示和推 理普遍采用定性的方法c 3 3 j 。定性表示获得的定性信息一方面可以满足一定的应用 需求，另一方面它为进一步更精细的定量表示和处理提供更可靠的候选集。将定 性表示与定量表示结合起来便成为定性与定量结合方法。 目前，空间对象拓扑关系的研究主要集中在两条主线上： ( 1 ) 确定性对象间拓扑关系的研究，主要体现在g i s 和空间推理的相关研究 中3 4 】； ( 2 ) 不确定对象的表示及其分析方法的研究。主要体现在地理分析、图像理 解和计算机视觉的相关研究当中1 3 ”。 对于确定性对象间拓扑关系模型，主要有基于逻辑的公理化拓扑理论和传统 的数学拓扑3 叼两大类方法，其中最有代表性的是r c c 形式化