# How to solve binary labeling with graph cut?

Many literature references suggest that the binary labeling problem can be converted into a graph cut problem and solved with the max flow/min cut algorithm. I'm trying to understand the formulation given in Xiaowei Zhou's presentation of the reduction.

The binary labeling problem consists of partitioning `n` items (here segments of the overlapped regions of two images) into two disjoint sets in a way which minimises an energy function. We can denote the partition as a vector `(x_1, ..., x_n)` whose elements are `0` or `1`; we also have per-item fitness functions `D_i`; and we define a per-item-pair transition function `V_{i,j}` which penalises discontinuities. Then the energy function is given by

``````E(x_1, ..., x_n) = SUM_p D_p(x_p) + SUM_{p,q} V_{p,q}(x_p, x_q)
``````

In my particular case I have 32 segments, so there are 2^32 possible vectors to evaluate. I could evaluate `E` for each combination, performing 2^32 evaluations, and so get the minimum energy and the combination which achieves it. This is what my intuition suggests. But this is impractical, because the complexity is exponential.

Therefore I want to use the graph cut approach, but I don't understand how to formulate the graph. The 32 segments are the nodes of the graph, but what would be the weight of the edges? And what would be the capacity?

• As I am working with two images, in my case, E(L)=Sum_(i=0 to n-1)(D_1(i)+D_2(i)+Sum_(i=0 to n-1, j=0 to n-1)V(i, j)) Here, n is the number of segments, D_1(i) and D_2(i) are the costs of assigning segment i to image 1 and image 2 respectively(distance from corners of image 1 and 2 respectively). And if i and j segments are neighours, V(i, j) is the intensity difference between them, if i and j are not neighours, V(i, j) is 0. – Rifat Rousseau Sep 26 '13 at 17:24
• I've done some looking around, but no-one seems to have written a paper on this yet which actually defines their notation clearly. I believe that my edit correctly describes the energy function. I think I understand the graph reduction given in the presentation, but it seems to build a graph for which you need the min flow, not the max flow. – Peter Taylor Sep 26 '13 at 18:10
• In this link, at page 11, there is a simple example, but it doesn't tell how it formulated the binary labeling problem as the graph cut problem. This is the paper which proved some energy minimization can be solved with graph cut. I am going through it. But, if someone with more experience can put the algorithm in a programmer's perspective, that would be great. And, thanks Peter for your edit, it clarified my question greatly. – Rifat Rousseau Sep 26 '13 at 18:18
• Although this question is on-topic here and appears to have received a good and helpful answer, you may also be interested in the Computer Science Stack Exchange for similar questions that you may have in the future. The people there tend to have a more theoretical and mathematical background, as opposed to the practical, industry-focused background many users here have. – Thomas Owens Sep 27 '13 at 11:09

## 1 Answer

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)
``````
• Thanks for the explanation. But I'm stuck in the page 4 of this paper, as you can see, they are constructing a graph from energy function. Fig 2(a) and 2(b) make sense. Say, E_i(0)<E_i(1), so, fig 2(a) is applicable, and weight of s->v_i is E_i(1)-E_i(0). Then, when I make a subgraph from E_ij, I can understand why the weight of v_i->v_j is B+C-A-D, which is consistent with your explanaation. But s->vi becomes C-A. So, how do I merge the different weights of the edge s->v_i in different graphs? – Rifat Rousseau Sep 27 '13 at 9:58
• @RifatRousseau, sum them. That's the sum in my "Putting it all together". – Peter Taylor Sep 27 '13 at 10:03
• Nevermind, I have found my answer on the last part of your explanation. I just have to update the weight by adding. Thanks a lot. – Rifat Rousseau Sep 27 '13 at 10:03