Graphhopper: Filter out artificial elevation gain/loss

[msbarry]

1953 improves the resolution of elevation profiles so that they don't miss real elevation changes along routes, but it also makes the profile more susceptible to noise artificially inflating total elevation gain/loss metrics.

For example, going around this turn in the Danube Valley should be flat, but any method that relies solely on DEM data will show it going up the side of the valley and back down to the river:
.

Also, see this example described in this blog post which should be a steady ascent and descent. Without smoothing, the switchbacks appear to go up and down the side of the hill:

With graph.elevation.smoothing the total ascent/descent and switchback gain/loss are reduced, but it introduces some artifacts to the elevation profile that look like shear cliffs:

We should see if there is a way to improve elevation profile smoothing to account for cases like these while maintaining an accurate looking profile.

See other examples and comparisons to other providers in comments on #1953.

[msbarry]

A few ideas off the top of my head:

• when we smooth the profile, get the min and max elevation sample used during bilinear interpolation and use that range to guess what elevation the road should be at, assuming roads are typically built to maintain a steady grade.
• during smoothing, do polyline simplification on the 2D elevation vs. distance profile of the segment, and assign elevations to points by interpolating along that (maybe using the DEM elevation range as the tolerance for each point)

[otbutz]

I think we should check whether the gradient of the path exceeds a certain threshold at any point. This should be a fairly safe criterion, otherwise the route would no longer be passable by cars.

For reference: https://en.wikipedia.org/wiki/Baldwin_Street (gradient of 35%)

[msbarry]

We'll have to take into account what kind of road as well, I know I've done at least a few hiking trails that exceed 35% for extended periods of time https://onthegomap.com/s/i76rib2u

[msbarry]

There's also probably some low hanging fruit with the existing elevation smoothing code. From my understanding it does a windowed average of all points within 150m on the segment. This results in a couple of issues:

• points are denser around corners and each is given equal weight, so it ends up "pulling" nearby samples toward the turn (weighted average based on distance between points might help)
• if a path is going up a hill, and there is an intersection halfway up, the windowed average on the uphill side of the intersection get "pulled up" because they don't take into account samples from lower on the hill, and points on the downhill side get "pulled down" resulting in a sharp increase at that intersection
• the smoothing code changes the elevation samples as it iterates through them, which leads to elevation profiles looking different based on the direction the way is processed

Likely, these don't impact overall elevation gain/loss much, they just result in issues with the profile shape.

[boldtrn]

One idea off the top of my head would to filter out the noise. So we should probably look at filtering out outliers.

For example for an elevation profile that looks like this:

______/\______

We should filter out that bump.

But like this:

____/    \______

We should keep it.

So for example, if there is just one point that is different than the two surrounding points, then maybe the center point is wrong.

This results in a couple of issues

Yes, a major issue, IIRC, is that the algorithm doesn't touch the tower nodes and I think we made some compromises there in regards to speed vs. accuracy. But in general, yes the algorithm certainly has potential for improvement :).

I think we should check whether the gradient of the path exceeds a certain threshold at any point.

I had a similar idea in the past. And I think, back then I checked for slopes > 25%, and there weren't that many, that were obviously wrong. I mean there a lot of paths up the mountain that are that steep. So that got a bit tricky to use it as rule of thumb.

during smoothing, do polyline simplification on the 2D elevation vs. distance profile of the segment, and assign elevations to points by interpolating along that (maybe using the DEM elevation range as the tolerance for each point)

Could you elaborate on that idea? I am not sure I am understanding it.

[msbarry]

during smoothing, do polyline simplification on the 2D elevation vs. distance profile of the segment, and assign elevations to points by interpolating along that (maybe using the DEM elevation range as the tolerance for each point)

Could you elaborate on that idea? I am not sure I am understanding it.

After #1953 gets merged, the last step processing a way is that we do 3D polyline simplification that throws out any point that changes the 3d polyline by less than some tolerance. We are talking about setting the elevation tolerance to 3-5m, but that still retains the "exact" elevation at each point when going around turns. During the smoothing step, we could also run 2D polyline simplification on just the elevation profile to keep the overall shape but throw out noise in the middle.

The "DEM elevation range" idea is that each point lies somewhere between 4 neighboring elevation samples from the DEM data. You know the ground rises from the min to max neighboring value, but you don't know exactly where the rise happens, so you treat the entire possible elevation range as the tolerance for that point when doing polyline simplification or another smoothing technique. For example, if a road at 1000m goes along the edge of a cliff, every time you sample DEM data, 1 or 2 samples are in the canyon at 800-900m and the rest are at 1000m along the rim. The profile using bilinear interpolation oscillates between 900 and 1000m, but if you simplify that keeping in mind the "range" of each point, then you can throw out all of those artificial drops.

[otbutz]

I think we need to distinguish between "noise" which for me is lots of tiny changes in elevation falsifying the accumulated ascend/descend sums and real "errors" caused by outliers in the elevation profile.

We'll probably end up with a two phase process:

1. outlier detection
2. smoothing