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:
@James
Thanks Shawn,Amit for your good code!!
I guess I figure out the trick of saving label image. Now it seems can save the ‘proper’ label image.
================================================
% Clear All %
clc; clear all; close all;
%img=imread(‘brain.png’);
img=imread(‘20130423_150526.jpg’);
figure(‘name’,’Input Image’);imshow(img);
imgGray=rgb2gray(img);
figure(‘name’,’Gray Image’);imshow(imgGray);
[m,n]=size(imgGray);
nn=6;
disp(‘Select foreground piexel’);
[y,x]=ginput(nn);
hold on;
x=round(x);%foreground
y=round(y);
disp(‘Select background piexel’);
[yb,xb]=ginput(nn);
xb=round(xb);%background
yb=round(yb);
label1=zeros(m,n);
for i=1:nn
a1=x(i);%foreground
b1=y(i);
a2=xb(i);%background
b2=yb(i);
label1(a1,b1)=1;%foreground %
label1(a2,b2)=-1;%background %
end
labels=double(label1+2);
figure(‘name’,’labels Image’);imshow(labels,[]);
imwrite(labels,gray,’BD_label22.tif’);
imgLabel=double(imread(‘BD_label22.tif’));
figure(‘name’,’Read Label Image’);imshow(imgLabel,[]);
% Convert back to -1,0,1 range %
imgLabelC=imgLabel-1;
figure(‘name’,’Read Label Image Convert to -1,0,1 range’);imshow(imgLabelC,[]);
========================================================
Thanks Shawn,Amit for your good code!!
I guess I figure out the trick of saving label image. Now it seems can save the ‘proper’ label image.
================================================
% Clear All %
clc; clear all; close all;
%img=imread(‘brain.png’);
img=imread(‘20130423_150526.jpg’);
figure(‘name’,’Input Image’);imshow(img);
imgGray=rgb2gray(img);
figure(‘name’,’Gray Image’);imshow(imgGray);
[m,n]=size(imgGray);
nn=6;
disp(‘Select foreground piexel’);
[y,x]=ginput(nn);
hold on;
x=round(x);%foreground
y=round(y);
disp(‘Select background piexel’);
[yb,xb]=ginput(nn);
xb=round(xb);%background
yb=round(yb);
label1=zeros(m,n);
for i=1:nn
a1=x(i);%foreground
b1=y(i);
a2=xb(i);%background
b2=yb(i);
label1(a1,b1)=1;%foreground %
label1(a2,b2)=-1;%background %
end
labels=double(label1+2);
figure(‘name’,’labels Image’);imshow(labels,[]);
imwrite(labels,gray,’BD_label22.tif’);
imgLabel=double(imread(‘BD_label22.tif’));
figure(‘name’,’Read Label Image’);imshow(imgLabel,[]);
% Convert back to -1,0,1 range %
imgLabelC=imgLabel-1;
figure(‘name’,’Read Label Image Convert to -1,0,1 range’);imshow(imgLabelC,[]);
========================================================
hi Shawn,
i was trying to find the accuracy of the growcut algorithm, will u pls help me to plot a bar graph of the result of this code
@Sarah
can u explain the idea in growcutmex.cpp part
i download this folder Source & Compiled Binaries (96k) [zip]. but unable to compile. There is difficulty to access some file growcutmex, growcutmex.mexmaci,test.m,test_data.mat. please help
I dont’t know how to get the “label map”,can you tell me?
hello Shawn Lankton
i would like first to thank you for the release. when i run the code using Matlab 2012b I had this error
message Error: Could not detect a compiler on local system
which can compile the specified input file(s)
Error using mex (line 206)
Unable to complete successfully.
Error in growcut (line 37)
mex growcutmex.cpp;
Error in growcut_test (line 12)
[labels_out, strengths] = growcut(img,labels);
how can i do to solve the problem.
for notice i got the code from this URL
http://www.mathworks.com/matlabcentral/fileexchange/19091-growcut-image-segmentation
Hi,
the link with PDF does not work:
http://graphics.cs.msu.su/en/publications/text/gc2005vk.pdf
Where can I read the article?
Best, Adam.