Road network selection for medium scales using an extended stroke-mesh combination algorithm.

Author:Benz, Stefan A.


The road network is an essential part of topographic maps and databases (Zhang 2004; Touya 2010), and its generalization is considered to be complex. Roads are connected to each other by road segments (i.e., topologically speaking, the edge between two nodes in the corresponding road network graph), forming a contiguous network. Deletion of road segments without consideration of the entire network will result in loss of connectivity (Chaudhry and Mackaness 2005).

The selection of road segments usually precedes, and is a prerequisite for, other generalization operators (Jiang and Harrie 2004). It aims to reduce the level of detail in the road network by choosing the relevant road segments but also maintaining the main characteristics and structure (Touya 2010), as well as the essential topological, geometrical and semantic properties (Mackaness 1995). In order to achieve this, a hierarchy of roads is necessary. However, this hierarchy is difficult to obtain because it depends on different aspects that are related and coupled, such as geometry, attributes, topology and the implicit geographical context. Furthermore, differences in the road network density distribution in urban and rural areas have to be considered, too (Touya 2010).

There exist several algorithms that perform the selection process automatically. Among these, the stroke-based approach (Thomson and Richardson 1999) and the mesh-based approach (Chen et al. 2009) have been reported to produce promising results. Recently, an algorithm has been introduced that combines both the stroke, and the mesh-based approach in an integrated concept (Li and Zhou 2012). However, this algorithm has not been tested for many test cases yet, and particularly not for large and heterogeneous regions typical of topographic map and database production at national mapping agencies (NMAs) and commercial cartography companies.

This paper derives from a research project (Benz 2013) that was pursued in collaboration with swisstopo, the NMA of Switzerland. The topographic map and database products of swisstopo are derived from the TLM3D (Topographic Landscape Model 3D) database, and swisstopo --like many other NMAs - are seeking to automate their production processes, including road network selection as one example. TLM3D is a highly detailed, dense and large-scale spatial database corresponding to the source scale range of 1:10,000, covering Switzerland and the Principality of Liechtenstein with a high spatial resolution in all three spatial dimensions.

The interest of this project was on the transition from a large-scale source database to a medium target scale of 1:50,000. TLM3D was used as an example source database, but we believe our results to be adaptable to other databases of other NMAs as well. An initial analysis was conducted of how well three different algorithms for road network selection (the stroke-based, mesh-based, and the combined stroke-mesh algorithm) perform for this scale transition. The selection process and the algorithms were implemented using the constraint-based generalization approach as proposed by several researchers (Beard 1991; Weibel and Dutton 1998; Harrie and Weibel 2007). First, constraints set forth by expert cartographers were taken into account. Second, the results were evaluated using the defined constraints. The aim set by swisstopo is to select 70% of the features from the source database for the target scale.

A first round of experiments, documented in detail in (Benz 2013), showed that the integrated stroke-mesh algorithm by Li and Zhou (2012) clearly produces the best results of the road network selection algorithms published to date. As will be explained in the "State of the art" section, this algorithm represents a combination of two important streams of algorithms, the stroke-based and the mesh-based principle, in an attempt to capitalize on their respective strengths. Thus, invariably, results generated are superior to those obtained from either the stroke- or mesh-based algorithms alone, as documented by Li and Zhou (2012) for real test cases of considerable size. Medium scales, such as the target scale of 1:50,000, are still rather detailed and thus road network selection should handle the details of the network carefully, which turns out to be a particular strength of the stroke-mesh algorithm. Additionally, the algorithm can maintain the general connectivity of the network (i.e., no new dead-end roads arise where there are actually none), which was one of the main constraints defined by the swisstopo experts, and which is a general requirement in map generalization.

Despite these advantages, our preliminary experiments revealed that several difficulties remained, and not all of the cartographic requirements could be fulfilled. Therefore, an in-depth analysis was carried out as to how additional constraints and extensions could improve the results. These constraints and extensions form the focus of this paper.

