Publication: Cartography and Geographic Information Science
Publication Date: 01-JUL-07
Delivery: Immediate Online Access
Author: Steiniger, Stefan ; Weibel, Robert
Article Excerpt
Introduction
In the last decade, research in automated map generalization reached a point where automated methods were continuously introduced into map production lines. Reports on the successful and ongoing integration of automated map generalization procedures have been published, among others, for the production of topographic maps at the Institut Geographique National, Dance (Lecordix et al. 2005) and the Ordnance Survey of Great Britain (Revell et al. 2006). Most of the automated procedures used in operational production lines, however, are limited to rather isolated operations, or they are applied independently to individual map objects (e.g., shape simplification) or to objects of a single object class (e.g., typification of buildings).
While it is possible to achieve considerable productivity gains with such generalization operators (Lecordix et al. 2005), it is also clear that further progress can only be made if research delivers solid solutions for contextual generalization operators (i.e., operators taking into account their spatial context), as well as for the concurrent treatment of multiple object classes (i.e., operators considering the mutual relations among objects of more than one class). Although the development of contextual operators for individual object classes is on the way (e.g., Ware and Jones 1998; Bader et al. 2005), the development of methods that can deal with multiple object classes is still in its infancy. One of the rare examples is Gaffuri (2006) who reports on a first attempt to treat simultaneously different object classes. We argue that an agreement about the kinds of spatial and semantic relations that exist among objects in a map, as well as methods to formalize, detect, and represent such relations, will be essential prerequisites to the progress of research in this area.
A simple example of four lakes, shown in Figure 1, should help to illustrate the necessity of representing the structural knowledge embedded in contextual, inter-object relations. A legible map should meet several visual requirements, including that map objects should have a minimum size to be unambiguously perceived by the map reader. In our example we assume that three of the lakes would not meet this constraint for a particular target scale, and we have to decide how the problem can be solved. On the top right of Figure 1, two simple solutions are shown that ignore the contextual situation--deleting the three small lakes or enlarging them individually until they each reach the minimum size. These solutions both meet the basic perceptual requirement (of minimum size), but they do not necessarily represent a good cartographic solution from a structural point of view. A more adequate solution would be to maintain the typical structures or patterns that extend across map features and thus emphasize the specificities of the map. Such a solution can only be obtained by considering inter-object relations. Both solutions shown in the lower-right corner of Figure 1 better preserve the typical properties of the spatial arrangement, as well as the size and shape relations, among the objects involved.
[FIGURE 1 OMITTED]
In this article, we propose a typology of relations among map objects aimed to act as a foundation for future research on developing new methods for contextual generalization involving objects from multiple object classes. The typology should offer a basic set of elements to represent the structural knowledge necessary to characterize the types of relations occurring in both topographic and thematic maps, and inform the selection and parameterization of contextual generalization operators.
The idea outlined above, to characterize a map with relations and to store the characterization results to support subsequent decision processes, has been pursued by several other authors. In the map generalization community the idea is generally known today as "data enrichment" (Ruas and Plazanet 1996; Neun et al. 2004) and the sub-process of context analysis is known as "structure recognition" (Brassel and Weibel 1988) or "structure analysis" (Steiniger and Weibel 2005a). Even though data enrichment and associated processes have been around tot a while, to our knowledge, no author has as yet attempted to establish an inventory of possible map object relations. Until recently, the discussion of (spatial) context relations in map generalization has either remained on the general level (Mustiere and Moulin 2002) or it focused on the analysis of rather specific scenarios. Examples of the latter include the detection of groups of buildings and the modeling of relations between roads and buildings (Boffet 2001; Regnauld 2001; Duchene 2004).
The remainder of the paper is organized as follows. The next section introduces the necessary definitions as a foundation of the subsequent sections. The third, central section introduces the proposed typology of horizontal relations. It starts off with a short review of existing, related typologies in order to derive the structure of the proposed typology. Following that, the set of relations is presented, and existing work is discussed. In order to demonstrate the utility of our typology and show how complex relations can be formalized, we then offer an example on the grouping and generalization of islands. This is followed by a section discussing the various steps of the utilization of map object relations, including directions for future research. Finally we summarize the main insights of the paper. Note also that an extended version of the proposed typology has been presented in Steiniger and Weibel (2005b).
Defining Object Relations in Maps
Before we present our typology, it is necessary to define the underlying terminology. We start with definitions of the different types of relations that are particularly relevant in the context of map generalization and multiple representations. Then, we discuss the interactions between relations, constraints, and measures.
Horizontal, Vertical, and Update Relations
In mathematics, "relations" denote arbitrary associations of the elements of one set with the elements of other sets. Depending on the number of sets involved, the relations are termed unary (involving only elements of one set), binary (involving associations of elements of two sets) or n-ary (involving elements of multiple sets). While we embrace the mathematical notion of the term "relation," we are only interested in those relations that are relevant for map generalization. In map generalization, the notion of scale, resolution or level of detail (LOD) plays a crucial role, leading to the definition of the first two classes of relations, termed horizontal and vertical relations, respectively. Because map generalization is a process leading to modifications of the content of a map or map database, we further define update relations as a third relation class.
Horizontal Relations
These relations of map objects exist within a single scale, resolution, or level of detail, and they represent common structural properties--e.g., neighborhood relations and spatial patterns (Neun et al. 2004). For instance in a geological map, polygons of a particular rock type that are close to each other form a group, while polygons of another rock type that are also close to each other form another group (see Figure 2). The rock polygons now have a relationship to the groups, being part of the group or not, and the two groups of rocks have a relationship to each other as well (e.g., an exclusion relation, and a distance relation).
[FIGURE 2 OMITTED]
Vertical Relations
This class of relations links objects and groups among different map scales, resolutions, or levels of details. For instance, polygons of a particular soil type in a 1:25,000-scale geo-database are linked to the generalized soil polygons in a l:500,000-scale database (see Figure 2, right). Note that the cardinality of such relations may vary between nullary, unary, and n-ary. Thus, a soil polygon at 1:25,000 may not have a homologous object at 1:500,000; it may have exactly one correspondent; or several polygons at 1:25,000 may be aggregated to one polygon at 1:500,000.
Update Relations
This relation class is used to describe changes of map objects over time. According to Bobzien et al. (2006), the update relation has three states: insert, remove, and change. As an example of the application of this relation, one might think of a building that has been newly constructed (action: insert), extended (action: change), or knocked down (action: remove), with the last revision of the corresponding map or spatial database having been published.
The concepts of horizontal, vertical, and update relations are not new. For instance, horizontal relations--though not termed that way--have been extracted and utilized by Gaffuri and Trevisan (2004) for the generalization of buildings and settlements in the form of towns, districts, urban blocks, building groups, and building alignments. Vertical and update relations are a well known concept used in Multiple Representation Databases (MRDBs). The use of vertical relations (commonly termed "links" in MRDB literature) has been demonstrated, for instance, by Hampe and Sester (2004) for the display of topographic data on mobile devices. Update relations that describe propagated updates of data within a MRDB were initially described by Kilpelainen and Sarjakoski (1995).
A note should be made here on the naming of relation classes: We use the terms "horizontal relations" and "vertical relations" because we believe them to be intuitively (and linguistically) understood as terms that form a pail; yet are different. Obviously, these terms should not be understood in the geometrical sense; rather, as a stack of data layers (or maps) of different scales, where horizontal relations only affect a single layer (or resolution), while vertical relations extend across the entire stack of (resolution) layers. Other, equivalent terms have also been used, such as "intra-scale" and "intra-resolution" for "horizontal" and "inter-scale" and "inter-resolution" for "vertical" (Bobzien et al. 2006).
This paper intends to offer a more comprehensive and systematic discussion of horizontal relations in map generalization than available from previous research, which tended to focus on specific instances of horizontal relations, neglecting the more holistic view. Thus, the typology proposed below will focus exclusively on horizontal relations. As has been argued in the introductory section, we believe that a systematic analysis of the types of relations that exist among objects of a map (i.e., horizontal relations) will be instrumental to the further development of more complex, contextual generalization techniques. Vertical and update relations are not addressed further in this paper.
Relations, Constraints, and Measures
Together with the generalization algorithms, relations, constraints, and measures represent the fundamental parts of an automated generalization system. More specifically, the triplet relations-constraints-measures forms the basis for controlling the application of generalization algorithms, that is, the selection of appropriate generalization algorithms to remedy a given conflict situation, including suitable parameter settings. While it should be clear what (generalization) algorithms do, it seems to be useful to define measures and constraints and explain their interaction with relations.
Cartographic constraints are used to formalize spatial and human requirements that a map or a cartographic map feature needs to fulfill (Beard 1991; Weibel and Dutton 1998). Examples are the minimum size constraint of an object (e.g., a building) or part of an object (e.g., a building wall), or the maximum displacement constraint to preserve the positional accuracy of a map object. Certain constraints may be termed "hard constraints" (e.g., in generalization, a house must not change sides of the road along which it lies). Their evaluation will thus lead to a binary result (fulfilled / not fulfilled). Most constraints, however, will be "soft constraints," meaning that slight violations may be tolerated. A constraint can be described by a measure that appropriately captures the property expressed by the constraint (e.g., the area of a building as a measure of the size constraint). The degree of violation of a constraint can then be evaluated by calculating the value of the associated measure and comparing that value to a target value that should be met for an optimal map at the target scale. The deviation of the actual from the target value will then yield a normalized "severity" (05, conversely, satisfaction) score expressing the degree of constraint violation (Ruas 1999; Barrault et al. 2001).
While the interactions between constraints and measures have been studied by various authors (e.g., Ruas and Plazanet 1996; Ruas 1999; Harrie 1999; Bard 2004), we would like to extend this discussion by examining the roles and interactions in the triangle of constraints, measures, and relations, as shown schematically in Figure 3. We use the (simplified) example of a set of buildings that are aligned in a row, assuming that we would like to preserve this particular pattern in the generalization process.
[FIGURE 3 OMITTED]
The spatial arrangement of the buildings can be seen as a relation of the type "alignment," where every building is related to the group making up the alignment. Within the alignment, further relations can be found, such as distance relations (expressing the distance of the buildings from each other), angle relations (expressing the angular deviation from the alignment axis), size relations (expressing the area of the buildings compared to each other), shape relations (expressing the similarity of building shapes), and semantic relations (expressing the similarity of the building types). To describe and identify these relations, appropriate measures are required.
Identifying the complex relation "alignment," for example, requires measuring whether the buildings are not located too far from each other (distance relation), whether they are sufficiently collinear...
NOTE: All illustrations and photos have been removed from this article.
More articles from
Cartography and Geographic Information Science
Interpretation and generalization of 3D landscapes from LiDAR data, 01-JUL-07
Relations among map objects in cartographic generalization, 01-JUL-07
Testing the effects of thematic uncertainty on spatial decision-making, 01-JUL-07
Looking for additional articles?
Click here to search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Click here to search our complete database of Industry & Market reports by text, subject, publication name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.
Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information. |
