Skip to main content

2015 | Buch

Spatial Information Theory

12th International Conference, COSIT 2015, Santa Fe, NM, USA, October 12-16, 2015, Proceedings

herausgegeben von: Sara Irina Fabrikant, Martin Raubal, Michela Bertolotto, Clare Davies, Scott Freundschuh, Scott Bell

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science


Über dieses Buch

This book constitutes the proceedings of the 12th International Conference on Spatial Information Theory, COSIT 2015, held in Santa Fee, NM, USA, in October 2015.

The 22 papers presented in this book were carefully reviewed and selected from 52 full paper submissions. The following topics are addressed: formalizing and modeling space-time, qualitative spatio-temporal reasoning and representation, language and space, signs, images, maps, and other representations of space, navigations by humans and machines.



Formalizing and Modeling Space-Time

Outline of a Formal Theory of Processes and Events, and Why GIScience Needs One
It has often been noted that traditional GIScience, with its focus on data-modelling functions such as the input, storage, retrieval, organisation, manipulation, and presentation of data, cannot readily accommodate the process-modelling functions such as explanation, prediction, and simulation which it is increasingly acknowledged should form an essential element of the GI scientist’s toolkit. Although there are doubtless many different reasons for this seeming incompatibility, this paper singles out for consideration the different views of time presupposed by the two kinds of function: on the one hand, the ‘frozen’ historical time required by data modelling, and on the other, the ‘fluid’ experiential time required by process modelling. Whereas the former places an emphasis on events as discrete completed wholes, the latter is concerned with on-going continuous processes as they evolve from moment to moment. In order to reconcile the data-modelling and process-modelling requirements of GIScience, therefore, a formal theory of processes and events is developed, within which their fundamental properties can be made explicit independently of any specific implementation context, and their relationships systematically investigated.
Antony Galton
Extracting Causal Rules from Spatio-Temporal Data
This paper is concerned with the problem of detecting causality in spatiotemporal data. In contrast to most previous work on causality, we adopt a logical rather than a probabilistic approach. By defining the logical form of the desired causal rules, the algorithm developed in this paper searches for instances of rules of that form that explain as fully as possible the observations found in a data set. Experiments with synthetic data, where the underlying causal rules are known, show that in many cases the algorithm is able to retrieve close approximations to the rules that generated the data. However, experiments with real data concerning the movement of fish in a large Australian river system reveal significant practical limitations, primarily as a consequence of the coarse granularity of such movement data. In response, instead of focusing on strict causation (where an environmental event initiates a movement event), further experiments focused on perpetuation (where environmental conditions are the drivers of ongoing processes of movement). After retasking to search for a different logical form of rules compatible with perpetuation, our algorithm was able to identify perpetuation rules that explain a significant proportion of the fish movements. For example, approximately one fifth of the detected long-range movements of fish over a period of six years were accounted for by 26 rules taking account of variations in water-level alone.
Antony Galton, Matt Duckham, Alan Both
Modelling Spatial Structures
Data is spatial if it contains references to space. We can easily detect explicit references, for example coordinates, but we cannot detect whether data implicitly contains references to space, and whether it has properties of spatial data, if additional semantic information is missing. In this paper, we propose a graph model that meets typical properties of spatial data. We can, by the comparison of a graph representation of a data set to the graph model, decide whether the data set (implicitly or explicitly) has these typical properties of spatial data.
Franz-Benjamin Mocnik, Andrew U. Frank
Strong Spatial Cognition
The ability to perform spatial tasks is crucial for everyday life and of great importance to cognitive agents such as humans, animals, and autonomous robots. Natural embodied and situated agents often solve spatial tasks without detailed knowledge about geometric, topological, or mechanical laws; they directly relate actions to effects enabled by spatio-temporal affordances in their bodies and their environments. Accordingly, we propose a cognitive processing paradigm that makes the spatio-temporal substrate an integral part of the problem-solving engine. We show how spatial and temporal structures in body and environment can support and replace reasoning effort in computational processes: physical manipulation and perception in spatial environments substitute formal computation, in this approach. The strong spatial cognition paradigm employs affordance-based object-level problem solving to complement knowledge-level computation. The paper presents proofs of concept by providing physical spatial solutions to familiar spatial problems for which no equivalent computational solutions are known.
Christian Freksa

