10

问题：我有两个重叠的 2D 形状，A 和 B，每个形状具有相同数量的像素，但形状不同。形状的某些部分是重叠的，并且每个形状都有一些不重叠的部分。我的目标是将形状 A 中的所有非重叠像素移动到形状 B 中的非重叠像素。由于每个形状中的像素数相同，我应该能够找到 1 对 1 的映射像素。限制是我想找到最小化所有移动像素行进的总距离的映射。

蛮力：解决这个问题的蛮力方法显然是不可能的，因为我必须计算我认为有 n 的所有可能映射的总距离！（其中 n 是一个形状中的非重叠像素的数量）乘以计算映射中每对点的距离的计算，n，总共得到 O(n * n!) 或类似的东西。

回溯：我能想到的唯一“更好”的解决方案是使用回溯，我将在其中跟踪当前的最小值，并且在我评估某个映射时的任何时候，如果我达到或超过该最小值，我继续下一个映射。即使这样也不会比 O(n!) 做得更好。

有没有办法以合理的复杂性解决这个问题？

另请注意，简单地将一个点映射到它的最近匹配邻居的“明显”方法并不总是产生最佳解决方案。

更简单的方法？：作为次要问题，如果不存在可行的解决方案，一种可能性可能是将每个不重叠的部分划分为小区域，并映射这些区域，从而大大减少映射的数量。为了计算两个区域之间的距离，我将使用质心（区域中像素位置的平均值）。但是，这提出了我应该如何进行分区以获得接近最佳答案的问题。

任何想法表示赞赏！

4

3 回答 3

9

这是最小匹配问题，你说得对，一般来说这是一个难题。然而，对于2D 欧几里得二分最小匹配情况，它可以在接近 O(n²) 的情况下求解（参见链接）。

对于快速近似，FryGuy 在模拟退火方面走在了正确的轨道上。这是一种方法。

另请查看O((n/ε)^1.5*log^5(n)) (1+ε) 随机近似方案的平面中二分和非二分匹配的近似算法。

于 2009-02-15T09:51:41.563 回答
5

您可以考虑为此进行模拟退火。首先为每个像素随机分配 A[x] -> B[y]，然后计算距离平方和。然后随机交换一对 x<->y 映射。然后选择以概率 Q 接受这个，如果新映射更好，Q 会更高，并且随着时间的推移趋向于零。请参阅维基百科文章以获得更好的解释。

于 2009-02-15T09:42:19.650 回答
-1
  1. 对形状 A 中的像素进行排序：按“x”和“y”坐标的升序排列
  2. 对形状 B 中的像素进行排序：按 'x' 的递减顺序，然后增加 'y'

在同一索引处映射像素：在排序列表中，A 中的第一个像素将映射到 B 中的第一个像素。这不是您要查找的映射吗？

于 2009-02-15T09:43:26.810 回答