Preprocessing of roads in OpenStreetMap based geographic data on a property graph

Abstract

Abstract. This paper presents a method for generating property graphs from OpenStreetMap data as a precursor to track generating methods for cycling sports. The results indicate that OpenStreetMap geographical data can be represented on a property graph. This is beneficial, and needed for use of computational intelligence path generation algorithms. The paper is concluded by presenting a sample property graph representing roads and intersections as nodes and relationships based on OpenStreetMap geographical and EU-DEM elevation data.

Headnote

Abstract. This paper presents a method for generating property graphs from OpenStreetMap data as a precursor to track generating methods for cycling sports. The results indicate that OpenStreetMap geographical data can be represented on a property graph. This is beneficial, and needed for use of computational intelligence path generation algorithms. The paper is concluded by presenting a sample property graph representing roads and intersections as nodes and relationships based on OpenStreetMap geographical and EU-DEM elevation data.

Keywords. cycling, directed graph, OpenStreetMap, property graph, smart sport training

(ProQuest: ... denotes formulae omitted.)

11ntroduction

Cycling is an activity popular worldwide Rauter (2014). It offers numerous health benefits such as better cardiovascular fitness, significant risk reduction for all-causes and cancer mortality, reduction of obesity risk (Oja et al., 2011). In the European Union 8% (over 35 million people) of people use bicycles as their primary daily means of transport (Directorate-General for Mobility and Transport (European Commission), 2015).

Cycling is not just a means of transport but also a popular sport. Races such as the Tour de France, Giro d'Italia and Vuelta de España are known globally (Hansen, 2019). To have a chance to even perform at such elite events, or even get a chance to win, an athlete must prepare and train. A special circumstance of cycling is that most of the training can be done outdoors and in real environment conditions. Cycling training may represent a training where the cyclist simply rides a predetermined track to the best of his abilities. This means that the training track is a road in real world environments.

According to (Fister et al., 2019) sports training, including cycling, can be broken down into 4 phases: Planning, realization, control and evaluation.

Sports training is changing rapidly, aided by the rapid development of Information Technologies. Approaches which utilize the use of wearables, sensors, and Internet of Things (IoT) devices, and-or intelligent data analysis methods and tools to improve training performance and/or reduce workload while maintaining the same or better training performance, are classified as Smart Sport Training (SST) (Rajšp & Fister, 2020).

Multiple applications, such as Apple Fitness+ (Apple, 2021), Google Fit (Google LLC, 2021), Cycling Bike Tracker (Zeopoxa, 2021), Strava Strava Inc. (2021), Map My Ride (Map My Ride, 2021), which record training data in cycling already exist. They allow the use of wearables and smartphones to record speed, heart-rate, distance and other training data, and this aids the training phases of record, control and evaluation. But what none of the existing tools offer is track generation, that would allow the cyclist to choose the route which would offer him the optimum distance, altitude meters and track conditions for his planned training. The cyclist has to rely on his own intuition to plan an actual training session. In this paper we tackle this problem by developing a novel approach to track generation in a form of directed property graphs.

The contributions of this paper are:

* Proposal for combining OpenStreetMap (Openstreetmap Foundation, 2021) geographic data with EU-DEM (European Environment Agency, 2017) an European elevation data-set.

* A novel method for generation of a property graph from geographical data as a preprocessing step in future cycling track generating methods.

In a nutshell, this paper presents a method for generation, analysis and representation of cycling tracks as a group of nodes (road intersections) and connections (roads) between them, while analyzing the elevation, distances and track types of roads to enable generation of training tracks.

The paper is structured as follows, Section 2 presents the data sources used and the proposed method for generation of graphs from OpenStreetMap, Section 3 presents the generated property graph and a sample usage of it in Section 4 conclusions are presented and ideas for future research are conceptualized.

2Materials and methods

The purpose of this section is to present the data sources that were applied in the research, and to present the proposed method for generation of graphs from OpenStreetMaps.