Qualitative Spatio-Temporal Reasoning and Representation I

A Conceptual Quality Framework for Volunteered Geographic Information
The assessment of the quality of volunteered geographic information (VGI) is cornerstone to understand the fitness for purpose of datasets in many application domains. While most analyses focus on geometric and positional quality, only sporadic attention has been devoted to the interpretation of the data, i.e., the communication process through which consumers try to reconstruct the meaning of information intended by its producers. Interpretability is a notoriously ephemeral, culturally rooted, and context-dependent property of the data that concerns the conceptual quality of the vocabularies, schemas, ontologies, and documentation used to describe and annotate the geographic features of interest. To operationalize conceptual quality in VGI, we propose a multi-faceted framework that includes accuracy, granularity, completeness, consistency, compliance, and richness, proposing proxy measures for each dimension. The application of the framework is illustrated in a case study on a European sample of OpenStreetMap, focused specifically on conceptual compliance.
Andrea Ballatore, Alexander Zipf
A Coq-Based Axiomatization of Tarski’s Mereogeometry
During the last decade, the domain of Qualitative Spatial Reasoning, has known a renewal of interest for mereogeometry, a theory that has been initiated by Tarski. Mereogeometry relies on mereology, the Leśniewski’s theory of parts and wholes that is further extended with geometrical primitives and appropriate definitions. However, most approaches (i) depart from the original Leśniewski’s mereology which does not assume usual sets as a basis, (ii) restrict the logical power of mereology to a mere theory of part-whole relations and (iii) require the introduction of a connection relation. Moreover, the seminal paper of Tarki shows up unclear foundations and we argue that mereogeometry as it is introduced by Tarski, can be more suited to extend the whole theory of Leśniewski. For that purpose, we investigate a type-theoretical representation of space more closely related with the original ideas of Leśniewski and expressed with the Coq language. We show that (i) it can be given a more clear foundation, (ii) it can be based on three axioms instead of four and (iii) it can serve as a basis for spatial reasoning with full compliance with Leśniewski’s systems.
Richard Dapoigny, Patrick Barlatier
Shape Similarity Based on the Qualitative Spatial Reasoning Calculus eOPRAm
In our paper we investigate the use of qualitative spatial representations (QSR) about relative direction and distance for shape representation. Our new approach has the advantage that we can generate prototypical shapes from our abstract representation in first-order predicate calculus. Using the conceptual neighborhood which is an established concept in QSR we can directly establish a conceptual neighborhood between shapes that translates into a similarity metric for shapes. We apply this similarity measure to a challenging computer vision problem and achieve promising first results.
Christopher H. Dorr, Longin Jan Latecki, Reinhard Moratz
From Metric to Topology: Determining Relations in Discrete Space
This paper considers the nineteen planar discrete topological relations that apply to regions bounded by a digital Jordan curve. Rather than modeling the topological relations with purely topological means, metrics are developed that determine the topological relations. Two sets of five such metrics are found to be minimal and sufficient to uniquely identify each of the nineteen topological relations. Key to distinguishing all nineteen relations are regions’ margins (i.e., the neighborhood of their boundaries). Deriving topological relations from metric properties in \( {\mathbb{R}}^{2} \) vs. \( {\mathbb{Z}}^{2} \) reveals that the eight binary topological relations between two simple regions in \( {\mathbb{R}}^{2} \) can be distinguished by a minimal set of six metrics, whereas in \( {\mathbb{Z}}^{2} \), a more fine-grained set of relations (19) can be distinguished by a smaller set of metrics (5). Determining discrete topological relations from metrics enables not only the refinement of the set of known topological relations in the digital plane, but further enables the processing of raster images where the topological relation is not explicitly stored by reverting to mere pixel counts.
Matthew P. Dube, Jordan V. Barrett, Max J. Egenhofer

Language and Space

