本书共十章,内容包括:空间关系建模概述,空间方向关系演算,一种确定基本主方向关系的逆关系的方法,空间主方向关系的逆关系推理,一种基于MBR的不确定区域间方向关系建模方法,一种不确定区域间方向关系推理方法等。
空间是我们所处环境的基本特征,空间信息在人类社会活动中起着至关重要的作用。空间信息的形式化表示与推理,以及针对空间信息的及时、准确反应,是智能系统做出理性决策的前提,是解决许多理论与实际问题的关键。空间关系能够描述客观的空间信息年来,空间关系建模已成为人工智能领域的重要研究内容之一,在地理信息系统、机器人导航、图像理解领域有着广泛的应用。
定量方法是以往空间信息表示与推理的主要方法,该类方法采用的数值对空间信行处理。然而在很多情景下,通常难以获取严格的定量空问信息,无法基于定量方法开展有效的空间信息处理。另一方面,定性的空间信息更有助于人类认知所处的空间环境,因此精准完整的数值坐标数据对于开展很多实际应用服务并不是必要的。例如,人们通常会使用“在……的西南”、“在,……的右边”这样抽象的定性空问描述,很少使用“东经……”、“南纬……”这样的坐标表示来描述方向信息。人类会利用这些定行各种各样的推理以获得更多的空间信息,或者帮助自行决策、判断。由此可见,定性空间信息是一类普遍存在且不可忽视的可利用空间信息。在人工智能领域中,像人类一样能够表示、分析和处理这种定性空间信息已经成为智能设备应具备的重要能力之一,因此,开展定性空间信息的表示和推理研究具有重要的理论意义和应用价值。
方向关系是最基本的空间关系之一,能够描述空间对象问的相对位置信息。目前空间方向关系建模已取得很展,但仍存在一些问题,例如:现有研究多集中于模型的表示方面,在推理方面研究较少;对空间方向关系运算性质的研究不够深入,其中基本主方向关系的逆运算性质仍是一个有待解决的开放问题;此外现有模型多针对简单空间对象,难以处理复杂空间对象(不连通、带洞、具有不确定边界)问的方向关系,在不确定区域间方向关系的表示模型、基本运算性质、推理方法以及推理复杂性等方面的研究尚处于起步阶段;现有研究多针对静态空间对象,对动态空间对象问的空间关系建模研究不够深入;在大数据背景下,空间方向关系建模在智能交通、机器人导航等领域中的应用研究仍有待于深入。
本书采用定性研究方法,针对确定区域间基本主方向关系的逆运算、不确定区域间方向关系的表示与推理等问题展开研究。对现有定性空间关系模行分析和总结,在此基础上利用SK模型和MBR模型提出确定基本主方向关系的逆关系的方法、确定主方向关系的逆关系的方法;用宽边界模型表示带有不确定边界的复杂区域,利用区间代数和矩形代数分析不确定区域间方向关系的复合运算而提一种MBR宽边界方向关系复合推理方法;通过定义饱和凸主方向关系,找到了主方向关系上的一个已处理子集;分析不确定区域间方向关系自身所蕴含的约束信息,提出一种不确定区域间方向关系约束的相容性判定算法;面向动态空间对象,提出一种定性方向关系与距离变化的结合推理方法,用于智能交通、机器人导航等领域中海量数据的预处理问题与交通轨迹的邻查询问题。本书的主要贡献、研究思路和结构如下:
第pan style="font-family: 宋体">章:空间关系建模概述。首先论述空间关系建模的研究背景和意义,介绍几种主要空间关系的基本概念和研究现状;然后以定性空间方向关系研究为主线,分别从简单对象间方向关系和不确定对象间方向关系两方面,着重对现有空间方向关系建模研究的现行分析与总结;最后讨论了目前空间方向关系建模研究所存在的问题。
第2章:定性空间方向关系演算。介绍定性空间方向关系推理中3种重要的关系代数,即区间代数、矩形代数、主方向关系代数;论述了3种关系代数的研究意义和现状;分别给出3种关系代数的基本定义以及基本关系运算(着重介绍了其中的交、并、逆、复合运算)。
第3章:提出了一种确定基本主方向关系的逆关系的方法。首先研究了基本主方向关系的逆关系这一开放问题。首先基于模型SK和MBR提出一种四元组表示模型,将任意一个基本主方向关系.R转换成其对应的四元组,称该四元组为R的位置,记为(R);然后分析了R与zoc(R),zoc(尺)与Z0c叫(R)以及Z0c。(R)与inu(R)间的对应关系;在此基础上提出一种确定基本主方向关系的逆关系的方法。该方法能够确括单片、多片和矩形关系在内的所有基本主方向关系的逆关系。
第4章:提出了一种确定主方向关系的逆关系的方法,利用矩形主方向关系和区间关系之间的联系给出了推理矩形主方向关系的逆关系的具体算法,并证明算法是可靠完备的;然后定义基本主方向关系集合上的相似关系,并证明其是等价关系;根据该等价关系,将2pan style="font-family:宋体">个基本主方向关系划分成了36个等价类,在此基础上提出了一种确定主方向关系的逆关系的算法,证明该算法是可靠完备的,并给出了逆关系表。
第5章:提出了一种基于MBR的不确定区域间方向关系建模方法。首先讨论了导致空间关系不确定性的各种原因;介绍了不确帘宰问肯向羊系建模研究现状,并指出了存在的问题;提出了一种基于MBR的不确定区域间方向关系建模方法,该方法采用宽边界统一表示区域的不确定边界,将矩形代数的良好计算性质应用于不确定区域间MBR主方向关系的表示与推理中,定义MBR宽边界方向关系用以表示不确定区域间的方向关系;给出MBR宽边界方向关系间相容性复合的定义;基于矩形代数提出一种复合运算方法,并形式化证明其正确性。
第6章:提出了一种不确定区域间方向关系的推理方法。首先对提出的MBR宽边界方向关系模行扩展,定义了宽边界方向关系用以描述不确定区域间的方向关系,更符合人们对方向关系的认知;然后基于基本主方向关系的形式化定义,分析并证明宽边界方向关系自身蕴含的约束规则;最后定义宽边界方向关系的复合,给出一种基于复合运算的不确定区域间方向关系推理方法,并证明了该方法的正确性。
第7章:根据一个新的主方向关系的已处理子集重新定义了饱和凸矩形主方向关系而给出了一个主方向关系上的已处理子集;证明了基于该已处理子集上的相容性问题是多项式问题,并证明出该集合是主方向演算的一个子代数。
第8章:提出了一种不确定区域间方向关系相容性检测方法。首先介绍空间约束满足问题的基本概念和研究现状;其后定义宽边界方向关系约束,~?YaT宽边界方向关系约束集合的相容性问题;然后分析了宽边界约束和确定区域间方向关系约束之间的转换规则,从而将基于宽边界方向关系的约束满足问题转换为基于确定区域间方向关系的约束满足问题;最后基于路径相容算法,提出一种基于宽边界方向关系约束的相容性算法BBD-CON,并分析了算法的复杂度。
第9章:大数据概述与大数据应用。介绍了国内外大数据的发展现状,多层面阐述了大数据的定义,并总结了大数据的典型特征;与以往的科学发现思维范式相对比,分析了大数据思维的主要特征与内涵;简要介绍T3v~i据在移动通信、金融、工业、农业、等领域中的具体应用。
第pan style="font-family: 宋体">章:基于空间方向关系建模的大规模交通轨迹预处理。对智能交行概述;分析并总结了交通大数据的主要特征;针对交通大数据中的轨迹数据展开研究,介绍了交通轨迹数据的定义及其预法;针对传统智能交通系统难以对大规模的交通移轨迹数行处理的问题,基于Ha—doo,SDa。k、Hb。。。等大数据处理框架搭建了面向交通轨迹数据的大数台。针对基于静态位置信息的传统查询方法难以对路网中大规模移动对行准确地连续邻查询这一问题,将路网中移动对象抽象为有向线段,将移动对象间OPRA。方向关系约束作为从路网中选取特征点的重要依据而提出一种结合定性方向关系与距离变化的推理方法,能够从交通对象中过滤掉与查询点运动方向不一致的道路边与候选点。基于该理论模型一步结合大数据生态系统与处理技术,提出一种面向智能交通、机器人导航领域中大规模轨迹数据的预法。
在本书的撰写过程中,作者不仅参阅、引用了很多国内外相关文献资料,而且得到了同事亲朋的鼎力相助,在此一并表示衷心的感谢。由于作者有限,书中疏漏之处在所难免,恳请同行专家以及广大读者批评指正。
作 者
第l章空问关系建模概述
空间信息无处不在,诸如方向、拓扑、形状等,这些信息能够描述现实的空间特征,在人类社会活动中起着至关重要的作用。空间关系是空间信息的一种表示形式,空间关系建模旨在提供处理空间信息的手段和方式,即构造表示空间信息的形式化模型,并基于该模型完成推理任务。
IJCAI、AAAI、ECAI专门设立了相关的Workshop;《Artificial Intelli—g。nc。》等国际期刊和杂志上的空间关系建模文章数量呈逐年增长趋势。在国内,空问关系建模研究已取得较展:吉林大学在拓扑与方向关系建模、时空语义处理、时空数据挖掘等方面取得了重要理论成果,应用于农业领域;清华大学在空间关系的推理方法、推理复杂性等方面取得了重要理论成果;北京大学遥感所、武汉大学、中科院地理所和浙江大学等围绕空间关系的不确定性、空间数据库等问题展开了一系列卓有成效研究。目前我国空间基础信息建设已初具规模,为空间关系建模研究提供了良好的条件。
空间关系建模主要有定量和定性两种方法。定量方法属于传统方法,通常基于空间对象及对象间完整、准确的数据,推理时需行数值或几何计算,因此很难处理复杂的空间问题;与定量方法不同,定性方法采用有限的词汇表(例如空间关系)描述空间信息,不仅更人们的空间认知,而且便于利用智能方行推理,因此定性空间关系建模成为空间关系建模今后的发展方向,已成为人工智能、认知科学、语言学、地理信息科学等领域的重要研究内容。虽然定性空间关系建模取得了一系列开创性的成果,但其理论不够系统,仍需完善。现有定性空间关系模型大多建立在理想环境中,例如通常只考虑静态环境中确定的空间对象,将复杂的空间对象抽象成简单的点或其他规则的几何对象,且主要针对空间对象间单一种类的空间信息,同时在推理复杂性、完备性,以及关系运算性质等方面仍存在许多开放问题。这些与现实中的复杂问题以及人们对空间方向的认知尚存在较大差异,因此定性空间关系建模尚存在巨大的理论研究空间。
由于定性空间关系建模具有抽象程度高、理论完备、空间认知等特点,因此成为解决诸如矿产资源勘探、灾害预警等领域中重大应用问题的关键技术。基于定性空间关系建模开发的GIS(Geographic information sys-tern)、GNSS(Global Navigation Satellite Systems)、LBS(Location Based Services)、SDSS(Spatial Decision Systems)等系统已在地质、全球定位、机器人导航、图像处理和常识推理等领域得以广泛应用,因此定性空间关系建模具有重要的实际应用价值。
pan style="font-family:宋体">.1 空问关系建模
空间关系能够描述空间对象以及对象间的空问信息,是空间信息的一种重要表示形式。基于空间对象的几何特征(形状、位置等属性),可以将空间对象间的空间信息表示为拓扑关系、方向关系、距离关系等;对于空间对象的非几何特征(例如温度、密度、时间等属性),可用空间分布现象的统计相关、空间相互作用、空间依赖、空间自相关等来表示空间信息。空间关系的概念贯穿于空间关系建模的整个过程,它是空间关系建模的核心与基础。空间关系建模主要研究空间对象的表示方法、对象间空间信息描述方法以及在此基础上关系间的推理方法。
pan style="font-family:宋体">.pan style="font-family:宋体">.1 空间关系建模的定量与定性方法
定量方法是指事先建立假设并确定具有因果关系的各种变量,然后使用某些经过检测的工具对这些变行测量和分析,从而验证研究者预定的假设。定量方法属于传统方法,多基于经验测量、概率、统计分析等理论方法,通常基于空间对象及对象间完整、准确的数据。一方面严格的定量空间数据通常难以、甚至是无法获取的;另一方面人类用定去认知和描述现实。这使得基于定性方法的空间关系建模研究成为必然趋势。
定性空间关系建模旨在将复杂的物理行符号化的抽象表示,以提供有效完备的空间信息推理方法。定性空间关系建模方法由定性空间关系表示模型与定性空间关系推理模型两部分组成。定性空间关系表示模型主要解决空间对象似表示以及空间方向关系的描述问题,而定性空间关系推理模型主要解决空间方向关系的推理问题。与定量方法相比,定性空间关系建模具有抽象程度高、理论完备、空间认知等特点,因而成年来研究的热点。本书所研究的空间关系表示与推理模型均基于定性方法……