方向关系与拓扑关系的组合推理研究
|
摘要
定性空间推理是空间数据库和地理信息系统应用研究中必不可少的组成部分,而随着定性空间推理研究的深入,方向关系与拓扑关系等多种空间关系组合推理成为了定性空间推理的研究热点。目前已有的方向关系与拓扑关系组合的模型和推理方法都存在缺陷和不足,更缺少方向关系与拓扑关系组合网络一致性检验的专门研究。因此,本文对方向关系与拓扑关系的组合推理和一致性检验进行了研究和探索。
首先,基于井字投影模型,结合区间代数和矩形代数理论,提出了空间对象拓扑关系投影区间矩形代数的表示方法,实现了空间对象方向关系和拓扑关系的统一表示。
其次,考虑到组合推理的灵活性,引入了方向关系和拓扑关系的取反运算,基于拓扑与方向间的相互依赖关系,给出了方向关系与拓扑关系的交互表,进而得到了矩形基本方向关系、非矩形基本方向关系及多基本方向关系与拓扑关系组合的推理算法,并给出了推理算法的正确性证明和示例验证。通过对上述三种算法进行分析,给出了方向关系与拓扑关系同质和异质组合推理的通用算法和该算法的正确性证明。
最后,本文对空间对象井字投影模型中的凸关系进行详细分析,给出了空间对象方向关系与拓扑关系组合中凸关系的判断方法和异质约束判断方法,结合凸关系网络定理和路径一致性算法,提出了方向关系与拓扑关系组合网络一致性检验的算法,并对算法进行了复杂性分析和理论性证明,最后,根据算法进行了实验设计,对实验结果进行了详细分析,验证了算法的正确性。
Qualitative spatial reasoning is an absolutely necessary part of the study about the application of spatial database and Geography Information System. With the deepening of qualitative spatial reasoning, reasoning with topological relations, cardinal direction relations etc multi-aspect spatial information has become the focus of qualitative spatial reasoning. The current model and the approaches of heterogeneous composition reasoning of all kinds of direction relations with topological relations have some kind of disadvantages, in addition, the specific studies in consistency checking of the combinatory networks of direction relation and topological. So this paper carries on studies and explores in the direction relation with topological relation combine reasoning and consistency checking.
First of all, based on projection model and combined the rectangle algebra, this paper will propose approaches of rectangle algebra of projective intervals for topological relations of spatial object, having the united rectangle algebra expressing of direction relations and topological relations.
Secondly, taking the flexibility of heterogeneous complex reasoning into account, this paper will introduce inverse to direction relations and topological relations. Based on the Interdependence of direction relations and topological relations, interaction table for direction relations and topological relations will be given. Based on the above-mentioned study, the accurate heterogeneous composition reasoning of rectangular basic direction relations and non-rectangular basic direction relations respectively with the topology relations are solved, and the correctness of the reasoning and example application will also be given. Three algorithms above are analyzed in detail, the common composition reasoning algorithm of direction relations and topological relations is provided.
Finally, convex relations in the projection model of intersecting parallels are analyzed in detail. The judging method of convex relations and heterogeneous restraint in composition with direction relation and topological relation is provided. This method and algorithm of consistency checking for the combinatory networks of direction relation and topological are proposed by combining the convex relation network theorem and path consistency checking algorithm, as well as the corresponding correctness proof and analysis of complexity are given. At the end of the paper, the experiment is designed based on the algorithm. The experimental result shows that the algorithm is correct.
首先,基于井字投影模型,结合区间代数和矩形代数理论,提出了空间对象拓扑关系投影区间矩形代数的表示方法,实现了空间对象方向关系和拓扑关系的统一表示。
其次,考虑到组合推理的灵活性,引入了方向关系和拓扑关系的取反运算,基于拓扑与方向间的相互依赖关系,给出了方向关系与拓扑关系的交互表,进而得到了矩形基本方向关系、非矩形基本方向关系及多基本方向关系与拓扑关系组合的推理算法,并给出了推理算法的正确性证明和示例验证。通过对上述三种算法进行分析,给出了方向关系与拓扑关系同质和异质组合推理的通用算法和该算法的正确性证明。
最后,本文对空间对象井字投影模型中的凸关系进行详细分析,给出了空间对象方向关系与拓扑关系组合中凸关系的判断方法和异质约束判断方法,结合凸关系网络定理和路径一致性算法,提出了方向关系与拓扑关系组合网络一致性检验的算法,并对算法进行了复杂性分析和理论性证明,最后,根据算法进行了实验设计,对实验结果进行了详细分析,验证了算法的正确性。
Qualitative spatial reasoning is an absolutely necessary part of the study about the application of spatial database and Geography Information System. With the deepening of qualitative spatial reasoning, reasoning with topological relations, cardinal direction relations etc multi-aspect spatial information has become the focus of qualitative spatial reasoning. The current model and the approaches of heterogeneous composition reasoning of all kinds of direction relations with topological relations have some kind of disadvantages, in addition, the specific studies in consistency checking of the combinatory networks of direction relation and topological. So this paper carries on studies and explores in the direction relation with topological relation combine reasoning and consistency checking.
First of all, based on projection model and combined the rectangle algebra, this paper will propose approaches of rectangle algebra of projective intervals for topological relations of spatial object, having the united rectangle algebra expressing of direction relations and topological relations.
Secondly, taking the flexibility of heterogeneous complex reasoning into account, this paper will introduce inverse to direction relations and topological relations. Based on the Interdependence of direction relations and topological relations, interaction table for direction relations and topological relations will be given. Based on the above-mentioned study, the accurate heterogeneous composition reasoning of rectangular basic direction relations and non-rectangular basic direction relations respectively with the topology relations are solved, and the correctness of the reasoning and example application will also be given. Three algorithms above are analyzed in detail, the common composition reasoning algorithm of direction relations and topological relations is provided.
Finally, convex relations in the projection model of intersecting parallels are analyzed in detail. The judging method of convex relations and heterogeneous restraint in composition with direction relation and topological relation is provided. This method and algorithm of consistency checking for the combinatory networks of direction relation and topological are proposed by combining the convex relation network theorem and path consistency checking algorithm, as well as the corresponding correctness proof and analysis of complexity are given. At the end of the paper, the experiment is designed based on the algorithm. The experimental result shows that the algorithm is correct.
引文
1 AG Cohn, SM Hazarika. Qualitative spatial representation and reasoning: An overview. Fundamental Informatics, 2001, 46(2):1-29
2郭平.定性空间推理技术及应用研究. [重庆大学博士论文], 2004
3李松,郝忠孝.空间关系推理的研究方法.计算机工程与应用, 2009, 45(19):17-21
4谢琦,刘大有,虞强源,陈娟.定性方向关系模型研究进展.计算机科学, 2006, 33(11):5-9
5 Tarkan Sevilmis, Muhanmmet Bastan, Ugur Gudukbay, Qzgur Ulusoy. Automatic Detection of Salient objects and Spatial Relations in Videos for A Video database System. Image and Vision Computing, 2008, 26(10):1384-1396
6 Yosoon Choi, Seo-Youn Yoon, Hyeong-Dong Park. A 3D GIS Extension for Rock Mass Classification and Fault Zone Analysis in Tunneling. Compuers and Geosciences, 2009, 35(6):1322-1333
7 Egenhofer, R.Golledge. Spatial and Temporal Reasoning in Geographic Information Systems[M]. Spatial Information Systems, Oxford University Press, New York, 1998, 3:1-10
8 P.L.Lin, W.H.Tan. An Efficient Method for the Retrieval of Objects by Topological Relations in Spatial Database Systems. Information Processing and Management, 2002:543-559
9王昱之,杜世宏.空间关系推理方法分类体系.地理与地理信息科学, 2009, 25(3):1-7
10 J.F.Allen. Maintaining Knowledge about Temporal Intervals. Communications of the ACM, 1983, 26(11):832-834
11 Balbiani, P.Condotta and D.Cerro. A Model for Reasoning about Bidimensional Temporal Relations. In Proceedings of Principles of Knowledge Representation and Reasoning, Trento, Italy, 1998:124-130
12谢琦.空间方位关系模型与时空结合推理的研究. [吉林大学博士论文], 2006
13 Sistla A P, Yu C. Reasoning about qualitative spatial relation-ships. Journal of Automated Reasoning, 2000, 25:291-328
14陈娟.空间方向关系模型及多方面空间关系结合推理的研究. [吉林大学博士论文], 2007
15陈娟,刘大有,张长海等. RCC5与方向关系结合的定性空间推理.计算机研究与发展, 2008, 45(1):279-28
16杜世宏.空间关系模糊描述及组合推理的理论和方法研究. [中国科学院博士论文], 2004
17杜世宏,秦其明,王桥. GIS中由多种方向关系推理拓扑关系的方法.计算机辅助设计与图形学学报, 2005, 17(9): 1917-1927
18王净,江刚武,郭锐.一种空间方向关系的细节描述方法.地理空间信息, 2009, 7(3):45-47
19 Sun H B, Li W H. Combining topological and cardinal directional relation information in qualitative spatial reasoning[C]. Adaptive and Natural Computing Algorithms Proceedings of the International Conference in Coimbra, Portugal, 2005, 23(2):152-157
20孙海滨,李文辉.基于结合空间拓扑和方向关系信息的空间推理.计算机研究与发展, 2006, 43(2):253-259
21侯睿.结合方向关系和拓扑关系的约束满足推理.计算机工程与应用, 2008, 44(16):63-65
22 Li S J. Combining topological and directional information for spatial reasoning. Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, 2007: 435-440
23刘大有,胡鹤,王先生,谢琦.时空推理研究进展.软件学报, 2004, 25(8):1141-1149
24 Jochen Renz, Qualitative Spatial Reasoning with Topological Information. LNCS 2293, Springer Berlin, 2002
25 Max.J.Egenhofer, Robert.D.Franzosa. Point-set Topological Spatial Relations. International Journal of Geographical Information Science, 1991, 2:161-174
26 Ivo Duntsch, HuiWang, Steve McCloskey. A relation algebraic approach to the region connection calculus. Theoretical Computer Science, 2001, 25(5):63-83
27 Sanjiang Li, Mingsheng Ying, Yongming Li. On countable RCC models. Fundamenta Informaticae, 2005, 65:329-351
28 Sanjiang Li. On Topological Consistency and Realization. Constraints, 2006, 11:31-51
29 Sanjiang Li, Huaiqing Wang. RCC8 binary constraint network can be consistently extended. Artificial Intelligence, 2006, 170:1-18
30 Max.J.Egenhofer, J.Sharma. Topological relations between regions in R2 and Z2, in Advances in Spatial Databases. The 3rd International Symposium, SSD, 1993:316-336
31 M.Grigni, D.Papadias, C.Papadimitrious. Topological inference in the 14th international joint conference on artificial intelligence. Mellish, Ed.San Francisco: Morgan KaufmannPublishers, 1995:901-906
32 M.J.Egenhofer, R.Franzosa. On the equivalence of topological relations. International Journal of Geographical Information Systcms, 1995, 9(2):133-152
33廖士中,石纯一.拓扑关系的闭球模型及复合表的推导.软件学报, 1997, 8(12):894-900
34 Siyka Zlatanova. 3D Gis for Urban Development. Ph.D disertation, 2000
35 J.Chen, CM Li. A voronoi-based 9-intersection model for spatial relations. International Journal of Geographical Information Science, 2001, 15(3):201-220
36 El-Geresy BA, Abdehnoly AI. Order in Space: A General Formalism for Spatial Reasoning. Int. J. on Artificial Intelligence Tools, 2004, 6(4):423-450
37 Max J. Egenhofer. Spherical Topological Relations. Journal on Data Scmantics, 2005
38 M.Schneider, T.Behr. Topological Relationships between Complex Spatial Objects. ACM Transactions on Database Systems, 2006, 31(1):39-81
39 J.H.OuYang, Q.Fu, D.Y. Liu. A Model for Representing Topological Relations between Simple Concave Regions. International Conference of Computer Science , 2007
40 Andrew U Frank. Qualitative spatial reasoning about cardinal direction. In the 7th Austrian Conference on Artificial Intelligence, 1991:157-167
41 A.U. Frank. International Journal of Geographical Information Systems. Qualitative spatial reasoning: Cardinal directions as an example, 1996, 10(3):269-290
42 Clristian Freksa. Using orientation information for qualitative spatial reasoning. in Theories and methods of spatio-temporal reasoning in geographic space, LNCS 639, Springer-Verlag, Berlin, Heidelberg, New York, 1992
43 Isli, V Haarslev, R.Moller. Combining Cardinal Direction Relations and Relative Relations in QSR. In 8th International Symposium on Artificial Intelligence and Mathematics, 2004
44 A.I.Abdelmoty, H.Williams. Approaches to the representation of qualitative spatial relationships for geographic databases. International GIS Workshop, 1994
45 R.Goyal, M.J.Egenhofer. The Direction-Relation Matrix: A Representation for Direction Relations between Extended Spatial Objects. In The Annual Assembly and the Summer Retreat of University Consortium for Geographic Information Systems Science, 1997
46 R.GoyaI, M.J.Egenhofer. Consistent queries over cardinal directions across different levels of detail. In the 11th International Workshop on Database and Expert Systems Applications, 2000:876-880
47 R.Goya1, M.J.Egenhofer. Similarity of Cardinal directions. In the 7th InternationalSymposium on Advances in Spatial and Temporal Databases, 2001:36-58
48 Serafino Cicerone, Paolino Di Felice. Cardinal directions between spatial objects: the pairwise-consistency problem. Information Sciences, 2004:165-188
49 Yu Liu, Xiaoming Wang, Xin Jin, Lun Wu. On Internal Cardinal Direction Relations , 2005:283-299
50 Spiros Skiadopoulos, Manolis Koubarakis. Composing cardinal direction relations. Artificial Intelligence, 2004:143-171
51 Spiros Skiadopoulos, Manolis Koubarakis. On the consistency of cardinal direction constraints. Artificial Intelligence, 2005, 15(12)91-135
52 Isabel Navarrete, Antonio Morales, Guido Sciavicco. Consistency Checking of Basic Cardinal Constraints over Connected Regions, 2007:495-500
53 Gerevini, J. Renz. Combining topological and size information for spatial reasoning. Artificial Tntelligence, 2002:1-42
54王生生,刘大有,谢琦,王新颖.集成多方面信息的定性空间推理及应用.软件学报, 2003,14(11):1857-1862
55 Sanjiang Li. Combining Topological and Directional Information: First Results. in KSEM 2006
56 Sanjiang Li. Combining Topological and Directional Information for Spatial Reasoning. IJCAI, 2007, 14(11):1647-1651
57 Balbiani, J.F.Condotta and L.F.Cerro. A New Tractable Subclass of the Rectangle Algebra. IJCAI, 1999:442-447
58刘永山,郝忠孝.空间对象方向关系推理的研究.小型微型计算机系统, 2008, 29(8):1458-1466
2郭平.定性空间推理技术及应用研究. [重庆大学博士论文], 2004
3李松,郝忠孝.空间关系推理的研究方法.计算机工程与应用, 2009, 45(19):17-21
4谢琦,刘大有,虞强源,陈娟.定性方向关系模型研究进展.计算机科学, 2006, 33(11):5-9
5 Tarkan Sevilmis, Muhanmmet Bastan, Ugur Gudukbay, Qzgur Ulusoy. Automatic Detection of Salient objects and Spatial Relations in Videos for A Video database System. Image and Vision Computing, 2008, 26(10):1384-1396
6 Yosoon Choi, Seo-Youn Yoon, Hyeong-Dong Park. A 3D GIS Extension for Rock Mass Classification and Fault Zone Analysis in Tunneling. Compuers and Geosciences, 2009, 35(6):1322-1333
7 Egenhofer, R.Golledge. Spatial and Temporal Reasoning in Geographic Information Systems[M]. Spatial Information Systems, Oxford University Press, New York, 1998, 3:1-10
8 P.L.Lin, W.H.Tan. An Efficient Method for the Retrieval of Objects by Topological Relations in Spatial Database Systems. Information Processing and Management, 2002:543-559
9王昱之,杜世宏.空间关系推理方法分类体系.地理与地理信息科学, 2009, 25(3):1-7
10 J.F.Allen. Maintaining Knowledge about Temporal Intervals. Communications of the ACM, 1983, 26(11):832-834
11 Balbiani, P.Condotta and D.Cerro. A Model for Reasoning about Bidimensional Temporal Relations. In Proceedings of Principles of Knowledge Representation and Reasoning, Trento, Italy, 1998:124-130
12谢琦.空间方位关系模型与时空结合推理的研究. [吉林大学博士论文], 2006
13 Sistla A P, Yu C. Reasoning about qualitative spatial relation-ships. Journal of Automated Reasoning, 2000, 25:291-328
14陈娟.空间方向关系模型及多方面空间关系结合推理的研究. [吉林大学博士论文], 2007
15陈娟,刘大有,张长海等. RCC5与方向关系结合的定性空间推理.计算机研究与发展, 2008, 45(1):279-28
16杜世宏.空间关系模糊描述及组合推理的理论和方法研究. [中国科学院博士论文], 2004
17杜世宏,秦其明,王桥. GIS中由多种方向关系推理拓扑关系的方法.计算机辅助设计与图形学学报, 2005, 17(9): 1917-1927
18王净,江刚武,郭锐.一种空间方向关系的细节描述方法.地理空间信息, 2009, 7(3):45-47
19 Sun H B, Li W H. Combining topological and cardinal directional relation information in qualitative spatial reasoning[C]. Adaptive and Natural Computing Algorithms Proceedings of the International Conference in Coimbra, Portugal, 2005, 23(2):152-157
20孙海滨,李文辉.基于结合空间拓扑和方向关系信息的空间推理.计算机研究与发展, 2006, 43(2):253-259
21侯睿.结合方向关系和拓扑关系的约束满足推理.计算机工程与应用, 2008, 44(16):63-65
22 Li S J. Combining topological and directional information for spatial reasoning. Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, 2007: 435-440
23刘大有,胡鹤,王先生,谢琦.时空推理研究进展.软件学报, 2004, 25(8):1141-1149
24 Jochen Renz, Qualitative Spatial Reasoning with Topological Information. LNCS 2293, Springer Berlin, 2002
25 Max.J.Egenhofer, Robert.D.Franzosa. Point-set Topological Spatial Relations. International Journal of Geographical Information Science, 1991, 2:161-174
26 Ivo Duntsch, HuiWang, Steve McCloskey. A relation algebraic approach to the region connection calculus. Theoretical Computer Science, 2001, 25(5):63-83
27 Sanjiang Li, Mingsheng Ying, Yongming Li. On countable RCC models. Fundamenta Informaticae, 2005, 65:329-351
28 Sanjiang Li. On Topological Consistency and Realization. Constraints, 2006, 11:31-51
29 Sanjiang Li, Huaiqing Wang. RCC8 binary constraint network can be consistently extended. Artificial Intelligence, 2006, 170:1-18
30 Max.J.Egenhofer, J.Sharma. Topological relations between regions in R2 and Z2, in Advances in Spatial Databases. The 3rd International Symposium, SSD, 1993:316-336
31 M.Grigni, D.Papadias, C.Papadimitrious. Topological inference in the 14th international joint conference on artificial intelligence. Mellish, Ed.San Francisco: Morgan KaufmannPublishers, 1995:901-906
32 M.J.Egenhofer, R.Franzosa. On the equivalence of topological relations. International Journal of Geographical Information Systcms, 1995, 9(2):133-152
33廖士中,石纯一.拓扑关系的闭球模型及复合表的推导.软件学报, 1997, 8(12):894-900
34 Siyka Zlatanova. 3D Gis for Urban Development. Ph.D disertation, 2000
35 J.Chen, CM Li. A voronoi-based 9-intersection model for spatial relations. International Journal of Geographical Information Science, 2001, 15(3):201-220
36 El-Geresy BA, Abdehnoly AI. Order in Space: A General Formalism for Spatial Reasoning. Int. J. on Artificial Intelligence Tools, 2004, 6(4):423-450
37 Max J. Egenhofer. Spherical Topological Relations. Journal on Data Scmantics, 2005
38 M.Schneider, T.Behr. Topological Relationships between Complex Spatial Objects. ACM Transactions on Database Systems, 2006, 31(1):39-81
39 J.H.OuYang, Q.Fu, D.Y. Liu. A Model for Representing Topological Relations between Simple Concave Regions. International Conference of Computer Science , 2007
40 Andrew U Frank. Qualitative spatial reasoning about cardinal direction. In the 7th Austrian Conference on Artificial Intelligence, 1991:157-167
41 A.U. Frank. International Journal of Geographical Information Systems. Qualitative spatial reasoning: Cardinal directions as an example, 1996, 10(3):269-290
42 Clristian Freksa. Using orientation information for qualitative spatial reasoning. in Theories and methods of spatio-temporal reasoning in geographic space, LNCS 639, Springer-Verlag, Berlin, Heidelberg, New York, 1992
43 Isli, V Haarslev, R.Moller. Combining Cardinal Direction Relations and Relative Relations in QSR. In 8th International Symposium on Artificial Intelligence and Mathematics, 2004
44 A.I.Abdelmoty, H.Williams. Approaches to the representation of qualitative spatial relationships for geographic databases. International GIS Workshop, 1994
45 R.Goyal, M.J.Egenhofer. The Direction-Relation Matrix: A Representation for Direction Relations between Extended Spatial Objects. In The Annual Assembly and the Summer Retreat of University Consortium for Geographic Information Systems Science, 1997
46 R.GoyaI, M.J.Egenhofer. Consistent queries over cardinal directions across different levels of detail. In the 11th International Workshop on Database and Expert Systems Applications, 2000:876-880
47 R.Goya1, M.J.Egenhofer. Similarity of Cardinal directions. In the 7th InternationalSymposium on Advances in Spatial and Temporal Databases, 2001:36-58
48 Serafino Cicerone, Paolino Di Felice. Cardinal directions between spatial objects: the pairwise-consistency problem. Information Sciences, 2004:165-188
49 Yu Liu, Xiaoming Wang, Xin Jin, Lun Wu. On Internal Cardinal Direction Relations , 2005:283-299
50 Spiros Skiadopoulos, Manolis Koubarakis. Composing cardinal direction relations. Artificial Intelligence, 2004:143-171
51 Spiros Skiadopoulos, Manolis Koubarakis. On the consistency of cardinal direction constraints. Artificial Intelligence, 2005, 15(12)91-135
52 Isabel Navarrete, Antonio Morales, Guido Sciavicco. Consistency Checking of Basic Cardinal Constraints over Connected Regions, 2007:495-500
53 Gerevini, J. Renz. Combining topological and size information for spatial reasoning. Artificial Tntelligence, 2002:1-42
54王生生,刘大有,谢琦,王新颖.集成多方面信息的定性空间推理及应用.软件学报, 2003,14(11):1857-1862
55 Sanjiang Li. Combining Topological and Directional Information: First Results. in KSEM 2006
56 Sanjiang Li. Combining Topological and Directional Information for Spatial Reasoning. IJCAI, 2007, 14(11):1647-1651
57 Balbiani, J.F.Condotta and L.F.Cerro. A New Tractable Subclass of the Rectangle Algebra. IJCAI, 1999:442-447
58刘永山,郝忠孝.空间对象方向关系推理的研究.小型微型计算机系统, 2008, 29(8):1458-1466