README.txt

October 30, 2014 ยท View on GitHub

This software implements the MATLAB wrapper for Boykov-Kolmogorov max-flow/min-cut algorithm.

Anton Osokin, (firstname.lastname@gmail.com) 19.05.2013 https://github.com/aosokin/graphCutDynamicMex_BoykovKolmogorov

Please cite the following papers in any resulting publication:

Y. Boykov and V. Kolmogorov, An experimental comparison of Min-Cut/Max-Flow algorithms for energy minimization in vision, IEEE TPAMI, 26(9):1124-1137, 2004.

P. Kohli and P. Torr, Dynamic graph cuts for efficient inference in markov random fields, IEEE TPAMI, 29(12):2079-2088, 2007.

PACKAGE

./graphCutDynamicMex.cpp, ./updateGraphCutDynamicMex.cpp, ./deletegraphCutDynamicMex.cpp, ./graphCutMemory.h, ./graphCutMemory.cpp, , ./graphCutMex.h, - the C++ code of the wrapper

./build_graphCutDynamicMex.m - function to build the wrapper

./graphCutDynamicMex.m, ./updateGraphCutDynamicMex.m, ./deleteGraphCutDynamicMex.m - the description of the implemented functions

./example_graphCutDynamicMex.m - the example of usage

./maxflow-v3.03.src - C++ code by Vladimir Kolmogorov (the code was slightly modified) http://pub.ist.ac.at/~vnk/software/maxflow-v3.03.src.zip

./graphCutDynamicMex.mexw64, ./updateGraphCutDynamicMex.mexw64, ./deleteGraphCutDynamicMex.mexw64 - Win_x64 binary files for the MEX-functions compiled using MATLAB R2014a + MSVC 2012

./graphCutDynamicMex.mexa64, ./updateGraphCutDynamicMex.mexa64, ./deleteGraphCutDynamicMex.mexa64 - Linux_x64 binary files for the MEX-functions compiled using MATLAB R2012a + gcc-4.4

USING THE CODE

  1. Install MATLAB and one of the supported compilers

  2. Run build_graphCutDynamicMex.m

  3. Run example_graphCutDynamicMex.m to check if the code works

The code was tested under

  • Win7-x64 using MATLAB R2014a and MSVC 2012;
  • ubuntu-12.04-x64 using MATLAB R2012a and gcc-4.4

OTHER PACKAGES

If you need to solve just one graph cut problem you probably do not need dynamic graph cuts.

The IBFS algorithm has polynomial time runtime guarantees. The BK does not. In my experience BK works faster for graphs built for standard 4(8)-connected grid MRFs. If the graph becomes more complicated (especially hierarchical) consider trying IBFS instead.

If you need to minimize energy with just a few non-submodular edges try using the QPBO algorithm