| In all the research methods of Artificial Intelligence, the representation and reasoning of time and space is always one of the most important components. In recent years, spatio-temporal reasoning has become the hot researching directions, which makes it the one of the important researches in Geographic Information System, Robotics Navigation, Image Understanding, Computer Vision and Spatio-Temporal Database.Among the various spatial relations, the topological relation between spatial objects is the most basic one, which is one of the basic problems in the research of qualitative spatial reasoning. Therefore, research on the model of spatial topological relation became the hot issues in spatial reasoning, and has played a very important role in qualitative spatial reasoning. The methods for modeling spatial topological relation are classified into mainly two kinds, i.e. the logic-based ones and the algebra-based ones, in which the most typical models are Region Connection Calculus (RCC) and intersection model. So far, the research on spatial topological relations of simple objects are formed a mature and sophisticated theory system. However, the spatial objects are not simple but complicated in the real world. It is hard for the traditional topological models to satisfy the requirements of practical applications. Thus, it is necessary to set up the models which can describe the spatial topological relation of complicated objects, which would be one of the most important trends in the future development of spatial reasoning. The major problem in developing a useful formalism for reasoning about spatial information is the trade off between expressive power and computational tractability. Whilst Egenhofer's representation does allow for certain inferences to be computed effectively, the scope of the theory is limited. On the other hand, although the formalism presented by Randell et al. is very expressive, since it is presented in 1st-order logic, reasoning in the calculus is extremely difficult. How to build a spatial model of topological relation which is both expressive and has a low computational tractability is one of the directions of our research work. Shape is one of the most important features of object, and is hard to describe in a qualitative way. The shape characteristic is not considered in the traditional spatial relation models which take the object as a whole. The qualitative shape representation has become an important aspect in the field of qualitative spatial reasoning as the rapid development of complex spatial relation modeling.Researches on spatial relation modeling of complex objects are currently focusing on topological relation models and directional relation models, and the work on property researching of complex spatial objects is mainly focusing on the representation of shape feature. This thesis focuses on the research problems of a special kind of complex objects in space, which is spatial concave region. The topological relation and qualitative shape representation of concave regions are surveyed and discussed. The existing models of topological relation and qualitative shape representation of complex objects are surveyed analyzed. With the topological aspects, in order to enhance the expressiveness and practicability of traditional models which take the convex region as representing elements, the algebraic method based RCC62 model which describes the topological relation between simple concave regions and the logical method based RCC62* model are proposed. With the shape aspect, focusing on the the region-based qualitative shape representation methods, an improved method for distinguishing the SameSide relation of two concavities in a concave region is proposed to resovle the problems existing in Cohn's method for qualitative shape representation of concave regions.The major contributions and research results are as follows:(1) The survey of modeling methods on spatial relation of complex objects.Most of the existing methods in spatial relation modeling are limited for describing simple objects, the single spatial relation between simple objects in 2D space. However, the world we lived in is 3D space, the spatial object in it is also complex and there are more than one spatial relation exists in the real world, which we called complex spatial relation. The existing researches on complex spatial relation modeling mainly include the topological relation models of complex objects, the qualitative shape representation of spatial object, the 3D spatial relation models, and the reasoning of combined spatial relation. Focusing on the relative research work on topological relation and shape relation, the first-order based topological models, the modal logic based topological modesl, the algebraic based topological models and the qualitative shape representation models are surveyed and analyzed.(2) RCC62 model for representing and reasoning of simple concave regionsBased on the point set topology theory, the modeling for topological relation of simple concave regions is conducting which includes the following research work: based on 16-intersection matrix, the RCC23 are refined to RCC62. The Conceptual Neighborhood Graph and the Closest Topological Relation Graph of RCC62 are given; reasoning formalism for RCC62 is presented, from which the composition table of RCC62 can derived. There are 39 new relations in RCC62, which is more expressive than RCC23, in which the description for spatial relation is more accurate.(3) The representing system of topological relation model RCC62*On the basis of RCC62 model, the representing system of topological relation formal model is proposed in a modal way, which includes the following research work: based on the interior operator of S4 modal logic and Bennett's modal explanation of convex hull operator, the modal definition of 16-intersection matrix is given; based on the extended intuitionistic 0-order calculus, the basic relations of RCC62 is transformed to a two-tuple structure which composed of both model constraint and entailment constraint, from which the representing system of RCC62* model is derived. The expressiveness of RCC62* is the same as RCC62, yet RCC62* has a more formal representation structure than RCC62.(4) The reasoning system of topological relation model RCC62*Several usual reasoning methods in modal logics are introduced, which include tabuleaux based, resolution based, translation based and sequent calculus based reasoning methods. Based on Gentzen's sequent calculus reasoning method, the reasoning procedure of spatial relation is translated into the validity determination problem of the corresponding sequent of modal formula. The reasoning of spatial relations which are instances of the RCC8 relation set are analysed respectively in a 0-order classic calculus and a 0-order intuitionistic calculus. The modal convex-hull operator is then introduced and the validity testing for certain sequent of modal formula is implemented based on the modal schema of convex-hull operator and Hudelmaier's proof rules. The reasoning system of RCC62 is then established in a modal way.(5) The qualitative shape representation of spatial concave regionsShape characteristic is one of the important features of a spatial object. The qualitative representation method is adopted for characterizing the shape features of objects in spatial reasoning. Among the region-based methods for qualitative shape representation, Cohn's hierarchical method base on connection and convex hull is analyzed; in order to solve the problems existing in Cohn's SameSide predicate, an improved method of qualitative shape representation for SameSide distionction of concavities is presented. The results derived using our improved method is more reasonable.The survey of research contributions in spatial reasoning, direct the further research on spatial relation models of complex object in qualitative spatial reasoning. The research work on topological relations modeling between simple concave regions, have a refinement of the RCC23 model, thus both the expressiveness and practicality of the original model are inhanced. Combined with RCC62 model and Bennett's modal explanation of convex hull operator, the representing system of topological relation model RCC62* is proposed. The reasoning system of RCC62* is also established based on Gentzen's sequent calculus reasoning method. The research work on modeling spatial topological relation in a modal way has the advantage of both expressive and of lower computational complexity. Research on qualitative shape representation makes up the deficiency of lacking effective description of the spatial object itself.In a word, the study results of this thesis are of both theoretical and practical benefit to further researches on modeling topological spatial relation of complex objects, qualitative shape representation of spatial object, modal logic based qualitative spatial reasoning, Geographic Information System and Spatial Database.
|
PDF Full Text Request