我有两个图像的重叠区域的 32 段。我必须根据最低成本将每个片段分配给任一图像。所以，这是一个二元标注问题，上面是能量最小化函数。
L 是长度为 32（等于段数）的向量，每个元素的值取决于其对应于段号的索引。比如说，如果第 3 段分配给图像 1，则 L(2)=0，第 14 段分配给图像 2，因此 L(13)=1。即 L[x] 的值为 0 或 1。因此，L 有 2^32 个可能的赋值。因此，我可以为每个组合计算 E(L)，在执行 2^32 计算后，我可以得到最小 E(L)，并使用该组合。这就是我的直觉所暗示的。但这是不切实际的，因为复杂性是指数级的。
但是，许多文献表明这个二元标记问题可以通过最大流/最小切割算法作为图切割问题来解决。但是，如何将此问题表述为最大流量/最小切割问题？32 个段是图的节点，但边的权重是多少？容量是多少？
作为图论问题的公式和“当且仅当”关系的证明可以在“哪些能量函数可以通过图割最小化？”中找到。弗拉基米尔·科尔莫戈罗夫和拉明·扎比赫。
关键思想是在 i 和 j 之间构建一个权重为 Vij(0,1)+Vij(1,0)-Vij(0,0)-Vij(1,1) 的有向边。
如果 Vij(1,0)-Vij(0,0)>0 你还需要在源和权重 Vij(1,0)-Vij(0,0) 的 i 之间构造一条有向边。否则，您需要在 i 和权重 Vij(0,0)-Vij(1,0) 的目的地之间构造一条有向边。
类似地，如果 Vij(0,1)-Vij(0,0)>0，您还需要在源和权重 Vij(0,1)-Vij(0,0) 的 j 之间构造一条有向边。否则，您需要在 j 和权重 Vij(0,0)-Vij(0,1) 的目的地之间构造一条有向边。
请注意，该图的最小切割将被连接到目的地的边上的权重 V(0,0)-sum 所抵消。