Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

3.1 Introduction

Map generalisation is not simply the simplification of geographic features for legibility purposes but more generally a holistic abstraction process that seeks to represent geographic features at a given scale for a given purpose. Patterns and in particular spatial relations are key to the understanding of geographic space (Mackaness and Edwards 2002). For instance, Fig. 3.1a shows a town symbol placed over a road symbol, which can be expressed as the spatial relation “the town symbol is on the road”. This relation conveys the information to the map reader that the road crosses the town. In contrast, the relation “the town symbol is near the road” (Fig. 3.1b) conveys the information that the road passes by the town. This simple example illustrates the importance of understanding spatial relations in the map generalisation processes. In Fig. 3.1c, the spatial relation “the cycle path is along the road” has to be explicit to adapt the road symbol with an additional dotted centreline. More generally, the generalisation process should as much as possible preserve the spatial relations existing in initial data. For example if a building is within a forest clearing, it should still be there after generalisation (Fig. 3.1d)!

Fig. 3.1
figure 1

The town symbol is on the road when it actually crosses the town (a) or near the road when it passes by the town (b) (©IGN). c The relation “the cycle path follows the road” facilitates the symbolising of the road with the dotted line. d The relation “the building is inside a clearing” should be preserved by generalisation

Full size image

The detection of spatial relations in order to guide generalisation has long been identified as one of the challenges for automation (McMaster and Shea 1988; Brassel and Weibel 1988). To achieve this goal, Mackaness and Edwards (2002) suggested reifying both spatial relations and patterns in order to ensure their preservation during generalisation. In the CartACom model (Ruas and Duchêne 2007; Duchêne et al. 2012), relations are additional objects on which constraints are defined, which guide the generalisation of geographical features.

As a prerequisite we need to formalise spatial relations in order to develop such relation-driven generalisation processes and also to facilitate relational constraint modelling (Burghardt et al. 2007) and to monitor such processes. A better formalisation of spatial relations would also improve process interoperability (Chap. 7) and help users define their needs (Chap. 2) (Touya et al. 2012).

This chapter presents recent research on modelling spatial relations for automatic mapping environments. Its second part describes related work on spatial relations classifications. The third part presents a proposal for a spatial relations ontology and the fourth part explains how such an ontology can be used in automatic environments. Section 3.5 presents a first Case study on spatial relations for 3D city models. Section 3.6 describes the second Case study on relations based on spatial analysis. Section 3.7 details the third use case on data migration guided by explicit relations. Finally, conclusions are drawn on some research perspectives on spatial relations for generalisation.

3.2 Spatial Relations Classification

This section mainly focuses on spatial relations between pairs of geographical objects, but the relations between more than two objects are briefly discussed in Sect. 3.2.3.

3.2.1 Classification and Formalisation of Spatial Relations

Over the past thirty years, several spatial relations classifications have been proposed (Egenhofer and Franzosa 1991; Jones 1997; Ruas 1999; Steiniger and Weibel 2007; Burghardt et al. 2010). They were designed from different points of view, and some were specifically dedicated to map generalisation (Fig. 3.2). We note that most classifications distinguish between topological and geometric relations, the focus being mainly on the former. Steiniger and Weibel (2007) add more detail by subdividing their geometric relations classification into into size, position, shape and orientation relations while semantic relations are divided into similarity, priority, resistance/attraction and causal/logic relations.

Fig. 3.2
figure 2

Several spatial relations classifications, the last three being dedicated to generalisation

Full size image

In respect of the topological relations, models were developed to enable automatic reasoning, such as the 4-intersection model (4IM) (included, includes, covered by, covers, overlaps, equals, meets, disjoint) that manages topological relations between polygons. The most commonly used topological model is the 9-intersection model (Egenhofer and Franzosa 1991), adopted by the OGC, and the Region Connection Calculus (Randell et al. 1992)—somewhat similar to the former.

There are many ways to define a set of spatial relations for an automatic application such as map generalisation. The question then becomes: which one has the greatest utility? Cohn and Hazarika (2001) claim that a set of spatial relations has to be relevant to the task being performed, and that none is universal. Following the same idea, Clementini (2010) divides relations models into three levels: geometric (e.g. touch), computation (e.g. line touch polygon) and user level (e.g. dam touch lake) where application related relations are defined (further discussed in Sect. 3.5.3). In Sect. 3.3, a user level relation model is proposed.

3.2.2 Quantitative Versus Binary Relations

In the literature, two ways of describing a relation between a pair of objects can be found (Touya et al. 2012). The first one quantitatively considers a spatial relation with a measure: e.g. a proximity relation is characterised by a distance, or a relative orientation relation is characterised by an angle (Fig. 3.3a). This is a convenient model for the “metric relations” of Egenhofer and Franzosa (1991). The second way of describing a relation considers a predicate that can be true if the relation exists, or false. For instance, Fig. 3.3b shows a spatial relation described by the predicate is orthogonal to. Only crisp relations are discussed here, fuzzy relations being discussed later in the section.

Fig. 3.3
figure 3

a A relative orientation quantitatively described by an angle. b An orthogonal relation described by a predicate

