Add user selected track smoothing to decrease distance

[GoogleCodeExporter]

A lot of people have asked for this feature.  So I am going to write up what it 
would take.  Hopefully someone can read through this and decide to implement it.

1. I think it is important to faithfully record the points as we record them.  
So we should write all points as we received them from the hard ware into the 
db.

2. While recording we use a shared preference along with a smoothing algorithm 
to smooth out the track.  It is important to let this be user selected because 
the right value is probably different for different hardware and use cases.  IE 
it is probably not useful at all when flying as you move to fast but probably 
very useful hiking in narrow canyons.
Smoothing algorithms
2.1 Simple exponential decay of previous points.
2.2 Kamlan filter http://en.wikipedia.org/wiki/Kalman_filter

3. This is where the problem gets actually hard.  We recalculate distance when 
creating the chart view.  It is important that this distance is the same as 
what we calculate when we recorded the track.  So we have a few choices to make 
that work:
3.1 Store distance with each track point.  I have wanted to do this for a while 
but it is a lot of extra data.
3.2 Store the smoothing factor used when calculating the track. This uses a lot 
less data but seems a little hacky.

4. (Optional) We should provide some way to post process a track with different 
smoothing functions/values.

Original issue reported on code.google.com by sandordo...@google.com on 24 Feb 2011 at 4:58

[GoogleCodeExporter]

Another smoothing algorithm - Douglas-Peucker:
http://softsurfer.com/Archive/algorithm_0205/algorithm_0205.htm#Douglas-Peucker%
20Algorithm

Original comment by ba...@google.com on 25 Feb 2011 at 6:47

[GoogleCodeExporter]

Eduardo had investigated some of these when we did Tour de France. Eduardo, can 
you comment?

Original comment by rdama...@google.com on 25 Feb 2011 at 9:22

[GoogleCodeExporter]

I think, we need to consider the following features of a moving object/person:
1) Velocity and max acceleration
2) Ability to do rapid turns (important factor for hiking, skiing, walking, 
jogging etc.)
3) Rapid elevation gains/drops (e.g. skiing, hiking, kayaking (waterfall 
drops), flying)
4) Sensor precision

Each of these categories has serious implications on the smoothing algorithm.  
Also, it's important to note, that in most cases you can't do realtime 
smoothing.

I vote for recording all data points w/o smoothing and applying smoothing at 
the time of export or in the cloud (in near future).  Anything else is 
unpredictable and error prone.

Original comment by ba...@google.com on 25 Feb 2011 at 9:33

[GoogleCodeExporter]

Re: Douglas-Peucker and other line simplification algorithms, you need to keep 
in mind that this approach is only useful for coordinates (i.e. the algorithm 
tries to draw a line/polygon that looks visually the same with much fewer 
points). Picking these points and the respective values for other variables 
(speed, height) might make the charts for the other variables skewed, or miss 
important peak values.

I don't know what different users want this feature for, but if they need 
smoother charts for a given variable, then talking about line simplification 
doesn't make sense. If it's about getting a simpler path saved for a track, 
then line simplification would be the way to go, but you may want to modify the 
algorithm to try to keep peaks in other variables in mind.

Actually, modifying Douglas-Peucker to take other variables into account should 
be simple; each step takes a pivot point that is the most distant to the start 
and end point. It adds these points until a certain threshold distance is 
reached, and drops all intervening points in the (start, pivot), (pivot, end) 
ranges. If you account for the other variables in the distance formula, you 
might get a simplification that is a good compromise between all different 
variables at all points in the track.

If you only add height, then 3D distance is still simple. With more variables, 
I'm not so sure. Does this make sense?

Original comment by escorde...@google.com on 25 Feb 2011 at 9:33

[GoogleCodeExporter]

I agree that all points should be recorded and smoothing should be performed
only at export, or later.

Original comment by escorde...@google.com on 25 Feb 2011 at 9:37

[GoogleCodeExporter]

"I vote for recording all data points w/o smoothing ... Anything else is 
unpredictable and error prone."

