# Graph cuts in computer vision

As applied in the field of computer vision, graph cuts can be employed to efficiently solve a wide variety of low-level computer vision problems (early vision), such as image smoothing, the stereo correspondence problem, and many other computer vision problems that can be formulated in terms of energy minimization. Such energy minimization problems can be reduced to instances of the maximum flow problem in a graph (and thus, by the max-flow min-cut theorem, define a minimal cut of the graph). Under most formulations of such problems in computer vision, the minimum energy solution corresponds to the maximum a posteriori estimate of a solution. Although many computer vision algorithms involve cutting a graph (e.g., normalized cuts), the term "graph cuts" is applied specifically to those models which employ a max-flow/min-cut optimization (other graph cutting algorithms may be considered as graph partitioning algorithms).

"Binary" problems (such as denoising a binary image) can be solved exactly using this approach; problems where pixels can be labeled with more than two different labels (such as stereo correspondence, or denoising of a grayscale image) cannot be solved exactly, but solutions produced are usually near the global optimum.

## History

The theory of graph cuts was first applied in computer vision in the seminal paper by Greig, Porteous and Seheult of Durham University. In the Bayesian statistical context of smoothing noisy (or corrupted) images, they showed how the maximum a posteriori estimate of a binary image can be obtained exactly by maximizing the flow through an associated image network, involving the introduction of a source and sink. The problem was therefore shown to be efficiently solvable. Prior to this result, approximate techniques such as simulated annealing (as proposed by the Geman brothers), or iterated conditional modes (a type of greedy algorithm as suggested by Julian Besag) were used to solve such image smoothing problems.

Although the general $k$ -colour problem remains unsolved for $k>2,$ the approach of Greig, Porteous and Seheult has turned out to have wide applicability in general computer vision problems. Greig, Porteous and Seheult approaches are often applied iteratively to a sequence of binary problems, usually yielding near optimal solutions.

## Existing methods

• Standard Graph cuts: optimize energy function over the segmentation (unknown S value).
• Iterated Graph cuts:
1. First step optimizes over the color parameters using K-means.
2. Second step performs the usual graph cuts algorithm.
These 2 steps are repeated recursively until convergence.
• Dynamic graph cuts:
Allows to re-run the algorithm much faster after modifying the problem (e.g. after new seeds have been added by a user).

## Energy function

### Likelihood / Color model / Regional term

$E_{\rm {color}}$ — unary term describing the likelihood of each color.

• This term can be modeled using different local (e.g. texons) or global (e.g. histograms, GMMs, Adaboost likelihood) approaches that are described below.

#### Histogram

• We use intensities of pixels marked as seeds to get histograms for object (foreground) and background intensity distributions: P(I|O) and P(I|B).
• Then, we use these histograms to set the regional penalties as negative log-likelihoods.

#### GMM (Gaussian Mixture Model)

• We usually use 2 distributions to model background and foreground pixels.
• Use a Gaussian mixture model (with 5-8 components) to model those 2 distributions.
• Goal: Try to pull apart those 2 distributions.

#### Texon

• A texon (or texton) is a set of pixels that has certain characteristics and is repeated in an image.
• Steps:
1. Determine a good natural scale for the texture elements.
2. Compute non-parametric statistics of the model-interior texons, either on intensity or on Gabor filter responses.
• References:

### Prior / Coherence model / Boundary term

$E_{\rm {coherence}}$ — binary term describing the coherence between neighborhood pixels.

• In practice, pixels are defined as neighbors if they are adjacent either horizontally, vertically or diagonally (4 way connectivity or 8 way connectivity).
• Costs can be based on local intensity gradient, Laplacian zero-crossing, gradient direction, color mixture model,...