mean of curves - how to define and approximate?

[Helmut Jarausch]

Hi,

let's start with the application I have in mind:

Given several tracks, i.e. piecewise linear curves in 2D, as recorded by
a GPS device for the same real track. Because of measurement errors these
tracks aren't identical.

How can one define and approximate something like a "mean curve" oder
"median curve" or averaged curve?

Thanks for any pointers,
Helmut.

[Kaba]

Helmut Jarausch wrote:
> Hi,
>
> let's start with the application I have in mind:
>
> Given several tracks, i.e. piecewise linear curves in 2D, as recorded by
> a GPS device for the same real track. Because of measurement errors these
> tracks aren't identical.
>
> How can one define and approximate something like a "mean curve" oder
> "median curve" or averaged curve?

Hi,

This seems to be an estimation problem, but I am unable to formulate a
problem with this information.

Could you give some more details? Is there a time-stamp with every
measurement? How does the "track" get formed?

--
http://kaba.hilvi.org

[Dr J R Stockton]

In comp.graphics.algorithms message <4f59ff08$0$7696$ba62...@news.skyne
t.be>, Fri, 9 Mar 2012 13:00:56, Helmut Jarausch <jara...@skynet.be>
posted:

>let's start with the application I have in mind:
>
>Given several tracks, i.e. piecewise linear curves in 2D, as recorded by
>a GPS device for the same real track. Because of measurement errors these
>tracks aren't identical.
>
>How can one define and approximate something like a "mean curve" oder
>"median curve" or averaged curve?

