Spatial Information Theory

We commonly make decisions based on different kinds of maps, and under varying time constraints. The accuracy of these decisions often can decide even over life and death. In this study, we investigate how varying time constraints and different map types can influence people’s visuo-spatial decision making, specifically for a complex slope detection task involving three spatial dimensions. We find that participants’ response accuracy and response confidence do not decrease linearly, as hypothesized, when given less response time. Assessing collected responses within the signal detection theory framework, we find that different inference error types occur with different map types. Finally, we replicate previous findings suggesting that while people might prefer more realistic looking maps, they do not necessarily perform better with them.

Over the past years user-generated content has gained increasing importance in the area of geographic information science. Private citizens collect environmental data of their neighborhoods and publish it on the web. The wide success of volunteered geographic information relies on the simplicity of such systems. We propose to use sketch maps as a visual user interface, because sketch maps are intuitive, easy to produce for humans and commonly used in human-to-human communication. Sketch maps reflect users’ spatial knowledge that is based on observations rather than on measurements. However, sketch maps, often considered as externalizations of cognitive maps, are distorted, schematized, incomplete, and generalized. Processing spatial information from sketch maps must therefore account for these cognitive aspects. In this paper, we suggest a set of qualitative spatial aspects that should be captured in representations of sketch maps and give empirical evidence that these spatial aspects are robust against typical schematizations and distortions in human spatial knowledge. We propose several existing qualitative spatial calculi to formally represent the spatial aspects, suggest appropriate methods for applying them, and evaluate the proposed representations for alignment of sketch maps and metric maps.

Navigating unfamiliar places is a common problem people face, and there is a wealth of commercial and research-based applications particularly for mobile devices that provide support in these settings. While many of these solutions work well on an individual level, they are less well suited for very crowded situations, e.g. sports matches, festivals and fairs, or events such as pilgrimages. In a large crowd, attending to a mobile device can be hazardous, the underlying technology might not scale well enough, and some people might be excluded due to not having access to a mobile device. Public signage does not suffer from these issues, and consequently, people frequently rely on signage in crowded settings. However, a key disadvantage of public signage is to not provide personalized navigation support. In this paper, we therefore investigate augmented signage as a means to provide navigation support for large crowds. We introduce a scalable signage-based approach and present results from a comparison study contrasting two designs for augmented signage with a base case. The results provide initial evidence that such a system could be easily useable, may help to reduce task load, and has the potential to improve navigation performance.

This paper proposes a new method of navigational assistance in unfamiliar environments. In such environments, major concerns would normally be how to find a good route to a selected destination and how to design and communicate directions to follow that route. This may not be the case, however, if route selection criteria are not complete or subject to change during a trip. To cope with such uncertainty, the proposed method calculates, for each possible move from the current position, a single value characterizing the consequence of that move, e.g., how long it will take to reach the destination if that move is made. The paper outlines a design of a route improvisation support system equipped with this method, and underlines the merit of letting the user build up a route progressively by taking into account highly local, temporary, or personal information that is not stored in the system but collected by the user while traveling.

This paper addresses the role of activity on the construction of route directions. Primary to our conceptualization is that the activity at hand constrains the relevance of spatial information for task performance, as well as the level of granularity at which information is needed. In this paper, we highlight the role of activity for relevance and granularity first based on a review of each of the components involved, and furthermore by a semantic analysis of content patterns in human-generated instructions. The analysis identifies the verbalization styles that are associated with distinct types of activities on the basis of individual keywords that may serve as indicators. We offer a strong theoretical argument for the importance of activities and provide a first step towards an operationalization of this concept, as well as implications for the development of cognitively motivated navigation systems.

Wayfinding activities often pose difficulty, especially for people with poor spatial abilities. If wayfinding aides can take into account individual differences during navigation, targeted assistance may be able to improve wayfinding performance. To enable this, the performance of wayfinders must first be classified. This work proposes a novel method that uses a probabilistic scoring function to classify wayfinding performance using only information available in real-time during route traversal. Training data for the classifier was algorithmically generated as routes representing different levels of wayfinding performance. This approach was tested through an empirical study in which people with different abilities walked from a start to a goal. The results show that performance of wayfinders can be reliably classified into two groups–good and poor–and that this classification can be done using only information available during route traversal. Our results suggest that environmental structure plays an important role in wayfinders’ route choice.

