A Qualitative Model of Directional Relations Based on Topological Constraint

Abstract

Abstract:

Directional relation is one of the most important characters of spatial objects and is useful for spatial retrieval, analysis and reasoning. For line and area reference objects, the directional reference is distinct in the different topological area. However, existing models ignore this difference and represent the direction relations based on the same reference in the whole region of MBR (minimum bounding rectangle). To overcome the problems of direction-relation representation in the MBR of reference object, this paper extend the model of direction-relation matrix and propose a new model based on topological restraint. The new model, called the hierarchical direction-relation matrix based on topological restraint, retains three direction-matrixes with empty and non-empty tiles, which record direction-relation codes for three topological regions. The new qualitative model is based on the topological restraints to direction-relation definition, in which (1) the minimum bounding rectangle of reference object is decomposed into three topological regions (i.e. exterior, boundary and interior); (2) topological references are defined to discribe the alteration of directional reference in three topological regions; (3) three direction-relation matrixes (i.e. exterior, boudary, interior direction-relation matrix) are utilized to represent the directional relations of three topological regions; and (4) a hierarchical calculative approach is proposed for discription of direction relations between different topolical spatial objects to improve the computational efficiency. The new model overcomes the discription difficulty of directional relations bewteen objects of complex topological relations and improve the accuracy and veracity of direction relations models.

Key words: Directional relations, Qualitative Description, Minimum bounding rectangle of reference object, Topological reference for direction-relation, Direction-relation hierarchical matrix model based on topological reference

CLC Number:

P208

References

