skip to main content

Title: Comparing Directed and Weighted Road Maps
With the increasing availability of GPS trajectory data, map construction algorithms have been developed that automatically construct road maps from this data. In order to assess the quality of such (constructed) road maps, the need for meaningful road map comparison algorithms becomes increasingly important. Indeed, different approaches for map comparison have been recently proposed; however, most of these approaches assume that the road maps are modeled as undirected embedded planar graphs. In this paper, we study map comparison algorithms for more realistic models of road maps: directed roads as well as weighted roads. In particular, we address two main questions: how close are the graphs to each other, and how close is the information presented by the graphs (i.e., traffic times, trajectories, and road type)? We propose new road network comparisons and give illustrative examples. Furthermore, our approaches do not only apply to road maps but can be used to compare other kinds of graphs as well.  more » « less
Award ID(s):
Author(s) / Creator(s):
; ; ; ; ; ; ; ;
Date Published:
Journal Name:
Association for Women in Mathematics series
Page Range / eLocation ID:
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We propose a new approach for constructing the underlying map from trajectory data. Our algorithm is based on the idea that road segments can be identified as stable subtrajectory clusters in the data. For this, we consider how subtrajectory clusters evolve for varying distance values, and choose stable values for these. In doing so we avoid a global proximity parameter. Within trajectory clusters, we choose representatives, which are combined to form the map. We experimentally evaluate our algorithm on vehicle and hiking tracking data. These experiments demonstrate that our approach can naturally separate roads that run close to each other and can deal with outliers in the data, two issues that are notoriously difficult in road network reconstruction. 
    more » « less
  2. Abstract

    Road network design, as an important part of landscape modeling, shows a great significance in automatic driving, video game development, and disaster simulation. To date, this task remains labor‐intensive, tedious and time‐consuming. Many improved techniques have been proposed during the last two decades. Nevertheless, most of the state‐of‐the‐art methods still encounter problems of intuitiveness, usefulness and/or interactivity. As a rapid deviation from the conventional road design, this paper advocates an improved road modeling framework for automatic and interactive road production driven by geographical maps (including elevation, water, vegetation maps). Our method integrates the capability of flexible image generation models with powerful transformer architecture to afford a vectorized road network. We firstly construct a dataset that includes road graphs, density map and their corresponding geographical maps. Secondly, we develop a density map generation network based on image translation model with an attention mechanism to predict a road density map. The usage of density map facilitates faster convergence and better performance, which also serves as the input for road graph generation. Thirdly, we employ the transformer architecture to evolve density maps to road graphs. Our comprehensive experimental results have verified the efficiency, robustness and applicability of our newly‐proposed framework for road design.

    more » « less
  3. Abstract

    Proximity to roads is one of the main determinants of deforestation in the Amazon basin. Determining the construction year of roads (CYR) is critical to improve the understanding of the drivers of road construction and to enable predictions of the expansion of the road network and its consequent impact on ecosystems. While recent artificial intelligence approaches have been successfully used for road extraction, they have typically relied on high spatial‐resolution imagery, precluding their adoption for the determination of CYR for older roads. In this article, we developed a new approach to automate the process of determining CYR that relies on the approximate position of the current road network and a time‐series of the proportion of exposed soil based on the multidecadal remote sensing imagery from the Landsat program. Starting with these inputs, our methodology relies on the Least Cost Path algorithm to co‐register the road network and on a Before‐After Control‐Impact design to circumvent the inherent image‐to‐image variability in the estimated amount of exposed soil. We demonstrate this approach for a 357 000 km2area around the Transamazon highway (BR‐230) in the Brazilian Amazon, encompassing 36 240 road segments. The reliability of this approach is assessed by comparing the estimated CYR using our approach to the observed CYR based on a time‐series of Landsat images. This exercise reveals a close correspondence between the estimated and observed CYR (). Finally, we show how these data can be used to assess the effectiveness of protected areas (PAs) in reducing the yearly rate of road construction and thus their vulnerability to future degradation. In particular, we find that integral protection PAs in this region were generally more effective in reducing the expansion of the road network when compared to sustainable use PAs.

    more » « less
  4. The development of the transport network affects the socio-economic development of the territory and it is one of the most important factors in the growth of the level and quality of the population life. There is the need for a study of transport accessibility. In our work, we presented the mapping and assessment of changes in transport accessibility after the construction of service road. After the construction of the ESPO pipeline, a service road was built along it to maintenance the pipeline, which is located close to the district centers and crosses the local roads. This new road connected them into one network with year-round traffic. The object of our research is the Area of Oil and Gas Extraction in the Republic of Sakha (Yakutia) and the North Irkutsk region.We have created transport accessibility maps with and without all service roads, separately for winter and summer seasons. We have created maps for several district centers. We calculated transport accessibility using the method of constructing isochrones — lines of equal travel time to overcome the space relative to given points, using open GIS GRASS GIS. After construction, the company owner of this road gives permission to the municipal and federal services and local population use for free, but a preliminary application is required. There is a payment requirement and compliance with restrictions for transportation of commercial goods. After the construction of the ESPO pipeline, people who live close to the pipeline can reach to the district centers and neighboring districts by car year-round theoretically. The materials of this study can be useful in calculating the travel time on these roads, and finding priority areas for the construction of new roads. 
    more » « less
  5. Comparing two road maps is a basic operation that arises in a variety of situations. A map comparison method that is commonly used, mainly in the context of comparing reconstructed maps to ground truth maps, is based ongraph sampling. The essential idea is to first compute a set of point samples on each map, and then to match pairs of samples—one from each map—in a one-to-one fashion. For deciding whether two samples can be matched, different criteria, e.g., based on distance or orientation, can be used. The total number of matched pairs gives a measure of how similar the maps are.

    Since the work of Biagioni and Eriksson [11, 12], graph sampling methods have become widely used. However, there are different ways to implement each of the steps, which can lead to significant differences in the results. This means that conclusions drawn from different studies that seemingly use the same comparison method, cannot necessarily be compared.

    In this work we present a unified approach to graph sampling for map comparison. We present the method in full generality, discussing the main decisions involved in its implementation. In particular, we point out the importance of the sampling method (GEO vs. TOPO) and that of the matching definition, discussing the main options used, and proposing alternatives for both key steps. We experimentally evaluate the different sampling and matching options considered on map datasets and reconstructed maps. Furthermore, we provide a code base and an interactive visualization tool to set a standard for future evaluations in the field of map construction and map comparison.

    more » « less