ISSN 1000-1239 CN 11-1777/TP

• 论文 • 上一篇    下一篇


王生生 刘 杰 谢 琦 刘大有   

  1. (吉林大学计算机科学与技术学院 长春 130012) (吉林大学符号计算与知识工程教育部重点实验室 长春 130012) (
  • 出版日期: 2009-11-15

A Buffer Based Extensional Model for Topological Relation and Its Application

Wang Shengsheng, Liu Jie, Xie Qi, and Liu Dayou   

  1. (College of Computer Science and Technology, Jilin University, Changchun 130012) (Ministry Education Key Laboratory of Symbolic Computing and Knowledge Engineering, Jilin University, Changchun 130012)
  • Online: 2009-11-15

摘要: 定性空间推理在人工智能等领域有着广阔的应用前景,但目前单方面空间关系研究较多,多方面结合研究较少,这与实际应用需求不符.由于各类空间关系具有独立性,需要找到适当的理论将它们融合,目前对于拓扑、距离结合模型的研究还不够充分.针对缺乏基本关系可处理且易于在GIS系统中实现的模型等情况,提出了一种扩展拓扑关系模型BERCC.BERCC源于RCC理论,其主要思想是通过考虑缓存区之间的拓扑关系来提高模型表达能力,同时能表达一定程度的距离信息.推导了BERCC的弱复合表,证明了BERCC基本关系是可处理的,给出了一个包括全集关系和基本关系的可处理子集,在此基础上实现了约束满足推理算法.最后,基于该理论和方法实现了一个实验系统,进一步验证了模型及算法的正确性和实用性.

关键词: 定性空间推理, 区域连接演算, 缓冲区, 约束满足问题, 结合空间关系

Abstract: Qualitative spatial reasoning (QSR) is promising for applications in artificial intelligence and other fields. Much research work bas been done on single spatial relation aspect, while little research focused on integration of two or more aspects. This does not accord with the real world applications, where several aspects are usually involved together. Since different aspects of space are often dependent, it is needed to establish more elaborate formalisms that combine different types of information. The researches on combining topology and distance are not sufficient now. And the model which is tractable in basic relations and easy to implement in GIS is lacking. An extensional topology relation model, BERCC, is proposed based on RCC theories. Its main idea is to improve express ability by using the topological relation of buffers. Some distant information is included in the model. The weak composition table of BERCC is deduced. The basic relations of BERCC are proved to be tractable. The tractable subset of BERCC including basic and full relations is given. A constraint satisfaction reasoning algorithm of BERCC is implemented. Finally, an experimental system is developed with the above theories and methods. The correctness and practicability of the model and the algorithm are validated by the system.

Key words: qualitative spatial reasoning, region connection calculus, buffer, constraint satisfaction problem, integrated spatial relation