c++ - 如何用图切解决二元标注问题？

Question

我有两张图片重叠区域的 32 段。我必须根据最低成本将每个片段分配给其中一个图像。所以，这是一个二元标记问题，上面是能量最小化函数。

L是长度为32(等于段数)的 vector ，每个元素的值取决于其段号对应的索引。比如说，如果第 3 段分配给图像 1，则 L(2)=0，第 14 段分配给图像 2，因此 L(13)=1。即 L[x] 的值为 0 或 1。因此，L 有 2^32 种可能的赋值。因此，我可以为每个组合计算 E(L)，在执行 2^32 计算后，我可以得到最小 E(L)，并使用该组合。这就是我的直觉所暗示的。但这是不切实际的，因为复杂性呈指数级增长。

但是，许多文献表明这个二元标记问题可以作为使用最大流/最小切割算法的图切割问题来解决。但是，如何将此问题表述为最大流量/最小切割问题？ 32 段是图的节点，但边的权重是多少？容量是多少？

Answer 1

可以在 "What Energy Functions Can Be Minimized via Graph Cuts?" by Vladimir Kolmogorov and Ramin Zabih 中找到图论问题的表述和“当且仅当”关系的证明。 .

关键思想是在 i 和 j 之间构造一条权重为 Vij(0,1)+Vij(1,0)-Vij(0,0)-Vij(1,1) 的有向边。

如果 Vij(1,0)-Vij(0,0)>0，您还需要在源和 i 之间构造一条权重为 Vij(1,0)-Vij(0,0) 的有向边。 否则你需要在 i 和目标权重 Vij(0,0)-Vij(1,0) 之间构造一条有向边。

类似地，如果 Vij(0,1)-Vij(0,0)>0，您还需要在源和 j 之间构造一条权重为 Vij(0,1)-Vij(0,0) 的有向边。 否则你需要在 j 和目标权重 Vij(0,0)-Vij(0,1) 之间构造一条有向边。

请注意，此图的最小切割将偏移 V(0,0) - 连接到目的地的边上的权重总和。