This software implements the maxflow algorithm described by Boykov and Kolmogorov in the paper:

"An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Computer Vision", published In IEEE Transactions on Pattern Analysis and Machine Intelligence, September 2004. See below for full reference details.

Minimum cut/maximum flow algorithms on graphs emerged as an increasingly useful tool for exact or approximate energy minimization in low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with different polynomial time complexity. Their practical efficiency, however, has to date been studied mainly outside the scope of computer vision. The goal of the referenced IEEE paper was to provide an experimental comparison of the efficiency of min-cut/max flow algorithms for applications in vision, using several standard algorithms as well as the algorithm developed by the authors. In many cases the Boykov/ Kolmogorov algorithm worked several times faster than any of the other methods, making near real-time performance possible.

Note that the experimental results reported in this IEEE paper are based on the original implementation of the algorithm as developed by the authors during their time with Siemens. The algorirthm has since been fully re-encoded.

Yuri Boykov is currently Assistant Professor in the Computer Vision Research Group at the University of Western Ontario.
Vladimir Kolmogorov joined UCL in 2005 as Lecturer in the Department of Computer Science. He moved to IST, Austria in 2011 where he holds the position of Assistant Professor.

PLEASE NOTE: This software was originally released under the GNU GPL licence. It may still be accessed under this licence from the author's academic webpage at http://pub.ist.ac.at/~vnk/software.html. However, please be aware that any program that incorporates the code under this licence must, under the terms of the GNU GPL, be released itself under a licence compatible with the GPL. GNU GPL does not permit incorporating this software into programs that are to be distributed under proprietary licence.  Following requests to include the software in commercial products outside of the GNU licensing restriction, the code is now available under a variety of proprietary UCLB licences which offer different rights relating to development and distribution. View full terms by selecting the black 'View Licence' buttons on the left hand side of the page.

The software has been tested under the following:

• Windows
• Visual C++ 6.0 compiler
• Unix (SunOS 5.8 and RedHat Linux 7.0, GNU c++ compiler)