2.1Outline of data

The data used for generation of the property graph came from OpenStreetMap (Openstreetmap Foundation, 2021) for defining and detecting the intersections and roads between them and, EU-DEM (European Environment Agency, 2017) for determining the elevation difference among those nodes and the roads connecting them.

OpenStreetMap is a free, editable map of the world that is edited by volunteers and released with an open-content license (Openstreetmap Foundation, 2021). The map is generated from XML files. The map consists of the following element types:

* Nodes - the specific points on the earth's surface. Each node has her own id, latitude and longitude. They can be used to define standalone point features (e.g. postboxes, water wells, bus stops) or combined to form ways.

* Ways - are an ordered list between 2 to 2000 nodes defining a polygon line, they represent linear features (rivers, roads) and areas (e.g. borders, buildings).

* Relations - data structure that documents a relationship between two or more data elements (nodes, ways, and/or other relations). They are also needed when a feature needs more than 2000 nodes to display it.

* Tags - key value pairs that can be used to describe nodes, ways and relations further.

An example of a way (orange color) with it's nodes (green color) is presented in Fig. 1. In this case it represents a residential road.

The Overpass Application Programming Interface (OpenStreetMap Foundation, 2021) was self hosted, to retrieve these types of data. Overpass API is a read-only API that serves up queried parts of OpenStreetMap map data. It uses the Overpass Query Language for queries.

EU-DEM (European Environment Agency (2017)) is a digital surface model of European Economic Area member countries. It has a 25 metre resolution and it has an accuracy of 7 metres ± root mean square error. The data were used, together with the self hosted Open Elevation API (Ricardo Lourenço (2021)), which is a read only API for serving elevation at queried latitudes and longitudes.

2.2 Proposed method for generation of property graphs from geographical data

Our goal was to combine the OpenStreetMap and EU-DEM data, and transform it into a suitable graph model. To shorten the processing time the data were limited to the borders of Slovenia, but the same experiment can simply be extended in such a way to include the whole of Europe. The process was broken down into the following phases: (1) Identification of key attributes of an intersection and a road, (2) Identification and transformation of road intersections into graph nodes, (3) Identification of roads between intersections (4) Transformation of identified roads into bidirectional graph relationships.

In-memory graph database was used for modelling the graph, RedisGraph (Redis Labs Ltd., 2021). Graph databases are databases used for representing relationships between entities (Vaish, 2013); there can be multiple links between two nodes in a graph, representing multiple relationships that the two nodes share.

