（计算机应用技术专业论文）关于方向关系模型和查询的研究.pdf

哈尔滨理工大学工学硕士学位论文 关于方向关系模型和查询的研究 摘要 空间数据库是近年来的热点研究领域，是- l l 前沿的交叉学科。空间关 系的表示和处理在地图制图、计算机辅助设计、图像和多媒体数据库以及地 理信息系统等领域中有着广泛的应用，越来越引起人们的注意。空间关系主 要包括：拓扑关系、方向关系和距离关系。方向关系描述的是空间中对象之 间的顺序关系，是空间关系研究的重要领域。以往的文献主要集中于拓扑和 距离关系的研究，近年来方向关系得到了人们越来越多的重视。 空间关系是指空间对象之间具有某种空间特性的关系。空间对象之间的 方向关系是顺序关系中的一类，是空间中最基本的关系之一，构成了空间关 系研究的基本方面。方向关系描述的是空间对象之间在空间之中的相互排序， 一般使用方向性名词描述空间实体间的顺序关系。 本文主要研究了空间数据库中方向关系的两个方面：方向关系模型和方 向关系查询，归纳和比较了目前已经提出的理论和方法。本论文的主要贡献 如下： 1 深入分析和研究现有的方向关系模型，比较各种方向模型的优缺点， 针对其缺陷和不足之处，以及方向关系的特点和应用的需求，提出一种新的 方向关系模型一星形模型。该模型具有形式化、认知性、多尺度性、兼容性 等特点。 2 研究现有的方向关系查询，在新的方向关系模型中应用r 树索引，针 对应用的需求，给出一种基于r 树的方向关系查询方法。同时也给出了一种 基于方向关系矩阵的相似性计算方法，该方法改进了方向关系矩阵的形式化 表示，实现了矩阵距离不变条件下的相似性计算。 3 根据提出的新的方向关系模型和查询方法，搭建试验平台，研究其性 能以及特点理论分析和试验评估得出基于r 树的方向查询提高了效率。 关键词空间数据库：方向关系模型；方向查询；空间数据索引：方向谓词 哈尔滨理工大学工学硕士学位论文 1 i i 一一 i m 置昌暑昌宣鼻一 r e s e a r c ho nm o d e la n d q u e r y f o rd i r e c t i o n a lr e l a t i o n a b s t r a c t s p a t i a ld a t a b a s eh a sg a i n e dm o r ea n dm o r ea t t e n t i o n si nr e c e n ty e a r s ，i ti sa i n t e r d i s c i p l i n a r ys u b je c t s p a t i a l r e l a t i o n r e p r e s e n t a t i o n a n d p r o c e s s i o n i s i m p o r t a n ti nn u m e r o u sa p p l i c a t i o nd o m a i n ss u c ha sc a r t o g r a p h y , c o m p u t e r - a i d e d d e s i g n ，i m a g ea n dm u l t i m e d i ad a t a b a s e s ，s p a t i a la n dg e o g r a p h i ca p p l i l c a t i o n s s p a t i a lr e l a t i o n sm a i n l yi n c l u d et 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 n a lr e l a t i o na n d d i s t a n c er e l a t i o n d i r e c t i o n a lr e l a t i o nd e s c r i b e st h eo r d e rb e t w e e no b j e c t s i ti sa i m p o r t a n tr e s e a r c ha r e ao ns p a t i a lr e l a t i o n s b e f o r em o s tp a p e r s c o n c e n t r a t eo n t o p o l o g i c a lr e l a t i o na n dd i s t a n c er e l a t i o n d i r e c t i o n a lr e l a t i o nh a sg a i n e dm o r e a n dm o r ea t t e n t i o n si nr e c e n ty e a r s s p a t i a lr e l a t i o ni sar e l a t i o nw i t hs o m ep r o p e r t yb e t w e e ns p a t i a lo b je c t s d r e c t i o n a lr e l a t i o ni so n ek i n do fo r d e rr e l a t i o n s i ti sa l s oab a s i cr e l a t i o ni n s p a t i a lr e l a t i o n sa n dah o ta r e ao nr e s e a r c h d i r e c t i o n a lr e l a t i o n sd e s c r i b et h e o r d e rb e t w e e ns p a t i a lo b j e c t si ns p a c eu s i n gw o r d so nd i r e c t i o n s t h i sp a p e rm a i n l yr e s e a r c h e dt w oa s p a c t so fd i r e c t i o n a lr e l a t i o ni nd a t a b a s e ： d i r e c t i o n a lr e l a t i o nm o d e la n dq u e r y , g e n e r a l i z e da n dc o m p a r e dt h e o r i e sa n d m e t h o d sw h i c ha r ea c h i e v e d t h em a i nc o n t r i b u t i o n sa n dr e s u l t si n c l u d e di nt h e t h e s i sa r ea sf o l l o w s ： f i r s t l y , t h et h e s i ss u m m a r i z e sa n da n a l y s e sd i r e c t i o n a lr e l a t i o nm o d e l s w h i c he x i s t e ds of a r , c o m p a r e st h ea d v a n t a g e sa n dd i s v a n t a g e sa m o n ga l lk i n d s o fd i r e c t i o n a lm o d e l s ，a n dt h e np r e s e n t san e wd i r e c t i o n a lr e l a t i o nm o d e l - - s t a r - b a s e dm o d e la c c o r d i n gt ot h e i rd e f e c t s ，f e a t u r e so fd i r e c t i o n a lr e l a t i o na n d r e q u i r e m e n t s o f a p p l i c a t i o n s t h i sm o d e lh a ss o m ep r o p e r t i e s ，s u c ha s f o r m a l i z a t i o n ，c o g n i t i o n ，m u l t i s c a l e ，c o m p a t i b i l i t ya n ds oo n s e c o n d l y , d i r e c t i o n a lq u e r i e st h a th a v eb e e ng i v e na r es t u d i e d an e w m e t h o db a s e do nr t r e ef o rd i r e t i o n a lq u e r yi ap r o p o s e db yc o m b i n i n gw i t ht h e n e wd i r e c t i o n a lr e l a t i o nm o d e la n dr e q u i r e m e n t so fa p p l i c a t i o n s a tt h es a m e t i m e ，ac a l c u l a t i o nf o rs i m i l a r i t yb a s e do nd i r e c t i o n a lm a t r i xi sg i v e n t h e i i 哈尔滨理工大学工学硕士学位论文 一。iiii昌皇暑暑皇皇詈置兽皇一 m e t h o di m p r o v e sd i r e c t i o n a lr e l a t i o nm a t r i xf o rf o r m a l i z e dr e p r e s e n t a t i o n ，a n d i m p l e m e n t sc a l c u l a t i o nf o rs i m i l a r i t yo nt h ec o n d i t i o nt h a tt h ed i s t a n c ei s c o n s t a n tf o rt h ed i r e c t i o n a lr e l a t i o nm a t r i x t h i r d l y , a tl a s tt h ee x p e r i m e n tp l a t f o r mi sb u i l tu pb a s e do nt h en e w d i r e c t i o n a lr e l a t i o nm o d e la n dt h en e wm e t h o df o rd i r e c t i o n a lq u e r y , a n dt h e nt h e p e r f o r m a n c ea n dt h ef e a t u r ea r ep r o b e d t h et h e o r ya n a l y s i sa n de v a l u a t i o nb a s e d o ne x p e r i m e n tp r o v et h a td i r e c t i o n a lq u e r yb a s e do nr t r e ei m p r o v e se f f i c i e n c y k e y w o r d ss p a t i a ld a t a b a s e ，d i r e c t i o n a lr e l a t i o nm o d e l ，d i r e c t i o n a lq u e r y , s p t i a l d a t ai n d e x ，d i r e c t i o n a lp r e d i c a t e m - 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文 ：关于方向关系模型和查询的研 究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研究 工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰 写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以明确方 式注明。本声明的法律结果将完全由本人承担。 作者签名： 王她 日期： 即艿年弓月i oe l 哈尔滨理工大学硕士学位论文使用授权书 关于方向关系模型和查询的研究系本人在哈尔滨理工大学攻读硕士学位 期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所 有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工大 学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文和电子 版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、缩印或 其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密团。 ( 请在以上相应方框内打4 ) 作者签名： 一多6 b 丈义名 导师签名：蒡似芬 日期：聊万年弓月i o 日 日期：谚 年多月，日 哈尔滨理j t 大学工学硕上学位论文 第1 章绪论 1 1 课题研究的背景及意义 空间数据库是近年来的热点研究领域，是一门前沿的交叉学科。空间关系 的表示和处理在地图制图、计算机辅助设计、图像和多媒体数据库以及地理信 息系统等领域中有着广泛的应用，越来越引起人们的注意。空间关系主要包括： 拓扑关系，方向关系和距离关系。方向关系描述的是空间中对象之间的顺序关 系，是空间关系研究的重要领域。以往的文献主要集中于拓扑和距离关系的研 究，近年来方向关系得到了人们越来越多的重视。 1 1 1 空间数据库研究的背景 空间数据是用于表示空间物体的位置、形状、大小和分布特征等方面信息的 数据，适用于描述二维、三维和多维分布的关于区域的现象。空间数据的特点 是不仅包括物体本身的空间位置及状态信息，还包括表示物体的空间关系的信 息。属性数据为非空间数据，用于描述空间物体的性质，对空间物体进行语义 定义。 空间数据库系统则是描述、存储和处理空间数据及其属性数据的数据库系 统。空间数据库是随着地理信息系统的开发和应用而发展起来的数据库新技术。 目前，空间数据库系统尚不是独立存在的系统，它与应用紧密结合，大多数作 为地理信息系统的基础和核心的形式出现。 空间数据库的研究始于2 0 世纪7 0 年代的地图制图与遥感图像处理领域，其 目的是为了有效利用卫星遥感资源迅速绘制出各种经济专题地图。由于传统数 据库在空间数据的表示、存储和检索上存在许多缺陷，从而形成了空间数据库 这一新的数据库研究领域。它涉及计算机科学、地理学、地图制图学、摄影测 量与遥感、图像处理等多个学科。 目前，以空间数据库为核心的地理信息系统的应用已经从解决道路、输电线 路等基础设施的规划和管理，发展到更加复杂的领域，地理信息系统已经广泛 应用于环境和资源管理、土地利用、城市规划、森林保护、人口调查、交通、 地下管网、输油管道、商业网络等各个方面的管理与决策。例如，人们研制了 哈尔滨理工大学工学硕士学位论文 许多国土资源管理信息系统，洪水灾情预报分析系统以及地理信息系统g i s 软 件产品。 1 1 2 方向关系研究的重要性 空间关系是指空间对象之间具有某种空间特性的关系，主要分为拓扑关系、 顺序关系和度量关系三大类。空间对象之间的方位关系是顺序关系中的一类， 是空间中最基本的关系之一，构成了空间关系研究的基本方面。方向关系描述 的是空间对象之间在空间之中的相互排序，一般使用方向性名词描述空间实体 问的顺序关系。方位关系在空间关系研究中占重要地位。 对空间方向关系的研究意义，从目前来讲主要可以概括为以下几点： 1 空间关系理论完整性的需要空间方向关系理论是空间关系理论体系中 不可缺少的重要组成部分n 。缺少了空间方向关系理论，就无法对空间关系进行 完整而准确的描述。拓扑关系，方向关系和距离关系只有密切结合，协同工作， 空间系统才能达到最佳的效果，才能组成空间关系的完整体系。空间方向关系 为空间分析研究提供了一个重要的参数，丰富了空间分析的方法，增加了空间 分析的手段。方向关系的合理定义与描述能够为空间关系模型的建立、表达与 分析提供前提条件。 2 空间查询的需要方向是日常生活中常用的一个普通的空间概念。方向 经常作为空间查询的选取条件，以找到满足人们查询需要的对象。现在的地理 信息系统应用中，其查询功能大部分是基于拓扑和距离关系的查询，基于方向 关系的查询功能很少涉及到。 3 空间推理的需要空间推理是是从已知的空间关系推导出新的空间关 系，这有利于在给定的空间关系中检测可能的不一致性，预处理空间关系，对 需要搜索的空间进行剪枝，从而提高空间查询效率。基于方向关系推理的研究 基本上还处于尝试和探索阶段。 4 新一代g i s 研制的需要新一代g i s 的一个显著特征是语音功能的增加， 表现为用户通过规范化的自然语言的输入，进行满足需要的空间查询，分析等 等操作，同时g i s 能够以友好的方式与用户进行直接的语言交流。 综上所述，对空间方向关系进行研究是十分必要。 1 1 3 方向关系的特征 方向关系受到空间数据组织、空间认知等影响，具有尺度、认知、层次、 哈尔滨理工大学工学硕士学位论文 不确定性、形式化等几个特征【2 1 。 1 尺度特征空间方向关系是空间对象之间的顺序关系，而空间对象是有 尺度特征的，因此方向关系是有尺度特征的。这种尺度特征表现在：在一个较 大的尺度下，对象表现为一个多边形；而在一个较小的尺度下，表现为一个点。 因此在不同的尺度下所研究的对象的表现形式是不同的。虽然在较大的尺度下， 研究的是面之间的方向关系，在较小的尺度下，研究的是点之间的方向关系， 但是它们之间的关系是相同的。 2 认知特征空间方向关系直接反映了人们对空间方向关系概念的理解。 不同的人对方向关系具有不同的认识和理解。比如说有人把某个方向可能理解 为一条线，也有人把它认为是一个区域，该区域有可能是三角区域，也有可能 是矩形区域。因此在研究方向关系的时候，一定要具有良好的认知和表达能力。 既能正确地理解表达和理解用户的输入，又要按照符合认知要求的形式输出。 用户和g i s 之间要有一致而友好的接口，其中的方向关系概念要与人们的认知 概念相一致。基于自然语言的方向关系处理是人们认知习惯和空间关系相结合 的典范。 3 层次特征层次特征主要表现为两个方面：一是语义引起的层次性：另 一个是空间对象引起的层次性。语义的层次性主要体现在语义的分辨率上。如 语义上比较弱的北，即语义层次更高，更抽象的北可以包括语义上比较强的北、 西北、东北，即语义层次上更低，更具体的北、西北、东北。空间对象也是有 层次性的。层次性可以用一个树的结构来表示。树根是最高层次，最抽象，最 模糊。树的叶子节点是最低层次，最具体，最清楚。对空间对象来说，树根就 是一个总的空间，叶子就是各个原子对象，中间节点就是由原子对象组成的复 合对象。 4 不确定性特征不确定性表现出了现实空间的复杂性，主要有几个因素 引起的：一是认知具有不确定性。比如说人们对方向关系具有不同的理解，从 而造成了对方向关系的认识模糊，无法统一方向到底是一条线呢还是一个区域。 二是空间数据的不确定。如空间数据的表达不一致。三是应用需求的不确定。 不同的应用需求导致方向关系具有不同的表达和表现形式。 5 时间特征时间特征表现为随着时间的不断变化，对象之间的位置在不 断的改变，引起了对象之间的方向关系也会不断随之改变。研究时空对象的方 向关系有利于扩展g i s 对时间的建模能力，满足不同用户和管理的需求。 6 形式化特征形式化特征主要是根据尺度、认知、层次、不确定性和时 间性来确定的，是空间表达和推理的要求。方向关系必须形式化以方便方向关 哈尔滨理工大学工学硕士学位论文 系的处理。 7 可推理性特征可推理性特征是指可以从一个已知的方向推导出未知的 方向，增进智能性，同时为查询提供逻辑条件。 8 完备性特征方向关系表达模型能够表达空间对象所有的方向关系。 9 通用性特征通用性特征是指能够处理多尺度、不同层次下的对象，兼 容多种模型。 1 2 国内外研究概况 研究方向关系可以从两个角度进行：一个是数学角度研究；另一个是从语 言和认知角度研究乜1 。从数学角度出发，可以对方向关系建立形式化的模型，对 概念进行严格的定义，进行有效的查询和推理分析。从语言和认知的角度研究 出发，研究如何建立一个友好而自然的人机接口，进行直接顺畅的交流。这两 个角度有互斥性，但是不能把它们孤立起来分别对待，应该有机的结合起来， 为新一代g i s 的研制提供条件。 1 2 1 从语言与认知角度研究方向关系 认知主要是研究方向关系与人们认知之间的关系。人们的认知思维习惯和 方式、自然语言的表达特征和表现等等对空间方向关系概念的定义和划分、方 向模型的建立，空间方向推理规则的制定，空间方向的查询策略等等具有重要 的影响，是进行方向关系研究的基础。 1 2 2 从数学角度研究方向关系 从数学角度研究主要包括形式化表达、建模、查询、推理和相似性计算。 1 2 2 1 空间方向关系表达空间方向关系表达的主要目的是建立空间对象与所 对应的空间之间的方向关系映射。通过映射，任何空间对象之间的方向关系都 可以用一个词语、句子或者符号表达式来表达。映射的结果必须与认知思维习 惯和方式接近，同时还要考虑到方向关系的形式化，可推理性等特征。 1 2 2 2 基于方向关系的建模方向关系模型在地理信息系统的可视化接口中非 常重要。同时它也是方向关系查询、推理、相似性评估的基础。 方向模型是建立在参考框架之上的。参考框架有三种口1 ：1 内在型2 直接 型3 外在型。 哈尔滨理工大学t 学硕士学位论文 方向模型按照性质划分，分为两种：定量方向模型和定性方向模型。定性 方向模型接着细分又可以分为：点对象之间的定性方向模型和扩展对象之间的 方向模型。目前主要有三种类型的点对象之间的方向模型：基于锥形的方向模 型h 1 ( c o n e - b a s e d ) 、基于投影的方向模型啼1 ( p r o j e c t i o n - b a s e d ) 以及双十字模型柚1 。 郭庆胜等人提出了一种融入方向关系矩阵模型思想的改进型锥形模型h 1 。该模型 同时具备了两者的优点，尤其对多尺度空间目标的空间方位关系的表达比较有 效，并顾及到了多尺度的包容性。扩展对象之间的方向模型主要有：1 三角模型 伫1 2 二维串模型阻3 符号阵列模型扫4 最小边界矩形模型n 5 方向关系矩阵模型 n 6 v o r o n o i 图模型n 羽。 在这些原始模型的基础之上，很多学者又针对各种模型提出了改进。b o w o n k i m 等人提出了2 d + 掣”1 ；g o y a l 又提出了一种深度方向关系矩阵，用于场景的 相似性计算n 劓。闫浩文等人运用认知心理学信息加工的观点，建立了基于v o r o n o i 图的空间方向关系形式化描述模型n 埔1 ；杜世宏等人提出了一种能够表达与参照 对象外接矩形内部有关信息的细节方向关系表达模型n l 埔1 ；谢琦等人基于区间值 及其运算性质给出了不确定区域间方向关系的表示及推理方法n 鲫；邓敏等人研 究了空间目标间方向关系的统计建模方法，提出一种统计模型：他以点点空 间方向关系的计算量为基础，在综合考虑空间目标的几何构成和分布关系后， 又提出了定量化演算空间方向关系的一种新模型乜；为了更细致、准确地描述 方向关系，曹菡等人提出一种方向关系描述的分层多级处理方法，在以点、线、 面为参照目标的空间目标间建立方向关系描述的3 层模式结构，每层模式又由 基本方向关系描述、推理模型和方向关系描述、推理细化模型组成，从而扩展 了方向关系的描述n 2 瑚1 ；冯玉才等人也对方向关系模型进行了研究1 ；谢琦等人、 还有夏宇等人介绍了近年来空间对象的方向关系形式化模型的主要研究内容、 研究方法和研究进展，对已有的方向关系模型做了比较，并探讨了目前存在的 问题和今后的发展方向( 2 5 , 2 6 o 现有的这些模型都是针对具体的应用需求建立的，具有针对性的。要么是 定量的，要么是定性的，要么只适用于点对象，要么只适用于扩展对象。没有 哪个模型具有良好的兼容性和通用性，既能进行定量的方向表达，又能定性的 方向表达，同时既适用于点对象又适用于扩展对象，而且能够在多尺度下良好 地表达方向关系，还能够兼容现有的各种方向关系描述模型。 1 2 2 3 基于方向关系的查询总结先前的文章，基于方向关系的查询可以归结 为两种方法第一种方法注重于过滤空间对象来消除错误命中，得出一组候选 对象，然后对候选对象进行提炼，找到满足要求的对象。通过使用m b r ( m i n i m u m 哈尔滨理工大学工学硕士学位论文 b o u n d i n gr e c t a n g l e ，简称m b r ) 过滤和使用比m b r 更精确的近似过滤，是该种 方法的典范。该种方法可以使用索引结构进行快速的查询，适用于点和区域对 象。p a p a d i a s 等人论述了如何使用r 树的方法进行方向关系的存储和查询乜7 1 ； x u a nl i u 、s h e k h a r 等人研究了基于对象的方位查询处理方法，提出一种全新的 基于模型的开放策略，使得查询时不必知晓嵌入式世界坐标系的边界，同时省 去了与坐标边界相关的计算问题，以o s s 为模型的查询算法，通过提高传送效 率来减少i o 和c p u 的开销汹1 ；肖予钦等人研究了基于r 树的方向关系查询处 理方法，定义了四元组模型表示对象m b r 间的方向关系，提出了基于r 树的处 理方向关系查询过滤( f i l t e r ) 步骤的方法，并将提炼( r e f i n e m e n t ) 步骤细化为3 种 不同的操作，所提出的方法能够高效处理任意对象间的方向关系查询啪1 ：孙海 龙等人给出了一种基于m b r s 表示空间对象之间的方向关系以及基于r 树对方 向关系进行检索的方法洲。第二种方法是使用元数据，例如2 d + 串n 别。该方法 比较适用于推理，但计算复杂，实现起来比较困难，无法有效的应用索引。 由于空间数据库中的数据量很大，而且是多维的，因此空间数据库查询的开 销一般要比关系数据库大，特别是查询语句的条件谓词中包含一些对空间数据 操作的函数，计算这些函数的开销远比数值或字符串的比较要大。如果用顺序扫 描的方法查询，则效率非常低。因此，为了提高查询效率，采用空间索引是十分必 要的。空间数据的快速索引是实现海量数据管理的关键技术之一。空间数据索 引方法的采纳与否以及索引性能的优劣直接影响地理空间数据库的整体性能。 目前所提出的空间索引数据结构，可概括为树结构、线性映射和多维空间 区域变换三种类型。从应用范围上可分为静态索引和动态索引。由于空间数据 的多维性，人们已经提出了多种多维索引技术。这些多维索引技术包括b a n g 文 件、网格文件m 、l a b 树1 、k d b 树1 、p a r a m i d 树m 1 、四叉树m 1 、r 树 、 r + 树汹1 、r 树侧、t v 树和v a 文件。这些索引主要是用来对点的集合进行索 引。能够同时处理区域数据和点数据的索引结构包括区域四叉树、r 树和s k d 树。 1 2 2 4 基于方向关系的推理方向关系关系的推理在方向关系研究中占有重要 地位。在地理信息系统中，方向与距离相结合可以推理出物体的位置关系，方 向也可以与拓扑相结合推理出物体的形状。空间方向推理可以从已知的方向推 导出未知的新方向，有利于在给定的空间关系中检测出可能的不一致，预处理 空间查询，对需要搜索的空间进行剪枝，从而提高空间查询的效率。 p a p a d i a s 等人给出了两种类型的推理：第一种使用层次中祖先区域的关系， 第二种是基于空间关系的合成以及路径的一致性h ；s p i r o ss k i a d o p o u l o s 和 哈尔滨理工大学工学硕士学位论文 m a n o l l i sk o u b a r a k i s 研究了( 3 0 y a l 和e g e n h o f e r 提出的关于主方向的定性空间推 理模型，对g 0 y a l 和e g e n h o f e r 的表示进行了补充，给出了两个主方向关系的的 合成操作池1 ：刘永山等在方向关系矩阵的基础上，深入研究了原子方向关系的 合成m 1 ；他还利用区间代数及矩形代数理论，以物体的最小外接矩形m b r 为模 型，提出了一种基于m b r 的主方向关系与矩形代数关系相结合的推理方法1 ； 杜世宏给出了g i s 中由多种方向关系推理拓扑关系的方法m 1 ：吴静提出了四种情 况下基于1 个参照系的定性方向关系推理方法1 。 1 2 2 5 基于方向关系的相似性评估空间场景的相似性包含了场景几何结构相 似性及语义相似性。基于方向关系的相似性评估就是使用方向关系捕捉空间对 象的分布，通过多分辨率模型，允许从不同尺度和不同层次上度量空间结构的 相似性。而语义相似性是通过特征类的语义网来评价的。一个复杂的空间场景 中的多个不同类型对象之间存在多类型和多层次的空间关系。因此相似性评估 是必要的。相似性评估在大型的图像和多媒体数据库中经常被使用。现有的相 似性评估方法有：基于深度方向关系矩阵的相似性评估n 劓，基于栅格数据的面 状目标空间方向相似性评估“ 等等。 1 3 课题的来源及研究内容 1 3 1 课题的来源 本课题来源于黑龙江省自然科学基金项目：f 2 0 0 6 0 1 。 1 3 2 课题的研究内容 本课题主要对空间数据库中的方向关系模型和方向关系查询进行深入的研 究。 1 深入分析和研究现有的方向关系模型，比较各种方向模型的优缺点，针 对其缺陷和不足之处，以及方向关系的特点和应用的需求，提出一种新的方向 关系模型一星形模型。 2 研究现有的方向关系查询，在新的方向关系模型星形模型中应用r 树索引，针对具体的应用需求，给出一种基于r 树的方向关系查询方法。同时 也给出了一种基于方向关系矩阵的相似性计算方法，用于图像数据库中的相似 哈尔滨理工大学工学硕士学位论文 性检索查询。 3 根据提出的新的方向关系模型和查询方法，搭建试验平台，研究其性能 以及特点。 哈尔滨理工大学工学硕士学位论文 第2 章方向关系模型 2 1 方向关系模型简介 2 1 1 基本概念 定义2 1 模型：是对现象、实体对象、过程、状态等的模拟表达。 定义2 2 基于目标对象的模型：将空间信息划分为实体对象集，每一个实 体对象都是可辨析的、有意义的、有属性描述的。 定义2 3 空间特征：是应用领域的概念，是所要处理的空间对象所具有的 特征，如定位、大小、位置等。 定义2 4 图形特征：是其表征，从空间特征到图形特征要经过抽象和概括。 定义2 5 空间参考对象：空间中所要处理的对象，如建筑、河流、湖泊等。 定义2 6 空间对象：空间中所有处理的实体对象，一般被抽象为点、线、 多边形等。 定义2 7 欧式空间( e u c l i d e a n ) ：能实施通常的长度、方位运算的空间表 达为坐标元组集合。 欧式空间的对象种类如下图2 1 所示： 图2 - 1 欧式空间的对象类型 f i g 2 - 1o b j e c tt y p e si ne u c l i d e a ns p a c e 2 1 2 方向关系模型的分类 方向关系模型是非常重要的，是描述空间对象之间方向关系的基础。谢琦 哈尔滨理工大学工学硕士学位论文 等人把方向关系模型划分为两大类1 ：1 确定性对象之间的方向关系模型2 不 确定对象之间的方向关系模型( 主要针对区域而言) 。夏宇等人把方向关系模 型划分为三类啪1 ：1 锥形模型2 投影模型3 v o r o n o i 图模型。 本文从方向关系模型的性质和研究对象的类型进行分类。方向关系模型按 照性质划分，分为定量方向模型和定性方向模型。按照所处理的对象类型划分， 分为点对象之间的方向模型和扩展对象之间的方向模型。目前主要有三种类型 的点对象之间的方向模型：1 基于锥形的模型( c o i i e b a s e d ) 2 基于投影的模型 ( p r o j e c t i o n - b a s e d ) 3 双十字模型。扩展对象之间的方向模型主要有：1 三角模型 2 二维串模型3 符号阵列模型4 最小外接矩形模型5 方向关系矩阵模型 6 v o r o n o i 图模型。 现有的这些模型都是针对具体的应用需求建立的，具有针对性的。要么是 定量的，要么是定性的，要么只适用于点对象，要么只适用于扩展对象。没有 哪个模型具有良好的通用性，既能进行定量的方向表达，又能定性的方向表达， 同时既适用于点对象又适用于扩展对象。 2 1 3 参考框架 描述方向关系的三要素是参考对象、目标对象和参考框架。方向是一个二 元关系，用来记录两个对象之间的有序关系。比如空间中有两个对象a 和b ， a 是参考对象，b 是目标对象。方向的第三部分就是参考框架，把方向符号赋 给空间分区。在讨论方向关系时，为了使方向有意义，首先必须建立一个参考 框架。如果参考框架改变了，方向也要改变。一般有三种类型： 1 内在( i n t r i n s i c ) 参考框架内在参考框架是相对于一个目标对象的定向 而言的。比如，一座大楼的前或者后，左或者右，大楼的前面是由主要入口或 者其主面所决定的。 2 直接( d e i c t i c ) 参考框架直接参考框架是相对于每一个观察个体而言的， 也就是基于观察者的观测点把空间划分为四个方向区域：前、后、左、右。比 如，对于自己来说某目标对象是在前面，但是对于其他人来说该目标对象可能 在其左边。 3 外在( e x t r i n s i c ) 参考框架外在参考框架是独立于目标对象的定向和观 察者而建立的，是以地球的极轴位置定义的。比如，东、南、西、北。 哈尔滨理工大学工学硕士学位论文 2 2 定量方向关系模型 定量方向关系模型是使用准确的值对空间对象之间的方向关系进行表示。在 地理应用中，目标点的方向一般是使用方位角相对于参考点来定义的。方位角 是穿过目标点a 的南北垂直线和从点o 到目标点b 的射线之间的角( 如图2 - 2 所示) 。对于垂直线上朝北的所有点相对点o 来说，方向值都是o 。对于所有 的点来说，方位角是从垂直线的北面部分沿顺时针测量的，位于半开的区间 o 。，3 6 0 。) ( 见公式2 一1 ) 。大于3 6 0 。的角以循环的方式映射到区间上。例如 3 6 0 。映射为0 。，4 5 0 。映射为9 0 。 o s 图2 2 方位角 f i g 2 - 2t h ea z i m u t ha n g l e 口；t a n 一x s - x o ( 2 1 ) y 8 一y o 两个点之间的定量的方向使用方位角记录，在应用中它们的值可以以合适 的分辨率来近似。例如b 相对于o 的方位角可能是4 5 0 2 0 1 0 。象土地勘查和机 械设计这样要求精确性较高的应用使用定量方向。然而，对于精确性要求不高 的空间应用可以使用定性的方向，而不是定量的方向。 2 3 定性方向关系模型 定性方向是比定量方向粗糙的方向的近似，使用比定量方向更少的一组符号 描述。典型的是，区间 0 。，3 6 0 。) 被划分为四个或者八个方向区间，每个区间 使用合适的方向术语。四方向的系统使用基本方向北、东、南、西，八方向的 系统使用基本方向和第二组方向东北、东南、西南、西北。相比定量方向来说， 人们更喜欢定量方向，因为定性方向是他们经常需要的，大部分人在头脑中不 能够计算出象t 锄。1 这样的三角表达式1 。 ， 哈尔滨理工大学工学硕士学位论文 2 4 点对象之间的方向关系模型 在小比例尺下，对象一般是作为点来处理的。点对象模型主要用来描述点 对象之间的方向关系。目前比较有代表性的点对象之间的方向关系模型有锥形 模型、投影模型、双十字模型以及它们的改进型。 2 4 1 基于锥形的方向模型 基于锥形的模型把一个参考点周围的空间划分为四个( 如图2 - 3 ( a ) ) 或者八 个( 如图2 - 3 ( c ) ) 9 0 。或者4 5 。彼此互斥的区域。四方向锥形模型使用四个定性 方向：北( n ) 、东( e ) 、南( s ) 、西( w ) ，而八方向锥形模型则使用八个定性方 向：北( n ) 、东( e ) 、南( s ) 、西( w ) 、东北( n e ) 、东南( s e ) 、西南( s w ) 、西北 ( n w ) 。两个方向分区之间的边界是由模型系统分配的，如把边界逆时针分配。 比如，北和东之间的边界在四方向锥形模型中分配给北分区，东和南分区之间 的边界分配给东分区。 如果目标对象同参考对象是重合的，它们之间的方向被称为同一。包括同 一方向在内，四方向锥形模型可以识别出五个方向，八方向模型能够识别出九 个方向。目标点对象相对于参考点对象的方向是由目标所在的方向分区决定的。 例如在四方向描述模型中d i r ( o ，b ) = s ( 如图2 3 ( a ) ) ，而在八方向描述模型中 d i r ( o ，b ) = s e ( 如图2 - 3 ( c ) ) 。 sd ( a ) 四方向模型 ( a ) f o u r - d i r e c t i o nm o d e l w o 、。 ( b ) 四方向模型中的错误描述( c ) 八方向模型 ( b ) e r r o ri nf o u r - d i r e c t i o nm o d e l( c ) e i g h t - d i r e c t i o nm o d e l 图2 - 3 锥形模型 f i g 2 - 3t h ec o n e b a s e dm o d e l 由于锥形模型是把目标对象抽象为一个点，忽略了空间对象的形状和大小 对方向关系的影响。当空间目标对象之间的距离相对于自身大小的比例失调时， r 就会出现错误的方向描述，如上图2 - 3 ( b ) 所示。如果按照人的直觉来说，b 相 对于o 是在东面，但是使用四方向模型描述时，b 相对于o 是在南面。八方向 哈尔滨理工大学工学硕士学位论文 模型相对于四方向模型来说，把空间平面划分的更加精细，所以可以更精确的 描述方向关系。八方向模型与四方向模型的思想是一样的，因此当空间对象之 间的距离相对于自身的大小相差太大时，同样会出现四方向模型那样描述错误 的情况。因此，四方向和八方向锥形模型比较适合描述点对象之间的方向关系， 以及空间对象之间的距离远大于参考对象自身大小的方向关系，但相对于距离 较小的情况就可能出现错误的描述和判断。 四方向描述模型对北、东、南、西方向的描述与人们的认知习惯比较相似， 但缺少东北、东南、西南、西北方向的描述，如果使用四条线作为东北、东南、 西南、西北方向的话，尽管符合认知习惯，但是不符合认知理解。八方向具有 八个方向，符合认知习惯，但是认知理解也不尽然。 2 4 2 基于投影的方向模型 基于投影的方向模型使用穿越参考点的水平和垂直线划分空间。水平线把 空间划分为北和南两个半平面( 如图2 - 4 ( a ) ) ，而垂直线把空间划分为东西两个 半平面( 如图2 - 4 ( b ) ) 。水平线和垂直线一起把空间平面划分为四个象限：西北， 东北，东南，西南( 如图2 4 ( c ) ) 。四象限的参考框架包含四个方向区域，四条 线和一个点。四个象限区域是第二方向：东北、东南、西南、西北。四条方向 线是基本方向：北、东、南、西。同一方向是与参考点重合的点方向。 s w ( a ) 南北半平面( b ) 东西半平面( c ) 九方向模型 ( a ) n o r t h s o u t hh a l fp l a n e s ( b ) w e s t - e a s th a l fp l a n e s( c ) n i n e - d i r e c t i o nm o d e l 图2 - 4 投影模型 f i g 2 - 4t h ep r o j e c t i o n - b a s e dm o d e l 基于投影的模型与锥形模型相比有几个优点： 1 地球上的经度和纬度线的结构是同基于投影的模型是一致的。 2 相比锥形模型，投影模型能产生大量精确的合成推理。 3 由于方向区域的矩形本质，投影模型在空间数据库中比锥形模型更容易 实现。 哈尔滨理工大学工学硕士学位论文 另一方面锥形模型对于定性方向来说更容易按比例增加，如1 6 或者3 2 方 向。投影模型对空间平面的划分与锥形模型一样有合理的地方也有不合理的地 方。投影模型对东北、东南、西南、西北的区域划分比较合理，但是北、东、 南、西仅仅是一条线，与人们的认知理解完全不符。但是投影模型可以基于欧 式空间进行比较精确的方向计算。 2 4 3 基于双十字的方向模型 双十字模型更精确地说应该是描述一个点相对于一条线的方向模型。由两 条平行线和一条垂直线把空间平面划分为1 5 个方向关系，其中有2 个点、7 条线 和6 个区域( 如图2 - 5 ( a ) ) 。一个点可以是相对于一条线的1 5 个不同的定性位置 中的任何一个，这些关系可以使用图标表示，如下图2 - 5 ( b ) 所示。 ( a ) 不同的定性位置( b ) 关系的图标表示 ( a ) d i s t i n c tq u a l i t a t i v ei o c a t i o i l s( b ) i c o n i cr c p r c s i o n t a t i o n so nr e l a t i o n s 图2 = 5 双十字模型 f i g 2 - 5t h