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.