Font Size: a A A

Research On Spatial Directional Relation Models And Integrative Reasoning Of Multi-aspect Spatial Relations

Posted on:2008-06-11Degree:DoctorType:Dissertation
Country:ChinaCandidate:J ChenFull Text:PDF
GTID:1118360242460151Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
Spatial relation, which is an important part of spatial reasoning, geographic information system and computer vision, plays an essential role in spatial querying, spatial analysis, spatial data modeling and map interpretation.As a fundamental relationship, direction describes the relative position of objects and presents the order of spatial entities therefore it is a critical part of spatial reasoning. The present works about direction are focusing on planar space, but seldom on three-dimensional space. With the increasing applications of spatial reasoning, it is inadequate to consider only one aspect of spatial relation, more aspects as a combination are needed. Presently, with more attention paid on the reasoning with two aspect relations, there are few researches about the integrative reasoning.This thesis focuses on the problems of the directional model and integrative reasoning of multi-aspect spatial relations, surveys and analyzes the current qualitative spatial relation models. It also proposes the novel ways to solve the reasoning problems of cardinal direction model with rectangle algebra, meanwhile gives the three-dimensional cardinal direction model, elaborates on the correlations between direction relations and topological relations, and then gives the combinative reasoning method. At last, it proposes the integrative representing and reasoning model of topological, directional and size information.The major contributions, ideas and research results are as follows:⑴The survey of qualitative spatial relation models.This thesis summarizes and analyzes the current qualitative spatial relation models of two different kinds of objects respectively: determinate and indeterminate. In determinate models, it first analyzes the single aspect spatial relations, such as toplogy, direction, distance, shape and moving trajectory; then elaborates on the current works of integrative reasoning with multi-aspect spatial relations. In indeterminate models, according to different ways to process indeterminacy, it divides the models into accurate model, fuzzy set, rough set and probability based models; and explained respectively. The existent problems and future research directions are discussed at the end.⑵Research of cardinal direction relation model based on rectangle algebraTo build the mapping between rectangle relations and basic cardinal direction relations, the thesis defines the concepts of smallest basic rectangular cardinal direction relations and entity cardinal direction relations, which divide the basic relations into 36 equivalence classes corresponding to 36 rectangle relations respectively. Then based on the operations of rectangle relations, the algorithms of inveresing and composing basic cardinal direction relations as well as the proofs are given. Further, the thesis analyzes the differences between cardinal direction relations and direction relation matrix. It indicates that the intersection of target object and direction tile in cardinal direction relation model must be a region while in direction relation matrix, it can be a point, a line or a region, which leads to 379 pairs of inversing relations over simple regions in cardinal direction relation model, much less than the 2004 pairs in direction relation matrix. According to the basic rectangular cardinal direction relations, it defines the convex cardinal direction relations and proves that the constraint satisfaction problem composed by it can be decided by path-consistent algorithm.⑶The cardinal direction relations in three-dimensional spaceThe current 3D direction models approximate spatial objects either as a point or as a minimal bounding block, which decreases the descriptive capability and precision. Considering the influence of object's shape, this thesis extends the planar cardinal direction model into 3D space by introducing new symbols to represent 3D directonal relations. Based on the correlations between retangle algebra and planar model, it generalizes the associations between block algebra and 3D model and gives the relation computation rules. It discusses the constraint satisfaction problems of the model, and gives the consistency checking algorithm of basic three-dimensional cardinal direction relations over simple objects and compound objects respectively.⑷Combinative reasoning with RCC5 and cardinal direction relations.Most previous works of combing topological and directional information centered on the combination with MBR based direction model or single-tile directions. The directional description is too approximate to do precise reasoning. Different from former research, cardinal direction relation is employed to describe directional information, since it does not discriminate the boundary of objects; RCC5 is introduced to represent topological information. Based on the definitions, the mutual dependencies between basic relations of two formalisms and the detail composing rules are given. An improved constraint propagation algorithm is presented to enforce path consistency, which is formally analogous to the classical path-consistent algorithm, but considering not only the composition of same kind relations but also different kind relations.⑸Integrative reasoning of topological, directional and size information based on MBR Current research about the integrative reasoning concentrates on the reasoning with two aspect relations, such as topology and direction, topology and size, distance and direction. It lacks of the integrative reasoning over three or more aspect spatial relations. The thesis proposes the method to represent the size of a region by its projections on each axis, analyzes the correlations between interval relations and topological as well as directional relations, then presents an integrative model of topology, direction and size information based on extended rectangle relations. Moreover it also discusses the constraint satisfaction problems of the hybrid constraints.To sum up, the survey of qualitative spatial relation model presented in this paper sets the direction for the further working of spatial relation models. The research of directional models improves the works of cardinal direction relation model. More importantly, the method of reasoning cardinal direction relations based on rectangle algebra is extensible on spatial dimensionality, and it also provides reference to spatio-temporal reasoning model. The study of integrative reasoning with multi-aspect spatial relations develops the previous works and makes up the deficiency of lacking integrative reasoning with three or more aspect relations. The results of the thesis are of both theoretical and practical benefit to further researches of formalized modeling cardinal directional relations, integration of multi-aspect spatial relations, geographic information system and spatial database.
Keywords/Search Tags:Qualitative Spatial Reasoning, Spatial Relations, Integrative Reasoning with Multi-aspect Spatial Relations, Cardinal Direction Relations, Topological Relations, Interval Algebra, Rectangle Algebra, Block Algebra, Inversing, Composing
PDF Full Text Request
Related items