The current code is not just error prone, but essentially guaranteed to be in 
large error- at least for runners. My morning run today was off by nearly 33% 
because of recording jitter (careful use of gmaps pedometer shows that it was a 
5.4K run, my tracks showed it as 7.2K.) Perhaps the right thing to do is to 
smooth it by default if smoothing would change it more than (say) 20%? Or if it 
is known to be a particularly error-prone situation (i.e., you are moving 
particularly slowly?) As it currently stands, the error margin is so large as 
to make it useless for at least some use cases.

Original comment by luis.vi...@gmail.com on 5 Apr 2011 at 2:43

[GoogleCodeExporter]

Issue 420 has been merged into this issue.

Original comment by sandordo...@google.com on 13 Apr 2011 at 3:41

[GoogleCodeExporter]

Please could you explain how all this affects the inaccuracy in elevation?
I posted issue 420 and don't really understand what you are talking about in 
this issue, maybe you could explain the fix in plain speak for me.
It is a great app but:
my track states my maximum elevation as 424m but if I look at the contours on 
the map I never went above 380m 
And the sitting still but moving around in 10m jumps issue...

Original comment by JamesSwe...@gmail.com on 14 Apr 2011 at 12:32

[GoogleCodeExporter]

I recently updated to 1.1.4 and can confirm the observations described in 
comment 6. According to MyTracks todays hike had a distance of 7,98 km when in 
fact it was only 5,88 km (distance determined by Google Earth from the exported 
KML file). That accounts to an error of about 36%.
It seems the work on correctly counting the moving time (r506) messed up the 
distance counting. This basically also re-opens issue 281, as both the moving 
time and the distance are counted incorrectly again. I tried to re-open issue 
281, but apparently that's not possible via the web-interface, so instead I'm 
commenting here.

Original comment by axel.kap...@gmail.com on 18 Apr 2011 at 8:22

[GoogleCodeExporter]

Issue 475 has been merged into this issue.

Original comment by sandordo...@google.com on 10 Jun 2011 at 3:21

[GoogleCodeExporter]

I'm quite sure that issues 281, 420, and 475 (marked as duplicates of 363) 
aren't related to track smoothing in any way, but are rather caused by a bug in 
the distance counting algorithm. In version 1.1.1 distance overcounting (issue 
281) was fixed and the error in track distance went down to 3% - 5%. Seems this 
is the small, one digit error that is actually introduced by the current track 
smoothing algorithm. Not perfect, but also not too bad. Unfortunately, the fix 
for distance overcounting messed up the counting of moving time. A fix 
introduced for 1.1.2 to solve this (most likely rb3b6aec4273d) broke distance 
counting again and the error in track distance went back up to >30%.
So I think we are really dealing with two different problems here and it should 
be possible to fix distance overcounting without having to implement a 
completely new way to process track data.
Or am I wrong? Would be nice, if one of the googlers could comment on this.

Thanks,

Axel

P.S. Hope I got the revision numbers right this time, sorry if that's not the 
case. ;)

Original comment by axel.kap...@gmail.com on 18 Jun 2011 at 3:22

[GoogleCodeExporter]

Issue 525 has been merged into this issue.

Original comment by sandordo...@google.com on 23 Jul 2011 at 8:54

[GoogleCodeExporter]

I used to be a professional navigator but have forgotten all the mathematics 
now. I remember using a matrix computation of a least squares solution to 
smooth out data - that was generally how it was done for accurate survey 
navigation. We used microwave and sub microwave systems that were much more 
accurate than GPS but never relied on raw data to give tracks - raw data was 
logged as was computed track data. As far as I recall with least squares you 
don't need "user selection" because it is automatically a "best fit". Sorry 
that I can't remember more - it was 20 years ago...

Original comment by skito...@gmail.com on 23 Jul 2011 at 9:25

[GoogleCodeExporter]

Did a 38.6km bike ride today and MyTracks read 41.02km. This makes it 
unsuitable for even basic use. I can't see the point in using MyTracks until 
this is sorted.