A graph model was used in our solution to represent individual intersections as nodes (N1, N2,...) and relationships (R(N1N2) representing roads between them, and a sketch of an intersection-road graph can be seen in Fig. 2. The proposed relationships are bidirectional, because riding from intersection N1 to N2 is not the same as conducting a journey in the opposite direction, due to the elevation differences between the two intersections.

Using graphs can simplify complex map data, and allows us to choose the needed data to represent nodes, relationships and their attributes.

2.3 Graph model attributes

The inspected attributes relate to the data included for each node (intersection) and edge (path). As such, what was included in each node/intersection was its OpenStreetMap id, their latitude and longitude and way ids it belongs to, as seen in Table 1. The last part is not necessary, but it was saved in the graph to simplify the search for connections.

For relationships (roads) this was the total ascent, descent and distance in meters between two connected nodes, as well as the types, since a road type can change, or the road linking them (e.g. track, residential road, primary road, secondary road, tertiary road) as seen in Table 2.

The established relationships are bidirectional. Although the distance from intersection A to B is the same as the distance from B to A, the elevation difference means that the cyclist must exert more effort to travel from a higher to a lower intersection than the other way around.

2.4Identification and transformation of road intersections

Multiple types of roads exist, so only the suitable intersections had to be identified. For example, a cyclist can't cycle on a motorway, but he can cycle on a regional road. The proposed identification was done in batches, where the whole map was broken down into equally sized boxes of 0.03 latitude and longitude. Intersections were also identified when there was no actual intersection, but a road type changed from one type to another, e.g. transition from a residential into a secondary regional road, since we classified them as two different roads.

The intersection detection was first used for analysis of cycling training interruptions in Rajšp & Fister (2021). A pseudo-code of the algorithm for identification of road intersections is shown in Algorithm 1.

We move slowly through the map and identify ways that conform to the determined conditions of road types (line 6). After all ways in a given square are identified, intersections are identified (line 7); intersections are simply nodes which share two or more of the identified ways. The intersections are then appended to the list of road intersections (i). Both queries are done using the Overpass Query Language. Each identified node is saved at the end into the RedisGraph database as a node of the graph.

2.5Identification of roads between intersections

Relationships with surrounding intersections had to be established for each of the intersections identified in the previous step. This means that we had to establish a two way relationship between linked intersections.

We classified two intersections (nodes) as bidirectionally connected when a road of a required type existed between them, but no intersection nodes were found between them. This was done to ensure that each intersection was only connected to the intersections by relationships similar to the connections the roads provide in the real world environment.

Each node was inspected for surrounding intersections, as shown on Fig. 3. The inspected node is marked by a red circle, and the ways it belongs to are shown in blue. For a node in a four way intersection (two ways intersecting) the search has to be conducted in both forward and backward directions for both of the ways the node belongs to.

As shown, only the nearest intersection nodes are identified as intersections (marked by the color green). Sometimes there is no intersection at the end of the way (upwards blue arrow), because a road may be made from multiple ways. In that case, the search simply continues at the end of the way through the next way until a suitable connection is found, as seen by Fig. 4.

Special care must be taken when connecting multiple paths, because the nodes in the ways may not point in the same direction, as seen on Fig. 5. The four cases lead to the following four outcomes:

* a.) the termination of path 2 becomes the termination of the combined path. Ascent and descent is summed.

* b.) the start of path 2 becomes the start of the combined path. Ascent and descent is summed.

* c.) the termination of path 2 becomes the start of the combined path. The total ascent is equal to the descent in path 2 and ascent in path 1, the total descent is equal to the descent in path 1 and ascent in path 2.

* d.) the start of path 2 becomes the termination of the combined path. The total ascent is equal to the descent in path 2 and ascent in path 1, the total descent is equal to the descent in path 1 and ascent in path 2.

Sometimes no intersections are found even after continuing the search, because the road simply terminates in one way (e.g. the way continues into a blind alley). In that case, no connection is established. The search is also terminated if the road changes into a type that is not permitted for a cyclist to ride on (e.g. transition into a motorway).

For each of the identified connections all the nodes between them are saved, so that they can be used for generating graph relationships in the next step of processing.

2.6Generation of bidirectional graph relationships

After all the surrounding connected intersections nodes of an intersection node are found the analysis of data can continue. Before generating the relationships we need to measure the distance, total ascent and descent between each of the nodes on the list, and sum them up. To measure the distance (d) the Haversine formula is used, as seen in eq. 1,2. Where in eq. 1, ф represents the latitude and A represents longitude (both in radians). The distance is then calculated in eq. 2, where R represents the mean earths radius, which has the value of 6371,23 (value from (Chambat & Valette, 2001)).

... (1)

... (2)

The distance calculated by the aforementioned equations does not take into account the difference in elevations. To measure the elevation EU-DEM ((European Environment Agency, 2017)) elevation data are consumed using Open Elevation API (Ricardo Lourenço, 2021).

For further calculation of distance (d·) between the two consecutive nodes the Euclidean distance formula is used, as seen in eq. 3, where d represents the previously calculated distance, ei the elevation of the first node and e2 the elevation of the second node.

... (3)

The procedure for establishing a bidirectional relationship including the calculations of distances described in eq. 1, 2 and 3 is shown in the Algorithm 2.

TThe algorithm receives a list of nodes (nodes0...nodesn) because two intersections are not usually connected by a straight path. The while loop (line 4) goes through each of the succeeding nodes.

