maxflow

A wrapper library for Boykov and Kolmogorov max-flow/min-cut implementation

Description

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.

• MATLAB release: MATLAB 7.4 (R2007a)

[Eran Mukamel]

Looks very interesting, but I was unable to compile under Mac OSX 10.5.

[Cris Luengo]

This is very nice, but the documentation and examples could use some improvement.

To compile I had to add
#include "maxflow.cpp"
#include "graph.cpp"
to the maxflowmex.cpp file, and remove
#include "instances.inc"
from the .cpp files in the maxflow library. Don't ask me why, but it works this way!

[Zoltan]

Thanks for the files Miki!
And Chris thanks for the correction regarding the compilation! Worked great.

[Yongjian Yu]

I tested the code on a binary image with one closed region being 1 and the background being set to zero but the code didn't yield a correct result. Could anybody offer a solution please? Thanks.

[Antonella Zanna]

Hi Miki, and thanks for your files.
I have managed to compile successfully the files using Cris' suggestions, however I'm experiencing the problem that when I run "test1" or "test2' Matlab suddently quits. (Mac OSX 10.5.8, Matlab R2007b).

[Petter]

 

[James Hays]

I used this wrapper for my computational photography class. 20 students used it with no problems. It works as advertised.

[Joao Henriques]

Nice! A few small issues:
1) The help mentions a link for creating sparse matrices efficiently, but I can't find anywhere!
2) I don't get why you release the DLL after every call, which seems wasteful when using repeatedly (isn't it ok to just call the mex file directly?).
3) The 2nd example could be more interesting -- the cut is not exactly what you'd expect, until you find out that the flow is from the left-most pixels to the right-most.

Other than that, excellent work, and thanks for sharing this!

[Courosh]

The interface seems to require the same number of object and background seeds. Is there a workaround to this, because it is a severe limitation.

[Joao Henriques]

Courosh, just set T(i,j)=0 where you *don't* want a seed (capacity 0).

[Francis]

 

[Francis]

Thanks Miki for the files. Thanks Cris for the correction as I can now compile the code on MAC OS 10.6.

However, got the following error message when running test1.m and test2.m:
??? Error using ==> maxflowmex
Function "mxGetIr_700" is obsolete in file "compat32.cpp", line 264.(64-bit mex files using sparse matrices must be rebuilt with the "-largeArrayDims" option. See the R2006b release notes for more details.)

As suggested in the error message, I did compile with the suggested option in the make.m file as follows :

mex -largeArrayDims 'maxflowmex.cpp' 'maxflow-v3.01/graph.cpp' 'maxflow-v3.01/maxflow.cpp'

Now the test1.m and test2.m are running properly.

[frank]

test1 and test2 seem to run fine with the given image example images but when i try running on another image from my database it doesn't segment it out. Has anyone tried it on other images? Is there any matlab code for the graph cut algorithm since I am not too much of a C++ person?

Thanks

[zhu]

hello, Miki, thanks for your work, but i have some trouble in compiling the files. i have read the README.txt file and followed the Build Instructions, but when i run make.m, some errors occurred as follows:
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 99 syntax error; found `<' expecting `;'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 99 skipping `<'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 99 syntax error; found `Type' expecting `;'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 99 syntax error; found `>' expecting `;'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 99 skipping `>'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 99 syntax error; found `Block' expecting `;'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 100 syntax error; found `{' expecting `;'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 100 skipping `{'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 101 syntax error; found `:' expecting `;'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 101 skipping `:'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 106 illegal initialization for parameter `err_function'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 106 redeclaration of `Block' previously declared at C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h 99
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 106 undeclared identifier `first'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 106 undeclared identifier `last'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 106 undeclared identifier `block_size'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 106 undeclared identifier `error_function'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 106 operands of = have illegal types `int' and `pointer to void function(pointer to char)'
Warning C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 106 missing return value
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 109 unrecognized declaration
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 109 conflicting argument declarations for function `Block'
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 109 redefinition of `Block' previously defined at C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h 106
Error C:\Users\zhuyong\Desktop\maxflow\maxflowmex.cpp: C:\Users\zhuyong\Desktop\maxflow\maxflow-v3.0\block.h: 109 too many errors
 
  E:\PROGRA~1\MATLAB\R2008A\BIN\MEX.PL: Error: Compile of 'maxflowmex.cpp' failed.

i need your help

[Allan]

I received the same errors when i first tried to compile the mex file zhu, I assume that you are using matlabs LCC-win32 C compiler which is default to compile mex files. you need to change it to a C++ compiler supported by matlab. Type mex -setup and select a C++ compiler. (I used Microsoft Visual C++ and it worked).

Thanks for the upload!

[Tak Yeon Lee]

When trying to build it, I got this error below :

??? Error using ==> maxflowmex
Function "mxGetIr_700" is obsolete in file ".\compat32.cpp", line 264.
(64-bit mex files using sparse matrices must be rebuilt with the "-largeArrayDims" option.
See the R2006b release notes for more details.)

Error in ==> maxflow at 35
[flow,labels] = maxflowmex(A,T);

Error in ==> test1 at 32
[flow,labels] = maxflow(A,T)

[Tak Yeon Lee]

I'm sorry .. build seems to be okay. But when I'm trying to run test1.m and test2.m I got the above error.

[JD]

Thanks for upload. Need help with interpreting output to confirm code runs properly.

The code builds and runs fine on R2010b-64 bit system with VisualStudio2008-64. However, Test2.m output produces a binary labeled image of the waterfallf.bmp picture that does not match RGB image. The boundary between labeled regions does not match coastline or any other feature.
What is the correct output for Test2.m ?

[JD]

Per 23 june 2010 comment, I also tried flipping image.
Per 17 Aug 2009 comment I also tried simple binary test images (black X and black blob on white background.
Binary labeling does not match source image in any case.

Was someone able to get proper labeling for an image? If so, what image did you use?