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!

Please let me know if you find this useful, and if you make improvements! Also, check out these related segmentation posts:

## 58 thoughts on “GrowCut Segmentation In Matlab”

1. Anonymous says:

@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,[]);
========================================================

James :
OH~ I will try to do that. Thanks!

Shawn Lankton :
Make sure the type of your labels image can support negative numbers. For example, a signed int

2. Anonymous says:

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,[]);
========================================================

3. deep says:

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

4. pavan patil says:

@Sarah
can u explain the idea in growcutmex.cpp part

5. nazma says:

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

6. Crystal says:

I dont’t know how to get the “label map”,can you tell me?

7. mohammed says:

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