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.
Cite As
Miki Rubinstein (2020). maxflow (https://www.mathworks.com/matlabcentral/fileexchange/21310-maxflow), MATLAB Central File Exchange. Retrieved .
Comments and Ratings (35)
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxCategories
Tags
Acknowledgements
Inspired: Microscopy Image Browser (MIB), Microscopy Image Browser 2 (MIB2)
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
Select web siteYou can also select a web site from the following list:
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)
Hi there,
I got error using this code as below:
Error using mex
maxflowmex.cpp
c:\users\cisir\documents\matlab\maxflow-v3\maxflow\graph.cpp(7) : fatal error C1014: too many include files : depth = 1024
Can anyone help me to solve this error? Thank you.
Hi there,
I tried to follow the steps in the readme.txt.
1) When I run the following statement:
>> run make.m
Building with 'Microsoft Visual C++ 2010'.
Could Not Find C:\MATLAB\CMSC_MinCut_Problem\lib_home\maxflow-v3.0\maxflowmex.exp
Could Not Find C:\MATLAB\CMSC_MinCut_Problem\lib_home\maxflow-v3.0\maxflowmex.exp
MEX completed successfully.
2) Then I started to run the following statement:
>> run test1.m
Undefined function 'maxflow' for input arguments of type 'double'.
Error in test1 (line 32)
[flow,labels] = maxflow(A,T)
Error in run (line 63)
evalin('caller', [script ';']);
What is the problem actually?
Can somebody help me in this matter?
3) Besides that, I tried to compile MEXT projects MSVS, I wasn't able to locate the file of mexversion.rc from the MATLAB include directory, matlab\extern\include to the project.
Do you know where I can obtain the file?
Hope to hear from you soon.
Thank you very much.
Hi there,
I tried to follow the steps in the readme.txt.
1) When I run the following statement:
>> run make.m
Building with 'Microsoft Visual C++ 2010'.
Could Not Find C:\MATLAB\CMSC_MinCut_Problem\lib_home\maxflow-v3.0\maxflowmex.exp
Could Not Find C:\MATLAB\CMSC_MinCut_Problem\lib_home\maxflow-v3.0\maxflowmex.exp
MEX completed successfully.
2) Then I started to run the following statement:
>> run test1.m
Undefined function 'maxflow' for input arguments of type 'double'.
Error in test1 (line 32)
[flow,labels] = maxflow(A,T)
Error in run (line 63)
evalin('caller', [script ';']);
What is the problem actually?
Can somebody help me in this matter?
Hope to hear from you soon.
Thank you very much.
Hi there,
I tried to follow the steps in the readme.txt.
1) When I run the following statement:
>> run make.m
Building with 'Microsoft Visual C++ 2010'.
Could Not Find C:\MATLAB\CMSC_MinCut_Problem\lib_home\maxflow-v3.0\maxflowmex.exp
Could Not Find C:\MATLAB\CMSC_MinCut_Problem\lib_home\maxflow-v3.0\maxflowmex.exp
MEX completed successfully.
2) Then I started to run the following statement:
>> run test1.m
Undefined function 'maxflow' for input arguments of type 'double'.
Error in test1 (line 32)
[flow,labels] = maxflow(A,T)
Error in run (line 63)
evalin('caller', [script ';']);
What is the problem actually?
Can somebody help me in this matter?
3) Besides that, I tried to compile MEXT projects MSVS, I wasn't able to locate the file of mexversion.rc from the MATLAB include directory, matlab\extern\include to the project.
Do you know where I can obtain the file?
Hope to hear from you soon.
Thank you very much.
Hi there,
I tried to follow the steps in the readme.txt.
1) When I run the following statement:
>> run make.m
Building with 'Microsoft Visual C++ 2010'.
Could Not Find C:\MATLAB\CMSC_MinCut_Problem\lib_home\maxflow-v3.0\maxflowmex.exp
Could Not Find C:\MATLAB\CMSC_MinCut_Problem\lib_home\maxflow-v3.0\maxflowmex.exp
MEX completed successfully.
2) Then I started to run the following statement:
>> run test1.m
Undefined function 'maxflow' for input arguments of type 'double'.
Error in test1 (line 32)
[flow,labels] = maxflow(A,T)
Error in run (line 63)
evalin('caller', [script ';']);
What is the problem actually?
Can somebody help me in this matter?
3) Besides that, I tried to compile MEXT projects MSVS, I wasn't able to locate the file of mexversion.rc from the MATLAB include directory, matlab\extern\include to the project.
Do you know where I can obtain the file?
Hope to hear from you soon.
Thank you very much.
Alright here is what you gotta do to make it work I guess,
1. DLL the maxflow-v3.01 from http://vision.csd.uwo.ca/code/, put the files in the same folder as maxflow.
2.
in maxflowmex.cpp change #include "maxflow-v3.0/graph.h" to #include "graph.h"
Then add
#include "maxflow.cpp"
#include "graph.cpp"
to the maxflowmex.cpp file.
and then run:
mex -largeArrayDims maxflowmex.cpp graph.cpp maxflow.cpp
it works for me, hope work for y'all too :)
Why an I getting this error:
Error using mex
C:\Users\sgolest1\Desktop\UGM\New folder\maxflow\maxflow-v3.0\graph.cpp
not found; check that you are in the correct current folder, and check the
spelling of 'C:\Users\sgolest1\Desktop\UGM\New
folder\maxflow\maxflow-v3.0\graph.cpp'.
Error in make (line 11)
mex maxflowmex.cpp maxflow-v3.0/graph.cpp maxflow-v3.0/maxflow.cpp
Thanks falak shah It is resolved
I could not find graph.cpp file... or maxflow.cpp
It seems `mex` might work differently on mac and windows. I had trouble compiling this for mac: duplicate symbols. I fixed this by commenting out the `#include "instances.inc"` line at the bottom of graph.cpp and adding `#include "graph.cpp"` just below `#include "graph.h"` at the top of `maxflow.cpp`. Then I compiled with:
mex -largeArrayDims maxflowmex.cpp maxflow-v3.0/maxflow.cpp
The file layout of this source code is strange, indeed.
All those troubled by the error
Error using maxflowmex
Function "mxGetIr_700" is obsolete.
(64-bit mex files using sparse matrices must be rebuilt with the "-largeArrayDims" option.
See the R2006b release notes for more details.)
try using this:It will solve the problem
mex -largeArrayDims 'maxflowmex.cpp' 'maxflow-v3.0/graph.cpp' 'maxflow-v3.0/maxflow.cpp'
I just compiled it and it does work fine. The files I've used to compile are available at the following address:
http://ecco-qua.tk/?fi=Ln4Ba4dxsE&fn=maxflow.zip
I modified a bit some codes to remove the "deprecated conversion" warnings.
Hope it helps.
Hi all,
Can't comile mex file... here is my output
/usr/local/matlab79/bin/mex -I.. -O -output maxflowmex.mexa64 maxflowmex.cpp
Warning: You are using gcc version "4.6.2". The earliest gcc version supported
with mex is "4.1". The latest version tested for use with mex is "4.2".
To download a different version of gcc, visit http://gcc.gnu.org
In file included from maxflow-v3.0/graph.h:43:0,
from maxflowmex.cpp:20:
maxflow-v3.0/block.h: In member function ‘Type* Block<Type>::New(int)’:
maxflow-v3.0/block.h:124:76: warning: deprecated conversion from string constant to ‘char*’ [-Wwrite-strings]
maxflow-v3.0/block.h: In member function ‘Type* DBlock<Type>::New()’:
maxflow-v3.0/block.h:223:76: warning: deprecated conversion from string constant to ‘char*’ [-Wwrite-strings]
maxflowmex.o: In function `mexFunction':
maxflowmex.cpp:(.text+0x116): undefined reference to `Graph<float, float, float>::Graph(int, int, void (*)(char*))'
maxflowmex.cpp:(.text+0x139): undefined reference to `Graph<float, float, float>::reallocate_nodes(int)'
maxflowmex.cpp:(.text+0x209): undefined reference to `Graph<float, float, float>::reallocate_arcs()'
maxflowmex.cpp:(.text+0x3ee): undefined reference to `Graph<float, float, float>::maxflow(bool, Block<int>*)'
maxflowmex.cpp:(.text+0x464): undefined reference to `Graph<float, float, float>::~Graph()'
collect2: ld returned 1 exit status
mex: link of ' "maxflowmex.mexa64"' failed.
Can some one help me with it ?
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?
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 ?
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.
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)
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!
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
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
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.
Courosh, just set T(i,j)=0 where you *don't* want a seed (capacity 0).
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.
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!
I used this wrapper for my computational photography class. 20 students used it with no problems. It works as advertised.
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).
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.
Thanks for the files Miki!
And Chris thanks for the correction regarding the compilation! Worked great.
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!
Looks very interesting, but I was unable to compile under Mac OSX 10.5.