Full size image

Some authors have defined families of predicates that cover all possible relations between a pair of objects from a particular point of view. In this case, a pair of objects only meets one predicate of the family, e.g. the 4IM or the 9-intersection model (9IM) (Egenhofer and Franzosa 1991). Other families may not follow this principle: for example a family made of two predicates is orthogonal to and is parallel to does not cover all the types of relative orientation.

Whether a model of spatial relations considers one relation (e.g. relative orientation) and several associated predicates (parallel, orthogonal), or several relations (parallelism, orthogonality) is an arbitrary choice. We choose the second, because, in the context of map generalisation, the qualitative evaluation of the preservation or transformation of the relation is easier considering several relations. As a consequence, it is possible to distinguish between quantitative relations (relations described by a quantitative measure) and binary relations (relations described by a predicate, which are present, or not, between a pair of objects). Binary does not refer, here, to the mathematical definition that means that a pair of objects is related.

Now, a particular situation with respect to binary relations is the situation where the relation is not completely present, but almost (Duchêne et al. 2012). For instance, in Fig. 3.4, the building is not strictly parallel to the road but almost parallel: it is not clear if it should read as parallel to the road or not, particularly if scale is reduced. This situation is tricky in the context of generalisation, which seeks to avoid the fuzziness that blurs legibility, and replace it by a sharp relation through caricature. So, for each sharp binary relation we propose to add an associated fuzzy relation in our ontology corresponding to the case where the sharp relation is “almost” present, such as near parallelism.

Fig. 3.4
figure 4

A sharp relation and its fuzzy version considered for cognitive perception limits

Full size image

Fuzzy topological relationships have been studied, [for example by Winter (2000) and Bejaoui et al. (2009)] in the context of objects with fuzzy limits. Here, in the context of generalisation, the same models can be applied, in which the fuzziness is a ‘perceived fuzziness’ due to the ‘noise’ that distracts perception.

To summarise, quantitative and binary relations are distinguished, and among binary relations, sharp and fuzzy relations are further distinguished.

3.2.3 Spatial Relations Between More than Two Features

Up to now, we mainly considered spatial relations between pairs of objects, what Mustière and Moulin (2002) call non-hierarchical relations, in opposition to hierarchical 1-to-n (or n-to-m) relations. Mustière and Moulin (2002) distinguish objects being part of a group [like the components of the meso objects from Ruas and Duchêne (2007)], and objects being inside an area (e.g. a mountain road is inside a mountainous area). For their part, Mackaness and Edwards (2002) state that relations related to patterns or structure can be divided in two categories: taxonomies and partonomies. Taxonomies refer to categorisation hierarchies, e.g. an orchard is a forest. Partonomies refer more to a conceptual and geometrical division of space, e.g. buildings are part of cities (Chaudhry and Mackaness 2007). Mackaness and Chaudhry (2011) propose methods to automatically retrieve urban functional partonomies such as schools (Fig. 3.5) or retail areas from their sub-components.

Fig. 3.5
figure 5

The toponym, buildings, sports fields and footpaths are all functionally related to the complex object school (outlined with dashes)

Full size image

Steiniger and Weibel (2007) proposed a vast classification of spatial relations between more than two objects, divided into two main categories: statistical and density relations and structural relations which cover the partonomies and functional relations. Ternary relations such as above or left, with a reference as third object, are also worth noting (Borrmann and Rank 2009).

3.3 An Ontology of Spatial Relations

In light of the literature previously presented, this section describes a spatial relation ontology dedicated to generalisation and on-demand mapping, first proposed by Touya et al. (2012). The first subsection presents the general model of the ontology, the second proposes a taxonomy integrated to the ontology, and the third focuses on multiple representations relations.

3.3.1 Modelling Spatial Relations

This section describes the formalisation of spatial relations, proposed by Touya et al. (2012), as the upper concepts of an ontology that would contain the spatial relations relevant to generalisation or on-demand mapping (Fig. 3.6). Figure 3.7 shows an instance of the “cycle route follows the road” relation that will be used to explain the features of the proposed model.

Fig. 3.6
figure 6

An OWL model of spatial relations (Touya et al. 2012)

Full size image
Fig. 3.7
figure 7

A cycle route that follows a road

Full size image

A spatial relation has two members denoted as spatial features (e.g. linear road). Each of these spatial features is described by a geographic entity (e.g. road), its geometric primitive (e.g. line) and possibly its feature type (e.g. roads in the INSPIRE schema). As relations are not all symmetrical (e.g. Fig. 3.9e), the property ‘has members’ is divided into ‘has member 1’ and ‘has member 2’.

The ‘condition of achievement’ property describes the configurations where the spatial relation holds. It only applies to binary relations. For instance, a cycle route follows a road when the distance between a part of the route and a part of the road is small. In some geographic contexts, a spatial relation may become irrelevant, which can be described by the ‘condition of relevance’ property of the ontology. For instance, there is no proximity relation between two close buildings that are separated by a river. A spatial relation may be described by several properties. For instance, the follow relation is described by the convergence points (two per convergence section) on the road (Fig. 3.7) and the distance between lines. Finally, relevance and achievement can be assessed by an operation, e.g. the achievement of the follow relation is assessed by a network matching operation (Chap. 5).

