Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2015 Volume 30
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

A survey of qualitative spatial representations

  • 1.

    College of Computer Science and Technology

  • 2.

    Key Laboratory of Symbolic Computing and Knowledge Engineering of Ministry of Education

  • 3.

    School of Computing

More Information
  • Abstract: Representation and reasoning with qualitative spatial relations is an important problem in artificial intelligence and has wide applications in the fields of geographic information system, computer vision, autonomous robot navigation, natural language understanding, spatial databases and so on. The reasons for this interest in using qualitative spatial relations include cognitive comprehensibility, efficiency and computational facility. This paper summarizes progress in qualitative spatial representation by describing key calculi representing different types of spatial relationships. The paper concludes with a discussion of current research and glimpse of future work.
  • 加载中
  • Allen J. F.1983. Maintaining knowledge about temporal intervals. Communications of the ACM26(11), 832–843.

    Google Scholar

    Balbiani P., Condotta J.-F., del Cerro L. F.1998. A model for reasoning about bidemensional temporal relations. In Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98), Cohn, A. G., Schubert, L. K. & Shapiro, S. C. (eds). Trento, Italy, June 2–5. Morgan Kaufmann, 124–130.

    Google Scholar

    Balbiani P., Condotta J.-F., del Cerro L. F.1999a. A new tractable subclass of the rectangle algebra. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99, Dean, T. (ed.). Stockholm, Sweden, July 31–August 6. Morgan Kaufmann, 442–447.

    Google Scholar

    Balbiani P., Condotta J.-F., del Cerro L. F.1999b. A tractable subclass of the block algebra: constraint propagation and preconvex relations. In Proceedings of the Progress in Artificial Intelligence, 9th Portuguese Conference on Artificial Intelligence, EPIA ‘99, Évora, Portugal, September 21–24. Lecture Notes in Computer Science 1695, 75–89. Springer.

    Google Scholar

    Balbiani P., Condotta J.-F., Ligozat G.2006. On the consistency problem for the calculus. Journal of Applied Logic4(2), 119–140.

    Google Scholar

    Bédard Y., Merrett T., Han J.2001. Fundamentals of spatial data warehousing for geographic knowledge discovery. In Research Monographs in GIS, Miller, J. M. & Han, J. (eds). chapter 3. Taylor & Francis, 45–68.

    Google Scholar

    Bennett B., Isli A., Cohn A. G.1997. When does a composition table provide a complete and tractable proof procedure for a relational constraint language? In Proceedingsof the IJCAI97 Workshop on Spatial and Temporal Reasoning, NAGOYA, Aichi, Japan, 1–18.

    Google Scholar

    Bittner T.2002. Approximate qualitative temporal reasoning. Annals of Mathematics and Artificial Intelligence36(1–2), 39–80.

    Google Scholar

    Bittner T., Smith B.2001. Granular partitions and vagueness. In Proceedings of the 2nd International Conference on Formal Ontology in Information Systems(FOIS 2001), Welty, C. & Smith, B. (eds). Ogunquit, Maine, USA, October 17–19. ACM Press, 309–320.

    Google Scholar

    Bittner T., Stell J. G.2000. Rough sets in approximate spatial reasoning. In Rough Sets and Current Trends in Computing, Second International Conference, RSCTC 2000 Banff, Canada, October 16–19. Lecture Notes in Computer Science 2005, 445–453. Springer.

    Google Scholar

    Bittner T., Stell J. G.2002. Vagueness and rough location. GeoInformatica6(2), 99–121.

    Google Scholar

    Bogaert P., de Weghe N. V., Cohn A. G., Witlox F., Maeyer P. D.2006. The qualitative trajectory calculus on networks. In Spatial Cognition V: Reasoning, Action, Interaction, International Conference Spatial Cognition 2006, Bremen, Germany, September 24–28, Revised Selected Papers. Lecture Notes in Computer Science 4387, 20–38. Springer.

    Google Scholar

    Chang S., Jungert E., Green R., Gray D., Powers E.1996. Symbolic Projection for Image Information Retrieval and Spatial Reasoning. Elsevier.

    Google Scholar

    Chang S. K., Shi Q. Y., Yan C. W.1987. Iconic indexing by 2-D strings. IEEE Transactions on Pattern Analysis and Machine Intelligence9(3), 413–428.

    Google Scholar

    Chen J., ming Li C., lin Li Z., Gold C. M.2001. A voronoi-based 9-intersection model for spatial relations. International Journal of Geographical Information Science15(3), 201–220.

    Google Scholar

    Chen J., Jia H., Liu D., Zhang C.2010a. Inversing cardinal direction relations. In Proceedings of 5th International Conference on Frontier of Computer Science and Technology (FCST 2010), Stojmenovic, I., Farin, G., Guo, M., Jin, H., Li, K., Hu, L., Wei, X. & Che, X. (eds). Changchun, Jilin Province, China, August 18–22. IEEE Computer Society, 276–281.

    Google Scholar

    Chen J., Jia H., Liu D., Zhang C.2010b.Composing cardinal direction relations based on interval algebra. International Journal of Software and Informatics4(3), 291–303.

    Google Scholar

    Chen J., Jia H., Liu D., Zhang C.2010c.Integrative reasoning with topological, directional and size information based on MBR. Journal of Computer Research and Development47(3), 426–433.

    Google Scholar

    Cicerone S., Felice P. D.2000. Cardinal relations between regions with a broad boundary. In ACM-GIS 2000, Proceedings of the Eighth ACM Symposium on Advances in Geographic Information Systems, Li, K-J., Makki, K., Pissinou, N. & Ravada, S. (eds). Washington D.C., USA, November 10–11. ACM, 15–20.

    Google Scholar

    Cicerone S., Felice P. D.2004. Cardinal directions between spatial objects: the pairwise-consistency problem. Information Sciences164(1–4), 165–188.

    Google Scholar

    Clementini E.2008. Projective relations on the sphere. In Proceedings of Advances in Conceptual Modeling – Challenges and Opportunities, ER 2008 Workshops CMLSA, ECDM, FP-UML, M2AS, RIGiM, SeCoGIS, WISM, Barcelona Spain, October 20–23. Lecture Notes in Computer Science 5232, 313–322. Springer.

    Google Scholar

    Clementini E., Billen R.2006. Modeling and computing ternary projective relations between regions. IEEE Transactions on Knowledge and Data Engineering18(6), 799–814.

    Google Scholar

    Clementini E., Felice P. D.1997. Approximate topological relations. International Journal of Approximate Reasoning16(2), 173–204.

    Google Scholar

    Clementini E., Felice P. D.2001. A spatial model for complex objects with a broad boundary supporting queries on uncertain data. Data Knowledge Engineering37(3), 285–305.

    Google Scholar

    Clementini E., Felice P. D., Hernández D.1997. Qualitative representation of positional information. Artificial Intelligence95(2), 317–356.

    Google Scholar

    Clementini E., Felice P. D., van Oosterom P.1993. A small set of formal topological relationships suitable for end-user interaction. In Proceedings of the Advances in Spatial Databases, Third International Symposium, SSD'93, Singapore, June 23–25. Lecture Notes in Computer Science 692, 277–295. Springer.

    Google Scholar

    Clementini E., Skiadopoulos S., Billen R., Tarquini F.2010. A reasoning system of ternary projective relations. IEEE Transactions on Knowledge and Data Engineering22(2), 161–178.

    Google Scholar

    Cohn A. G.1995. A hierarchical representation of qualitative shape based on connection and convexity. In Proceedings of the Spatial Information Theory: A Theoretical Basis for GIS, International Conference COSIT ‘95, Semmering, Austria, September 21–23. Leecture Notes in Computer Science 988, 311–326. Springer.

    Google Scholar

    Cohn A. G.1997. Qualitative spatial representation and reasoning techniques. In Proceedings of the KI-97: Advances in Artificial Intelligence, 21st Annual German Conference on Artificial Intelligence, Freiburg, Germany, September 9–12. Lecture Notes in Computer Science 1303, 1–30. Springer.

    Google Scholar

    Cohn A. G., Bennett B., Gooday J., Gotts N. M.1997. Qualitative spatial representation and reasoning with the region connection calculus. GeoInformatica1(3), 275–316.

    Google Scholar

    Cohn A. G., Gotts N. M.1996. The ‘egg-yolk’ representation of regions with indeterminate boundaries. In Proceedings GISDATA Specialist Meeting on Spatial Objects with Undetermined Boundaries, Burrough, P. & Frank, A. M. (eds). Francis & Taylor, 171–187.

    Google Scholar

    Cohn A. G., Hazarika S. M.2001. Qualitative spatial representation and reasoning: an overview. Fundamenta Informaticae46(1–2), 1–29.

    Google Scholar

    Cohn A. G., Renz J.2007. Qualitative spatial reasoning. In Handbook of Knowledge Representation (Foundations of Artificial Intelligence), van Harmelen, F., Lifschitz, V. & Porter, B. (eds). chapter 13. Elsevier, 551–596.

    Google Scholar

    Condotta J.-F., Saade M., Ligozat G.2006. A generic toolkit for n-ary qualitative temporal and spatial calculi. In Proceedings of the 13th International Symposium on Temporal Representation and Reasoning (TIME 2006), Budapest, Hungary, June 15–17. IEEE Computer Society, 78–86.

    Google Scholar

    Davis E., Gotts N. M., Cohn A.1999. Constraint networks of topological relations and convexity. Constraints4, 241–280.

    Google Scholar

    Delafontaine M., Cohn A. G., de Weghe N. V.2011. Implementing a qualitative calculus to analyse moving point objects. Expert Systems with Applications38(5), 5187–5196.

    Google Scholar

    Delafontaine M., de Weghe N. V., Bogaert P., Maeyer P. D.2008. Qualitative relations between moving objects in a network changing its topological relations. Information Science178(8), 1997–2006.

    Google Scholar

    de Weghe N. V., Cohn A. G., Maeyer P. D.2004. A qualitative representation of trajectory pairs. In Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAI'2004, including Prestigious Applicants of Intelligent Systems, PAIS 2004, de Mántaras, R. L. & Saitta, L. (eds). Valencia, Spain, August 22–27. IOS Press, 1103–1104.

    Google Scholar

    de Weghe N. V., Cohn A. G., Maeyer P. D., Witlox F.2005a.Representing moving objects in computer-based expert systems: the overtake event example. Expert Systems with Application29(4), 977–983.

    Google Scholar

    de Weghe N. V., Kuijpers B., Bogaert P., Maeyer P. D.2005b. A qualitative trajectory calculus and the composition of its relations. In Proceedings of the GeoSpatial Semantics, First International Conference, GeoS 2005, Mexico, November 29–30. Lecture Notes in Computer Science 3799, 60–76. Springer.

    Google Scholar

    Dong Y., Liu D., Wang F., Wang S., Lü S.2011. A MBR-based modeling method for direction relations between indeterminate regions. Acta Eelectronica Sinica39(2), 329–335.

    Google Scholar

    Du S., Guo L., Wang Q.2008a.A model for describing and composing direction relations between overlapping and contained regions. Information Science178(14), 2928–2949.

    Google Scholar

    Du S., Qin Q., Wang Q., Li B.2005. Fuzzy description of topological relations I: a unified fuzzy 9-intersection model. In Proceedings of the Advances in Natural Computation, First International Conference, ICNC 2005, Part III, Changsha, China, August 27–29. Lecture Notes in Computer Science 3612, 1261–1273. Springer.

    Google Scholar

    Du S., Qin Q., Wang Q., Ma H.2006. Description of combined spatial relations between broad boundary regions based on rough set. In Proceedings of the Intelligent Data Engineering and Automated Learning – IDEAL 2006, 7th International Conference, Burgos, Spain, September 20–23. Lecture Notes in Computer Science 4224, 729–737. Springer.

    Google Scholar

    Du S., Qin Q., Wang Q., Ma H.2008b.Reasoning about topological relations between regions with broad boundaries. International Journal of Approximate Reasoning47(2), 219–232.

    Google Scholar

    Düntsch I., Wang H., McCloskey S.2001. A relation – algebraic approach to the region connection calculus. Theoretical Computer Science255(1–2), 63–83.

    Google Scholar

    Dylla F., Frommberger L., Wallgrün J. O., Wolter D.2006. SparQ: a toolbox for qualitative spatial representation and reasoning. In Proceedings of the Workshop on Qualitative Constraint Calculi: Application and Integration at KI 2006, Bremen, Germany, 79–90.

    Google Scholar

    Egenhofer M. J.2005. Spherical topological relations. Journal on Data Semantics3(1), 25–49.

    Google Scholar

    Egenhofer M. J., Clementini E., Felice P. D.1994a.Topological relations between regions with holes. International Journal of Geographical Information Systems8(2), 129–142.

    Google Scholar

    Egenhofer M. J., Franzosa R. D.1991. Point set topological relations. International Journal of Geographical Information Systems5(2), 161–174.

    Google Scholar

    Egenhofer M. J., Franzosa R. D.1995. On the equivalence of topological relations. International Journal of Geographical Information Systems9(2), 133–152.

    Google Scholar

    Egenhofer M. J., Herring J.1991. Categorizing Binary Topological Relationships between Regions, Lines and Points in Geographic Database. Technical report, University of Maine.

    Google Scholar

    Egenhofer M. J., Mark D. M., Herring J.1994b. The 9-intersection: formalism and its use for natural-language spatial predicates. Technical report, National Center for Geographic Information and Analysis.

    Google Scholar

    Egenhofer M. J., Sharma J.1993. Topological relations between regions in and . In Proceedings of the Advances in Spatial Databases, Third International Symposium, SSD'93, Singapore, June 23–25. Lecture Notes in Computer Science 692, 316–336. Springer.

    Google Scholar

    Egenhofer M. J., Vasardani M.2007. Spatial reasoning with a hole. In Proceedings of the Spatial Information Theory, 8th International Conference, COSIT 2007, Melbourne, Australia, September 19–23. Lecture Notes in Computer Science 4736, 303–320. Springer.

    Google Scholar

    El-Geresy B. A., Abdelmoty A. I.2004. SPARQS: a qualitative spatial reasoning engine. Knowledge Based System17(2–4), 89–102.

    Google Scholar

    Frank A. U.1991. Qualitative spatial reasoning with cardinal directions. In Proceedings of the 7th Austrian Conference on Artificial Intelligence, ÖGAI-91, Wien, September 24–27. Informatik-Fachberichte 287, 157–167. Springer.

    Google Scholar

    Frank A. U.1996. Qualitative spatial reasoning: cardinal directions as an example. International Journal of Geographical Information Science10(3), 269–290.

    Google Scholar

    Franklin N., Henkel L. A., Zangas T.1995. Parsing surrounding space into regions. Memory & Cognition23(4), 397–407.

    Google Scholar

    Freksa C.1992. Using orientation information for qualitative spatial reasoning. In Proceedings of the Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, International Conference GIS – From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning, Pisa, Italy, September 21–23. Lecture Notes in Computer Science 639, 162–178. Springer.

    Google Scholar

    Galton A., Meathrel R. C.1999. Qualitative outline theory. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99, Dean, T. (ed.). Stockholm, Sweden, July 31–August 6. Morgan Kaufmann, 1061–1066.

    Google Scholar

    Gantner Z., Westphal M., Wölfl S.2008. GQR – a fast reasoner for binary qualitative constraint calculi. In Proceedings of the AAAI'08 Workshop on Spatial and Temporal Reasoning, Chicago, Illinois, USA, July 13–14. AAAI Press, 24–29.

    Google Scholar

    Gerevini A., Renz J.2002. Combining topological and size information for spatial reasoning. Artificial Intelligence137(1–2), 1–42.

    Google Scholar

    Gottfried B.2003a. Tripartite line tracks – bipartite line tracks. In Proceedings of the KI 2003: Advances in Artificial Intelligence, 26th Annual German Conference on AI, KI 2003, Hamburg, Germany, September 15–18. Lecture Notes in Computer Science 2821, 535–549. Springer.

    Google Scholar

    Gottfried B.2003b. Tripartite line tracks qualitative curvature information. In Proceedings of the Spatial Information Theory. Foundations of Geographic Information Science, International Conference, COSIT 2003, Ittingen, Switzerland, September 24–28. Lecture Notes in Computer Science 2825, 101–117. Springer.

    Google Scholar

    Gottfried B.2004. Reasoning about intervals in two dimensions. In Proceedings of the IEEE International Conference on Systems, Man & Cybernetics, The Hague, Netherlands, October 10–13. IEEE, 5324–5332.

    Google Scholar

    Gottfried B.2006. Characterising meanders qualitatively. In Geographic Information Science, Proceedings of 4th International Conference, GIScience 2006, Münster, Germany, September 20–23. Lecture Notes in Computer Science 4197, 112–127. Springer.

    Google Scholar

    Gottfried B.2008. Qualitative similarity measures – the case of two-dimensional outlines. Computer Vision and Image Understanding110(1), 117–133.

    Google Scholar

    Gotts N. M., Gooday J. M., Cohn A. G.1996. A connection based approach to common-sense topological description and reasoning. The Monist79(1), 51–75.

    Google Scholar

    Goyal R. K., Egenhofer M. J.2000. Consistent queries over cardinal directions across different levels of detail. In Proceedings of 11th International Workshop on Database and Expert Systems Applications (DEXA'00), Ibrahim, M. T., Küng, J. & Revell, N. (eds). 6–8 September, Greenwich, London, UK. IEEE Computer Society, 876–880.

    Google Scholar

    Goyal R. K., Egenhofer M. J.2001. Similarity of cardinal directions. In Proceedings of the Advances in Spatial and Temporal Databases, 7th International Symposium, SSTD 2001, Redondo Beach, CA, USA, July 12–15. Lecture Notes in Computer Science 2121, 36–58. Springer.

    Google Scholar

    Grenon P.2003. Tucking RCC in Cyc's ontological bed. In IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Gottlob, G. & Walsh, T. (eds). Acapulco, Mexico, August 9–15. Morgan Kaufmann, 894–899.

    Google Scholar

    Guo L., Du S.2009. Deriving topological relations between regions from direction relations. Journal of Visual languages and Computing2(6), 368–384.

    Google Scholar

    Hirsch R.1999. A finite relation algebra with undecidable network satisfaction problem. Logic Journal of the IGPL7(4), 547–554.

    Google Scholar

    Hobbs J. R.1985. Granularity. In Proceedings of the 9th International Joint Conference on Artificial Intelligence, Joshi, A. K. (ed.). Los Angeles, CA, August. Morgan Kaufmann, 432–435.

    Google Scholar

    Huttenlocher J., Hedges L. V., Duncan S.1991. Categories and particulars: prototype effects in estimating spatial location. Psychological Review98(3), 352–376.

    Google Scholar

    Isli A., Cohn A. G.2000. A new approach to cyclic ordering of 2D orientations using ternary relation algebras. Artificial Intelligence122(1–2), 137–187.

    Google Scholar

    Isli A., Haarslev V., Möller R.2003. Combining cardinal direction relations and relative orientation relations in qualitative spatial reasoning. Technical report, University of Hamburg, Department of Informatics.

    Google Scholar

    Kurata Y.2008. The 9+-intersection: a universal framework for modeling topological relations. In Proceedings of the Geographic Information Science, 5th International Conference, GIScience 2008, Park City, UT, USA, September 23–26. Lecture Notes in Computer Science 5266, 181–198. Springer.

    Google Scholar

    Ladkin P. B., Maddux R. D.1994. On binary constraint problems. Journal of the ACM41(3), 435–469.

    Google Scholar

    Langacker R.1987. The Foundations of Cognitive Grammar: volume I: Theoretical Prerequisites, Foundations of Cognitive Grammar. Stanford University Press.

    Google Scholar

    Lee S.-Y., Hsu F.-J.1990. 2D C-string: a new spatial knowledge representation for image database systems. Pattern Recognition23(10), 1077–1087.

    Google Scholar

    Leyton M.1988. A process-grammar for shape. Artificial Intelligence34(2), 213–247.

    Google Scholar

    Li S.2006a.On topological consistency and realization. Constraints11(1), 31–51.

    Google Scholar

    Li S.2006b.A complete classification of topological relations using the 9-intersection method. International Journal of Geographical Information Science20(6), 589–610.

    Google Scholar

    Li S.2007. Combining topological and directional information for spatial reasoning. In IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Veloso, M. M. (ed.). Hyderabad, India, January 6–12. Morgan Kaufmann, 435–440.

    Google Scholar

    Li S., Cohn A. G.2012. Reasoning with topological and directional spatial information. Computational Intelligence28(4), 579–616.

    Google Scholar

    Li S., Liu W.2010. Topological relations between convex regions. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Fox, M. & Poole, D. (eds). Atlanta, Georgia, USA, July 11–15. AAAI Press, 321–326.

    Google Scholar

    Li S., Nebel B.2007. Qualitative spatial representation and reasoning: a hierarchical approach. The Computer Journal50(4), 391–402.

    Google Scholar

    Li S., Wang H.2006. RCC8 binary constraint network can be consistently extended. Artificial Intelligence170(1), 1–18.

    Google Scholar

    Li S., Ying M.2003. Region connection calculus: its models and composition table. Artificial Intelligence145(1–2), 121–146.

    Google Scholar

    Li S., Ying M.2004. Generalized region connection calculus. Artificial Intelligence160(1–2), 1–34.

    Google Scholar

    Li S., Ying M., Li Y.2005. On countable RCC models. Fundamenta Informaticae65(4), 329–351.

    Google Scholar

    Ligozat G.1993. Qualitative triangulation for spatial reasoning. In Proceedings of the Spatial Information Theory: A Theoretical Basis for GIS, International Conference COSIT ‘93, Marciana Marina, Elba Island, Italy, September 19–22. Lecture Notes in Computer Science 716, 54–68. Springer.

    Google Scholar

    Liu D., Hu H., Wang S., Xie Q.2004. Research progress in spatio-temporal reasoning. Journal of Software15(8), 1141–1149.

    Google Scholar

    Liu J.1998. A method of spatial reasoning based on qualitative trigonometry. Artificial Intelligence98(1–2), 137–168.

    Google Scholar

    Liu W., Li S., Renz J.2009. Combining RCC-8 with qualitative direction calculi: algorithms and complexity. In IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Boutilier, C. (ed.). Pasadena, California, USA, July 11–17. AAAI Press, 854–859.

    Google Scholar

    Liu W., Zhang X., Li S., Ying M.2010. Reasoning about cardinal directions between extended objects. Artificial Intelligence174(12–13), 951–983.

    Google Scholar

    Liu Y., Wang X., Jin X., Wu L.2005. On internal cardinal direction relations. In Proceedings of the Spatial Information Theory, International Conference, COSIT 2005, Ellicottville, NY, USA, September 14–18. Lecture Notes in Computer Science 3693, 283–299. Springer.

    Google Scholar

    Moratz R.2006. Representing relative direction as a binary relation of oriented points. In Proceedings of the ECAI 2006, 17th European Conference on Artificial Intelligence, August 29–September 1, 2006, Riva del Garda, Italy, Including Prestigious Applications of Intelligent Systems (PAIS 2006), Frontiers in Artificial Intelligence and Applications. IOS Press, 407–411.

    Google Scholar

    Moratz R., Ragni M.2008. Qualitative spatial reasoning about relative point position. Journal of Visual Languages and Computing19(1), 75–98.

    Google Scholar

    Moratz R., Renz J., Wolter D.2000. Qualitative spatial reasoning about line segments. In ECAI 2000, Proceedings of the 14th European Conference on Artificial Intelligence, Horn, W. (ed.). Berlin, Germany, August 20–25. IOS Press, 234–238.

    Google Scholar

    Moreira J., Ribeiro C., Saglio J.1999. Representation and manipulation of moving points:an extended data model for location estimation. Cartography and Geographic Information Systems26(2), 109–123.

    Google Scholar

    Mossakowski T., Moratz R.2012. Qualitative reasoning about relative direction of oriented points. Artificial Intelligence180–181, 34–45.

    Google Scholar

    Navarrete I., Sciavicco G.2006. Spatial reasoning with rectangular cardinal direction relations. In ECAI 2006, 17th European Conference on Artificial Intelligence, Workshop on Spatialand Temporal Reasoning, Riva del Garda, Italy, August 29–September 1, 1–10.

    Google Scholar

    Ouyang J., Fu Q., Liu D.2009a.A model for representing and reasoning of spatial relations between simple concave regions. Acta Electronica Sinica37(8), 1830–1836.

    Google Scholar

    Ouyang J., Fu Q., Liu D.2009b.Improved method of qualitative shape representation for sameside distinction of concavities. Journal of Jilin University (Engineering and Technology Edition)39(2), 413–418.

    Google Scholar

    Pacheco J., Escrig M. T., Toledo F.2002. Integrating 3D orientation models. In Proceedings of the Topics in Artificial Intelligence, 5th Catalonian Conference on AI, CCIA 2002, Castellón, Spain, October 24–25. Lecture Notes in Computer Science 2504, 88–100. Springer.

    Google Scholar

    Palshikar G. K.2004. Fuzzy region connection calculus in finite discrete space domains. Applied Soft Computing4(1), 13–23.

    Google Scholar

    Pujari A. K., Kumari G. V., Sattar A.1999. : An interval and duration network. In Proceedings of the Advanced Topics in Artificial Intelligence, 12th Australian Joint Conference on Artificial Intelligence, AI ‘99, Sydney, Australia, December 6–10. Lecture Notes in Computer Science 1747, 291–303. Springer.

    Google Scholar

    Randell D. A., Cohn A. G., Cui Z.1992a. Computing transivity tables: a challenge for automated theorem provers. In Proceedings of the Automated Deduction – CADE-11, 11th International Conference on Automated Deduction, Saratoga Springs, NY, USA, June 15–18. Lecture Notes in Computer Science 607, 786–790. Springer.

    Google Scholar

    Randell D. A., Cui Z., Cohn A. G.1992b. A spatial logic based on regions and connection. In Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR'92), Nebel, B., Rich, C. & Swartout, W. R. (eds). Cambridge, MA, October 25-29. Morgan Kaufmann, 165–176.

    Google Scholar

    Renz J.2001. A spatial odyssey of the interval algebra: 1. directed intervals. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Nebel, B. (ed.). Washington, USA, August 4–10. Morgan Kaufmann, 51–56.

    Google Scholar

    Renz J.2002. Qualitative Spatial Reasoning with Topological Information, Lecture Notes in Computer Science 2293. Springer. ISBN 3-540-43346-5.

    Google Scholar

    Renz J., Ligozat G.2005. Weak composition for qualitative spatial and temporal reasoning. In Proceedings of the Principles and Practice of Constraint Programming – CP 2005, 11th International Conference, CP 2005, Sitges, Spain, October 1–5, 2005, Lecture Notes in Computer Science 3709, 534–548. Springer.

    Google Scholar

    Renz J., Nebel B.1999. On the complexity of qualitative spatial reasoning: a maximal tractable fragment of the region connection calculus. Artificial Intelligence108(1–2), 69–123.

    Google Scholar

    Roddick J. F., Spiliopoulou M.2002. A survey of temporal knowledge discovery paradigms and methods. IEEE Transactions on Knowledge and Data Engineering14(4), 750–767.

    Google Scholar

    Röhrig R.1994. A theory for qualitative spatial reasoning based on order relations. In Proceedings of the 12th National Conference on Artificial Intelligence, Hayes-Roth, B. & Korf, R. E. (eds). volume 2, Seattle, WA, USA, July 31–August 4. AAAI Press/The MIT Press, 1418–1423.

    Google Scholar

    Röhrig R.1997. Representation and processing of qualitative orientation knowledge. In KI-97: Advances in Artificial Intelligence, Proceedings of 21st Annual German Conference on Artificial Intelligence, Freiburg, Germany, September 9–12. Lecture Notes in Computer Science 1303, 219–230. Springer.

    Google Scholar

    Roy A. J., Stell J. G.2001. Spatial relations between indeterminate regions. International Journal of Approximate Reasoning27(3), 205–234.

    Google Scholar

    Schneider M.2000. Finite resolution crisp and fuzzy spatial objects. In Proceedings of the 9th International Symposium on Spatial Data Handling(SDH), volume 2, Beijing, China, 3–17.

    Google Scholar

    Schneider M.2003. Design and implementation of finite resolution crisp and fuzzy spatial objects. Data and Knowledge Engineering44(1), 81–108.

    Google Scholar

    Schneider M., Behr T.2006. Topological relationships between complex spatial objects. ACM Transactions on Database System31(1), 39–81.

    Google Scholar

    Schneider M., Chen T., Viswanathan G., Yuan W.2012. Cardinal directions between complex regions. ACM Transactions on Database System37(2), 8–40.

    Google Scholar

    Schockaert S., Cock M. D., Cornelis C., Kerre E. E.2008. Fuzzy region connection calculus: an interpretation based on closeness. International Journal of Approximate Reasoning48(1), 332–347.

    Google Scholar

    Schockaert S., Cock M. D., Kerre E. E.2009. Spatial reasoning in a fuzzy region connection calculus. Artificial Intelligence173(2), 258–298.

    Google Scholar

    Schockaert S., Cornelis C., Cock M. D., Kerre E.2006. Fuzzy spatial relations between vague regions. In Proceedings of the 3rd International IEEE Conference on Intelligent Systems, London UK, September 4–6. International IEEE Conference Print, 221–226.

    Google Scholar

    Scivos A., Nebel B.2004. The finest of its class: the natural point-based ternary calculus for qualitative spatial reasoning. In Spatial Cognition IV: Reasoning, Action, Interaction, International Conference Spatial Cognition 2004, Frauenchiemsee, Germany, October 11–13, Revised Selected Papers. Lecture Notes in Computer Science 3343, 283–303. Springer.

    Google Scholar

    Sirin E., Parsia B.2004. Pellet: an OWL DL reasoner. In Proceedings of the 2004 International Workshop on Description Logics (DL2004), Whistler, British Columbia, Canada, June 6–8. CEUR Workshop Proceedings 104. CEUR-WS.org.

    Google Scholar

    Sistla A. P., Yu C. T.2000. Reasoning about qualitative spatial relationships. Journal of Automated Reasoning25(4), 291–328.

    Google Scholar

    Skiadopoulos S., Koubarakis M.2004. Composing cardinal direction relations. Artificial Intelligence152(2), 143–171.

    Google Scholar

    Skiadopoulos S., Koubarakis M.2005. On the consistency of cardinal direction constraints. Artificial Intelligence163(1), 91–135.

    Google Scholar

    Skiadopoulos S., Sarkas N., Sellis T. K., Koubarakis M.2007. A family of directional relation models for extended objects. IEEE Transactions on Knowledge and Data Engineering19(8), 1116–1130.

    Google Scholar

    Stell J. G.2003. Qualitative extents for spatio-temporal granularity. Spatial Cognition and Computation3, 119–136.

    Google Scholar

    Stickel M. E., Waldinger R. J., Chaudhri V. K.2000. A guide to SNARK. Technical report, AI Center, SRI International.

    Google Scholar

    Stocker M., Sirin E.2009. PelletSpatial: a hybrid RCC-8 and RDF/OWL reasoning and query engine. In Proceedings of the 5th International Workshop on OWL: Experiences and Directions (OWLED 2009), Chantilly, VA, United States, October 23–24. CEUR Workshop Proceedings 529. CEUR-WS.org.

    Google Scholar

    Tarski A.1941. On the calculus of relations. Journal of Symbolic Logic6(3), 73–89.

    Google Scholar

    Vasardani M., Egenhofer M. J.2008. Single-holed regions: their relations and inferences. In Proceedings of the Geographic Information Science, 5th International Conference, GIScience 2008, Park City, UT, USA, September 23–26. Lecture Notes in Computer Science 5266, 337–353. Springer.

    Google Scholar

    Vasardani M., Egenhofer M. J.2009. Comparing relations with a multi-holed region. In Proceedings of the Spatial Information Theory, 9th International Conference, COSIT 2009, Aber Wrac'h, France, September 21–25. Lecture Notes in Computer Science 5756, 159–176. Springer.

    Google Scholar

    Vieu L.1997. Spatial Representation and Reasoning in Artificial Intelligence. Spatial and Temporal Reasoning, 5–41.

    Google Scholar

    Vilain M., Kautz H., van Beek P.1990. Constraint propagation algorithms for temporal reasoning: a revised report. Morgan Kaufmann Publishers Inc., 373–381.

    Google Scholar

    Waldinger R., Jarvis P., Dungan J.2003. Using deduction to choreograph multiple data sources. In Proceedings of the Semantic Web – ISWC 2003: Second International Semantic Web Conference, Sanibel Island, FL, USA, October 20–23. Lecture Notes of Computer Science 2870. Springer.

    Google Scholar

    Wallgrün J. O., Frommberger L., Dylla F., Wolter D.2010. Sparq user manual v0.7. Technical report, SFB/TR 8 spatial Cognition- Project R3-[Q-Shape].

    Google Scholar

    Wallgrün J. O., Frommberger L., Wolter D., Dylla F., Freksa C.2006. Qualitative spatial representation and reasoning in the sparq-toolbox. In Spatial Cognition V: Reasoning, Action, Interaction, International Conference Spatial Cognition 2006, Bremen, Germany, September 24–28, Revised Selected Papers, Lecture Notes in Computer Science 4387, 39–58. Springer.

    Google Scholar

    Wang S., Liu D., Hu H., Wang X.2003. Approximate spatial relation algebra ASRA and application. Journal of Image and Graphics8(8), 946–950.

    Google Scholar

    Wang S., Liu D., Liu J.2005. A new spatial algebra for road network moving objects. International Journal of Information Technology11(12), 47–58.

    Google Scholar

    Wölfl S., Westphal M.2009. On combinations of binary qualitative constraint calculi. In IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Boutilier, C. (ed.). Pasadena, California, USA, July 11–17. AAAI Press, 967–973.

    Google Scholar

    Wolter D., Lee J. H.2010. Qualitative reasoning with directional relations. Artificial Intelligence174(18), 1498–1507.

    Google Scholar

    Yu Q., Liu D., Liu Y.2004. An extended egg-yolk model between indeterminate regions. Acta Eelectronica Sinica32(4), 610–615.

    Google Scholar

    Zhan F. B.1998. Approximate analysis of binary topological relations between geographic regions with indeterminate boundaries. Soft Computing2(2), 28–34.

    Google Scholar

    Zhan F. B., Lin H.2003. Overlay of two simple polygons with indeterminate boundaries. Transactions in GIS7(1), 67–81.

    Google Scholar

    Zimmermann K.1993. Enhancing qualitative spatial reasoning – combining orientation and distance. In Proceedings of the Spatial Information Theory: A Theoretical Basis for GIS, International Conference COSIT ‘93, Marciana Marina, Elba Island, Italy, September 19–22. Lecture Notes in Computer Science 716, 69–76. Springer.

    Google Scholar

    Zimmermann K., Freksa C.1996. Qualitative spatial reasoning using orientation, distance, and path knowledge. Applied Intelligence6(1), 49–58.

    Google Scholar

    Zlatanova S.2000. 3D GIS for Urban Development. PhD thesis, The International Institute for Aerospace Survey and Earth Sciences.

    Google Scholar

  • Cite this article

    Juan Chen, Anthony G. Cohn, Dayou Liu, Shengsheng Wang, Jihong Ouyang, Qiangyuan Yu. 2015. A survey of qualitative spatial representations. The Knowledge Engineering Review 30(1)106−136, doi: 10.1017/S0269888913000350
    Juan Chen, Anthony G. Cohn, Dayou Liu, Shengsheng Wang, Jihong Ouyang, Qiangyuan Yu. 2015. A survey of qualitative spatial representations. The Knowledge Engineering Review 30(1)106−136, doi: 10.1017/S0269888913000350
    shu
Download PDF

Article Metrics

Article views(23) PDF downloads(15)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

A survey of qualitative spatial representations

  • 1.

    College of Computer Science and Technology

  • 2.

    Key Laboratory of Symbolic Computing and Knowledge Engineering of Ministry of Education

  • 3.

    School of Computing

  • Published online: 17 October 2013
The Knowledge Engineering Review  30,  2015, 30(1): 106−136  |  Cite this article

Abstract: Abstract: Representation and reasoning with qualitative spatial relations is an important problem in artificial intelligence and has wide applications in the fields of geographic information system, computer vision, autonomous robot navigation, natural language understanding, spatial databases and so on. The reasons for this interest in using qualitative spatial relations include cognitive comprehensibility, efficiency and computational facility. This paper summarizes progress in qualitative spatial representation by describing key calculi representing different types of spatial relationships. The paper concludes with a discussion of current research and glimpse of future work.

    HTML

    Acknowledgments

    • This work is supported by the National Natural Science Foundation of China under Grant No. 61103091, 61133011, 61170092; Special Funds of Central Colleges Basic Scientific Research Operating Expenses of China, Jilin University under Grant No.200903188, 93K172010Z05, 93K172011K04, 93K172012K11; the DARPA Mind's Eye program (project VIGIL, W911NF-10-C-0083), and the EU in the COGNITO and RACE projects (ICT-248290 and ICT- 87752) at University of Leeds.

    • It is important to distinguish between RCC as a general theory of space, that is, as an axiomatization in first-order logic, and the various constraint languages with varying numbers of JEPD relations (such as RCC5 and RCC8); in these languages the JEPD relations are themselves taken as primitives rather than the C relation. Terms such as RCC8 are usually regarded as referring to the constraint language, though in some presentations the first-order theory interpretation is actually meant.

    • RCC is actually formulated for an arbitrary, fixed, dimension, though most often has been applied in the 2D case.

    • Orientation is an inherent character of objects. For example, an oriented point can be seen as an abstraction of a car, since cars have heads and tails intrinsically. The main difference from direction is that orientation often does not involve reference objects, thus orientation is not a relative relation.

    • If regions are abstracted to MBRs, then the actual topological relations between the actual regions will not in general be correctly reflected. As shown in Figure 13x DC y is satisfied, although using MBRs to abstract the region x and y then MBR(x) PO MBR(b) holds.

    • In general, the distance relation has meaning only when combined with direction relations; strictly speaking, it should be classified into the combination of different spatial calculi as said in section 3.6. But such distance relations are quite common in daily life, so it is selected as a single category.

    • http://www.cril.univ-artois.fr/~saade/QAT/

    • http://www.sfbtr8.uni-bremen.de/project/r3/sparq/

    • http://sfbtr8.informatik.uni-freiburg.de/R4LogoSpace/Tools/gqr.html

    • http://www.opencyc.org/doc/

    • http://www.ai.sri.com/~stickel/snark.html

    • http://clarkparsia.com/pellet/spatial/

    Rights and permissions
    • Copyright © Cambridge University Press 2013 2013Cambridge University Press
References (154)
  • About this article
    Cite this article
    Juan Chen, Anthony G. Cohn, Dayou Liu, Shengsheng Wang, Jihong Ouyang, Qiangyuan Yu. 2015. A survey of qualitative spatial representations. The Knowledge Engineering Review 30(1)106−136, doi: 10.1017/S0269888913000350
    Juan Chen, Anthony G. Cohn, Dayou Liu, Shengsheng Wang, Jihong Ouyang, Qiangyuan Yu. 2015. A survey of qualitative spatial representations. The Knowledge Engineering Review 30(1)106−136, doi: 10.1017/S0269888913000350
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return