Code covered by the BSD License  

Highlights from
maxflow

3.88889

3.9 | 9 ratings Rate this file 149 Downloads (last 30 days) File Size: 136 KB File ID: #21310

maxflow

by

 

02 Sep 2008 (Updated )

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

| Watch this File

File Information
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)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (22)
14 Jul 2014 Falak Shah

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'

09 Mar 2012 Cédric Devivier

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.

09 Feb 2012 Antoniuk

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 ?

13 Jul 2011 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?

13 Jul 2011 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 ?

02 May 2011 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.

02 May 2011 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)

28 Mar 2011 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!

14 Mar 2011 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

11 Mar 2011 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

20 Nov 2010 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.

20 Nov 2010 Francis  
16 Nov 2010 Joao Henriques

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

27 Oct 2010 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.

23 Jun 2010 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!

20 Apr 2010 James Hays

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

22 Dec 2009 Petter  
02 Sep 2009 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).

17 Aug 2009 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.

14 Aug 2009 Zoltan

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

14 Jul 2009 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!

20 May 2009 Eran Mukamel

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

Updates
04 Sep 2008

description update

08 Sep 2008

minor modification

Contact us