三维空间有向点关系代数的推理研究

发布时间：2018-08-04 20:59

【摘要】：空间和时间是人类认识世界无法回避的问题,也是人工智能研究的热门主题。定性时空推理正是在这两个问题上的尝试。它首先将时间或空间抽象为对象,然后使用定性的描述符号表示空间或时间间的关系,最后研究这些关系之间的变化规律。定性空间推理可以应用于机器人导航、无线传感器网络(WSN),用于处理其中的不确定空间信息。在地理信息系统(GIS)中,定性空间关系作为查询谓词可以用于空间查询,这得益于定性模型与自然语言接近,易于理解的优势。定性空间推理也应用于图像检索和分类,因为兴趣区域间的空间关系可以作为重要的图像特征。方向关系是众多空间关系之一,而有向点关系代数又是方向关系模型中极为优秀的一个。有向点关系代数(Oriented Point Relation Algebra,OPRA)研究空间中物体之间的方向关系以及方向关系之间的推理问题。它把空间对象建模为带方向的点,称为有向点。然后通过两个有向点之间的连线与有向点自身方向之间的两个夹角来表示方向关系,当然对于特殊情况有特殊的处理。有向点关系代数是一个定性关系模型,它在使用夹角时,把角度或角度区间用一个整数代号来表示。这使得它具有以下几个优势:(1)与人们认知方向的一般模式相吻合。例如,人们走在马路上时说,“前方”有一辆车,十字路口“左”转,这里的“前”与“左”可以看做一个角度区间的代号。(2)可以从各种数据中提取信息建模,例如,文本、语音、摄像头等,当然使用更为精确的GPS也是可以的,这就使得有向点关系代数成为一个可以广泛使用的模型。(3)使用有向点关系代数表示的方向关系易于理解,例如在二维空间,对于粒度为1的模型,其方向代号0,1,2,3分别代表上、左、下、右。(4)能适应不同精度需求的场景,有向点关系代数有一个可以调整的粒度参数,如果简单的上下左右不能满足对方向的定位需求,可以使用著名的点钟方向,当然该模型还可以提供更多其他的精度。推理问题是关系模型的一个重要问题。它使用已知的关系求取未知的关系。假设空间对象A和B相互可见,B和C相互可见,但是A和C由于各种原因相互不可见。这时,可以用已知的关系(A,B),(B,C)推理得出未知的关系(A,C)。这就是推理问题。很多关系模型过于复杂,在其上的推理很难进行,例如Pacheco的Integrating 3D Orientation模型。而有向点关系代数的模型简单,在其上的推理很容易进行。2012年,Mossakowski等人研究了OPRA的复合运算。2014年,王生生等研究了OPRA的多粒度复合推理,使得OPRA推理可以应用于任意混合粒度之间。现有的工作大都是在二维空间中进行的,涉及的对象也只有三个,场景多数也是静态的。而现实场景常常是三维的,也常常涉及更多的对象,同时需要处理的场景也常常是动态的,这就需要新的模型和推理方法。本文针对这些问题展开了如下讨论:(1).三维空间中的有向点表示与三维有向点关系代数模型(Oriented Point Relation Algebra in 3-Dimension,OPRA3D)(2).OPRA3D的复合推理(3).涉及多个对象的动态的OPRA3D关系的表示和推理对于OPRA3D模型的表示,本文从有向点的建模出发,逐步建立整个表示模型。对于OPRA3D的复合推理,本文给出了三维空间的两个几何约束及其定性化形式,从而使用这两个约束构造了OPRA3D的复合推理算法,同时,本文还简单讨论了OPRA3D的多粒度推理问题。在面对多对象动态场景时,OPRA3D也能发挥作用,本文提出了OPRA3D关系网络及其序列描述这种场景中对象间的方向关系,提出了关系网络的时空推理来处理多对象动态场景中的推理问题。最后,本文讨论了在工程中使用OPRA3D推理算法需要考虑的一个问题,并给出一个模拟实验来验证OPRA3D网络时空推理的有效性。本文的建模方法和推理算法在处理三维空间中物体的方向关系时具有潜在价值。在机器人导航、无人机导航、太空导航、战场分析等领域,,本文的方法有望发挥重要作用。
[Abstract]:Space and time are an unavoidable problem in the human understanding of the world. It is also a hot topic in the research of artificial intelligence. Qualitative spatio-temporal reasoning is an attempt on these two problems. It first abstracts time or space as an object, and then uses qualitative description symbols to express the relationship between space or time, and finally studies the changes between these relationships. Qualitative spatial reasoning can be applied to robot navigation and wireless sensor networks (WSN) to deal with uncertain spatial information. In geographic information system (GIS), qualitative spatial relations can be used as query predicates for spatial queries, which benefit from the proximity of qualitative models to natural languages and the predominance of easy understanding. Qualitative space is the advantage. Inter reasoning is also applied to image retrieval and classification, because the spatial relationship between interested regions can be regarded as an important image feature. The direction relation is one of the many spatial relationships, and the directed point relation algebra is a very excellent one in the direction relation model. The Oriented Point Relation Algebra (OPRA) research space The reasoning problem between the direction relation and the direction relationship between the objects. It models the spatial object as the point with direction, which is called the directed point. Then, it expresses the direction relationship by the two angles between the connection lines between two directed points and the direction of the directed point, and of course, it has special treatment for special cases. A number is a qualitative relation model, which is represented by an integer code in the angle or angle interval when using the angle. This makes it have the following advantages: (1) it is in accordance with the general pattern of people's cognitive direction. For example, when people walk on the road, there is a car ahead, the intersection "left", the "front" here. And "left" can be regarded as the code name of an angle interval. (2) it is possible to extract information from various data, such as text, voice, camera, etc., of course, using a more precise GPS, which makes the directed point relation algebra a widely used model. (3) use the direction of the directed point relation algebra. The system is easy to understand, for example, in a two-dimensional space, for a model with granularity 1, its direction code 0,1,2,3 is represented, left, lower, right. (4) can adapt to different precision requirements. There is an adjustable granularity parameter for the point relation algebra. If simple up and down is not enough to meet the orientation requirement of the direction, it can be used famous A and B are visible to each other, but B and C are visible to each other, but A and C are invisible to each other for a variety of reasons. Then, we can use a known relationship (A, B), (B, C) inference is an unknown relationship (A, C). This is a reasoning problem. Many relational models are too complex, and the reasoning on it is difficult to carry out, such as the Integrating 3D Orientation model of Pacheco. The model with the directed point relation algebra is simple, and the reasoning on it is easy to carry out.2012 years, Mossakowski and others have studied the complex operation.201 of OPRA. In the 4 years, Wang Shengsheng has studied the multi granularity complex reasoning of OPRA so that OPRA reasoning can be applied to any mixed granularity. Most of the existing work is carried out in the two-dimensional space, only three objects are involved, and most of the scenes are static. The real scene is often three-dimensional, often involving more objects and needs at the same time. The processing scene is also often dynamic, which requires new models and reasoning methods. This paper discusses these problems as follows: (1) the complex reasoning of the directed point representation in three-dimensional space and the Oriented Point Relation Algebra in 3-Dimension, OPRA3D (2) (3) (3). It involves multiple objects. The representation and reasoning of dynamic OPRA3D relations for the representation of the OPRA3D model, this paper starts from the modeling of the directed point, and gradually establishes the entire representation model. For the complex reasoning of OPRA3D, this paper gives two geometric constraints and the qualitative forms of the three-dimensional space, and then constructs a compound inference algorithm of the OPRA3D by using these two constraints. At the same time, this paper also briefly discusses the multi granularity reasoning problem of OPRA3D. In the face of multi object dynamic scenes, OPRA3D can also play a role. In this paper, the OPRA3D relation network and its sequence are proposed to describe the direction relation among the objects in this scene, and the spatio-temporal reasoning of the relational network is proposed to deal with the reasoning problem in the multi object dynamic scene. Finally, this paper discusses a problem that needs to be considered in the use of OPRA3D reasoning algorithm in engineering, and gives a simulation experiment to verify the effectiveness of OPRA3D network spatiotemporal reasoning. The modeling method and inference algorithm in this paper have potential value when dealing with the direction relation of objects in three-dimensional space. In the field of space navigation and battlefield analysis, the method of this paper is expected to play an important role.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】