The main contribution of this paper thus consists of five extensions that address deficiencies of the basic version of the integrated stroke-mesh algorithm by Li and Zhou (2012) and lead to a significant improvement of the results. Two of these extensions apply directly to the inner workings of the basic stroke-mesh algorithm. A third extension provides an approach to ensure that roundabouts are selected or omitted correctly (i.e., selected or omitted as complete objects). Additionally, two extensions are introduced that allow incorporating external feature classes. External feature classes are seldom used in the automated selection process of road networks. However, such external classes contain additional information that can guide and improve the selection. The first class used contains a set of POIs (points of interests) and the second class consists of a set of polygons that define settlement areas. The POIs are used to ensure the accessibility to important infrastructure objects in the selected road network whereas the settlement areas are used to guarantee that a cartographically adequate road network density distribution can be maintained in the result. For situations where a settlement feature class is not available, we also show how proxies of settlement areas can be generated from the road network.

The results of the extended stroke-mesh combination algorithm have been thoroughly evaluated in four large test areas of largely differing and heterogeneous road network character, both by quantitative analysis and by a detailed assessment by swisstopo experts. The experts' evaluation was highly positive, leading to the conclusion that the proposed approach is ready to be deployed in production at swisstopo.

In the "State of the art" section, we will discuss the state of the art that also provides a short overview of the stroke-mesh combination algorithm. The "Extensions of the integrated approach" section then introduces our extensions to the basic stroke-mesh combination algorithm, one by one. The "Evaluation by swisstopo experts" section presents the evaluation of the final results by swisstopo experts. The paper ends with "Conclusions" and an outlook on future research.

State of the art

Related work

Liu, Zhan, and Ai (2010) subdivide automatic road network selection into three groups: semantics-based selection, graph-based selection, and stroke-based selection.

Semantics-based selection makes use of attributes (e.g., road class). Roads are ordered according to their relative importance of attributes and the selection is based on this order. Owing to their simplicity, they are often used in practice. However, they are clearly insufficient due to the neglect of geometrical and topological constraints.

The graph-based methods treat road networks as connected graphs and use pattern detection algorithms (Yang, Luan, and Li 2011) or concepts such as shortest/ best path or minimum-spanning-trees, which serve as the basis for the selection (Mackaness and Beard 1993; Mackaness 1995). A special group of algorithms uses the dual graph approach at the topological level, where nodes represent roads and edges represent intersections of roads, respectively (Porta, Crucitti, and Latora 2006).

Dual graphs are often used to compute centrality measures, such as degree, closeness, or betweenness as a measure of importance for roads, which then serve as the basis for the actual selection task (Jiang and Claramunt 2004). With their focus on graph-theoretic principles that involve the entire road network, such as centrality measures, graph-based algorithms tend to favor the main connectivity structures of the network, making them particularly suitable for selection at smaller scales, as shown by a related study (Weiss 2013).

Stroke-based selection is based on the principle of "good continuation" and takes into account functional importance and perceptual significance. A stroke is a chain of road segments with continuous curvature, that is, with "good continuation" (Thomson and Richardson 1999; Thomson and Brooks 2000). Strokes can be used for pattern detection (Heinzle, Anders, and Sester 2005; Thom 2005; Yang, Luan, and Li 2011), for topological analysis (Touya 2010) or for the hierarchical modeling of roads (Tomko, Winter, and Claramunt 2008; Jiang 2009). Most often, however, strokes are used for the selection of road networks (Thomson and Richardson 1999; Edwardes and Mackaness 2000; Thomson and Brooks 2000; Chaudhry and Mackaness 2005; Heinzle, Anders, and Sester 2005; Liu, Zhan, and Ai 2010; Yang, Luan, and Li 2011; Li and Zhou 2012). The strokes are ordered according to some predefined rules (e.g., length or attributes of strokes), and the selection is conducted selecting strokes in descending order. The general idea is that long strokes with attributes of higher order form roads with a high functional importance that should be selected for the smaller target scale, whereas short strokes with...

To continue reading