Graph Cut Matching

Advanced Vision Assignment

Salman Khan

Matric No: 0451222

Feb 11, 2005



Graph cut matching is one of two primary approaches to stereo matching along with correllation matching. The stereo matching problem can be formulated as energy function minimization, and Graph Min-Cut algorithms can be applied to solve the minimization problem. This was first discovered by Greig et al.[3]

The Min-Cut problem is defined as follows [4]

Let be a (not necessarily simple) undirected edge-weighted graph with nonnegative weights. A cut C of G is any nontrivial subset of V, and the weight of the cut is the sum of weights of edges crossing the cut. A mincut is then defined as a cut of G of minimum weight. The problem is polynomial time solvable as a series of network flow problems or using the algorithm of Stoer and Wagner [5].

A good introduction to the graph theoretical background of the problem is given in [6] Many standard algorithms in combinatorial optimization are known to solve the graph max-flow/min-cut problem. Most of the algorithms belong to one of the following two groups: Goldberg-Tarjan style “push-relabel” methods and algorithms based on Ford-Fulkerson style “augmenting paths”.

The Dinic algorithm is an example of an augmenting path algorithm.



The Dinic algorithm

The Dinic algorithm consists of two phases. In the first phase, one constructs a layered network which consists of all the "useful" edges of G: A useful edge [u, v] has the property that f(u, v) < c(u, v) (Where f(u,v) is flow from vertex u to v, and c(u,v) is capacity of link from u to v). The first and the last layer of this layered network always contain s (source) and t (sink) respectively. If such a layered network cannot be constructed then the flow in G is maximum and the algorithm ends.

In the second phase of the Dinic algorithm, one finds a maximal flow by constructing paths from s to t (using a depth-first search) in the layered network. Note that a maximal flow may not be maximum: A maximal flow satisfies the condition that for every path P from s to t in the layered network, there is at least a saturated edge in P. A saturated edge is one for which its flow equals its capacity.

The worst case running time complexity for Dinic algorithm is

O(mn2) where n is the number of nodes and m is the number of edges in the graph.



The push-relabel method

The generic push-relabel algorithm does not construct a flow by constructing paths from s to t. Rather, it starts by pushing the maximum possible flow out from the source s into the neighbours of s, then pushing the excess flow at those vertices into their own neighbours. This is repeated until all vertices of G except s and t have an excess flow of zero (that is, the flow conservation property is satisfied). Undeliverable flows are pushed back to s.

[1] and [2] are treatments of graph cut algorithms as applied to vision problems.



References

  1. Yuri Boykov and Vladimir Kolmogorov; An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision, IEEE Transactions on PAMI, Vol. 26, No. 9, pp. 1124-1137, Sept. 2004 p.1 pdf

  2. Sudipta N Sinha, "Graph Cut Algorithms in Vision, Graphics and Machine Learning", Integrative Paper, November, 2004, UNC Chapel Hill. pdf

  3. D. Greig, B. Porteous, and A. Seheult. Exact maximum a posteriori estimation images. Journal of the Royal Statistical Society, Series B, 51(2):271–279, 1989.

  4. Eric W. Weisstein. "Mincut." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Mincut.html

  5. Stoer, M. and Wagner, F. "A Simple Min Cut Algorithm." Algorithms--ESA '94, LNCS 855, 141-147, 1994. pdf

  6. Reinhard Diestel,Graph Theory,Second Edition. pdf