3.3.2 A Taxonomy of Spatial Relations for Generalisation

Touya et al. (2012) proposed to fill the ontology with spatial relations following a taxonomy, dedicated to generalisation and on-demand mapping, which combines various classifications presented in the literature (Sect. 3.2.1). A spatial relation belongs to one of the eight types, and can be sharp or fuzzy (Fig. 3.8).

Fig. 3.8
figure 8

Proposed taxonomy for spatial relations between two geographic entities

Full size image

Figures 3.9 and 3.10 show examples of the different relation types of the taxonomy. Topological relations include the 9IM relations (e.g. meet Fig. 3.9a) including as well their fuzzy counterpart (Fig. 3.9b). Relative orthogonality (Fig. 3.9c) and almost parallelism (Fig. 3.9d) are examples of orientation relations. Position relations contain relative position relations (Papadias and Theodoridis 1997; Matsakis et al. 2008) (Fig. 3.9f), that can be specific such as the relative position of buildings with dead ends proposed by Duchêne et al. (2012) (Fig. 3.9e). Proximity relations represent objects close to each other (Fig. 3.9g).

Fig. 3.9
figure 9

Examples of spatial relations

Full size image
Fig. 3.10
figure 10

Further examples of spatial relations

Full size image

Figure 3.10a, b present shape and size relations that generalisation typically seeks to preserve between buildings. The semantic relations can be illustrated by “the road is access to the touristic site” relation (Fig. 3.10c) or by the “lakes are flat” relation with respect to relief, visualised in Fig. 3.10d through contour lines. Finally, so-called movement relations are spatial relations that can be named by a movement verb (Mathet 2000) such as “the river circles the building” (Fig. 3.10e) or “the path passes across the forest” (Fig. 3.10f).

3.3.3 Multiple Representations Relations

Different abstractions of real world features lead to different possible representations for the same features in geographical databases. Mathet (2000) states that some features are polymorph, and can be seen either as polygons, or as lines, or points, in spatial relations. This can be reformulated as spatial relations that may occur between implicit alternative representations of features. For instance, Fig. 3.11e shows a follows spatial relation between a river and the implicit linear representation of a forest area.

Fig. 3.11
figure 11

Spatial relations between a feature and a part (or an implicit structure) of a feature

Full size image

Mustière and Moulin (2002) claim that spatial relations are a scale-dependant notion: spatial relations may occur between representations of features dedicated to different scales. For instance in Fig. 3.11d, the three forest patches can be seen as a line that is a small scale representation of a row of trees along the river.

Finally, some features may be in relation to some small part of a feature and not to the complete feature. For instance, the limit of the forest locally circles the building in Fig. 3.11f, or the building is on a summit in Fig. 3.11a, which is a characteristic part of the relief.

Such kinds of relations can be called multi-representations relations and require an adjustment of the spatial relations model of Fig. 3.6 to be included in the ontology. Corcoran et al. (2012) propose a method to identify and model the multi-representations relation “a set of roads is access to a housing estate”.

3.4 Spatial Relations Ontology to Support Automatic Processes

This sections presents research where the spatial relations ontology could be used in an automatic mapping environment. This can be accomplished by deriving constraints from the ontology or by improving interoperability of automatic processes.

3.4.1 Relational Constraints to Monitor Generalisation

Chapter 2 showed that user specifications for a map generalisation process are commonly expressed by generalisation constraints. Relational constraints are constraints on spatial relations that need to be preserved or caricatured (Duchêne et al. 2012). The spatial relations ontology proposed in the previous section helps to define a relational constraints ontology that would help users define their specifications regarding spatial relations (Fig. 3.12). The deeper the user goes into the ontology hierarchy, the less they have to specify constraint details, when defining their specifications.

Fig. 3.12
figure 12

The constraints ontology derived from Touya et al. (2010) and an example on how the axioms restrict the variables for a user to define their constraints

Full size image

The relations ontology helps defining a taxonomy of relational constraints for generalisation (Fig. 3.13). Four types of relational constraints are identified: (1) the relational preservation constraints that monitor the preservation of salient relations during generalisation; (2) the relation caricature constraints that monitor only fuzzy relations in order to make them sharp (e.g. caricature ‘almost parallel’ relations into ‘parallel’ relations); (3) the relation transformation constraints that change a relation into another during generalisation (e.g. transform road/building parallelism into adjacency); finally, (4) non-creation constraints that prevent non-existing relations from being created by generalisation transformations (e.g. no relative prominence relation between buildings are allowed to be created by building enlargement algorithms).

Fig. 3.13
figure 13

Four types of relational constraints (Touya et al. 2012)

Full size image

3.4.2 From Ontology to Algorithm

A challenge in defining spatial relations in automatic environments such as generalisation is to finding algorithms that assess these relations, i.e. defining the ‘operation’ in the model of Fig. 3.6. It is the same challenge that Steiniger and Weibel (2007) stated as finding measures to identify relations. With respect to possible algorithms, Mathet (2000) proposed geometrical methods to measuring movement relations such as circles or passes through, while Duchêne et al. (2012) proposed algorithms for the relations handled by the CartACom generalisation process.