[1]. LI Deren, ZHU Qing, ZHU Xinyan, SHUI Haigang. Task-Oriented remote sensing information focusing Service [M]. Beijing: Science Press, 2011. (李德仁, 朱庆, 朱欣焰, 眭海刚. 面向任务的遥感信息聚焦服务[M]. 北京: 科学出版社, 2011.)
[2]. CHENG Qimin. Remote Sensing Image Retrieval Technologies [M]. Wuhan: Wuhan University Press, 2011. 16-16.(程起敏. 遥感图像检索技术[M]. 武汉：武汉大学出版社, 2011. 16-16.)
[3]. YAN Haowen. On Theories of Spatial Directional Relationships [M]. ChengDu: 闫浩文, 2003.空间方向关系理论研究[M]. 成都: 成都地图出版社, 2003.
[4]. Kulik L., Klippel A. Reasoning about cardinal directions using grid as qualitative geographic coordinates [C]. Spatial Information Theory-Cognitive and Computational Foundations of Geographic Information Science COSIT′99, Stade, Germany, C. Freksa and Mark D., Eds., Lecture Notes in Computer Science, 1999, 1661: 205-220.
[5]. Frank. Qualitative spatial reasoning: cardinal directions as an example [J]. International tree-an Intelligent Graphical Zoom. Computers & Graphics, 1996, 18(6): 823-829.
[6]. Goyal R. K. Similarity assessment for cardinal directions between extended spatial objects [D]. The University of Maine, 2000.
[7]. Haar R. Computational Models of Spatial Relations[R]. Technical Report: TR- 478, MSC - 72 - 03610, Computer Science, University of Maryland, College Park, MD,1976.
[8]. Peuquet D., Zhan C.X. An algorithm to determine the directional relationship between arbitrary - shape polygons in the plane[J]. Pattern Recognition, 1987, 20 (1):65- 74.
[9]. Abdelmoty A.I, Williams M.H. Approaches to the representation of qualitative spatial relationship for geographic database [C]//In: M. Molenaar and S de Hoop(eds.), Proceedings of Advanced Geographic Data Modeling, Netherlands Geodetic Commission,1994, 40: 204- 216.
[10]. Hong. Qualitative Distance and Direction Reasoning in Geographic Space [D]. Department of Surveying Engineering, University of Maine, Orono, 1994.
[11]. Shekhar S., Liu X. Direction as spatial object: a summary of results [C]. The sixth International Symposium on Advances in Geographic Information Systems, Washington. 1998, 69-75.
[12]. XIA Yu, ZHU Xinyan, LI Deren, QIN Kun. Research on spatial directional relation description mode [J]. Science of Surveying and Mapping, 2007, 32(5): 94-97.(夏宇, 朱欣焰, 李德仁, 秦昆. GIS空间方向关系形式化描述模型分析[J]. 测绘科学, 2007, 32(5): 94-97.)
[13]. CAI Jianhong, LI Deren. Research on Cone shaped Models of Cardinal Direction Relations Considering Positional Uncertainty of Multiple Spatial scale Data [J]. Geomatics and Information Science of Wuhan University, 2007, 32(8): 735-739. (蔡剑红, 李德仁. 多尺度下的不确定性空间方向锥形模型研究[J]. 武汉大学学报(信息科学版), 2007, 32(8): 735-739.)
[14]. DENG Min, LIU Wenbao, LIN Junjie, SUN Dian. Computational Model of Spatial Direction Relations in Vector GIS [J]. Journal of Remote Sensing, 2006, 10(6): 821-828. (邓敏, 刘文宝, 李俊杰, 孙电. 矢量GIS空间方向关系的演算模型[J]. 遥感学报, 2006, 10(6): 821-828.)
[15]. CHEN Jun, ZHAO Renliang. Spatial relation s in GIS: a survey on its key issues and research progress [J]. Acta Geodaetica et Cartographica Sinica, 1999, 28(2): 95-102. (陈军, 赵仁亮, 1999. GIS空间关系的基本问题与研究进展[J]. 测绘学报, 1999, 28(2): 95-102.)
[16]. Chang S.K., Shi Q.S. and Yan C.W., 1987. Iconic indexing by 2-D string. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(6): 413-428.
[17]. Chang S.K. and Jurgert E., 1996. Symbolic projection for image information retrieval and spatial reasoning [M]. Academic Press, London.
[18]. Mukerjee A., Joe G. A qualitative model for space [C]. Eighth National Conference on Artificial Intelligence, Boston, MA,1990, 2:721-727.
[19]. DU Shihong. Research on Theoretics and Methods of Fuzzy Description and Composite Reasoning of Spatial Relations [D]. Beijing: Graduate University of Chinese Academy of Sciences, 2004. (杜世宏. 空间关系模糊描述及组合推理的理论和方法研究 [D]. 北京: 中国科学院研究生院, 2004.)
[20]. HE Jianhua, LIU Yaolin. An Integrated Model for Topology & Direction Relation Reasoning [J]. Acta Geodaetica et Cartographica Sinica, 2009, 33(2): 257-260. (何建华, 刘耀林.GIS中拓扑和方向关系推理模型[J]. 测绘学报, 2009, 33(2): 257-260.)
[21]. DENG Min，XU Rui，LI Guang-qiang, ZHAO Wei. Integrated representation of region-region spatial relations in GIS [J]. Computer Engineering and Applications, 2009, 45(2):39-43. (邓敏, 徐锐, 李光强, 赵伟.GIS面目标间空间关系的集成表达方法[J]. 计算机工程与应用,2009, 45(2): 39-43.)
[22]. Salamat N., Zahzah EH. On the improvement of combined fuzzy topological and directional relations information [J]. Pattern recognition, 2012, 45(4): 1559-1568.
[23]. Egenhofer M. J. Reasoning about Binary Topological Relations [C]. Advances in Spatial Databases, 2nd Symposium, SSD’ 91 Proceedings, 1991, 143-160.
[24]. J.M. Ware, C.B. Jones, and G.L. Bundy. A triangulated spatial model for cartographic generalisation of areal objects[C]. Springer-Verlag Lecture Notes in Computer Science, 1995, 988:173-193.
[25]. CHEN Tao, AI Tinghua. Automatic Extraction of Skeleton and Center of Area Feature[J]. Geomatics and Information Science of Wuhan University, 2004, 29(5): 443-446. (陈涛, 艾延华.多边形骨架线与形心自动搜寻算法研究[J]. 武汉大学学报(信息科学版), 2004, 29(5): 443-446.)