Uphill/downhill is not correct after saving route

[AxdrKom]

Description

Than i create a route in Osmand using build in routing i see calculated elevation (up/down) for this route in navigation panel. After i save this route as a track in navigation/details. Calculated elevation for saved track is much more higher than original route. This is actual for mountain regions with big elevation gradients. I analyze different Osmand versions and tracks for this problem and find what this problem starts after version >=4.0.9. Some tracks created outside osmand have the same problem in Osm versions >4.0.9. I find what <time>XXXX</time> field in gpx data points of tracks affects the result. For example - i take the gpx file with <time> field in data points and see the incorrect result of elevation calculation. Then i delete <time> field elevation calculated correctly.

Steps to reproduce

Need a Osm version <4.0.9 and >4.0.9 Example files in https://drive.google.com/drive/folders/1ApMEwsdWIffujdQvsxML-useXg0vf43O?usp=sharing 4.4.5svd.gpx - file created in Osm 4.4.5 and saved in navigation/details 4.4.5svd_fixT.gpx - the same file but added <time> field in gpx data points Garm.gpx - the 4.4.5svd route recorded by Garmin eTrex 20 (it has a <time> field) in a travel Garm_noT.gpx - the same file but <time> filed deleted.

Actual result

See the table with results of elevation calculation (Up/Down) for theese 4 files in different Osm versions:

Ver/File	4.4.5svd.gpx	4.4.5svd_fixT.gpx	Garm_noT.gpx	Garm.gpx
4.0.9	1642/1404	1642/1404	1710/1470	1710/1470
4.4.5	2393/2162	1704/1485	2287/2047	1853/1629

Expected result

The same results for pairs 4.4.5svd.gpx - 4.4.5svd_fixT.gpx and Garm_noT.gpx- Garm.gpx like in Osmand 4.0.9

Your Environment

OsmAnd Version: After 4.0.9 (for example 4.4.5) Android/iOS version: 9 and 7 Device model: Mi Mix2s and LdPlayer emulator

[sonora]

v4.0.9 still used my normal trend channel analysis and a 5 meter threshold of detecting a trend reversal. It was a rather simple, 1 parameter solution counting trend channels of 5 meters and more, while ignoring any smaller fluctuations as noise.

Then we changed to a more dynamic model. I find it seems equivalent in many situations, but sometimes counts in too much noise. Not sure there are too many cases where it really beats my old method. But it is hard to say. If more evidence will be provided here like yours, it would help to evaluate.

More reading is available in #13224.

[AxdrKom]

But why result affected by <time> field in gpx data. And then track is only routed but not saved elevation calculated correctly (or using different method)? With last versions of Osmand i need to add field with fixed value of time for every point to see the correct uphill/downhill. The value of time for every point does't matter the result.

[sonora]

I think the new algorithm somehow factors in a time/speed dimension when possible. Strange that the values don't matter, though. I'll leave it for someone knowledgeable with the new algorithm to take a look here for now.

[vshcherb]

We're going to update algorithm and document it https://docs.osmand.net/docs/technical/algorithms/

[vshcherb]

@sonora after lots of discussions and comparison with trend and averaging algorithms we decided to switch to algorithm calculate pure Extremums. In a nutshell:

• We will try to find local max/min points. These points should have at least 2-3 (Constant A?) meter higher (lower) than other points in 50m radius (Constant B?)
• Difference altitude between these local min/max will be uphill / downhill
• Based on this point Slope will be displayed and it will be exactly 0 in these points
• For noisy recorded tracks altitude filtering procedure will be applied (most likely not to average points but to eliminate wrong points so back to filter algorithm)

[sonora]

Thanks for the info and your attention to this topic, Victor!

Yes, 2 parameters sounds about the most we should have for the purpose. As you know, in my old solution I had even resorted to just 1, the "5m noise threshold".I think it worked quite well for ascent/descent, but probably when you go to slope determination it may not have captured enough detail for that derivative.

(And please note that 2-3 m may be a bit of a challenge for GPS, that's why I used 5m as a sort of "meaningful compromise".)

[vshcherb]

New algorithm is implemented. We're still developing filters, please read about our findings - https://docs.osmand.net/docs/technical/algorithms/calculate-uphill-slope

Quote: OsmAnd uses 3 steps algorithm: Filter noisy data - not yet implemented Find local extremums (minimums and maximums) Calculate sum of differences between min and max

[vshcherb]

Image to show what extremums should look like on the map (as you see it with elevation isolines)

[sonora]

@vshcherb Yes! Looking good in principle.

• Like the single point filtering!
• Remains to be seen how a Douglas-Peuker impacts the results here. I feel my old 5m trend channel may have been more predictable/transparent, and easier on the code and CPU. Chances are a 7m DP will not differ too much.

Maybe I still find an old OsmAnd 4.0.9 (or so) installation to diretlly compare (or we take the pain to reinstate the old code in parallel for a direct comparison of the results.)

I think this issue https://github.com/osmandapp/OsmAnd/issues/13224 contained our benchmarks at the time, could re-visit.

[vshcherb]

Signal approach:

• still have same constant (call heuristic)
• doesn't take into account scale distribution at all (this one also doesn't on very very short scale which easy to fix, but it does on a long scale cause it searches trend)
• not symmetrical as it moves only forward not backward.

