1

我需要按距离将蓝色物体映射到红色物体。每个对象的中心是已知的。黄色和绿色对象（如果显示）是提示。它们有助于确定哪个红色物体更重要。

例如，在下图所示的情况下：

  • 底部的蓝色对象应该映射到最右下方的红色对象，因为绿色和黄色对象都非常靠近那个红色对象。
  • 右边的蓝色对象应该映射到右上角的红色对象，因为它更靠近它。


在此处输入图像描述

我有一个天真的解决方案，但我不太确定该怎么做而不是“？？？？” 以下

你有什么建议吗？

我在某种伪代码中的天真解决方案：

for each BLUE:
   find group P=(YELLOW_BLUE, GREEN_BLUE and RED_BLUE) when each object in P is the closest to BLUE
   vector<RED> redCandidates
   for each O in P:
       if O is YELLOW OR O is GREEN
          find closest RED to O 
          insert RED to redCandidates

   if size of redCandidates is 0 -> return RED_BLUE
   else if size of redCandidates is 1 -> return redCandidates[0] since hint has more weight to the decision
   else if size of redCandidates is > 1 -> ????

UPDATE1
在研究了@ldog 建议的最小成本流问题后，我决定使用Hungarian Algorithm。我创建了二分图，其中每个蓝色节点都连接到每个红色节点，边上的权重是蓝色和红色之间的距离。 现在，在我解决图表之前，我需要在黄色/绿色接近红色的边缘上应用奖励。我不太明白该怎么做。 假设蓝色 1 和红色 4 之间的距离是 D_1_4 = 10，黄色提示 11 和红色 4 之间的距离是 D_4_11 = 3。那么，因为 D_1_4 > D_4_11，我应该只在边 1_4 上添加奖励吗？或者，我应该将奖励添加到进入节点 4 的每条边，即边 1_4、2_4 和 3_4？在此处输入图像描述

4

1 回答 1

1

看来您的问题尚未完全形成，您正在寻找用文字表达的东西的体面表述。

以下是一些建议：

  1. 使用交集而不是联合来处理如何为重叠区域分配相似性。
  2. 有很多方法可以尝试使你用文字表达的内容量化，从而能够进行优化。量化您用文字表达的内容的一种合理方法是我将在下面讨论的最小化问题。

最小化应该将一个蓝色框分配给一个红色框（根据您告诉我的内容。）绿色和黄色框是提示，不包含在此约束中，它们仅用于修改哪个红色框优先于其他框。为了形式化您用文字描述的内容，我们有一组红色框R和一组蓝色框B。有m红框和n蓝框m >= n。i蓝框和红框的每一对j都有一个偏好w_{ij}（这个偏好是预先计算的，考虑到提示框以及空间接近度。）

我们希望计算：

           max \sum_{i<j} w_{ij}x_{ij}
 such that 
           \sum_{k} x_{ik} = 1, \sum_{l} x_{lj} = 1, x_{ik} \in {0,1}

x_{ij}当且仅当将蓝色框i分配给红色框时，该变量为 1 j，否则为 0。

这个问题（完全是单模的）并且可以在多项式时间内解决。事实上，它可以作为常见的最小成本流问题的一个实例来解决。为此，请在图中为每个蓝色框定义一个节点i，并在图中为每个红色框定义一个节点j。使用权重和容量为 1 的边将每个蓝色节点连接到每个红色节点（有向蓝色->红色）。使用-w_{ij}容量为 1 和权重 0 的边将每个蓝色节点连接到源（有向源->蓝色）。连接每个红色节点到接收器（有向红色->接收器），边缘容量为 1，权重为 0。给源一个供应量n，给接收器一个需求量n。计算此图上的最小成本流（参见例如柠檬) 和由此产生的流量产生最大的解决方案（或者最小的流量。）

在详细描述了这一点之后，我发现这已经是一种常见的方法 [1] 来解决像您这样的问题。这是一个实现。

YMMV 取决于你的重量有多好。您可能想尝试一种机器学习方法，以使用地面实况数据集和迭代细化来确定最佳权重。可以通过细化权重来计算一组固定的蓝色和红色基础实况框的细化，w_{ij}直到除基础实况之外的所有其他可能分配的优化分数低于基础实况。这可以使用任何最大边距学习框架或技术迭代完成，并结合我上面描述的方法（显然在 [1] 中有描述。）

[1] Zhang, Li, Nevatia：使用网络流进行多目标跟踪的全球数据关联，CVPR (2008)。

于 2019-05-28T01:19:04.080 回答