To create the link between relations in an ontology and the algorithms for assessing them, several approaches have been proposed. A simple but non automatic solution is to semantically annotate the services that encapsulate the algorithms with the relations from the ontology, as proposed in Touya et al. (2010). When an ontology of the measures/algorithms is available, one has only to fill the ‘achievement can be assessed by’ property of the relations ontology (Balley et al. 2012). Finally, Gould and Chaudhry (2012) propose an automatic matching between relations and an algorithm ontology, provided the algorithm capabilities are described in the ontology.

3.5 Case Study I: Spatial Relations for Urban 3D Models

  • Bénédicte Bucher &
  • Gilles Falquet 

  1. Laboratoire COGIT, IGN, Paris, France

    Bénédicte Bucher

  2. Centre for Computer Science, University of Geneva, Geneva, Switzerland

    Gilles Falquet

This section illustrates the relevance of an ontology of spatial relations in the context of applications based on city models. The first subsection describes the context of this use case and the requirements for the ontology. The second subsection describes how CityGML partially meets these requirements and the last subsection details design choices for extending the ontology.

3.5.1 Ontological Requirements for Urban Applications

With the growing availability of city models, more and more applications have begun exploiting possibilities offered by these models to support not only visualisation but also automated operations and analysis. Below are examples of such applications.

Wind comfort for pedestrians in an urban environment is a function of wind velocity. Therefore, the comfort of an urban area can be estimated from the average wind velocity at 1.5 m above ground. In wind comfort simulation applications, such as (Amorim et al. 2012), a 3D city model is needed to provide the geometry (terrain, buildings, vegetation) of the space in which the fluid dynamics simulator must operate. To visualise and exploit the simulation results, the 3D city model must support the representation of air flows and some of their characteristics, such as average speed, location of vortices, etc. It must also represent the relationship between the air flows direction, open spaces, and meteorological conditions.

Visual openness and visual exposure are important characteristics that determine the quality of life in a dwelling area (Fisher-Gewirtzman 2012). Visual exposure measures the number of points from which the interior of an apartment is visible. It can depend on the number of openings in other buildings that are in an intervisibility relationship with one or more openings of the considered apartment. Intervisibility is the combination of a metric relation, the distance between the openings must be sufficiently short, and a projective relation, no opaque object must stand between the two openings.

Urban planning and civil engineering heavily rely on the formulation and evaluation of spatial properties and relations such as solar availability (of a parcel, of a room, of a terrace), intervisibility, minimal distance (between two buildings), walking distance, and accessibility. Moreover design can be seen as the activity of using primitives that can be combined as functional units to compose buildings. (Caneporo et al. 2007) proposed an ontology to support the design of new buildings based on a set of elementary components and relevant properties and relations that act as constraints on the possible combination of these primitives. More recently, Brasebin et al. (2011) have proposed an implementation in a 3D GIS of operations to support the automatic evaluation of 3D spatial relations and properties relevant to urban rules evaluation (Fig. 3.14).

Fig. 3.14
figure 14

Spatial properties and relations useful in urban planning. a Floor area ratio. b Distance between features

Full size image

The first 3D city models were merely dedicated to visualisation and entailed information about the terrain shape together with appearance (textures). More advanced applications call for a more structured model of information. The wind comfort application will require summarising the city in terms of canyons and will need to deliver its result not only as a 3D coverage but also as features related to the cityscape. The visual exposure application will require the evaluation of intervisibility relations. Civil engineering and urban planning will also require computing intervisibility and other spatial relations and properties. Sometimes end users do not have the geocomputational expertise to select the relevant type of data set and derive the necessary information. Furthermore, it should be noted that some relations such as “topological relations” or “touches” do not have the same meaning depending on the understanding of the author. Topology may refer to the fact that at the data level a network is correctly connected. It may also refer to the ability for a driver to go from one street to another at a cross road. While relations between pure geometric entities (points, lines, planes …) are well established, relations between application/urban objects (on the other side, close to, salient …) are more elusive.

To improve the usage of existing city data and the development and sharing of useful software we propose an ontology of spatial properties and relations that are meaningful to users and define their possible computation on available data, 2D or 3D (Bucher et al. 2012):

  • It should serve as a vocabulary for researchers and application designers to avoid ambiguities.

  • It should support the indexation of algorithms and assist an application developer to identify contributions from other disciplines.

  • It could serve as a starting point for defining data types or database schemas for urban applications. Such schemas would be designed based on commonly used algorithms and useful datatypes to support them, such as the topological map datatypes to support routing of network data.

  • The formal definition of relations, coupled with automated reasoning, can be used to automatically infer relations, and, to a certain extent, automatically validate relation computation algorithms.

3.5.2 CityGML