Mereotopologies have traditionally been defined in terms of the intersection of point sets representing the regions in question. Whilst these semantic schemes work well for purely topological aspects, they do not give any semantic insight into the degree to which the different mereotopological relations hold. This paper explores this idea of a distance based interpretation for mereotopology. By introducing a distance measure between x and y, and for various Boolean combinations of x and y, we show that all the RCC8 relations can be distinguished. We then introduce a distance measure which combines these individual measures which we show reflect different paths through the RCC8 conceptual neighbourhood – i.e. the measure decreases/increases monotonically given certain monotonic transitions (such as one region expanding). There are several possible applications of this revised semantics; in the second half of the paper we explore one of these in some depth – the problem of abstracting mereotopological relations from noisy video data, such that the sequences of qualitative relations between pairs of objects do not suffer from “jitter”. We show how a Hidden Markov Model can exploit this distance based semantics to yield improved interpretation of video data at a qualitative level.

A key challenge facing many applications of new geosensor networks technology is to derive meaningful spatial knowledge from low-level sensed data. This paper presents a formal model for representing and computing topological relationship changes between continuously evolving regions monitored by a geosensor network. The definition of “continuity” is used to constrain region evolution and enables the local detection of node state transitions in the network. The model provides a computational framework for the detection of global high-level qualitative relationship changes from local low-level quantitative sensor measurements. In this paper, an efficient decentralized algorithm is also designed and implemented to detect relationship changes and its computational efficiency is evaluated experimentally using simulation.

We present a novel approach to modelling the evolution of spatial entities over time by using bigraphs. We use the links in a bigraph to represent the sharing of a common ancestor and the places in a bigraph to represent spatial nesting as usual. We provide bigraphical reaction rules that are able to model situations such as two crowds of people merging together while still keeping track of the resulting crowd’s historical links.

A large range of monitoring applications can benefit from binary sensor networks. Binary sensors can detect the presence or absence of a particular target in their sensing regions. They can be used to partition a monitored area and provide localization functionality. If many of these sensors are deployed to monitor an area, the area is partitioned into sub-regions: each sub-region is characterized by the sensors detecting targets within it. We aim to maximize the number of unique, distinguishable sub-regions. Our goal is an optimal placement of both omni-directional and directional static binary sensors. We compute an upper bound on the number of unique sub-regions, which grows quadratically with respect to the number of sensors. In particular, we propose arrangements of sensors within a monitored area whose number of unique sub-regions is asymptotically equivalent to the upper bound.

We propose a hybrid geometric-qualitative spatial reasoning system that is able to simultaneously deal with input information that is partially given geometrically and partially qualitatively using spatial relations of different qualitative spatial calculi. The reasoning system combines a geometric reasoning component based on computational geometry methods with a qualitative reasoning component employing relation algebraic reasoning techniques. An egg-yolk representation approach is used to maintain information about objects with underdetermined geometry and also allows for vague objects in the input. In an experimental evaluation we apply the reasoning system to infer geometric information for a set of only qualitatively described objects. The experiments demonstrate that the hybrid reasoning approach produces better results than geometric and qualitative reasoning individually.

We propose CLP(QS), a declarative spatial reasoning framework capable of representing and reasoning about high-level, qualitative spatial knowledge about the world. We systematically formalize and implement the semantics of a range of qualitative spatial calculi using a system of non-linear polynomial equations in the context of a classical constraint logic programming framework. Whereas CLP(QS) is a general framework, we demonstrate its applicability for the domain of Computer Aided Architecture Design. With CLP(QS) serving as a prototype, we position declarative spatial reasoning as a general paradigm open to other formalizations, reinterpretations, and extensions. We argue that the accessibility of qualitative spatial representation and reasoning mechanisms via the medium of high-level, logic-based formalizations is crucial for their utility toward solving real-world problems.

