Spatial Information Theory

This paper reviews progress on the Ethnophysiography study of the Yindjibarndi language from the Pilbara region of Western Australia. Concentrating on terms for water-related features, it concludes that there are significant differences to the way such features are conceptualized and spoken of in English. Brief comments regarding a similar project with the Diné (Navajo) people of Southwestern USA are provided, together with conclusions regarding Ethnophysiography.

This paper examined cultural impacts on absolute and relative location estimates of 12 Eastern Chinese cities, based on questionnaires of each city’s latitude and distances between city pairs. Linear regression analysis of the latitude estimates revealed that the estimated latitude of a city is statistically significantly related to its actual latitude. MDS analysis of the distance estimates revealed the gap that divided Eastern China into two regions and cultural-related causation of the gap was explained in detail. In particular, the Chinese language and its impact on spatial cognition were addressed. Results were compared with North America; some important features of spatial cognition were similar: the categorical storage of spatial information and the absolute-relative location reasoning process.

How do we reason about topological relations? Do people with different cultural backgrounds differ in how they reason about such relations? We conducted two topological reasoning experiments, one in Germany and one in Mongolia to analyze such questions. Topological relations such as “A overlaps B”, “B lies within C” were presented to the participants as premises and they had to find a conclusion that was consistent with the premises (“What is the relation between A and C?”). The problem description allowed multiple possible “conclusions”. Our results, however, indicate that the participants had strong preferences: They consistently preferred one of the possible conclusions and neglected other conclusions, although they were also consistent with the premises. The preferred and neglected conclusions were quite similar in Germany and Mongolia.

This paper shows how to use a top-level ontology to create robust and logically coherent domain ontology in a way that facilitates computational implementation and interoperability. It uses a domain ontology of ecosystem classification and delineation outlined informally Bailey’s paper on ‘Delineation of Ecoregions’ as a running example. Baily’s (from an ontological perspective) rather imprecise and ambiguous definitions are made more logically rigorous and precise by (a) restating the informal definitions formally using the top-level terms whose semantics was specified rigorously in a logic-based top-level ontology and (b) by enforcing the clear distinction of types of relations as specified at the top-level and specific relations of a given type as they occur in the ecosystem domain. In this way it becomes possible to formally distinguish a number of relations which logical interrelations are important but which have been confused and been taken to be a single relation before.

Higher level semantics are considered useful in the geospatial domain, yet there is no general consensus on the form these semantics should take. Indeed, knowledge representation paradigms such as classification based ontologies do not always pay tribute to the complexity of geospatial semantics. Other approaches, originating from psychology, linguistics, philosophy or cognitive sciences are regularly investigated to enrich the GIScientist’s representational toolbox. However, each of these techniques is often used to the exclusion of others, creating new representational difficulties, or merely as a useful addendum to host theories with which they only superficially integrate. The present work is an attempt to introduce a common ground to these techniques by reducing them to the notion of differences or difference spaces. Differences are discernible properties of the environment, detected or produced by a computational process. I describe the following semantic frameworks: category-based ontologies, conceptual spaces, affordance based models, image schemata, and multi representation, explaining how each of them can be projected to a model based on differences. Illustrative examples from table top and geographic space are produced in order to show the model in use.

Consistent and flawless communication between humans and machines is the precondition for a computer to process instructions correctly. While machines use well-defined languages and formal rules to process information, humans prefer natural language expressions with vague semantics. Similarity comparisons are central to the human way of thinking: we use similarity for reasoning on new information or new situations by comparing them to knowledge gained from similar experiences in the past. It is necessary to overcome the differences in representing and processing information to avoid communication errors and computation failures. We introduce an approach to formalize the semantics of natural language spatial relations and specify it in a computational model which allows for similarity comparisons. This paper describes an experiment that investigates human similarity perception between spatial relations and compares it to the similarity determined by the our semantic similarity measure.

