Spatial Information Theory

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.