Reasoning about cardinal directions between extended objects

Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a relation model, known as the cardinal direction calculus (CDC), for representing direction relations between connected plane regions. The CDC is perhaps the most expressive qualitative calculus for directional information, and has attracted increasing interest from areas such as artificial intelligence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking the consistency of complete networks of basic CDC constraints, and proves that reasoning with the CDC is in general an NP-complete problem. For a consistent complete network of basic CDC constraints, our algorithm returns a ‘canonical’ solution in cubic time. This cubic algorithm is also adapted to check the consistency of complete networks of basic cardinal constraints between possibly disconnected regions.     

基于MBR的主方向关系一致性检验

定性的空间推理在地理信息系统、人工智能、数据库及多媒体等领域中的应用越来越引起人们的注意.空间推理的基础理论以及相应算法也在不断地创新和发展.方向关系推理是空间推理研究领域的重要分支,利用区间代数及矩形代数理论,以物体的极小边界盒(minimum bounding rectangle,简称MBR)为模型,提出了一种基于MBR的主方向关系与矩形代数关系相结合的推理方法.利用该方法,可以将矩形代数良好的计算性质应用于空间方向关系推理中,实现了矩形代数与基于MBR主方向关系的相互转换方法、主方向关系合成及求反方法、主方向关系中凸(convex)关系判定方法及方向关系一致性检验算法.     

描述定性方向关系的复合表达模型

目的：由于锥形模型和方向关系矩阵模型没有很好地顾及目标的形状、大小和距离等对方向关系的影响,导致方向关系判断在许多情况下出现错误。鉴于此,通过锥形模型与方向关系矩阵模型的相互结合,提出一种复合表达模型,以克服二者的不足,从而更好地描述两目标之间的定性方向关系。方法：首先,利用锥形模型的锥形方向区域和方向关系矩阵模型中对应的矩形方向区域之间的几何运算,对各方向区域重新进行划分,构造出复合表达模型;然后,通过计算源目标与复合表达模型各方向区域之间的交,得到源目标相对于参考目标的定性方向关系,并将结果以矩阵的形式进行保存。结果：实验表明,复合表达模型有效地避免了锥形模型与方向关系矩阵模型存在的缺陷。结论：该模型能够对两目标之间的定性方向关系进行准确地描述,可以为空间推理与空间查询提供较好的支持。     

Fuzzy semantics for direction relations between composite regions

This paper proposes a model that combines qualitative spatial reasoning with fuzzy semantic typing to derive direction relations between two composite regions in a spatial configuration. It extends Goyal and Egenhofer’s direction relation model, initially proposed for simple regions, towards composite regions. A fuzzy semantics typing qualifies the overall direction relations of two composite regions. We introduce flexible fuzzy measures that allow for both a qualitative and metric study of direction relation similarities.     

Computing and managing cardinal direction relations

Qualitative spatial reasoning forms an important part of the commonsense reasoning required for building intelligent geographical information systems (GIS). Previous research has come up with models to capture cardinal direction relations for typical GIS data. In this paper, we target the problem of efficiently computing the cardinal direction relations between regions that are composed of sets of polygons and present two algorithms for this task. The first of the proposed algorithms is purely qualitative and computes, in linear time, the cardinal direction relations between the input regions. The second has a quantitative aspect and computes, also in linear time, the cardinal direction relations with percentages between the input regions. Our experimental evaluation indicates that the proposed algorithms outperform existing methodologies. The algorithms have been implemented and embedded in an actual system, CARDIRECT, that allows the user to 1) specify and annotate regions of interest in an image or a map, 2) compute cardinal direction relations between them, and 3) pose queries in order to retrieve combinations of interesting regions.     

一种用于常识空间信息处理的定性空间关系模型

在空间信息处理中,一些常识空间信息通常结合多方面空间关系,而且这些空间关系是动态变化的.为了有效地表示这些复杂的空间关系,并对其进行推理,提出了一种结合拓扑、方向和大小关系的空间信息处理模型TDSC (topology-direction-size calculus),并基于TDSC模型提出了处理动态空间关系变化的表示推理框架.首先,利用同对象多属性的方法建立了融合大小、拓扑和方向关系的完备至斥基本关系表示;然后提出了复合表生成算法和推理算法,使得原有模型的表示和推理结果可以直接在新模型中使用.同时提出处理动态空间关系的邻域划分图,给出了邻域划分图的自动生成算法,以及TDSC模型的邻域划分图.最后给出基于TDSC模型邻域划分图的表示和推理框架,并结合实例说明框架的正确性和有效性.     

