I'm going to attempt this from first principles based on my understanding from the papers I've read. Warning: I've left in a false start.
Initialisation step 1
To your 32 segments nodes we add a source node S
and a sink node T
. Then we aim to construct things such that a cut which partitions the nodes into disjoint sets, one containing S
and the other containing T
, has a capacity equal to the energy of the corresponding partition.
So we start by adding edges from S
to each segment p
with capacity D_p(1)
(these edges are cut if the segments are in T
's half) and from each segment p
to T
with capacity D_p(0)
(these edges are cut if the segments are in S
's half).
Initialisation step 2
We then run a loop through the non-trivial V_{p,q}
updating the subgraph generated by S
, p
, q
, and T
. We add an edge p->q
and an edge q->p
, and we also update the capacities of S->p
, S->q
, p->T
, q->T
. Our aim is to make these updates in such a way that any cut has an overall capacity increase of V_{p,q}(x_p, x_q)
for the corresponding values of x_p
, x_q
. Let's draw up a table of the edges cut by each of the four cases:
x_p x_q Edges cut
0 0 p->T, q->T
0 1 p->T, S->q, p->q, (q->p)
1 0 S->p, q->T, (p->q), q->p
1 1 S->p, S->q
(The edges in brackets are back-edges and hence don't affect the capacity of the cut).
The values of the deltas
So if the capacity changes of our update are c_{vertex,vertex}
we derive the simultaneous equations
c_pT + c_qT = V_{p,q}(0,0)
c_pT + c_Sq + c_pq = V_{p,q}(0,1)
c_Sp + c_qT + c_qp = V_{p,q}(1,0)
c_Sp + c_Sq = V_{p,q}(1,1)
That's underdetermined. The easy approach looks to be to set c_pq = c_qp = 0
and effectively ditch the edges between neighbours. However, that is of course singular. The next easy approach is to set c_Sp = c_pT = 0
. Then we get:
c_Sq = V_{p,q}(1,1)
c_qT = V_{p,q}(0,0)
c_pq = V_{p,q}(0,1) - V_{p,q}(1,1)
c_qp = V_{p,q}(1,0) - V_{p,q}(0,0)
Optimisation
Are we done?
The aim was to get the cut equal to the energy. We want to minimise the energy, which means finding a min cut, and we're definitely ok provided that all of the capacity changes above are non-negative. For any reasonable transition penalisation function we can expect a transition to be penalised more than a non-transition, so that's fine.
However, there is a small optimisation which the standard approach takes. If we ensure that every cut adds the same constant value K
to the energy, then it doesn't change which input gives the minimum solution. So we can add K
to our simultaneous equations and get
c_pT + c_qT = K + V_{p,q}(0,0)
c_pT + c_Sq + c_pq = K + V_{p,q}(0,1)
c_Sp + c_qT + c_qp = K + V_{p,q}(1,0)
c_Sp + c_Sq = K + V_{p,q}(1,1)
Now, the standard approach to a determined system is to set c_Sq = c_qp = c_pT = 0
, reducing to
c_qT - K' = V_{p,q}(0,0)
+ c_pq - K' = V_{p,q}(0,1)
c_Sp + c_qT - K' = V_{p,q}(1,0)
c_Sp - K' = V_{p,q}(1,1)
with solution
K' = V_{p,q}(1,0) - V_{p,q}(0,0) - V_{p,q}(1,1)
c_Sp = V_{p,q}(1,0) - V_{p,q}(0,0)
c_qT = V_{p,q}(1,0) - V_{p,q}(1,1)
c_pq = V_{p,q}(0,1) + V_{p,q}(1,0) - V_{p,q}(0,0) - V_{p,q}(1,1)
This only requires one additional edge between p
and q
, which will give a small optimisation in the setup and in the graph flow computation. Of course, it induces slightly different inequality constraints on the values which V_{p,q}
can take.
Putting it all together
For each p
, we add edges
S->p with weight D_p(1) + SUM_q (V_{p,q}(1,0) - V_{p,q}(0,0))
p->T with weight D_p(0) + SUM_q (V_{q,p}(1,0) - V_{q,p}(1,1))
For each p,q
we add edge
p->q with weight V_{p,q}(0,1) + V_{p,q}(1,0) - V_{p,q}(0,0) - V_{p,q}(1,1)