仅使用平移和旋转将一组 2d 点与另一组 2d 点对齐
我正在 OpenCV 中工作，但我认为没有这方面的功能。我可以找到一个用于查找仿射变换的函数，但是仿射变换包括缩放，而我只想考虑旋转+平移。
想象一下，我有两组 2d 点 - 假设每组恰好有 50 个点。
例如设置 A = {x1, y1, x2, y2, ... , x50, y50}
设置 B = {x1', y1', x2', y2', ... , x50', y50'}
我想要找到最接近将集合 A 映射到集合 B 的旋转和平移组合。我想我会将“最接近”定义为最小化 A 中的点与 BIe 中对应点之间的平均距离，最小化(x1, y1) 和 (x1', y1') 之间的平均距离等。
我想我可以使用强力测试所有可能的平移和旋转，但这会非常低效。有谁知道更简单的方法吗？
谢谢！
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!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这个问题在邻近矩阵（点对之间的距离）的奇异值分解方面有一个非常优雅的解决方案。这个问题的名字是正交普罗克拉斯特斯问题，源自希腊传说，讲述的是一个为旅行者提供了适合任何人的床。
解决方案来自于找到与给定（不一定是正交）矩阵最接近的正交矩阵。
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.
我在 Excel 中执行此操作的方法是制作几列来表示点。
代表一组旋转/平移的单元格（不需要旋转和平移它们）。
然后代表这些相同点的列被旋转/平移。
然后另一列表示旋转/平移点之间的距离。
然后是点之间距离总和的单元格。
最后，使用 Solver 优化旋转和平移单元。
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.
如果您修复了一些旋转，您可以使用三元搜索获得答案。在 x 中运行搜索，并针对每个测试的 x 在 y 中运行搜索以获得最佳值。这将为您提供正确的答案，因为函数（相应距离的总和）是凸函数（这可以通过观察函数对任何直线的限制是一维凸函数来证明；最后一个是标准事实：几个凸函数的和是凸的）。
我可以提出一种基于三元搜索的方法，而不是对角度进行暴力破解。选择一些不是很大的步长 S。计算 (0, S, 2S,...) 中每个角度的目标函数。然后，如果 S 足够小，我们可以从考虑中排除一些段 (iS, (i + 1)S)。即具有角度 iS 和 (i + 1)S 的函数值相对较大的函数。仔细实施，这可以给出答案，并且可以比暴力更快地完成。
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.