代码之家 › 专栏 › 技术社区 › MahlerFive

需要更好的算法来查找具有最小距离的两组点之间的映射

mathematical-optimization mapping math algorithm image

MahlerFive · 技术社区 · 17 年前

我有两个重叠的2D形状,A和B,每个形状有相同数量的像素,但形状不同。形状的某些部分是重叠的,每个形状的某些部分是不重叠的。我的目标是将形状A中的所有非重叠像素移动到形状B中的非重叠像素。由于每个形状中的像素数量相同,我应该能够找到像素的1:1映射。限制是我想找到使所有移动像素的总移动距离最小化的映射。

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

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

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

更简单的方法

任何想法都很感激!!

3 回复 | 直到 12 年前

Imran 17 年前

这是最小匹配问题,您是正确的,它通常是一个困难的问题。但是对于 2D Euclidean Bipartite Minimum Matching 在接近O(n)的情况下它是可解的(见链接)。

对于快速近似,FryGuy的模拟退火方法是正确的。这是一种方法。

也来看看 Approximation algorithms for bipartite and non-bipartite matching in the plane 对于O((n/)^1.5*log^5(n))(1+)随机近似方案。

FryGuy 17 年前

simulated annealing 为了这个。首先分配一个[x]->B[y]为每个像素,随机,并计算平方距离之和。然后交换一对x<-&燃气轮机;y映射,随机。然后选择接受概率Q,如果新映射更好,则Q更高,并且随着时间的推移趋于零。有关更好的解释,请参阅维基百科文章。

-1

Sesh 17 年前

对形状A中的像素排序:按“x”坐标和“y”坐标的递增顺序

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

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

2 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

2 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

2 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

2 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

2 年前