Recognizing a trajectory from a set

Question

Given a set of 2d trajectories/paths, where a trajectory is a list of [x,y,time] coordinates, and a new trajectory, how can I recognize which one in the set is most similar to it? The lists may not be of the same length, the time differences not the same.

I've tried using perceptual image hashes of the resulting lines, but this approach seems unreliable.

The measure of similarity should be scale and translation, but not rotation invariant.

I'm trying to recognize 2d gestures that are input with a mouse or touchpad in order to execute commands[0]. For this application, the velocity/acceleration of the movement will not matter.

I found this library that contains a few algorithms: https://github.com/bguillouet/traj-dist

[0] https://github.com/void4/termagic

Answer 1

The Fréchet distance is a similarity measure for trajectories that often works well for curves that we consider visually similar. However, it is not scale or translation invariant, because it compares the distances between the points of the trajectories.

You can try the Direction-Based Fréchet Distance, introduced in this paper by de Berg and Cook. This is a variant of the Fréchet distance that is based on the directions of movement instead of the points directly. This means that it is both scale invariant and translation invariant, but not rotation invariant.

---

Another possible approach that may be easier to implement if you have a library that can compute Fréchet distance and DTW¹ distance between a pair of trajectories, is to first translate the pair of trajectories such that the first points have the same position, and then scale the trajectories such that the distance between the first and last point of the trajectories is the same in both trajectories. If you compute either the Fréchet distance or DTW-distance after these transformations, the total measure will be scale and translation invariant.

_{1: DTW (Dynamic time warping) is similar to the Fréchet distance, the main difference is that the Fréchet distance is a bottleneck measure, while DTW is not. In other words, only the 'most dissimilar parts' of the trajectories determine the Fréchet distance, while DTW takes the entire trajectory into account.}