Problem: I have two overlapping 2D shapes, A and B, each shape having the same number of pixels, but differing in shape. Some portion of the shapes are overlapping, and there are some pieces of each that are not overlapping. My goal is to move all the non-overlapping pixels in shape A to the non-overlapping pixels in shape B. Since the number of pixels in each shape is the same, I should be able to find a 1-to-1 mapping of pixels. The restriction is that I want to find the mapping that minimizes the total distance traveled by all the pixels that moved.
问题:我有两个重叠的2D形状,A和B,每个形状具有相同的像素数,但形状不同。形状的一些部分是重叠的,并且每个形状的一些部分不重叠。我的目标是将形状A中的所有非重叠像素移动到形状B中的非重叠像素。由于每个形状中的像素数相同,我应该能够找到1对1的映射像素。限制是我想找到最小化所有移动像素行进的总距离的映射。
Brute Force: The brute force approach to solving this problem is obviously out of the question, since I would have to compute the total distance of all possible mappings of which I think there are n! (where n is the number of non-overlapping pixels in one shape) times the computation of calculating a distance for each pair of points in the mapping, n, giving a total of O( n * n! ) or something similar.
蛮力:解决这个问题的蛮力方法显然是不可能的,因为我必须计算所有可能的映射的总距离,我认为有n个! (其中n是一个形状中非重叠像素的数量)乘以计算映射中每对点的距离n的计算,给出总共O(n * n!)或类似的东西。
Backtracking: The only "better" solution I could think of was to use backtracking, where I would keep track of the current minimum so far and at any point when I'm evaluating a certain mapping, if I reach or exceed that minimum, I move on to the next mapping. Even this won't do any better than O( n! ).
回溯:我能想到的唯一“更好”的解决方案是使用回溯,我将跟踪目前的最小值,在任何时候,当我评估某个映射时,如果我达到或超过该最小值,我继续下一个映射。即使这样做也不会比O(n!)更好。
Is there any way to solve this problem with a reasonable complexity?
有没有办法以合理的复杂性解决这个问题?
Also note that the "obvious" approach of simply mapping a point to it's closest matching neighbour does not always yield the optimum solution.
还要注意,简单地将一个点映射到它最接近的匹配邻居的“明显”方法并不总能产生最佳解决方案。
Simpler Approach?: As a secondary question, if a feasible solution doesn't exist, one possibility might be to partition each non-overlapping section into small regions, and map these regions, greatly reducing the number of mappings. To calculate the distance between two regions I would use the center of mass (average of the pixel locations in the region). However, this presents the problem of how I should go about doing the partitioning in order to get a near-optimal answer.
更简单的方法?:作为次要问题,如果不存在可行的解决方案,一种可能性可能是将每个非重叠区域划分为小区域,并映射这些区域,从而大大减少映射的数量。为了计算两个区域之间的距离,我将使用质心(该区域中像素位置的平均值)。然而,这提出了我应该如何进行分区以获得接近最佳答案的问题。
Any ideas are appreciated!!
任何想法都赞赏!!
3 个解决方案
#1
This is the Minimum Matching problem, and you are correct that it is a hard problem in general. However for the 2D Euclidean Bipartite Minimum Matching case it is solvable in close to O(n²) (see link).
这是最小匹配问题,你是正确的,一般来说这是一个难题。然而,对于2D Euclidean Bipartite最小匹配情况,它可以接近O(n²)求解(见链接)。
For fast approximations, FryGuy is on the right track with Simulated Annealing. This is one approach.
对于快速近似,FryGuy采用模拟退火处于正确的轨道上。这是一种方法。
Also take a look at Approximation algorithms for bipartite and non-bipartite matching in the plane for a O((n/ε)^1.5*log^5(n)) (1+ε)-randomized approximation scheme.
还要看一下O((n /ε)^ 1.5 * log ^ 5(n))(1 +ε) - 随机近似方案的平面中的二分和非二分匹配的近似算法。
#2
You might consider simulated annealing for this. Start off by assigning A[x] -> B[y] for each pixel, randomly, and calculate the sum of squared distances. Then swap a pair of x<->y mappings, randomly. Then choose to accept this with probability Q, where Q is higher if the new mapping is better, and tends towards zero over time. See the wikipedia article for a better explanation.
您可以考虑模拟退火。首先为每个像素随机分配A [x] - > B [y],然后计算平方距离之和。然后随机交换一对x < - > y映射。然后选择以概率Q接受这个,其中如果新映射更好则Q更高,并且随着时间趋向趋于零。有关更好的解释,请参阅*文章。
#3
- Sort pixels in shape A: in increasing order of 'x' and then 'y' ordinates
- Sort pixels in shape B: in decreasing order of 'x' and then increasing 'y'
对形状A中的像素进行排序:按“x”的递增顺序排列,然后按“y”纵向排序
对形状B中的像素进行排序:按'x'的降序排列,然后增加'y'
Map pixels at the same index: in the sorted list the first pixel in A will map to first pixel in B. Is this not the mapping you are looking for?
映射相同索引处的像素:在排序列表中,A中的第一个像素将映射到B中的第一个像素。这不是您要查找的映射吗?
#1
This is the Minimum Matching problem, and you are correct that it is a hard problem in general. However for the 2D Euclidean Bipartite Minimum Matching case it is solvable in close to O(n²) (see link).
这是最小匹配问题,你是正确的,一般来说这是一个难题。然而,对于2D Euclidean Bipartite最小匹配情况,它可以接近O(n²)求解(见链接)。
For fast approximations, FryGuy is on the right track with Simulated Annealing. This is one approach.
对于快速近似,FryGuy采用模拟退火处于正确的轨道上。这是一种方法。
Also take a look at Approximation algorithms for bipartite and non-bipartite matching in the plane for a O((n/ε)^1.5*log^5(n)) (1+ε)-randomized approximation scheme.
还要看一下O((n /ε)^ 1.5 * log ^ 5(n))(1 +ε) - 随机近似方案的平面中的二分和非二分匹配的近似算法。
#2
You might consider simulated annealing for this. Start off by assigning A[x] -> B[y] for each pixel, randomly, and calculate the sum of squared distances. Then swap a pair of x<->y mappings, randomly. Then choose to accept this with probability Q, where Q is higher if the new mapping is better, and tends towards zero over time. See the wikipedia article for a better explanation.
您可以考虑模拟退火。首先为每个像素随机分配A [x] - > B [y],然后计算平方距离之和。然后随机交换一对x < - > y映射。然后选择以概率Q接受这个,其中如果新映射更好则Q更高,并且随着时间趋向趋于零。有关更好的解释,请参阅*文章。
#3
- Sort pixels in shape A: in increasing order of 'x' and then 'y' ordinates
- Sort pixels in shape B: in decreasing order of 'x' and then increasing 'y'
对形状A中的像素进行排序:按“x”的递增顺序排列,然后按“y”纵向排序
对形状B中的像素进行排序:按'x'的降序排列,然后增加'y'
Map pixels at the same index: in the sorted list the first pixel in A will map to first pixel in B. Is this not the mapping you are looking for?
映射相同索引处的像素:在排序列表中,A中的第一个像素将映射到B中的第一个像素。这不是您要查找的映射吗?