Topological Spatio–Temporal Reasoning and Representation

We present here a theory of motion from a topological point of view, in a symbolic perspective. Taking space–time histories of objects as primitive entities, we introduce temporal and topological relations on the thus defined space–time to characterize classes of spatial changes. The theory thus accounts for qualitative spatial information, dealing with underspecified, symbolic information when accurate data are not available or unnecessary. We show that these structures give a basis for commonsense spatio–temporal reasoning by presenting a number of significant deductions in the theory. This can serve as a formal basis for languages describing motion events in a qualitative way.     

A fuzzy sets theoretic approach to approximate spatial reasoning

Relational composition-based reasoning has become the most prevalent method for qualitative reasoning since Allen's 1983 work on temporal intervals. Underlying this reasoning technique is the concept of a jointly exhaustive and pairwise disjoint set of relations. Systems of relations such as RCC5 and RCC8 were originally developed for ideal regions, not subject to imperfections such as vagueness or fuzziness which are found in many applications in geographic analysis and image understanding. This paper, however, presents a general method for classifying binary topological relations involving fuzzy regions using the RCC5 or the RCC8 theory. Our approach is based on fuzzy set theory and the theory of consonant random set. Some complete classifications of topological relations between fuzzy regions are also given. Furthermore, two composition operators on spatial relations between fuzzy regions are introduced in this paper. These composition operators provide reasonable relational composition-based reasoning engine for spatial reasoning involving fuzzy regions.     

Relation Algebras and their Application in Temporal and Spatial Reasoning

Qualitative temporal and spatial reasoning is in many cases based on binary relations such as before, after, starts, contains, contact, part of, and others derived from these by relational operators. The calculus of relation algebras is an equational formalism; it tells us which relations must exist, given several basic operations, such as Boolean operations on relations, relational composition and converse. Each equation in the calculus corresponds to a theorem, and, for a situation where there are only finitely many relations, one can construct a composition table which can serve as a look up table for the relations involved. Since the calculus handles relations, no knowledge about the concrete geometrical objects is necessary. In this sense, relational calculus is pointless. Relation algebras were introduced into temporal reasoning by Allen (1983, Communications of the ACM 26(1), 832–843) and into spatial reasoning by Egenhofer and Sharma (1992, Fifth International Symposium on Spatial Data Handling, Charleston, SC). The calculus of relation algebras is also well suited to handle binary constraints as demonstrated e.g. by Ladkin and Maddux (1994, Journal of the ACM 41(3), 435–469). In the present paper I will give an introduction to relation algebras, and an overview of their role in qualitative temporal and spatial reasoning.     

GIS中由多种方向关系推理拓扑关系的方法

研究了根据多种方向关系（包括内部、边界、环部和外部等方向关系）推理拓扑关系的方法．在推理中,首先提出了根据单种方向关系推理拓扑关系的规则;然后,将多种方向关系的组合分为4种基本类型,每种类型的推理方法和规则可表示为单种方向关系推理的组合;最后,讨论了根据多种方向关系可得到的拓扑关系的几何关系、约束条件和推理规则,根据多种方向关系推理拓扑关系的方法和规则可用于空间数据库查询和基于内容的数据检索．     

Spatial reasoning in a fuzzy region connection calculus

Although the region connection calculus (RCC) offers an appealing framework for modelling topological relations, its application in real-world scenarios is hampered when spatial phenomena are affected by vagueness. To cope with this, we present a generalization of the RCC based on fuzzy set theory, and discuss how reasoning tasks such as satisfiability and entailment checking can be cast into linear programming problems. We furthermore reveal that reasoning in our fuzzy RCC is NP-complete, thus preserving the computational complexity of reasoning in the RCC, and we identify an important tractable subfragment. Moreover, we show how reasoning tasks in our fuzzy RCC can also be reduced to reasoning tasks in the original RCC. While this link with the RCC could be exploited in practical reasoning algorithms, we mainly focus on the theoretical consequences. In particular, using this link we establish a close relationship with the Egg-Yolk calculus, and we demonstrate that satisfiable knowledge bases can be realized by fuzzy regions in any dimension.     

基于区域伸缩的空间关系表示

区域连接演算(RCC)是定性空间推理的重要基础理论之一.但由于缺乏必要的度量,RCC只是粗略地描述空间拓扑关系而难以对其更准确地描述,也难以利用RCC描述除拓扑关系之外的其它空间关系,如距离、方向等.本文在RCC理论的基础上,提出了区域伸缩演算(RESC).RESC增加了一个全等CG的原始空间关系,引入了两个新颖的对区域的演算函数,即区域延伸和区域收缩,从而给出了一种以区域为单位的形式化的度量方法.利用RESC,不仅可以扩展RCC-8拓扑关系,而且能以灵活多样的粒度来描述区域间的距离关系、方向关系、位置关系以及运动关系.RESC增强了RCC的空间关系表示能力,拓展了RCC理论的适用范围.     

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

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

