GCoptimization Library

If you use this software you have to reference ALL THREE of these papers

  1. Efficient Approximate Energy Minimization via Graph Cuts Yuri Boykov, Olga Veksler, Ramin Zabih, IEEE transactions on PAMI, vol. 20, no. 12, p. 1222-1239, November 2001.
  2. What Energy Functions can be Minimized via Graph Cuts? Vladimir Kolmogorov and Ramin Zabih. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 26, no. 2, February 2004, pp. 147-159.
  3. An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. Yuri Boykov and Vladimir Kolmogorov. In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 26, no. 9, September 2004, pp. 1124-1137.
Notes on the above bibliography:

Paper in [1] is our original paper developing multi-label energy minimization techniques based on graph cuts which we called the expansion and the swap algorithms. Note that in most cases these approximation techniques are not exact (since the problem is NP hard, in general), but there are strong approximation guarantees, see the paper/thesis for more details

Paper in [2] is about 2-label (binary) energy minimization with graph cuts. It describes the class of binary energies that can be optimized exactly with graph cuts. Because the title of the paper in [2] sounds more general than the title of paper [1], some people have been confused about the relationship between the results of these two papers. The title of paper in [2] does not say binary, whereas in fact, the paper in [2] deals only with binary energies. Thus the paper in [2] is not a generalization of paper in [1], since [1] deals with multi-label energies (Neither, of course, is [1] a generalization of [2]). However, as a very nice "bi-product" of research in paper [2], they produce useful results for the algorithms described in paper [1]. In particular, they show how to construct a smaller graph for the expansion algorithm which was introduced in paper [1], since each individual step inside the main loop of algorithms in [1] is, in fact, a binary energy minimization step. Another very nice result of paper [2] is that they also slightly generalize the class of energy functions to which the expansion and the swap algorithms apply. In the software that we distribute, we use the graph construction described in [2] for the algorithm described in [1]. In fact, we directly use Vladimir Kolmogorov's implementation for binary energy minimization, which he kindly allowed us to include in our library. You can also download Vladimir's code which we use, "energy.h", directly from his home page .

Paper in [3] develops a very fast max-flow algorithm needed for graph cuts computation. Again, the authors of that algorithm kindly allowed us to include their implementation in our library. There are 2 implementation versions available, for simplicity we only use one version, where the graph is implemented with "forward star". If you wish to explore other max-flow versions, and for a better description of max-flow library, go to V. Kolmogorov's web page

Matlab wrapper for GC Version 2.2, written by Brian Fulkerson

Matlab wrapper for GC Version 1.3, written by Shai Bagon

Important Information

This software can be used only for research purposes. If you wish to use this software (or even your own implementation of the algorithms described in the paper (1) ) for commercial purposes, you should be aware that there is a US patent:

Download the Software