#########################################################################
# #
# GC_optimization - software for energy minimization with graph cuts #
# Version 1.1 #
# http://www.csd.uwo.ca/faculty/olga/software.html #
# #
# Copyright 2005 Olga Veksler (olga@csd.uwo.ca) #
# #
#########################################################################
/* email olga@csd.uwo.ca for any questions, suggestions and bug reports
/***************** IMPORTANT!!!!!!!!!!!***********************************************************
If you use this software, YOU HAVE TO REFERENCE (at least) 3 papers, the citations [1]
[2] and [3] below
/****************************************************************************************************/
/*
0. Matlab Wrapper.
This README file was written by Olga Veksler and reffers to the C++ core implementation.
In order to use the Matlab Wrapper you should
a. unzip the bundle into a directory within your Matlab's path
b. compile the required mex-files using
>> compile_gc
(You might need to set your mex compiler first. Type mex -setup on Matlab's prompt)
c. type doc GraphCut and you will have the rest of the necessary documentation.
This software is for academic use ONLY.
If you are using this software please note required citations in the Matlab documenation.
For any questions/remarks/problems with the Matlab wrapper please contact shai.bagon@weizmann.ac.il
1. Introduction.
This software library implements the Graph Cuts Energy Minimization methods
described in
[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.
This software can be used only for research purposes, you should cite
the aforementioned paper in any resulting publication.
If you wish to use this software (or the algorithms described in the aforementioned paper)
for commercial purposes, you should be aware that there is a US patent:
R. Zabih, Y. Boykov, O. Veksler,
"System and method for fast approximate energy minimization via graph cuts ",
United Stated Patent 6,744,923, June 1, 2004
/* Together with the library implemented by O. Veksler, we provide, with the permission of the
V. Kolmogorov and Y. Boykov the following libraries:
1) energy.h, which was developed by Vladimir Kolmogorov and implements binary energy minimization
technique described in
[2] What Energy Functions can be Minimized via Graph Cuts?
Vladimir Kolmogorov and Ramin Zabih.
To appear in IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI).
Earlier version appeared in European Conference on Computer Vision (ECCV), May 2002.
We use "energy.h" to implement the binary energy minimization step
for the alpha-expansion and swap algorithms. The graph construction provided by "energy.h" is
more efficient (and slightly more general) than the original graph construction for the
alpha-expansion algorithm in the paper cited as [1]
This software can be used only for research purposes. IF YOU USE THIS SOFTWARE,
YOU SHOULD CITE THE AFOREMENTIONED PAPER [2] IN ANY RESULTING PUBLICATION.
2) graph.h, block.h, maxflow.cpp
This software library implements the maxflow algorithm
described in
[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),
September 2004
This algorithm was developed by Yuri Boykov and Vladimir Kolmogorov
at Siemens Corporate Research. To make it available for public use,
it was later reimplemented by Vladimir Kolmogorov based on open publications.
If you use this software for research purposes, you should cite
the aforementioned paper in any resulting publication.
*/
/* These 4 files (energy.h,graph.h, block.h, maxflow.cpp) are included in the curent library with permission of
Vladimir Kolmogorov and Yuri Boykov. They are included in a separate subdirectory named NotVekslerCode.
The can also be downloaded independently from Vladimir Kolmogorov's
website:http://research.microsoft.com/~vnk/
Please Note that Vladimir's website is likely to move in the future */
Tested under windows, Visual C++ 6.0 compiler
##################################################################
2. License.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
##################################################################
3. Energy Minimization
This software is for minimizing energy functions of the form:
E(l) = sum_p D(p,l_p) + sum_{p,q} Vpq(l_p,l_q)
Here we have a finite set of sites (or pixels) P and a finite set of labels L.
A labeling l is assignments of labels in L to pixels in P. The individual pixels
are referred to with small letters p and q, label of pixel p is denoted by l_p,
and the set of all label-pixel assignments is denoted by l, that is
l = {l_p | p in P}.
The first term in the energy function E(l) is typically called the data term, and
it consists of the sum over all pixels p of the penalty(or cost) D(p,l_p), what
should be the cost of assigning label l_p to pixel p. D(p,l_p) can be arbitrary.
The second term is a sum over all pairs of neighboring pixels {p,q}.
That is there is a neighborhood relation on the set of pixels (this relationship
is symmetric, that is if p is a neighbor of q then q is a neighbor of p).
Here we assume that the neighbor pairs are unordered. This means that if pixels p and q are
neighbors, then there is either Vpq(l_p,l_q) in the second sum of the energy,
or Vqp(l_q,l_p), but not both. This is not a restriction, since in practice, one can always go
from the ordered energy to the unordered one. This second term is typically called the smoothness
term.
The expansion algorithm for energy minimization can be used whenever for any 3 labels a,b,c
V(a,a) + V(b,c) <= V(a,c)+V(b,a). In other words, expansion algorithm can be used if
the binary energy for the expansion algorithm step is regular, using V. Kolmogorov's terminology.
The swap algorithm for energy minimization can be used whenever for any 2 labels a,b
V(a,a) + V(b,b) <= V(a,b)+V(b,a). In other words, swap algorithm can be used if
the binary energy for the swap algorithm step is regular, using V. Kolmogorov's terminology.
##################################################################
4. Datatypes
a) EnergyTermType. This is the type for each individual energy term,
that is for the terms D and V. By default, it is set to short.
To change it, go into file "graph.h" and modify the statement
"typedef int captype;" from short to any d