If the times of the points of the tracks are known, then the obvious
move seems to be select suitable intervals (interpolating tracks if
necessary, linearly or otherwise, and to plot the mean, or RMS,
positions to give the average.

If you do not know the times of the points, but do know the relative
durations of the tracks, then you can divide each track into suitable
intervals and proceed from there.

Otherwise, the question may possibly not be meaningful, or wise.

--
(c) John Stockton, nr London, UK. ?@merlyn.demon.co.uk Turnpike 6.05 WinXP.
Web <http://www.merlyn.demon.co.uk/> - FAQ-type topics, acronyms, and links.
Command-prompt MiniTrue is useful for viewing/searching/altering files. Free,
DOS/Win/UNIX now 2.0.6; see <URL:http://www.merlyn.demon.co.uk/pc-links.htm>.

[JohnF]

Dr J R Stockton <repl...@merlyn.demon.co.uk> wrote:
> Helmut Jarausch <jara...@skynet.be> posted:
>
>>let's start with the application I have in mind:
>>
>>Given several tracks, i.e. piecewise linear curves in 2D, as recorded by
>>a GPS device for the same real track. Because of measurement errors these
>>tracks aren't identical.
>>
>>How can one define and approximate something like a "mean curve" oder
>>"median curve" or averaged curve?
>
> If the times of the points of the tracks are known, then the obvious
> move seems to be select suitable intervals (interpolating tracks if
> necessary, linearly or otherwise, and to plot the mean, or RMS,
> positions to give the average.
>
> If you do not know the times of the points, but do know the relative
> durations of the tracks, then you can divide each track into suitable
> intervals and proceed from there.
>
> Otherwise, the question may possibly not be meaningful, or wise.

Not a suggestion, just curious -- couldn't you formulate this
as some calculus of variations problem, parameterizing each
track by its arclength, s, with a lat,lon point associated with
each s? Then, the best curve, f(s), would minimize the sum over
all tracks of \int_{s=s1}^{s2} d^2(f(s),t_i(s)) ds, where t_i(s)
is the i^th track, and d^2(.,.) is the distance(squared) function
between lat,lon for f(s) and lat,lon for t_i(s). Or something
like that.
--
John Forkosh ( mailto: j...@f.com where j=john and f=forkosh )

[Helmut Jarausch]

Thanks!

First, what is d ? (in d^2(f(s),t_i(s)) ) ?
Second, the different tracks don't have equal arclengths, some of them
might even have tiny kinks.

The main problem, for me, is the lack of a "reference curve".

Helmut.




--

[Helmut Jarausch]

On Sat, 10 Mar 2012 20:33:18 +0000, Dr J R Stockton wrote:

> In comp.graphics.algorithms message <4f59ff08$0$7696$ba62...@news.skyne
> t.be>, Fri, 9 Mar 2012 13:00:56, Helmut Jarausch <jara...@skynet.be>
> posted:
>
>>let's start with the application I have in mind:
>>
>>Given several tracks, i.e. piecewise linear curves in 2D, as recorded by
>>a GPS device for the same real track. Because of measurement errors
>>these tracks aren't identical.
>>
>>How can one define and approximate something like a "mean curve" oder
>>"median curve" or averaged curve?
>
> If the times of the points of the tracks are known, then the obvious
> move seems to be select suitable intervals (interpolating tracks if
> necessary, linearly or otherwise, and to plot the mean, or RMS,
> positions to give the average.
>
> If you do not know the times of the points, but do know the relative
> durations of the tracks, then you can divide each track into suitable
> intervals and proceed from there.
>
> Otherwise, the question may possibly not be meaningful, or wise.

The tracks are obtained by traversing the real track several times.
Therefore the speed of traversal isn't the same for each track.
The formulation of the average problem is the main problem.
Heuristically, I'd consider the tracks as clouds of points forming a
narrow tube. Then I'd draw a middle curve - but what's this
mathematically?

Thanks,
Helmut.

[JohnF]

d(.,.) is the distance function, but I mentioned that very clearly.
Do you have some other related question?
A little more detail: at a given s, there's a lat,lon for the trial
function f(s) you're testing, and a lat_i,lon_i for the track t_i(s).
Then d(f(s),t_i(s)) is the distance from point lat,lon at arclength s
along f, to point lat_i,lon_i at arclength s along t_i. You can calculate
that for a flat earth, or for great circle distance, or however you like.
But you have the lat,lon for two points, so I assume you can get the
distance between them. And then d^2 =d*d is that number squared.

> Second, the different tracks don't have equal arclengths, some of them
> might even have tiny kinks.

That might be a problem. As a zeroth-order guess, I'd probably
"normalize" the curves so s=0 to s=1 along all of them.
If the tracks are wildly different, no procedure's going to
make much sense, anyway. Kinks I'd personally just cut out,
but I don't know where those tracks come from (personally,
I'm a sailor-type person thinking about offshore passage making,
where, say, an autopilot might bring you back to your preprogrammed
bearing line by the shortest possible route), or what you're doing
with them.

> The main problem, for me, is the lack of a "reference curve".
> Helmut.

Note that I originally said "formulate" the problem, not "solve" it.
For the latter, you need some way to search the function space f(s),
and improve your guess based on previous results (a "result" being
the \sum_{t_i's}\int_{s}... for a trial f(s) function).
There's "steepest descent" stuff, and trucloads of other
methodologies to do that. You'll have to read up on all that
and figure out what might do a good job for your situation,
assuming you choose to use my suggestion.

[Helmut Jarausch]

That's problematic. I've seen that people are considering unknown
reparametrizations for time series which are even easier to handle.
It's not easy to even 'compare' the starting and final points of the
tracks.

> If the tracks are wildly different, no procedure's going to make much
> sense, anyway. Kinks I'd personally just cut out,
> but I don't know where those tracks come from (personally,
> I'm a sailor-type person thinking about offshore passage making,
> where, say, an autopilot might bring you back to your preprogrammed
> bearing line by the shortest possible route), or what you're doing with
> them.

They are not 'wildly different'. They come from hiking or cycling along
a trail several times. The 'averaged curved' could then be used to enter
this trail into an open street map.

>
>> The main problem, for me, is the lack of a "reference curve".
>> Helmut.
>
> Note that I originally said "formulate" the problem, not "solve" it.
> For the latter, you need some way to search the function space f(s),
> and improve your guess based on previous results (a "result" being the
> \sum_{t_i's}\int_{s}... for a trial f(s) function).
> There's "steepest descent" stuff, and trucloads of other methodologies
> to do that. You'll have to read up on all that and figure out what might
> do a good job for your situation,
> assuming you choose to use my suggestion.

No, I didn't think of a solution, yet. If I had a reference curve, I
could consider orthogonal distance regression, i.e. minimize the sum of
squares or L1-norms of the perpendiculars onto the reference curve.

So, it seems to be tough to even decide if there exists a meaningful,
well defined problem formulation.

Thanks for the discussion,
Helmut.

[Jens Kleimann]

On 10.03.2012 21:33, Dr J R Stockton wrote:
> In comp.graphics.algorithms message <4f59ff08$0$7696$ba62...@news.skyne
> t.be>, Fri, 9 Mar 2012 13:00:56, Helmut Jarausch <jara...@skynet.be>
> posted:
>
>> let's start with the application I have in mind:
>>
>> Given several tracks, i.e. piecewise linear curves in 2D, as recorded by
>> a GPS device for the same real track. Because of measurement errors these
>> tracks aren't identical.
>>
>> How can one define and approximate something like a "mean curve" oder
>> "median curve" or averaged curve?
>
> If the times of the points of the tracks are known, then the obvious
> move seems to be select suitable intervals (interpolating tracks if
> necessary, linearly or otherwise, and to plot the mean, or RMS,
> positions to give the average.
>
> If you do not know the times of the points, but do know the relative
> durations of the tracks, then you can divide each track into suitable
> intervals and proceed from there.

I think you can do something meaningful about this without knowing either the timestamps or the relative duration:
Suppose Pj[i] is the position of the ith vertex of track number j, which thus consists of line elements with endpoints (Pj[0],Pj[1]), ..., (Pj[Nj-1],Pj[Nj]), where Nj+1 is the number of vertices that make up the track.
Then let Fj(s) (with parameter s in [0,1]) be the position along the piecewise linear track j, such that Fj(0)=Pj[0] and Fj(1)=P[N_j]. You then pick an integer M > max{Nj} and create for each track a set of vertices Vj[i]:=Fj(i/Nj). Vj has the same number M of vertices for each track, and given that the tracks only differ by measurement errors (which I take to be small compared to the mean curvature scale of the track), the Vj(i) for given i are close by each other. Your "average" track could then be defined as the piecewise linear track consisting of the M averaged vertices A[i]:=Sum(Vj[i],j=1..NT)/NT, NT being the total number of tracks. This average track thus
1. connects the average starting point to the average destination of all tracks,
2. is identical to all tracks if these are identical to each other (i.e. in the case of vanishing measurement errors),
3. depends on individual tracks only with weighting 1/NT, and
4. will not be longer than the longest individual track.

Other choices are possible, depending on what additional constraints (like total length, smoothness, etc.) you wish to impose on the solution.

Jens.
--
Remove '_nospam' for actual email address.