空间凹形对象的定性表示及推理方法的研究
摘要
近年来,空间推理已成为人工智能、地理信息系统和时空数据库等相关领域的研究热点。空间关系模型的研究取得了很大进展,目前大多数空间关系的形式化表示及推理都采用逻辑方法和代数方法进行研究。定性空间推理中,最著名的逻辑和代数模型是Cohn等人提出的区域连接演算RCC和Egenhofer等人提出的9-交集模型。
本文围绕空间凹形对象的定性形状、拓扑关系的表示和推理,展开了研究和讨论。主要工作包括:(1)以空间关系的形式化表示为主线,总结和分析了空间凹形对象定性形状、拓扑关系表示的一些主要研究工作;(2)改进Cohn等提出的基于连接和凸壳的定性形状表示法,提出了基于凹处变换的SameSide判断方法(简称方法CTS)及其相应算法;(3)基于RCC23和9-交集模型,提出了模型TSC,用于两个简单凹形区域间拓扑关系的表示及推理;定义了TSC31,并给出其概念邻域图和最小拓扑距离关系图;(4)设计并实现了模型TSC的演示系统。
本文工作能够描述更具一般性、更丰富的空间关系,在一定程度上丰富了空间拓扑关系的表达能力,同时也为拓扑关系复合表的自动推导奠定了理论基础。本文的研究对于定性空间推理、地理信息系统、空间查询语言的研究具有一定的理论意义和应用价值。
In recent years, researches on theory and application on spatialinformation are getting more and more attentions in ArtificialIntelligence(AI), Geographical Information System(GIS), Spatial Databaseand other relating fields. The relations of spatial objects are various, andsometimes rely on the domain specific applications. The research oncognition, description and representation of spatial relations are the basis ofan effective application. At present, there are two main methods on spatialrelation representation: logic-based methods and point-set topology basedmethods.
Topological relation is the most elementary relation in space, and is oneof the basic problems in qualitative spatial reasoning. Qualitative shaperepresentation is one important aspect in qualitative reasoning. Unlike thetraditional quantitative methods, the qualitative shape measures concernmainly on abstracting and representing the qualitative properties of objects'shape. It is meaningful to apply the exiting qualitative spatial methods intothe shape representation. This paper is focused on representation andreasoning about qualitative shape, topological representation of spatialobjects.
The main work and results included in this paper are as follows:
Firstly, the paper summarized and analysed the state of arts inrepresentation about qualitative shape and topological relations of spatialobjects based on the two essential methods in spatial relation description. Itintroduces some basic theories including Allen's interval calculus, RegionConnection Calculus(RCC) and 9-intersection model. The relate researchworks in topological relations of spatial objects are surveyed and analyzed. Itdescribes a hierarchical representation of qualitative shape based onconnection and convexity presented by Cohn, and a process-grammar shape
representation methods proposed by Leyton.Secondly, this paper gave a detailed introduction of a hierarchicalrepresentation of qualitative shape based on connection and convexitypresented by Cohn. We proposed a SameSide deducing method on the basisof concavity transforming, and give the arithmetic description. Based on theessential binary relation 'connection' and the concept of 'convex hull', Cohnhad presented a hierarchical representation of qualitative shape to describemany kinds of concave regions. During the analyzing process, we found thatillogical results would be derived by directly using the SameSide predicatefor some kinds of concave regions. Based on Allen's interval algebra, wepresent a method CTS by distinguishing the type of the concavities makinguse of tangent scanning measure. The results derived from method CTSaccords with people's cognition.Thirdly, on the basis of Cohn's RCC23 and Egenhofer's 9-intersectionmodel, we proposed a model TSC, defined TSC31, and gave the conceptualneighborhood and closest topological relation graph. The RCC formal modeland 9-intersection model are the most typical theory models in therepresentation of spatial topological relations. Combining the idea of the twomethods, we constructed a model TSC. The model consists of two parts,namely the representing system and the reasoning system. Based on RCC23,we defined TSC31 by introducing eight new topological relations, and alsogave the conceptual neighborhood and closest topological relation graph ofTSC31. The model TSC is more expressive than RCC23, the topologicalrelations of two concave regions are represented more finely, thus much moreand rich spatial relations can be described. The limitation of 9-intersectionmodel is that it can only represents the topological relations between simpleconvex regions. The model TSC extends the objects into simple concaveregions. It is more general and applicable to practical application fields.Fourthly, we designed and implemented a demonstrating system ofmodel TSC. The demo system is composed of three main functions, that is,
demonstrating, distinguishing and reasoning of topological relations. The partof topological relations reasoning can be applied directly to the automaticreasoning of composition table. It is of importance both in theory andapplication in some degree.The method CTS proposed in this paper increases the correctness andreasonableness of the deriving results using SameSide predicate. Based onRCC23 and 9-intersection model, we extend RCC23 by introducing eightnew topological relations besides the original 23 topological relations. Thus,it will enrich the expressive power of topological relations to some extend,obtain more spatial relations and can be the theoretical basis of automaticreasoning of composition table on topological relations.In a word, the study results of the paper are of both theoretical andpractical benefit to further researches in spatial relations on spatial reasoning,spatial query language and geographic information system (GIS).
本文围绕空间凹形对象的定性形状、拓扑关系的表示和推理,展开了研究和讨论。主要工作包括:(1)以空间关系的形式化表示为主线,总结和分析了空间凹形对象定性形状、拓扑关系表示的一些主要研究工作;(2)改进Cohn等提出的基于连接和凸壳的定性形状表示法,提出了基于凹处变换的SameSide判断方法(简称方法CTS)及其相应算法;(3)基于RCC23和9-交集模型,提出了模型TSC,用于两个简单凹形区域间拓扑关系的表示及推理;定义了TSC31,并给出其概念邻域图和最小拓扑距离关系图;(4)设计并实现了模型TSC的演示系统。
本文工作能够描述更具一般性、更丰富的空间关系,在一定程度上丰富了空间拓扑关系的表达能力,同时也为拓扑关系复合表的自动推导奠定了理论基础。本文的研究对于定性空间推理、地理信息系统、空间查询语言的研究具有一定的理论意义和应用价值。
In recent years, researches on theory and application on spatialinformation are getting more and more attentions in ArtificialIntelligence(AI), Geographical Information System(GIS), Spatial Databaseand other relating fields. The relations of spatial objects are various, andsometimes rely on the domain specific applications. The research oncognition, description and representation of spatial relations are the basis ofan effective application. At present, there are two main methods on spatialrelation representation: logic-based methods and point-set topology basedmethods.
Topological relation is the most elementary relation in space, and is oneof the basic problems in qualitative spatial reasoning. Qualitative shaperepresentation is one important aspect in qualitative reasoning. Unlike thetraditional quantitative methods, the qualitative shape measures concernmainly on abstracting and representing the qualitative properties of objects'shape. It is meaningful to apply the exiting qualitative spatial methods intothe shape representation. This paper is focused on representation andreasoning about qualitative shape, topological representation of spatialobjects.
The main work and results included in this paper are as follows:
Firstly, the paper summarized and analysed the state of arts inrepresentation about qualitative shape and topological relations of spatialobjects based on the two essential methods in spatial relation description. Itintroduces some basic theories including Allen's interval calculus, RegionConnection Calculus(RCC) and 9-intersection model. The relate researchworks in topological relations of spatial objects are surveyed and analyzed. Itdescribes a hierarchical representation of qualitative shape based onconnection and convexity presented by Cohn, and a process-grammar shape
representation methods proposed by Leyton.Secondly, this paper gave a detailed introduction of a hierarchicalrepresentation of qualitative shape based on connection and convexitypresented by Cohn. We proposed a SameSide deducing method on the basisof concavity transforming, and give the arithmetic description. Based on theessential binary relation 'connection' and the concept of 'convex hull', Cohnhad presented a hierarchical representation of qualitative shape to describemany kinds of concave regions. During the analyzing process, we found thatillogical results would be derived by directly using the SameSide predicatefor some kinds of concave regions. Based on Allen's interval algebra, wepresent a method CTS by distinguishing the type of the concavities makinguse of tangent scanning measure. The results derived from method CTSaccords with people's cognition.Thirdly, on the basis of Cohn's RCC23 and Egenhofer's 9-intersectionmodel, we proposed a model TSC, defined TSC31, and gave the conceptualneighborhood and closest topological relation graph. The RCC formal modeland 9-intersection model are the most typical theory models in therepresentation of spatial topological relations. Combining the idea of the twomethods, we constructed a model TSC. The model consists of two parts,namely the representing system and the reasoning system. Based on RCC23,we defined TSC31 by introducing eight new topological relations, and alsogave the conceptual neighborhood and closest topological relation graph ofTSC31. The model TSC is more expressive than RCC23, the topologicalrelations of two concave regions are represented more finely, thus much moreand rich spatial relations can be described. The limitation of 9-intersectionmodel is that it can only represents the topological relations between simpleconvex regions. The model TSC extends the objects into simple concaveregions. It is more general and applicable to practical application fields.Fourthly, we designed and implemented a demonstrating system ofmodel TSC. The demo system is composed of three main functions, that is,
demonstrating, distinguishing and reasoning of topological relations. The partof topological relations reasoning can be applied directly to the automaticreasoning of composition table. It is of importance both in theory andapplication in some degree.The method CTS proposed in this paper increases the correctness andreasonableness of the deriving results using SameSide predicate. Based onRCC23 and 9-intersection model, we extend RCC23 by introducing eightnew topological relations besides the original 23 topological relations. Thus,it will enrich the expressive power of topological relations to some extend,obtain more spatial relations and can be the theoretical basis of automaticreasoning of composition table on topological relations.In a word, the study results of the paper are of both theoretical andpractical benefit to further researches in spatial relations on spatial reasoning,spatial query language and geographic information system (GIS).
引文
[1] Egenhofer MJ. A model for detailed binary topological relations. Geomatica. 1993, 47(3&4):261-273.
[2] Egenhofer MJ, Franzosa RD, Point-set topological spatial relations, International Journal of Geographical Information Systems, 1991, 5(2):161-174.
[3] Randell DA, Cui Z, Cohn AG. A spatial logic based on regions and connection. In: Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning. Morgan Kaufmann, Sanmateo, 1992, 165-176.
[4] 虞强源. 空间区域拓扑关系分析方法的研究. 吉林大学博士学位论文. 2003.
[5] 欧阳继红. 时空推理中一些问题的研究. 吉林大学博士学位论文. 2005.
[6] Clarke BL. A calculus of individuals based on 'connection'. Notre Dame Journal of Formal Logic. 1981, 23(3):204-218.
[7] Randell DA, Cohn AG. Modelling topological and metrical properties in physical processes. In: Proc 1st Int Conf on the Principles of Knowledge Representation and Reasoning. Morgan Kaufmann, Los Altos, 1989, 55-66.
[8] Cui Z, Cohn AG and Randell DA. Qualitative simulation based on a logical formalism of space and time. In: Proc of AAAAI-92. AAAI Press, Menlo Park, California, 1992, 679-684.
[9] Benntte B. Spatial reasoning with propositional logics, In: Proc of KR-94. Morgan Kaufmann, 1994, 51-62.
[10] Cohn AG. A hierarchical representation of qualitative shape based on connection and convexity. In: Proc of COSIT-95. Semmering, 1995.
[11] Bennett B, Cohn AG. Multi-dimensional multi-modal logics as a framework for spatio-temporal reasoning. In: Proc of the 'Hot Topics in Spatio-Temporal Reasoning' workshop, IJCAI-99. Stockholm, 1999.
[12] Egenhofer MJ, Franzosa R. Point-set topological relations. Int J of Geographical Information Systems. 1991, 5(2):161-174.
[13] Egenhofer MJ, Herring J. Categorizing binary topological relationships between regions, lines and points in geographical database. Technical Report. Department of Surveying Engeering, University of Maine, 1991.
[14] Leyton M. A process grammar for shape. Artificial Intelligence. 1988, 34.
[15] Gotts NM. How far can we 'C'? Defining a doughnut using connection alone. In: Proc of KR-94, Morgan Kaufmann, 1994, 246-257.
[16] Allen JF. An interval based representation of temporal knowledge. IJCAI, August 1981.
[17] Allen JF. Maintaining Knowledge about Temporal Intervals [J]. Communications of the ACM, 1983, 26:832-843.
[18] Cohn AG, Randell DA, Cui Z and Bennett B. Qualitative Spatial Reasoning and Representation. In: Qualitative Reasoning and Decision Technologies, CIMNE, Barcelona, 1993, 513-522.
[19] Cohn AG, Bennett B, Gooday J and Gotts NM. Qualitative spatial representation and reasoning with the region connection calculus. GeoInformatica, 1997, 1(1):1-44.
[20] Güting RH. Geo-relational algebra: a model and query language for geometric database systems. In: Advances in Database Technology, EDBT-98, LNCS 303. Berlin: Springer-Verlag, 1988, 506-527.
[21] Zhan FB. A fuzzy set model of approximate linguistic terms in descriptions of binary topological relations between simple regions. In: Applying Soft Computing IN Defining Spatial Relations. Heidelberg: Physica-Verlag, 2001, 179-202.
[22] Grigni M, Papadias D and Papadimitriou C. Topological inference. In: Proc of 14th Int Joi Conf on Artificial Intelligence, volume I. San Francisco: Morgan Kaufmann, 1995, 901-906.
[23] Egenhofer MJ, Clementini E and Di Felice P. Topological relations between regions with holes. International Journal of Geographical Information Systems, 1994, 8(2):129-144.
[24] Egenhofer MJ, Franzosa R. On the equivalence of topological relations. International Journal of Geographical Information Systems, 1995, 9(2):133-152.
[25] Clementini E, Di Felice P and Califano G. Composite Regions in Topological Queries. Information Systems, 1995, 20(7):579-594.
[26] Clementini E, Di Felice P. A Model for Representing Topological Relationships Between Complex Gemetric Features in Spatial Databases. Information Sciences, 1995, 3:149-178.
[27] Clementini E, Di Felice P. An algebraic model for spatial objects with indeterminate boundaries. In: Geographic Objects with Indeterminate Boundaries. London: Taylor & Francis, 1996, 155-169.
[28] Nguyen VH, Parent C and Spaccapietra S. Complex Regions in Topological Queries. In Proc of the Int Conf on Spatial Information Theory COSIT-97, Springer Verlag, 1997, LNCS 1329:175-192.
[29] El-Geresy BA and Abdelmoty AI. Order in Space: A General Formalism for Spatial Reasoning. International Journal of Artificial Intelligence Tools, IJAIT, World Scientific, 1997, 6(4):423-450.
[30] 廖士中, 石纯一. 拓扑关系的闭球模型及复合表的推导. 软件学报, 1997, 8(12):894~900.
[31] Coenen FP, Pepijn V. A generic ontology for spatial reasoning. In Proc of Research and Development in Expert Systems XV, ES-98, Springer Verlag, 1998, 44-57.
[32] Chen J, Li CM, Li ZL and Gold C. A voronoi-based 9-intersection model for spatial relations. International Journal of Geographical Information Science, 2001, 15(3):201~220.
[33] 曹菡,师军,李生刚,陈军. 点集拓扑理论在拓扑关系描述中的应用. 工程数学学报, 2001, 18(4):76~82.
[34] Brady M. Criteria for representations of shape. Human and Machine Vision. 1983.
[35] Freksa C. Temporal reasoning based on semi-intervals. Artificial Intelligence, 1992, 54:199-227.
[36] Egenhofer MJ, Al-Taha K. Reasoning about gradual changes of topological relationships. In: Theories and models of spatio-temporal reasoning in geographic space. LNCS693. Springer-Verlag, Berlin. 1992, 196-219.
[37] Cohn AG. The challenge of qualitative spatial reasoning. ACM Computinig Surveys, 1995, 27(3):323-325.
[2] Egenhofer MJ, Franzosa RD, Point-set topological spatial relations, International Journal of Geographical Information Systems, 1991, 5(2):161-174.
[3] Randell DA, Cui Z, Cohn AG. A spatial logic based on regions and connection. In: Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning. Morgan Kaufmann, Sanmateo, 1992, 165-176.
[4] 虞强源. 空间区域拓扑关系分析方法的研究. 吉林大学博士学位论文. 2003.
[5] 欧阳继红. 时空推理中一些问题的研究. 吉林大学博士学位论文. 2005.
[6] Clarke BL. A calculus of individuals based on 'connection'. Notre Dame Journal of Formal Logic. 1981, 23(3):204-218.
[7] Randell DA, Cohn AG. Modelling topological and metrical properties in physical processes. In: Proc 1st Int Conf on the Principles of Knowledge Representation and Reasoning. Morgan Kaufmann, Los Altos, 1989, 55-66.
[8] Cui Z, Cohn AG and Randell DA. Qualitative simulation based on a logical formalism of space and time. In: Proc of AAAAI-92. AAAI Press, Menlo Park, California, 1992, 679-684.
[9] Benntte B. Spatial reasoning with propositional logics, In: Proc of KR-94. Morgan Kaufmann, 1994, 51-62.
[10] Cohn AG. A hierarchical representation of qualitative shape based on connection and convexity. In: Proc of COSIT-95. Semmering, 1995.
[11] Bennett B, Cohn AG. Multi-dimensional multi-modal logics as a framework for spatio-temporal reasoning. In: Proc of the 'Hot Topics in Spatio-Temporal Reasoning' workshop, IJCAI-99. Stockholm, 1999.
[12] Egenhofer MJ, Franzosa R. Point-set topological relations. Int J of Geographical Information Systems. 1991, 5(2):161-174.
[13] Egenhofer MJ, Herring J. Categorizing binary topological relationships between regions, lines and points in geographical database. Technical Report. Department of Surveying Engeering, University of Maine, 1991.
[14] Leyton M. A process grammar for shape. Artificial Intelligence. 1988, 34.
[15] Gotts NM. How far can we 'C'? Defining a doughnut using connection alone. In: Proc of KR-94, Morgan Kaufmann, 1994, 246-257.
[16] Allen JF. An interval based representation of temporal knowledge. IJCAI, August 1981.
[17] Allen JF. Maintaining Knowledge about Temporal Intervals [J]. Communications of the ACM, 1983, 26:832-843.
[18] Cohn AG, Randell DA, Cui Z and Bennett B. Qualitative Spatial Reasoning and Representation. In: Qualitative Reasoning and Decision Technologies, CIMNE, Barcelona, 1993, 513-522.
[19] Cohn AG, Bennett B, Gooday J and Gotts NM. Qualitative spatial representation and reasoning with the region connection calculus. GeoInformatica, 1997, 1(1):1-44.
[20] Güting RH. Geo-relational algebra: a model and query language for geometric database systems. In: Advances in Database Technology, EDBT-98, LNCS 303. Berlin: Springer-Verlag, 1988, 506-527.
[21] Zhan FB. A fuzzy set model of approximate linguistic terms in descriptions of binary topological relations between simple regions. In: Applying Soft Computing IN Defining Spatial Relations. Heidelberg: Physica-Verlag, 2001, 179-202.
[22] Grigni M, Papadias D and Papadimitriou C. Topological inference. In: Proc of 14th Int Joi Conf on Artificial Intelligence, volume I. San Francisco: Morgan Kaufmann, 1995, 901-906.
[23] Egenhofer MJ, Clementini E and Di Felice P. Topological relations between regions with holes. International Journal of Geographical Information Systems, 1994, 8(2):129-144.
[24] Egenhofer MJ, Franzosa R. On the equivalence of topological relations. International Journal of Geographical Information Systems, 1995, 9(2):133-152.
[25] Clementini E, Di Felice P and Califano G. Composite Regions in Topological Queries. Information Systems, 1995, 20(7):579-594.
[26] Clementini E, Di Felice P. A Model for Representing Topological Relationships Between Complex Gemetric Features in Spatial Databases. Information Sciences, 1995, 3:149-178.
[27] Clementini E, Di Felice P. An algebraic model for spatial objects with indeterminate boundaries. In: Geographic Objects with Indeterminate Boundaries. London: Taylor & Francis, 1996, 155-169.
[28] Nguyen VH, Parent C and Spaccapietra S. Complex Regions in Topological Queries. In Proc of the Int Conf on Spatial Information Theory COSIT-97, Springer Verlag, 1997, LNCS 1329:175-192.
[29] El-Geresy BA and Abdelmoty AI. Order in Space: A General Formalism for Spatial Reasoning. International Journal of Artificial Intelligence Tools, IJAIT, World Scientific, 1997, 6(4):423-450.
[30] 廖士中, 石纯一. 拓扑关系的闭球模型及复合表的推导. 软件学报, 1997, 8(12):894~900.
[31] Coenen FP, Pepijn V. A generic ontology for spatial reasoning. In Proc of Research and Development in Expert Systems XV, ES-98, Springer Verlag, 1998, 44-57.
[32] Chen J, Li CM, Li ZL and Gold C. A voronoi-based 9-intersection model for spatial relations. International Journal of Geographical Information Science, 2001, 15(3):201~220.
[33] 曹菡,师军,李生刚,陈军. 点集拓扑理论在拓扑关系描述中的应用. 工程数学学报, 2001, 18(4):76~82.
[34] Brady M. Criteria for representations of shape. Human and Machine Vision. 1983.
[35] Freksa C. Temporal reasoning based on semi-intervals. Artificial Intelligence, 1992, 54:199-227.
[36] Egenhofer MJ, Al-Taha K. Reasoning about gradual changes of topological relationships. In: Theories and models of spatio-temporal reasoning in geographic space. LNCS693. Springer-Verlag, Berlin. 1992, 196-219.
[37] Cohn AG. The challenge of qualitative spatial reasoning. ACM Computinig Surveys, 1995, 27(3):323-325.