Similarity measures between curves?

I would like to compute the measure of similarity between two ordered sets of points---the ones under User compared with the ones under Teacher:

The points are curves in 3D space, but I was thinking that the problem is simplified if I plotted them in 2 dimensions like in the picture. If the points overlap, similarity should be 100%.

-
Do you need to account for scaling, rotation and/or translation? –  nico May 6 '12 at 7:54
No, I don't need to take them into account. –  Alex May 7 '12 at 14:04
meaning that I will apply take care of that. –  Alex May 7 '12 at 14:15

You are comparing trajectories, or curves. This is a studied topic. Procrustes analysis and dynamic time warping, as EMS says, are tools of the trade. Once you've aligned the curves you'll want to measure the distance, say the Fréchet distance. If you want to share some of your data we could take a crack at it ourselves.

If you disregard the temporal dimension:

You could fit the User and Teacher to multivariate Gaussian densities and find the volume of their product--that's pretty easy. If you want more accuracy, you could use a nonparametric density estimate instead.

-
Thank you Emre for your suggestion! I have updated the problem - I think it may be simpler now so please have a look. –  Alex May 7 '12 at 14:13
You could fit the User and Teacher to multivariate Gaussian densities and find the volume of their product--that's pretty easy Could you please kindly point me to the correct resources to learn this? Really newbie here. –  Farticle Pilter Sep 6 '13 at 14:45

You might consider Procrustes distance, or some distance based on dynamic time warping (even if one of your dimensions is not "time" per se, you can still use this transformation idea). See this recent work on Tracklets for an illustrative use case of dynamic time warping for measuring similarity between 3D space curves carved out by point trajectories in videos.

There are many libraries with built-in Procrustes distance calculations, such as Matlab, or the PyGeometry library for Python.

-

The original post asked for a metric between ORDERED points in 3D. The only such metric is the Frechet distance. There was no mention of time as one of the dimensions, so I would assume that all the dimensions have units of distance (i.e. the units are not mixed). This can be done by modifying a function recently uploaded to the MathWorks file exchange (Frechet distance calculation: http://www.mathworks.com/matlabcentral/fileexchange/38714). These routines were written for points in the plane, but the extension to 3D points is straightforward.

-
Are you sure the Frechet distance is between ordered pairs? the wikipedia page says that a point in one path can be matched to multiple points in another. Also, surely there is more than one such metric. What about the sum of the distances between ordered pairs? –  naught101 Oct 31 '12 at 23:09

Hausdorff Distance might be what you are looking for. Hausdorff Distance between two point sets $X$ and $Y$ is defined as, $d_H(X, Y) = \max \{\sup_{x \in X} \inf_{y \in Y} ||x - y||, \sup_{y \in Y} \inf_{x \in X} ||x - y||\}$.

-
I don't think this is a very tractable approach. Unless you mean to approximate this by replacing all of the $\sup$ and $\inf$ with $\max$ and $\min$.. but Hausdorff distance won't be well approximated by these in many cases. How do you propose to actually compute (in software) such distances? –  EMS May 7 '12 at 17:37
@EMS There are two ways to go about this, 1. either consider $X$ and $Y$ as discrete point sets, makes things simpler 2. or try to come up with some form of convex hull for each point set (not quite sure whether this is necessary) and something like [this][1] could be used to approximately compute the distance. [1]: cg.cs.uni-bonn.de/aigaion2root/attachments/guthe-2005-fast.pdf –  TenaliRaman May 7 '12 at 18:21
Thank you for the link, I had only seen Hausdorff distance in computer vision in Tony Chan's book. It's cool to see more computational approaches. –  EMS May 7 '12 at 19:13

Similarity is quantity that reflects the strength of relationship between two objects or two features. This quantity is usually having range of either -1 to +1 or normalized into 0 to 1. Than you need to calculate the distance of two features by one of the methods below:

1. Simple Matching distance
2. Jaccard's distance
3. Hamming distance
4. Jaccard's coefficient
5. simple matching coefficient

For line... you can represent it by angle (a) and length (l) properties or L1= P1(x1,y1), P2(x2,y2) below is the similarity with a and l.

now measure the angle for angles and lengths

• A_user =20 and Length_User =50
• A_teacher30 and Length_Teacher =55
• Now, normalize the values.

Using euclidean distance

similarity = SquareRoot((A_user - A_teacher30 )^2 +(Length_User - Length_Teacher )^2)

gives the similarity measure. You can also use above mentioned methods based on the problem and the features.

-