Where Snow is a Landmark: Route Direction Elements in Alpine Contexts
Route directions research has mostly focused on urban space so far, highlighting human concepts of street networks based on a range of recurring elements such as route segments, decision points, landmarks and actions. We explored the way route directions reflect the features of space and activity in the context of mountaineering. Alpine route directions are only rarely segmented through decision points related to reorientation; instead, segmentation is based on changing topography. Segments are described with various degrees of detail, depending on difficulty. For landmark description, direction givers refer to properties such as type of surface, dimension, colour of landscape features; terrain properties (such as snow) can also serve as landmarks. Action descriptions reflect the geometrical conceptualization of landscape features and dimensionality of space. Further, they are very rich in the semantics of manner of motion.
Ekaterina Egorova, Thora Tenbrink, Ross S. Purves
Spatial Natural Language Generation for Location Description in Photo Captions
We present a spatial natural language generation system to create captions that describe the geographical context of geo-referenced photos. An analysis of existing photo captions was used to design templates representing typical caption language patterns, while the results of human subject experiments were used to create field-based spatial models of the applicability of some commonly used spatial prepositions. The language templates are instantiated with geo-data retrieved from the vicinity of the photo locations. A human subject evaluation was used to validate and to improve the spatial language generation procedure, examples of the results of which are presented in the paper.
Mark M. Hall, Christopher B. Jones, Philip Smart
More Than a List: What Outdoor Free Listings of Landscape Categories Reveal About Commonsense Geographic Concepts and Memory Search Strategies
Categorization is central to abstraction from real world geographic phenomena to computational representations, and as such has been the subject of considerable research. We report on one common approach, free listing, in an outdoor setting and explore terms elicited in response to the question ‘What is there for you in a landscape?’. We collected term lists, and explanations for the strategies used from 89 participants in two mountain and one parkland setting. We analyzed results not only using term frequency, but also by cognitive saliency, exploring list structures, and building aggregated networks visualizing links between terms. We observed memory search strategies, such as exploiting and switching semantic clusters in our data, with participants using for example not only the local setting to start clusters, but also memories of familiar landscapes to switch between clusters. Our results reveal that simple free listing experiments can help us understand how categories are linked, and also highlight ways in which landscapes are conceptualized.
Flurina M. Wartmann, Ekaterina Egorova, Curdin Derungs, David M. Mark, Ross S. Purves

Signs, Images, Maps, and other Representations of Space

Identifying the Geographical Scope of Prohibition Signs
Prohibition signs warn of actions considered dangerous or annoying. Typically, these signs are located near the beginning of their scope, but knowledge about applicable prohibitions is important at any place within the scope. We developed an automated method to determine the scope of signs, aiming to support volunteered geographic information (VGI) applications that wish to capture prohibitions. In this paper we investigate the problem of computing the scope of geo-referenced signs that refer to human outdoor activities using OpenStreetMap (OSM) data. We analyze the problem and discuss the specific challenges faced. From the analysis we derive a symbolic representation that links activities with (OSM) map features, enabling semantic assessment of map features with respect to a prohibition and reasoning to infer its scope. In a comparative evaluation we demonstrate that our spatial-semantic approach significantly outperforms a previous method based on proximity.
Konstantin Hopf, Florian Dageförde, Diedrich Wolter
Conceptualizing Landscap
A Comparative Study of Landscape Categories with Navajo and English-Speaking Participants
Understanding human concepts, spatial and other, is not only one of the most prominent topics in the cognitive and spatial sciences; it is also one of the most challenging. While it is possible to focus on specific aspects of our spatial environment and abstract away complexities for experimental purposes, it is important to understand how cognition in the wild or at least with complex stimuli works, too. The research presented in this paper addresses emerging topics in the area of landscape conceptualization and explicitly uses a diversity fostering approach to uncover potentials, challenges, complexities, and patterns in human landscape concepts. Based on a representation of different landscapes (images) responses from two different populations were elicited: Navajo and the (US) crowd. Our data provides support for the idea of conceptual pluralism; we can confirm that participant responses are far from random and that, also diverse, patterns exist that allow for advancing our understanding of human spatial cognition with complex stimuli.
Alexander Klippel, David Mark, Jan Oliver Wallgrün, David Stea
Citizen Science Land Cover Classification Based on Ground and Aerial Imagery
If citizen science is to be used in the context of environmental research, there needs to be a rigorous evaluation of humans’ cognitive ability to interpret and classify environmental features. This research, with a focus on land cover, explores the extent to which citizen science can be used to sense and measure the environment and contribute to the creation and validation of environmental data. We examine methodological differences and humans’ ability to classify land cover given different information sources: a ground-based photo of a landscape versus a ground and aerial based photo of the same location. Participants are solicited from the online crowdsourcing platform Amazon Mechanical Turk. Results suggest that across methods and in both ground-based, and ground and aerial based experiments, there are similar patterns of agreement and disagreement among participants across land cover classes. Understanding these patterns is critical to form a solid basis for using humans as sensors in earth observation.
Kevin Sparks, Alexander Klippel, Jan Oliver Wallgrün, David Mark

