4

With limited knowledge of mathematics, I am not sure what tags to use for this question.

I have a path on a 2D surface called $(p1)$. A path consists of a set of ordered $(x,y)$ coordinates. By ordered I mean the first line segment in a path would be $(x1,y1) to (x2,y2)$, the second line segment would be $(x2,y2) to (x3,y3)$ and so on. So these ordered points create a shape and direction of travel similar to what you would see on top-down Google Maps view.

I need to match this path $(p1)$ against some other arbitrary paths to determine which one is the closest to the original path $(p1)$ in terms of shape and direction of travel. The number of line segments making up each path could be arbitrary by the way so there needs to be a way of handling tolerance.

Not sure what this is called but I have explored some LQE techniques such as the Kalman Filter in vain. What I am looking for is analysing a static set of ordered points against another rather than progressive prediction.

I am not sure what constructs can represent similarity between paths. Any guidance would be highly appreciated.

Raheel Khan
  • 569
  • 1
  • 5
  • 21
  • 1
    You could use the Fréchet distance, but that might be too generic. What do your paths represent? – Chris Culter Aug 02 '13 at 22:01
  • Thanks @ChrisCulter. The original paths $(p1,p2, etc.)$ represent the expected path of travel for vehicles. This is hand-drawn over a map. The arbitrary paths are actual vehicle coordinates. So I need to take each vehicle and determining which predefined path is it most likely travelling on. – Raheel Khan Aug 02 '13 at 22:46
  • 1
    @ChrisCulter: Could you elaborate how to go about implementing this measure as an algorithm. It seems to be what I am looking for but mathematical notation is beyond me. A little narration would go a long way. Thanks in advance. – Raheel Khan Aug 02 '13 at 22:51
  • Unfortunately, I've never implemented it myself. I remember considering it for an application and deciding it was too involved. :) But the references on Wikipedia lead to some descriptions of algorithms that should work. As for your application... hmm, I don't know. The Frechet distance doesn't intuitively feel like the best approach, since it's sensitive to the measurement with the worst error, it doesn't take into account the density of measurements, and it doesn't use velocity information. But I don't actually know of any better approach. Sorry! – Chris Culter Aug 03 '13 at 00:09
  • Why doesn't a matched filter work? – AnonSubmitter85 Aug 03 '13 at 00:30
  • @AnonSubmitter85: Thanks. A quick Wikipedia view tells me it is logically possible to apply the concept here but I'm afraid without some guidance, I will not be able to implement it. What I can tell you is that the template path will have just enough points to allow users to draw a recognizable path. While the data to be matched will be sampled 30 times a second (video processing) and will have varying noise due to occlusion and other factors. Is this something you could help with? – Raheel Khan Aug 03 '13 at 02:54
  • 1
    You could also try the Hausdorff distance, which is much easier to implement (here's pseudocode, though it needs modification to work for non-convex polygons). The main difference is that the Fréchet distance considers backtracking, so if I go back and forth on some part of the path, it increases my Fréchet distance but not my Hausdorff distance to the path. –  Aug 03 '13 at 04:44
  • Thanks @RahulNarain: Since you mention non-convex, I assume you mean closed paths. Would this work on open paths (where the start and end do not meet)? – Raheel Khan Aug 04 '13 at 08:12
  • 1
    Sure, the Hausdorff distance is incredibly general. It works for closed polygons, open paths, filled shapes, and in fact arbitrary sets of points. The only computational primitive you need is to be able to compute $d(x,Y)$, the distance from an arbitrary point $x$ in the plane to its nearest point on a shape $Y$. –  Aug 04 '13 at 08:34

0 Answers0