GrowCut Segmentation In Matlab
I came across a cute segmentation idea called “Grow Cut” [pdf]. This paper by Vladimir Vezhnevets and Vadim Konouchine presents a very simple idea that has very nice results. I always feel that the simplest ideas are the best! Below I give a brief description of the algorithm and link to the Matlab/C/mex code.
GrowCut Region Growing Algorithm
This algorithm is presented as an alternative to graph-cuts. The operation is very simple, and can be thought of with a biological metaphor: Imagine each image pixel is a “cell” of a certain type. These cells can be foreground, background, undefined, or others. As the algorithm proceeds, these cells compete to dominate the image domain. The ability of the cells to spread is related to the image pixel intensity.
The authors give some pseudocode that very concisely describes the algorithm.
//for every cell p
for all p in image
//copy previous state
labels_new = labels;
strength_new = strength;
// all neighbors q of p attack
for all q neighbors
if(attack_force*strength(q)>strength_new(p))
labels_new(p) = labels(q)
strength(p) = strength_new(q)
end if
end for
end for
Segmentation Results
Once implemented, this is a nice way to get segmentations. It is quite fast, and the initialization is very intuitive. Consider this picture of a lotus flower:
I made an initialization by clicking 20 points in the flower and 30 points outside. I then made a “label map” where unlabeled pixels are 0 (gray), foreground pixels are 1 (white) and background pixels are -1 (black).
Based on this simple initialization, we obtain a very decent segmentation:
As you can see, it isn’t perfect, but it is quite good. Its possible to interactively refine the seed points to improve the segmentation, but I didn’t do that here.
Matlab Code Downloads
I implemented this code in Matlab (using mex files due to the extensive use of for loops). You can download this below with compiled binaries for mac, linux, and windows. Unzip the file and run >>growcut_test for a demo.
UPDATE: I’ve fixed some bugs thanks to reader, Lin. The code works much better now!
Source & Compiled Binaries (96k) [zip]
“GrowCut” Paper [pdf]
Please let me know if you find this useful, and if you make improvements! Also, check out these related segmentation posts:
sir,
i have a question about growcut segmentation that you use lotus image for segmntation,find result
but we use that algotrithm in another image m,we will not get proper result,
sir any program setting for that we run on different image
plz send reply as early as possibl
@tariq With grow-cut you must be careful with your initializations. If at first your segmentation is incorrect, try adding some additional initialization points both inside and outside your object. As shown in the post, the ‘inside’ initialization points should have a value of 1 and the ‘outside’ initialization points should have a value of 0.
Dear sir,
From where do you get maxC? How do you know the coordinate of the seeds?
@Jhon maxC is (256)^2 which is the maximum value of the cost function. To get the coordinate of the seeds, you simply search the “seed image.”
I will learn it .
Hi Shawn,
Just a quick comment regarding maxC… if it is indeed the maximum value of the cost function, if you’re using the L2-norm in RGB space, shouldn’t the max be sqrt(3*(255^2))? I’m not sure where you got the 441 figure from… as 256^2 is 65536, unless you considered a perceptually uniform colour space, but judging from your code, it is RGB data.
In any case, that was just my two cents. Your code is actually quite good, and I actually stumbled upon this posting by accident. I was looking for something else all together, and found this GrowCut entry you made. I’m considering using it for another application I’m developing.
Thanks,
- Ray.
Hi Shawn,
Never mind about that previous post… I just didn’t bother to crunch in the number myself. Your 441 figure is in fact sqrt(3*255^2)… thanks!
@Jhon, the 441.673 figure is the greatest possible L2 norm between the darkest and brightest colours… in this case, it’s black and white, so sqrt((255-0)^2 + (255-0^2 + (255-0)^2) = sqrt(3*(255^2)) = 441.673.
Hope this helps,
- Ray.
@Ray Right-on. Thanks for answering some of these other questions, too!
Hi Shawn, i am interestied in it.
but i have some questions,like what is the “strength” ?
how do i get “strength” in this method ?
Thanks!!
I will learn it . thanks!
hello shawn,
i am very beginner at image processing. I am trying to understand your code, but to use it for other pictures, i should have another label maps. How could you assign a label map just by clicking? I didn’t understand…
thanks a lot!
hello Mr.Shawn
I tried to construct labels picture, but I found it very difficult to built labels picture for each picture I am going to segment. could you please provide me by the code to construct the labels picture just by clicking?
thanks alot.
Hi Shawn
I already got. thanks.
@azilawati
Glad you figured it out. I’ve found that the easiest way to create label maps like that is with the command
>>ginput
This lets you capture (x,y) coordinates using the mouse
Hi Shawn, I tried the algorithm and find good results for some simple images. But when applied to image with fuzzy or semi-transparent edge, the semi-transparent part was lost. How to improve this?
Hi Shawn..im doing project in Grow cut segmentation..But i need matlab code for refine the seed points to improve the segmentation..Can you guide me??
Hello sir, can u send me some more example images for my references…… please sir…….
Shawn,for gray scale image i selected maxC=360.62 as per your formula. Is it right?
@Jay
type following code to create label image.
Here nn=6 which means you can choose first 6 piexel as foreground piexel and next 6 piexel as background piexel. You can choose more piexel by changing nn value.
img=imread(‘brain.png’)
imshow(img);
nn=6;
[y,x]=ginput(nn);
hold on;
x=round(x);
y=round(y);
disp(‘Select background piexel’);
[yb,xb]=ginput(nn);
xb=round(xb);
yb=round(yb);
label1=zeros(m,n);
for i=1:nn
a1=x(i);
b1=y(i);a2=xb(i);
b2=yb(i);
label1(a2,b2)=-1;
label1(a1,b1)=1;
end
labels=double(label1);
sir,
is it possible to extract a particular cartoon character from pictures and save it without background information
good morning sir
in the GROWCUT algorithm, assert function is not present in the zip file.
can you send me the assert function for testing the algorithm please.
assert shouldn’t be needed to run the algorithm – you can just comment that out.
SIR,
Can you give me some suggestion how to segment overlapping cells using matlab
Is this the same algorithm as ‘Seeded Region Growing Segmentation’?
can growcut algorithm be used for nuclei segmentation of medical images. can this algorithm segment multiple objects or cells in a single image. can this algorithm handle overlapping of nuclei or cells.
I think you could easily modify the code to have more than two competing regions. Check the original paper – I believe the authors discuss this.
Overlapping cells would be a challenge for this algorithm. For that you may consider shape-constrained active contours.
There are many algorithms that use seeded region-growing. This one in particular plays off the idea of cellular autonomy. Not sure if it’s the same as what you’re calling, “Seeded Region Growing Segmentation.”
Hi Shawn
I think that your algorithm is just what I need to proceed in my Bachelor Thesis, but I cannot get the function to work on my Mac. When I try to run the test-script I get following error message:
??? Undefined function or method ‘growcutmex’ for input arguments of type ‘double’.
Error in ==> growcut at 29
[l s] = growcutmex(img,labels);
Error in ==> test at 8
[labels_out, strengths] = growcut(img,labels);
It appears that it cannot find growcutmex even though it is in the directory. Do you know if anyone else have had this problem when running the script on a Mac and do you have any idea to what I could do to make it work?
Thanks, Sarah
Download code from following ling: http://www.mathworks.com/matlabcentral/fileexchange/19091-growcut-image-segmentation@Sarah
Do u have C++ compiler like visual studio on your system?@Sarah
@ amit
I think that I have already downloaded all the files, but for some reason the mex file does not work. I have had this problem with another mex file and in that cases it was because I needed the *.mexmaci64 file and not just the *.mexmaci file.
I do not think that I have C++ compiler, but I must admit that I do not know for sure.
Can I get only the MATLAB CODEs (not the compiled ones) of your growcut method?
–Rgds
@Sandra the code is implemented in mex (meaning that the codes are a combination of C++ and MATLAB). If you implement GrowCut in pure-MATLAB it will be very slow because it’s highly-dependent on for loops.
All of the codes I used are provided above for download.
sir, will you please give me the steps to create the label map for different images..
hello sir,
can i know how to apply measures like local consistency error,global consistency error or rand index,variation of information etc,…which are used for measuring performance….
kindly mail me at sumanthshaan@yahoo.com
Shawn, I’ve downloaded your code and the paper you have linked to just to learn and play with the code so I can understand the theory.
What’s the difference between your grow-cut algorithm and region-growing algorithm available in Matlab file exchange?
http://www.mathworks.com/matlabcentral/fileexchange/19084-region-growing/content/regiongrowing.m
Sorry, if my question seem stupid as I’m totally new to image processing & vision. I’ll learn your code and possibly try and port it into Java.
Hi – Not sure how the Matlab codes work, but the GrowCut algorithm uses seeding in a unique way that (in my experience) produces better results than the build-in Matlab function. It also provides the opportunity to build in new “similarity” measures (beyond color similarity). For instance you could extend this method to compare tensors, textures, etc. Hope that’s helpful.
Hello Shawn , i am a beginner in Image Processing .Would you please explain me what line number and paragraph of code in “glowcutmex.cpp” should be edit and what the purpose of each editing , if i need to take glow-cut segmentation with another image
Pardon for my poor english and thank you for your kind.
Knotto.