Graph cuts in computer vision
As applied in the field of computer vision, graph cut optimization can be employed to efficiently solve a wide variety of low-level computer vision problems, such as image smoothing, the stereo correspondence problem, image segmentation, object co-segmentation, and many other computer vision problems that can be formulated in terms of energy minimization. Many of these energy minimization problems can be approximated by solving a maximum flow problem in a 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, the term "graph cuts" is applied specifically to those models which employ a max-flow/min-cut optimization.
"Binary" problems can be solved exactly using this approach; problems where pixels can be labeled with more than two different labels cannot be solved exactly, but solutions produced are usually near the global optimum.
History
The theory of graph cuts used as an optimization method was first applied in computer vision in the seminal paper by Greig, Porteous and Seheult of Durham University. Seheult and Porteous were members of Durham's much lauded statistics group of the time, lead by Julian Besag and Peter Green, with the optimisation expert Margaret Greig also notable as the first ever female member of staff of the Durham Mathematical Sciences Department.In the Bayesian statistical context of smoothing noisy 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, or iterated conditional modes were used to solve such image smoothing problems.
Although the general -colour problem remains unsolved for 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.
In 2011, C. Couprie et al. proposed a general image segmentation framework, called the "Power Watershed", that minimized a real-valued indicator function from over a graph, constrained by user seeds set to 0 or 1, in which the minimization of the indicator function over the graph is optimized with respect to an exponent. When, the Power Watershed is optimized by graph cuts, when the Power Watershed is optimized by shortest paths, is optimized by the Random walker algorithm and is optimized by the Watershed algorithm. In this way, the Power Watershed may be viewed as a generalization of graph cuts that provides a straightforward connection with other energy optimization segmentation/clustering algorithms.
Binary segmentation of images
Notation
- Image:
- Output: Segmentation . For hard segmentation
- Energy function: where C is the color parameter and λ is the coherence parameter.
- Optimization: The segmentation can be estimated as a global minimum over S:
Existing methods
- Standard Graph cuts: optimize energy function over the segmentation.
- Iterated Graph cuts:
- First step optimizes over the color parameters using K-means.
- Second step performs the usual graph cuts algorithm.
- Dynamic graph cuts:
Energy function
where the energy is composed of two different models :Likelihood / Color model / Regional term
— unary term describing the likelihood of each color.- This term can be modeled using different local or global approaches that are described below.
Histogram
- We use intensities of pixels marked as seeds to get histograms for object and background intensity distributions: P and P.
- Then, we use these histograms to set the regional penalties as negative log-likelihoods.
GMM (Gaussian mixture model)
- We usually use two distributions: one for background modelling and another for foreground pixels.
- Use a Gaussian mixture model to model those 2 distributions.
- Goal: Try to pull apart those two distributions.
Texon
- A texon is a set of pixels that has certain characteristics and is repeated in an image.
- Steps:
- Determine a good natural scale for the texture elements.
- Compute non-parametric statistics of the model-interior texons, either on intensity or on Gabor filter responses.
- Examples:
- *
- *
Prior / Coherence model / Boundary term
- In practice, pixels are defined as neighbors if they are adjacent either horizontally, vertically or diagonally.
- Costs can be based on local intensity gradient, Laplacian zero-crossing, gradient direction, color mixture model,...
- Different energy functions have been defined:
- * Standard Markov random field: Associate a penalty to disagreeing pixels by evaluating the difference between their segmentation label. See Boykov and Kolmogorov ICCV 2003
- * Conditional random field: If the color is very different, it might be a good place to put a boundary. See Lafferty et al. 2001; Kumar and Hebert 2003
Criticism
- Metrication artifacts: When an image is represented by a 4-connected lattice, graph cuts methods can exhibit unwanted "blockiness" artifacts. Various methods have been proposed for addressing this issue, such as using additional edges or by formulating the max-flow problem in continuous space.
- Shrinking bias: Since graph cuts finds a minimum cut, the algorithm can be biased toward producing a small contour. For example, the algorithm is not well-suited for segmentation of thin objects like blood vessels.
- Multiple labels: Graph cuts is only able to find a global optimum for binary labeling problems, such as foreground/background image segmentation. Extensions have been proposed that can find approximate solutions for multilabel graph cuts problems.
- Memory: the memory usage of graph cuts increase quickly as the image size increase. As an illustration, the Boykov-Kolmogorov max-flow algorithm v2.2 allocates bytes. Nevertheless, some amount of work has been recently done in this direction for reducing the graphs before the maximum-flow computation.
Algorithm
- Minimization is done using a standard minimum cut algorithm.
- Due to the Max-flow min-cut theorem we can solve energy minimization by maximizing the flow over the network. The Max Flow problem consists of a directed graph with edges labeled with capacities, and there are two distinct nodes: the source and the sink. Intuitively, it's easy to see that the maximum flow is determined by the bottleneck.
Implementation (exact)
Implementation (approximation)
The Sim Cut algorithm approximates the graph cut. The algorithm implements a solution by simulation of an electrical network. This is the approach suggested by Cederbaum's maximum flow theorem. Acceleration of the algorithm is possible through parallel computing.Software
- — An implementation of the maxflow algorithm described in "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Computer Vision" by Vladimir Kolmogorov
- — some graph cut libraries and MATLAB wrappers
- — fast multi-core max-flow/min-cut solver optimized for grid-like graphs
- — An implementation of the Sim Cut; an algorithm for computing an approximate solution of the minimum s-t cut in a massively parallel manner.