一种基于OPRA\\-4方向关系推理定性距离变化的方法

空间信息包含方向、拓扑、形状、距离等多种关系.定性空间关系表示与推理是人工智能的重要研究子域,在空间信息系统、机器人导航、自然语言理解、智能交通等领域有着广泛的应用.以往研究多面向静态空间对象,侧重单一空间关系,对不同空间关系间的约束研究不够深入,难以基于一种空间关系对另一种空间关系的演变做出有效推理.针对移动空间对象之间定性方向关系与定性距离变化的结合推理问题,利用射线与圆之间位置关系的组合来描述2个空间对象之间的相对移动方向;分别研究并证明该位置关系的组合对定性距离变化的约束作用、该位置关系的组合与粒度为4的有向点方向代数(oriented point algebra with granularity of 4, OPRA\\-4)间的对应关系,进而建立起OPRA\\-4方向关系与定性距离变化之间的内在联系;提出一种基于基本OPRA\\-4方向关系推理定性距离变化的方法,并结合交通领域中的连续k近邻查询实例说明该方法的正确性和有效性.     

原子方向与基本方向关系合成方法的研究

随着空间数据库技术的不断发展,基于方向关系的空间推理越来越引起人们的注意,作为空间推理的一部分方向关系合成的研究应运而生。文章使用方向关系矩阵表示物体MBR(MinimumBoundingBox)之间方向关系模型,通过一系列方向关系矩阵的性质和运算的定义、定理,提出了原子方向关系与基本方向关系合成问题的求解方法,并证明其正确性。     

Composing cardinal direction relations

We study the recent proposal of Goyal and Egenhofer who presented a model for qualitative spatial reasoning about cardinal directions. Our approach is formal and complements the presentation of Goyal and Egenhofer. We focus our efforts on the composition operator for two cardinal direction relations. We consider two interpretations of the composition operator: consistency-based and existential composition. We point out that the only published method to compute the consistency-based composition does not always work correctly. Then, we consider progressively more expressive classes of cardinal direction relations and give consistency-based composition algorithms for these classes. Our theoretical framework allows us to prove formally that our algorithms are correct. When we consider existential composition, we demonstrate that the binary relation resulting from the composition of two cardinal direction relations cannot be expressed using the relations defined by Goyal and Egenhofer. Finally, we discuss some extensions to the basic model and consider the composition problem for these extensions.     

空间区域拓扑关系分析方法综述

空间关系形式化模型的发展是空间推理、地理信息系统(geographic information systems,简称GIS)、计算机视觉等领域中的一个非常重要的主题,近年来受到相关领域研究者的极大关注,特别是在空间区域间拓扑关系模型的研究方面取得了很大进展.介绍了区域间拓扑关系形式化分析的主要研究内容、研究方法和研究进展,并探讨了目前存在的问题和今后的发展方向.     

RCC5与主方位关系结合的定性空间推理

解决实际问题需要将多方面空间信息结合进行推理,仅考虑单方面空间信息是不够的.多方面空间信息结合推理已成为定性空间推理的一个研究热点.现有拓扑与方位结合推理工作主要集中在与基于最小外包矩形或单片方位模型的结合.方位信息描述是近似的,不适于精确推理;因此分别采用主方位模型和RCC5描述方位、拓扑信息.根据定义给出基本RCC5和主方位关系间的相互依赖及异质复合表;讨论了其上约束满足问题,得到一个路径相容算法,并分析了推理复性问题.     

Multi-scale qualitative location: A direction-based model

Qualitative locations describe the locations of spatial objects by relating them to a reference frame with qualitative relations. Existing models concerned with regional partitions are mainly topology-based and do not consider the effects of scale changes on locations. This study develops a direction-based multi-scale qualitative location (DMQL) model to fill this gap. First, a cell partition is defined by extending the borders of the minimum bounding rectangles of the regions in a regional partition. Relating spatial objects to all regions by a set of directions is equal to representing the objects as a set of cells in a cell partition. Second, due to the multiple cell representations of spatial objects and the changes in direction relations across scales, some approaches are presented to derive the direction changes between regions in different frames, between spatial objects and regions, and between spatial objects at different scales. Third, the location and relation consistencies of qualitative locations are evaluated based on the cell representations of spatial objects at multiple scales through a case study. The results indicate that the DMQL model can locate objects more precisely than the topology-based models.     

近似空间关系代数ASRA及应用