So 1D approach is weakness no a strength.

So in the end we started from trend approach, moved to averaged approach and got back to trend approach. However we keep averaging approach to the slope calculation.

[vshcherb]

As we were comparing trend / signal calculations we've investigated:

• https://en.wikipedia.org/wiki/Weierstrass_function (looks really cool and smooth but produces irrelevant data)
• https://en.wikipedia.org/wiki/Fast_Fourier_transform FFT - https://en.wikipedia.org/wiki/Window_function all different windows
• Finding extremums using windows
• Finding extremums just by points

And then we got back to find trends using Peucker cause it has lots good advantages:

1. It's step by step based approach - so at 1st iteration it finds the most important trend and so on
2. Easy to understand and visualize
3. Understands different slopes but when uphill continues
4. Resistent to sinuse wave function even if they are rotated to the certain slope

[sonora]

Yes, accepted! Let's put it to the test, perhaps with our old benchmarks.

Trouble with many sophisticated methods like FFT or perhaps even DP is they rely on reasonably well behaved and large enough samples. If this was a well controlled scientific experiment, things woulde be fine. Many tracks will hopefully work fine. But some actual user-recorded tracks will be severely over- or undersampled, and we may receive complaints from single users about their individual results. (And we need the expertise to explain the results.).

But again: Good work, by my judgement! Let"s test!

[sonora]

Quick check using my old mountain test of https://github.com/osmandapp/OsmAnd/issues/13224#issue-1059390914 and https://github.com/osmandapp/OsmAnd/issues/13224#issuecomment-975337020:

OsmAnd 4.0.9: OsmAnd 4.4.7: Latest:

[vshcherb]

Noise Filtering is not implemented yet, just attach to the roads or altitude correction and check the values

[sonora]

Ok! Let's see if we can afford to noise-filter so agressively that it makes uo for this potential over-sensitivity of the approach... 😉

[sonora]

Much improved after https://github.com/osmandapp/OsmAnd/commit/6f849147ca3fda5de9520bd5df12bd54dc62aedf!

However, as I sort of expected, we now overfilter to a very obvious degree, see a typical mountain trip here:

The ascent is now underestimated to be just 808 m while the elevation difference covered (a lower boundary for the ascent), is 1884 -1007 = 877 m.

(It's a round trip, so true ascent = desent. OsmAnd 4.5.2 reports +883 m / -841 m, BTW.)

[vshcherb]

That's probably @alex-osm https://github.com/osmandapp/OsmAnd/commit/6f849147ca3fda5de9520bd5df12bd54dc62aedf but I didn't review it yet cause I disagree that it's a correct approach. I think noise filtering shouldn't use peak algorithm and should be purely based on filtering impossible slopes

[sonora]

Perhaps we are solving problems we never had? How about we simply

• (1) return to the v4.0.9 5-meter trend channel for the elevation change, which worked well?
• (2) And apply your suggested "impossible slope" filtering to determine slope? (Slope determination was the weakness?)

We could still check if we do it in this order, or do (2) before (1), i.e. apply the slppe filtering before or after the ascent/desecent determination.

[AxdrKom]

But why field in gpx data affecting result calculated?

[vshcherb]

I think we had problems with trend channel otherwise we wouldn't dare to change it.

[sonora]

@vshcherb Any details/documentation on the issues? I could offer to take a look.

Only unwanted behavior I can imagine may have been the impact of singular outliers - but that would not be a weakness of trend channeling, and could be fixed by slope-filtering.

[vshcherb]

@sonora

Quick check using my old mountain test of https://github.com/osmandapp/OsmAnd/issues/13224#issue-1059390914 and https://github.com/osmandapp/OsmAnd/issues/13224#issuecomment-975337020:

Please check I think newer version much improved and works according documentation, you should see uphill 1264m, downhill 2286m

[vshcherb]

Algorithms start shaping so 2 phase algorithm: filter + calculate extremums now give confident results. Filter tries to eliminate impossible outliers that have slope > 100%, where 2nd phase calculates trends using Douglas Peucker algorithms and once extremums are calculated it calcualtes uphill / downhill

[vshcherb]

As a reference of different algorithms on provided tracks

[sonora]

you should see uphill 1264m, downhill 2286m

With build of 2023-07-02:

@sonora probably track is different check it on internal issue 2083.

Correct, my apologies, same mountain, but different route :wink: . Here is the one we had used:

[vshcherb]

@sonora probably track is different check it on internal issue 2083.

[sonora]

Good job, it looks like! :wink: Perhaps a very slight over-filtering now - I find some examples where the estimated ascent is slightly less (up to 5%) than the actual max-min elevation change covered. But from what I see so far, very tolerable.

Climbers may think different - they better take their true ascent from the max-min difference, rather than from the "impossible slope-filtered" summation... :wink:

[vshcherb]

Update documentaiton https://docs.osmand.net/docs/technical/algorithms/calculate-uphill-slope