Qualitative Spatio-Temporal Reasoning and Representation II

Swiss Canton Regions: A Model for Complex Objects in Geographic Partitions
Spatial regions are a fundamental abstraction of geographic phenomena. While simple regions—disk-like and simply connected—prevail, in partitions complex configurations with holes and/or separations occur often as well. Swiss cantons are one highlighting example of these, bringing in addition variations of holes and separations with point contacts. This paper develops a formalism to construct topologically distinct configurations based on simple regions. Using an extension to the compound object model, this paper contributes a method for explicitly constructing a complex region, called a canton region, and also provides a mechanism to determine the corresponding complement of such a region.
Matthew P. Dube, Max J. Egenhofer, Joshua A. Lewis, Shirly Stephen, Mark A. Plummer
Spatial Symmetry Driven Pruning Strategies for Efficient Declarative Spatial Reasoning
Declarative spatial reasoning denotes the ability to (declaratively) specify and solve real-world problems related to geometric and qualitative spatial representation and reasoning within standard knowledge representation and reasoning (KR) based methods (e.g., logic programming and derivatives). One approach for encoding the semantics of spatial relations within a declarative programming framework is by systems of polynomial constraints. However, solving such constraints is computationally intractable in general (i.e. the theory of real-closed fields).
We present a new algorithm, implemented within the declarative spatial reasoning system CLP(QS), that drastically improves the performance of deciding the consistency of spatial constraint graphs over conventional polynomial encodings. We develop pruning strategies founded on spatial symmetries that form equivalence classes (based on affine transformations) at the qualitative spatial level. Moreover, pruning strategies are themselves formalised as knowledge about the properties of space and spatial symmetries. We evaluate our algorithm using a range of benchmarks in the class of contact problems, and proofs in mereology and geometry. The empirical results show that CLP(QS) with knowledge-based spatial pruning outperforms conventional polynomial encodings by orders of magnitude, and can thus be applied to problems that are otherwise unsolvable in practice.
Carl Schultz, Mehul Bhatt
On Distributive Subalgebras of Qualitative Spatial and Temporal Calculi
Qualitative calculi play a central role in representing and reasoning about qualitative spatial and temporal knowledge. This paper studies distributive subalgebras of qualitative calculi, which are subalgebras in which (weak) composition distributives over nonempty intersections. The well-known subclass of convex interval relations is an example of distributive subalgebras. It has been proven for RCC5 and RCC8 that path consistent constraint network over a distributive subalgebra is always minimal and strongly n-consistent in a qualitative sense (weakly globally consistent). We show that the result also holds for the four popular qualitative calculi, i.e. Point Algebra, Interval Algebra, Cardinal Relation Algebra, and Rectangle Algebra. Moreover, this paper gives a characterisation of distributive subalgebras, which states that the intersection of a set of \(m\ge 3\) relations in the subalgebra is nonempty if and only if the intersection of every two of these relations is nonempty. We further compute and generate all maximal distributive subalgebras for those four qualitative calculi mentioned above. Lastly, we establish two nice properties which will play an important role in efficient reasoning with constraint networks involving a large number of variables.
Zhiguo Long, Sanjiang Li
What is in a Contour Map?
A Region-Based Logical Formalization of Contour Semantics
Contours maps (such as topographic maps) compress the information of a function over a two-dimensional area into a discrete set of closed lines that connect points of equal value (isolines), striking a fine balance between expressiveness and cognitive simplicity. They allow humans to perform many common sense reasoning tasks about the underlying function (e.g. elevation).
This paper analyses and formalizes contour semantics in a first-order logic ontology that forms the basis for enabling computational common sense reasoning about contour information. The elicited contour semantics comprises four key concepts – contour regions, contour lines, contour values, and contour sets – and their subclasses and associated relations, which are grounded in an existing qualitative spatial ontology. All concepts and relations are illustrated and motivated by physical-geographic features identifiable on topographic contour maps. The encoding of the semantics of contour concepts in first-order logic and a derived conceptual model as basis for an OWL ontology lay the foundation for fully automated, semantically-aware qualitative and quantitative reasoning about contours.
Torsten Hahmann, E. Lynn Usery