A condensed semantics for qualitative spatial reasoning about oriented straight line segments

More than 15 years ago, a set of qualitative spatial relations between oriented straight line segments (dipoles) was suggested by Schlieder. However, it turned out to be difficult to establish a sound constraint calculus based on these relations. In this paper, we present the results of a new investigation into dipole constraint calculi which uses algebraic methods to derive sound results on the composition of relations of dipole calculi. This new method, which we call condensed semantics, is based on an abstract symbolic model of a specific fragment of our domain. It is based on the fact that qualitative dipole relations are invariant under orientation preserving affine transformations.The dipole calculi allow for a straightforward representation of prototypical reasoning tasks for spatial agents. As an example, we show how to generate survey knowledge from local observations in a street network. The example illustrates the fast constraint-based reasoning capabilities of dipole calculi. We integrate our results into two reasoning tools which are publicly available.     

Efficient Estimation of Qualitative Topological Relations based on the Weighted Walkthroughs Model

Weighted walkthroughs are a quantitative model for representing the spatial relation between two raster features in image databases. In this paper, we establish a correspondence between the weighted walkthroughs and qualitative models for spatial reasoning. We provide rules for estimating qualitative geometric properties and topological relations from the quantitative data that are computed for each pair of pixel sets. The approach has been tested through experiments with raster regions.     

地理信息系统中空间对象间拓扑关系的推理

首先讨论了地理信息系统中空间对象的空间数据模型,然后定性地分析了空间对象点与点、点与线和点与区域之间的拓扑关系,并给出了空间对象拓扑关系的推理算法.最后,将模糊技术与空间对象之间的拓扑关系的推理算法结合起来,使其可以方便地处理地理信息系统中的模糊性和不确定性.     

基于区域伸缩的空间关系研究与实现

区域连接演算(RCC)是空间推理的重要基础理论之一,它只能粗略地描述空间拓扑关系,难以描述除拓扑关系之外的其他空间关系,如距离和方向。在RCC理论的基础上,引入2个对区域的演算函数,即区域延伸和区域收缩,给出一种以区域为单位的形式化的度量方法。在RESC理论的基础上,利用栅格区域法应用简单和易于实现的特性,准确地得出区域间的空间关系。     

拓扑关系的闭球模型及复合表的推导

Egenhofer和Franzosa提出的拓扑关系的4-交集模型是定性空间推理中常用的模型，但基于4-交集模型难以推导出拓扑关系的完备集、概念邻域和复合表．本文以拓扑学为基础，提出了（n，n）完备集的概念，建立了拓扑关系的闭球模型．基于闭球模型可以直接推导出拓扑关系的（n，n）完备集和概念邻域以及复合表．结果表明，对定性空间推理来说，闭球模型比4-交集模型更简单有效．     

基于区域延伸的定性空间表示

在区域连接演算(region connection calculus,RCC)理论基础上给出了区域延伸的形式定义.通过区域延伸,定义了关联空间的概念,进而提出了空间表示的一个模型,在这个模型中给出了空间中物体的空间拓扑关系、距离关系、方向关系以及位置等信息的定性表示.智能体对空间关系的确定是通过区域延伸实现的,模型为智能体在约束空间环境中的行动推理提供了一个新的表示方法.     

Qualitative representation of spatial knowledge in two-dimensional space

Various relation-based systems, concerned with the qualitative representation and processing of spatial knowledge, have been developed in numerous application domains. In this article, we identify the common concepts underlying qualitative spatial knowledge representation, we compare the representational properties of the different systems, and we outline the computational tasks involved in relation-based spatial information processing. We also describesymbolic spatial indexes, relation-based structures that combine several ideas in spatial knowledge representation. A symbolic spatial index is an array that preserves only a set of spatial relations among distinct objects in an image, called the modeling space; the index array discards information, such as shape and size of objects, and irrelevant spatial relations. The construction of a symbolic spatial index from an input image can be thought of as a transformation that keeps only a set of representative points needed to define the relations of the modeling space. By keeping the relative arrangements of the representative points in symbolic spatial indexes and discarding all other points, we maintain enough information to answer queries regarding the spatial relations of the modeling space without the need to access the initial image or an object database. Symbolic spatial indexes can be used to solve problems involving route planning, composition of spatial relations, and update operations.     

利用简化9交模型进行三维拓扑分析

针对点、线、面和体等简单空间对象提出新的否定规则，对9交模型进行了简化．利用简化后的9交模型，仅需分析4组相交关系即可得出实际拓扑关系．在此基础上构建了拓扑关系推导表，可进一步分析复合空间对象之间的拓扑关系，并以线与体之间拓扑关系为例讨论了算法实现．与已有的算法相比，该算法能分析更为复杂的空间对象之间的拓扑关系．     