To understand memory of and reasoning about real-world environments, all aspects of the environment, both spatial and non-spatial need to be considered. Non-spatial information can be either integral to or associated with the spatial information. This paper reviews two lines of research conducted in our lab that explore interactions between spatial information and non-spatial information associated with it (namely social information). Based on results of numerous studies, we propose that full accounts of spatial cognition about real-world environments should consider non-spatial influences, noting that some phenomena, while seemingly spatial in nature, may have substantive non-spatial influences.

In a recent study by Haun et al. (2011), Dutch-speaking children who prefer an egocentric (left/right) reference frame when describing spatial relationships, and Hai||om-speaking children who use a geocentric (north/south) frame were found to vary in their capacity to memorize small-scale arrays using their language-incongruent system. In two experiments, we reconcile these results with previous findings by Li et al. (2011) which showed that English (egocentric) and Tseltal Mayan (geocentric) speakers can flexibly use both systems. In Experiment 1, attempting to replicate Haun et al., we found that English- but not Tseltal-speaking children could use their language-incongruent system. In Experiment 2, we demonstrate that Tseltal children can use an egocentric system when instructed nonverbally without left/right language. We argue that Haun et al.’s results are due to the Hai||om children’s lack of understanding of left/right instructions and that task constraints determine which system is easier to use.

We analyze self-reported sense-of-direction in samples of people from Santa Barbara, Freiburg, Saarbrücken, Tokyo, and Beijing. The Santa Barbara Sense-of-Direction Scale (SBSOD) by Hegarty and colleagues primarily assesses survey spatial abilities in directly-experienced environments. It was translated into German, Japanese, and Mandarin Chinese. Results suggest sense-of-direction is a unitary and meaningful concept across the five samples and four languages. In four of the samples, males report significantly better sense-of-direction than do females. Some variations are found across the five samples in overall level of sense-of-direction and in response patterns across the 15 items. Because it is strongly related to the survey spatial thinking that primarily underlies sense-of-direction, and because it can be counted in a relatively straightforward manner, we specifically examine thinking in terms of cardinal directions as a component of sense-of-direction, including conducting a count of cardinal-direction words from Internet corpora in the four languages. We find support for sense-of-direction as a coherent concept across the four languages and as a useful tool to measure individual differences in sense-of-direction. We also consider linguistic/cultural variations in sense-of-direction, especially with respect to variations in physical environments.

This article presents a taxonomy of social spaces distinguishing five basic types: personal space, activity space, affordance space, territory, and penetrated space. The respective space-constituting situations and the mereotopological structure for each social space type are specified. We show how permissions for actions of agents in social spaces can be modeled using the situations calculus. Specifications of social spaces and permissions build the fundament for socially aware action planning.

Formal geometry is a fundamental tool for showing how relevant metric qualities, such as depths, lengths, and volumes, as well as location concepts, such as points, can be constructed from experience. The ontological challenge of information grounding lies in the choice of concepts to consider as primitive, vs. those to be constructed. It also lies in accounting for the relativity and finiteness of experiential space. The grounding approach proposed here constructs geometrical concepts from primitives of the human attentional apparatus for guiding attention and performing perceptual operations. This apparatus enables humans to take attentional steps in their perceived vista environment and to perform geometric comparisons. We account for the relativity of experienced space by constructing locations relative to a reference frame of perceived point-like features. The paper discusses perceptual operations and the idea of point-like features, and introduces a constructive calculus that reflects the generation of domains of geometric comparison from the perspective of an observer. The calculus is then used to construct a model and to motivate an axiomatization of absolute geometry in a finite relativist flavour.

Assisting utterances are helpful for blind and visually impaired map users exploring tactile maps. Virtual tactile maps explorable by haptic human-computer interfaces form the basis for multimodal presentations including automatically generated assisting utterances. This paper presents first empirical results regarding the type of utterances suitable for assisting the acquisition of survey knowledge on the basis of virtual tactile maps. The structure of the internal knowledge base, which has to support a connection between dynamic exploration movements and natural language, is presented. An example illustrates the approach and shows its practicability.