When interacting with the environment subjects tend to classify entities with respect to the functionalities they offer for solving specific tasks. The theory of affordances accounts for this agent-environment interaction, while similarity allows for measuring resemblances among entities and entity types. Most similarity measures separate the similarity estimations from the context—the agents, their tasks and environment—and focus on structural and static descriptions of the compared entities and types. This paper argues that an affordance-based representation of the context in which similarity is measured, makes the estimations situation-aware and therefore improves their quality. It also leads to a better understanding of how unfamiliar entities are grouped together to ad-hoc categories, which has not been explained in terms of similarity yet. We propose that types of entities are the more similar the more common functionalities their instances afford an agent. This paper presents a framework for representing affordances, which allows determining similarity between them. The approach is demonstrated through a planning task.

How we categorize certain objects depends on the processes they afford: something is a vehicle because it affords transportation, a house because it offers shelter or a watercourse because water can flow in it. The hypothesis explored here is that image schemas (such as LINK, CONTAINER, SUPPORT, and PATH) capture abstractions that are essential to model affordances and, by implication, categories. To test the idea, I develop an algebraic theory formalizing image schemas and accounting for the role of affordances in categorizing spatial entities.

In order to apply advanced high-level concepts for transportation networks, like hypergraphs, multi-level wayfinding and traffic forecasting, to commercially available street network datasets, it is often necessary to generalise from network primitives. However, the appropriate method of generalisation strongly depends on the complex street network feature they belong to. In this paper, we develop formal expressions for road segments and some essential types of roads, like roundabouts, dual carriageways and freeways. For this purpose, a formal network language is developed, which allows a clear distinction among the geometrical network, its embedding into the Euclidian plane, as well as navigational constraints for a traffic mode.

When animals (including humans) first explore a new environment, what they remember is fragmentary knowledge about the places visited. Yet, they have to use such fragmentary knowledge to find their way home. Humans naturally use more powerful heuristics while lower animals have shown to develop a variety of methods that tend to utilize two key pieces of information, namely distance and orientation information. Their methods differ depending on how they sense their environment. Could a mobile robot be used to investigate the nature of such a process, commonly referred to in the psychological literature as cognitive mapping? What might be computed in the initial explorations and how is the resulting “cognitive map” be used for localization? In this paper, we present an approach using a mobile robot to generate a “cognitive map”, the main focus being on experiments conducted in large spaces that the robot cannot apprehend at once due to the very limited range of its sensors. The robot computes a “cognitive map” and uses distance and orientation information for localization.

Probabilistic robot mapping techniques can produce high resolution, accurate maps of large indoor and outdoor environments. However, much less progress has been made towards robots using these maps to perform useful functions such as efficient navigation. This paper describes a pragmatic approach to mapping system development that considers not only the map but also the navigation functionality that the map must provide. We pursue this approach within a bio-inspired mapping context, and use results from robot experiments in indoor and outdoor environments to demonstrate its validity. The research attempts to stimulate new research directions in the field of robot mapping with a proposal for a new approach that has the potential to lead to more complete mapping and navigation systems.

The paper proposes a novel approach for a scale-dependent geometric simplification of 3D building models that are an integral part of virtual cities. In contrast to real-time photorealistic visualisations, map-like presentations emphasize the specific cartographic properties of objects. For buildings objects, such properties are e.g. the parallel and right-angled arrangements of facade walls and the symmetries of the roof structure. To a map, a clear visual perception of the spatial situation is more important than a detailed reflection of reality. Therefore, the simplification of a 3D building model must be the transformation of the object into its global shape. We present a two-stage algorithm for such an object-specific simplification, which combines primitive instancing and cell decomposition to recreate a basic building model that best fits the objects original shape.

Over-reliance on automated navigation systems may cause users to be “mindless” of the environment and not develop the spatial knowledge that maybe required when automation fails. This research focused on the potential degradation in spatial knowledge acquisition due to the reliance on automatic wayfinding systems. In addition, the impact of “keeping the user in the loop” strategies on spatial knowledge was examined. Participants performed wayfindings tasks in a virtual building with continuous or by-request position indication, in addition to responding to occasional orientation quizzes. Findings indicate that having position indication by request and orientation quizzes resulted in better acquired spatial knowledge. The findings are discussed in terms of keeping the user actively investing mental effort in the wayfinding task as a strategy to reduce the possible negative impact of automated navigation systems.