Multi-level Topological Relations Between Spatial Regions Based Upon Topological Invariants

Topological relations have played important roles in spatial query, analysis and reasoning. In a two-dimensional space (IR²), most existing topological models can distinguish the eight basic topological relations between two spatial regions. Due to the arbitrariness and complexity of topological relations between spatial regions, it is difficult for these models to describe the order property of transformations among the topological relations, which is important for detailed analysis of spatial relations. In order to overcome the insufficiency in existing models, a multi-level modeling approach is employed to describe all the necessary details of region–region relations based upon topological invariants. In this approach, a set of hierarchically topological invariants is defined based upon the boundary–boundary intersection set (BBIS) of two involved regions. These topological invariants are classified into three levels based upon spatial set concept proposed, which include content, dimension and separation number at the set level, the element type at the element level, and the sequence at the integrated level. Corresponding to these hierarchical invariants, multi-level formal models of topological relations between spatial regions are built. A practical example is provided to illustrate the use of the approach presented in this paper.

Approximate analysis of binary topological relations between geographic regions with indeterminate boundaries

 The development of formal models of spatial relations is a topic of great importance in spatial reasoning, geographic information systems (GIS) and computer vision, and has gained much attention from researchers across these research areas during the past two decades. In recent years significant achievements have been made on the development of models of spatial relations between spatial objects with precisely defined boundaries. However, these models cannot be directly applied to spatial objects with indeterminate boundaries which are found in many applications in geographic analysis and image understanding. This article develops a method for approximately analyzing binary topological relations between geographic regions with indeterminate boundaries based upon previous work on topological spatial relations and fuzzy sets. In addition, examples are given to demonstrate the method and related concepts. It is shown that the eight binary topological relations between regions in a two-dimensional space can be easily determined by the method.     

Interplay of spatial aggregation and computational geometry in extracting diagnostic features from cardiac activation data

Functional imaging plays an important role in the assessment of organ functions, as it provides methods to represent the spatial behavior of diagnostically relevant variables within reference anatomical frameworks. The salient physical events that underly a functional image can be unveiled by appropriate feature extraction methods capable to exploit domain-specific knowledge and spatial relations at multiple abstraction levels and scales. In this work we focus on general feature extraction methods that can be applied to cardiac activation maps, a class of functional images that embed spatio-temporal information about the wavefront propagation. The described approach integrates a qualitative spatial reasoning methodology with techniques borrowed from computational geometry to provide a computational framework for the automated extraction of basic features of the activation wavefront kinematics and specific sets of diagnostic features that identify an important class of rhythm pathologies.     

Spatial reasoning with rectangular cardinal relations

Qualitative spatial representation and reasoning plays a important role in various spatial applications. In this paper we introduce a new formalism, we name RCD calculus, for qualitative spatial reasoning with cardinal direction relations between regions of the plane approximated by rectangles. We believe this calculus leads to an attractive balance between efficiency, simplicity and expressive power, which makes it adequate for spatial applications. We define a constraint algebra and we identify a convex tractable subalgebra allowing efficient reasoning with definite and imprecise knowledge about spatial configurations specified by qualitative constraint networks. For such tractable fragment, we propose several polynomial algorithms based on constraint satisfaction to solve the consistency and minimality problems. Some of them rely on a translation of qualitative networks of the RCD calculus to qualitative networks of the Interval or Rectangle Algebra, and back. We show that the consistency problem for convex networks can also be solved inside the RCD calculus, by applying a suitable adaptation of the path-consistency algorithm. However, path consistency can not be applied to obtain the minimal network, contrary to what happens in the convex fragment of the Rectangle Algebra. Finally, we partially analyze the complexity of the consistency problem when adding non-convex relations, showing that it becomes NP-complete in the cases considered. This analysis may contribute to find a maximal tractable subclass of the RCD calculus and of the Rectangle Algebra, which remains an open problem.     

Spatial relations between 3D objects: The association between natural language,topology, and metrics

With the proliferation of 3D image data comes the need for advances in automated spatial reasoning. One specific challenge is the need for a practical mapping between spatial reasoning and human cognition, where human cognition is expressed through natural-language terminology. With respect to human understanding, researchers have found that errors about spatial relations typically tend to be metric rather than topological; that is, errors tend to be made with respect to quantitative differences in spatial features. However, topology alone has been found to be insufficient for conveying spatial knowledge in natural-language communication. Based on previous work that has been done to define metrics for two lines and a line and a 2D region in order to facilitate a mapping to natural-language terminology, herein we define metrics appropriate for 3D regions. These metrics extend the notions of previously defined terms such as splitting, closeness, and approximate alongness. The association between this collection of metrics, 3D connectivity relations, and several English-language spatial terms was tested in a human subject study. As spatial queries tend to be in natural language, this study provides preliminary insight into how 3D topological relations and metrics correlate in distinguishing natural-language terms.