With the increasing success and commercial integration of Volunteered Geographic Information (VGI), the focus shifts away from coverage to data quality and homogeneity. Within the last years, several studies have been published analyzing the positional accuracy of features, completeness of specific attributes, or the topological consistency of line and polygon features. However, most of these studies do not take geographic feature types into account. This is for two reasons. First, and in contrast to street networks, choosing a reference set is difficult. Second, we lack the measures to quantify the degree of feature type mis-categorization. In this work, we present a methodology to analyze the spatial-semantic interaction of point features in Volunteered Geographic Information. Feature types in VGI can be considered special in both, the way they are formed and the way they are applied. Given that they reflect community agreement more accurately than top-down approaches, we argue that they should be used as the primary basis for assessing spatial-semantic interaction. We present a case study on a spatial and semantic subset of OpenStreetMap, and introduce a novel semantic similarity measure based on the change history of OpenStreetMap elements. Our results set the stage for systems that assist VGI contributors in suggesting the types of new features, cleaning up existing data, and integrating data from different sources.

We provide a systematic model of spatial reference frames. The model captures concepts underlying natural language expressions in English that represent both external and internal as well as static and dynamic relationships between entities. Our implementation in the functional language Haskell generates valid English sentences from situations and reference frames. Spatial reference frames are represented by the spatial roles of locatum, relatum, and, optionally, vantage, together with a directional system. Locatum, relatum, and vantage can be filled by entities taking on the discourse roles of speaker, addressee, andparticipant (grammatically expressed by first, second, and third person). Each of these roles may remain unspecified in a linguistic description.

Most approaches to the description of spatial relations for use in spatial querying attempt to describe a set of spatial relations that are universally understood by users. While this method has proved successful for expert users of geographic information, it is less useful for non-experts. Furthermore, while some work has implied the universal nature of spatial relations, a large amount of linguistic evidence shows that many spatial relations vary fundamentally across languages. Natural Semantic Metalanguage (NSM) is a body of linguistic research that has identified the few specific spatial relations that are universal across languages. We show how these spatial relations can be used to describe a range of more complex spatial relations, including some from non-Indo-European languages that cannot readily be described with the usual spatial operators. Thus we propose that NSM is a tool that may be useful for the development of the next generation of spatial querying tools, supporting multilingual environments with widely differing ways of talking about space.

Recent research in cognitive linguistics has shown that a good deal of systematicity is involved in semantic of prepositions, once the many meanings of a single preposition are treated as motivated categories. The aim of this research is to apply a cognitive linguistics analysis for the semantics of a preposition in Farsi. The study takes Tyler and Evans’ [1] approach to polysemy as a means for developing the semantic network of Farsi preposition be with the central meaning similar to English to. For this purpose a large amount of corpus data were analyzed and the semantics of the preposition were studied. The results of the analysis showed that Tyler & Evanss’ Principled polysemy model can be successfully applied to the Farsi preposition be. The analysis sheds light on the semantics of this preposition and highlights the potential ability of this model for the systematic account of prepositions in languages other than English.

Expanding on recent research into the predictability of explicit linguistic spatial information relative to features of discourse structure, we present the results of several machine learning studies which leverage rhetorical relations, events, temporal information, text sequence, and both explicit and implicit linguistic spatial information in three different corpora of narrative discourses. On average, classifiers predict figure, ground, spatial verb and preposition and frame of reference to 75% accuracy, rhetorical relations to 72% accuracy, and events to 76% accuracy (all values have statistical significance above majority class baselines). These results hold independent of the number of authors, subject matter, length and density of spatial and temporal information. Consequently, we argue for a generalized model of spatiotemporal information in narrative discourse, which not only provides a deeper understanding of the semantics and pragmatics of discourse structure, but also alternative robust approaches to analysis.