While navigation instructions in terms of turn instructions and distances are suitable for guiding drivers on roads, a different context of use - like pedestrian navigation - requires extended routing data and algorithms as well as adapted presentation forms to be effective. In our work we study alternative forms of navigation instructions for pedestrians in city environments. In this paper we explore the usefulness of directions given in the form of a short story. To aid retention of navigation instructions and recognition of decision points along the route we have expanded a landmark-based navigation system to present navigation instructions as a sequence of story elements. In this paper we introduce the concept of stories as route descriptions, describe the current prototype implementation, and present preliminary evaluation results from user tests that will guide further development.

The character of a landscape can be seen as the outcome of people’s perception of their physical environment, which is important for spatial planning and decision making. Three modes of landscape perception are proposed: view from a viewpoint, view from a road, and view of an area. Three sampling methods to calculate visibility measures simulate these modes of perception. We compared the results of the three sampling methods for two study areas. The ROPE method provides information about subspaces. The road method enables the analysis of sequences. The grid point method calculates visibility measures at almost every location in space, providing detailed information about transitions and pattern change between original and new situations. The mean visibility values for the study areas reveal major differences between the sampling methods. Combining the results of the three methods is expected to be useful for describing all the facets of landscape perception.

Semantic integrity constraints specify relations between entity classes. These relations must hold to ensure that the data conforms to the semantics intended by the data model. For spatial data many semantic integrity constraints are based on spatial properties like topological or metric relations. Reasoning on such spatial relations and the corresponding derivation of implicit knowledge allow for many interesting applications. The paper investigates reasoning algorithms which can be used to check the internal consistency of a set of spatial semantic integrity constraints. Since integrity constraints are defined at the class level, the logical properties of spatial relations can not directly be applied. Therefore a set of 17 abstract class relations has been defined, which combined with the instance relations enables the specification of integrity constraints. The investigated logical properties of the class relations enable to discover conflicts and redundancies in sets of spatial semantic integrity constraints.

Cavities in spatial phenomena require geometric representations of regions with holes. Existing models for reasoning over topological relations either exclude such specialized regions (9-intersection) or treat them indistinguishably from regions without holes (RCC-8). This paper highlights that inferences over a region with a hole need to be made separately from, and in addition to, the inferences over regions without holes. First the set of 23 topological relations between a region and a region with a hole is derived systematically. Then these relations’ compositions over the region with the hole are calculated so that the inferences can be compared with the compositions of the topological relations over regions without holes. For 266 out of the 529 compositions the results over the region with the hole were more detailed than the corresponding results over regions without holes, with 95 of these refined cases providing even a unique result. In 27 cases, this refinement up to uniqueness compares with a completely undetermined inference for the relations over regions without holes.

This paper describes an algorithm for generating a figure in a two-dimensional plane from a qualitative spatial representation of PLCA. In general, it is difficult to generate a figure from qualitative spatial representations, since they contain positional relationships but do not hold quantitative information such as position and size. Therefore, an algorithm is required to determine the coordinates of the objects while preserving the positional relationships. Moreover, it is more desirable that the resulting figure meets a user’s requirement. PLCA is a simple symbolic representation consisting of points, lines, circuits and areas. We have already proposed one algorithm for drawing, but the resulting figures are far from a “good” one. In that algorithm, we generate the graph corresponding to a given PLCA expression, decompose it into connected subgraphs, determine the coordinates in a unit circle for each subgraph independently, and finally determine the position and size of each subgraph by locating the circles in appropriate positions. This paper aims at generating a “good” figure for a PLCA expression. We use a genetic algorithm to determine the locations and the sizes of circles in the last step of the algorithm. We have succeeded in producing a figure in which objects are drawn as large as possible, with complex parts larger than others. This problem is considered to be a type of “circle packing,” and the method proposed here is applicable to the other problems in which locating objects in a non-convex polygon.

