Jochen Albrecht and Hans Guesgen
Department of Geography - Department of Computer Science
The University of Auckland, Private Bag 92019, Auckland, New Zealand
Email: j.albrecht@auckland.ac.nz, hans@cs.auckland.ac.nz
The concept of space underlying geographic information systems is basically Euclidean and most attempts to deal with imprecise or uncertain geographic information try to accommodate for this imperfection rather than to change the conceptual view. In this paper, we describe a way of incorporating imprecise qualitative spatial reasoning with quantitative reasoning in geographic information systems (GIS). In particular, we show how the common models of geometry can be extended to allow for qualitative spatial reasoning. The idea is to use fuzzy sets to model qualitative spatial relations among objects, such as The downtown shopping mall is close to the harbour. The membership function of such a fuzzy set, in this instance, defines a fuzzy distance operator.
We illustrate a way of incorporating imprecise qualitative spatial reasoning with quantitative reasoning in GIS. For this, we develop a data model to support qualitative spatial reasoning based on constraints, and we provide an example to illustrate our model. We propose a set of locations, each consisting of a vector of base values. We then associate fuzzy membership functions with the locations to describe qualitative spatial information, from which spatial relations and queries can be computed, regardless of the crispness/fuzzyness of the base data.
Keywords: qualitative reasoning, distance operator, proximity measure, perceived space
In spite of their name, GISs have so far been mostly be geometric in nature, ignoring the thematic and temporal dimensions of geographic features (Molenaar 1996, Sinton 1978, Usery 1996). Various attempts to overcome these limitations have been documented in a number of disciplines (Frank 1992, Goodchild 1992, Gupta et al. 1991, Herring 1991, 1992, Raper and Maguire 1992). Several publications deal with extensions of the data model while Allen's work on temporal logic forms the basis for numerous endeavours to deal with dynamic aspects of geographic information (Egenhofer and Golledge 1997, Frank 1994, Peuquet 1994). Applications of fuzzy techniques are most commonly found in remote sensing literature (Altmann 1994, Brimicombe 1997, Molenaar 1996, Plewe 1997) but the inherent fuzziness of geographic features becomes increasingly acknowledged in the geographic information science as well. The notion of qualitative reasoning stems originally from artificial intelligence and has been applied to spatial phenomena only since about 1990 (Freksa 1990, Hernández 1991, Mukerjee and Joe 1990) but has become well established with conference series such as COSIT and the European research initiative SPACENET. Each of these areas will be briefly described, providing the context for the application of qualitative reasoning in the absence of precise geographic data.
A framework, outlining the concept of a hierarchy of spaces, links the different approaches and forms the epistemological background for a new data model proposed in this article. This data model resembles the field view (Goodchild 1992, Worboys 1995) of current GIS, in that it defines (a) a vector of base values for each areal unit and (b) relations and queries on these base values in the form of equations. These equations, however, are based on fuzzy sets rather than crisp sets, and they can be defined across spatial and non-spatial dimensions of the vectors comprising the base data. This way, the whole bounty of (current) GIS operations (requiring crisp data) can be applied to fuzzy data as well.
There is a quite extensive body of literature on the use of fuzzy logic in 2-dimensional spatial applications. One of the first authors to introduce this concept to the area of GeoComputation even before this term had been invented, was Peter Burrough with his standard textbook (1986). While the techniques have been sophisticated since then, the main ideas have remained unchanged, although the range of applications has spread from map-based modelling to now include spatial decision support (Saint-Joan and Mezzadri-Centeno 1998), hierarchical spatial reasoning (Frank 1998), user interface design (Wang), and even psycho-linguistics (Rodrigo and Guesgen). The focus of these authors is on the spatial and semantic fuzziness of geographic objects (Burrough and Frank 1996). Even where operators on fuzzy sets have been defined (e.g. Burrough and McDonnell 1998, p. 274), they are by definition limited to set-based operations and hence possess a rather low-level functionality. They are adequate for the ubiquitous overlay operation but are not to much avail in concert with most of the other fundamental GIS operations (Albrecht 1998) such as 'nearest neighbour' or 'path analysis'.
The Combinatorial Approach
Atkin (1974), and subsequently Gould (1981), Johnson (1981), Beaumont (1984) and others have introduced the algebraic-topological method of Q-analysis as a mean to describe set relations and hierarchical structures in social and planning sciences. Originally, Q-analysis is an aspatial, general purpose (multi-dimensional) data analysis. The following section describes notions that are dear to spatially oriented scientists, namely 'distance', 'neighbourhood', and 'continuity'. Set-oriented analysis can be regarded as a generalisation of the topological routines set in Euclidean space commonly employed in GIS. Couclelis (1996) gives a glimpse of its potential in the use of objects with indeterminate boundaries (hereby bridging the notions of "hard data" and "soft data"). Kemppainen and Albrecht (1996) outline a hierarchy of conceptual spaces as a foundation for the definition of low-level spatial operators (see Figure 1). Some of them, such as 'union' and 'intersection', are more of a technical nature and lend themselves to be mapped to the more general spaces such as (fuzzy) sets. Others, such as 'distance' or 'neighbourhood', are at the core of geographical analysis (Nystuen 1968) and appear more ambiguous but nevertheless find their expression in set-oriented terms as shown below. Yet others, such as 'eccentricity', open new realms of data analysis.
Union and Intersection
The two most basic GIS operations union and intersection
are fundamental in dealing with (fuzzy) sets as well. If {Si},
i Î I, is any family of
sets indexed by some I, then the union of this family of
sets is {x | x Î Si, for
at least one i Î I}. The
union {Si}, i Î I,
may be denoted by 
,
or 
I}.
The intersection of this family of sets is {x|x Î
Si for every i Î I,
that is, x is an element of every member of the family
of sets}.
Distance
A metric space is a set in which we have a measure of the closeness or proximity of two elements of the set, that is, we have a distance defined on the set. A metric is nothing more than the ordinary notion of distance. A set X with metric D is said to be a metric space, and may be denoted by X, D. This distance function may also be expressed in terms of a mapping from V ´ V into the field of scalars Â. It is then expressed as d : V ´ V ® Â with
Neighbourhood
Let X, D be a metric space. If x is any point of X, then we may want to consider all the points of X within a certain distance of x, that is, the set of points of X which are within some degree of nearness to x. Expressed more formally, if X, D is a metric space, x Î X, and p is a positive real number, then the D-p-neighbourhood of x is defined to be the set of all points y of X such that D(x, y) < p; that is, the D-p-neighbourhood of x is defined to be {y Î X | D(x,y) < p}. Where there is no danger of ambiguity, the D-p-neighbourhood of x will be called the p-neighbourhood of x and will be denoted N(x, p). If X, D is a metric space and p is any positive number, then the D-p-neighbourhood N(x, p) of any x Î X is an open set.
Reasoning about neighbourhoods differentiates between operations on open sets (boundaries are not included) and closed sets (boundaries are included). Consequently, the rules for 4-intersections and 9-intersections (Egenhofer and Herring 1990) can be applied.
This definition of neighbourhood can be applied to any n-dimensional object. A number of well-known, but usually difficult to formalise, spatial concepts may be derived from this definition. A set theoretical definition of nearness, for example, assumes each point x to be part of a neighbourhood X. Nearness then means that two points have some overlapping neighbourhoods (see Figure 2).
Eccentricity
We can define the eccentricity e of a simplex in a form
that conforms closely to our everyday use of the word. We call
the dimensionality of a simplex top-q or 
,
and the dimensionality at which it begins to connect with other
simplices bottom-s or 
.
Then one measure of eccentricity is
Gatrell (1991, p. 119) defines space as "a relation defined on a set of objects", which includes just about any structured collection. While singular sets allow for a very limited set of operations only, the relations between two or more sets do provide some powerful methods of (spatial) reasoning. Traditionally, spaces are represented in some form of geometry (thereby neglecting the realms of attribute spaces). The new data model, proposed in this paper, combines n-dimensional Q-analysis with a fuzzy set theoretic reasoning. Based on Beguin and Thiesse (1979) we define a place s as the elementary spatial unit and space S as a set of (at least two) places. Places are separated and this separation can be characterised by their relative position. The distance dL between any two places is a fuzzy membership function. Following the reasoning of the previous section on Q-analysis, this membership function can be n-dimensional if there are at least n places - in which case m A is a measure of extension. A restricted definition of space is given by the triplet (S, dL, m A) which can be simplified if dL is taken to be one instance of m A. Simple attributes m i are described by a membership function over any measurable subset (including the unitary) of places in S. Composite attributes are then defined as functions of simple attributes and/or of basic components of space S. An extended definition of space, therefore, incorporates simple attributes [S, m A,(m i; i Î I)]. Thus, each place is described by a vector [s, m A,(m i; i Î I)] and all the possible places of a space S build an multi-dimensional simplicial complex containing the usual x, y, z spatial coordinates as well as simple and complex attributes. Any query on parts or the whole of this set can then be expressed as an equation defining the membership function either to a spatial or to a semantical object.
The conference presentation will mainly consist of some examples for the new types of queries that can be expressed using the combinatorial fuzzy logic model. Current GIS can be customised to perform an of the queries given beneath, however, the advantage of our proposed model is that it requires no customisation other than a dictionary / library of natural language expressions. The operations in any case are analogue to those implemented in crisp Euclidean-based GIS. Examples for this type of queries are:
Altmann, D. 1994. Fuzzy set-theoretic approaches for handling imprecision in spatial analysis. International Journal of Geographical Information Systems, 8(2):271-189.
Atkin, R. 1974. An approach to structure in architecture and urban design. Environment and Planning B 1:56-67,173-191.
Albrecht, J., 1998. Universal Analytical GIS Operations, In Craglia, M and H. Onsrud (Eds) Geographic Information Research: transatlantic perspectives. London: Taylor & Francis. (in press)
Beaumont, J. 1984. A description of structural change in a central place system: a speculation using Q-analysis. International Journal of Man-Machine Studies 20:567-594.
Beguin H. and J. Thiesse, 1979. An axiomatic approach to geographical space, Geographical Analysis, 11:325-341.
Brimicombe, A. 1997. A universal translator of linguistic hedges for the handling of uncertainty and fitness-of-use in GIS. In Z. Kemp (Ed), Innovations in GIS 4, pp. 115-126. London: Taylor & Francis.
Burrough, P. 1986. Principles of Geographical Information Systems. Oxford: Oxford University Press.
Burrough P. and A. Frank (Eds) 1996. Geographic Objects with Indeterminate Boundaries. GISDATA 2. London: Taylor & Francis.
Burrough, P. and R. McDonnell 1998. Principles of Geographical Information Systems. 2º, Oxford: Oxford University Press.
Couclelis, H. 1996. A typology of geographic entities with ill-defined boundaries. In Burrough, P. and A. Frank (Eds) Geographic Objects With Indeterminate Boundaries, pp. 44-55, GISDATA 2, London: Taylor & Francis.
Egenhofer, M. and R. Golledge 1997. Spatial and Temporal Reasoning in Geographic Information Systems. New York: Oxford University Press.
Egenhofer, M. and J. Herring, 1990. A mathematical framework for the definition of topological relationships. In Brassel, K. and Kishimoto, H. (Eds) Proceedings of the 4th International Symposium on Spatial Data Handling, Zürich, pp. 803-813.
Frank, A. 1992. Spatial concepts, geometric data models, and geometric data structures. Computers and Geosciences, 18:409-417.
Frank, A. 1994. Qualitative temporal reasoning in GIS-ordered time scales. In Proceedings Symposium on Spatial Data Handling. Edinburgh, Scotland. pp. 410-431
Frank, A. 1998. 'Metamodels for Data Quality Description'. In Jeansoulin, R., and M. Goodchild, (Eds) Data quality in Geographic Information: from Error to Uncertainty. Paris: Editions Hermès.
Fisher P. 1998. Sorites paradox and vague geographies. Transactions of the Institute of British Geographers (in press).
Freksa, C. 1990. Qualitative spatial reasoning. Proceedings Workshop RAUM, Koblenz, Germany, pp. 21-36.
Gatrell, A. 1991. Concepts of space and geographical data. In Maguire, D. et al., (Eds) Geographical Information Systems, Vol 1, Harlow: Longmans, pp. 119-134.
Goodchild, M. 1992. Geographic data modeling. Computer and Geosciences, 18:401-408.
Gould, P. 1981. A structural language of relations. In Craig, R and M. Labovitz (Eds) Future Trends in Geomathematics. London: Pion.
Gupta, A., T. Weymouth and R. Jain 1991. An object-oriented data model for large image bases. In Günther O. and H. Schek (Eds), Advances in Spatial Databases, Lecture Notes in Computer Science 525, pp. 45-61. Berlin: Springer.
Hernández, D. 1991. Relative representation of spatial knowledge: the 2-D case. In Mark, D. and A Frank (Eds), Cognitive and Linguistic Aspects of Geographic Space, pp. 373-385. Dordrecht: Kluwer.
Herring, J. 1991. The mathematical modeling of spatial and non-spatial information in geographic information systems. In Mark, D. and A Frank (Eds), Cognitive and Linguistic Aspects of Geographic Space, pp. 313-350. Dordrecht: Kluwer.
Herring, J. 1992. TIGRIS: A data model for an object-oriented geographic information system. Computer and Geosciences, 18:443-452.
Johnson, J. 1981. Some structures and notation of Q-analysis. Environment and Planning B 8:73-86.
Kemppainen, H. and J. Albrecht 1996. Scalability of Spatial Operators. Proceedings GIS/LIS'96 18-21 November 1996 Denver CO, pp. 162-172.
Molenaar, M. 1996. The extensional uncertainty of spatial objects. in Proceedings Symposium of Spatial data Handling 96, pp. 9B1-13. Delft, The Netherlands.
Mukerjee, A. and G. Joe 1990. A qualitative model for space. In Proceedings AAAI-90, pp. 721-727. Boston, MS.
Nystuen, J. 1963. Identification of some fundamental spatial concepts. Papers of the Michigan Academy of Sciences 48, pp. 373-384. Reprinted in Berry, B. and Marble, D., (Eds) Spatial Analysis: a reader in statistical geography. Englewood-Cliffs: Prentice-Hall, pp. 35-41.
Peuquet, D. 1994. It's about time: A conceptual framework for the representation of temporal dynamics in geographic information systems. Annals of the Association of American Geographers, 84(3):441-461.
Plewe, B. 1997. A representation-oriented taxonomy of gradation. In Hirtle, S. and A. Frank (Eds), Spatial Information Theory: A Theoretical Basis for GIS, Lecture Notes in Computer Science 1329, pp. 121-136. New York: Springer.
Raper, J. and D. Maguire 1992. Design models and functionality in GIS. Computer and Geosciences, 18: 387-394.
Rodrigo, S. and H. Guesgen 1998. Fuzzy spatial reasoning in psycholinguistic experiments on braille reading. Proceedings IEEE International Conference on Fuzzy Systems (FUZZ-IEEE '98), pp. 216-219, Anchorage, Alaska.
Saint-Joan, D. and T. Mezzadri-Centeno 1998. GEODES: A Fuzzy Expert System for Spatial Decision Support with GIS. Proceedings Information Processing and Management of Uncertainty in Knowledge-Based Systems, 6-10 July 1998, Paris, France.
Sinton, E. 1978. The inherent structure of information as a constraint to analysis: Mapped thematic data as a case study. In Dutton, D. (Ed) Harvard Papers on Geographic Information Systems, Vol 6. Reading: Addison-Wesley.
Usery, L. 1996. A conceptual framework and fuzzy set implementation for geographic features. In Burrough, P. and A. Frank (Eds), Geographic Objects with Indeterminate Boundaries, GISDATA Series 2, pp. 71-85. London: Taylor & Francis.
Worboys, M. 1995. GIS-a computing perspective. London: Taylor and Francis.