Research On Combining Direction Relation With Topological Relation For Qualitative Spatial Reasoning

Qualitative spatial reasoning uses algebraic methods to describe spatial relations, andto reserch the problems of the composition reasoning and so on between spatial relations.Qualitative spatial reasoning plays an important role in the field of sptial database, theinterpretation of remote sensing image, geographic information system, the understandingof natural language and so on. Previous research works focused on the single type of spatialrelationship reasoning. For example, reasoning only between topological relations or onlybetween direction relations. However, with the research and the need for solving practicalproblems in recent years, combining a variety of spatial relations for reasoning is becomingnew research hotspots. Direction relation and topological relation are two importantrelations in spatial relations. So combining direction relation and topological relation forreasoning has a great practical significance.Although combining direction relation and topological relation for reasoning has priorknowledge, we still find some questions through analysis and summary as follows. Theprevious relative works focused on the research of combining single tile direction relationwith topological relation for reasoning, which were lack of the research of combiningmulti tile direction relation with topological relation. Most of these works putted attentionon the research of some aspects of it, which were lack of scientific method of reasoning.To address these issues, this thesis undertake the research and disscussion based oncombining the model of cardinal direction relation with the RCC8 model of topologicalrelation for reasoning. Based on the analysis and summary on the current situation of theresearch of combining direction relation and topological relation for reasoning, this thesiselaborates the method of combining direction relation and topological relation for reasoningsystematically and advances the relevant theorems, algorithms and the implements for them.The specific works and research results of this thesis are as follows:(1)We introduced the background and significance of this thesis. Then, we analyzedand summarized the current situation of the research of combining direction relation andtopological relation for reasoning. (2)We introduced the theoretical background in which this thesis involved. There is anintroduction on the knowledge of the model of cardinal direction relation. The model ofcardinal direction relation is the most commonly used model recently. It is the one of themost accurate models to describe the direction relation now. There is an introduction on theRCC8 model of topological relation. The RCC8 model of topological relation is recognizedas the best model of the models which designed to describe topological relation at themoment. We introduced the composition of topological relations based on the RCC8, whichis regarded as the one of the most classic theory in the field of spatial reasoning deduced byRandell. We introduced the existential composition and the comsistency based composition.Then we introduced the method of combining single tile direction relation which advancedby XieQi. The method provided a guideline for this thesis for discussing combining generaldirection relation and topological relation for reasoning.(3)We analyzed the constraint that direction relation towards topological relation, anddefine the operator Constraint_D_to_T to express the constraint. In dealing with the theconstraint, we divided the direction relation(D) into three situations: (1)B?D; (2)D=B;(3)B∈D, D≠B. We discussed the constraint separately in each case. For each case, weadvanced the relevant theorems and gave the proof of them. On that basis, we gave thealgorithm TDT to calculate the result set of the composition of topological relation withdirection relation for reasoning topological relation and the algorithm DTT to calculate theresult set of the composition of direction relation with topological relation for reasoningtopological relation. Finally, we encoded the RCC8 composition table with CD code by theorder of DC, EC, PO, TPP, NTPP, TPPi, NTPPi, EQ with binary and displayed them withdecimalist. With the OR operation of CD code we could complete the union operation ofthe composite result set of topological relation in algorithm TDT and DTT. With algorithmTDT and DTT, the combining direction relation with topological relation for reasoningtopological relation has been completed.(4)We researched the method of combining direction relation and topological relationfor reasoning direction relation respectively from two aspects. One is the composition ofdirection relation with topological relation. The other is the composition of topologicalrelation with direction relation. In dealing with these two aspects, we discussed thecombining method classificated by the topological relation. On that basis, the algorithmDTD_TppiOrNtppi_NB, DTD_TppiOrNtppi_CB, DTD_TppOrNtpp, DTD_PE, TDD_TppiOrNtppi, TDD_TppOrNtpp, TDD_PO and TDD_EC are advanced to calculate thecomposite result set of direction relation after composing. By the algorithms mentioned above, the combining direction relation with topological relation for reasoning directionrelation has been completed.(5)We disigned and implemented combining direction relation with topologicalrelation for reasoning system. The system implemented the algorithm that this thesismentioned. With the result of the system's running, we verified the correctness of thealgorithms. The system is developped by Microsoft Visual Studio 2008 using C++ for itsprogram language. This system which based on the architecture of MVC separated logicalprocess from GUI. By doing this, the system makes itself have a higher running efficiency.By functionality, the system has four GUIs. Each GUI supplies a good input interface. Afterthe input of the spatial relation by the user, the system calculates the composite result setand displays the result to the user.This thesis researched and discussed the combining direction relation with topologicalrelation for qualitative spatial reasoning based on the model of cardinal direction relationand the RCC8 model of topological relation. In the research of combining direction relationwith topological relation for reasoning topological relation, the method advanced by thisthesis abandon the traditional reasoning method which focused on single tile directionrelation or researched single tile direction relation first and then multi tile direction relation.By divided the direction relation into some classes by key direction relation B, the methodadvanced by this thesis solved the problem of incomplete and inprecise reasoning resultwhich existing research works have. In the research of combining direction relation withtopological relation for reasoning direction relation, this thesis provided the specificreasoning method for each case, and implemented the relative specific algorithms. By doingthis, this thesis solved the problem which most reasoning method of existing researchworks were not comprehensive and the reasoing result were biased. The algorithms whichadvanced by this thesis verified by the experiment system, can make combining directionrelation with topological relation for reasoning correctly. So the research highlights of thisthesis can be used in field of spatial database, geographic information system, robot visionand some other fields which need to do reasoning jobs by combining two aspect of spatialinformation direction relation and topological relation. So the research highlights of thisthesis have both theoretical and practical benefits.