The procedure calculates the total ascent and descent between the two nodes, where the elevations are firstly retrieved from Open Elevation API (lines 5 and 6) and then added to the total ascent (lines 10 and 11) if the elevation of the succeeding node is higher than the previous one, and to the total descent (lines 14 and 15) if it isn't.

When we have the ascent / descent values we can calculate the actual distance between the nodes (lines 7 and 8). This distance is then added to the total distance (line 9) between the intersections.

Once all the values are calculated the relationships are generated (lines 17-22). The total ascent between intersections ii- > i2 represents the total descent between intersections i2 - > ii, and the total descent between ii - > i2 represents the total ascent between intersections i2- > ii.

Before each of the relations are stored, the graph is checked if the connection already exist, since a node could already have been checked.

3Presentation of a graph model

The generated graph stored all of the viable intersections and paths between them for roads (suitable for cycling) in Slovenia. A smaller part of the graph model will be presented since the graph contains almost 200 thousand intersections. Querying the box of (latitude: 46.1338 - 46.1649, longitude:15.0215 - 15.0732) which corresponds roughly to the town of Trbovlje (Slovenia) returns the graph seen on Fig. 6.

It contains 389 different intersections, with 808 existing connections between the intersections.

A sample 4 node two-way pathway is presented on a graph in Fig. 7, and on an actual OpenStreetMap visualization on 8. The intersections correspond to the following OpenStreetMap node identificators: (1) 494036708, (2) 3304812495, (3) 3304812528, (4) 494036664. Manually inspecting the paths shows that travelling from nodes (1) -> (4) returns an ascent of 18 meters and descent of 6 meters, and the trip from (1) -> (4) takes 318.94 meters.

The generated graph model can be used on computational intelligence algorithms to find the optimum routes, given the requested parameters of distance, total ascent, total descent.

The generation of cycling training tracks was already attempted and presented in (Fister Jr et al., 2020). The difference between our graph and the mentioned approach is that our approach generates graphs from raw OpenStreetMap data, while the mentioned approach generates them from past training data. The key possibilities of using the developed graph for generation of training are:

* Possibility of fine tuning the training track distance, ascent and descent allowing better trainings for the cyclist.

* Discovering new training routes not known to the trainee

* Creating circular training routes where the trainee does not visit the same location twice

* Creating comparable (distance, ascent, descent) training routes even if they are done in different locations.

The proposed graph approach could also be adapted to generation of running tracks, where the only change would be the different input criteria for identification of viable paths.

4Conclusion

A lot of routines already exist for various sports; in fitness you can follow a specific training regime with an exact number and types of exercises to perform, and the same is true for a lot of sports. Cycling, however, is a different sport, where the training can and should be done in the outdoor environment.

In this paper, a novel method for pre-processing of OpenStreetMap and EU-DEM elevation data was used to create a bi-directed property graph to represent maps as a series of intersections and the paths between them. The method has been tested and applied on the map of Slovenia to demonstrate and prove it's applicability. The method proposed in this paper is the necessary pre-processing step in the development of methods for cycling training tracks4 generation.

In the future we will use the developed approach, together with Computational Intelligence methods, to develop an algorithm for cycling training track generation, where the cyclist will choose the exact distance, type and ascent of the generated track. This will be beneficial, because it will allow the cyclist to optimize his training, and travel through previously unknown tracks, breaking down the monotony of training. We also plan on publishing the generated data-set so it can be verified and used by other researchers. The algorithm will be updated in the future, to measure not only the distance and ascent/descent, but also the inclination of the ascents. The approach can also be expanded to running track generation by changing the input parameters of suitable intersections and paths in the graph.

Acknowledgments

This research was funded by the Javna Agencija za Raziskovalno Dejavnost RS (Research Core Funding No. P2-0057).

References

References

Apple, I. (2021). Apple Fitness+ - Apple. Retrieved 2021-05-15, from https://www.apple .com/apple-fitness-plus/

