地理信息系统中拓扑关系的不确定性推理方法

首先基于点集拓扑学理论提出了一个新的4交差模型,在此基础上分析了空间数据不确定性对拓扑关系形式化描述的影响.通过引入拓扑距离,建立了拓扑关系概念邻域图,并用以实现拓扑关系的不确定性推理.然后,在4交差模型下建立了拓扑关系合成推理关系表,并给出了合成过程中不确定性的表达方法.通过算例分析表明,本文提出的方法是合理的,具有兼顾定性空间推理和定量表达的优点.     

一个结合多方面定性空间信息的新方法

定性空间推理是人工智能领域中非常重要的研究内容.空间信息包含拓扑关系、大小关系、形状、距离等很多方面.以往多侧重于单一方面的研究,如何将孤立的各方面信息进行统一表示和推理是当前定性空间推理中的一个重要问题.提出利用结合操作来融合不同空间信息表示的新方法.利用结合操作,可以由原先完备互斥关系集合得到新关系,同时利用原有的复合表自动生成新关系的粗复合表.基于结合操作,给出2个理论模型:结合拓扑关系与大小关系模型、结合拓扑关系与远近关系模型.并提出了邻域划分图的概念,说明了邻域划分图与概念邻域图的关系.利用邻域划分图回答了Galton提出的问题:为什么LOS(视觉光线演算)的概念邻域图不同于标准的空间或时间关系的概念邻域图,这些关系的复合表中关系总是来自于概念邻域图.     

结合方向关系和拓扑关系的约束满足推理

结合定性空间推理中的区域连接演算（RCC）和基于区域的主方向关系模型,应用拓扑和方向关系上的复合表,将方向关系和拓扑关系的推理看作约束满足问题（CSP）,给出了结合RCC8和主方向关系的约束满足问题推理算法,该算法可结合拓扑关系和方向关系进行推理。     

一种分层递阶的定性拓扑推理方法

文章针对现有的定性表示方法和拓扑推理算法存在的问题,提出了一种新的方法.首先,提出了基于概念邻域结构的定性表示方法.然后,给出了不同粒度层次上拓扑关系复合表的计算方法.最后,设计得出分层递阶的拓扑推理算法.文章给出的方法具有较高的认知合理性,所提出的推理算法可根据问题来选择合适的表示和推理层次,在已有推理算法给不出解的情况下,可以给出问题的合理解,对一般定性推理研究有参考价值.     

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

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

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

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

GIS中拓扑关系及空间推理研究

通过研究分析GIS中的核心问题——空间拓扑关系,将空间推理引入拓扑关系的研究中,并在拓扑推理的基础上,提出加入方向关系的推理机制,最后给出了推理的模型。     

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

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

定性空间推理中区域连接演算的多维扩展

区域连接演算(RCC)是定性空问推(QSR)的基础理论之一．但RCC理论只支持区域，不能处理包括点、线和区域在内的空问多维对象，这阻碍了RCC应用的发展．扩展了区域概念，将点和线对象视为特殊的区域．提出了能直接用RCC理论描述空间多维对象拓扑关系的MRCC理论．在保留RCC公理的前提下，MRCC增加了2条新公理，并由此推导出了36种MRCC基本关系．进而讨论了基于概念邻域图和复合表的推理．MRCC拓展了RCC理论的适用范围，促进了RCC向实际应用的发展．     

基于MBR的拓扑、方位、尺寸结合的定性空间推理

解决实际问题需将多方面空间关系结合进行推理,多方面空间关系结合推理已成为定性空间推理的研究热点;已有工作主要集中在两方面空间关系结合,缺少两方面以上空间关系结合工作.为解决上述问题,通过最小外包矩形近似表示区域对象,利用其在坐标轴上投影间的关系表示相应空间关系;提出扩展矩形关系模型,实现拓扑、方位和尺寸关系的统一表示和推理;给出RCC8、主方位及尺寸关系转换成扩展矩形关系的转换算法;讨论其上关系取反和复合,指出其复合是基于相容性而非存在性;证明(强预)凸扩展矩形关系约束网是可处理的.     

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.

领域值信息表上的邻域逻辑及其数据推理

引入了一种基于邻域值信息表的邻域逻辑,它是用邻域拓扑内点和邻域拓扑闭包作为逻辑算子的一种逻辑。其内点和闭包是先经二元关系定义了邻域系统,然后用这种邻域系统来定义它。这种逻辑被定义在信息表上,其表上的每个个体关于属性不是取单独一个值,而是扩充到取一个值的领域。公式的真值被扩充为一个区间或邻域,因此讨论一个公式可满足性的三种类型：邻域内点可满足、邻域闭包可满足和邻域可满足,即将公式的真值扩充为多值,并讨论了这种真值关于逻辑联结词的运算和公式的语义模型。最后还给出了这种逻辑的数据推理。     

Determining Consistency of Topological Relations

This paper examines the problem of testing consistency of sets of topological relations which are instances of the RCC-8 relation set Leeds92a. Representations of these relations as constraints within a number of logical frameworks are considered. It is shown that, if the arguments of the relations are interpreted as non-empty open sets within an arbitrary topological space, a complete consistency checking procedure can be provided by means of a composition table. This result is contrasted with the case where regions are required to be planar and bounded by Jordan curves, for which the consistency problem is known to be NP-hard.In order to investigate the completeness of compositional reasoning, the notion of k-compactness of a set of relations w.r.t. a theory is introduced. This enables certain consistency properties of relational networks to be examined independently of any specific interpretation of the domain of entities constrained by the relations.     