Navigation by Humans and Machines

Learning Spatial Models for Navigation
Typically, autonomous robot navigation relies on a detailed, accurate map. The associated representations, however, do not readily support human-friendly interaction. The approach reported here offers an alternative: navigation with a spatial model and commonsense qualitative spatial reasoning. Both are based on research about how people experience and represent space. The spatial model quickly develops as the result of incremental learning while the robot moves through its environment. In extensive empirical testing, qualitative spatial reasoning principles that reference this model support increasingly effective navigation in a variety of built spaces.
Susan L. Epstein, Anoop Aroor, Matthew Evanusa, Elizabeth I. Sklar, Simon Parsons
Defensive Wayfinding: Incongruent Information in Route Following
Extensive research has focused on what constitutes good route directions, identifying qualities such as the logical sequential ordering, the inclusion of landmarks, and ergonomic ways of referring to turns as critical to delivering cognitively adequate instructions. In many cases, however, people are not actually provided with route directions adhering to these qualities. Yet, often people are still able to successfully navigate to the planned destinations, despite poor or even erroneous direction giving. In this paper, we introduce the concept of defensive wayfinding as the particular type of problem solving people undertake when presented with route directions incongruent with their experience of the environment. We present a systematic investigation of the incompatibilities that may occur between route descriptions and the environment. We note that the content of route directions is produced by the direction giver based on observations of the environment. We develop a classification of the impacts of uncertainty in these observations based on the theory of measurement scales of Stevens [33]. We then relate uncertainty to its impact on route following and the ability of the wayfinder to detect problems during wayfinding. We conclude with a discussion of the impacts of common-sense expectations on the need to engage in defensive wayfinding.
Martin Tomko, Kai-Florian Richter
A Wayfinding Grammar Based on Reference System Transformations
Wayfinding models can be helpful in describing, understanding, and technologically supporting the processes involved in navigation. However, current models either lack a high degree of formalization, or they are not holistic and perceptually grounded, which impedes their use for cognitive engineering. In this paper, we propose a novel formalism that covers the core wayfinding processes, yet is modular in nature by allowing for open slots for those spatial cognitive processes that are modifiable, or not yet well understood. Our model is based on a formal grammar grounded in spatial reference systems and is both interpretable in terms of observable behavior and executable to allow for empirical testing as well as the simulation of wayfinding.
Peter Kiefer, Simon Scheider, Ioannis Giannopoulos, Paul Weiser
Quantifying the Significance of Semantic Landmarks in Familiar and Unfamiliar Environments
During navigation, people tend to associate objects that have outstanding characteristics to useful landmarks. The landmarkness is usually divided into three categories of salience: the visual, the structural, and the semantic. Actually, the roles of visual and structural landmarks have been widely explored at the expense of the semantic salience. Thus, we investigated its significance compared to the two others through an exploratory experiment conducted on the Internet. Specifically, 63 participants were asked to select landmarks along 30 intersections located in Quebec City. Participants were split by gender and familiarity with the study area. Unsurprisingly, the results show that unlike strangers, locals tended to focus on highly semantic landmarks. In addition, we found that women were more influenced by the structural salience than men. Finally, our findings suggest that the side where travelers move compared to the road impacts on the landmark selection process.
Teriitutea Quesnot, Stéphane Roche
Spatial Information Theory
herausgegeben von
Sara Irina Fabrikant
Martin Raubal
Michela Bertolotto
Clare Davies
Scott Freundschuh
Scott Bell
Electronic ISBN
Print ISBN