maxflow

Yuri Boykov's and Vladimir Kolmogorov's work on graph cuts and MRF optimization has been extensively cited in the academia, and their maximum flow implementation is widely used in computer vision and image processing research.

This is a MEX library that wraps their code, so that it could be easily accessed from MATLAB, using a sparse matrix graph representation. Typical usage:

[flow,labels] = maxflow(A,T);

Where A is the (sparse) adjacency matrix representation of the graph (smoothness term), and T contains the terminal connections (data term). Refer to maxflow.m for further details.

This library currently supports maximum flow calculation for the case of binary partition, based on their work:

Yuri Boykov and Vladimir Kolmogorov, 'An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision', IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124-1137, Sept. 2004.

It has been created on a Windows machine and tested with MATLAB R2007a. See README.txt for building instructions.

Please report any issues.

Future Steps:
=============
1. Extend this wrapper to support reusing of search trees
2. Add support for their multi-label optimization algorithm
Both of these are rather straightforward and I expect to do them in the near future.