1

在此处输入图像描述

我有两个图像的重叠区域的 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 个段是图的节点,但边的权重是多少?容量是多少?

4

1 回答 1

1

作为图论问题的公式和“当且仅当”关系的证明可以在“哪些能量函数可以通过图割最小化?”中找到。弗拉基米尔·科尔莫戈罗夫和拉明·扎比赫

关键思想是在 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 所抵消。

于 2013-09-27T19:45:16.093 回答