align one set of 2d points with another using only translation and rotation

Question

I'm working in OpenCV but I don't think there is a function for this. I can find a function for finding affine transformations, but affine transformations include scaling, and I only want to consider rotation + translation.

Imagine I have two sets of points in 2d - let's say each set has exactly 50 points.

E.g. set A = {x1, y1, x2, y2, ... , x50, y50}

set B = {x1', y1', x2', y2', ... , x50', y50'}

I want to find the rotation and translation combination that gets closest to mapping set A onto set B. I guess I would define "closest" as minimises the average distance between points in A and corresponding points in B. I.e., minimises the average distance between (x1, y1) and (x1', y1'), etc.

I guess I could use brute force testing all possible translations and rotations but this would be extremely inefficient. Does anyone know a simpler way?

Thanks!

Answer 1

This problem has a very elegant solution in terms of singular value decomposition of the proximity matrix (distances between pairs of points). The name of this is the orthogonal Procrustes problem, after the Greek legend about a fellow who offered travellers a bed that would fit anyone.

The solution comes from finding the nearest orthogonal matrix to a given (not necessarily orthogonal) matrix.

Answer 2

The way I would do it in Excel is to make a couple columns representing the points. Cells representing rotation/translation of a set (no need to rotate and translate both of them). Then columns representing those same points rotated/translated.
Then another column for the distance between the points of the rotated/translated points.
Then a cell of the sum of the distances between points. Finally, use Solver to optimize the rotation and translation cells.

Answer 3

If you fix some rotation you can get an answer using ternary search. Run search in x and for every tested x run it in y to get the best value. This will give you the correct answer since the function (sum of corresponding distances) is convex (this can be proved through observing that restriction of the function to any line is a one-dimensional convex function; and the last is a standard fact: the sum of several convex functions is convex). Instead of brute force over the angle I can propose such a method based on the ternary search. Choose some not very large step S. Compute the target function for every angle in (0, S, 2S,...). Then, if S is small enough, we can exclude some of segments (iS, (i + 1)S) from consideration. Namely ones with relatively large values of function with angles iS and (i + 1)S. Being implemented carefully this can give an answer and can do it faster than brute force.