Soon after the explosion of virtual globes, Kolbe et al. (2005) proposed the CityGML model to enrich such terrain models with object, semantics and with more structured geometric information to support automated calculus. This model has been adopted as an OGC standard under continuous revision (OGC 2012). In CityGML, the city is modelled through city objects that have a geometric representation and a thematic representation. Class definitions are proposed for the most important city features: relief, buildings, city furniture, tunnels, bridges, water bodies, transportation (roads and railways), and vegetation (Fig. 3.15). The first introduced relation was the aggregation of objects. There is now the concept of CityObjectGroup to attach properties to an aggregation of objects and to specify the role of each component within the group.

Fig. 3.15
figure 15

CityGML packages [after (OGC 2012)]

Full size image

An important feature of CityGML is to propose a scale to reference meaningful scales (or levels of detail) in cities: LOD0 to LOD4. The same object can have five different such representation (thematic and geometric) corresponding to the different levels in this scale and generalisation relations can also exist between aggregated objects to support the browsing of the city from one LODi to another.

CityGML objects can also have appearances features. The model also supports the explicit representation of topological relation between features and the terrain (or the water) firstly through a property “relativeToTerrain” (resp. “relativeToWater”)—the values ranging from “entirelyAboveTerrain” to “entirelyBelowTerrain” and secondly, for buildings, through a property terrainIntersection whose value is a Multicurve. The geometry used in city models is a profile of the GML3 geometry model. It contains 3D primitives and different kinds of combinations of primitives: composites (combination of elements of the same dimension with topological connections), aggregates (combination with a topological structure) and complex (free combination).

To conclude, CityGML is a big step forward in terms of an ontology of spatial relations and properties but does not fully meet our requirements since it contains a limited set of relations: aggregation, combination of geometries, topological relation with the terrain or water, and a generalisation relation between groups of objects.

3.5.3 Improving CityGML with an Ontology of Spatial Relations

We therefore, propose to extend CityGML with ontological items that will meet the requirements listed above (Fig. 3.16). Some items have already been introduced in this chapter and others are defined in the following section.

Fig. 3.16
figure 16

Spatial relations separated into three levels: application, computational and mathematical

Full size image

Several classification schemes for spatial relations have been mentioned in the beginning of this chapter. Clementini (2010) proposal is especially interesting since it provides a mapping between unambiguous relations and properties expressed in an application context and the possible evaluation of these relations and properties based on automated manipulation of city data. It has been extended in Bucher et al. (2012) to better fit urban applications requirements. Spatial relations may be:

Mathematical relations, i.e. relations that exist in the scientific domain of mathematics. These can be geometric relations (distance, symmetry) or topological relations not always supported by the geometry.

Computational relations, i.e. relations that can be instantiated based on data and Operations (presented earlier in this chapter).

Application relation, i.e. relations that appear in the user’s expression of needs and which reflects their experience of reality and background. Importantly, this level contains many common concepts, properties and relations across applications such as salience, visibility, and shape. As mentioned earlier, application-level relations often bear the same names as geometric relations: touches, between, closer, however, their exact meaning is much more difficult to define. Other application-level relations, such as intervisibility or accessibility, refer to application objects, must satisfy complex conditions, and depend on other objects that form an evaluation context. For application level relations, it is important to specify the Context which describes in what universe the relation holds. For example the intervisibility relation between two windows may suppose that there is neither fog nor truck passing by. This means that for an application, computing intervisibility may require data in addition to the city model, e.g. hypothesis on weather conditions.

Importantly, two important observations were made by Bucher et al. (2012) in the context of an ontology of spatial relations for urban applications.

The first is the property FrameOfReference of a spatial relation that refers to the point of view from which a spatial relation is observed (Trinh et al. 2011). It can be deictic such as in the relations “the street to the right of the church” where the meaning of the relations depends on the location of an observer. It can be intrinsic when it is attached to an object orientation such as “at the front of the car” (a car has a front and a back). In the case where it does not depend on an observer or on an object but depends on an absolute reference system such as “north of” it is called extrinsic. It is true for relations experienced in reality and for relations experienced in the representation: there are several ways for a user to interact with a 3D model of a city: they can manipulate the model as a single object (a digital mockup) or focus on an individual object (e.g. a building) or navigate within the model to simulate the experience of a human being walking in the city. The 3D model may also be used in an augmented reality application on a tablet or smartphone. These interaction patterns correspond to different frames of reference (absolute, object-centered, user-centered, etc.) and hence to different ways of understanding and computing relations such as left of, behind, etc. Frames of reference can be absolute—independent from the observer- or relative to an observer point of view (first person or third person).

The second observation relates to non binary relations that occur in many simulation applications: objects are interfaces between two other objects (e.g. for a car, a street network is the interface between an area to downtown). This is an extension from Billen et al. (2012) who suggested that buildings be described as a set of interfaces between outer empty space and indoor empty space with windows being the connections for specific agents (such as air). This proposal sounds very promising and could be extended to other kinds of interface (such as streets, bridges). This would be a vector counterpart to a raster view where a city model is decomposed into a mesh to run a simulation algorithm.

As 3D generalisation is still in its infancy with algorithms for individual features, such an extension of CityGML with relations information would greatly to step further to complex processes such as the ones presented in this book for two dimensions features.

3.6 Case Study II: Relations for the Extraction of Groups of Objects

  • Stefan Steiniger 

  1. Geomatics Engineering, University of Calgary, Calgary, Canada

    Stefan Steiniger

This second Case study illustrates how spatial analysis can be used to model spatial relations. More specifically, we will model relations for the extraction of groups of objects. One Case study for this is the generalisation of naturally formed objects such as lakes and islands. Here, the preservation—or typification—of object groups during generalisation is important as patterns will often relate to the process by which they were formed (e.g. glacial processes). An example of the generalisation of a lake district, near Lyon in France, is for instance, given in Bertin (1983). Elements of the process he describes are: (1) the recognition of the overall shape of the lake group, (2) the identification of the individual lake shapes (since they may form a directional pattern), (3) the identification of a structural, visual skeleton within the group of lakes, and (4) the visual grouping of large lakes in the lake district.

An important part of Bertin’s generalisation process description is the identification of structures, i.e. groups of objects, which are formed only by looking at them, i.e. through visual perception and cognition. To detect these groups they need to be described. For a group of lakes or islands, such description can be achieved by formalising the relations between the objects of the group, for instance by formalising the relation between the islands within one group and between groups. If these relations are sufficiently formalised, then we can use this description to extract the island groups from a dataset.

In the following two subsections, we describe a particular form of object groups, so-called “similarity groups”. These groups emerge from perceptual similarities in shape and size of group individuals, (islands in our Case study). In the second subsection, we formulate relations for these types of groupings using the presented modelling approach.

3.6.1 Perceptual Grouping of Islands by Similarity

In the seminal work by Wertheimer (1938) on the “laws of organization in perceptual forms”, several principles are described under which single objects, e.g. points and lines, are perceived as a group. These principles describe for instance inter-object characteristics such as object proximity, object similarity, good continuation (e.g. a sequence of line segments), and the observers past experience.

Different authors have noted the importance of the similarity principle in cartography e.g. the work of Bertin (1983) or work on building group detection for map generalisation by Li et al. (2004). Steiniger et al. (2006) and Steiniger and Hay (2008) describe an experiment in which participants were asked to group islands, lakes, and triangles. In that experiment participants seem to have applied the principle of similarity to group islands. Three examples for similarity groups, taken from that experiment, are shown in Fig. 3.17. An analysis of such similarity groups (i.e. not only those three groups) reveals that the following conditions seem to hold: (1) the members of the group are close to each other (proximity principle), (2) the members of the group have a similar size, (3) they have a similar shape, and (4) for the two groups, SG2 and SG3, the orientation of the island shape seem to be similar [see also Williams and Wentz (2008)]. We now describe these similarity groups by using relations.

Fig. 3.17
figure 17

Marked with bold lines are groups of islands delineated by participants of an experiment described in Steiniger and Hay (2008). These three groups are likely to be grouped due to similarities in size, shape and orientation of the islands

Full size image

3.6.2 Similarity Relations Among Island Groups

We identified four member properties, or conditions, of similarity groups: proximity, size similarity, shape similarity, and orientation similarity. Each of these four properties should be modelled as relations. This will allow us to detect such groups for generalisation and monitor their changes during the generalisation process. In the modelling example we will use measures and thresholds that are “informed guesses” to illustrate our ideas, rather than using tested measures and values. Figure 3.18 shows how “similarity in size” can be modelled for the island example by adopting the schema of Fig. 3.6. We assume that a relation is modelled only between two geographic features, i.e. island i 1 and island i 2.

Fig. 3.18
figure 18

Modelling of the size similarity relation for similarity groups

Full size image

In Fig. 3.18, the relation “similarity in size” is described by:

  • the type of relation: isA binary relation,

  • the expression: true if 2/3 size(i 1) < size(i 2) < 4/3 size(i 1),

  • the members/spatial features: entity = Island, type != water, geometric primitive = polygon,

  • the operation for the assessment: polygon area—isA measure operation, isA area measure, isA Euclidian 2D area measure,

  • the properties: size-factor(i 2) = size(i 2)/size(i 1), lower limit = 2/3, and upper limit = 4/3.

As we don’t have sufficient space to describe the three remaining relations similar to the size similarity relation we have summarised this information in Table 3.1.

Table 3.1 Relations for micro groups formed by the similarity principle
Full size table

3.6.3 Open Modelling Challenges

There remain a number of open challenges that require further research. Three of these challenges are:

Challenge 1—In the applied modelling approach we have assumed that a relation is formed only between 2 geographic features. But a similarity group has at least 3 members. For the distance condition we need to describe at least two distances if three features exists, i.e. d 1,2 and d 1,3, assuming that d 2,3 may not be important to establish the existence of the group. While the modelling of only two distances avoids redundancies, this will does not allow us to monitor changes of d 2,3. So the third, seemingly unimportant, distance relation needs to be observed as well.

Challenge 2—When observing the two island groups that may be formed due to similarity principles in Fig. 3.17, we see that for the group SG 1 on the left side, the islands have a fairly compact shape. In this case, the orientation of the individuals is quite different, and there is no need to treat the similarity of orientations as a necessary relation. Thus the existence of an orientation similarity makes the classification and detection more reliable. Therefore, it would be good to have a general relation property that allows us to assign a weight or importance value to a relation.