粗定位模型是一种基于粗集的近似区域表示模型 ,基于定性空间推理理论对其进行了代数形式化 .通过空间关系矩阵和 2 4 9种基本空间关系构造了近似空间关系代数 ASRA;讨论了 ASRA的公理和基本性质 ,研究了ASRA和 RCC5关系映射中存在的不确定性 ;把 ASRA应用于 GIS,提出了基于 ASRA的空间关系判定算法ASRA- RCC.与同类算法相比 ,ASRA- RCC能够同时支持确定和近似区域 ,并且具有较高的效率     

时空推理中自动生成复合表的通用算法

时空推理是面向时间/空间问题的研究领域,在人工智能(如语义Web、机器人导航、自然语言处理、物理过程的定性模拟和常识推理等)和其他领域有着广泛的应用前景.复合推理在时空推理中具有重要作用,是约束满足问题等其他定性推理的基础.复合推理是由R(a,b)和R(b,c)决定R(a,c)的一种演绎推理.一般将关系复合结果放在复合表中备查.但目前复合表的建立需要逐个模型进行手工推导,少数模型给出了独立的复合表生成算法,没有适合多种时空关系模型、能自动生成复合表的通用算法.为此,提出了一种能自动生成复合表的通用算法.首先,给出了基于空间划分的通用时空表示模型.在此基础上,提出了基于场景检测的通用复合表生成算法.通过理论分析和对RCC、宽边界、区间代数等20余种典型时空模型的测试,证明了本算法对于所有以精确区域(或区间)为基础的确定、不确定时空模型均能正确快速地生成复合表.     

一种定性细节方向关系的表达模型

空间关系在空间数据库查询语言、基于内容的图像检索及空间场景的相似性等领域有着广泛的应用。然而，当目标对象与参照对象的外接矩形相交或位于其内时，现有方向关系表达方法不能有效地描述有关方向的信息，从而限制了与空间关系有关概念的表达。为此提出了一种能够表达与参照对象外接矩形内部有关信息的细节方向关系表达模型，研究了线／面、面／面和点／面间拓扑关系和方向关系的组合表达问题，最后给出了细节方向关系的计算模型。与现有的方向关系描述方法相比，细节方向关系能够描述参照对象的形状、岛屿，并且能够提高空间关系的分辨率。     

一种动态定性空间关系自动规划方法

为解决定性空间关系的规划问题,在概念邻域图的基础上提出描述动作与定性空间关系交互的邻域划分图.基于邻域划分图,提出了定性空间关系自动规划的形式化表示和推理算法,证明了算法的可靠性,并举例说明了新方法的应用.该方法在处理单方面空间关系规划中具有用通用性,在机器人导航方面具有潜在的应用前景.     

On the consistency of cardinal direction constraints

We present a formal model for qualitative spatial reasoning with cardinal directions utilizing a co-ordinate system. Then, we study the problem of checking the consistency of a set of cardinal direction constraints. We introduce the first algorithm for this problem, prove its correctness and analyze its computational complexity. Utilizing the above algorithm, we prove that the consistency checking of a set of basic (i.e., non-disjunctive) cardinal direction constraints can be performed in O(n⁵) time. We also show that the consistency checking of a set of unrestricted (i.e., disjunctive and non-disjunctive) cardinal direction constraints is NP-complete. Finally, we briefly discuss an extension to the basic model and outline an algorithm for the consistency checking problem of this extension.     

基于Voronoi图的定性路径推理

动态空间知识的表示与推理是定性空间推理研究的重要内容.基于Voronoi图及其动态变化,提出运动路径定性表示与推理方法.先根据Voronoi图空间邻近关系定义Voronoi图生成子空间关系,进一步定义定性位置及概念邻域,并应用概念相邻的定性位置序列给出定性路径表示.再由动态Voronoi图的边集变化和给出的概念邻域中定性位置间最短路径的启发式算法,设计并实现具有观察者角度的定性路径推理算法.最后,实验分析并验证该方法的有效性.     

基于结合空间拓扑和方向关系信息的空间推理

结合了定性空间推理中著名的区域连接演算（region connection calculus,RCC）和基于区域的方向关系演算（cardinal direction calculus,CDC）,并且给出两个演算在两个方向上的交互表,即RCC8-To-CDC和CDC-To-RCC8．给出了结合RCC8和CDC知识的约束满足问题的路径一致算法（path consistency algorithm）（该算法是对Allen著名的路径一致算法的修改）,并且采用两个队列实现了该算法,采用这种结构可以实现并行计算．在该算法中,基于以上两个交互表的交互操作被嵌入到算法里面来保证整个约束满足问题的一致性．算法的计算复杂性证明是多项式的,