TransWikia.com

Transforming data points to match other data points

Data Science Asked by jazzchipc on March 14, 2021

I have two sets of data points, set A and set B.

Each point of both sets has two dimensions $(x, y)$.

Consider the set $A$ to be the orange set on the left of the image below and $B$ to be the blue on the right (some points are more transparent, because the points represent a position over time; the darker the point, the more recent is the position it represents).

Data sets

I can observe that there is a similarity between both sets. If I perform some rotation and scaling to set $B$, I end up with a set $B’$ more similar to set $A$.

My question is, what method can I used to find the transformation that makes set $B$ as similar to $A$ as possible? And how can I measure the similarity?

I do not need a programming solution, just some tips on possibly existing algorithms.

If there is no easy solution, I’d like to know if there is some designation for this type of problem or some keywords that could point me in the right direction.

Thanks!

2 Answers

For this task, you need to decide 3 things:

(1) What are the allowed transformations.

For example do you allow an arbirtrary affine transformation (rotation, scaling, translation). Then you need a matrix $f in mathbb{R}^{3 times 3}$ (using homogeneous coordinates) that maps the points from the left image to the right one. Each entry of the matrix is a variable you want to determine. You could also restrict to specific affine maps (e.g. only rotations) by setting certain entries in $mathbf{A}$ fixed.

In principle you can use any map $f_{w}: mathbb{R}^{2 times 2} rightarrow mathbb{R}^{2 times 2}$, that depends on some variables $w$.

(2) You need to think about a measure (or "loss"), which evaluates how similar the two sets are. For arbitrary sets, there is the Hausdorff distance, which ignores any temporal information. If you consider your data as two curves over time, there is the Frechet distance. You can have a look here to see that its a difficult problem to using the Haussdorf distance in general. In fact, computing only the Hausdorff distance, without any optimization is already not trivial. However, for polygonal curves, you can compute Hausdorff distance, Frechet distance, and discrete Frechet distance efficiently.

Finally, in your specific case, you have for each point of $A$ a corresponding point in $B$, you can measure the distance for each correspondence (this gives you simply the mean squared errors in $mathbb{R}^{2}$).

(3) Depending on the choice of (1) and (2), you need to employ a corresponding optimizer.

If you want to minimize the pairwise distance, but you do not have the correspondences available, there is the Iterative closest point. If you simple compute the distance between corresponding points, you have a non-linear optimization problem. You can use solvers such as Levenberg–Marquardt.

As @bogovicj points out, the topic is called point-set registration.

Answered by Graph4Me Consultant on March 14, 2021

Dynamic Time Warping measures the similarity between two sequences of values across time. It combines the idea of comparing a pair of points $(ain A,bin B)$ with the idea of finding the optimal alignment of points $(a,b)$ between the two sequence. The alignment algorithm is similar to the edit distance between strings, and can be used to extract a mapping between the sequences.

Answered by Erwan on March 14, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP