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!