Research On Some Problems Of Qualitative Spatial Direction Relations Modeling

Spatial relations, which can describe the spatial information of the objective world, are the keys to many theoretical and practical problems. For its importance in the field of artificial intelligence, spatial relations modeling has been widely applied to geographic information system, robotics navigation and image understanding.As a fundamental relationship, direction can describe the relative position between objects, and plays an essential role in qualitative spatial relations modeling. The present works about direction relations focus on the representation, but seldom on the reasoning and the operation properties, and the inverse operation of basic cardinal direction relations is still an open problem. Moreover, most conventional direction relation models are suitable for the relations between simple spatial objects, not appropriate for the relations between complex objects (e.g. the disconnected regions, the regions with holes or indeterminate boundaries). The representation models, operation properties and reasoning approaches for the direction relations between uncertain objects with indeterminate boundaries are still at preliminary stage.This thesis concentrates on the inverse relations of basic cardinal direction relations between crisp regions and the modeling approaches for direction relations between uncertain regions (DRUR). First, it surveys and analyzes the present works about qualitative direction relations. Based on the model SK and model MBR, an approach for determining inverse relations of basic cardinal direction relations is proposed. Second, the uncertain regions with indeterminate boundaries are represented with board boundary model. Based on rectangular algebra, it analyzes the consistency-based composition between MBR board boundary direction relations, and then the reasoning method based this composition is put forward. Moreover, it also extends the model of MBR board boundary direction relations to improve its representation ability. Finally the constraint rules and a consistency checking algorithm for the DRUR are proposed. The major contributions, ideas and research results are as follows:(1) The survey of qualitative spatial relation modelsThis thesis introduces the research background and significance of the qualitative spatial relations modeling, and some concepts of fundamental spatial relationships. Then it takes the qualitative spatial direction relations as study objects, summarizes and analyses current works from two different aspects respectively:the models of direction relations between crisp regions and the models of DRUR. Finally the existent problems and future research directions are discussed.(2) The survey of qualitative spatial direction relational algebrasThis thesis introduces three famous algebras for qualitative spatial direction relations: interval algebra, rectangle algebra and cardinal direction relation calculus. The fundamental concepts and operations (such as intersection, union, composition) of these three algebras are summarized respectively.(3) The inverse relations of basic cardinal direction relationsThe determination method for inverse relations of basic cardinal direction relations, which is still an open problem in qualitative direction relations modeling, is researched in this thesis. A quadruple model of basic cardinal direction relation is proposed. Then, based on this model, a basic cardinal direction relation R can be transferred into loc(R). Moreover, the constraints between R and loc(R), loc(R) and loc-1(R) as well as loc-1(R) and inv(R) are analyzed. On this basis, a new determination method for the inverse relation is put forward, which can capture all the inverse relations of basic cardinal direction relations including single tile, multi-tile and rectangular relation.(4) Modeling for direction relations between uncertain regions based on MBRThis thesis discusses the main causes of indeterminate spatial relations with uncertainty. Then it introduces the research situation and existent problems of spatial direction relations modeling between uncertain regions. For the uncertain regions with indeterminate boundaries, the indeterminate boundaries are represented with broad boundaries. The DRUR are described by MBR-based cardinal direction relations and rectangle algebra, then we study the consistency-based composition of DRUR, and a computation method for this composition is put forward, whose correctness is formally proved.(5) Reasoning direction relations between uncertain regionsA reasoning approach for DRUR is proposed in this thesis. DRUR are described with board boundary direction relations, which are the combinations of basic cardinal direction relations. Then the constraints rules implied in board boundary direction relations are analyzed. Moreover, the consistency-based composition of DRUR is defined, and a method is put forward for calculating this composition.(6) Consistency checking for direction relations between uncertain regionsThe board boundary direction relations constraints are formally defined, and their consistency checking problem is discussed in this thesis. A CSP based on board boundary direction relation constraints are transformed into a CSP based on cardinal direction relation constraints, then an improved consistency checking algorithm is proposed, whose correctness and computational complexity is proved at the end.