This paper discusses the conceptualization of turn directions along traveled routes. Foremost, we are interested in the influence that language has on the conceptualization of turn directions. Two experiments are presented that contrast the way people group turns into similarity classes when they expect to verbally label the turns, as compared to when they do not. We are particularly interested in the role that major axes such as the perpendicular left and right axis play—are they boundaries of sectors or central prototypes, or do they have two functions: boundary and prototype? Our results support a) findings that linguistic and nonlinguistic categorization differ and b) that prototypes in linguistic tasks serve additionally as boundaries in nonlinguistic tasks, i.e. they fulfill a double function. We conclude by discussing implications for cognitive models of learning environmental layouts and for route-instruction systems in different modalities.

Landmarks are crucial for human wayfinding. Their integration in wayfinding assistance systems is essential for generating cognitively ergonomic route directions. I present an approach to automatically determining references to different types of landmarks. This approach exploits the circular order of a decision point’s branches. It allows uniformly handling point landmarks as well as linear and areal landmarks; these may be functionally relevant for a single decision point or a sequence of decision points. The approach is simple, yet powerful and can handle different spatial situations. It is an integral part of Guard, a process generating context-specific route directions that adapts wayfinding instructions to a route’s properties and environmental characteristics. Guard accounts for cognitive principles of good route directions; the resulting route directions reflect people’s conceptualization of route information.

Previous work is reviewed and an experiment described to examine the spatial and strategic cognitive factors impacting on human orientation in the ‘drop-off’ static orientation scenario, where a person is matching a scene to a map to establish directional correspondence. The relative roles of salient landmarks and scene content and geometry, including space syntax isovist measures, are explored both in terms of general effects, individual differences between participant strategies, and the apparent cognitive processes involved. In general people tend to be distracted by salient 3D landmarks even when they know these will not be detectable on the map, but benefit from a salient 2D landmark whose geometry is present in both images. However, cluster analysis demonstrated clear variations in strategy and in the relative roles of the geometry and content of the scene. Results are discussed in the context of improving future geographic information content.

Data quality and ontology are two of the dominating research topics in GIS, influencing many others. Research so far investigated them in isolation. Ontology is concerned with perfect knowledge of the world and ignores so far imperfections in our knowledge. An ontology for imperfect knowledge leads to a consistent classification of imperfections of data (i.e., data quality), and a formalizable description of the influence of data quality on decisions. If we want to deal with data quality with ontological methods, then reality and the information model stored in the GIS must be represented in the same model. This allows to use closed loops semantics to define “fitness for use” as leading to correct, executable decisions. The approach covers knowledge of physical reality as well as personal (subjective) and social constructions. It lists systematically influences leading to imperfections in data in logical succession.

The concept of the categorical gradient field is introduced to encompass spatially continuous fields of probabilities or membership values in a fixed number of categories. Three models for implementing categorical gradient fields are examined: raster grids, epsilon bands and gradient polygons. Of these, the gradient polygon model shows promise but has not been fully specified. A specification of the model is developed via a four-step process: 1) the constrained Delaunay triangulation of the polygon is created, 2) vertices are added to the polygon edge to ensure consistency, 3) a skeleton of the medial axis is produced and flat spurs are identified, and 4) additional vertices are added along each flat spur. The method is illustrated on a hypothetical transition zone between four adjacent regions, and evaluated according to five general criteria. The model is efficient in terms of data storage, moderately flexible and robust, and intuitive to build and visualize.

Rough sets have been applied in spatial information theory to construct theories of granularity – presenting information at different levels of detail. Mathematical morphology can also be seen as a framework for granularity, and the question of how rough sets relate to mathematical morphology has been raised by Bloch. This paper shows how by developing mathematical morphology in terms of relations we obtain a framework which includes the basic constructions of rough set theory as a special case. The extension of the relational framework to mathematical morphology on graphs rather than sets is explored and new operations of dilations and erosions on graphs are obtained.