Original comment by skito...@gmail.com on 25 Jul 2011 at 8:47

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

I recorded a track along the Thames on a boat today, looking at the map the 
track looks great following the river, but when you look at the elevation gain 
you wonder how we managed to gain 200 metres going 8 kms up river. We did go 
through a lock but that was only 1.5 metres. When you look at the elevation 
graph it is going up from 50 to 70 metres in huge spikes, very wierd. 

Original comment by JamesSwe...@gmail.com on 27 Jul 2011 at 3:32

[GoogleCodeExporter]

GPS elevation is not so reliable - but filtering of that too is essential. I 
can't understand why this software doesn't have any of that already - I'd have 
thought it would be there before the very start it's so fundamental.

Original comment by skito...@gmail.com on 27 Jul 2011 at 6:34

[GoogleCodeExporter]

Issue 46 outlines a method to fix inaccurate GPS elevation readings, I 
recommend you also star that.

BTW, I agree with comments #6 and #14. You should really put some emphasis on 
sorting out all those quirks in statistics and track data calculation. That's 
basic stuff that has to work correctly for the app to be useful.

Original comment by axel.kap...@gmail.com on 27 Jul 2011 at 7:17

[GoogleCodeExporter]

Statistician and runner here. I agree that the distance calculation is almost 
useless for a runner, and smoothing is necessary. I believe the Garmin watches 
use a smoothing algorithm to provide better accuracy, but I can't find anything 
online about what they do specifically.

For on-the-go calculations, I think the Kalman filter will work quite well. It 
was designed to efficiently estimate the state of a system (e.g. your position) 
when the measurements of the state are subject to noise. Actually the first 
example on the wikipedia page for the Kalman filter is GPS navigation.

For post-processing purposes, you might want to look into using B-splines. They 
are useful when the curve has different degrees of smoothness at different 
times, which describes a usual path for a runner or cyclist--you may go 
straight for a mile and then take a sharp 90 degree turn and continue straight 
for another mile.

Original comment by joeguinn...@gmail.com on 12 Aug 2011 at 5:16

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Using ver 1.1.18.  On recent 40km bike ride got pretty good results for the 
total distance, moving time, average moving speed based on the results other 
riders had from their "cycle computers". However my maximum speed was 109 kph - 
I'm a reasonably good cyclist but not that good!! Looking at the track in 
Google Earth it's pretty clear the GPS locking wasn't that good in the forest 
section of the ride. Should any smoothing algorithms take into account the GPS 
accuracy at each point. I'm not sure if the GPS driver provides this 
information for every point and/or if MyTracks retains the info the database? 
It may make sense to check for slack GPS locking before utilising some points? 
They tend to average out OK but seem inappropriate for calculating a maximum 
speed or say gradient changes.

Original comment by bigya...@gmail.com on 26 Aug 2011 at 11:13

[GoogleCodeExporter]

Dear Developers,
I have programmed but I am not able to help with development.  However I was 
looking at the code that updates the elevation and elevation gained statistic 
and found a few things:

In function addLocation(), the call to updateElevation() occurs near the 
beginning of the routine, before various validations on current location, such 
as making sure that we are currently moving.  So, it seems to me that the call 
to updateElevation() should be moved down to the other update function calls 
such as addTotalDistance(), updateSpeed() and updateGrade() - near the bottom 
of the function.   Making this change should at least slightly decrease the 
errors in the Elevation Gained statistic since currently it is being updated 
even if the code thinks the user is not moving.

Secondly, by my reading of the code, the elevation gain calculation is not done 
on the actual elevation data, but instead is done on the 25 point moving 
average (smoothed) elevation data.  However, this does not really do anything 
significantly to decrease the possible error in the elevation gain calculation 
- it just makes it different.  Let me give an example:

Instead of averaging 25 data, let's change it to 5 for the purpose of this 
example.  Assume the incoming elevation data are: A, B, C, D, E and F.  If you 
did not use the smoothed data, the first elevation difference would be (A-B).  
But if you do the 5 point smoothing, the difference between the first two 
smoothed elevation points are

   (A+B+C+D+E)/5 - (B+C+D+E+F)/5 == (A-F)/5