Challenge 3—A broader issue remains: How do we connect the relations to each other and to a micro group object, which links to its individuals? One idea is to model the micro group object as a “similarity group relation”. This relation could be a binary relation where the expression requires all other relations—i.e., proximity, shape similarity, size similarity, number of members, and eventually orientation similarity—to be evaluated as true. In that case the operation type would be a “spatial analysis operation” that links to the 3 (or 4) mentioned relations. This remains an idea in further need of development.

3.7 Case Study III: Data Migration of User Data

  • Kusay Jaara 

  1. Laboratoire COGIT, IGN, Paris, France

    Kusay Jaara

With the wide availability of topographic data for the general public from National Mapping Agencies and from collaborative geographic data resources (e.g. OpenStreetMap), users are able to create their own thematic geographic data using public topographic data as a reference. At a future point, users could have more current versions of their reference data, or they may want to change the reference data to use more or less detailed data. In order to obtain consistent data after the replacement of reference data, user data has to be processed. We call this processing thematic data migration.

If the relations between the users’ thematic data and reference data are not taken into account during the thematic data migration, then errors can occur. For example, an accident (a user dataset) that took place in front of a bridge could be located behind the bridge after the migration process. For analysis purposes, such a change can be important. Moreover, users may want to emphasise some initial relations in order to make them visible. If we take the example of the accident near the bridge and the aim to obtain topographic data at a smaller scale, then the user may want to exaggerate, i.e. increase, the distance between the accident location and the bridge to clarify that the accident took place before the bridge and not on it.

A method of thematic data migration has been proposed in Jaara et al. (2013). It is an automatic process that takes into account geographic relations between a user’s thematic data and reference data during data migration. The next sections describe the main principles of this method.

3.7.1 General Workflow of Thematic Data Migration

Relations between thematic and topographic data are not explicit in the initial database, so they have to be extracted and represented (Jaara et al. 2012). As the representation of the real world changes from one database to another, it is not always possible to maintain all initial relations. For instance, a roundabout can be represented as a set of road segments forming a round pattern in the initial topographic database and as a simple crossroad in the final topographic database. Relations in this case have to be modified according to the differences in representation of the same object in the topographic database. Relations may change even if the reference object is not modified. For example, a disjoint relation between a thematic region and a reference region might be discarded if the final reference data is presented at a smaller scale and the distance is small. In Fig. 3.19, the data migration workflow of Jaara et al. (2013) is presented.

Fig. 3.19
figure 19

Proposed workflow for the thematic data migration

Full size image

According to the workflow, thematic data migration consists of:

  1. (a)

    Relation extraction and modelling: significant types of relations are identified depending on the application case. Then relevant instances of these relations are extracted from the initial data (e.g. accident a1 is on road r1 and accident a2 is close to junction j1). These relations are represented using a referencing model (Sect. 3.7.2).

  2. (b)

    Matching: initial and final topographic data are matched to detect the corresponding objects and changes on them (Chap. 5).

  3. (c)

    Relations modification: expected relations within the final dataset are inferred, and are also modified when needed. The modification is based on matching links between the initial and final topographic data (Sect. 3.7.3).

  4. (d)

    Thematic data relocalisation: the expected relations within the final dataset are used to control the spatial relocalisation process, i.e. the propagation of the reference data transformations on the thematic data. In some cases, we have to ignore one or more relations in order reach a solution (Sect. 3.7.4).

3.7.2 Referencing Model Between Thematic and Topographic Objects

The extracted relations have to be modelled in order to be stored and used in the subsequent stages. A model for relations between thematic and topographic data is presented in Jaara et al. (2012). In this model (Fig. 3.20), topographic objects are considered as ‘support objects’. A relation connects one support object and one thematic object. Another type of support object are characteristic objects, which help to obtain a better description of the thematic data, such as roundabouts and road-river intersections. Characteristic objects are not explicitly represented in the initial data. Hence, they have to be extracted in a data enrichment stage. Relations can then be established for topographic objects and for characteristic objects.

Fig. 3.20
figure 20

Class diagram of the referencing model of Jaara et al. (2012)

Full size image

The ontology of relations (Fig. 3.6) has been extended to include the thematic data referencing model—so that a spatial feature can either be characteristic, topographic or thematic. Every relation has two members: Member1 that is thematic and Member2 that is a support object. Figure 3.21 shows the resulting modifications.

Fig. 3.21
figure 21

Extension to the relations ontology of Touya et al. (2012) that includes spatial relations between thematic and topographic data

Full size image

3.7.3 Modification of Relations

Before the modification of relations step (Fig. 3.19), initial and final dataset have to be matched, the matching links being used by the modification of relations process.

