匹配点集的算法 [英] Algorithm for matching point sets

问题描述

我有两组积分 A 和 B ，而积分可以是2D或3D。两组的尺寸相同（ n ），这是相当低的（5 - 20）。

我想知道这些组合如何。也就是说，理想情况下，我会找到点之间的配对，使得所有欧几里德对距离之和 d（A，B）最小。所以

d（A，B）= \ sum_ {i = 1} ^ n || A_i - B_i || _2

最终结果用于与其他点集进行比较。因此，例如：

• A =（1,1），（1,2），（1,3）

B =（1,1），（2,2），（1,3）

给我 d（A，B）= 1 。

• C =（1 ，1），（2,1），（3,1）
  D =（2,1），（2,2），（3,1）





会给我 d（C，D）= 1.414 。





任何好主意？

您可以将您的问题建模为作业问题（），您可以在其中定义分配点A_i的成本C_ij（从集合A）到B_j（从集合B）到等于它们之间的距离。然后可以使用匈牙利算法（）解决此分配问题。



I have two sets of points A and B, whereas the points can be 2D or 3D. Both sets have the same size n, which is rather low (5 - 20).

I would like to know how well these sets agree. That is, ideally I would find pairings between the points such that the sum of all Euclidean pair distances d(A,B) is minimal. So

d(A,B) = \sum_{i=1}^n ||A_i - B_i||_2

The final outcome is used to compare with other point sets. So, for example:

• A = (1,1), (1,2), (1,3)
• B = (1,1), (2,2), (1,3)

would give me d(A,B) = 1.

• C = (1,1), (2,1), (3,1)
• D = (2,1), (2,2), (3,1)

would give me d(C,D) = 1.414.

Any good ideas?

解决方案

You can for example model your problem as an assignment problem (Wikipedia link), where you define the cost C_ij of assigning point A_i (from set A) to point B_j (from set B) to be equal to the distance between them. This assignment problem can then be solved using the Hungarian algorithm (Wikipedia link).

这篇关于匹配点集的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！