定性空间方向关系建模中若干问题研究

论文摘要

空间关系能够描述客观世界的空间信息,是解决许多理论与实际问题的关键。空间关系建模是人工智能的重要研究内容,在地理信息系统、机器人导航、图像理解领域有着广泛的应用。方向关系是最基本的空间关系之一,能够描述空间对象间的相对位置信息。目前空间方向关系建模已取得很大进展,但仍存在一些问题：现有研究多集中于模型的表示方面,推理方面研究较少；对空间方向关系运算性质的研究不够深入,其中基本主方向关系的逆运算性质仍是一个有待解决的开放问题；此外现有模型多针对简单空间对象,难以处理复杂空间对象（不连通、带洞、具有不确定边界）间的方向关系,不确定区域间方向关系的表示模型、基本运算性质、推理方法以及推理复杂性等方面的研究尚处于起步阶段。本文采用定性研究方法,针对确定区域间基本主方向关系的逆运算、不确定区域间方向关系的表示与推理等问题展开研究。对现有定性空间关系模型进行分析和总结,在此基础上利用SK模型和MBR模型提出一种确定基本主方向关系的逆关系的方法；用宽边界模型表示带有不确定边界的复杂区域,利用区间代数和矩形代数分析不确定区域间方向关系的复合运算,进而提一种MBR宽边界方向关系复合推理方法；分析不确定区域间方向关系自身所蕴含的约束信息,提出一种不确定区域间方向关系约束的相容性判定算法。本文的主要贡献、研究思路和研究结果如下：（1）定性空间方向关系建模论述空间关系建模的研究背景和意义,介绍几种主要空间关系的基本概念和研究现状；然后以定性空间方向关系研究为主线,分别从简单对象间方向关系和不确定对象间方向关系两方面,着重对现有空间方向关系建模研究的现状进行分析与总结,最后讨论了目前空间方向关系建模研究所存在的问题。（2）定性空间方向关系演算介绍了定性空间方向关系推理中三种重要的关系代数：区间代数、矩形代数、主方向关系代数。论述了三种关系代数的研究意义和现状；分别给出三种关系代数的基本定义以及基本关系运算（着重介绍了其中的交、并、逆、复合运算）。（3）基本主方向关系的逆关系研究研究了基本主方向关系的逆关系这一开放问题。首先基于模型SK和MBR提出一种四元组表示模型,将任意一个基本主方向关系R转换成其对应的四元组,称该四元组为R的位置,记为loc（R）;然后分析了R与loc（R）, loc（R）与loc-1（R）以及loc-1（R）与inv（R）间的对应关系；在此基础上提出一种确定基本主方向关系的逆关系的方法。该方法能够确定包括单片、多片和矩形关系在内的所有基本主方向关系的逆关系。（4）基于MBR的不确定区域间方向关系建模研究讨论了导致空间关系不确定性的各种原因；介绍了不确定空间方向关系建模研究现状,并指出了存在问题。提出了一种基于MBR的不确定区域间方向关系建模方法,该方法采用宽边界统一表示区域的不确定边界,将矩形代数的良好计算性质应用于不确定区域间MBR主方向关系的表示与推理中,定义MBR宽边界方向关系用以表示不确定区域间的方向关系；给出MBR宽边界方向关系间相容性复合的定义；基于矩形代数提出一种复合运算方法,并形式化证明其正确性。（5）不确定区域间方向关系推理方法研究提出了一种不确定区域间方向关系的推理方法。对提出的MBR宽边界方向关系模型进行扩展,定义了宽边界方向关系用以描述不确定区域间的方向关系,更符合人们对方向关系的认知；基于基本主方向关系的形式化定义,分析并证明宽边界方向关系自身蕴涵的约束规则；定义宽边界方向关系的复合,给出一种基于复合运算的不确定区域间方向关系推理方法,并证明了该方法的正确性。（6）不确定区域间方向关系相容性检测方法介绍空间约束满足问题的基本概念和研究现状；定义宽边界方向关系约束,讨论了宽边界方向关系约束集合的相容性问题；分析了宽边界约束和确定区域间方向关系约束之间的转换规则,从而将基于宽边界方向关系的约束满足问题转换为基于确定区域间方向关系的约束满足问题；基于路径相容算法,提出一种基于宽边界方向关系约束的相容性算法BBD-CON,并分析了算法的复杂度。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 空间关系建模
• 1.1.1 空间关系建模的定量与定性方法
• 1.1.2 定性空间关系表示模型
• 1.1.3 定性空间关系推理模型
• 1.1.4 定性空间关系建模现状
• 1.2 定性空间方向关系模型
• 1.2.1 确定空间方向关系模型
• 1.2.2 不确定空间方向关系模型
• 1.3 存在问题
• 1.4 论文的研究目标与技术路线
• 1.4.1 研究目标
• 1.4.2 研究内容与技术路线
• 1.4.3 内容安排
• 1.5 本章小结
• 第2章 空间方向关系演算
• 2.1 引言
• 2.2 区间代数
• 2.2.1 基本区间关系
• 2.2.2 区间关系代数的运算性质
• 2.3 矩形代数
• 2.3.1 基本矩形代数关系
• 2.3.2 矩形关系代数的运算性质
• 2.4 主方向关系代数
• 2.4.1 基本主方向关系
• 2.4.2 基本主方向关系的运算性质
• 2.5 本章小结
• 第3章 一种确定基本主方向关系的逆关系的方法
• 3.1 引言
• 3.2 基本主方向关系的逆关系
• 3.2.1 矩形基本主方向关系的逆关系
• 3.2.2 任意基本主方向关系的逆关系
• 3.3 四元组模型
• 3.3.1 四元组模型表示的基本主方向关系
• 3.3.2 四元组模型下基本主方向关系与其逆关系的联系
• 3.4 确定基本主方向关系的逆关系
• 3.4.1 关系C与Ci
• 3.4.2 确定基本主方向关系的逆位置
• INV'>3.4.3 算法GET_INV
• 3.5 实例分析
• 3.6 本章小节
• 第4章 一种基于MBR的不确定区域间方向关系建模方法
• 4.1 引言
• 4.2 空间关系的不确定性的原因
• 4.3 不确定空间方向关系建模
• 4.4 矩形基本主方向关系与矩形代数间的关联
• 4.4.1 矩形基本主方向关系与基本矩形代数关系间的转换
• 4.4.2 矩形基本主方向关系与矩形代数关系间的转换
• 4.5 宽边界区域间方向关系表示模型
• 4.5.1 MBR宽边界方向关系
• 4.5.2 基于矩形代数表示的MBR宽边界方向关系
• 4.6 MBR宽边界方向关系间的相容性复合
• 4.7 复合算法与实例分析
• 4.8 本章小结
• 第5章 一种不确定区域间方向关系推理方法
• 5.1 引言
• 5.2 宽边界方向关系
• 5.3 宽边界方向关系约束
• 5.4 不确定区域间方向关系推理
• 5.4.1 宽边界方向关系的复合运算
• 5.4.2 基于复合运算的宽边界方向关系推理
• 5.5 实例分析
• 5.6 本章小结
• 第6章 一种不确定区域间方向关系相容性检测方法
• 6.1 引言
• 6.2 约束满足问题
• 6.2.1 相关概念
• 6.2.2 基本求解方法
• 6.3 空间约束满足问题
• 6.3.1 基于空间拓扑关系的相容性检测
• 6.3.2 基于空间方向关系的相容性检测
• 6.3.3 结合多种空间关系的相容性检测
• 6.4 宽边界方向关系的相容性检测
• 6.4.1 宽边界方向关系约束
• 6.4.2 问题描述
• 6.4.3 宽边界方向关系约束转换方法
• 6.4.4 路径相容判定算法BBD-CON
• 6.5 本章小结
• 第7章 结论与展望
• 7.1 论文内容总结
• 7.2 论文的创新点
• 7.3 不足与展望
• 参考文献
• 作者简介及在学期间所取得的科研成果
• 致谢