Similarity measures between curves?

Question

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%.

Answer 1

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.

Relevant reading:

• Curve Matching, Time Warping, and Light Fields: New Algorithms for Computing Similarity between Curves
• Discovering Similar Multidimensional Trajectories (uses the LCSS for robustness)

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.

Answer 2

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.

Answer 3

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.

Answer 4

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||\}$.

Answer 5

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.