问题:我有两个重叠的2D形状,A和B,每个形状具有相同的像素数,但形状不同.形状的一些部分是重叠的,并且每个形状的一些部分不重叠.我的目标是将形状A中的所有非重叠像素移动到形状B中的非重叠像素.由于每个形状中的像素数相同,我应该能够找到1对1的映射像素.限制是我想找到最小化所有移动像素行进的总距离的映射.
蛮力:解决这个问题的蛮力方法显然是不可能的,因为我必须计算所有可能的映射的总距离,我认为有n个!(其中n是一个形状中的非重叠像素的数量)乘以计算映射中每对点的距离n的计算,给出总的O(n*n!)或类似的东西.
回溯:我能想到的唯一"更好"的解决方案是使用回溯,我会跟踪当前的最小值,在我评估某个映射的任何时候,如果我达到或超过该最小值,我继续下一个映射.即使这样做也不会比O(n!)更好.
有没有办法以合理的复杂性解决这个问题？
还要注意,简单地将一个点映射到它最接近的匹配邻居的"明显"方法并不总能产生最佳解决方案.
更简单的方法？:作为次要问题,如果不存在可行的解决方案,一种可能性可能是将每个非重叠部分划分为小区域,并映射这些区域,从而大大减少映射的数量.为了计算两个区域之间的距离,我将使用质心(该区域中像素位置的平均值).然而,这提出了我应该如何进行分区以获得接近最佳答案的问题.
任何想法都赞赏!!
这是最小匹配问题,你是正确的,一般来说这是一个难题.然而,对于2D Euclidean Bipartite最小匹配情况,它可以接近O(n²)求解(见链接).
对于快速近似,FryGuy采用模拟退火处于正确的轨道上.这是一种方法.
还要看一下O((n /ε)^ 1.5*log ^ 5(n))(1 +ε) - 随机近似方案的平面中的二分和非二分匹配的近似算法.
京公网安备 11010802040832号 | 京ICP备19059560号-6 