The objective of this step is to modify the relations, if required, in order to reflect modifications in the topographic data (Jaara et al. 2013). Transition rules have to be defined at the beginning of the process. These rules define acceptable changes, necessary changes, and conditions of every transformation of relations. For example, a “near parallelism” relation, which is a fuzzy relation (Fig. 3.4), becomes a “parallelism” relation when the difference of scale between the original and the target scale exceeds a given (orientation angle) threshold. Rules can be used in order to make certain relations particularly visible (exaggeration). A transition rule for an “almost disjoint” relation between two regions can be defined in order to keep a visible distance between both regions in case a smaller scale map of the final topographic database is intended. The output of this processing stage is the expected relations between the final and initial topographic datasets.

3.7.4 Relocalisation Process

After identifying the expected relations in the final dataset (either preserving the initial or transforming them), the objective will be to find the position for the thematic object where these relations are best preserved or transformed. For this reason, we introduced the relation satisfaction measure. For a given position of thematic data, it measures how well the relation in the final reference data is preserved (or transformed). In the framework of the ontology of spatial relations (Fig. 3.6) proposed by Touya et al. (2012), the satisfaction measure is an operation that assesses the achievement (i.e. existence) of the spatial relation. The calculation of the satisfaction measure depends on the relation type and attributes. For quantitative relations, the satisfaction is equivalent to the difference of values before and after the migration (e.g. distances). For qualitative relations, neighbourhood graphs (Egenhofer and Franzosa 1991) could be used to extract the satisfaction, by measuring the distance between the expected relation and the actual relation, i.e. by evaluating the satisfaction.

The relocalisation can be treated as an optimisation problem: solutions are based on a local search near the initial position, where possible places for an object are calculated by adding regularly spaced vertices on the line that carries the object (the object can be moved to one of the vertices). Every possible place has a number of satisfaction values, one value for every expected relation. In some cases, certain relations have to be ignored in order to obtain a better result. In the accident example, in which the accident occurs next to the bridge and, additionally, in front of a building. If the building has a different position in the final topographic database, we may prefer to ignore the relation with the building and leave the accident next to the bridge. It is more important to have an acceptable solution than to end up with a bad compromise. To solve the multi-criteria problem the PROMETHEE II approach (Brans and Mareschal 2005) has been used, because of its suitability and because it can be easily parameterised. It allows us to ignore some relations in instances of bad compromise. Solutions are scored and the one with the best scores are chosen.

3.7.5 Results

The model is illustrated using two examples. The first one illustrates the advantage of our thematic data migration method over using the simple curvilinear ratio method that could be the simple method one could use for data migration. With the curvilinear ratio, the thematic data is moved at a point that corresponds to the same curvilinear ratio on line length: for instance, if the thematic data is located at 50 m on the road curvilinear axis, with the road being 100 m long, then it is relocated at 45 m on the generalised road curvilinear axis that is 90 m long. The example shows how data migration is improved by the presented method (Fig. 3.22). The second example illustrates the usefulness of the chosen multicriteria system that favours some relations over others.

Fig. 3.22
figure 22

Results of thematic data migration. a Initial combination of accidents with initial topographic database. b Final combination using curvilinear ratio. c Final combination using our methods

Full size image

In the first example, two accidents located at different distances from a roundabout have to be migrated (Fig. 3.22); the final topographic database is a generalised version where the roundabout is changed into a crossroad.

The main relation that has to be preserved is the proximity relation to the roundabout. But as the roundabout is represented by a crossroad in the final database, the proximity relations to the roundabout is changed to a proximity relation to the crossroad. A transition rule is defined as follows: If an accident is close to a roundabout and if a roundabout is matched with a crossroad, then the accident has to be situated in the middle of the crossroad. The relocalisation is done based on the changed relations, which gives the result shown in Fig. 3.22.

In the second example (Fig. 3.23), an accident is situated next to the river-road intersection (proximity relation) and in front of a building (relative position relation). In the final topographic database, the road was generalised and the building has been displaced. If we try to keep both relations as much as possible by finding a compromise solution, the result will be a partial satisfaction of the two relations. The score of the best location while keeping the two relations is calculated. The cases when ignoring one of the two relations are also evaluated. The solution with the best evaluation is taken. Evaluations are based on relation importance, which is related to user needs or the nature of the thematic object.

Fig. 3.23
figure 23

a Initial data. b Migration with compromise between relations. c Migration using a multicriteria approach

Full size image

3.8 Conclusions

Although research on spatial relations modelling began many years ago, their use in automated environments such as map generalisation is quite recent and research challenges remain. A model for a spatial relations ontology is proposed in this chapter but it requires further development to be useful for automatic processes. For instance, all relations identified by cartographers as important in the generalisation process should be included in the ontology. Then, it could be made freely available to spread this shared model in the generalisation research community and make it a standard resource of generalisation processes as well as of user requirement definition systems (see Chap. 2).

Moreover, the handling of relations during generalisation needs to be improved, particularly in the context of on-demand mapping with thematic data mapped onto topographic data. The migration use case raises the question of when to take relations into account during the generalisation process: before the process as parameters? Or afterwards with conflation or propagation techniques? Also, the handling and the definition of so-called multi-representations relations (Sect. 3.3.3) requires further research. For instance, how do we handle the relation of a building alignment along a dead end street when moving the street is required by the city generalisation process? By and large, a better management, in the generalisation process, of the interactions between geographic objects and their relations is required to improve generalisation automation.