Routing is a common task when using digital maps, but most engines offer only travel routes for automobiles. However, a more interesting aspect in this topic arises when being a cyclist. For this target audience especially elevation information is relevant. Such data is available from different sources, but is not perfectly usable for cycling routing. Those digital elevation models may include voids and outliers that falsify the elevation profile. Thus, a pre-processing step is necessary before using them. Therefore noise reduction steps and the Mean and Kalman filters are applied and evaluated in this work. They successfully eliminate erroneous and noisy information and smooth the elevation profiles. This enables a elevation aware routing engine to find and calculate more suitable paths for a cyclist, thereby allowing a more accurate route planning.
F.2.0 [ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY]: General; H.0 [Information Systems]: General; H.2.8 [DATABASE MANAGEMENT]: Database Applications—Spatial databases and GIS
A common use-case in today’s society is traveling and
exploring new locations. To fulfill this tasks easily, many online
services exist that propose best paths to the desired
destination. For motorists these suggestions deliver mostly very
accurate travel time estimations. In contrast, a cyclist never
could rely on the outcome of today’s standard online routers
as they ignore some essential factors. One of these is
elevation information. While cars mostly have enough power to
drive close to the speed limit regardless of the slope of the
street, cyclists come to their limits when going uphill. Many
of the currently available online routers do not consider the
altitude profile at all and thus suggest non-realistic values.
For example, for a 10 km long path with average incline
slope of 8 % a standard online router estimates a travel time of
approximately 30 minutes. Taking the elevation information
into account, GraphHopper [
The data used for elevation aware routing is available via digital elevation models. For usage within the final routing engine, the datasets should be prepared first. This preparation task includes a previous analysis of the elevation data and will be presented in Section 3. Different versions of the digital elevation model will be investigated to find the best one that meets the required properties. After the evaluation of the datasets a possible improvement of those is examined in Section 4. Presumably, the models need to be cleaned for proper usage as they may include noisy altitude values, possibly causing unrealistic steep slopes. To get rid of these noises and outliers it is necessary to apply smoothing algorithms before the elevation profiles are projected on an edge of the routing graph. Hence, in this paper, the Mean and Kalman filters are applied to investigate the possible improvement of elevation profiles.
These processing steps allow to optimize the elevation
profiles for cycling purposes. However, additional information
about a track itself, like type of road or surface, can lead
to even better route calculations. For this and as a routing
engine needs maps and street information for path finding,
the OpenStreetMap (OSM) [
For routing many commercial and open source systems
exist. When it comes to route engines for bicycles, the list
of available systems is shortened drastically. Examples for
regional bicycle routers are Cyclopath (USA) [
In numerous of the open source products, also in the ones
listed above, OpenStreetMap is often deployed as a base map
for routing. Well-known routers explicitly using OSM data
are OSRM [
Digital elevation models are such an alternative source for
elevation information and thus form important datasets for
many different research areas. Regarding the quality of these
datasets, Rexer et al. [
In order to calculate the optimum path for a cyclist, many
aspects have to be taken into account. Next to criteria such
as way type, way surface, etc., elevation data becomes the
most significant one. The first elements can be retrieved from
OSM, presuming these tags are filled with values.
Elevation information is basically also available in OSM through a
tag that can be set on all types of OSM elements. However,
currently it is rarely used: only 2.6 million elements out of
possible 3.6 billion elements (of those only 1.3 billion are
tagged) include this tag. According to the taginfo website [
There exist many accurate digital elevation models with
very low error rates, but they are usually only available for
small areas, e.g. DEM data of South Tyrol. Other globally
available solutions like the dataset of the WorldDEM (TM)
of the Airbus defense and space organization have a high
accuracy, but are only available for a fee1. Open source projects
like GraphHopper and BRouter therefore use the data from
Shuttle Radar Topography Mission (SRTM) or the CGIAR
[
The Shuttle Radar Topography Mission (SRTM) mission was a joint operation between the NASA, the National Geospatial-Intelligence Agency (NGA) and the German and Italian Space Agencies. Approximately 80 % of the worlds land surface was scanned during the first flight in year 2000 and at least 94.59% twice from different angles. After processing the radar information, the organizations exposed the first near global-elevation dataset. This first version, however, is quite noisy and has missing data. The reasons for this can be heavy shadows and water reflections. So refinement work was initiated which reduced spikes and wells, leveled water and defined coastlines.
Originally the dataset SRTM1 contained one arc-sec (approx. 30 meters) times one arc-sec resolution data only for the US. For the rest of the world SRTM3 exists which has three arc-sec times three arc-sec (approx. 90 meters) resolution. The resolutions are indicated in the number extension of the SRTM name (1 and 3). However, the SRTM dataset still has many voids, making it not well usable for routing in any area. This issue is addressed in the third version of the SRTM dataset. The NGA filled the voids using interpolation algorithms and thus produced the SRTM version 3. Again, the resolution of this void filled dataset is currently globally available in three arc-seconds and called SRTM3 v3. Only for some regions, including the US, the 30 meters dataset is released, called SRTM1 v3, but will be available for more regions in the future.
But SRTM is not the only nearly globally available DEM and therefore the following section will introduce the CGIAR dataset. 1http://www.geo-airbusds.com/worlddem/, 29.07.2015
The Consultative Group for International Agriculture
Research CGIAR provides a void-filled dataset of the SRTM3
v2 for 90 meters resolution quality. The resolution stayed
the same as the SRTM3s one: three arc-sec times three
arcsec. However, CGIAR additionally used external resources
to fill the voids and also transformed the data into the
widely adapted filetype GeoTiff [
Although this DEM is already quite good, more detailed ones are available for specific regions. Thus, in the following paragraph, the South Tyrol DEM is presented. 3.3
In contrast to the datasets presented before, a regional
elevation model is more precise. Thanks to the government of
South Tyrol (Autonome Provinz Bozen – Amt fu¨r
u¨bero¨rtliche Raumordnung [
The data was gained with the help of laser scanners and covers the entire area of the province of South Tyrol. It has a resolution of 2.5 meters times 2.5 meters and an absolute vertical error of 40 cm below 2.000 MASL (Meters Above Sea Level) and 55 cm above 2.000 MASL. The high resolution and accuracy make this product suitable for the ground truth source.
Having discussed three DEMs, a short comparison should allow an overview of the quality of those datasets. The following section includes an evaluation of the models.
Regarding routing for a cyclist it is more interesting to evaluate how well the datasets perform when they are mapped to the street network. This section will show an evaluation based on the South Tyrol ground truth.
The absolute vertical error of post-processed SRTMs
(voidfilled SRTM1 v3 and SRTM3 v2.1) and CGIAR with respect
to the South Tyrol as ground truth DEM is observed. The
experiment calculates the corresponding RMSE (Root Mean
Squared Error) for each nearly globally available dataset.
RMSE is a commonly used to measure the accuracy of
values in different models. In geo-information systems, RMSE
is “a measure of the difference between location that are
known and locations that have been interpolated or
digitized“[
For the evaluation, seven different tracks were recorded with a GARMINTMOregon 550t GPS tracker during bicycle trips. The tracks cover different environments such as valley, plateau or mountain. Figure 1 is an example of a recorded track in an alpine plateau (“Ritsch-Kompatsch“). The y-axis shows the meters above sea level, the x-axis the distance cycled in meters. Here the visual comparison of the available DEMs to the recorded GPS track are of interest. Looking at the regional SouthTyrol DEM (dark grey line with points), it can be seen that its shape is quite similar to the one of the GPS recorded elevation (black line on bottom). The discrepancy of about 20 meters from the GPS record to the other profiles is due to the barometric altimeter in the device. Comparing the GPS record to the globally available DEMs, it can be clearly stated that SRTM1 v3 (blue line with rectangles) matches best with the GPS track. CGIAR (light grey line with triangles), however, performs worst for this specific track.
Table 1 strengthens the previously made observations. With the South Tyrol DEM being the ground truth, the SRTM1 v3 DEM outperforms the other two datasets on each track. The RMSE for each evaluated track is the lowest for SRTM1 v3. The differences in the RMSE for the ways in one direction and backwards are due to the different point records of the GPS device, thus influencing the whole calculation. As SRTM1 v3 delivers the best result, this elevation model is used to feed the routing graph with elevation information. Although the results are already very promising, Section 4.2 shows with which algorithms the quality of a tracks elevation profile can be further improved. The digital elevation models have already undergone several post-processing steps, but peaks and troughs are still present in the elevation profile. Therefore, in the remaining part of this section algorithms for DEM improvement are suggested that should smooth the profile. 4.1
The DEM models are stored as rasterized data where each geographic region can be found in a tile of the raster. If the system extracts the elevation value for a specific geographic point, it would normally consider only a single tile. Due to the noisy elevation models it might withdraw a wrong value, that messes up the elevation profile. A simple approach to solve this problem is to not only use the value from a single tile, but also from the enclosing neighbors. Thus, the first goal is to remove noise by considering surrounding tiles on elevation extraction and secondly, to smooth the elevation values once they have been mapped on the way.
GraphHopper has already an implementation of the mean method in place. The algorithm takes the four adjacent tiles and averages the five extracted values. This approach has been extended to support also the neighboring eight tiles and the possibility to define the behavior of the filter with a kernel. The kernel is used to set the weight on each element. This makes it simple to test different combinations.
The second approach was to use a median filter on the eight surrounding tiles and the center tile.
These simple noise reduction algorithms were not able to improve the elevation profile of a way, because the datasets are already averaged. Therefore, another approach will be evaluated, which smooths the elevation profile after the extraction from the original DEM. 4.2
Slope is one of the main criteria for cyclists when they
choose their route [
The arithmetic Mean filter is a well known method to smooth datasets. In signal theory it is also referenced as low pass filter, because it removes high frequencies.
In this particular context the filter is used on a list of points with elevation information. In its simplest form it takes the actual value at position t, adds the value at position t-1 and t+1 and divides by three. The problem of this approach is that it ignores the distance between two points. The frequency of points within a certain distance differs depending on the shape of the street. A straight line needs only few points to be defined, but a curvy street has plenty of points. If the algorithm considers only a fixed number of adjacent points, it might lookup only in the same tile or considers points that should have no influence anymore, because they are too far away. This problem can be solved by selecting only those points, which are within a certain radius. The final version of the implemented Mean filter takes a number that defines the radius in meters and averages over all reachable points.
Table 2 gives a detailed overview of the evaluated tracks where the Mean filter has been applied with 50, 100 and 200 as distance parameter. This parameter defines the smoothness of the curve: a higher distance value causes a higher cutoff rate. The last row in Table 2 includes the average RMSE and it can be seen that the mean filtered elevation profile with distance equal to 50 meters performs best. The difference to the original dataset although is only about a maximum of 30 cm, which is a small improvement.
The smoothing algorithm flattened altitude peaks and lows. This influences the calculation of the slope for each edge in the route. For example, the original dataset has at one point of the route a very steep incline: 10m / 40m * 100 % = 25 % incline. The Mean filter 50m reduced this value to 6m / 40m * 100 % = 15% incline.
The observations show that the Mean filter is a great tool to smooth the elevation profile of a track, but the improvement of only 30 cm in absolute vertical accuracy is only marginal. Another well known smoothing algorithm might perform even better and is already frequently used in GPS signal smoothing: the Kalman filter. 4.2.2
Knowing that the DEM data of SRTM and CGIAR
have noisy data, it becomes necessary to apply a filter that is
useful to eliminate such noise. This is why the Kalman filter
[
For routing purposes it is necessary to adjust the filter to be influenced by the distance between each point of the path. If two points are very distant then the filter should trust the measurement more than the estimation, on the other hand if two points are very close the filter should trust the estimation more than the measurement. The Kalman filter assumes that a cyclist drives in one direction, but the algorithm should also consider that usually a street can be cycled also from the opposite site. The best results have been generated, when applying the filter for both directions and then merging the two smoothed datasets by taking the average. This fact can be observed in Table 2 for tracks that were cycled in both directions. Track Brixen – Klausen Klausen – Brixen Konstantin – Seis
Seis – Konstantin Ritsch – Kompatsch
Kastelruth – Seis Seis – Kastelruth Average RSME
Figure 2 shows how the Kalman filter removes peaks and lows in the elevation profile (track “Ritsch-Kompatsch“). The y-axis shows the meters above sea level, the x-axis the distance cycled in meters. The ground truth data of the South Tyrol DEM is represented with the black line with squares. The GPS data is not visible in this figure. The noisy SRTM1 v3 profile is the dark grey line with points. The other lines are the applied Kalman filter with different distances of 30, 60 and 100m. These profiles are very similar and perform better that the SRTM1 v3. To get a closer impression of the actual values of the filtered profiles, Table 2 includes the list of the RMSE results.
From Table 2 it can be seen that the Mean filter performs best with a distance value of 50. However, the improvement is small and not equally suitable for different tracks. In contrast, the Kalman filter delivers even better results for almost all tracks with a fixed distance of 30. However, in total there is not much difference between the Mean filtered, the Kalman filtered and the original dataset. Nevertheless, the major important aspect of filter application is to eliminate outliers and reduce or even remove high peaks and lows. By this, the profiles are smoothed, allowing a more realistic routing for cyclists.
In this section it has been shown how well smoothing algorithms perform on noisy elevation data. Without these algorithms it would not make any sense to extract the slope between each location pair, because the calculated slopes would have unrealistic inclines as well as declines. With the help of the filters it is now possible to have access to a more accurate shape of a street, which influences not only the travel time, but also the route selection and thus is relevant for profile based routing. 5.
Online routers become more and more important for people when planning their trips. For motorists, these route engines deliver good results, but for cyclists they often are quite useless. Having specific requirements for route finding, like different bicycles, physical condition or specific geographical location, more aspects have to be regarded by the routing algorithm. The most critical factor for a cyclist is the incline and decline of a path. For this, it is necessary to include elevation information when routing, as well as additional information about the ways. In this work, OpenStreetMap is the source for data about ways and geography. Coming to elevation information, the two digital elevation models SRTM and CGIAR are presented, as well as the regional South-Tyrolean DEM. These DEMs are compared, coming to the conclusion that data voids and interpolated datasets constitute a problem when finding routes for cyclists.
Therefore, methods for DEM improvement were discussed, like noise reduction and the application of smoothing algorithms. In the noise reduction approach the idea is to include more neighboring tiles in order to get a more correct interpolation value for the void in the elevation profile. Since this method did not achieve the desired improvement, different filter algorithms were applied. The Mean and the Kalman filter are two well-known instruments for noise removal in data samples. Especially with the help of the Kalman filter it is possible to reduce the mean average error rate and to flatten the noisy peeks and lows. Taking different distance values as a constant between two way points, the outcome of the algorithms varied, depending also on the basis of the chosen test tracks. These tracks were selected in the test region of South Tyrol as the DEM of this region is of good quality. A comparison of the applied filters to this original ground truth showed that out of all investigated distances applied in the experiment the Mean filter operates best with a distance factor of 50m and the Kalman filter with a distance of 30m. The filtered ways have very smooth slopes and thus, these results are taken into account for the prototypical implementation of the profile aware router.
Having information about the track type and its smoothed elevation profile, as well as the input of preferences of a user profile, which is very flexible and includes many critical factors for bicycle optimized routing, enable the router to calculate accurate travel times, weigh the possible paths according to the profile and thus in the end present the best options for the cyclist.
Future work in this area can be seen in a re-evaluation using the recently available and updated SRTM1 data set that was released in high resolution of one arc-second for Europe in April 2015. 6.