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.