# How to use a graph cut

I have to use a graph cut to create a binary image from a grayscale image. I can easily compute both energy functions $E_{data}$ and $E_{smooth}$. But after that, I don't know what is the next step.

What I see from wikipedia is $Pr(x|S) = K^{-E}$ where $E=E_{data} +E_{smooth}$ and $S=\left\{ 0\ for\ background, 1\ for\ foreground \right\}$ but I don't know what is $K$.

From this site, there are several methods but I don't know which one is suitable to my problem.

My energy functions are: $$\left\{ \begin{array}{ll} E_{data}(x_v = 1) = D(v) \\ E_{data}(x_v = 0) = 1−D(v) \end{array} \right.$$ where $D(v)$ is already computed. Labels can be 1 for foreground and 0 for background $$E_{smooth}(xu, xv) = \left\{ \begin{array}{ll} λ(1.0−\frac{tan^{−1}(||C_u−C_v||)} {π/2} ),\ if\ x_u\ \ne\ x_v, \\ 0,\ if\ x_u\ =\ x_v, \end{array} \right.$$

$\lambda$ is a constant and $C_u$ is a color vector of the pixel $u$ and $x_u$ is the label of the pixel $u$.

One more thing, for the $E_{data}$, if the pixel is not yet labelled what would be the value ? Would it be 0 ?

EDIT: my image is not any grayscale image, it is already computed and most of pixels are 0 (or close) or 1 (or close).

-

## 1 Answer

1. The methods here are to give fast approximate solutions in the case where there are more than $2$ labels. Since in your case there are only $2$ labels, $0$ and $1$, you can use the exact max-flow min-cut algorithm described in Greig, Porteous, and Seheult (also here.)

2. The problem is to find labels for which the energy function is minimized. The energy function has no defined value for unlabelled pixels.

3. The solution should have minimum energy (or maximum probability), so which $K>1$ you choose in your equation above does not matter, as it does not affect the relative ordering of the probabilities.

4. Addendum: Fox and Nicholls 2001 (here, here) point out that the minimum-energy solution may not be typical of the a posteriori distribution.

-
I understood the point 2 and 3. But I think I still need a bit help for the point 1. What I have to do is find $x^*=argminE(x)$. Therefore, the minimum is found when the derivative of E =0, right ? How do I find the derivative of E ? – Seltymar Jan 22 '13 at 7:32
It's a discrete optimization problem, so you don't want to take the derivative of $E$. Instead, you should encode the function $E$ as a weighted directed graph and then find a minimum cut in that graph, using a max-flow min-cut algorithm. The procedure is briefly described in section 2 of the Greig, Porteous, and Seheult paper. – David Moews Jan 22 '13 at 7:55
Yes, I have read it but I still have some problems to understand it. I'm currently reading this one homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/AV0405/COLLINS/… – Seltymar Jan 22 '13 at 8:04
I read again and again this paper but I can't find the analogy with my problem. I mean I have to compute the minimum capacity $C$ of the graph which correspond to the min-cut. I don't understand how to weight the edges of my graph. is $\lambda = E_{data}$ and $\beta = E_{smooth}$ ? – Seltymar Jan 23 '13 at 2:23
In the notation of the Greig, Porteous, and Seheult paper, yes, this is what corresponds to what. If you look at the equation on p. 272 of the GPS paper which gives $L(x|y)$, you should be able to find $\lambda_i$ and $\beta_{ij}$ such that $L(x|y)$ matches your $-E$, up to an additive constant. – David Moews Jan 23 '13 at 2:32