随时间演化的不确定区域间拓扑关系判定

不确定性处理是时空数据库技术研究的新领域,现有研究成果集中在时空不确定性的表示模型方面,缺乏不确定性对象间时空关系特别是拓扑关系的分析.提出了利用3维拓扑分析模型来分析2维运动对象的时空关系,针对随时间演化的2维不确定性区域,将Egg/Yolk模型中的RCC（region connection calculus）区域扩充至3维,得到46种联合完备且互不相交的基本拓扑关系,根据各基本拓扑关系的时空特性,将46种基本关系归类为21类不确定性时空关系.     

Basic Topological Models for Spatial Entities in 3-Dimensional Space

In recent years, models of spatial relations, especially topological relations, have attracted much attention from the GIS community. In this paper, some basic topologic models for spatial entities in both vector and raster spaces are discussed.It has been suggested that, in vector space, an open set in 1-D space may not be an open set any more in 2-D and 3-D spaces. Similarly, an open set in 2-D vector space may also not be an open set any more in 3-D vector spaces. As a result, fundamental topological concepts such as boundary and interior are not valid any more when a lower dimensional spatial entity is embedded in higher dimensional space. For example, in 2-D, a line has no interior and the line itself (not its two end-points) forms a boundary. Failure to recognize this fundamental topological property will lead to topological paradox. It has also been stated that the topological models for raster entities are different in Z ² and R ². There are different types of possible boundaries depending on the definition of adjacency or connectedness. If connectedness is not carefully defined, topological paradox may also occur. In raster space, the basic topological concept in vector space—connectedness—is implicitly inherited. This is why the topological properties of spatial entities can also be studied in raster space. Study of entities in raster (discrete) space could be a more efficient method than in vector space, as the expression of spatial entities in discrete space is more explicit than that in connected space.     

面目标间拓扑关系的形式化描述

为了更有效地描述和区分空间面目标间的拓扑关系,本文在4交差模型的基础上,结合两面目标交集的维数和边界交集的分离数,建立相应的面目标间的拓扑关系形式化描述模型。该模型可以进一步区分4交差模型无法区分的相接、交叠、覆盖于和覆盖的拓扑关系。     

一种模糊区域的拓扑关系模型

空间区域拓扑关系建模是空间推理、地理信息系统(GIS)和计算机视觉等领域一个非常重要的主题，模糊区域的拓扑关系建模正日益受到相关领域研究者的重视，在分析现有模型的基础上，提出了一种模糊区域的拓扑关系模型，该模型利用模糊集来表示模糊区域，通过三个谓词的真值来判断区域间的拓扑关系，将分明区域作为特例统一处理，根据谓词的多种真值能够实现多层次上的拓扑关系分析．     

STL格式文件的快速拓扑重建算法

针对立体光刻(STL)文件所表示的图形要素之间缺乏必要的拓扑关系,对STL格式文件进行分析和读取,以哈希表作为查找表快速建立三维模型各要素间的拓扑关系,建立能表示要素关系的点表和面表,利用基于哈希表的拓扑重建算法实现了拓扑结构的快速建立, 算法时间复杂度仅为O(n), 空间复杂度为O(3n+(4+m)f+m)。最后,列举5个实例进行验证测试,实验结果显示,与直接算法和红黑树法相比,所提出的算法用时更少,在普通计算机上重建含有65万个三角面片模型的拓扑结构只需2.3s。     

基于共同邻居邻域拓扑稠密性加权的链路预测方法

链路预测旨在利用已知的网络节点和拓扑结构信息,预测网络中未连接的两个节点之间存在连边的可能性。基于网络拓扑相似性的链路预测方法计算复杂度低且预测效果好,但现有的相似性指标对共同邻居的邻域拓扑信息考虑较少。针对此问题,提出一种基于共同邻居邻域拓扑稠密性加权的链路预测方法。首先,基于邻域拓扑相对稠密指数量化节点的邻域拓扑结构;然后,利用共同邻居的节点度和邻域拓扑相对稠密指数刻画共同邻居及其邻域拓扑的相似性贡献;最后,提出基于共同邻居邻域拓扑稠密性加权的节点相似性指标。在多个实际网络数据上的实验结果表明,与现有相似性指标相比,该方法能够取得更高的预测精度。     

在机检测中三角网格拓扑重建方法的研究

对STL（Stereo Lithographic）模型中三角面片进行拓扑重建是解决在机检测系统中对零件模型表面进行曲面划分的前提条件之一。在建立点-边拓扑关系的基础上,将原有基于顶点坐标值浮点数比较的半边匹配结构转化为基于索引值的整型数匹配,并提出了基于关联-散列结构三角网格拓扑重建方法。该方法采用散列结构为辅助数据结构来减少STL模型顶点归并和边界归并的计算量,利用STL模型相邻网格单元数据相关性降低哈希函数的构建难度并提高冲突处理效率,在滤除冗余数据的同时完成拓扑关系的建立。计算实例验证了该算法的高效性和有效性。