1
$\begingroup$

EDIT:

As pointed, there is already a similar question "buried" inside a larger-scope one. I'll reproduce the relevant part here:

If I have multiple recordings of the same routes are there any valid techniques to combine them to get closer to the real route?

The relevant part of the chosen answer, in the context of my question, is this:

With multiple recordings, you can create a 2D kernel smooth of each, sum the smooths, and subject that to a topographic analysis to look for a "ridgeline." You won't get a single connected line, usually, but you can often patch the ridges together into a continuous path. People have used this method to average hurricane tracks, for example.

I have a set of polylines in bidimensional space (X,Y) representing object trajectories. Every polyline in the set is a measured track along the same prescribed path, most of them (but not all) starting around the same point, and ending around the same other point.

I would like to statistically calculate the idealized path ("average polyline") from the set of polylines, in the same way I would manually manually trace it in a drawing program, except I would like this to happen without manual intervention.

A sample image of a part of the polyline set (cropped) is below. It seems to me that tere is an "obvious" place where I would draw the average line with the mouse, but I can't figure which algorithm I could use.

Important notes:

  1. I know I could use the nodes for calculations, but some segments might be arbitrarily long, thus not having nearby nodes that would help in the calculations. That is, I would like to consider the line segments themselves for the calculation, not just the nodes.
  2. There might be parts of a polyline behaving like outliers (see image). I think that, given the majority of polylines is well behaved, this outlier part would easily be "absorbed" by the well-behaved ones nearby.
  3. Although the original data is time-stamped, I believe no temporal relation should be necessary to infer the spatial result I am after, isn't it?
  4. Yes, this is GPS data (although this is incidental to the problem formulation, which has been purposefully abstracted).

enter image description here

Improve this question
$\endgroup$
6
  • $\begingroup$ Could you (via interpolation) put a fixed number of points on each polyline (somewhere in the region of say 100 to 1000), and then compute some robust "typical value) for the first such point, the second such point and so on? $\endgroup$
    – Glen_b
    Commented Mar 11, 2014 at 1:19
  • $\begingroup$ @Glen_b well, I thought about resampling the segments themselves so that I would have lots of small segments of similar length. Then I could consider the points themselves and use some walking algorithm, but which one? $\endgroup$
    – heltonbiker
    Commented Mar 11, 2014 at 1:34
  • $\begingroup$ @AndyW well I'm not sure if it is an exact duplicate, but this part is interesting: "With multiple recordings, you can create a 2D kernel smooth of each, sum the smooths, and subject that to a topographic analysis to look for a "ridgeline." You won't get a single connected line, usually, but you can often patch the ridges together into a continuous path. People have used this method to average hurricane tracks, for example." This would imply, I believe, the creation of a Grid with a given resolution, and this might be a very huge grid. A "flooding" algorithm could be more desireable. $\endgroup$
    – heltonbiker
    Commented Mar 13, 2014 at 13:11
  • $\begingroup$ By "flooding" I mean an algorithm which follows a bundle of paths near some vicinity, adding a breadcrumb and moving on. But I'll have to at least try the Kernel Density Estimation approach, for sure, maybe a segmented one. $\endgroup$
    – heltonbiker
    Commented Mar 13, 2014 at 13:13
  • $\begingroup$ @heltonbiker - If the prior question is unsatisfactory you can edit this one to more clearly state the differences. $\endgroup$
    – Andy W
    Commented Mar 13, 2014 at 13:59

0

Reset to default