Chambat, F., & Valette, B. (2001, aug). Mean radius, mass, and inertia for reference Earth models. Physics of the Earth and Planetary Interiors, 124(34), 237-253. doi: 10.1016/S0031-9201(01)00200 -X

Directorate-General for Mobility and Transport (European Commission). (2015, may). Quality of transport - Publications Office of the EU (Tech. Rep.). Brussels, Belgium. Retrieved from https://op.europa.eu/en/ publication-detail/-/publication/ 7ee1f35f-aecc-43a5-a718-bbfe053499be/ language-en

European Environment Agency. (2017, dec). EU-DEM 1.1. Retrieved 2021-0515, from https://www.eea.europa.eu/ data-and-maps/data/copernicus-land -monitoring-service-eu-dem

Fister, I., Fister, I., & Fister, D. (2019). Computational Intelligence in Sports. Cham: Springer International Publishing. Retrieved from http://link .springer.com/10.1007/978-3-030-03490-0 doi: 10.1007/978-3-030-03490-0

Fister Jr, I., Fister, D., & Fister, I. (2020). Topologybased generation of sport training sessions. Journal ofAmbient Intelligence and Humanized Computing, 1-12.

GoogleLLC. (2021). Google Fit: Health and Activity Tracking - Apps on Google Play. Retrieved 202105-15, from https://play.google.com/store/ apps/details?id=com.google.android.apps .fitness

Hansen, S. (2019, sep). The Most Famous Race For Cyclist? Retrieved 2021-05-15, from https://bestsportslounge.com/famous -cycling-race

Map My Ride, I. (2021). Map My Ride GPS Cycling Riding - Apps on Google Play. Retrieved 202105-15, from https://play.google.com/store/ apps/details?id=com.mapmyride.android2

Oja, P., Titze, S., Bauman, A., de Geus, B., Krenn, P., Reger-Nash, B., & Kohlberger, T. (2011, aug). Health benefits of cycling: a systematic review. Scandinavian Journal of Medicine & Science in Sports, 21(4), 496-509. Retrieved from http://doi.wiley.com/10.1111/j.1600 -0838.2011.01299.x doi: 10.1111/j.1600-0838 .2011.01299.x

Openstreetmap Foundation. (2021). OpenStreetMap. Retrieved 2021-05-15, from https:// www.openstreetmap.org/

OpenStreetMap Foundation. (2021). Overpass API. Retrieved 2021-05-15, from https://wiki .openstreetmap.org/wiki/Overpass\_API

Rajšp, A., & Fister, I. (2020, apr). A Systematic Literature Review of Intelligent Data Analysis Methods for Smart Sport Training. Applied Sciences, 10(9), 3013. Retrieved from https:// www.mdpi.com/2076-3417/10/9/3013 doi: 10 .3390/app10093013

Rajšp, A., & Fister, I. J. (2021). Discovering the influence of interruptions in cycling training: A data science study. In International conference on computational science (accepted for publication).

Rauter, S. (2014). Mass sports events as a way of life (differences between the participants in a cycling and a running event). Kinesiologia Slovenica, 20(1).

Redis Labs Ltd. (2021). RedisGraph - a graph database module for Redis. Retrieved 202105-15, from https://oss.redislabs.com/ redisgraph/

Ricardo Lourenço, J. (2021). Open-Elevation API. Retrieved 2021-05-15, from https://open -elevation.com/

Strava Inc. (2021). Strava: Track Running, Cycling & Swimming - Apps on Google Play. Retrieved 202105-15, from https://play.google.com/store/ apps/details?id=com.strava

Vaish, G. (2013). Graph store. Birmingham: Packt Publishing.

Zeopoxa. (2021). Cycling - Bike Tracker - Apps on Google Play. Retrieved 2021-05-15, from https://play.google.com/store/apps/ details?id=com.zeopoxa.fitness.cycling .bike