Representing And Reasoning About A Model Of Direction Relations Between Indeterminate Regions

A Spatial relation is one of the most important theoretical problems in the fields of Geographic Information System(GIS), Natural language process, Machine Vision System, and spatial relations play an important role in the processes of Spatial Query, Spatial Databases Analysis, Spatial Reasoning and so on.Direction relation is a spatial relation which reflects the relative position between spatial objects. The research on the models of direction relations is mostly based on the representaion and reasoning of crisp boundary regions currently, however, in practical applications, complex spatial regions are widespread existent. With the development of research, considering crisp boundary regions'direction relations merely does not meet the need of the practial applications, so research on spatial relations between indeterminate regions has become popular. There are two aspects on the research of direction relations, representing and reasoning. But by analyzing the proposed indeterminate regions models, some problems can be found: a unified model that covers the complexity of spatial objects has not been proposed, and works are implemented only on the basis of specified model, and there is little work to deal with reasoning problems. In the sides of qualitative reasoning direction relations, the better efficient method of compositon is currently proposed by Skiadopoulos, which can resolve the compositon between crisp regions, but the method of compositon between indeterminate regions has not been proposed.This paper focuses on the research on representing and reasoning about a model of direction relations between indeterminate regions. Sum up the theoretic reasearch in recent years, and based on the direction model proposed by Skiadopoulos, the model of direction relations between indeterminate regions MDRIR is proposed, and introduce the quality and the validation model's constraint and remove the unreasonable situation. Reasoning about MDRIR is also proposed, and realize the compositon algorithm to solve the problem of reasoning about MDRIR.The main work and research results we get in this paper are as follows:First, there is a brief introduction on the research's background, purpose and significance of this paper, sum up and analyze the research theoretical work on the direction relations between regions in recent years, and based on it, analyze the situation about representing and reasoning of direction relation.Second, theoretical basis is introduced that is involved in this paper in detail.Some theoretical basis including some concepts of the model of direction relations matrix, definiton of direction relations, formal representation and the reasoning of direction relations, the problem of existential compositon of relations and consistency-based composition of relations, and the research on the models of direction relations between indeterminate regions is also introduced.Third, the representation about model of direction relations between indeterminate regions MDRIR is proposed; introduce the quality of MDRIR and the validation model's constraint.The model of direction relations matrix is generally acknowledged model which is the most expressive and widespreadly uesd. We improve the model by substituting indeterminate regions for crisp regions, and propose a new model-MDRIR, and introduce its representation. Based on the precise and uncertainty of the broad boundary of indeterminate regions, we divide MDRIR into four types, and give an detailed explanation one by one, this model can uniform deal with crisp boundary regions and indeterminate regions, and we give the constraint regulation implied between direction relations, remove the unreasonable situation, and ensure the valid direction relation composition.Forth, on the basis of the consistency-based composition method involved in direction relations between crisp regions proposed by Skiadopoulos, we use MDRIR to realize reasoning, divide the indeterminate region into internal crisp region and external crisp region, make use of mutual assemble reasoning of direction relations between crisp regions to implement the composition reasoning direction relation between indeterminate regions, and propose a calculate method on MDRIR and prove it to be correct. By analyzing the thought about compositon proposed by Skiadopoulos, we realize the algorithm of atom direction relations composition named com_ss; the algorithm of atom-basic cardinal relations composition named com_sm; the algorithm of basic cardinal relation composition named com_mm, and compose three algorithms to realize the algorithms of crisp regions composition. These algorithms form the composition algorithm of MDRIR'crisp regions. Based on these works, we propose the algorithm of MDRIR'indeterminate regions and ADL language description, and realize this algorithm named com_allf.Fifth, design and implemente the system of the algorithm of MDRIR compositon, and use interface diagram to illustrate system's fuction, the process of operation and results. The tools of the system are Microsoft Visual Studio 2008, development language is language C, based on Microsoft basic class databases MFC. This system can get the correct composition result through inputting two valid direction relations'values which based on the constraint regulation.This paper has studied representing and reasoning about a model of direction relations between indeterminate regions, the current method of direction relations between crisp regions is not fit for indeterminate regions, by improving direction relation matrix model and combining related topology and knowledge about indeterminate regions, we propose MDRIR to deal with the problem of representation and reasoning direction relations between indeterminate regions, the model takes crisp regions as a specific case of indeterminate regions, which can uniformly deal with crisp boundary regions and indeterminate regions, it can intuitively and effectively judge the direction relations between indeterminate regions in accordance with human's acknowledge regularity. On the basis of calculation method of MDRIR composition, it is easily able to resolve the problems of consistency-based composition of direction relations between indeterminate regions, and its results can be showed in the description system intuitively. In this paper, the research work can be used to the application fields, such as Artificial Intelligence, Geographic Information System, spatial databases where need to express and analyze and to process of direction relations between indeterminate regions in applications, and the research results also have some theoretical significance and practical benefits.