7 replies to this topic

[radu]

Hi you all

I am trying to find a metric between 2 bezier courves that would tell me how similar they are. I am interested for the moment in cubic Beziers.

For example, if I have P(t) and Q(t) described each by four control points P0, P1, P2, P3 and Q0, Q1, Q2, Q3, I would like a metric M(P, Q) that will output for example a value between 0 and infinity, 0 meaning exact match.

What I can think of is (P0-Q0)^2 + (P1-Q1)^2 + (P2-Q2)^2 + (P3-Q3)^2 but it is just an initial guess so it is not that good.

Looking forward for your answers :)
radu

[Reedbeta]

Euclidean distance in the coefficient space of the polynomials (i.e. what you have) should work fine for a heuristic, and is easy to calculate. Just be careful that if you are using rational Bezier curves, you could have two curves that are scalar multiples and project to the same curve in real space. Also, you may want to take into account that the curves described by (P0, P1, P2, P3) and (P3, P2, P1, P0) are the same but with opposite orientation.

[SigKILL]

The scientific standard for measuring distance between any set (including curves) is the hausdorff metric. Using a discrete version of this should suffice (if you´re studying the approximation rate when the distance between controlpoints tends to zero you need to be careful). The good thing about this is that it gives you a metric based on the geometric properties instead of the algebraic properties (read coefficients) of the curve.

-si

[Reedbeta]

The Hausdorff metric sounds like it would take much longer to compute - something like O(N^2) where N is the number of times you choose to subdivide each curve. You would find the distance from each point on curve A to the closest point on curve B, and then take the maximum of these distances.

[SigKILL]

Well, if you use a discrete version of the hausdorff metric using n points on both curves you would most likely end up with something that are 2n^2.

[Reedbeta]

That's indeed O(N^2)

[radu]

Hi guys

Thank you for your answers, really appreciate it.

Thanks Reedbeta for the opposite observation, you are right. Thinking more, I believe I have to extend the orientation to translation and rotation invariance too. What I mean is 2 curves, the 2nd that gets obtained from the 1st using a PI/3 rotation for example are actually the same, except for the rotation. Hence the metric’s output should also be 0.

I have looked a bit into the Haussdorf distance and it looks like it gives me one measure only, the max distance between the N + N points that I pick on the 2 curves. That will indeed give me a value of 0 for 2 identical curves but it involves a bit of hassles:
- O(N^2) is a bit expensive as N should be quite large in order for my metric to be eps accurate and I need to do this real time
- I am not sure it is a good measure for what I’m looking for?

Ok, I have progressed a bit, I am first doing a translation of the 2nd curve so that their 1st points would match then do a rotation of the 2nd + scale so that their 2nd points match. This works for 2D but I am a bit lost for 3D? Any ideas here? Thanks

radu

[Reedbeta]

Oh - I didn't realize you wanted to test against the shape of the curves, so that curves differing by a rigid motion would be the same. In that case, you can calculate the curvature and torsion of the 3D curve - these are functions k(t) and tau(t) that define the curve's shape independent of its position/orientation in 3D space. I'm not sure, but I think the curvature and torsion of a Bezier spline might be another Bezier spline, or at least a quotient of two Bezier splines, and so you may be able to just calculate the control points for the curvature and torsion curves and then use a Euclidean metric between them (although you'd still have to take into account the ordering issue). Anyway, google for the definitions of curvature and torsion.