Research On Topological Relation Models Between Multiple Spatial Regions

Spatial reasoning is an important branch of Artificial Intelligence. It has turned out to be an interdisciplinary research issue involving disciplines like logic, algebra, topology and graph theory. Over the past three decades, the research on spatial reasoning is extremely active, which is one of the fundamental aspects in the fields of Geographic Information System, Robot Navigation, Image Processing, Computer Vision and Spatial-temporal Database.The research on spatial relation models plays a significant role in spatial reasoning. Topological relation has turned out to be the fundamental aspect in qualitative spatial reasoning due to its qualitative properties inherently. The existing models of topological relation mainly focus on the representation for simple objects, and only consider the relationship between two spatial objects, which is called binary topological relation. However, the spatial objects are normally complex, and the number of objects involved is far beyond two. At present, the research on multiple spatial objects is usually based on the models of binary topological relation, through which the global topological relations between multiple spatial objects are derived from the local binary topological relations between each pairwise objects. However, there have been some limitations of this method when applying in the practical applications:the topological relations between multiple spatial objects can only be partially described, thus the expressiveness is relatively low and the completeness is not satisfied. Therefore, it is not efficient to deal with the topological relation of multiple spatial objects based on binary topological relation models. It has been an urgent research problem on how to establish the topological relation model between multiple spatial objects with higher expressiveness and finer generality.In order to solve this kind of problem, it is investigated in our paper the representation and reasoning of topological relations between multiple spatial objects, and a series of topological relation models are presented:based on the RCC5, the topological spatial relation models between three regions and four regions are respectively established; The research results of the former models are extended to n regions, thus the topological spatial relation models between n regions is constructed. On the basis of RCC5and RCC8respectively, the topological relation models of complex regions such as concave region, region with holes and broad boundary region, which are considering as the composite regions of multiple simple regions that satisfying certain constraints, are presented.The research work included in this paper is as follows:(1) Topological relation model between three simple regions based on RCC5The classical4-intersection matrix is extended to represent the five basic binary topological relations of RCC5. The8-intersection cube matrix is defined to describe the topological relation between three simple regions simultaneously, which is called ternary topological relation. Two reasonable constraints are proposed to omit all the impossible ternary topological relations, based on which109ternary topological relations are derived between three simple regions. The illustrations of every ternary relation are given, and the completeness and exclusiveness of the derived relations are also verified. Comparing with the extended4-intersection matrix model, the8-intersection cube model is more expressive by distinguishing other more55topological relations. As the property for describing the topological relations between three regions at the same time, the8-intersection cube model can be used to check the consistency problem of binary topological relations between three objects. At last, the topological relation between concave region and simple region is discussed by considering the concave region as two simple regions between which the topological relation TPP holds.(2) Topological relation model between four simple regions based on RCC5The16-intersection matrix is defined to represent the topological relation between four simple regions, which is called ternary topological relation. The reasonable constraints for eliminating all the impossible ternary topological relations are given. According to the constraints,32406ternary topological relations are derived by programming procedure. It is shown that all the existing ternary topological relations are involved in this relation set, of which the completeness and exclusiveness are verified. Comparing with the method based on binary topological relation, the16-intersection model can distinguish more refined topological relations, and thus is more expressive. The16-intersection model can be used for checking the consistency problem of binary (or ternary) topological relations between four spatial objects. Two kinds of application cases of quaternary topological relation model are discussed. Firstly, the topological relation model between a concave region and a region with a hole is presented by considering the concave region (region with a hole) as two simple regions where the topological relation TPP (NTPP) holds. Lastly, the topological relation model between a region with two holes and a simple region is presented by considering the region with two holes as three simple regions where the nested topological relation NTPP holds.(3) Topological relation model between n simple regions based on RCC5In order to improve the generality of topological relation model between multiple spatial regions, the topological relation models between three and four regions are analyzed, and the research results are extended to n regions. The2n-intersection matrix is defined by introducing the concept of tensor product to represent the topological relation between n (n≤6) simple regions at the same time. The properties of2n-intersection model are analyzed, based on which the exclusiveness and completeness of this model are verified. It is validated that the result of2n-intersection model (n=3,4) are consistent with the result of8-intersection cube model and16-intersection model respectively.(4) Topological relation model between broad boundary region and simple region based on RCC8By considering the undetermined region as the region with broad boundary, the topological relation model between a broad boundary region and a simple region is proposed. The broad boundary region can be divided into two simple regions where the topological relation NTPP holds, thus the problem is transformed to the topological relation model between three simple regions based on RCC8. The27-intersection model is defined to describe the ternary topological relation which considers the boundary of spatial object. Based on the27-intersection matrix,23topological relations between a broad boundary and a simple region are derived, of which the conceptual neighborhood graph is also given. The reasoning formalism of27-intersection model is established, the composition table is given. The model presented in our paper is more expressive than that of Clementini, since there are more9topological relations that can be distinguished in our model.