定性空间方向关系建模中若干问题研究
|
摘要
空间关系能够描述客观世界的空间信息,是解决许多理论与实际问题的关键。空间关系建模是人工智能的重要研究内容,在地理信息系统、机器人导航、图像理解领域有着广泛的应用。
方向关系是最基本的空间关系之一,能够描述空间对象间的相对位置信息。目前空间方向关系建模已取得很大进展,但仍存在一些问题：现有研究多集中于模型的表示方面,推理方面研究较少；对空间方向关系运算性质的研究不够深入,其中基本主方向关系的逆运算性质仍是一个有待解决的开放问题；此外现有模型多针对简单空间对象,难以处理复杂空间对象(不连通、带洞、具有不确定边界)间的方向关系,不确定区域间方向关系的表示模型、基本运算性质、推理方法以及推理复杂性等方面的研究尚处于起步阶段。
本文采用定性研究方法,针对确定区域间基本主方向关系的逆运算、不确定区域间方向关系的表示与推理等问题展开研究。对现有定性空间关系模型进行分析和总结,在此基础上利用SK模型和MBR模型提出一种确定基本主方向关系的逆关系的方法；用宽边界模型表示带有不确定边界的复杂区域,利用区间代数和矩形代数分析不确定区域间方向关系的复合运算,进而提一种MBR宽边界方向关系复合推理方法；分析不确定区域间方向关系自身所蕴含的约束信息,提出一种不确定区域间方向关系约束的相容性判定算法。本文的主要贡献、研究思路和研究结果如下：
(1)定性空间方向关系建模
论述空间关系建模的研究背景和意义,介绍几种主要空间关系的基本概念和研究现状；然后以定性空间方向关系研究为主线,分别从简单对象间方向关系和不确定对象间方向关系两方面,着重对现有空间方向关系建模研究的现状进行分析与总结,最后讨论了目前空间方向关系建模研究所存在的问题。
(2)定性空间方向关系演算
介绍了定性空间方向关系推理中三种重要的关系代数：区间代数、矩形代数、主方向关系代数。论述了三种关系代数的研究意义和现状；分别给出三种关系代数的基本定义以及基本关系运算(着重介绍了其中的交、并、逆、复合运算)。
(3)基本主方向关系的逆关系研究
研究了基本主方向关系的逆关系这一开放问题。首先基于模型SK和MBR提出一种四元组表示模型,将任意一个基本主方向关系R转换成其对应的四元组,称该四元组为R的位置,记为loc(R);然后分析了R与loc(R), loc(R)与loc-1(R)以及loc-1(R)与inv(R)间的对应关系；在此基础上提出一种确定基本主方向关系的逆关系的方法。该方法能够确定包括单片、多片和矩形关系在内的所有基本主方向关系的逆关系。
(4)基于MBR的不确定区域间方向关系建模研究
讨论了导致空间关系不确定性的各种原因；介绍了不确定空间方向关系建模研究现状,并指出了存在问题。提出了一种基于MBR的不确定区域间方向关系建模方法,该方法采用宽边界统一表示区域的不确定边界,将矩形代数的良好计算性质应用于不确定区域间MBR主方向关系的表示与推理中,定义MBR宽边界方向关系用以表示不确定区域间的方向关系；给出MBR宽边界方向关系间相容性复合的定义；基于矩形代数提出一种复合运算方法,并形式化证明其正确性。
(5)不确定区域间方向关系推理方法研究
提出了一种不确定区域间方向关系的推理方法。对提出的MBR宽边界方向关系模型进行扩展,定义了宽边界方向关系用以描述不确定区域间的方向关系,更符合人们对方向关系的认知；基于基本主方向关系的形式化定义,分析并证明宽边界方向关系自身蕴涵的约束规则；定义宽边界方向关系的复合,给出一种基于复合运算的不确定区域间方向关系推理方法,并证明了该方法的正确性。
(6)不确定区域间方向关系相容性检测方法
介绍空间约束满足问题的基本概念和研究现状；定义宽边界方向关系约束,讨论了宽边界方向关系约束集合的相容性问题；分析了宽边界约束和确定区域间方向关系约束之间的转换规则,从而将基于宽边界方向关系的约束满足问题转换为基于确定区域间方向关系的约束满足问题；基于路径相容算法,提出一种基于宽边界方向关系约束的相容性算法BBD-CON,并分析了算法的复杂度。
Spatial relations, which can describe the spatial information of the objective world, are the keys to many theoretical and practical problems. For its importance in the field of artificial intelligence, spatial relations modeling has been widely applied to geographic information system, robotics navigation and image understanding.
As a fundamental relationship, direction can describe the relative position between objects, and plays an essential role in qualitative spatial relations modeling. The present works about direction relations focus on the representation, but seldom on the reasoning and the operation properties, and the inverse operation of basic cardinal direction relations is still an open problem. Moreover, most conventional direction relation models are suitable for the relations between simple spatial objects, not appropriate for the relations between complex objects (e.g. the disconnected regions, the regions with holes or indeterminate boundaries). The representation models, operation properties and reasoning approaches for the direction relations between uncertain objects with indeterminate boundaries are still at preliminary stage.
This thesis concentrates on the inverse relations of basic cardinal direction relations between crisp regions and the modeling approaches for direction relations between uncertain regions (DRUR). First, it surveys and analyzes the present works about qualitative direction relations. Based on the model SK and model MBR, an approach for determining inverse relations of basic cardinal direction relations is proposed. Second, the uncertain regions with indeterminate boundaries are represented with board boundary model. Based on rectangular algebra, it analyzes the consistency-based composition between MBR board boundary direction relations, and then the reasoning method based this composition is put forward. Moreover, it also extends the model of MBR board boundary direction relations to improve its representation ability. Finally the constraint rules and a consistency checking algorithm for the DRUR are proposed. The major contributions, ideas and research results are as follows:
(1) The survey of qualitative spatial relation models
This thesis introduces the research background and significance of the qualitative spatial relations modeling, and some concepts of fundamental spatial relationships. Then it takes the qualitative spatial direction relations as study objects, summarizes and analyses current works from two different aspects respectively:the models of direction relations between crisp regions and the models of DRUR. Finally the existent problems and future research directions are discussed.
(2) The survey of qualitative spatial direction relational algebras
This thesis introduces three famous algebras for qualitative spatial direction relations: interval algebra, rectangle algebra and cardinal direction relation calculus. The fundamental concepts and operations (such as intersection, union, composition) of these three algebras are summarized respectively.
(3) The inverse relations of basic cardinal direction relations
The determination method for inverse relations of basic cardinal direction relations, which is still an open problem in qualitative direction relations modeling, is researched in this thesis. A quadruple model of basic cardinal direction relation is proposed. Then, based on this model, a basic cardinal direction relation R can be transferred into loc(R). Moreover, the constraints between R and loc(R), loc(R) and loc-1(R) as well as loc-1(R) and inv(R) are analyzed. On this basis, a new determination method for the inverse relation is put forward, which can capture all the inverse relations of basic cardinal direction relations including single tile, multi-tile and rectangular relation.
(4) Modeling for direction relations between uncertain regions based on MBR
This thesis discusses the main causes of indeterminate spatial relations with uncertainty. Then it introduces the research situation and existent problems of spatial direction relations modeling between uncertain regions. For the uncertain regions with indeterminate boundaries, the indeterminate boundaries are represented with broad boundaries. The DRUR are described by MBR-based cardinal direction relations and rectangle algebra, then we study the consistency-based composition of DRUR, and a computation method for this composition is put forward, whose correctness is formally proved.
(5) Reasoning direction relations between uncertain regions
A reasoning approach for DRUR is proposed in this thesis. DRUR are described with board boundary direction relations, which are the combinations of basic cardinal direction relations. Then the constraints rules implied in board boundary direction relations are analyzed. Moreover, the consistency-based composition of DRUR is defined, and a method is put forward for calculating this composition.
(6) Consistency checking for direction relations between uncertain regions
The board boundary direction relations constraints are formally defined, and their consistency checking problem is discussed in this thesis. A CSP based on board boundary direction relation constraints are transformed into a CSP based on cardinal direction relation constraints, then an improved consistency checking algorithm is proposed, whose correctness and computational complexity is proved at the end.
方向关系是最基本的空间关系之一,能够描述空间对象间的相对位置信息。目前空间方向关系建模已取得很大进展,但仍存在一些问题：现有研究多集中于模型的表示方面,推理方面研究较少；对空间方向关系运算性质的研究不够深入,其中基本主方向关系的逆运算性质仍是一个有待解决的开放问题；此外现有模型多针对简单空间对象,难以处理复杂空间对象(不连通、带洞、具有不确定边界)间的方向关系,不确定区域间方向关系的表示模型、基本运算性质、推理方法以及推理复杂性等方面的研究尚处于起步阶段。
本文采用定性研究方法,针对确定区域间基本主方向关系的逆运算、不确定区域间方向关系的表示与推理等问题展开研究。对现有定性空间关系模型进行分析和总结,在此基础上利用SK模型和MBR模型提出一种确定基本主方向关系的逆关系的方法；用宽边界模型表示带有不确定边界的复杂区域,利用区间代数和矩形代数分析不确定区域间方向关系的复合运算,进而提一种MBR宽边界方向关系复合推理方法；分析不确定区域间方向关系自身所蕴含的约束信息,提出一种不确定区域间方向关系约束的相容性判定算法。本文的主要贡献、研究思路和研究结果如下：
(1)定性空间方向关系建模
论述空间关系建模的研究背景和意义,介绍几种主要空间关系的基本概念和研究现状；然后以定性空间方向关系研究为主线,分别从简单对象间方向关系和不确定对象间方向关系两方面,着重对现有空间方向关系建模研究的现状进行分析与总结,最后讨论了目前空间方向关系建模研究所存在的问题。
(2)定性空间方向关系演算
介绍了定性空间方向关系推理中三种重要的关系代数：区间代数、矩形代数、主方向关系代数。论述了三种关系代数的研究意义和现状；分别给出三种关系代数的基本定义以及基本关系运算(着重介绍了其中的交、并、逆、复合运算)。
(3)基本主方向关系的逆关系研究
研究了基本主方向关系的逆关系这一开放问题。首先基于模型SK和MBR提出一种四元组表示模型,将任意一个基本主方向关系R转换成其对应的四元组,称该四元组为R的位置,记为loc(R);然后分析了R与loc(R), loc(R)与loc-1(R)以及loc-1(R)与inv(R)间的对应关系；在此基础上提出一种确定基本主方向关系的逆关系的方法。该方法能够确定包括单片、多片和矩形关系在内的所有基本主方向关系的逆关系。
(4)基于MBR的不确定区域间方向关系建模研究
讨论了导致空间关系不确定性的各种原因；介绍了不确定空间方向关系建模研究现状,并指出了存在问题。提出了一种基于MBR的不确定区域间方向关系建模方法,该方法采用宽边界统一表示区域的不确定边界,将矩形代数的良好计算性质应用于不确定区域间MBR主方向关系的表示与推理中,定义MBR宽边界方向关系用以表示不确定区域间的方向关系；给出MBR宽边界方向关系间相容性复合的定义；基于矩形代数提出一种复合运算方法,并形式化证明其正确性。
(5)不确定区域间方向关系推理方法研究
提出了一种不确定区域间方向关系的推理方法。对提出的MBR宽边界方向关系模型进行扩展,定义了宽边界方向关系用以描述不确定区域间的方向关系,更符合人们对方向关系的认知；基于基本主方向关系的形式化定义,分析并证明宽边界方向关系自身蕴涵的约束规则；定义宽边界方向关系的复合,给出一种基于复合运算的不确定区域间方向关系推理方法,并证明了该方法的正确性。
(6)不确定区域间方向关系相容性检测方法
介绍空间约束满足问题的基本概念和研究现状；定义宽边界方向关系约束,讨论了宽边界方向关系约束集合的相容性问题；分析了宽边界约束和确定区域间方向关系约束之间的转换规则,从而将基于宽边界方向关系的约束满足问题转换为基于确定区域间方向关系的约束满足问题；基于路径相容算法,提出一种基于宽边界方向关系约束的相容性算法BBD-CON,并分析了算法的复杂度。
Spatial relations, which can describe the spatial information of the objective world, are the keys to many theoretical and practical problems. For its importance in the field of artificial intelligence, spatial relations modeling has been widely applied to geographic information system, robotics navigation and image understanding.
As a fundamental relationship, direction can describe the relative position between objects, and plays an essential role in qualitative spatial relations modeling. The present works about direction relations focus on the representation, but seldom on the reasoning and the operation properties, and the inverse operation of basic cardinal direction relations is still an open problem. Moreover, most conventional direction relation models are suitable for the relations between simple spatial objects, not appropriate for the relations between complex objects (e.g. the disconnected regions, the regions with holes or indeterminate boundaries). The representation models, operation properties and reasoning approaches for the direction relations between uncertain objects with indeterminate boundaries are still at preliminary stage.
This thesis concentrates on the inverse relations of basic cardinal direction relations between crisp regions and the modeling approaches for direction relations between uncertain regions (DRUR). First, it surveys and analyzes the present works about qualitative direction relations. Based on the model SK and model MBR, an approach for determining inverse relations of basic cardinal direction relations is proposed. Second, the uncertain regions with indeterminate boundaries are represented with board boundary model. Based on rectangular algebra, it analyzes the consistency-based composition between MBR board boundary direction relations, and then the reasoning method based this composition is put forward. Moreover, it also extends the model of MBR board boundary direction relations to improve its representation ability. Finally the constraint rules and a consistency checking algorithm for the DRUR are proposed. The major contributions, ideas and research results are as follows:
(1) The survey of qualitative spatial relation models
This thesis introduces the research background and significance of the qualitative spatial relations modeling, and some concepts of fundamental spatial relationships. Then it takes the qualitative spatial direction relations as study objects, summarizes and analyses current works from two different aspects respectively:the models of direction relations between crisp regions and the models of DRUR. Finally the existent problems and future research directions are discussed.
(2) The survey of qualitative spatial direction relational algebras
This thesis introduces three famous algebras for qualitative spatial direction relations: interval algebra, rectangle algebra and cardinal direction relation calculus. The fundamental concepts and operations (such as intersection, union, composition) of these three algebras are summarized respectively.
(3) The inverse relations of basic cardinal direction relations
The determination method for inverse relations of basic cardinal direction relations, which is still an open problem in qualitative direction relations modeling, is researched in this thesis. A quadruple model of basic cardinal direction relation is proposed. Then, based on this model, a basic cardinal direction relation R can be transferred into loc(R). Moreover, the constraints between R and loc(R), loc(R) and loc-1(R) as well as loc-1(R) and inv(R) are analyzed. On this basis, a new determination method for the inverse relation is put forward, which can capture all the inverse relations of basic cardinal direction relations including single tile, multi-tile and rectangular relation.
(4) Modeling for direction relations between uncertain regions based on MBR
This thesis discusses the main causes of indeterminate spatial relations with uncertainty. Then it introduces the research situation and existent problems of spatial direction relations modeling between uncertain regions. For the uncertain regions with indeterminate boundaries, the indeterminate boundaries are represented with broad boundaries. The DRUR are described by MBR-based cardinal direction relations and rectangle algebra, then we study the consistency-based composition of DRUR, and a computation method for this composition is put forward, whose correctness is formally proved.
(5) Reasoning direction relations between uncertain regions
A reasoning approach for DRUR is proposed in this thesis. DRUR are described with board boundary direction relations, which are the combinations of basic cardinal direction relations. Then the constraints rules implied in board boundary direction relations are analyzed. Moreover, the consistency-based composition of DRUR is defined, and a method is put forward for calculating this composition.
(6) Consistency checking for direction relations between uncertain regions
The board boundary direction relations constraints are formally defined, and their consistency checking problem is discussed in this thesis. A CSP based on board boundary direction relation constraints are transformed into a CSP based on cardinal direction relation constraints, then an improved consistency checking algorithm is proposed, whose correctness and computational complexity is proved at the end.
引文
[1]Alan K. Mackworth. Constraint satisfaction [C]. In Encyclopedia of Artificial Intelligence, S.C. Shapiro, Ed.:Wiley, Chichester, England,1987,205-211.
[2]P. B. Ladkin, R. D. Maddux. On binary constraint problems [J]. Journal of the ACM,1993,41(3):435-469.
[3]Alfred Tarski. On the calculus of relations [J]. Journal of Symbolic Logic,1941,6: 73-89.
[4]Daniel S. Weld. Readings in Qualitative Reasoning about Physical Systems [M]. Morgan Kaufmann, San Mateo, CA,1989.
[5]Haar R.Computational models of spatial relations [R]. TR-478, MSC-72-03610.Computer Science, University of Maryland, College Park, MD, 1976.
[6]Andrew U Frank. Qualitative spatial reasoning about cardinal directions [C]. in the 7th Austrian Conference on Artificial Intelligence,1991,157-167.
[7]陈军,赵仁亮.GIS空间关系的基本问题与研究进展[J].测绘学报,1999,28(2)：95-102
[8]谢琦,刘大有,虞强源,陈娟.定性方向关系模型研究进展[J].计算机科学,2006,33(11)：5-9.
[9]Chrisman N. R, Yandell B. S. Effects of point error on area calculations:a statistical model [J]. Surveying and Mapping,1982,48(4):241-246.
[10]Jochen Renz, G'erard Ligozat. Weak Composition for Qualitative Spatial and Temporal Reasoning[C]. in the Eleventh International Conference on Principles and Practice of Constraint Programming (CP'05), Sitges, Spain,2005,534-548.
[11]Brandon Bennett, Amar Isli, Anthony Cohn. When does a Composition Table Provide a Complete and Tractable Proof Procedure for a Relational Constraint Language Proof Procedure for a Relational Constraint Language [C]. in IJCAI-97 Workshop on Spatial and Temporal Reasoning,1997:1-18.
[12]J. Allen. Maintaining Knowledge about Temporal Intervals [J]. Communications of the ACM,1983,26:832-843.
[13]Philippe Balbiani, Jean-Francois Condotta, Luis Farinas delCerro. A new Tractable Subclass of the Rectangle Algebra [C]. in IJCAI-99,1999,442-447.
[14]Randell DA, Cui Z, Cohn AG. A spatial logic based on regions and connection [C]. In:Nebel B, Rich C, Swartout WR, eds.Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning. San Francisco:Morgan Kaufmann Publishers,1992,165-176.
[15]J. Renz, D. Mitra. Qualitative direction calculi with arbitrary granularity [C]. in PRICAI'04,2004:65-74.
[16]P. Balbiani, A. Osmani. A model for reasoning about topologic relations between cyclic intervals [C]. in KR-2000 Breckenridge, Colorado,2000.
[17]A. K. Pujari, G. Vijaya Kumari, A. Sattar. INDU:An Interval and Duration Network [C]. in Australian Joint Conference on Artificial Intelligence,1999, 291-303.
[18]I. Navarrete, A. Sattar, R.Wetprasit, R. Marin. On point-duration networks for temporal reasoning [J]. Artifcial Intelligence,2002,140(1-2):39-70.
[19]A. K. Pujari, A. Sattar. A new framework for reasoning about points, intervals and durations [C]. in 16th International Joint Conferenceon Artificial Intelligence (IJCAI'99), Dean Thomas, Ed.:Morgan Kaufmann Publishers,1999,1259-1267.
[20]Robin hirsch. A finite relation algebra with undecidabel network satisfaction problem [J]. Bulletin of the IGPL,1999,7(4):547-554.
[21]Alan K. Mackworth. Consistency in networks of relations [J]. Artificial Intelligence,1977,8(1):99-118.
[22]Ugo Montanari. Networks of constraints:fundamental properties and applications to picture processing [J]. Information Science,1974,7:95-132.
[23]Alan K. Mackworth, Eugene C. Freuder. The complexity of some polynomial network consistency lgorithms for constraint satisfaction problems. Artificial Intelligence [J],1985,25:65-73.
[24]Peter van Beek. Reasoning about qualitative temporal information. Artificial Intelligence [J],1992,58(1-3):297-321.
[25]Christian 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,162-178.
[26]R. Goyal, M. J Egenhofer. Cardinal directions between extended spatial objects [J]. IEEE Transactions on Knowledge and Data Engineering,2000.
[27]Spiros Skiadopoulos, Manolis Koubarakis. Composing cardinal direction relations [J]. Artificial Intelligence,2004,152:143-171.
[28]Gotts N. M., Gooday J. M., Cohn A.G. A connection based approach to common-sense topological description and reasoning [J]. The Monist,1996,79(1): 51-75.
[29]Jochen Renz, Qualitative Spatial Reasoning with Topological Information [M]. LNCS 2293, Springer Berlin/Heidelberg,2002.
[30]Max J. Egenhofer, Robert D. Franzosa. Point-set Topological Spatial Relations [J]. International Journal of Geographical Information Science,1991,2:161-174.
[31]Randell DA, Cohn AG. Modelling topological and metrical properties in physical processes [C]. In:Brachman R, Levesque H, Reiter R, eds. Proceedings of the 1st International Conference on the Principles of Knowledge Representation and Reasoning. San Francisco:Morgan Kaufmann Publishers,1989,55-66.
[32]Ivo Duntsch, Hui Wang, Steve McCloskey. A relation algebraic approach to the region connection calculus. Theoretical Computer Science,2001,255:63-83.
[33]Sanjiang Li, Mingsheng Ying. Region connection calculus:Its models and composition table [J]. Artificial Intelligence,2003,145:121-146.
[34]Sanjiang Li, Mingsheng Ying. Generalized region connection calculus. Artificial Intelligence [J],2004,160:1-34.
[35]Sanjiang Li, Mingsheng Ying, Yongming Li. On countable RCC models [J]. Fundamenta Informaticae,2003,65:329-351.
[36]Sanjiang Li. On Topological Consistency and Realization [J]. Constraints,2006, 11(1):31-51.
[37]Sanjiang Li, Huaiqing Wang. RCC8 binary constraint network can be consistently extended [J]. Artificial Intelligence,2006,170:1-18.
[38]J.H. OuYang, Q. Fu, D.Y. Liu. A Model for Representing Topological Relations between Simple Concave Regions [C]. Procedings of the 7th International Conference of Computational Science (ICCS2007), Beijing, China, Springer Berlin /Heidelberg,2007,160-167.
[39]M. Egenhofer and M. Vasardani, Spatial Reasoning with a Hole [C]. Conference on Spatial Information Theory (COSIT'07), Springer,2007,303-320.
[40]Egenhofer MJ, Herring JR. Categorizing binary topological relationships between regions, lines and points in geographic database [R].Technical Report,91-7, Orono: University of Maine,1991.
[41]T. Behr, M. Schneider. Topological Relationships of Complex Points and Complex Regions [C]. In:H.S. Kunii, S. Jajodia, A. Solvberg (eds.):The 20the Int. Conf. on Conceptual Modeling. Berlin Heidelberg:Springer-Verlag, LNCS 2224,2004: 56-69.
[42]M. Schneider, T. Behr. Topological Relationships between Complex Spatial Objects [J]. ACM Transactions on Database Systems,2006,31(1):39-81.
[43]S. Li. A Complete Classifcation of Topological Relations Using 9-Intersection Method [J]. International Journal of Geographical Information Science (IJGIS), 2006,20:589-610.
[44]M. McKenney, A. Pauly, R. Praing, M. Schneider. Local Topological Relationships for Complex Regions [C].10th Int. Symp. on Spatial and Temporal Databases (SSTD), LNCS 4605, Springer-Verlag,2007:203-220.
[45]欧阳继红,霍林林,刘大有,富倩.能表达带洞区域拓扑关系的扩展9-交集模型[J].吉林大学学报(工学版),2009,39(6)：1595-1600.
[46]S.Y. Lee, F.J Hsu.2D C-string:a new spatial knowledge representation for image database system [J]. Pattern Recognition,1990,23:1077-1087.
[47]F.P. Coenen, P. Visser. A General Ontology for Spatial Reasoning in Research and Development in Expert Systems XV [C]. Proceedings of ES'98, Berlin: Springer-Verlag,1998:44-57.
[48]Kainz W., Egenhofer M.J., Greasley I.. Modeling spatial relations and operations with partially orders [J]. Geographic Information Systems,1993,7(3):215-229.
[49]J. Chen, CM. Li, ZL. Li, C. Gold. A voronoi-based 9-intersection model for spatial relations [J]. International Journal of Geographical Information Science,2001, 15(3):201-220.
[50]B. Gottfried. Tripartite Line Tracks [C]. International Conference on Computer Vision and Graphics. Proceedings. of ICCVG'2002, Zakopane, Poland,2002, 288-293.
[51]B. Gottfried. Tripartite Line Tracks, Qualitative Curvature Information [C]. In: Kuhn, W., Worboys, M., Timpf, S. (Eds.), Spatial Information Theory: Foundations of Geographic Information Science, International Conference COSIT, Springer, Berlin,2003, LNCS (2825):101-117.
[52]Museros L, Escrig MT. A qualitative theory for shape representation and matching for design [C]. In:LopezdeMantaras R; Saitta L eds. Frontiers in Artificial Intelligence and Applications:Proceedings of 16th European Conference on Artificial Intelligence,2004,110:858-862.
[53]B. Gottfried. Global Feature Schemes for Qualitative Shape Descriptions [C]. In:H. W. Guesgen, Ch. Freksa, G. Ligozat (Ed.), IJCAI-05 Workshop notes on spatial and temporal reasoning. Edinburgh, Scotland,31 July 2005.
[54]B. Gottfried. Characterizing Meanders Qualitatively [C]. In:M. Raubal, H. Miller, A. Frank, M. Goodchild:Geographic Information Scienc. The 4th Int. Conf. of GIScience. Berlin Heidelberg:Springer:Springer LNCS 4197,2006,112-127.
[55]E. Staffetti, A. Grau, F. Serratosa, A. Sanfeliu. Object and image indexing based on Region Connection Calculus and Oriented Matroid Theory. Discrete Applied Mathematics.2005,147(2-3):345-361.
[56]Van de Weghe N, De Tre G, Kuijpers B, De Maeyer P. The double-cross and the generalization concept as a basis for representing and comparing shapes of polylines [C]. In:Meersman R; Tari Z; Herrero P et al. eds. On the Move to Meaningful Internet Systems:Proceedings of the OTM Confederated International Conference and Workshop,2005, LNCS 3762:1087-1096.
[57]A. Schuldt, B. Gottfried, O. Herzog. Retrieving Shapes Efficiently by a Qualitative Shape Descriptor:The Scope Histogram [C]. The 5th Int. Conf. of Image and Video Retrieval (CIVR). Springer, LNCS 4071,2006,261-270.
[58]A. Schuldt, B. Gottfried, O. Herzog. A Compact Shape Representation for Linear Geographical Objects:The Scope Histogram [C]. The 14th ACM Int. Symposium on Advances in Geographic Information Systems (ACM GIS). Arlington, VA, USA,2006,51-58.
[59]B. Gottfried, Arne Schuldt, Otthein Herzog. Extent, Extremum, and Curvature: Qualitative Numeric Features for Efficient Shape Retrieval [C]. KI'07 Proceedings of the 30th annual German conference on Advances in Artificial Intelligence. Osnabruck, Germany,2007,308-322.
[60]B. Gottfried. Qualitative similarity measures—The case of two-dimensional outlines [J]. Computer Vision and Image Understanding,2008,110(1):117-133.
[61]B. Gottfried. Global feature schemes in spatial and temporal reasoning [J]. Spatial Cognition & Computation,2008,8(1):27-46.
[62]Cohn AG. A hierarchical representation of qualitative shape based on connection and convexity [C]. In:Proc of COSIT-95, Semmering,1995,311-326.
[63]A.P. Sistla, C. Yu, Reasoning about qualitative spatial relationships [J]. Journal of Automated Reasoning,2000,25:291-328.
[64]Alfonso Gerevini, Jochen Renz, Combining topological and size information for spatial reasoning [J]. Artificial Intelligence,2002,137(1-2):1-42.
[65]王生生,刘大有,谢琦,王新颖.集成多方面信息的定性空间推理及应用[J].软件学报,2003,14(11)：1857-1862.
[66]Sanjiang Li. Combining Topological and Directional Information for Spatial Reasoning [C]. IJCAI,2007,435-440.
[67]Weiming Liu, Sanjiang Li, Jochen Renz. Combining RCC-8 with Qualitative Direction Calculi:Algorithms and Complexity [C]. IJCAI,2009,854-859.
[68]Reinhard Moratz, Marco Ragni. Qualitative spatial reasoning about relative point position [J]. Journal of visual languages and computing,2008,19:75-98.
[69]J. J. Li, T. Kowalski, J. Renz, and S. Li, Combining Binary Constraint Networks in Qualitative Reasoning [C]. Proceedings of the 18th European Conference on Artificial Intelligence (ECAI'08), Patras, Greece,2008,515-519.
[70]Luo Guo, ShihongDu. Deriving topological relations between regions from direction relations [J]. Journal of Visual Languages and Computing,2009,20: 368-384.
[71]Eliseo Clementini, Spiros Skiadopoulos, Roland Billen, Francesco Tarquini. A Reasoning System of Ternary Projective Relations [C]. IEEE Transactions on Knowledge and Data Engineering,2010,22(2):161-178.
[72]Pequet 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.
[73]S. Skiadopoulos, Nikos Sarkas, Timos Sellis. A family of directional relation models [J]. IEEE Transactions on Knowledge and Data Engineering,2007,19(8): 1116-1130.
[74]S. Skiadopoulos and M. Koubarakis. On the consistency of cardinal direction constraints [J]. Artificial Intelligence,2005,163(1):91-135.
[75]I. Navarrete and G. Sciavicco. Spatial Reasoning with Rectangular Cardinal Direction Relations [C]. ECAI,2006.
[76]I.Navarrete, Morales A. Consistency Checking of Basic Cardinal Constraints over Connected Regions [C]. IJCAI,2007:495-500.
[77]刘永山,郝忠孝.基于MBR的主方向关系一致性检验[J].软件学报,2006,17(5)：976-982.
[78]Shihong Du, Luo Guo, Qiao Wang. A model for describing and composing direction relations between overlapping and contained regions [J]. Information Sciences,2008,178:2928-2949.
[79]Weiming Liu, Xiaotong Zhang, Sanjiang Li, Mingsheng Ying. Reasoning about cardinal directions between extended objects. Artificial Intelligence [J],2010,174: 951-983.
[80]D. Wolter, J. H. Lee. Qualitative reasoning with directional relations [J]. Artificial Intelligence 2010,174:1498-1507.
[81]Philippe Balbiani, Jean-Francois Condotta, Luis Farinas del Cerro. A tractable subclass of block algebra:constraint propagation and preconvex relations [C]. in Portuguese Conference on Artificial Intelligence,1999,75-89.
[82]J. Pacheco, M. T. Escrig, F. Toledo. Integrating 3D Orientation Models [C]. in 5th Catalonian Conference on Artificial Intelligence, Lecture Notes in Artificial Intelligence 2504,2002,88-100
[83]Juan Chen, Dayou Liu, Haiyang Jia, Changhai Zhang, Cardinal direction relations in 3D space [C]. the 2nd International Conference on Knowledge Science, Engineering and Management, KSEM, Melboure, Australia LNAI 4798,2007, 623-629.
[84]Andre Borrmann, Ernst Rank. Specification and implementation of directional operators in a 3D spatial query language for building information models [J]. Advanced Engineering Informatics,2009,23:32-44.
[85]Chang S K, Shi Q S, Yan C W. Iconic Indexing by 2D Strings [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1987,9 (6):413-428.
[86]Chang S K, J ungert E. Symbolic Projection for Image Information Retrieval and Spatial Reasoning [M]. London:Academic Press,1996.
[87]闫浩文,郭仁忠.基于Voronoi图的空间方向关系形式化描述研究(二)[J].测绘学报,2002,27(3)：4-7.
[88]闫浩文,郭仁忠.基于Voronoi图的空间方向关系形式化描述研究(一)[J].测绘学报,,2002,27(1)：24-27.
[89]闫浩文,郭仁忠.空间方向关系基础性问题研究[J].测绘学报,2002,31(4)：357-360.
[90]闫浩文,郭仁忠.基于Voronoi图的空间方向关系形式化描述模型[J].武汉大学学报(信息科学版),2003,28(4)：468-47.
[91]S. Cierone, P.D.Felice. Cardinal relations between regions with a broad boundary [C]. In 8th ACM Symposium on Advances in Geographic Information Systems (GIS'00),2000:15-20.
[92]D. Papadias, N. Karacapilidis, D. Arkoumanis. Processing fuzzy spatial queries:a configuration similarity approach [J]. International Journal of Geographical Information Science Science,1999,13(2):93-118.
[93]杜世宏,王桥,杨一鹏,李治江.空间方向关系模糊描述[J].计算机辅助设计与图形学学报,2005,17(8)：1745-1751.
[94]谢琦,刘大有,虞强源,陈娟.一种不确定区域间的方向关系模型[J].吉林大学学报(理学版),2006,44(5)：748-753.
[95]何建华,刘耀林,俞艳.不确定方向关系的模糊描述模型[J].武汉大学学报(信息科学版),2008,33(3)：257-260.
[96]杜世宏,王桥,魏斌,申文明.空间方向关系粗糙推理[J].测绘学报,2003,32(4)：334-338.
[97]LIU Yu, TIAN Yuan, WENG JingNong. Probabilistic composition of cone-based cardinal direction relations [J]. Sci China Ser E-Tech Sci,2008,51:81-90.
[98]J Allen, P Hayes. A common sense theory of time [C]. IJCAI,1985,1:528-531.
[99]J van Benthem. The Logic of Time Reidel [M], Dordrecht 1983.
[100]P Ladkin. Models of axioms for time intervals [C]. Proceedings of the 6th National Conference on Artificial Intelligence,1987,1:234-239.
[101]G Ligozat. A new proof of tractability for ORD-Horn relations [C]. Proceedings of the 13th National Conference on Artificial Intelligence,1996,1:395-401.
[102]B. Nebel, H. J. Burckert. Reasoning about temporal relations:a maximal tractable subclass of Allen's interval algebra [C]. Proceedings of the 12th National Conference on Artificial Intelligence,1994,1:356-361.
[103]B. Clark. A calculus of individuals based on connection [C]. Notre Dame Journal of Formal Logic,1981,22:204-218.
[104]B. Clark. Individuals and points [J]. Notre Dame Journal of Formal Logic,1985, 26:61-75.
[105]T. Cohn.Z. Cui. D. Randell. Taxonomies of logical defined qualitative spatial rules [J]. Journal of Human-Computer Studies.43:831-846.
[106]D. Randell, Z.Cui, T. Cohn. An interval logic for space based on "connection" [C]. ECAI,1992,394-398.
[107]B. Nebel, J. Renz. On the complexity of qualitative spatial reasoning:A maximal tractable fragment of the region connection calculus [J]. Artifical Intellegence, 1999,108(1-2):69-123.
[108]Balbiani P, Condotta JF, Del Cerro LF. A model for reasoning about bidimensional temporal relations [C]. Proceedings, of Principles of Knowledge Representation and Reasoning (KR). Trento, Morgan Kaufmann,1998,124-130.
[109]D. Papadias, Relation-based representation of spatial knowledge [D]. Department of Electrical and Computer Engineering, National Technical University of Athens, 1994.
[110]J. Renz, B. Nebel. On the complexity of qualitative spatial reasoning:A maximal tractable fragment of the region connection calculus, Artificial Intelligence,1999, 108(1-2):69-123.
[111]G. Ligozat. When tables tell it all:Qualitative spatial and temporal reasoning based on linear ordering [C]. Proceedings of COSIT-01, in:Lecture Notes in Comput. Sci., Springer, Berlin,2001,2205:60-75.
[112]王净,江刚武,郭锐.空间方向关系的反转运算[J].测绘科学技术学报,2008,25(5)：324-328.
[113]刘永山,郝忠孝.基于MBR的主方向关系运算[J].哈尔滨工业大学学报,2007,39(11).
[114]S. Cicerone, P. Di. Felice. Cardinal directions between spatial objects:The pairwise-consistency problem [J]. Information Sciences,2004,164 (124):165-188.
[115]Spiros Skiadopoulos, ChriTileos Giannoukos, Nikos Sarkas, Panos Vassiliadis, Timos Sellis, and Manolis Koubarakis. Computing and Managing Cardinal Direction Relations [J]. IEEE transactions on knowledge and data engineering, 2005,17(12):1610-1623.
[116]孙海滨,李文辉.基于结合空间拓扑和方向关系信息的空间推理[J].计算机研究与发展,2006,43(2)：253-259.
[117]陈娟,刘大有,张长海,谢琦.RCC5与主方位关系结合的定性空间推理[J].计算机研究与发展,2008,45 (Suppl1):279-285.
[118]吴静,程朋根,陈斐,毛建华.空间目标的方向关系定性推理[J].测绘学报,2006,35(2)：160-165.
[119]杜世宏,王桥.不确定性空间关系[J].中国图象图形学报,2004,9(5)：539-546
[120]虞强源,刘大有,欧阳继红.基于区间值模糊集的模糊区域拓扑关系模型[J].电子学报,2005,33(1)：186-189.
[121]虞强源,刘大有,刘亚彬.一种不确定区域的扩展蛋黄模型[J].电子学报,2004,32(4)：610-615.
[122]Clementini E, Di Felice P. Approximate topological relations [J]. International Journal of Appoximate Reasoning,1997,16 (2):173-204.
[123]Liu Yaolin, He Jianhua, Yu Yan, Tang Xinming. Indeterminate direction relation model based on fuzzy description framework [J]. Science in China (Series E: Technological Sciences),2008, SI:72-80.
[124]R. Goyal, M.J. Egenhofer. The direction-relation matrix:A representation for directions relations between extended spatial objects [C]. In:The Annual Assembly and the Summer Retreat of University Consortium for Geographic Information Systems Science,1997.
[125]Tsang Edward. Foundations of Constraint Satisfaction [M]. London:Academic Press,1993.
[126]R.Dechter, J.Pearl. Tree clustering for constraint networks [J]. Artificial Intelligence 1989,38:353-366.
[127]R.Dechter. Bucket elimination:A unifying framework for reasoning [J]. Artificial Intelligence,1999,113,41-85.
[128]Gilles Pesant. Counting Solutions of CSPs:A Structural Approach [C]. IJCAI, 2005,260-265.
[129]D. Mehta and M. R. C. van Dongen. Two new lightweight arc-consistency algorithms [C]. In Proceedings of the First International Workshop on Constraint Propagation and Implementation, New York:Springer Press,2004,109-123.
[130]C.Bessiere. Arc consistency and arc consistency again [J]. Artficial Intelligence. 1994,65:179-190.
[131]Bessiere, E. C.Freuder, and J.C.Regin. Using inference to reduce arc consistency computation [C]. IJCAI,1995,592-598.
[132]C.Bessiere and J.-C.Regin. Refining the basic constraint propagation algorithm [C]. IJCAI,2001,309-315.
[133]Christian Bessiere and Jean-Charles Regin. MAC and combined heuristics:Two reasons to forsake FC(and CBJ)on hard problem [C]. Proceedings of First International Conference on Principles and Practice of Constraint Programming, 1996,1118:61-75.
[2]P. B. Ladkin, R. D. Maddux. On binary constraint problems [J]. Journal of the ACM,1993,41(3):435-469.
[3]Alfred Tarski. On the calculus of relations [J]. Journal of Symbolic Logic,1941,6: 73-89.
[4]Daniel S. Weld. Readings in Qualitative Reasoning about Physical Systems [M]. Morgan Kaufmann, San Mateo, CA,1989.
[5]Haar R.Computational models of spatial relations [R]. TR-478, MSC-72-03610.Computer Science, University of Maryland, College Park, MD, 1976.
[6]Andrew U Frank. Qualitative spatial reasoning about cardinal directions [C]. in the 7th Austrian Conference on Artificial Intelligence,1991,157-167.
[7]陈军,赵仁亮.GIS空间关系的基本问题与研究进展[J].测绘学报,1999,28(2)：95-102
[8]谢琦,刘大有,虞强源,陈娟.定性方向关系模型研究进展[J].计算机科学,2006,33(11)：5-9.
[9]Chrisman N. R, Yandell B. S. Effects of point error on area calculations:a statistical model [J]. Surveying and Mapping,1982,48(4):241-246.
[10]Jochen Renz, G'erard Ligozat. Weak Composition for Qualitative Spatial and Temporal Reasoning[C]. in the Eleventh International Conference on Principles and Practice of Constraint Programming (CP'05), Sitges, Spain,2005,534-548.
[11]Brandon Bennett, Amar Isli, Anthony Cohn. When does a Composition Table Provide a Complete and Tractable Proof Procedure for a Relational Constraint Language Proof Procedure for a Relational Constraint Language [C]. in IJCAI-97 Workshop on Spatial and Temporal Reasoning,1997:1-18.
[12]J. Allen. Maintaining Knowledge about Temporal Intervals [J]. Communications of the ACM,1983,26:832-843.
[13]Philippe Balbiani, Jean-Francois Condotta, Luis Farinas delCerro. A new Tractable Subclass of the Rectangle Algebra [C]. in IJCAI-99,1999,442-447.
[14]Randell DA, Cui Z, Cohn AG. A spatial logic based on regions and connection [C]. In:Nebel B, Rich C, Swartout WR, eds.Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning. San Francisco:Morgan Kaufmann Publishers,1992,165-176.
[15]J. Renz, D. Mitra. Qualitative direction calculi with arbitrary granularity [C]. in PRICAI'04,2004:65-74.
[16]P. Balbiani, A. Osmani. A model for reasoning about topologic relations between cyclic intervals [C]. in KR-2000 Breckenridge, Colorado,2000.
[17]A. K. Pujari, G. Vijaya Kumari, A. Sattar. INDU:An Interval and Duration Network [C]. in Australian Joint Conference on Artificial Intelligence,1999, 291-303.
[18]I. Navarrete, A. Sattar, R.Wetprasit, R. Marin. On point-duration networks for temporal reasoning [J]. Artifcial Intelligence,2002,140(1-2):39-70.
[19]A. K. Pujari, A. Sattar. A new framework for reasoning about points, intervals and durations [C]. in 16th International Joint Conferenceon Artificial Intelligence (IJCAI'99), Dean Thomas, Ed.:Morgan Kaufmann Publishers,1999,1259-1267.
[20]Robin hirsch. A finite relation algebra with undecidabel network satisfaction problem [J]. Bulletin of the IGPL,1999,7(4):547-554.
[21]Alan K. Mackworth. Consistency in networks of relations [J]. Artificial Intelligence,1977,8(1):99-118.
[22]Ugo Montanari. Networks of constraints:fundamental properties and applications to picture processing [J]. Information Science,1974,7:95-132.
[23]Alan K. Mackworth, Eugene C. Freuder. The complexity of some polynomial network consistency lgorithms for constraint satisfaction problems. Artificial Intelligence [J],1985,25:65-73.
[24]Peter van Beek. Reasoning about qualitative temporal information. Artificial Intelligence [J],1992,58(1-3):297-321.
[25]Christian 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,162-178.
[26]R. Goyal, M. J Egenhofer. Cardinal directions between extended spatial objects [J]. IEEE Transactions on Knowledge and Data Engineering,2000.
[27]Spiros Skiadopoulos, Manolis Koubarakis. Composing cardinal direction relations [J]. Artificial Intelligence,2004,152:143-171.
[28]Gotts N. M., Gooday J. M., Cohn A.G. A connection based approach to common-sense topological description and reasoning [J]. The Monist,1996,79(1): 51-75.
[29]Jochen Renz, Qualitative Spatial Reasoning with Topological Information [M]. LNCS 2293, Springer Berlin/Heidelberg,2002.
[30]Max J. Egenhofer, Robert D. Franzosa. Point-set Topological Spatial Relations [J]. International Journal of Geographical Information Science,1991,2:161-174.
[31]Randell DA, Cohn AG. Modelling topological and metrical properties in physical processes [C]. In:Brachman R, Levesque H, Reiter R, eds. Proceedings of the 1st International Conference on the Principles of Knowledge Representation and Reasoning. San Francisco:Morgan Kaufmann Publishers,1989,55-66.
[32]Ivo Duntsch, Hui Wang, Steve McCloskey. A relation algebraic approach to the region connection calculus. Theoretical Computer Science,2001,255:63-83.
[33]Sanjiang Li, Mingsheng Ying. Region connection calculus:Its models and composition table [J]. Artificial Intelligence,2003,145:121-146.
[34]Sanjiang Li, Mingsheng Ying. Generalized region connection calculus. Artificial Intelligence [J],2004,160:1-34.
[35]Sanjiang Li, Mingsheng Ying, Yongming Li. On countable RCC models [J]. Fundamenta Informaticae,2003,65:329-351.
[36]Sanjiang Li. On Topological Consistency and Realization [J]. Constraints,2006, 11(1):31-51.
[37]Sanjiang Li, Huaiqing Wang. RCC8 binary constraint network can be consistently extended [J]. Artificial Intelligence,2006,170:1-18.
[38]J.H. OuYang, Q. Fu, D.Y. Liu. A Model for Representing Topological Relations between Simple Concave Regions [C]. Procedings of the 7th International Conference of Computational Science (ICCS2007), Beijing, China, Springer Berlin /Heidelberg,2007,160-167.
[39]M. Egenhofer and M. Vasardani, Spatial Reasoning with a Hole [C]. Conference on Spatial Information Theory (COSIT'07), Springer,2007,303-320.
[40]Egenhofer MJ, Herring JR. Categorizing binary topological relationships between regions, lines and points in geographic database [R].Technical Report,91-7, Orono: University of Maine,1991.
[41]T. Behr, M. Schneider. Topological Relationships of Complex Points and Complex Regions [C]. In:H.S. Kunii, S. Jajodia, A. Solvberg (eds.):The 20the Int. Conf. on Conceptual Modeling. Berlin Heidelberg:Springer-Verlag, LNCS 2224,2004: 56-69.
[42]M. Schneider, T. Behr. Topological Relationships between Complex Spatial Objects [J]. ACM Transactions on Database Systems,2006,31(1):39-81.
[43]S. Li. A Complete Classifcation of Topological Relations Using 9-Intersection Method [J]. International Journal of Geographical Information Science (IJGIS), 2006,20:589-610.
[44]M. McKenney, A. Pauly, R. Praing, M. Schneider. Local Topological Relationships for Complex Regions [C].10th Int. Symp. on Spatial and Temporal Databases (SSTD), LNCS 4605, Springer-Verlag,2007:203-220.
[45]欧阳继红,霍林林,刘大有,富倩.能表达带洞区域拓扑关系的扩展9-交集模型[J].吉林大学学报(工学版),2009,39(6)：1595-1600.
[46]S.Y. Lee, F.J Hsu.2D C-string:a new spatial knowledge representation for image database system [J]. Pattern Recognition,1990,23:1077-1087.
[47]F.P. Coenen, P. Visser. A General Ontology for Spatial Reasoning in Research and Development in Expert Systems XV [C]. Proceedings of ES'98, Berlin: Springer-Verlag,1998:44-57.
[48]Kainz W., Egenhofer M.J., Greasley I.. Modeling spatial relations and operations with partially orders [J]. Geographic Information Systems,1993,7(3):215-229.
[49]J. Chen, CM. Li, ZL. Li, C. Gold. A voronoi-based 9-intersection model for spatial relations [J]. International Journal of Geographical Information Science,2001, 15(3):201-220.
[50]B. Gottfried. Tripartite Line Tracks [C]. International Conference on Computer Vision and Graphics. Proceedings. of ICCVG'2002, Zakopane, Poland,2002, 288-293.
[51]B. Gottfried. Tripartite Line Tracks, Qualitative Curvature Information [C]. In: Kuhn, W., Worboys, M., Timpf, S. (Eds.), Spatial Information Theory: Foundations of Geographic Information Science, International Conference COSIT, Springer, Berlin,2003, LNCS (2825):101-117.
[52]Museros L, Escrig MT. A qualitative theory for shape representation and matching for design [C]. In:LopezdeMantaras R; Saitta L eds. Frontiers in Artificial Intelligence and Applications:Proceedings of 16th European Conference on Artificial Intelligence,2004,110:858-862.
[53]B. Gottfried. Global Feature Schemes for Qualitative Shape Descriptions [C]. In:H. W. Guesgen, Ch. Freksa, G. Ligozat (Ed.), IJCAI-05 Workshop notes on spatial and temporal reasoning. Edinburgh, Scotland,31 July 2005.
[54]B. Gottfried. Characterizing Meanders Qualitatively [C]. In:M. Raubal, H. Miller, A. Frank, M. Goodchild:Geographic Information Scienc. The 4th Int. Conf. of GIScience. Berlin Heidelberg:Springer:Springer LNCS 4197,2006,112-127.
[55]E. Staffetti, A. Grau, F. Serratosa, A. Sanfeliu. Object and image indexing based on Region Connection Calculus and Oriented Matroid Theory. Discrete Applied Mathematics.2005,147(2-3):345-361.
[56]Van de Weghe N, De Tre G, Kuijpers B, De Maeyer P. The double-cross and the generalization concept as a basis for representing and comparing shapes of polylines [C]. In:Meersman R; Tari Z; Herrero P et al. eds. On the Move to Meaningful Internet Systems:Proceedings of the OTM Confederated International Conference and Workshop,2005, LNCS 3762:1087-1096.
[57]A. Schuldt, B. Gottfried, O. Herzog. Retrieving Shapes Efficiently by a Qualitative Shape Descriptor:The Scope Histogram [C]. The 5th Int. Conf. of Image and Video Retrieval (CIVR). Springer, LNCS 4071,2006,261-270.
[58]A. Schuldt, B. Gottfried, O. Herzog. A Compact Shape Representation for Linear Geographical Objects:The Scope Histogram [C]. The 14th ACM Int. Symposium on Advances in Geographic Information Systems (ACM GIS). Arlington, VA, USA,2006,51-58.
[59]B. Gottfried, Arne Schuldt, Otthein Herzog. Extent, Extremum, and Curvature: Qualitative Numeric Features for Efficient Shape Retrieval [C]. KI'07 Proceedings of the 30th annual German conference on Advances in Artificial Intelligence. Osnabruck, Germany,2007,308-322.
[60]B. Gottfried. Qualitative similarity measures—The case of two-dimensional outlines [J]. Computer Vision and Image Understanding,2008,110(1):117-133.
[61]B. Gottfried. Global feature schemes in spatial and temporal reasoning [J]. Spatial Cognition & Computation,2008,8(1):27-46.
[62]Cohn AG. A hierarchical representation of qualitative shape based on connection and convexity [C]. In:Proc of COSIT-95, Semmering,1995,311-326.
[63]A.P. Sistla, C. Yu, Reasoning about qualitative spatial relationships [J]. Journal of Automated Reasoning,2000,25:291-328.
[64]Alfonso Gerevini, Jochen Renz, Combining topological and size information for spatial reasoning [J]. Artificial Intelligence,2002,137(1-2):1-42.
[65]王生生,刘大有,谢琦,王新颖.集成多方面信息的定性空间推理及应用[J].软件学报,2003,14(11)：1857-1862.
[66]Sanjiang Li. Combining Topological and Directional Information for Spatial Reasoning [C]. IJCAI,2007,435-440.
[67]Weiming Liu, Sanjiang Li, Jochen Renz. Combining RCC-8 with Qualitative Direction Calculi:Algorithms and Complexity [C]. IJCAI,2009,854-859.
[68]Reinhard Moratz, Marco Ragni. Qualitative spatial reasoning about relative point position [J]. Journal of visual languages and computing,2008,19:75-98.
[69]J. J. Li, T. Kowalski, J. Renz, and S. Li, Combining Binary Constraint Networks in Qualitative Reasoning [C]. Proceedings of the 18th European Conference on Artificial Intelligence (ECAI'08), Patras, Greece,2008,515-519.
[70]Luo Guo, ShihongDu. Deriving topological relations between regions from direction relations [J]. Journal of Visual Languages and Computing,2009,20: 368-384.
[71]Eliseo Clementini, Spiros Skiadopoulos, Roland Billen, Francesco Tarquini. A Reasoning System of Ternary Projective Relations [C]. IEEE Transactions on Knowledge and Data Engineering,2010,22(2):161-178.
[72]Pequet 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.
[73]S. Skiadopoulos, Nikos Sarkas, Timos Sellis. A family of directional relation models [J]. IEEE Transactions on Knowledge and Data Engineering,2007,19(8): 1116-1130.
[74]S. Skiadopoulos and M. Koubarakis. On the consistency of cardinal direction constraints [J]. Artificial Intelligence,2005,163(1):91-135.
[75]I. Navarrete and G. Sciavicco. Spatial Reasoning with Rectangular Cardinal Direction Relations [C]. ECAI,2006.
[76]I.Navarrete, Morales A. Consistency Checking of Basic Cardinal Constraints over Connected Regions [C]. IJCAI,2007:495-500.
[77]刘永山,郝忠孝.基于MBR的主方向关系一致性检验[J].软件学报,2006,17(5)：976-982.
[78]Shihong Du, Luo Guo, Qiao Wang. A model for describing and composing direction relations between overlapping and contained regions [J]. Information Sciences,2008,178:2928-2949.
[79]Weiming Liu, Xiaotong Zhang, Sanjiang Li, Mingsheng Ying. Reasoning about cardinal directions between extended objects. Artificial Intelligence [J],2010,174: 951-983.
[80]D. Wolter, J. H. Lee. Qualitative reasoning with directional relations [J]. Artificial Intelligence 2010,174:1498-1507.
[81]Philippe Balbiani, Jean-Francois Condotta, Luis Farinas del Cerro. A tractable subclass of block algebra:constraint propagation and preconvex relations [C]. in Portuguese Conference on Artificial Intelligence,1999,75-89.
[82]J. Pacheco, M. T. Escrig, F. Toledo. Integrating 3D Orientation Models [C]. in 5th Catalonian Conference on Artificial Intelligence, Lecture Notes in Artificial Intelligence 2504,2002,88-100
[83]Juan Chen, Dayou Liu, Haiyang Jia, Changhai Zhang, Cardinal direction relations in 3D space [C]. the 2nd International Conference on Knowledge Science, Engineering and Management, KSEM, Melboure, Australia LNAI 4798,2007, 623-629.
[84]Andre Borrmann, Ernst Rank. Specification and implementation of directional operators in a 3D spatial query language for building information models [J]. Advanced Engineering Informatics,2009,23:32-44.
[85]Chang S K, Shi Q S, Yan C W. Iconic Indexing by 2D Strings [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1987,9 (6):413-428.
[86]Chang S K, J ungert E. Symbolic Projection for Image Information Retrieval and Spatial Reasoning [M]. London:Academic Press,1996.
[87]闫浩文,郭仁忠.基于Voronoi图的空间方向关系形式化描述研究(二)[J].测绘学报,2002,27(3)：4-7.
[88]闫浩文,郭仁忠.基于Voronoi图的空间方向关系形式化描述研究(一)[J].测绘学报,,2002,27(1)：24-27.
[89]闫浩文,郭仁忠.空间方向关系基础性问题研究[J].测绘学报,2002,31(4)：357-360.
[90]闫浩文,郭仁忠.基于Voronoi图的空间方向关系形式化描述模型[J].武汉大学学报(信息科学版),2003,28(4)：468-47.
[91]S. Cierone, P.D.Felice. Cardinal relations between regions with a broad boundary [C]. In 8th ACM Symposium on Advances in Geographic Information Systems (GIS'00),2000:15-20.
[92]D. Papadias, N. Karacapilidis, D. Arkoumanis. Processing fuzzy spatial queries:a configuration similarity approach [J]. International Journal of Geographical Information Science Science,1999,13(2):93-118.
[93]杜世宏,王桥,杨一鹏,李治江.空间方向关系模糊描述[J].计算机辅助设计与图形学学报,2005,17(8)：1745-1751.
[94]谢琦,刘大有,虞强源,陈娟.一种不确定区域间的方向关系模型[J].吉林大学学报(理学版),2006,44(5)：748-753.
[95]何建华,刘耀林,俞艳.不确定方向关系的模糊描述模型[J].武汉大学学报(信息科学版),2008,33(3)：257-260.
[96]杜世宏,王桥,魏斌,申文明.空间方向关系粗糙推理[J].测绘学报,2003,32(4)：334-338.
[97]LIU Yu, TIAN Yuan, WENG JingNong. Probabilistic composition of cone-based cardinal direction relations [J]. Sci China Ser E-Tech Sci,2008,51:81-90.
[98]J Allen, P Hayes. A common sense theory of time [C]. IJCAI,1985,1:528-531.
[99]J van Benthem. The Logic of Time Reidel [M], Dordrecht 1983.
[100]P Ladkin. Models of axioms for time intervals [C]. Proceedings of the 6th National Conference on Artificial Intelligence,1987,1:234-239.
[101]G Ligozat. A new proof of tractability for ORD-Horn relations [C]. Proceedings of the 13th National Conference on Artificial Intelligence,1996,1:395-401.
[102]B. Nebel, H. J. Burckert. Reasoning about temporal relations:a maximal tractable subclass of Allen's interval algebra [C]. Proceedings of the 12th National Conference on Artificial Intelligence,1994,1:356-361.
[103]B. Clark. A calculus of individuals based on connection [C]. Notre Dame Journal of Formal Logic,1981,22:204-218.
[104]B. Clark. Individuals and points [J]. Notre Dame Journal of Formal Logic,1985, 26:61-75.
[105]T. Cohn.Z. Cui. D. Randell. Taxonomies of logical defined qualitative spatial rules [J]. Journal of Human-Computer Studies.43:831-846.
[106]D. Randell, Z.Cui, T. Cohn. An interval logic for space based on "connection" [C]. ECAI,1992,394-398.
[107]B. Nebel, J. Renz. On the complexity of qualitative spatial reasoning:A maximal tractable fragment of the region connection calculus [J]. Artifical Intellegence, 1999,108(1-2):69-123.
[108]Balbiani P, Condotta JF, Del Cerro LF. A model for reasoning about bidimensional temporal relations [C]. Proceedings, of Principles of Knowledge Representation and Reasoning (KR). Trento, Morgan Kaufmann,1998,124-130.
[109]D. Papadias, Relation-based representation of spatial knowledge [D]. Department of Electrical and Computer Engineering, National Technical University of Athens, 1994.
[110]J. Renz, B. Nebel. On the complexity of qualitative spatial reasoning:A maximal tractable fragment of the region connection calculus, Artificial Intelligence,1999, 108(1-2):69-123.
[111]G. Ligozat. When tables tell it all:Qualitative spatial and temporal reasoning based on linear ordering [C]. Proceedings of COSIT-01, in:Lecture Notes in Comput. Sci., Springer, Berlin,2001,2205:60-75.
[112]王净,江刚武,郭锐.空间方向关系的反转运算[J].测绘科学技术学报,2008,25(5)：324-328.
[113]刘永山,郝忠孝.基于MBR的主方向关系运算[J].哈尔滨工业大学学报,2007,39(11).
[114]S. Cicerone, P. Di. Felice. Cardinal directions between spatial objects:The pairwise-consistency problem [J]. Information Sciences,2004,164 (124):165-188.
[115]Spiros Skiadopoulos, ChriTileos Giannoukos, Nikos Sarkas, Panos Vassiliadis, Timos Sellis, and Manolis Koubarakis. Computing and Managing Cardinal Direction Relations [J]. IEEE transactions on knowledge and data engineering, 2005,17(12):1610-1623.
[116]孙海滨,李文辉.基于结合空间拓扑和方向关系信息的空间推理[J].计算机研究与发展,2006,43(2)：253-259.
[117]陈娟,刘大有,张长海,谢琦.RCC5与主方位关系结合的定性空间推理[J].计算机研究与发展,2008,45 (Suppl1):279-285.
[118]吴静,程朋根,陈斐,毛建华.空间目标的方向关系定性推理[J].测绘学报,2006,35(2)：160-165.
[119]杜世宏,王桥.不确定性空间关系[J].中国图象图形学报,2004,9(5)：539-546
[120]虞强源,刘大有,欧阳继红.基于区间值模糊集的模糊区域拓扑关系模型[J].电子学报,2005,33(1)：186-189.
[121]虞强源,刘大有,刘亚彬.一种不确定区域的扩展蛋黄模型[J].电子学报,2004,32(4)：610-615.
[122]Clementini E, Di Felice P. Approximate topological relations [J]. International Journal of Appoximate Reasoning,1997,16 (2):173-204.
[123]Liu Yaolin, He Jianhua, Yu Yan, Tang Xinming. Indeterminate direction relation model based on fuzzy description framework [J]. Science in China (Series E: Technological Sciences),2008, SI:72-80.
[124]R. Goyal, M.J. Egenhofer. The direction-relation matrix:A representation for directions relations between extended spatial objects [C]. In:The Annual Assembly and the Summer Retreat of University Consortium for Geographic Information Systems Science,1997.
[125]Tsang Edward. Foundations of Constraint Satisfaction [M]. London:Academic Press,1993.
[126]R.Dechter, J.Pearl. Tree clustering for constraint networks [J]. Artificial Intelligence 1989,38:353-366.
[127]R.Dechter. Bucket elimination:A unifying framework for reasoning [J]. Artificial Intelligence,1999,113,41-85.
[128]Gilles Pesant. Counting Solutions of CSPs:A Structural Approach [C]. IJCAI, 2005,260-265.
[129]D. Mehta and M. R. C. van Dongen. Two new lightweight arc-consistency algorithms [C]. In Proceedings of the First International Workshop on Constraint Propagation and Implementation, New York:Springer Press,2004,109-123.
[130]C.Bessiere. Arc consistency and arc consistency again [J]. Artficial Intelligence. 1994,65:179-190.
[131]Bessiere, E. C.Freuder, and J.C.Regin. Using inference to reduce arc consistency computation [C]. IJCAI,1995,592-598.
[132]C.Bessiere and J.-C.Regin. Refining the basic constraint propagation algorithm [C]. IJCAI,2001,309-315.
[133]Christian Bessiere and Jean-Charles Regin. MAC and combined heuristics:Two reasons to forsake FC(and CBJ)on hard problem [C]. Proceedings of First International Conference on Principles and Practice of Constraint Programming, 1996,1118:61-75.