我有两个图像的重叠区域的32段。我必须根据最低成本将每个段分配给任一图像。因此，这是一个二进制标记问题，并且上面是能量最小化功能。
L是长度为32(等于段数)的 vector ，每个元素的值取决于其与段号相对应的索引。假设，如果第3个段分配了图像1，则L(2)= 0，第14个段分配了图像2，因此L(13)= 1。也就是说L [x]的值为0或1。因此，有2 ^ 32个可能的L赋值。因此，我可以为每个组合计算E(L)，执行2 ^ 32个计算后，我可以得到最小E(L)，并使用该组合。这就是我的直觉。但这是不切实际的，因为复杂度是指数级的。
但是，许多文献认为，可以使用最大流量/最小切割算法将这种二进制标记问题作为图形切割问题来解决。但是，如何将这个问题公式化为最大流量/最小切割问题？这32个段是图的节点，但是边的权重是多少？容量是多少？
最佳答案
可以在"What Energy Functions Can Be Minimizedvia Graph Cuts?" by Vladimir Kolmogorov and Ramin Zabih中找到作为图论问题的公式和“if and only if”关系的证明。
关键思想是在权重Vij(0,1)+ Vij(1,0)-Vij(0,0)-Vij(1,1)的i和j之间构造有向边。
如果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偏移。
关于c++ - 如何用图割解决二进制标记？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19033341/