So it looks like it really only takes difference in raw elevations that are 25 
positions apart (vs 5 in this example) and it also appears that the result will 
be divided by 25 and I don't see where the factor of 25 is corrected.  So, am I 
missing something?

By the way, is this the place to post stuff like this?  Is there a better place 
to get this kind of info to the developers?  Also, thank you so much to the 
developers!  I Love My Tracks!!!!

Original comment by fbh1...@gmail.com on 13 Sep 2011 at 3:48

[GoogleCodeExporter]

@fbhi...
A moving average will have lower total jitter.
I would consider movign the call to updateElevation lower down in the function. 
 Please test that change out and report your success.

Original comment by sandordo...@google.com on 13 Sep 2011 at 4:07

[GoogleCodeExporter]

@sandorodo... of Comment 23

If you are asking me, unfortunately, I don't have the ability to make the code 
change.  If you could send me a modified MyTracks App with that change made, I 
would be happy to test it for you.

I agree that on a plot of elevation, the jitter will be less by using a moving 
average, but if I am correct and the code is subtracting "adjacent" moving 
averages, the only effect that has is that the difference will be the 
difference between 2 individual elevation point separated by the size of the 
buffer (ELEVATION_SMOOTHING_FACTOR = 25) since the common 24 points of the two 
averages will cancel.  Also, the elevation difference will be divided by 25 
which I hope is compensated for somewhere else in the code (but I cannot find 
that place).

Original comment by fbh1...@gmail.com on 13 Sep 2011 at 4:32

[GoogleCodeExporter]

Issue 575 has been merged into this issue.

Original comment by sandordo...@google.com on 20 Sep 2011 at 3:52

[GoogleCodeExporter]

I also love my tracks!

One question I have regarding distance calculation.

I had a very simple view of GPS and naively thought that I could get accurate 
GPS points and find the distance between the current point and the previous 
point and this would add up to the distance traveled.

This very simple approach seems to work okay.

Here's the question.  I have a route I do often.  According to google maps it 
is 6.2 miles (adjusted for one mistake in the google directions), but My Tracks 
records it as 6.69 miles, while I use map my run on the same phone and it 
records 6.31 miles and the simple approach that I described earlier an 
application called ETA in the android market records 6.15 miles

To summarize:
* google maps walking directions: 6.2 miles
* my tracks: 6.69 miles
* map my run: 6.31 miles
* ETA (simple approach): 6.15 miles

I wonder what is the best approach for running / walking speed and does it 
change when at car or highway speeds.

I currently ask for a GPS window of 50 meters and disregard accuracy that are 
higher than 10 meters.

Is there a mode in My Tracks that shows what the current minDistance for 
requestLocationUpdates value is?

public void requestLocationUpdates (String provider, long minTime, float 
minDistance, LocationListener listener)

minTime the minimum time interval for notifications, in milliseconds. This 
field is only used as a hint to conserve power, and actual time between 
location updates may be greater or lesser than this value.
minDistance the minimum distance interval for notifications, in meters

Is there a debug mode where you can see how My Tracks calculates the distance 
and how it is smoothed etc.

Original comment by fed...@gmail.com on 20 May 2012 at 2:29

[GoogleCodeExporter]

MyTracks is useless for distance accuracy - it makes the software useless 
altogether. I use Endomondo for sports tracking and find it to be incredibly 
consistent. I abanoned MyTracks a year ago and won't be using it again.

Original comment by skito...@gmail.com on 20 May 2012 at 12:07

[GoogleCodeExporter]

Does anybody care about this? As many people have said earlier, this issue 
makes the program unusable for many people, including myself.

Original comment by mtsb...@gmail.com on 20 Mar 2014 at 1:38

[GoogleCodeExporter]

Original comment by jshih@google.com on 14 Oct 2014 at 8:52

• Changed state: WontFix