Problem:我有两个重叠的 2D 形状，A 和 B，每个形状具有相同数量的像素，但形状不同。形状的某些部分是重叠的，而每个形状的某些部分是不重叠的。我的目标是将形状 A 中的所有不重叠像素移动到形状 B 中的不重叠像素。由于每个形状中的像素数量相同，所以我应该能够找到 1 对 1 的映射像素。限制是我想找到最小化所有移动像素移动的总距离的映射。
蛮力：解决这个问题的蛮力方法显然是不可能的，因为我必须计算所有可能的映射的总距离，我认为其中有 n！ （其中 n 是一个形状中不重叠像素的数量）乘以计算映射中每对点的距离的计算量 n，总共为 O( n * n! ) 或类似的值。
回溯：我能想到的唯一“更好”的解决方案是使用回溯，我会跟踪到目前为止的当前最小值，并且在评估某个映射时的任何时候，如果我达到或超过该最小值，我会继续前进到下一个映射。即使这样也不会比 O(n!) 更好。
有没有办法以合理的复杂度来解决这个问题？
另请注意，简单地将点映射到其最接近的匹配邻居的“明显”方法并不总是能产生最佳解决方案。
更简单的方法？：作为第二个问题，如果不存在可行的解决方案，一种可能是将每个不重叠的部分划分为小区域，并对这些区域进行映射，从而大大减少映射的数量。为了计算两个区域之间的距离，我将使用质心（该区域中像素位置的平均值）。然而，这提出了我应该如何进行分区以获得接近最佳答案的问题。
任何想法表示赞赏！
这就是最小匹配问题，你是对的，这通常是一个难题。然而对于二维欧氏二分最小匹配 http://maven.smith.edu/~orourke/TOPP/P6.html在这种情况下，它可以在接近 O(n²) 的时间内解决（请参阅链接）。
对于快速近似，FryGuy 的模拟退火走在正确的轨道上。这是一种方法。
还看一下平面内二分和非二分匹配的近似算法 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.8281对于 O((n/ε)^1.5*log^5(n)) (1+ε)-随机近似方案。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
