Research On Modeling And Similarity Of Qualitative Direction Relations Based On The Direction Relation Matrix

Spatial reasoning is an important branch of artificial intelligence, it is also one of themost basic theoretical issues in the high-tech fields of machine vision, autonomous robotnavigation, image retrieval and smart home etc.. Qualitative spatial relation is the mainresearch content of spatial reasoning.Direction relation is one of the most basic and the most applicable spatial relations; it isalso a hot issue of spatial reasoning in recent years. Modeling and similarity assessment aretwo very important research contents of direction relations. At present, methods of research onqualitative direction relations mainly include algebra and logic, the algebraic method is verypopular because of its expressive ability and the high efficiency of its algorithms, the directionrelation matrix is the most representative model. Existing models mostly concentrated in howto express the relationships, reasoning is rare and lack of formal reasoning methods; most ofthe existing research is for the ideal spatial objects, we always ignore the complexity anduncertainty of the real world; related studies are all carried out at the theoretical level, but lackof practical application-oriented research etc.Based on direction relation matrix, this paper studies the modeling and similarityassessment of direction relations, promotes formal direction relation model and a series ofsimple reasoning, similarity assessment algorithms. The main results of this dissertation aresummarized as follows.(1) Aim at the low level of formality of the reasoning algorithms of direction relationmatrix, and the problem of these algorithms cannot be implemented. We refine the directionrelation matrix to expand its expressive ability and establish the corresponding relationsbetween direction relation matrix and rectangular algebra to improve its level of formality. Onthis basis, reasoning algorithms of direction relation matrix are proposed: the compositionalgorithm Composing and the pairwise-consistency checking algorithm PC-Checking. Theimplementation of these two algorithms improves the practicality of the theory of directionrelation reasoning.(2) Aim at the limitation of expressiveness of direction relation matrix and to model thedirection relations between uncertain regions, based on the idea of expanding the directionrelation matrix given by Cicerone, the direction relation matrix of regions with broad boundaries DRMRB is proposed. The constraint rules of DRMRB are also presented andcertified, based on these rules, we implement the constraint algorithm Rationality-Con().Comparing with the4-tuples model, we find that DRMRB is as expressive as the4-tuplesmodel, but the constraint algorithm of DRMRB is much simpler and easier to be achieved.Based on DRMRB, the pairwise-consistency checking method is proposed. This problem isstill an open problem, and the traditional method cannot be used for uncertain directionrelations. We establish the corresponding relations between the rectangle DRMRB and therectangle algebra, and then we complete the mutual conversion of the DRMRB with the basicinterval relationships. On this basis, the algorithm of pairwise-consistency checking betweenuncertain direction relations is implemented. The accomplishment of this algorithm solves theproblem of the direction relation matrix cannot handle uncertain direction relations.(3) Aim at existing methods cannot deal with the similarity assessment of qualitativedirection relations and uncertain direction relations, a new approach is proposed. Based on the4-neighbourhood distance graphs of direction relations, the transportation algorithm and theassignment algorithm, the similarity assessment of qualitative direction relations and theuncertain direction relations are given, the assessment algorithms SA-DRM and SA-DRMRBare implemented. The experimental results are used to verify the effectiveness of them, andthe instances can explain the practical value of this work.